37 #ifndef VIGRA_LABELIMAGE_HXX
38 #define VIGRA_LABELIMAGE_HXX
43 #include "stdimage.hxx"
44 #include "union_find.hxx"
45 #include "sized_int.hxx"
46 #include "multi_shape.hxx"
187 template <
class SrcIterator,
class SrcAccessor,
188 class DestIterator,
class DestAccessor,
189 class EqualityFunctor>
190 unsigned int labelImage(SrcIterator upperlefts,
191 SrcIterator lowerrights, SrcAccessor sa,
192 DestIterator upperleftd, DestAccessor da,
193 bool eight_neighbors, EqualityFunctor equal)
195 typedef typename DestAccessor::value_type LabelType;
197 int w = lowerrights.x - upperlefts.x;
198 int h = lowerrights.y - upperlefts.y;
201 const Diff2D neighbor[] = {
208 const int left = 0, top = 2, topright = 3;
209 int step = eight_neighbors ? 1 : 2;
211 SrcIterator ys = upperlefts;
212 DestIterator yd = upperleftd;
214 UnionFindArray<LabelType> label;
231 for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
234 DestIterator xd = yd;
236 int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top);
238 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
240 int beginNeighbor = (x == 0) ? top : left;
241 if(x == w-1 && endNeighbor == topright) endNeighbor = top;
243 for(i=beginNeighbor; i<=endNeighbor; i+=step)
245 if(equal(sa(xs), sa(xs, neighbor[i])))
247 LabelType neighborIndex = label.findIndex(da(xd,neighbor[i]));
249 for(
int j=i+2; j<=endNeighbor; j+=step)
251 if(equal(sa(xs), sa(xs, neighbor[j])))
253 neighborIndex = label.makeUnion(da(xd, neighbor[j]), neighborIndex);
257 da.set(neighborIndex, xd);
264 da.set(label.makeNewIndex(), xd);
271 unsigned int count = label.makeContiguous();
274 for(y=0; y != h; ++y, ++yd.y)
276 typename DestIterator::row_iterator xd = yd.rowIterator();
277 for(x = 0; x != w; ++x, ++xd)
279 da.set(label.findLabel(da(xd)), xd);
285 template <
class SrcIterator,
class SrcAccessor,
286 class DestIterator,
class DestAccessor>
288 unsigned int labelImage(SrcIterator upperlefts,
289 SrcIterator lowerrights, SrcAccessor sa,
290 DestIterator upperleftd, DestAccessor da,
291 bool eight_neighbors)
293 return labelImage(upperlefts, lowerrights, sa,
294 upperleftd, da, eight_neighbors,
295 std::equal_to<typename SrcAccessor::value_type>());
298 template <
class SrcIterator,
class SrcAccessor,
299 class DestIterator,
class DestAccessor,
300 class EqualityFunctor>
302 labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
303 pair<DestIterator, DestAccessor> dest,
304 bool eight_neighbors, EqualityFunctor equal)
306 return labelImage(src.first, src.second, src.third,
307 dest.first, dest.second, eight_neighbors, equal);
310 template <
class SrcIterator,
class SrcAccessor,
311 class DestIterator,
class DestAccessor>
313 labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
314 pair<DestIterator, DestAccessor> dest,
315 bool eight_neighbors)
317 return labelImage(src.first, src.second, src.third,
318 dest.first, dest.second, eight_neighbors,
319 std::equal_to<typename SrcAccessor::value_type>());
322 template <
class T1,
class S1,
324 class EqualityFunctor>
326 labelImage(MultiArrayView<2, T1, S1>
const & src,
327 MultiArrayView<2, T2, S2> dest,
328 bool eight_neighbors, EqualityFunctor equal)
330 vigra_precondition(src.shape() == dest.shape(),
331 "labelImage(): shape mismatch between input and output.");
333 destImage(dest), eight_neighbors, equal);
336 template <
class T1,
class S1,
339 labelImage(MultiArrayView<2, T1, S1>
const & src,
340 MultiArrayView<2, T2, S2> dest,
341 bool eight_neighbors)
344 destImage(dest), eight_neighbors,
345 std::equal_to<T1>());
488 template <
class SrcIterator,
class SrcAccessor,
489 class DestIterator,
class DestAccessor,
490 class ValueType,
class EqualityFunctor>
492 SrcIterator upperlefts,
493 SrcIterator lowerrights, SrcAccessor sa,
494 DestIterator upperleftd, DestAccessor da,
495 bool eight_neighbors,
496 ValueType background_value, EqualityFunctor equal)
498 int w = lowerrights.x - upperlefts.x;
499 int h = lowerrights.y - upperlefts.y;
502 const Diff2D neighbor[] = {
509 const int left = 0, top = 2, topright = 3;
510 int step = eight_neighbors ? 1 : 2;
512 SrcIterator ys(upperlefts);
516 typedef BasicImage<IntBiggest> TmpImage;
517 TmpImage labelimage(w, h);
518 TmpImage::ScanOrderIterator label = labelimage.begin();
519 TmpImage::Iterator yt = labelimage.upperLeft();
520 TmpImage::Iterator xt(yt);
525 for(y = 0; y != h; ++y, ++ys.y, ++yt.y)
530 int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top);
532 for(x = 0; x != w; ++x, ++xs.x, ++xt.x)
534 if(equal(sa(xs), background_value))
540 int beginNeighbor = (x == 0) ? top : left;
541 if(x == w-1 && endNeighbor == topright) endNeighbor = top;
543 for(i=beginNeighbor; i<=endNeighbor; i+=step)
545 if(equal(sa(xs), sa(xs, neighbor[i])))
549 for(
int j=i+2; j<=endNeighbor; j+=step)
551 if(equal(sa(xs), sa(xs, neighbor[j])))
555 if(neighborIndex != neighborLabel1)
558 while(neighborIndex != label[neighborIndex])
560 neighborIndex = label[neighborIndex];
562 while(neighborLabel1 != label[neighborLabel1])
564 neighborLabel1 = label[neighborLabel1];
568 if(neighborLabel1 < neighborIndex)
570 label[neighborIndex] = neighborLabel1;
571 neighborIndex = neighborLabel1;
573 else if(neighborIndex < neighborLabel1)
575 label[neighborLabel1] = neighborIndex;
599 DestIterator yd(upperleftd);
603 for(y=0; y != h; ++y, ++yd.y)
606 for(x = 0; x != w; ++x, ++xd.x, ++i)
608 if(label[i] == -1)
continue;
616 label[i] = label[label[i]];
618 da.set(label[i]+1, xd);
625 template <
class SrcIterator,
class SrcAccessor,
626 class DestIterator,
class DestAccessor,
630 SrcIterator upperlefts,
631 SrcIterator lowerrights, SrcAccessor sa,
632 DestIterator upperleftd, DestAccessor da,
633 bool eight_neighbors,
634 ValueType background_value)
638 eight_neighbors, background_value,
639 std::equal_to<typename SrcAccessor::value_type>());
642 template <
class SrcIterator,
class SrcAccessor,
643 class DestIterator,
class DestAccessor,
644 class ValueType,
class EqualityFunctor>
647 pair<DestIterator, DestAccessor> dest,
648 bool eight_neighbors,
649 ValueType background_value, EqualityFunctor equal)
652 dest.first, dest.second,
653 eight_neighbors, background_value, equal);
656 template <
class SrcIterator,
class SrcAccessor,
657 class DestIterator,
class DestAccessor,
661 pair<DestIterator, DestAccessor> dest,
662 bool eight_neighbors,
663 ValueType background_value)
666 dest.first, dest.second,
667 eight_neighbors, background_value,
668 std::equal_to<typename SrcAccessor::value_type>());
671 template <
class T1,
class S1,
673 class ValueType,
class EqualityFunctor>
676 MultiArrayView<2, T2, S2> dest,
677 bool eight_neighbors,
678 ValueType background_value, EqualityFunctor equal)
680 vigra_precondition(src.shape() == dest.shape(),
681 "labelImageWithBackground(): shape mismatch between input and output.");
684 eight_neighbors, background_value, equal);
687 template <
class T1,
class S1,
692 MultiArrayView<2, T2, S2> dest,
693 bool eight_neighbors,
694 ValueType background_value)
696 vigra_precondition(src.shape() == dest.shape(),
697 "labelImageWithBackground(): shape mismatch between input and output.");
700 eight_neighbors, background_value,
701 std::equal_to<T1>());
839 template <
class SrcIterator,
class SrcAccessor,
840 class DestIterator,
class DestAccessor,
class DestValue>
842 SrcIterator sul, SrcIterator slr, SrcAccessor sa,
843 DestIterator dul, DestAccessor da,
844 DestValue edge_marker)
846 int w = slr.x - sul.x;
847 int h = slr.y - sul.y;
850 const Diff2D right(1,0);
851 const Diff2D left(-1,0);
852 const Diff2D bottomright(1,1);
853 const Diff2D bottom(0,1);
854 const Diff2D top(0,-1);
856 SrcIterator iy = sul;
857 DestIterator dy = dul;
859 for(y=0; y<h-1; ++y, ++iy.y, dy.y+=2)
862 DestIterator dx = dy;
864 for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
867 da.set(sa(ix), dx, bottomright);
869 if(sa(ix, right) != sa(ix))
871 da.set(edge_marker, dx, right);
875 da.set(sa(ix), dx, right);
877 if(sa(ix, bottom) != sa(ix))
879 da.set(edge_marker, dx, bottom);
883 da.set(sa(ix), dx, bottom);
889 if(sa(ix, bottom) != sa(ix))
891 da.set(edge_marker, dx, bottom);
895 da.set(sa(ix), dx, bottom);
900 DestIterator dx = dy;
902 for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
905 if(sa(ix, right) != sa(ix))
907 da.set(edge_marker, dx, right);
911 da.set(sa(ix), dx, right);
916 dy = dul + Diff2D(1,1);
918 const Diff2D dist[] = {right, top, left, bottom };
920 for(y=0; y<h-1; ++y, dy.y+=2)
922 DestIterator dx = dy;
924 for(x=0; x<w-1; ++x, dx.x+=2)
929 if(da(dx, dist[i]) == edge_marker)
break;
932 if(i < 4) da.set(edge_marker, dx);
937 template <
class SrcIterator,
class SrcAccessor,
938 class DestIterator,
class DestAccessor,
class DestValue>
941 pair<DestIterator, DestAccessor> dest,
942 DestValue edge_marker)
945 dest.first, dest.second,
949 template <
class T1,
class S1,
950 class T2,
class S2,
class DestValue>
953 MultiArrayView<2, T2, S2> dest,
954 DestValue edge_marker)
956 vigra_precondition(2*src.shape()-
Shape2(1) == dest.shape(),
957 "regionImageToCrackEdgeImage(): shape mismatch between input and output.");
1086 template <
class SrcIterator,
class SrcAccessor,
1087 class DestIterator,
class DestAccessor,
class DestValue>
1089 SrcIterator sul, SrcIterator slr, SrcAccessor sa,
1090 DestIterator dul, DestAccessor da,
1091 DestValue edge_marker)
1093 int w = slr.x - sul.x;
1094 int h = slr.y - sul.y;
1097 const Diff2D right(1,0);
1098 const Diff2D left(-1,0);
1099 const Diff2D bottomright(1,1);
1100 const Diff2D bottom(0,1);
1101 const Diff2D top(0,-1);
1103 SrcIterator iy = sul;
1104 DestIterator dy = dul;
1106 for(y=0; y<h-1; ++y, ++iy.y, ++dy.y)
1108 SrcIterator ix = iy;
1109 DestIterator dx = dy;
1111 for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
1113 if(sa(ix, right) != sa(ix))
1115 da.set(edge_marker, dx);
1117 if(sa(ix, bottom) != sa(ix))
1119 da.set(edge_marker, dx);
1123 if(sa(ix, bottom) != sa(ix))
1125 da.set(edge_marker, dx);
1129 SrcIterator ix = iy;
1130 DestIterator dx = dy;
1132 for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
1134 if(sa(ix, right) != sa(ix))
1136 da.set(edge_marker, dx);
1141 template <
class SrcIterator,
class SrcAccessor,
1142 class DestIterator,
class DestAccessor,
class DestValue>
1145 pair<DestIterator, DestAccessor> dest,
1146 DestValue edge_marker)
1149 dest.first, dest.second,
1153 template <
class T1,
class S1,
1154 class T2,
class S2,
class DestValue>
1157 MultiArrayView<2, T2, S2> dest,
1158 DestValue edge_marker)
1160 vigra_precondition(src.shape() == dest.shape(),
1161 "regionImageToEdgeImage(): shape mismatch between input and output.");
1171 #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.
doxygen_overloaded_function(template<...> void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
MultiArrayShape< 2 >::type Shape2
shape type for MultiArray<2, T>
Definition: multi_shape.hxx:254
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