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"
46 #include "multi_shape.hxx"
183 doxygen_overloaded_function(template <...>
unsigned int labelImage)
185 template <
class SrcIterator,
class SrcAccessor,
186 class DestIterator,
class DestAccessor,
187 class EqualityFunctor>
188 unsigned int labelImage(SrcIterator upperlefts,
189 SrcIterator lowerrights, SrcAccessor sa,
190 DestIterator upperleftd, DestAccessor da,
191 bool eight_neighbors, EqualityFunctor equal)
193 typedef typename DestAccessor::value_type LabelType;
195 int w = lowerrights.x - upperlefts.x;
196 int h = lowerrights.y - upperlefts.y;
199 const Diff2D neighbor[] = {
206 const int left = 0, top = 2, topright = 3;
207 int step = eight_neighbors ? 1 : 2;
209 SrcIterator ys = upperlefts;
210 DestIterator yd = upperleftd;
212 detail::UnionFindArray<LabelType> label;
229 for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
232 DestIterator xd = yd;
234 int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top);
236 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
238 int beginNeighbor = (x == 0) ? top : left;
239 if(x == w-1 && endNeighbor == topright) endNeighbor = top;
241 for(i=beginNeighbor; i<=endNeighbor; i+=step)
243 if(equal(sa(xs), sa(xs, neighbor[i])))
245 LabelType neighborLabel = label.find(da(xd,neighbor[i]));
247 for(
int j=i+2; j<=endNeighbor; j+=step)
249 if(equal(sa(xs), sa(xs, neighbor[j])))
251 neighborLabel = label.makeUnion(da(xd, neighbor[j]), neighborLabel);
255 da.set(neighborLabel, xd);
262 da.set(label.makeNewLabel(), xd);
269 unsigned int count = label.makeContiguous();
272 for(y=0; y != h; ++y, ++yd.y)
274 typename DestIterator::row_iterator xd = yd.rowIterator();
275 for(x = 0; x != w; ++x, ++xd)
277 da.set(label[da(xd)], xd);
283 template <
class SrcIterator,
class SrcAccessor,
284 class DestIterator,
class DestAccessor>
286 unsigned int labelImage(SrcIterator upperlefts,
287 SrcIterator lowerrights, SrcAccessor sa,
288 DestIterator upperleftd, DestAccessor da,
289 bool eight_neighbors)
291 return labelImage(upperlefts, lowerrights, sa,
292 upperleftd, da, eight_neighbors,
293 std::equal_to<typename SrcAccessor::value_type>());
296 template <
class SrcIterator,
class SrcAccessor,
297 class DestIterator,
class DestAccessor,
298 class EqualityFunctor>
300 labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
301 pair<DestIterator, DestAccessor> dest,
302 bool eight_neighbors, EqualityFunctor equal)
304 return labelImage(src.first, src.second, src.third,
305 dest.first, dest.second, eight_neighbors, equal);
308 template <
class SrcIterator,
class SrcAccessor,
309 class DestIterator,
class DestAccessor>
311 labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
312 pair<DestIterator, DestAccessor> dest,
313 bool eight_neighbors)
315 return labelImage(src.first, src.second, src.third,
316 dest.first, dest.second, eight_neighbors,
317 std::equal_to<typename SrcAccessor::value_type>());
320 template <
class T1,
class S1,
322 class EqualityFunctor>
324 labelImage(MultiArrayView<2, T1, S1>
const & src,
325 MultiArrayView<2, T2, S2> dest,
326 bool eight_neighbors, EqualityFunctor equal)
328 vigra_precondition(src.shape() == dest.shape(),
329 "labelImage(): shape mismatch between input and output.");
331 destImage(dest), eight_neighbors, equal);
334 template <
class T1,
class S1,
337 labelImage(MultiArrayView<2, T1, S1>
const & src,
338 MultiArrayView<2, T2, S2> dest,
339 bool eight_neighbors)
342 destImage(dest), eight_neighbors,
343 std::equal_to<T1>());
484 template <
class SrcIterator,
class SrcAccessor,
485 class DestIterator,
class DestAccessor,
486 class ValueType,
class EqualityFunctor>
488 SrcIterator upperlefts,
489 SrcIterator lowerrights, SrcAccessor sa,
490 DestIterator upperleftd, DestAccessor da,
491 bool eight_neighbors,
492 ValueType background_value, EqualityFunctor equal)
494 int w = lowerrights.x - upperlefts.x;
495 int h = lowerrights.y - upperlefts.y;
498 const Diff2D neighbor[] = {
505 const int left = 0, top = 2, topright = 3;
506 int step = eight_neighbors ? 1 : 2;
508 SrcIterator ys(upperlefts);
512 typedef BasicImage<IntBiggest> TmpImage;
513 TmpImage labelimage(w, h);
514 TmpImage::ScanOrderIterator label = labelimage.begin();
515 TmpImage::Iterator yt = labelimage.upperLeft();
516 TmpImage::Iterator xt(yt);
521 for(y = 0; y != h; ++y, ++ys.y, ++yt.y)
526 int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top);
528 for(x = 0; x != w; ++x, ++xs.x, ++xt.x)
530 if(equal(sa(xs), background_value))
536 int beginNeighbor = (x == 0) ? top : left;
537 if(x == w-1 && endNeighbor == topright) endNeighbor = top;
539 for(i=beginNeighbor; i<=endNeighbor; i+=step)
541 if(equal(sa(xs), sa(xs, neighbor[i])))
545 for(
int j=i+2; j<=endNeighbor; j+=step)
547 if(equal(sa(xs), sa(xs, neighbor[j])))
551 if(neighborLabel != neighborLabel1)
554 while(neighborLabel != label[neighborLabel])
556 neighborLabel = label[neighborLabel];
558 while(neighborLabel1 != label[neighborLabel1])
560 neighborLabel1 = label[neighborLabel1];
564 if(neighborLabel1 < neighborLabel)
566 label[neighborLabel] = neighborLabel1;
567 neighborLabel = neighborLabel1;
569 else if(neighborLabel < neighborLabel1)
571 label[neighborLabel1] = neighborLabel;
595 DestIterator yd(upperleftd);
599 for(y=0; y != h; ++y, ++yd.y)
602 for(x = 0; x != w; ++x, ++xd.x, ++i)
604 if(label[i] == -1)
continue;
612 label[i] = label[label[i]];
614 da.set(label[i]+1, xd);
621 template <
class SrcIterator,
class SrcAccessor,
622 class DestIterator,
class DestAccessor,
626 SrcIterator upperlefts,
627 SrcIterator lowerrights, SrcAccessor sa,
628 DestIterator upperleftd, DestAccessor da,
629 bool eight_neighbors,
630 ValueType background_value)
634 eight_neighbors, background_value,
635 std::equal_to<typename SrcAccessor::value_type>());
638 template <
class SrcIterator,
class SrcAccessor,
639 class DestIterator,
class DestAccessor,
640 class ValueType,
class EqualityFunctor>
643 pair<DestIterator, DestAccessor> dest,
644 bool eight_neighbors,
645 ValueType background_value, EqualityFunctor equal)
648 dest.first, dest.second,
649 eight_neighbors, background_value, equal);
652 template <
class SrcIterator,
class SrcAccessor,
653 class DestIterator,
class DestAccessor,
657 pair<DestIterator, DestAccessor> dest,
658 bool eight_neighbors,
659 ValueType background_value)
662 dest.first, dest.second,
663 eight_neighbors, background_value,
664 std::equal_to<typename SrcAccessor::value_type>());
667 template <
class T1,
class S1,
669 class ValueType,
class EqualityFunctor>
672 MultiArrayView<2, T2, S2> dest,
673 bool eight_neighbors,
674 ValueType background_value, EqualityFunctor equal)
676 vigra_precondition(src.shape() == dest.shape(),
677 "labelImageWithBackground(): shape mismatch between input and output.");
680 eight_neighbors, background_value, equal);
683 template <
class T1,
class S1,
688 MultiArrayView<2, T2, S2> dest,
689 bool eight_neighbors,
690 ValueType background_value)
692 vigra_precondition(src.shape() == dest.shape(),
693 "labelImageWithBackground(): shape mismatch between input and output.");
696 eight_neighbors, background_value,
697 std::equal_to<T1>());
835 template <
class SrcIterator,
class SrcAccessor,
836 class DestIterator,
class DestAccessor,
class DestValue>
838 SrcIterator sul, SrcIterator slr, SrcAccessor sa,
839 DestIterator dul, DestAccessor da,
840 DestValue edge_marker)
842 int w = slr.x - sul.x;
843 int h = slr.y - sul.y;
846 const Diff2D right(1,0);
847 const Diff2D left(-1,0);
848 const Diff2D bottomright(1,1);
849 const Diff2D bottom(0,1);
850 const Diff2D top(0,-1);
852 SrcIterator iy = sul;
853 DestIterator dy = dul;
855 for(y=0; y<h-1; ++y, ++iy.y, dy.y+=2)
858 DestIterator dx = dy;
860 for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
863 da.set(sa(ix), dx, bottomright);
865 if(sa(ix, right) != sa(ix))
867 da.set(edge_marker, dx, right);
871 da.set(sa(ix), dx, right);
873 if(sa(ix, bottom) != sa(ix))
875 da.set(edge_marker, dx, bottom);
879 da.set(sa(ix), dx, bottom);
885 if(sa(ix, bottom) != sa(ix))
887 da.set(edge_marker, dx, bottom);
891 da.set(sa(ix), dx, bottom);
896 DestIterator dx = dy;
898 for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
901 if(sa(ix, right) != sa(ix))
903 da.set(edge_marker, dx, right);
907 da.set(sa(ix), dx, right);
912 dy = dul + Diff2D(1,1);
914 const Diff2D dist[] = {right, top, left, bottom };
916 for(y=0; y<h-1; ++y, dy.y+=2)
918 DestIterator dx = dy;
920 for(x=0; x<w-1; ++x, dx.x+=2)
925 if(da(dx, dist[i]) == edge_marker)
break;
928 if(i < 4) da.set(edge_marker, dx);
933 template <
class SrcIterator,
class SrcAccessor,
934 class DestIterator,
class DestAccessor,
class DestValue>
937 pair<DestIterator, DestAccessor> dest,
938 DestValue edge_marker)
941 dest.first, dest.second,
945 template <
class T1,
class S1,
946 class T2,
class S2,
class DestValue>
949 MultiArrayView<2, T2, S2> dest,
950 DestValue edge_marker)
952 vigra_precondition(2*src.shape()-
Shape2(1) == dest.shape(),
953 "regionImageToCrackEdgeImage(): shape mismatch between input and output.");
1082 template <
class SrcIterator,
class SrcAccessor,
1083 class DestIterator,
class DestAccessor,
class DestValue>
1085 SrcIterator sul, SrcIterator slr, SrcAccessor sa,
1086 DestIterator dul, DestAccessor da,
1087 DestValue edge_marker)
1089 int w = slr.x - sul.x;
1090 int h = slr.y - sul.y;
1093 const Diff2D right(1,0);
1094 const Diff2D left(-1,0);
1095 const Diff2D bottomright(1,1);
1096 const Diff2D bottom(0,1);
1097 const Diff2D top(0,-1);
1099 SrcIterator iy = sul;
1100 DestIterator dy = dul;
1102 for(y=0; y<h-1; ++y, ++iy.y, ++dy.y)
1104 SrcIterator ix = iy;
1105 DestIterator dx = dy;
1107 for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
1109 if(sa(ix, right) != sa(ix))
1111 da.set(edge_marker, dx);
1113 if(sa(ix, bottom) != sa(ix))
1115 da.set(edge_marker, dx);
1119 if(sa(ix, bottom) != sa(ix))
1121 da.set(edge_marker, dx);
1125 SrcIterator ix = iy;
1126 DestIterator dx = dy;
1128 for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
1130 if(sa(ix, right) != sa(ix))
1132 da.set(edge_marker, dx);
1137 template <
class SrcIterator,
class SrcAccessor,
1138 class DestIterator,
class DestAccessor,
class DestValue>
1141 pair<DestIterator, DestAccessor> dest,
1142 DestValue edge_marker)
1145 dest.first, dest.second,
1149 template <
class T1,
class S1,
1150 class T2,
class S2,
class DestValue>
1153 MultiArrayView<2, T2, S2> dest,
1154 DestValue edge_marker)
1156 vigra_precondition(src.shape() == dest.shape(),
1157 "regionImageToEdgeImage(): shape mismatch between input and output.");
1167 #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.
MultiArrayShape< 2 >::type Shape2
shape type for MultiArray<2, T>
Definition: multi_shape.hxx:241
void regionImageToCrackEdgeImage(...)
Transform a labeled image into a crack edge (interpixel edge) image.
detail::SelectBiggestIntegerType< detail::SignedIntTypes >::type IntBiggest
the biggest signed integer type of the system
Definition: sized_int.hxx:188