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"
46 #include "bucket_queue.hxx"
56 Point2D location_, nearest_;
63 : location_(0,0), nearest_(0,0), cost_(0), count_(0), label_(0)
66 SeedRgPixel(Point2D
const & location, Point2D
const & nearest,
67 COST
const & cost,
int const & count,
int const & label)
68 : location_(location), nearest_(nearest),
69 cost_(cost), count_(count), label_(label)
71 int dx = location_.x - nearest_.x;
72 int dy = location_.y - nearest_.y;
73 dist_ = dx * dx + dy * dy;
76 void set(Point2D
const & location, Point2D
const & nearest,
77 COST
const & cost,
int const & count,
int const & label)
85 int dx = location_.x - nearest_.x;
86 int dy = location_.y - nearest_.y;
87 dist_ = dx * dx + dy * dy;
93 bool operator()(SeedRgPixel
const & l,
94 SeedRgPixel
const & r)
const
96 if(r.cost_ == l.cost_)
98 if(r.dist_ == l.dist_)
return r.count_ < l.count_;
100 return r.dist_ < l.dist_;
103 return r.cost_ < l.cost_;
105 bool operator()(SeedRgPixel
const * l,
106 SeedRgPixel
const * r)
const
108 if(r->cost_ == l->cost_)
110 if(r->dist_ == l->dist_)
return r->count_ < l->count_;
112 return r->dist_ < l->dist_;
115 return r->cost_ < l->cost_;
123 while(!freelist_.empty())
125 delete freelist_.top();
131 create(Point2D
const & location, Point2D
const & nearest,
132 COST
const & cost,
int const & count,
int const & label)
134 if(!freelist_.empty())
136 SeedRgPixel * res = freelist_.top();
138 res->set(location, nearest, cost, count, label);
142 return new SeedRgPixel(location, nearest, cost, count, label);
145 void dismiss(SeedRgPixel * p)
150 std::stack<SeedRgPixel<COST> *> freelist_;
154 struct UnlabelWatersheds
156 int operator()(
int label)
const
158 return label < 0 ? 0 : label;
180 SRGWatershedLabel = -1
374 template <
class SrcIterator,
class SrcAccessor,
375 class SeedImageIterator,
class SeedAccessor,
376 class DestIterator,
class DestAccessor,
377 class RegionStatisticsArray,
class Neighborhood>
378 typename SeedAccessor::value_type
380 SrcIterator srclr, SrcAccessor as,
381 SeedImageIterator seedsul, SeedAccessor aseeds,
382 DestIterator destul, DestAccessor ad,
383 RegionStatisticsArray & stats,
388 int w = srclr.x - srcul.x;
389 int h = srclr.y - srcul.y;
392 SrcIterator isy = srcul, isx = srcul;
394 typedef typename SeedAccessor::value_type LabelType;
395 typedef typename RegionStatisticsArray::value_type RegionStatistics;
396 typedef typename RegionStatistics::cost_type CostType;
397 typedef detail::SeedRgPixel<CostType> Pixel;
399 typename Pixel::Allocator allocator;
401 typedef std::priority_queue<Pixel *, std::vector<Pixel *>,
402 typename Pixel::Compare> SeedRgPixelHeap;
410 copyImage(seedsul, seedsul+Diff2D(w,h), aseeds, ir, regions.accessor());
414 SeedRgPixelHeap pheap;
415 int cneighbor, maxRegionLabel = 0;
417 typedef typename Neighborhood::Direction Direction;
418 int directionCount = Neighborhood::DirectionCount;
421 for(isy=srcul, iry=ir, pos.y=0; pos.y<h;
422 ++pos.y, ++isy.y, ++iry.y)
424 for(isx=isy, irx=iry, pos.x=0; pos.x<w;
425 ++pos.x, ++isx.x, ++irx.x)
430 for(
int i=0; i<directionCount; i++)
433 cneighbor = irx[Neighborhood::diff((Direction)i)];
436 CostType cost = stats[cneighbor].cost(as(isx));
439 allocator.create(pos, pos+Neighborhood::diff((Direction)i), cost, count++, cneighbor);
446 vigra_precondition((LabelType)*irx <= stats.maxRegionLabel(),
447 "seededRegionGrowing(): Largest label exceeds size of RegionStatisticsArray.");
448 if(maxRegionLabel < *irx)
449 maxRegionLabel = *irx;
455 while(pheap.size() != 0)
457 Pixel * pixel = pheap.top();
460 Point2D pos = pixel->location_;
461 Point2D nearest = pixel->nearest_;
462 int lab = pixel->label_;
463 CostType cost = pixel->cost_;
465 allocator.dismiss(pixel);
467 if((srgType & StopAtThreshold) != 0 && cost > max_cost)
476 if((srgType & KeepContours) != 0)
478 for(
int i=0; i<directionCount; i++)
480 cneighbor = irx[Neighborhood::diff((Direction)i)];
481 if((cneighbor>0) && (cneighbor != lab))
483 lab = SRGWatershedLabel;
491 if((srgType & KeepContours) == 0 || lab > 0)
494 stats[*irx](as(isx));
498 for(
int i=0; i<directionCount; i++)
500 if(irx[Neighborhood::diff((Direction)i)] == 0)
502 CostType cost = stats[lab].cost(as(isx, Neighborhood::diff((Direction)i)));
505 allocator.create(pos+Neighborhood::diff((Direction)i), nearest, cost, count++, lab);
506 pheap.push(new_pixel);
513 while(pheap.size() != 0)
515 allocator.dismiss(pheap.top());
520 transformImage(ir, ir+Point2D(w,h), regions.accessor(), destul, ad,
521 detail::UnlabelWatersheds());
523 return (LabelType)maxRegionLabel;
526 template <
class SrcIterator,
class SrcAccessor,
527 class SeedImageIterator,
class SeedAccessor,
528 class DestIterator,
class DestAccessor,
529 class RegionStatisticsArray,
class Neighborhood>
530 inline typename SeedAccessor::value_type
532 SrcIterator srclr, SrcAccessor as,
533 SeedImageIterator seedsul, SeedAccessor aseeds,
534 DestIterator destul, DestAccessor ad,
535 RegionStatisticsArray & stats,
542 stats, srgType, n, NumericTraits<double>::max());
547 template <
class SrcIterator,
class SrcAccessor,
548 class SeedImageIterator,
class SeedAccessor,
549 class DestIterator,
class DestAccessor,
550 class RegionStatisticsArray>
551 inline typename SeedAccessor::value_type
553 SrcIterator srclr, SrcAccessor as,
554 SeedImageIterator seedsul, SeedAccessor aseeds,
555 DestIterator destul, DestAccessor ad,
556 RegionStatisticsArray & stats,
565 template <
class SrcIterator,
class SrcAccessor,
566 class SeedImageIterator,
class SeedAccessor,
567 class DestIterator,
class DestAccessor,
568 class RegionStatisticsArray>
569 inline typename SeedAccessor::value_type
571 SrcIterator srclr, SrcAccessor as,
572 SeedImageIterator seedsul, SeedAccessor aseeds,
573 DestIterator destul, DestAccessor ad,
574 RegionStatisticsArray & stats)
579 stats, CompleteGrow);
582 template <
class SrcIterator,
class SrcAccessor,
583 class SeedImageIterator,
class SeedAccessor,
584 class DestIterator,
class DestAccessor,
585 class RegionStatisticsArray,
class Neighborhood>
586 inline typename SeedAccessor::value_type
588 pair<SeedImageIterator, SeedAccessor> img3,
589 pair<DestIterator, DestAccessor> img4,
590 RegionStatisticsArray & stats,
596 img3.first, img3.second,
597 img4.first, img4.second,
598 stats, srgType, n, max_cost);
601 template <
class SrcIterator,
class SrcAccessor,
602 class SeedImageIterator,
class SeedAccessor,
603 class DestIterator,
class DestAccessor,
604 class RegionStatisticsArray,
class Neighborhood>
605 inline typename SeedAccessor::value_type
607 pair<SeedImageIterator, SeedAccessor> img3,
608 pair<DestIterator, DestAccessor> img4,
609 RegionStatisticsArray & stats,
614 img3.first, img3.second,
615 img4.first, img4.second,
616 stats, srgType, n, NumericTraits<double>::max());
619 template <
class SrcIterator,
class SrcAccessor,
620 class SeedImageIterator,
class SeedAccessor,
621 class DestIterator,
class DestAccessor,
622 class RegionStatisticsArray>
623 inline typename SeedAccessor::value_type
625 pair<SeedImageIterator, SeedAccessor> img3,
626 pair<DestIterator, DestAccessor> img4,
627 RegionStatisticsArray & stats,
631 img3.first, img3.second,
632 img4.first, img4.second,
636 template <
class SrcIterator,
class SrcAccessor,
637 class SeedImageIterator,
class SeedAccessor,
638 class DestIterator,
class DestAccessor,
639 class RegionStatisticsArray>
640 inline typename SeedAccessor::value_type
642 pair<SeedImageIterator, SeedAccessor> img3,
643 pair<DestIterator, DestAccessor> img4,
644 RegionStatisticsArray & stats)
647 img3.first, img3.second,
648 img4.first, img4.second,
649 stats, CompleteGrow);
652 template <
class SrcIterator,
class SrcAccessor,
653 class DestIterator,
class DestAccessor,
654 class RegionStatisticsArray,
class Neighborhood>
655 typename DestAccessor::value_type
656 fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
657 DestIterator destul, DestAccessor ad,
658 RegionStatisticsArray & stats,
662 std::ptrdiff_t bucket_count = 256)
664 typedef typename DestAccessor::value_type LabelType;
666 vigra_precondition((srgType & KeepContours) == 0,
667 "fastSeededRegionGrowing(): the turbo algorithm doesn't support 'KeepContours', sorry.");
669 int w = srclr.x - srcul.x;
670 int h = srclr.y - srcul.y;
672 SrcIterator isy = srcul, isx = srcul;
673 DestIterator idy = destul, idx = destul;
675 BucketQueue<Point2D, true> pqueue(bucket_count);
676 LabelType maxRegionLabel = 0;
679 for(isy=srcul, idy = destul, pos.y=0; pos.y<h; ++pos.y, ++isy.y, ++idy.y)
681 for(isx=isy, idx=idy, pos.x=0; pos.x<w; ++pos.x, ++isx.x, ++idx.x)
683 LabelType label = ad(idx);
686 vigra_precondition(label <= stats.maxRegionLabel(),
687 "fastSeededRegionGrowing(): Largest label exceeds size of RegionStatisticsArray.");
689 if(maxRegionLabel < label)
690 maxRegionLabel = label;
695 NeighborhoodCirculator<DestIterator, Neighborhood> c(idx), cend(c);
700 std::ptrdiff_t priority = (std::ptrdiff_t)stats[label].cost(as(isx));
701 pqueue.push(pos, priority);
709 RestrictedNeighborhoodCirculator<DestIterator, Neighborhood>
710 c(idx, atBorder), cend(c);
715 std::ptrdiff_t priority = (std::ptrdiff_t)stats[label].cost(as(isx));
716 pqueue.push(pos, priority);
727 while(!pqueue.empty())
729 Point2D pos = pqueue.top();
730 std::ptrdiff_t cost = pqueue.topPriority();
733 if((srgType & StopAtThreshold) != 0 && cost > max_cost)
739 std::ptrdiff_t label = ad(idx);
744 NeighborhoodCirculator<DestIterator, Neighborhood> c(idx), cend(c);
748 std::ptrdiff_t nlabel = ad(c);
751 ad.set(label, idx, c.diff());
752 std::ptrdiff_t priority =
753 std::max((std::ptrdiff_t)stats[label].cost(as(isx, c.diff())), cost);
754 pqueue.push(pos+c.diff(), priority);
761 RestrictedNeighborhoodCirculator<DestIterator, Neighborhood>
762 c(idx, atBorder), cend(c);
765 std::ptrdiff_t nlabel = ad(c);
768 ad.set(label, idx, c.diff());
769 std::ptrdiff_t priority =
770 std::max((std::ptrdiff_t)stats[label].cost(as(isx, c.diff())), cost);
771 pqueue.push(pos+c.diff(), priority);
778 return maxRegionLabel;
781 template <
class SrcIterator,
class SrcAccessor,
782 class DestIterator,
class DestAccessor,
783 class RegionStatisticsArray,
class Neighborhood>
784 inline typename DestAccessor::value_type
785 fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
786 DestIterator destul, DestAccessor ad,
787 RegionStatisticsArray & stats,
791 return fastSeededRegionGrowing(srcul, srclr, as,
793 stats, srgType, n, NumericTraits<double>::max(), 256);
796 template <
class SrcIterator,
class SrcAccessor,
797 class DestIterator,
class DestAccessor,
798 class RegionStatisticsArray>
799 inline typename DestAccessor::value_type
800 fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
801 DestIterator destul, DestAccessor ad,
802 RegionStatisticsArray & stats,
805 return fastSeededRegionGrowing(srcul, srclr, as,
810 template <
class SrcIterator,
class SrcAccessor,
811 class DestIterator,
class DestAccessor,
812 class RegionStatisticsArray>
813 inline typename DestAccessor::value_type
814 fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
815 DestIterator destul, DestAccessor ad,
816 RegionStatisticsArray & stats)
818 return fastSeededRegionGrowing(srcul, srclr, as,
820 stats, CompleteGrow);
823 template <
class SrcIterator,
class SrcAccessor,
824 class DestIterator,
class DestAccessor,
825 class RegionStatisticsArray,
class Neighborhood>
826 inline typename DestAccessor::value_type
827 fastSeededRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> src,
828 pair<DestIterator, DestAccessor> dest,
829 RegionStatisticsArray & stats,
833 std::ptrdiff_t bucket_count = 256)
835 return fastSeededRegionGrowing(src.first, src.second, src.third,
836 dest.first, dest.second,
837 stats, srgType, n, max_cost, bucket_count);
861 template <
class Value>
898 #endif // VIGRA_SEEDEDREGIONGROWING_HXX
Value result_type
Definition: seededregiongrowing.hxx:872
void seededRegionGrowing(...)
Region Segmentation by means of Seeded Region Growing.
AtImageBorder
Encode whether a point is near the image border.
Definition: pixelneighborhood.hxx:68
AtImageBorder isAtImageBorder(int x, int y, int width, int height)
Find out whether a point is at the image border.
Definition: pixelneighborhood.hxx:111
Statistics functor to be used for seeded region growing.
Definition: seededregiongrowing.hxx:862
SRGType
Definition: seededregiongrowing.hxx:176
Value cost_type
Definition: seededregiongrowing.hxx:880
BasicImageIterator< PIXELTYPE, PIXELTYPE ** > Iterator
Definition: basicimage.hxx:530
void operator()(argument_type const &) const
Definition: seededregiongrowing.hxx:884
Value value_type
Definition: seededregiongrowing.hxx:876
void copyImage(...)
Copy source image into destination image.
Value argument_type
Definition: seededregiongrowing.hxx:867
FourNeighborhood::NeighborCode FourNeighborCode
Definition: pixelneighborhood.hxx:356
Definition: pixelneighborhood.hxx:70
void initImageBorder(...)
Write value to the specified border pixels in the image.
cost_type const & cost(argument_type const &v) const
Definition: seededregiongrowing.hxx:888
BasicImage< Int32 > IImage
Definition: stdimage.hxx:116