36#ifndef VIGRA_SEEDEDREGIONGROWING_HXX
37#define VIGRA_SEEDEDREGIONGROWING_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_;
155struct UnlabelWatersheds
157 int operator()(
int label)
const
159 return label < 0 ? 0 : label;
180 SRGWatershedLabel = -1
418typename SeedAccessor::value_type
434 typedef typename SeedAccessor::value_type LabelType;
436 typedef typename RegionStatistics::cost_type
CostType;
437 typedef detail::SeedRgPixel<CostType>
Pixel;
439 typename Pixel::Allocator allocator;
441 typedef std::priority_queue<Pixel *, std::vector<Pixel *>,
446 IImage::Iterator
ir = regions.upperLeft() +
Diff2D(1,1);
447 IImage::Iterator
iry,
irx;
457 typedef typename Neighborhood::Direction Direction;
458 int directionCount = Neighborhood::DirectionCount;
470 for(
int i=0;
i<directionCount;
i++)
479 allocator.create(pos, pos+Neighborhood::diff((Direction)
i), cost, count++,
cneighbor);
486 vigra_precondition((LabelType)*
irx <= (LabelType)stats.maxRegionLabel(),
487 "seededRegionGrowing(): Largest label exceeds size of RegionStatisticsArray.");
488 if(maxRegionLabel < *
irx)
489 maxRegionLabel = *
irx;
505 allocator.dismiss(
pixel);
507 if((srgType & StopAtThreshold) != 0 && cost > max_cost)
516 if((srgType & KeepContours) != 0)
518 for(
int i=0;
i<directionCount;
i++)
523 lab = SRGWatershedLabel;
531 if((srgType & KeepContours) == 0 ||
lab > 0)
538 for(
int i=0;
i<directionCount;
i++)
540 if(
irx[Neighborhood::diff((Direction)
i)] == 0)
545 allocator.create(pos+Neighborhood::diff((Direction)
i),
nearest, cost, count++,
lab);
555 allocator.dismiss(
pheap.top());
561 detail::UnlabelWatersheds());
563 return (LabelType)maxRegionLabel;
566template <
class SrcIterator,
class SrcAccessor,
567 class SeedImageIterator,
class SeedAccessor,
568 class DestIterator,
class DestAccessor,
569 class RegionStatisticsArray,
class Neighborhood>
570inline typename SeedAccessor::value_type
572 SrcIterator srclr, SrcAccessor as,
573 SeedImageIterator seedsul, SeedAccessor aseeds,
574 DestIterator destul, DestAccessor ad,
575 RegionStatisticsArray & stats,
582 stats, srgType, n, NumericTraits<double>::max());
587template <
class SrcIterator,
class SrcAccessor,
588 class SeedImageIterator,
class SeedAccessor,
589 class DestIterator,
class DestAccessor,
590 class RegionStatisticsArray>
591inline typename SeedAccessor::value_type
593 SrcIterator srclr, SrcAccessor as,
594 SeedImageIterator seedsul, SeedAccessor aseeds,
595 DestIterator destul, DestAccessor ad,
596 RegionStatisticsArray & stats,
605template <
class SrcIterator,
class SrcAccessor,
606 class SeedImageIterator,
class SeedAccessor,
607 class DestIterator,
class DestAccessor,
608 class RegionStatisticsArray>
609inline typename SeedAccessor::value_type
611 SrcIterator srclr, SrcAccessor as,
612 SeedImageIterator seedsul, SeedAccessor aseeds,
613 DestIterator destul, DestAccessor ad,
614 RegionStatisticsArray & stats)
619 stats, CompleteGrow);
622template <
class SrcIterator,
class SrcAccessor,
623 class SeedImageIterator,
class SeedAccessor,
624 class DestIterator,
class DestAccessor,
625 class RegionStatisticsArray,
class Neighborhood>
626inline typename SeedAccessor::value_type
628 pair<SeedImageIterator, SeedAccessor> img3,
629 pair<DestIterator, DestAccessor> img4,
630 RegionStatisticsArray & stats,
633 double max_cost = NumericTraits<double>::max())
636 img3.first, img3.second,
637 img4.first, img4.second,
638 stats, srgType, n, max_cost);
641template <
class SrcIterator,
class SrcAccessor,
642 class SeedImageIterator,
class SeedAccessor,
643 class DestIterator,
class DestAccessor,
644 class RegionStatisticsArray>
645inline typename SeedAccessor::value_type
647 pair<SeedImageIterator, SeedAccessor> img3,
648 pair<DestIterator, DestAccessor> img4,
649 RegionStatisticsArray & stats,
653 img3.first, img3.second,
654 img4.first, img4.second,
658template <
class SrcIterator,
class SrcAccessor,
659 class SeedImageIterator,
class SeedAccessor,
660 class DestIterator,
class DestAccessor,
661 class RegionStatisticsArray>
662inline typename SeedAccessor::value_type
664 pair<SeedImageIterator, SeedAccessor> img3,
665 pair<DestIterator, DestAccessor> img4,
666 RegionStatisticsArray & stats)
669 img3.first, img3.second,
670 img4.first, img4.second,
671 stats, CompleteGrow);
674template <
class T1,
class S1,
677 class RegionStatisticsArray,
class Neighborhood>
680 MultiArrayView<2, TS, AS>
const & img3,
681 MultiArrayView<2, T2, S2> img4,
682 RegionStatisticsArray & stats,
685 double max_cost = NumericTraits<double>::max())
687 vigra_precondition(img1.shape() == img3.shape(),
688 "seededRegionGrowing(): shape mismatch between input and output.");
692 stats, srgType, n, max_cost);
695template <
class T1,
class S1,
698 class RegionStatisticsArray>
701 MultiArrayView<2, TS, AS>
const & img3,
702 MultiArrayView<2, T2, S2> img4,
703 RegionStatisticsArray & stats,
706 vigra_precondition(img1.shape() == img3.shape(),
707 "seededRegionGrowing(): shape mismatch between input and output.");
714template <
class T1,
class S1,
717 class RegionStatisticsArray>
720 MultiArrayView<2, TS, AS>
const & img3,
721 MultiArrayView<2, T2, S2> img4,
722 RegionStatisticsArray & stats)
724 vigra_precondition(img1.shape() == img3.shape(),
725 "seededRegionGrowing(): shape mismatch between input and output.");
729 stats, CompleteGrow);
738template <
class SrcIterator,
class SrcAccessor,
739 class DestIterator,
class DestAccessor,
740 class RegionStatisticsArray,
class Neighborhood>
741typename DestAccessor::value_type
742fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
743 DestIterator destul, DestAccessor ad,
744 RegionStatisticsArray & stats,
748 std::ptrdiff_t bucket_count = 256)
750 typedef typename DestAccessor::value_type LabelType;
752 vigra_precondition((srgType & KeepContours) == 0,
753 "fastSeededRegionGrowing(): the turbo algorithm doesn't support 'KeepContours', sorry.");
755 int w = srclr.x - srcul.x;
756 int h = srclr.y - srcul.y;
758 SrcIterator isy = srcul, isx = srcul;
759 DestIterator idy = destul, idx = destul;
761 BucketQueue<Point2D, true> pqueue(bucket_count);
762 LabelType maxRegionLabel = 0;
765 for(isy=srcul, idy = destul, pos.y=0; pos.y<h; ++pos.y, ++isy.y, ++idy.y)
767 for(isx=isy, idx=idy, pos.x=0; pos.x<w; ++pos.x, ++isx.x, ++idx.x)
769 LabelType label = ad(idx);
772 vigra_precondition(label <= stats.maxRegionLabel(),
773 "fastSeededRegionGrowing(): Largest label exceeds size of RegionStatisticsArray.");
775 if(maxRegionLabel < label)
776 maxRegionLabel = label;
781 NeighborhoodCirculator<DestIterator, Neighborhood> c(idx), cend(c);
786 std::ptrdiff_t priority = (std::ptrdiff_t)stats[label].cost(as(isx));
787 pqueue.push(pos, priority);
795 RestrictedNeighborhoodCirculator<DestIterator, Neighborhood>
796 c(idx, atBorder), cend(c);
801 std::ptrdiff_t priority = (std::ptrdiff_t)stats[label].cost(as(isx));
802 pqueue.push(pos, priority);
813 while(!pqueue.empty())
815 Point2D pos = pqueue.top();
816 std::ptrdiff_t cost = pqueue.topPriority();
819 if((srgType & StopAtThreshold) != 0 && cost > max_cost)
825 std::ptrdiff_t label = ad(idx);
830 NeighborhoodCirculator<DestIterator, Neighborhood> c(idx), cend(c);
834 std::ptrdiff_t nlabel = ad(c);
837 ad.set(label, idx, c.diff());
838 std::ptrdiff_t priority =
839 std::max((std::ptrdiff_t)stats[label].cost(as(isx, c.diff())), cost);
840 pqueue.push(pos+c.diff(), priority);
847 RestrictedNeighborhoodCirculator<DestIterator, Neighborhood>
848 c(idx, atBorder), cend(c);
851 std::ptrdiff_t nlabel = ad(c);
854 ad.set(label, idx, c.diff());
855 std::ptrdiff_t priority =
856 std::max((std::ptrdiff_t)stats[label].cost(as(isx, c.diff())), cost);
857 pqueue.push(pos+c.diff(), priority);
864 return maxRegionLabel;
867template <
class SrcIterator,
class SrcAccessor,
868 class DestIterator,
class DestAccessor,
869 class RegionStatisticsArray,
class Neighborhood>
870inline typename DestAccessor::value_type
871fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
872 DestIterator destul, DestAccessor ad,
873 RegionStatisticsArray & stats,
877 return fastSeededRegionGrowing(srcul, srclr, as,
879 stats, srgType, n, NumericTraits<double>::max(), 256);
882template <
class SrcIterator,
class SrcAccessor,
883 class DestIterator,
class DestAccessor,
884 class RegionStatisticsArray>
885inline typename DestAccessor::value_type
886fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
887 DestIterator destul, DestAccessor ad,
888 RegionStatisticsArray & stats,
891 return fastSeededRegionGrowing(srcul, srclr, as,
896template <
class SrcIterator,
class SrcAccessor,
897 class DestIterator,
class DestAccessor,
898 class RegionStatisticsArray>
899inline typename DestAccessor::value_type
900fastSeededRegionGrowing(SrcIterator srcul, SrcIterator srclr, SrcAccessor as,
901 DestIterator destul, DestAccessor ad,
902 RegionStatisticsArray & stats)
904 return fastSeededRegionGrowing(srcul, srclr, as,
906 stats, CompleteGrow);
909template <
class SrcIterator,
class SrcAccessor,
910 class DestIterator,
class DestAccessor,
911 class RegionStatisticsArray,
class Neighborhood>
912inline typename DestAccessor::value_type
913fastSeededRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> src,
914 pair<DestIterator, DestAccessor> dest,
915 RegionStatisticsArray & stats,
919 std::ptrdiff_t bucket_count = 256)
921 return fastSeededRegionGrowing(src.first, src.second, src.third,
922 dest.first, dest.second,
923 stats, srgType, n, max_cost, bucket_count);
926template <
class T1,
class S1,
928 class RegionStatisticsArray,
class Neighborhood>
930fastSeededRegionGrowing(MultiArrayView<2, T1, S1>
const & src,
931 MultiArrayView<2, T2, S2> dest,
932 RegionStatisticsArray & stats,
936 std::ptrdiff_t bucket_count = 256)
938 vigra_precondition(src.shape() == dest.shape(),
939 "fastSeededRegionGrowing(): shape mismatch between input and output.");
940 return fastSeededRegionGrowing(srcImageRange(src),
942 stats, srgType, n, max_cost, bucket_count);
961template <
class Value>
Two dimensional difference vector.
Definition diff2d.hxx:186
int y
Definition diff2d.hxx:392
int x
Definition diff2d.hxx:385
Two dimensional point or position.
Definition diff2d.hxx:593
Class for a single RGB value.
Definition rgbvalue.hxx:128
Statistics functor to be used for seeded region growing.
Definition seededregiongrowing.hxx:963
Value value_type
Definition seededregiongrowing.hxx:976
Value result_type
Definition seededregiongrowing.hxx:972
cost_type const & cost(argument_type const &v) const
Definition seededregiongrowing.hxx:988
Value argument_type
Definition seededregiongrowing.hxx:967
Value cost_type
Definition seededregiongrowing.hxx:980
void operator()(argument_type const &) const
Definition seededregiongrowing.hxx:984
size_type size() const
Definition tinyvector.hxx:913
SRGType
Definition seededregiongrowing.hxx:176
void seededRegionGrowing(...)
Region Segmentation by means of Seeded Region Growing.
FourNeighborhood::NeighborCode FourNeighborCode
Definition pixelneighborhood.hxx:379
AtImageBorder
Encode whether a point is near the image border.
Definition pixelneighborhood.hxx:69
@ NotAtBorder
 
Definition pixelneighborhood.hxx:70
void initImageBorder(...)
Write value to the specified border pixels in the image.
AtImageBorder isAtImageBorder(int x, int y, int width, int height)
Find out whether a point is at the image border.
Definition pixelneighborhood.hxx:111
void copyImage(...)
Copy source image into destination image.