36 #ifndef VIGRA_SEEDEDREGIONGROWING_HXX
37 #define VIGRA_SEEDEDREGIONGROWING_HXX
42 #include "utilities.hxx"
43 #include "stdimage.hxx"
44 #include "stdimagefunctions.hxx"
45 #include "pixelneighborhood.hxx"
55 Point2D location_, nearest_;
62 : location_(0,0), nearest_(0,0), cost_(0), count_(0), label_(0)
65 SeedRgPixel(Point2D
const & location, Point2D
const & nearest,
66 COST
const & cost,
int const & count,
int const & label)
67 : location_(location), nearest_(nearest),
68 cost_(cost), count_(count), label_(label)
70 int dx = location_.x - nearest_.x;
71 int dy = location_.y - nearest_.y;
72 dist_ = dx * dx + dy * dy;
75 void set(Point2D
const & location, Point2D
const & nearest,
76 COST
const & cost,
int const & count,
int const & label)
84 int dx = location_.x - nearest_.x;
85 int dy = location_.y - nearest_.y;
86 dist_ = dx * dx + dy * dy;
92 bool operator()(SeedRgPixel
const & l,
93 SeedRgPixel
const & r)
const
95 if(r.cost_ == l.cost_)
97 if(r.dist_ == l.dist_)
return r.count_ < l.count_;
99 return r.dist_ < l.dist_;
102 return r.cost_ < l.cost_;
104 bool operator()(SeedRgPixel
const * l,
105 SeedRgPixel
const * r)
const
107 if(r->cost_ == l->cost_)
109 if(r->dist_ == l->dist_)
return r->count_ < l->count_;
111 return r->dist_ < l->dist_;
114 return r->cost_ < l->cost_;
122 while(!freelist_.empty())
124 delete freelist_.top();
130 create(Point2D
const & location, Point2D
const & nearest,
131 COST
const & cost,
int const & count,
int const & label)
133 if(!freelist_.empty())
135 SeedRgPixel * res = freelist_.top();
137 res->set(location, nearest, cost, count, label);
141 return new SeedRgPixel(location, nearest, cost, count, label);
144 void dismiss(SeedRgPixel * p)
149 std::stack<SeedRgPixel<COST> *> freelist_;
153 struct UnlabelWatersheds
155 int operator()(
int label)
const
157 return label < 0 ? 0 : label;
163 enum SRGType { CompleteGrow = 0, KeepContours = 1, StopAtThreshold = 2, SRGWatershedLabel = -1 };
365 template <
class SrcImageIterator,
class SrcAccessor,
366 class SeedImageIterator,
class SeedAccessor,
367 class DestImageIterator,
class DestAccessor,
368 class RegionStatisticsArray,
class Neighborhood>
370 SrcImageIterator srclr, SrcAccessor as,
371 SeedImageIterator seedsul, SeedAccessor aseeds,
372 DestImageIterator destul, DestAccessor ad,
373 RegionStatisticsArray & stats,
378 int w = srclr.x - srcul.x;
379 int h = srclr.y - srcul.y;
382 SrcImageIterator isy = srcul, isx = srcul;
384 typedef typename RegionStatisticsArray::value_type RegionStatistics;
385 typedef typename RegionStatistics::cost_type CostType;
386 typedef detail::SeedRgPixel<CostType> Pixel;
388 typename Pixel::Allocator allocator;
390 typedef std::priority_queue<Pixel *, std::vector<Pixel *>,
391 typename Pixel::Compare> SeedRgPixelHeap;
399 copyImage(seedsul, seedsul+Diff2D(w,h), aseeds, ir, regions.accessor());
403 SeedRgPixelHeap pheap;
406 typedef typename Neighborhood::Direction
Direction;
407 int directionCount = Neighborhood::DirectionCount;
410 for(isy=srcul, iry=ir, pos.y=0; pos.y<h;
411 ++pos.y, ++isy.y, ++iry.y)
413 for(isx=isy, irx=iry, pos.x=0; pos.x<w;
414 ++pos.x, ++isx.x, ++irx.x)
419 for(
int i=0; i<directionCount; i++)
422 cneighbor = irx[Neighborhood::diff((Direction)i)];
425 CostType cost = stats[cneighbor].cost(as(isx));
428 allocator.create(pos, pos+Neighborhood::diff((Direction)i), cost, count++, cneighbor);
437 while(pheap.size() != 0)
439 Pixel * pixel = pheap.top();
442 Point2D pos = pixel->location_;
443 Point2D nearest = pixel->nearest_;
444 int lab = pixel->label_;
445 CostType cost = pixel->cost_;
447 allocator.dismiss(pixel);
449 if((srgType & StopAtThreshold) != 0 && cost > max_cost)
458 if((srgType & KeepContours) != 0)
460 for(
int i=0; i<directionCount; i++)
462 cneighbor = irx[Neighborhood::diff((Direction)i)];
463 if((cneighbor>0) && (cneighbor != lab))
465 lab = SRGWatershedLabel;
473 if((srgType & KeepContours) == 0 || lab > 0)
476 stats[*irx](as(isx));
480 for(
int i=0; i<directionCount; i++)
482 if(irx[Neighborhood::diff((Direction)i)] == 0)
484 CostType cost = stats[lab].cost(as(isx, Neighborhood::diff((Direction)i)));
487 allocator.create(pos+Neighborhood::diff((Direction)i), nearest, cost, count++, lab);
488 pheap.push(new_pixel);
495 while(pheap.size() != 0)
497 allocator.dismiss(pheap.top());
502 transformImage(ir, ir+Point2D(w,h), regions.accessor(), destul, ad,
503 detail::UnlabelWatersheds());
506 template <
class SrcImageIterator,
class SrcAccessor,
507 class SeedImageIterator,
class SeedAccessor,
508 class DestImageIterator,
class DestAccessor,
509 class RegionStatisticsArray,
class Neighborhood>
512 SrcImageIterator srclr, SrcAccessor as,
513 SeedImageIterator seedsul, SeedAccessor aseeds,
514 DestImageIterator destul, DestAccessor ad,
515 RegionStatisticsArray & stats,
522 stats, srgType, n, NumericTraits<double>::max());
527 template <
class SrcImageIterator,
class SrcAccessor,
528 class SeedImageIterator,
class SeedAccessor,
529 class DestImageIterator,
class DestAccessor,
530 class RegionStatisticsArray>
533 SrcImageIterator srclr, SrcAccessor as,
534 SeedImageIterator seedsul, SeedAccessor aseeds,
535 DestImageIterator destul, DestAccessor ad,
536 RegionStatisticsArray & stats,
545 template <
class SrcImageIterator,
class SrcAccessor,
546 class SeedImageIterator,
class SeedAccessor,
547 class DestImageIterator,
class DestAccessor,
548 class RegionStatisticsArray>
551 SrcImageIterator srclr, SrcAccessor as,
552 SeedImageIterator seedsul, SeedAccessor aseeds,
553 DestImageIterator destul, DestAccessor ad,
554 RegionStatisticsArray & stats)
559 stats, CompleteGrow);
562 template <
class SrcImageIterator,
class SrcAccessor,
563 class SeedImageIterator,
class SeedAccessor,
564 class DestImageIterator,
class DestAccessor,
565 class RegionStatisticsArray,
class Neighborhood>
568 pair<SeedImageIterator, SeedAccessor> img3,
569 pair<DestImageIterator, DestAccessor> img4,
570 RegionStatisticsArray & stats,
576 img3.first, img3.second,
577 img4.first, img4.second,
578 stats, srgType, n, max_cost);
581 template <
class SrcImageIterator,
class SrcAccessor,
582 class SeedImageIterator,
class SeedAccessor,
583 class DestImageIterator,
class DestAccessor,
584 class RegionStatisticsArray,
class Neighborhood>
587 pair<SeedImageIterator, SeedAccessor> img3,
588 pair<DestImageIterator, DestAccessor> img4,
589 RegionStatisticsArray & stats,
594 img3.first, img3.second,
595 img4.first, img4.second,
596 stats, srgType, n, NumericTraits<double>::max());
599 template <
class SrcImageIterator,
class SrcAccessor,
600 class SeedImageIterator,
class SeedAccessor,
601 class DestImageIterator,
class DestAccessor,
602 class RegionStatisticsArray>
605 pair<SeedImageIterator, SeedAccessor> img3,
606 pair<DestImageIterator, DestAccessor> img4,
607 RegionStatisticsArray & stats,
611 img3.first, img3.second,
612 img4.first, img4.second,
616 template <
class SrcImageIterator,
class SrcAccessor,
617 class SeedImageIterator,
class SeedAccessor,
618 class DestImageIterator,
class DestAccessor,
619 class RegionStatisticsArray>
622 pair<SeedImageIterator, SeedAccessor> img3,
623 pair<DestImageIterator, DestAccessor> img4,
624 RegionStatisticsArray & stats)
627 img3.first, img3.second,
628 img4.first, img4.second,
629 stats, CompleteGrow);
653 template <
class Value>
690 #endif // VIGRA_SEEDEDREGIONGROWING_HXX