37 #ifndef VIGRA_LABELIMAGE_HXX
38 #define VIGRA_LABELIMAGE_HXX
42 #include "utilities.hxx"
43 #include "stdimage.hxx"
44 #include "union_find.hxx"
45 #include "sized_int.hxx"
155 doxygen_overloaded_function(template <...>
unsigned int labelImage)
157 template <
class SrcIterator,
class SrcAccessor,
158 class DestIterator,
class DestAccessor,
159 class EqualityFunctor>
160 unsigned int labelImage(SrcIterator upperlefts,
161 SrcIterator lowerrights, SrcAccessor sa,
162 DestIterator upperleftd, DestAccessor da,
163 bool eight_neighbors, EqualityFunctor equal)
165 typedef typename DestAccessor::value_type LabelType;
167 int w = lowerrights.x - upperlefts.x;
168 int h = lowerrights.y - upperlefts.y;
171 static const Diff2D neighbor[] = {
178 static const int left = 0, top = 2, topright = 3;
179 int step = eight_neighbors ? 1 : 2;
181 SrcIterator ys = upperlefts;
182 DestIterator yd = upperleftd;
184 detail::UnionFindArray<LabelType> label;
201 for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
204 DestIterator xd = yd;
206 int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top);
208 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
210 int beginNeighbor = (x == 0) ? top : left;
211 if(x == w-1 && endNeighbor == topright) endNeighbor = top;
213 for(i=beginNeighbor; i<=endNeighbor; i+=step)
215 if(equal(sa(xs), sa(xs, neighbor[i])))
217 LabelType neighborLabel = label.find(da(xd,neighbor[i]));
219 for(
int j=i+2; j<=endNeighbor; j+=step)
221 if(equal(sa(xs), sa(xs, neighbor[j])))
223 neighborLabel = label.makeUnion(da(xd, neighbor[j]), neighborLabel);
227 da.set(neighborLabel, xd);
234 da.set(label.makeNewLabel(), xd);
241 unsigned int count = label.makeContiguous();
244 for(y=0; y != h; ++y, ++yd.y)
246 typename DestIterator::row_iterator xd = yd.rowIterator();
247 for(x = 0; x != w; ++x, ++xd)
249 da.set(label[da(xd)], xd);
255 template <
class SrcIterator,
class SrcAccessor,
256 class DestIterator,
class DestAccessor,
257 class EqualityFunctor>
259 unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
260 pair<DestIterator, DestAccessor> dest,
261 bool eight_neighbors, EqualityFunctor equal)
263 return labelImage(src.first, src.second, src.third,
264 dest.first, dest.second, eight_neighbors, equal);
267 template <
class SrcIterator,
class SrcAccessor,
268 class DestIterator,
class DestAccessor>
270 unsigned int labelImage(SrcIterator upperlefts,
271 SrcIterator lowerrights, SrcAccessor sa,
272 DestIterator upperleftd, DestAccessor da,
273 bool eight_neighbors)
275 return labelImage(upperlefts, lowerrights, sa,
276 upperleftd, da, eight_neighbors,
277 std::equal_to<typename SrcAccessor::value_type>());
280 template <
class SrcIterator,
class SrcAccessor,
281 class DestIterator,
class DestAccessor>
283 unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
284 pair<DestIterator, DestAccessor> dest,
285 bool eight_neighbors)
287 return labelImage(src.first, src.second, src.third,
288 dest.first, dest.second, eight_neighbors,
289 std::equal_to<typename SrcAccessor::value_type>());
409 template <
class SrcIterator,
class SrcAccessor,
410 class DestIterator,
class DestAccessor,
411 class ValueType,
class EqualityFunctor>
413 SrcIterator upperlefts,
414 SrcIterator lowerrights, SrcAccessor sa,
415 DestIterator upperleftd, DestAccessor da,
416 bool eight_neighbors,
417 ValueType background_value, EqualityFunctor equal)
419 int w = lowerrights.x - upperlefts.x;
420 int h = lowerrights.y - upperlefts.y;
423 static const Diff2D neighbor[] = {
430 static const int left = 0, top = 2, topright = 3;
431 int step = eight_neighbors ? 1 : 2;
433 SrcIterator ys(upperlefts);
437 typedef BasicImage<IntBiggest> TmpImage;
438 TmpImage labelimage(w, h);
439 TmpImage::ScanOrderIterator label = labelimage.begin();
440 TmpImage::Iterator yt = labelimage.upperLeft();
441 TmpImage::Iterator xt(yt);
446 for(y = 0; y != h; ++y, ++ys.y, ++yt.y)
451 int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top);
453 for(x = 0; x != w; ++x, ++xs.x, ++xt.x)
455 if(equal(sa(xs), background_value))
461 int beginNeighbor = (x == 0) ? top : left;
462 if(x == w-1 && endNeighbor == topright) endNeighbor = top;
464 for(i=beginNeighbor; i<=endNeighbor; i+=step)
466 if(equal(sa(xs), sa(xs, neighbor[i])))
470 for(
int j=i+2; j<=endNeighbor; j+=step)
472 if(equal(sa(xs), sa(xs, neighbor[j])))
476 if(neighborLabel != neighborLabel1)
479 while(neighborLabel != label[neighborLabel])
481 neighborLabel = label[neighborLabel];
483 while(neighborLabel1 != label[neighborLabel1])
485 neighborLabel1 = label[neighborLabel1];
489 if(neighborLabel1 < neighborLabel)
491 label[neighborLabel] = neighborLabel1;
492 neighborLabel = neighborLabel1;
494 else if(neighborLabel < neighborLabel1)
496 label[neighborLabel1] = neighborLabel;
520 DestIterator yd(upperleftd);
524 for(y=0; y != h; ++y, ++yd.y)
527 for(x = 0; x != w; ++x, ++xd.x, ++i)
529 if(label[i] == -1)
continue;
537 label[i] = label[label[i]];
539 da.set(label[i]+1, xd);
546 template <
class SrcIterator,
class SrcAccessor,
547 class DestIterator,
class DestAccessor,
548 class ValueType,
class EqualityFunctor>
551 triple<SrcIterator, SrcIterator, SrcAccessor> src,
552 pair<DestIterator, DestAccessor> dest,
553 bool eight_neighbors,
554 ValueType background_value, EqualityFunctor equal)
557 dest.first, dest.second,
558 eight_neighbors, background_value, equal);
561 template <
class SrcIterator,
class SrcAccessor,
562 class DestIterator,
class DestAccessor,
566 triple<SrcIterator, SrcIterator, SrcAccessor> src,
567 pair<DestIterator, DestAccessor> dest,
568 bool eight_neighbors,
569 ValueType background_value)
572 dest.first, dest.second,
573 eight_neighbors, background_value,
574 std::equal_to<typename SrcAccessor::value_type>());
577 template <
class SrcIterator,
class SrcAccessor,
578 class DestIterator,
class DestAccessor,
582 SrcIterator upperlefts,
583 SrcIterator lowerrights, SrcAccessor sa,
584 DestIterator upperleftd, DestAccessor da,
585 bool eight_neighbors,
586 ValueType background_value)
590 eight_neighbors, background_value,
591 std::equal_to<typename SrcAccessor::value_type>());
701 template <
class SrcIterator,
class SrcAccessor,
702 class DestIterator,
class DestAccessor,
class DestValue>
704 SrcIterator sul, SrcIterator slr, SrcAccessor sa,
705 DestIterator dul, DestAccessor da,
706 DestValue edge_marker)
708 int w = slr.x - sul.x;
709 int h = slr.y - sul.y;
712 static const Diff2D right(1,0);
713 static const Diff2D left(-1,0);
714 static const Diff2D bottomright(1,1);
715 static const Diff2D bottom(0,1);
716 static const Diff2D top(0,-1);
718 SrcIterator iy = sul;
719 DestIterator dy = dul;
721 for(y=0; y<h-1; ++y, ++iy.y, dy.y+=2)
724 DestIterator dx = dy;
726 for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
729 da.set(sa(ix), dx, bottomright);
731 if(sa(ix, right) != sa(ix))
733 da.set(edge_marker, dx, right);
737 da.set(sa(ix), dx, right);
739 if(sa(ix, bottom) != sa(ix))
741 da.set(edge_marker, dx, bottom);
745 da.set(sa(ix), dx, bottom);
751 if(sa(ix, bottom) != sa(ix))
753 da.set(edge_marker, dx, bottom);
757 da.set(sa(ix), dx, bottom);
762 DestIterator dx = dy;
764 for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
767 if(sa(ix, right) != sa(ix))
769 da.set(edge_marker, dx, right);
773 da.set(sa(ix), dx, right);
778 dy = dul + Diff2D(1,1);
781 for(y=0; y<h-1; ++y, dy.y+=2)
783 DestIterator dx = dy;
785 for(x=0; x<w-1; ++x, dx.x+=2)
787 static const Diff2D dist[] = {right, top, left, bottom };
792 if(da(dx, dist[i]) == edge_marker)
break;
795 if(i < 4) da.set(edge_marker, dx);
800 template <
class SrcIterator,
class SrcAccessor,
801 class DestIterator,
class DestAccessor,
class DestValue>
804 triple<SrcIterator, SrcIterator, SrcAccessor> src,
805 pair<DestIterator, DestAccessor> dest,
806 DestValue edge_marker)
809 dest.first, dest.second,
907 template <
class SrcIterator,
class SrcAccessor,
908 class DestIterator,
class DestAccessor,
class DestValue>
910 SrcIterator sul, SrcIterator slr, SrcAccessor sa,
911 DestIterator dul, DestAccessor da,
912 DestValue edge_marker)
914 int w = slr.x - sul.x;
915 int h = slr.y - sul.y;
918 static const Diff2D right(1,0);
919 static const Diff2D left(-1,0);
920 static const Diff2D bottomright(1,1);
921 static const Diff2D bottom(0,1);
922 static const Diff2D top(0,-1);
924 SrcIterator iy = sul;
925 DestIterator dy = dul;
927 for(y=0; y<h-1; ++y, ++iy.y, ++dy.y)
930 DestIterator dx = dy;
932 for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
934 if(sa(ix, right) != sa(ix))
936 da.set(edge_marker, dx);
938 if(sa(ix, bottom) != sa(ix))
940 da.set(edge_marker, dx);
944 if(sa(ix, bottom) != sa(ix))
946 da.set(edge_marker, dx);
951 DestIterator dx = dy;
953 for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
955 if(sa(ix, right) != sa(ix))
957 da.set(edge_marker, dx);
962 template <
class SrcIterator,
class SrcAccessor,
963 class DestIterator,
class DestAccessor,
class DestValue>
966 triple<SrcIterator, SrcIterator, SrcAccessor> src,
967 pair<DestIterator, DestAccessor> dest,
968 DestValue edge_marker)
971 dest.first, dest.second,
979 #endif // VIGRA_LABELIMAGE_HXX
unsigned int labelImage(...)
Find the connected components of a segmented image.
unsigned int labelImageWithBackground(...)
Find the connected components of a segmented image, excluding the background from labeling...
void regionImageToEdgeImage(...)
Transform a labeled image into an edge image.
void regionImageToCrackEdgeImage(...)
Transform a labeled image into a crack edge image.
detail::SelectBiggestIntegerType< detail::SignedIntTypes >::type IntBiggest
the biggest signed integer type of the system
Definition: sized_int.hxx:188