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"
47 #include "multi_shape.hxx"
57 Point2D location_, nearest_;
64 : location_(0,0), nearest_(0,0), cost_(0), count_(0), label_(0)
67 SeedRgPixel(Point2D
const & location, Point2D
const & nearest,
68 COST
const & cost,
int const & count,
int const & label)
69 : location_(location), nearest_(nearest),
70 cost_(cost), count_(count), label_(label)
72 int dx = location_.x - nearest_.x;
73 int dy = location_.y - nearest_.y;
74 dist_ = dx * dx + dy * dy;
77 void set(Point2D
const & location, Point2D
const & nearest,
78 COST
const & cost,
int const & count,
int const & label)
86 int dx = location_.x - nearest_.x;
87 int dy = location_.y - nearest_.y;
88 dist_ = dx * dx + dy * dy;
94 bool operator()(SeedRgPixel
const & l,
95 SeedRgPixel
const & r)
const
97 if(r.cost_ == l.cost_)
99 if(r.dist_ == l.dist_)
return r.count_ < l.count_;
101 return r.dist_ < l.dist_;
104 return r.cost_ < l.cost_;
106 bool operator()(SeedRgPixel
const * l,
107 SeedRgPixel
const * r)
const
109 if(r->cost_ == l->cost_)
111 if(r->dist_ == l->dist_)
return r->count_ < l->count_;
113 return r->dist_ < l->dist_;
116 return r->cost_ < l->cost_;
124 while(!freelist_.empty())
126 delete freelist_.top();
132 create(Point2D
const & location, Point2D
const & nearest,
133 COST
const & cost,
int const & count,
int const & label)
135 if(!freelist_.empty())
137 SeedRgPixel * res = freelist_.top();
139 res->set(location, nearest, cost, count, label);
143 return new SeedRgPixel(location, nearest, cost, count, label);
146 void dismiss(SeedRgPixel * p)
151 std::stack<SeedRgPixel<COST> *> freelist_;
155 struct UnlabelWatersheds
157 int operator()(
int label)
const
159 return label < 0 ? 0 : label;
181 SRGWatershedLabel = -1
415 template <
class SrcIterator,
class SrcAccessor,
416 class SeedImageIterator,
class SeedAccessor,
417 class DestIterator,
class DestAccessor,
418 class RegionStatisticsArray,
class Neighborhood>
419 typename SeedAccessor::value_type
421 SrcIterator srclr, SrcAccessor as,
422 SeedImageIterator seedsul, SeedAccessor aseeds,
423 DestIterator destul, DestAccessor ad,
424 RegionStatisticsArray & stats,
429 int w = srclr.x - srcul.x;
430 int h = srclr.y - srcul.y;
433 SrcIterator isy = srcul, isx = srcul;
435 typedef typename SeedAccessor::value_type LabelType;
436 typedef typename RegionStatisticsArray::value_type RegionStatistics;
437 typedef typename RegionStatistics::cost_type CostType;
438 typedef detail::SeedRgPixel<CostType> Pixel;
440 typename Pixel::Allocator allocator;
442 typedef std::priority_queue<Pixel *, std::vector<Pixel *>,
443 typename Pixel::Compare> SeedRgPixelHeap;
451 copyImage(seedsul, seedsul+Diff2D(w,h), aseeds, ir, regions.accessor());
455 SeedRgPixelHeap pheap;
456 int cneighbor, maxRegionLabel = 0;
458 typedef typename Neighborhood::Direction Direction;
459 int directionCount = Neighborhood::DirectionCount;
462 for(isy=srcul, iry=ir, pos.y=0; pos.y<h;
463 ++pos.y, ++isy.y, ++iry.y)
465 for(isx=isy, irx=iry, pos.x=0; pos.x<w;
466 ++pos.x, ++isx.x, ++irx.x)
471 for(
int i=0; i<directionCount; i++)
474 cneighbor = irx[Neighborhood::diff((Direction)i)];
477 CostType cost = stats[cneighbor].cost(as(isx));
480 allocator.create(pos, pos+Neighborhood::diff((Direction)i), cost, count++, cneighbor);
487 vigra_precondition((LabelType)*irx <= stats.maxRegionLabel(),
488 "seededRegionGrowing(): Largest label exceeds size of RegionStatisticsArray.");
489 if(maxRegionLabel < *irx)
490 maxRegionLabel = *irx;
496 while(pheap.size() != 0)
498 Pixel * pixel = pheap.top();
501 Point2D pos = pixel->location_;
502 Point2D nearest = pixel->nearest_;
503 int lab = pixel->label_;
504 CostType cost = pixel->cost_;
506 allocator.dismiss(pixel);
508 if((srgType & StopAtThreshold) != 0 && cost > max_cost)
517 if((srgType & KeepContours) != 0)
519 for(
int i=0; i<directionCount; i++)
521 cneighbor = irx[Neighborhood::diff((Direction)i)];
522 if((cneighbor>0) && (cneighbor != lab))
524 lab = SRGWatershedLabel;
532 if((srgType & KeepContours) == 0 || lab > 0)
535 stats[*irx](as(isx));
539 for(
int i=0; i<directionCount; i++)
541 if(irx[Neighborhood::diff((Direction)i)] == 0)
543 CostType cost = stats[lab].cost(as(isx, Neighborhood::diff((Direction)i)));
546 allocator.create(pos+Neighborhood::diff((Direction)i), nearest, cost, count++, lab);
547 pheap.push(new_pixel);
554 while(pheap.size() != 0)
556 allocator.dismiss(pheap.top());
561 transformImage(ir, ir+Point2D(w,h), regions.accessor(), destul, ad,
562 detail::UnlabelWatersheds());
564 return (LabelType)maxRegionLabel;
567 template <
class SrcIterator,
class SrcAccessor,
568 class SeedImageIterator,
class SeedAccessor,
569 class DestIterator,
class DestAccessor,
570 class RegionStatisticsArray,
class Neighborhood>
571 inline typename SeedAccessor::value_type
573 SrcIterator srclr, SrcAccessor as,
574 SeedImageIterator seedsul, SeedAccessor aseeds,
575 DestIterator destul, DestAccessor ad,
576 RegionStatisticsArray & stats,
583 stats, srgType, n, NumericTraits<double>::max());
588 template <
class SrcIterator,
class SrcAccessor,
589 class SeedImageIterator,
class SeedAccessor,
590 class DestIterator,
class DestAccessor,
591 class RegionStatisticsArray>
592 inline typename SeedAccessor::value_type
594 SrcIterator srclr, SrcAccessor as,
595 SeedImageIterator seedsul, SeedAccessor aseeds,
596 DestIterator destul, DestAccessor ad,
597 RegionStatisticsArray & stats,
606 template <
class SrcIterator,
class SrcAccessor,
607 class SeedImageIterator,
class SeedAccessor,
608 class DestIterator,
class DestAccessor,
609 class RegionStatisticsArray>
610 inline typename SeedAccessor::value_type
612 SrcIterator srclr, SrcAccessor as,
613 SeedImageIterator seedsul, SeedAccessor aseeds,
614 DestIterator destul, DestAccessor ad,
615 RegionStatisticsArray & stats)
620 stats, CompleteGrow);
623 template <
class SrcIterator,
class SrcAccessor,
624 class SeedImageIterator,
class SeedAccessor,
625 class DestIterator,
class DestAccessor,
626 class RegionStatisticsArray,
class Neighborhood>
627 inline typename SeedAccessor::value_type
629 pair<SeedImageIterator, SeedAccessor> img3,
630 pair<DestIterator, DestAccessor> img4,
631 RegionStatisticsArray & stats,
634 double max_cost = NumericTraits<double>::max())
637 img3.first, img3.second,
638 img4.first, img4.second,
639 stats, srgType, n, max_cost);
642 template <
class SrcIterator,
class SrcAccessor,
643 class SeedImageIterator,
class SeedAccessor,
644 class DestIterator,
class DestAccessor,
645 class RegionStatisticsArray>
646 inline typename SeedAccessor::value_type
648 pair<SeedImageIterator, SeedAccessor> img3,
649 pair<DestIterator, DestAccessor> img4,
650 RegionStatisticsArray & stats,
654 img3.first, img3.second,
655 img4.first, img4.second,
659 template <
class SrcIterator,
class SrcAccessor,
660 class SeedImageIterator,
class SeedAccessor,
661 class DestIterator,
class DestAccessor,
662 class RegionStatisticsArray>
663 inline typename SeedAccessor::value_type
665 pair<SeedImageIterator, SeedAccessor> img3,
666 pair<DestIterator, DestAccessor> img4,
667 RegionStatisticsArray & stats)
670 img3.first, img3.second,
671 img4.first, img4.second,
672 stats, CompleteGrow);
675 template <
class T1,
class S1,
678 class RegionStatisticsArray,
class Neighborhood>
681 MultiArrayView<2, TS, AS>
const & img3,
682 MultiArrayView<2, T2, S2> img4,
683 RegionStatisticsArray & stats,
686 double max_cost = NumericTraits<double>::max())
688 vigra_precondition(img1.shape() == img3.shape(),
689 "seededRegionGrowing(): shape mismatch between input and output.");
693 stats, srgType, n, max_cost);
696 template <
class T1,
class S1,
699 class RegionStatisticsArray>
702 MultiArrayView<2, TS, AS>
const & img3,
703 MultiArrayView<2, T2, S2> img4,
704 RegionStatisticsArray & stats,
707 vigra_precondition(img1.shape() == img3.shape(),
708 "seededRegionGrowing(): shape mismatch between input and output.");
715 template <
class T1,
class S1,
718 class RegionStatisticsArray>
721 MultiArrayView<2, TS, AS>
const & img3,
722 MultiArrayView<2, T2, S2> img4,
723 RegionStatisticsArray & stats)
725 vigra_precondition(img1.shape() == img3.shape(),
726 "seededRegionGrowing(): shape mismatch between input and output.");
730 stats, CompleteGrow);
739 template <
class SrcIterator,
class SrcAccessor,
740 class DestIterator,
class DestAccessor,
741 class RegionStatisticsArray,
class Neighborhood>
742 typename DestAccessor::value_type
743 fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
744 DestIterator destul, DestAccessor ad,
745 RegionStatisticsArray & stats,
749 std::ptrdiff_t bucket_count = 256)
751 typedef typename DestAccessor::value_type LabelType;
753 vigra_precondition((srgType & KeepContours) == 0,
754 "fastSeededRegionGrowing(): the turbo algorithm doesn't support 'KeepContours', sorry.");
756 int w = srclr.x - srcul.x;
757 int h = srclr.y - srcul.y;
759 SrcIterator isy = srcul, isx = srcul;
760 DestIterator idy = destul, idx = destul;
762 BucketQueue<Point2D, true> pqueue(bucket_count);
763 LabelType maxRegionLabel = 0;
766 for(isy=srcul, idy = destul, pos.y=0; pos.y<h; ++pos.y, ++isy.y, ++idy.y)
768 for(isx=isy, idx=idy, pos.x=0; pos.x<w; ++pos.x, ++isx.x, ++idx.x)
770 LabelType label = ad(idx);
773 vigra_precondition(label <= stats.maxRegionLabel(),
774 "fastSeededRegionGrowing(): Largest label exceeds size of RegionStatisticsArray.");
776 if(maxRegionLabel < label)
777 maxRegionLabel = label;
782 NeighborhoodCirculator<DestIterator, Neighborhood> c(idx), cend(c);
787 std::ptrdiff_t priority = (std::ptrdiff_t)stats[label].cost(as(isx));
788 pqueue.push(pos, priority);
796 RestrictedNeighborhoodCirculator<DestIterator, Neighborhood>
797 c(idx, atBorder), cend(c);
802 std::ptrdiff_t priority = (std::ptrdiff_t)stats[label].cost(as(isx));
803 pqueue.push(pos, priority);
814 while(!pqueue.empty())
816 Point2D pos = pqueue.top();
817 std::ptrdiff_t cost = pqueue.topPriority();
820 if((srgType & StopAtThreshold) != 0 && cost > max_cost)
826 std::ptrdiff_t label = ad(idx);
831 NeighborhoodCirculator<DestIterator, Neighborhood> c(idx), cend(c);
835 std::ptrdiff_t nlabel = ad(c);
838 ad.set(label, idx, c.diff());
839 std::ptrdiff_t priority =
840 std::max((std::ptrdiff_t)stats[label].cost(as(isx, c.diff())), cost);
841 pqueue.push(pos+c.diff(), priority);
848 RestrictedNeighborhoodCirculator<DestIterator, Neighborhood>
849 c(idx, atBorder), cend(c);
852 std::ptrdiff_t nlabel = ad(c);
855 ad.set(label, idx, c.diff());
856 std::ptrdiff_t priority =
857 std::max((std::ptrdiff_t)stats[label].cost(as(isx, c.diff())), cost);
858 pqueue.push(pos+c.diff(), priority);
865 return maxRegionLabel;
868 template <
class SrcIterator,
class SrcAccessor,
869 class DestIterator,
class DestAccessor,
870 class RegionStatisticsArray,
class Neighborhood>
871 inline typename DestAccessor::value_type
872 fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
873 DestIterator destul, DestAccessor ad,
874 RegionStatisticsArray & stats,
878 return fastSeededRegionGrowing(srcul, srclr, as,
880 stats, srgType, n, NumericTraits<double>::max(), 256);
883 template <
class SrcIterator,
class SrcAccessor,
884 class DestIterator,
class DestAccessor,
885 class RegionStatisticsArray>
886 inline typename DestAccessor::value_type
887 fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
888 DestIterator destul, DestAccessor ad,
889 RegionStatisticsArray & stats,
892 return fastSeededRegionGrowing(srcul, srclr, as,
897 template <
class SrcIterator,
class SrcAccessor,
898 class DestIterator,
class DestAccessor,
899 class RegionStatisticsArray>
900 inline typename DestAccessor::value_type
901 fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
902 DestIterator destul, DestAccessor ad,
903 RegionStatisticsArray & stats)
905 return fastSeededRegionGrowing(srcul, srclr, as,
907 stats, CompleteGrow);
910 template <
class SrcIterator,
class SrcAccessor,
911 class DestIterator,
class DestAccessor,
912 class RegionStatisticsArray,
class Neighborhood>
913 inline typename DestAccessor::value_type
914 fastSeededRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> src,
915 pair<DestIterator, DestAccessor> dest,
916 RegionStatisticsArray & stats,
920 std::ptrdiff_t bucket_count = 256)
922 return fastSeededRegionGrowing(src.first, src.second, src.third,
923 dest.first, dest.second,
924 stats, srgType, n, max_cost, bucket_count);
927 template <
class T1,
class S1,
929 class RegionStatisticsArray,
class Neighborhood>
931 fastSeededRegionGrowing(MultiArrayView<2, T1, S1>
const & src,
932 MultiArrayView<2, T2, S2> dest,
933 RegionStatisticsArray & stats,
937 std::ptrdiff_t bucket_count = 256)
939 vigra_precondition(src.shape() == dest.shape(),
940 "fastSeededRegionGrowing(): shape mismatch between input and output.");
941 return fastSeededRegionGrowing(srcImageRange(src),
943 stats, srgType, n, max_cost, bucket_count);
962 template <
class Value>
999 #endif // VIGRA_SEEDEDREGIONGROWING_HXX
Value result_type
Definition: seededregiongrowing.hxx:973
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:963
SRGType
Definition: seededregiongrowing.hxx:177
Value cost_type
Definition: seededregiongrowing.hxx:981
BasicImageIterator< PIXELTYPE, PIXELTYPE ** > Iterator
Definition: basicimage.hxx:530
void operator()(argument_type const &) const
Definition: seededregiongrowing.hxx:985
Value value_type
Definition: seededregiongrowing.hxx:977
void copyImage(...)
Copy source image into destination image.
Value argument_type
Definition: seededregiongrowing.hxx:968
FourNeighborhood::NeighborCode FourNeighborCode
Definition: pixelneighborhood.hxx:379
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:989
BasicImage< Int32 > IImage
Definition: stdimage.hxx:116