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
420 seededRegionGrowing(SrcIterator srcul,
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;
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());
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
572 seededRegionGrowing(SrcIterator srcul,
573 SrcIterator srclr, SrcAccessor as,
574 SeedImageIterator seedsul, SeedAccessor aseeds,
575 DestIterator destul, DestAccessor ad,
576 RegionStatisticsArray & stats,
580 return seededRegionGrowing(srcul, srclr, as,
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
593 seededRegionGrowing(SrcIterator srcul,
594 SrcIterator srclr, SrcAccessor as,
595 SeedImageIterator seedsul, SeedAccessor aseeds,
596 DestIterator destul, DestAccessor ad,
597 RegionStatisticsArray & stats,
600 return seededRegionGrowing(srcul, srclr, as,
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
611 seededRegionGrowing(SrcIterator srcul,
612 SrcIterator srclr, SrcAccessor as,
613 SeedImageIterator seedsul, SeedAccessor aseeds,
614 DestIterator destul, DestAccessor ad,
615 RegionStatisticsArray & stats)
617 return seededRegionGrowing(srcul, srclr, as,
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
628 seededRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> img1,
629 pair<SeedImageIterator, SeedAccessor> img3,
630 pair<DestIterator, DestAccessor> img4,
631 RegionStatisticsArray & stats,
634 double max_cost = NumericTraits<double>::max())
636 return seededRegionGrowing(img1.first, img1.second, img1.third,
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
647 seededRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> img1,
648 pair<SeedImageIterator, SeedAccessor> img3,
649 pair<DestIterator, DestAccessor> img4,
650 RegionStatisticsArray & stats,
653 return seededRegionGrowing(img1.first, img1.second, img1.third,
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
664 seededRegionGrowing(triple<SrcIterator, SrcIterator, SrcAccessor> img1,
665 pair<SeedImageIterator, SeedAccessor> img3,
666 pair<DestIterator, DestAccessor> img4,
667 RegionStatisticsArray & stats)
669 return seededRegionGrowing(img1.first, img1.second, img1.third,
670 img3.first, img3.second,
671 img4.first, img4.second,
672 stats, CompleteGrow);
675 template <
class T1,
class S1,
678 class RegionStatisticsArray,
class Neighborhood>
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.");
690 return seededRegionGrowing(srcImageRange(img1),
693 stats, srgType, n, max_cost);
696 template <
class T1,
class S1,
699 class RegionStatisticsArray>
704 RegionStatisticsArray & stats,
707 vigra_precondition(img1.
shape() == img3.
shape(),
708 "seededRegionGrowing(): shape mismatch between input and output.");
709 return seededRegionGrowing(srcImageRange(img1),
715 template <
class T1,
class S1,
718 class RegionStatisticsArray>
723 RegionStatisticsArray & stats)
725 vigra_precondition(img1.
shape() == img3.
shape(),
726 "seededRegionGrowing(): shape mismatch between input and output.");
727 return seededRegionGrowing(srcImageRange(img1),
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;
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;
787 std::ptrdiff_t priority = (std::ptrdiff_t)stats[label].cost(as(isx));
788 pqueue.
push(pos, priority);
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())
820 if((srgType & StopAtThreshold) != 0 && cost > max_cost)
826 std::ptrdiff_t label = ad(idx);
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);
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>
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>
989 cost_type
const &
cost(argument_type
const & v)
const 999 #endif // VIGRA_SEEDEDREGIONGROWING_HXX Value result_type
Definition: seededregiongrowing.hxx:973
Priority queue implemented using bucket sort.
Definition: bucket_queue.hxx:69
Circulator that walks around a given location in a given image, using a restricted neighborhood...
Definition: pixelneighborhood.hxx:1345
Accessor accessor()
Definition: basicimage.hxx:1064
int y
Definition: diff2d.hxx:392
void seededRegionGrowing(...)
Region Segmentation by means of Seeded Region Growing.
const difference_type & shape() const
Definition: multi_array.hxx:1551
AtImageBorder
Encode whether a point is near the image border.
Definition: pixelneighborhood.hxx:68
int x
Definition: diff2d.hxx:385
const_reference top() const
The current top element.
Definition: bucket_queue.hxx:123
Two dimensional difference vector.
Definition: diff2d.hxx:185
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
void push(value_type const &v, priority_type priority)
Insert new element.
Definition: bucket_queue.hxx:142
Definition: accessor.hxx:43
Encapsulation of direction management for 4-neighborhood.
Definition: pixelneighborhood.hxx:165
Value cost_type
Definition: seededregiongrowing.hxx:981
Two dimensional point or position.
Definition: diff2d.hxx:592
Definition: basicimage.hxx:262
void operator()(argument_type const &) const
Definition: seededregiongrowing.hxx:985
priority_type topPriority() const
Priority of the current top element.
Definition: bucket_queue.hxx:116
Value value_type
Definition: seededregiongrowing.hxx:977
void pop()
Remove the current top element.
Definition: bucket_queue.hxx:131
Circulator that walks around a given location in a given image.
Definition: pixelneighborhood.hxx:1037
void copyImage(...)
Copy source image into destination image.
bool empty() const
Queue contains no elements. Equivalent to size() == 0.
Definition: bucket_queue.hxx:101
Fundamental class template for images.
Definition: basicimage.hxx:473
Value argument_type
Definition: seededregiongrowing.hxx:968
Base class for, and view to, vigra::MultiArray.
Definition: multi_array.hxx:655
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
traverser upperLeft()
Definition: basicimage.hxx:923