[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

labelimage.hxx |

1 /************************************************************************/
2 /* */
3 /* Copyright 1998-2002 by Ullrich Koethe */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35
36
37 #ifndef VIGRA_LABELIMAGE_HXX
38 #define VIGRA_LABELIMAGE_HXX
39
40 #include <vector>
41 #include <functional>
42 #include "utilities.hxx"
43 #include "stdimage.hxx"
44 #include "union_find.hxx"
45 #include "sized_int.hxx"
46 #include "multi_shape.hxx"
47
48 namespace vigra {
49
50 /** \addtogroup Labeling Connected Components Labeling
51 The 2-dimensional connected components algorithms may use either 4 or 8 connectivity.
52 By means of a functor the merge criterion can be defined arbitrarily.
53 */
54 //@{
55
56 /********************************************************/
57 /* */
58 /* labelImage */
59 /* */
60 /********************************************************/
61
62 /** \brief Find the connected components of a segmented image.
63
64 Deprecated. Use \ref labelMultiArray() instead.
65
66 Connected components are defined as regions with uniform pixel
67 values. Thus, <TT>T1</TT> either must be
68 equality comparable, or a suitable EqualityFunctor must be
69 provided that realizes the desired predicate. The
70 destination's value type <tt>T2</tt> should be large enough to hold the labels
71 without overflow. Region numbers will be a consecutive sequence
72 starting with one and ending with the region number returned by
73 the function (inclusive). The parameter '<TT>eight_neighbors</TT>'
74 determines whether the regions should be 4-connected (false) or
75 8-connected (true).
76
77 Return: the number of regions found (= largest region label)
78
79 See \ref labelMultiArray() for a dimension-independent implementation of
80 connected components labelling.
81
82 <b> Declarations:</b>
83
84 pass 2D array views:
85 \code
86 namespace vigra {
87 template <class T1, class S1,
88 class T2, class S2,
89 class EqualityFunctor = std::equal_to<T1> >
90 unsigned int
91 labelImage(MultiArrayView<2, T1, S1> const & src,
92 MultiArrayView<2, T2, S2> dest,
93 bool eight_neighbors, EqualityFunctor equal = EqualityFunctor());
94 }
95 \endcode
96
97 \deprecatedAPI{labelImage}
98 pass \ref ImageIterators and \ref DataAccessors :
99 \code
100 namespace vigra {
101 template <class SrcIterator, class SrcAccessor,
102 class DestIterator, class DestAccessor>
103 unsigned int labelImage(SrcIterator upperlefts,
104 SrcIterator lowerrights, SrcAccessor sa,
105 DestIterator upperleftd, DestAccessor da,
106 bool eight_neighbors);
107
108 template <class SrcIterator, class SrcAccessor,
109 class DestIterator, class DestAccessor,
110 class EqualityFunctor>
111 unsigned int labelImage(SrcIterator upperlefts,
112 SrcIterator lowerrights, SrcAccessor sa,
113 DestIterator upperleftd, DestAccessor da,
114 bool eight_neighbors, EqualityFunctor equal);
115 }
116 \endcode
117 use argument objects in conjunction with \ref ArgumentObjectFactories :
118 \code
119 namespace vigra {
120 template <class SrcIterator, class SrcAccessor,
121 class DestIterator, class DestAccessor>
122 unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
123 pair<DestIterator, DestAccessor> dest,
124 bool eight_neighbors);
125
126 template <class SrcIterator, class SrcAccessor,
127 class DestIterator, class DestAccessor,
128 class EqualityFunctor>
129 unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
130 pair<DestIterator, DestAccessor> dest,
131 bool eight_neighbors, EqualityFunctor equal)
132 }
133 \endcode
134 \deprecatedEnd
135
136 <b> Usage:</b>
137
138 <b>\#include</b> <vigra/labelimage.hxx><br>
139 Namespace: vigra
140
141 \code
142 MultiArray<2, unsigned char> src(w,h);
143 MultiArray<2, unsigned int> labels(w,h);
144
145 // threshold at 128
146 transformImage(src, src, Threshold<int, int>(128, 256, 0, 255));
147
148 // find 4-connected regions
149 labelImage(src, labels, false);
150 \endcode
151
152 \deprecatedUsage{labelImage}
153 \code
154 vigra::BImage src(w,h);
155 vigra::IImage labels(w,h);
156
157 // threshold at 128
158 vigra::transformImage(srcImageRange(src), destImage(src),
159 vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
160 128, 256, 0, 255));
161
162 // find 4-connected regions
163 vigra::labelImage(srcImageRange(src), destImage(labels), false);
164 \endcode
165 <b> Required Interface:</b>
166 \code
167 SrcImageIterator src_upperleft, src_lowerright;
168 DestImageIterator dest_upperleft;
169
170 SrcAccessor src_accessor;
171 DestAccessor dest_accessor;
172
173 SrcAccessor::value_type u = src_accessor(src_upperleft);
174
175 u == u // first form
176
177 EqualityFunctor equal; // second form
178 equal(u, u) // second form
179
180 int i;
181 dest_accessor.set(i, dest_upperleft);
182 \endcode
183 \deprecatedEnd
184 */
185 doxygen_overloaded_function(template <...> unsigned int labelImage)
186
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)
194 {
195 typedef typename DestAccessor::value_type LabelType;
196
197 int w = lowerrights.x - upperlefts.x;
198 int h = lowerrights.y - upperlefts.y;
199 int x,y,i;
200
201 const Diff2D neighbor[] = {
202 Diff2D(-1,0), // left
203 Diff2D(-1,-1), // topleft
204 Diff2D(0,-1), // top
205 Diff2D(1,-1) // topright
206 };
207
208 const int left = 0, /* unused: topleft = 1, */ top = 2, topright = 3;
209 int step = eight_neighbors ? 1 : 2;
210
211 SrcIterator ys = upperlefts;
212 DestIterator yd = upperleftd;
213
214 UnionFindArray<LabelType> label;
215
216 // pass 1: scan image from upper left to lower right
217 // to find connected components
218
219 // Each component will be represented by a tree of pixels. Each
220 // pixel contains the scan order address of its parent in the
221 // tree. In order for pass 2 to work correctly, the parent must
222 // always have a smaller scan order address than the child.
223 // Therefore, we can merge trees only at their roots, because the
224 // root of the combined tree must have the smallest scan order
225 // address among all the tree's pixels/ nodes. The root of each
226 // tree is distinguished by pointing to itself (it contains its
227 // own scan order address). This condition is enforced whenever a
228 // new region is found or two regions are merged
229
230
231 for(y = 0; y != h; ++y, ++ys.y, ++yd.y)
232 {
233 SrcIterator xs = ys;
234 DestIterator xd = yd;
235
236 int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top);
237
238 for(x = 0; x != w; ++x, ++xs.x, ++xd.x)
239 {
240 int beginNeighbor = (x == 0) ? top : left;
241 if(x == w-1 && endNeighbor == topright) endNeighbor = top;
242
243 for(i=beginNeighbor; i<=endNeighbor; i+=step)
244 {
245 if(equal(sa(xs), sa(xs, neighbor[i])))
246 {
247 LabelType neighborIndex = label.findIndex(da(xd,neighbor[i]));
248
249 for(int j=i+2; j<=endNeighbor; j+=step)
250 {
251 if(equal(sa(xs), sa(xs, neighbor[j])))
252 {
253 neighborIndex = label.makeUnion(da(xd, neighbor[j]), neighborIndex);
254 break;
255 }
256 }
257 da.set(neighborIndex, xd);
258 break;
259 }
260
261 }
262 if(i > endNeighbor)
263 {
264 da.set(label.makeNewIndex(), xd);
265 }
266 }
267 }
268
269 // pass 2: assign one label to each region (tree)
270 // so that labels form a consecutive sequence 1, 2, ...
271 unsigned int count = label.makeContiguous();
272
273 yd = upperleftd;
274 for(y=0; y != h; ++y, ++yd.y)
275 {
276 typename DestIterator::row_iterator xd = yd.rowIterator();
277 for(x = 0; x != w; ++x, ++xd)
278 {
279 da.set(label.findLabel(da(xd)), xd);
280 }
281 }
282 return count;
283 }
284
285 template <class SrcIterator, class SrcAccessor,
286 class DestIterator, class DestAccessor>
287 inline
288 unsigned int labelImage(SrcIterator upperlefts,
289 SrcIterator lowerrights, SrcAccessor sa,
290 DestIterator upperleftd, DestAccessor da,
291 bool eight_neighbors)
292 {
293 return labelImage(upperlefts, lowerrights, sa,
294 upperleftd, da, eight_neighbors,
295 std::equal_to<typename SrcAccessor::value_type>());
296 }
297
298 template <class SrcIterator, class SrcAccessor,
299 class DestIterator, class DestAccessor,
300 class EqualityFunctor>
301 inline unsigned int
302 labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
303 pair<DestIterator, DestAccessor> dest,
304 bool eight_neighbors, EqualityFunctor equal)
305 {
306 return labelImage(src.first, src.second, src.third,
307 dest.first, dest.second, eight_neighbors, equal);
308 }
309
310 template <class SrcIterator, class SrcAccessor,
311 class DestIterator, class DestAccessor>
312 inline unsigned int
313 labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
314 pair<DestIterator, DestAccessor> dest,
315 bool eight_neighbors)
316 {
317 return labelImage(src.first, src.second, src.third,
318 dest.first, dest.second, eight_neighbors,
319 std::equal_to<typename SrcAccessor::value_type>());
320 }
321
322 template <class T1, class S1,
323 class T2, class S2,
324 class EqualityFunctor>
325 inline unsigned int
326 labelImage(MultiArrayView<2, T1, S1> const & src,
327 MultiArrayView<2, T2, S2> dest,
328 bool eight_neighbors, EqualityFunctor equal)
329 {
330 vigra_precondition(src.shape() == dest.shape(),
331 "labelImage(): shape mismatch between input and output.");
332 return labelImage(srcImageRange(src),
333 destImage(dest), eight_neighbors, equal);
334 }
335
336 template <class T1, class S1,
337 class T2, class S2>
338 inline unsigned int
339 labelImage(MultiArrayView<2, T1, S1> const & src,
340 MultiArrayView<2, T2, S2> dest,
341 bool eight_neighbors)
342 {
343 return labelImage(srcImageRange(src),
344 destImage(dest), eight_neighbors,
345 std::equal_to<T1>());
346 }
347
348 /********************************************************/
349 /* */
350 /* labelImageWithBackground */
351 /* */
352 /********************************************************/
353
354 /** \brief Find the connected components of a segmented image,
355 excluding the background from labeling.
356
357 Deprecated. Use \ref labelMultiArray() instead.
358
359 This function works like \ref labelImage(), but considers all background pixels
360 (i.e. pixels having the given '<TT>background_value</TT>') as a single region that
361 is ignored when determining connected components and remains untouched in the
362 destination image. Usually, you will zero-initialize the output image, so that
363 the background gets label 0 (remember that actual region labels start at one).
364
365 Return: the number of non-background regions found (= largest region label)
366
367 See \ref labelMultiArrayWithBackground() for a dimension-independent implementation
368 if this algorithm.
369
370 <b> Declarations:</b>
371
372 pass 2D array views:
373 \code
374 namespace vigra {
375 template <class T1, class S1,
376 class T2, class S2,
377 class ValueType,
378 class EqualityFunctor = std::equal_to<T1> >
379 unsigned int
380 labelImageWithBackground(MultiArrayView<2, T1, S1> const & src,
381 MultiArrayView<2, T2, S2> dest,
382 bool eight_neighbors,
383 ValueType background_value,
384 EqualityFunctor equal = EqualityFunctor());
385 }
386 \endcode
387
388 \deprecatedAPI{labelImageWithBackground}
389 pass \ref ImageIterators and \ref DataAccessors :
390 \code
391 namespace vigra {
392 template <class SrcIterator, class SrcAccessor,
393 class DestIterator, class DestAccessor,
394 class ValueType>
395 int labelImageWithBackground(SrcIterator upperlefts,
396 SrcIterator lowerrights, SrcAccessor sa,
397 DestIterator upperleftd, DestAccessor da,
398 bool eight_neighbors,
399 ValueType background_value );
400
401 template <class SrcIterator, class SrcAccessor,
402 class DestIterator, class DestAccessor,
403 class ValueType, class EqualityFunctor>
404 int labelImageWithBackground(SrcIterator upperlefts,
405 SrcIterator lowerrights, SrcAccessor sa,
406 DestIterator upperleftd, DestAccessor da,
407 bool eight_neighbors,
408 ValueType background_value, EqualityFunctor equal);
409 }
410 \endcode
411 use argument objects in conjunction with \ref ArgumentObjectFactories :
412 \code
413 namespace vigra {
414 template <class SrcIterator, class SrcAccessor,
415 class DestIterator, class DestAccessor,
416 class ValueType>
417 int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src,
418 pair<DestIterator, DestAccessor> dest,
419 bool eight_neighbors,
420 ValueType background_value);
421
422 template <class SrcIterator, class SrcAccessor,
423 class DestIterator, class DestAccessor,
424 class ValueType, class EqualityFunctor>
425 int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src,
426 pair<DestIterator, DestAccessor> dest,
427 bool eight_neighbors,
428 ValueType background_value, EqualityFunctor equal);
429 }
430 \endcode
431 \deprecatedEnd
432
433 <b> Usage:</b>
434
435 <b>\#include</b> <vigra/labelimage.hxx><br>
436 Namespace: vigra
437
438 \code
439 MultiArray<2, unsigned char> src(w,h);
440 MultiArray<2, unsigned int> labels(w,h);
441
442 // threshold at 128
443 transformImage(src, src, Threshold<int, int>(128, 256, 0, 255));
444
445 // find 4-connected regions of foreground (= white pixels) only
446 labelImageWithBackground(src, labels, false, 0);
447 \endcode
448
449 \deprecatedUsage{labelImageWithBackground}
450 \code
451 vigra::BImage src(w,h);
452 vigra::IImage labels(w,h);
453
454 // threshold at 128
455 vigra::transformImage(srcImageRange(src), destImage(src),
456 vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
457 128, 256, 0, 255));
458
459 // find 4-connected regions of foreground (= white pixels) only
460 vigra::labelImageWithBackground(srcImageRange(src), destImage(labels),
461 false, 0);
462 \endcode
463 <b> Required Interface:</b>
464 \code
465 SrcImageIterator src_upperleft, src_lowerright;
466 DestImageIterator dest_upperleft;
467
468 SrcAccessor src_accessor;
469 DestAccessor dest_accessor;
470
471 SrcAccessor::value_type u = src_accessor(src_upperleft);
472 ValueType background_value;
473
474 u == u // first form
475 u == background_value // first form
476
477 EqualityFunctor equal; // second form
478 equal(u, u) // second form
479 equal(u, background_value) // second form
480
481 int i;
482 dest_accessor.set(i, dest_upperleft);
483 \endcode
484 \deprecatedEnd
485 */
486 doxygen_overloaded_function(template <...> unsigned int labelImageWithBackground)
487
488 template <class SrcIterator, class SrcAccessor,
489 class DestIterator, class DestAccessor,
490 class ValueType, class EqualityFunctor>
491 unsigned int labelImageWithBackground(
492 SrcIterator upperlefts,
493 SrcIterator lowerrights, SrcAccessor sa,
494 DestIterator upperleftd, DestAccessor da,
495 bool eight_neighbors,
496 ValueType background_value, EqualityFunctor equal)
497 {
498 int w = lowerrights.x - upperlefts.x;
499 int h = lowerrights.y - upperlefts.y;
500 int x,y,i;
501
502 const Diff2D neighbor[] = {
503 Diff2D(-1,0), // left
504 Diff2D(-1,-1), // topleft
505 Diff2D(0,-1), // top
506 Diff2D(1,-1) // topright
507 };
508
509 const int left = 0, /* unused: topleft = 1,*/ top = 2, topright = 3;
510 int step = eight_neighbors ? 1 : 2;
511
512 SrcIterator ys(upperlefts);
513 SrcIterator xs(ys);
514
515 // temporary image to store region labels
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);
521
522 // pass 1: scan image from upper left to lower right
523 // find connected components
524
525 for(y = 0; y != h; ++y, ++ys.y, ++yt.y)
526 {
527 xs = ys;
528 xt = yt;
529
530 int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top);
531
532 for(x = 0; x != w; ++x, ++xs.x, ++xt.x)
533 {
534 if(equal(sa(xs), background_value))
535 {
536 *xt = -1;
537 }
538 else
539 {
540 int beginNeighbor = (x == 0) ? top : left;
541 if(x == w-1 && endNeighbor == topright) endNeighbor = top;
542
543 for(i=beginNeighbor; i<=endNeighbor; i+=step)
544 {
545 if(equal(sa(xs), sa(xs, neighbor[i])))
546 {
547 IntBiggest neighborIndex = xt[neighbor[i]];
548
549 for(int j=i+2; j<=endNeighbor; j+=step)
550 {
551 if(equal(sa(xs), sa(xs, neighbor[j])))
552 {
553 IntBiggest neighborLabel1 = xt[neighbor[j]];
554
555 if(neighborIndex != neighborLabel1)
556 {
557 // find roots of the region trees
558 while(neighborIndex != label[neighborIndex])
559 {
560 neighborIndex = label[neighborIndex];
561 }
562 while(neighborLabel1 != label[neighborLabel1])
563 {
564 neighborLabel1 = label[neighborLabel1];
565 }
566
567 // merge the trees
568 if(neighborLabel1 < neighborIndex)
569 {
570 label[neighborIndex] = neighborLabel1;
571 neighborIndex = neighborLabel1;
572 }
573 else if(neighborIndex < neighborLabel1)
574 {
575 label[neighborLabel1] = neighborIndex;
576 }
577 }
578 break;
579 }
580 }
581 *xt = neighborIndex;
582 break;
583 }
584
585 }
586 if(i > endNeighbor)
587 {
588 // new region
589 // The initial label of a new region equals the
590 // scan order address of it's first pixel.
591 // This is essential for correct operation of the algorithm.
592 *xt = x + y*w;
593 }
594 }
595 }
596 }
597
598 // pass 2: assign contiguous labels to the regions
599 DestIterator yd(upperleftd);
600
601 int count = 0;
602 i = 0;
603 for(y=0; y != h; ++y, ++yd.y)
604 {
605 DestIterator xd(yd);
606 for(x = 0; x != w; ++x, ++xd.x, ++i)
607 {
608 if(label[i] == -1) continue;
609
610 if(label[i] == i)
611 {
612 label[i] = count++;
613 }
614 else
615 {
616 label[i] = label[label[i]];
617 }
618 da.set(label[i]+1, xd);
619 }
620 }
621
622 return count;
623 }
624
625 template <class SrcIterator, class SrcAccessor,
626 class DestIterator, class DestAccessor,
627 class ValueType>
628 inline
629 unsigned int labelImageWithBackground(
630 SrcIterator upperlefts,
631 SrcIterator lowerrights, SrcAccessor sa,
632 DestIterator upperleftd, DestAccessor da,
633 bool eight_neighbors,
634 ValueType background_value)
635 {
636 return labelImageWithBackground(upperlefts, lowerrights, sa,
637 upperleftd, da,
638 eight_neighbors, background_value,
639 std::equal_to<typename SrcAccessor::value_type>());
640 }
641
642 template <class SrcIterator, class SrcAccessor,
643 class DestIterator, class DestAccessor,
644 class ValueType, class EqualityFunctor>
645 inline unsigned int
646 labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src,
647 pair<DestIterator, DestAccessor> dest,
648 bool eight_neighbors,
649 ValueType background_value, EqualityFunctor equal)
650 {
651 return labelImageWithBackground(src.first, src.second, src.third,
652 dest.first, dest.second,
653 eight_neighbors, background_value, equal);
654 }
655
656 template <class SrcIterator, class SrcAccessor,
657 class DestIterator, class DestAccessor,
658 class ValueType>
659 inline unsigned int
660 labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src,
661 pair<DestIterator, DestAccessor> dest,
662 bool eight_neighbors,
663 ValueType background_value)
664 {
665 return labelImageWithBackground(src.first, src.second, src.third,
666 dest.first, dest.second,
667 eight_neighbors, background_value,
668 std::equal_to<typename SrcAccessor::value_type>());
669 }
670
671 template <class T1, class S1,
672 class T2, class S2,
673 class ValueType, class EqualityFunctor>
674 inline unsigned int
675 labelImageWithBackground(MultiArrayView<2, T1, S1> const & src,
676 MultiArrayView<2, T2, S2> dest,
677 bool eight_neighbors,
678 ValueType background_value, EqualityFunctor equal)
679 {
680 vigra_precondition(src.shape() == dest.shape(),
681 "labelImageWithBackground(): shape mismatch between input and output.");
682 return labelImageWithBackground(srcImageRange(src),
683 destImage(dest),
684 eight_neighbors, background_value, equal);
685 }
686
687 template <class T1, class S1,
688 class T2, class S2,
689 class ValueType>
690 inline unsigned int
691 labelImageWithBackground(MultiArrayView<2, T1, S1> const & src,
692 MultiArrayView<2, T2, S2> dest,
693 bool eight_neighbors,
694 ValueType background_value)
695 {
696 vigra_precondition(src.shape() == dest.shape(),
697 "labelImageWithBackground(): shape mismatch between input and output.");
698 return labelImageWithBackground(srcImageRange(src),
699 destImage(dest),
700 eight_neighbors, background_value,
701 std::equal_to<T1>());
702 }
703
704 /********************************************************/
705 /* */
706 /* regionImageToCrackEdgeImage */
707 /* */
708 /********************************************************/
709
710 /** \brief Transform a labeled image into a crack edge (interpixel edge) image.
711
712 <b> Declarations:</b>
713
714 pass 2D array views:
715 \code
716 namespace vigra {
717 template <class T1, class S1,
718 class T2, class S2, class DestValue>
719 void
720 regionImageToCrackEdgeImage(MultiArrayView<2, T1, S1> const & src,
721 MultiArrayView<2, T2, S2> dest,
722 DestValue edge_marker);
723 }
724 \endcode
725
726 \deprecatedAPI{regionImageToCrackEdgeImage}
727 pass \ref ImageIterators and \ref DataAccessors :
728 \code
729 namespace vigra {
730 template <class SrcIterator, class SrcAccessor,
731 class DestIterator, class DestAccessor, class DestValue>
732 void regionImageToCrackEdgeImage(
733 SrcIterator sul, SrcIterator slr, SrcAccessor sa,
734 DestIterator dul, DestAccessor da,
735 DestValue edge_marker)
736 }
737 \endcode
738 use argument objects in conjunction with \ref ArgumentObjectFactories :
739 \code
740 namespace vigra {
741 template <class SrcIterator, class SrcAccessor,
742 class DestIterator, class DestAccessor, class DestValue>
743 void regionImageToCrackEdgeImage(
744 triple<SrcIterator, SrcIterator, SrcAccessor> src,
745 pair<DestIterator, DestAccessor> dest,
746 DestValue edge_marker)
747 }
748 \endcode
749 \deprecatedEnd
750
751 This algorithm inserts border pixels (so called "crack edges" or "interpixel edges")
752 between regions in a labeled image like this (<TT>a</TT> and
753 <TT>c</TT> are the original labels, and <TT>0</TT> is the value of
754 <TT>edge_marker</TT> and denotes the inserted edges):
755
756 \code
757 original image insert zero- and one-cells
758
759 a 0 c c c
760 a c c a 0 0 0 c
761 a a c => a a a 0 c
762 a a a a a a 0 0
763 a a a a a
764 \endcode
765
766 The algorithm assumes that the original labeled image contains
767 no background. Therefore, it is suitable as a post-processing
768 operation of \ref labelImage() or \ref seededRegionGrowing().
769
770 The destination image must be twice the size of the original
771 (precisely, <TT>(2*w-1)</TT> by <TT>(2*h-1)</TT> pixels). The
772 source value type (<TT>SrcAccessor::value-type</TT>) must be
773 equality-comparable.
774
775 <b> Usage:</b>
776
777 <b>\#include</b> <vigra/labelimage.hxx><br>
778 Namespace: vigra
779
780 \code
781 MultiArray<2, unsigned char> src(w,h);
782 MultiArray<2, unsigned int> labels(w,h),
783 cellgrid(2*w-1, 2*h-1);
784
785 // threshold at 128
786 transformImage(src, src, Threshold<int, int>(128, 256, 0, 255));
787
788 // find 4-connected regions
789 labelImage(src, labels, false);
790
791 // create cell grid image, mark edges with 0
792 regionImageToCrackEdgeImage(labels, cellgrid, 0);
793 \endcode
794
795 \deprecatedUsage{regionImageToCrackEdgeImage}
796 \code
797 vigra::BImage src(w,h);
798 vigra::IImage labels(w,h);
799 vigra::IImage cellgrid(2*w-1, 2*h-1);
800
801 // threshold at 128
802 vigra::transformImage(srcImageRange(src), destImage(src),
803 vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
804 128, 256, 0, 255));
805
806 // find 4-connected regions
807 vigra::labelImage(srcImageRange(src), destImage(labels), false);
808
809 // create cell grid image, mark edges with 0
810 vigra::regionImageToCrackEdgeImage(srcImageRange(labels), destImage(cellgrid), 0);
811 \endcode
812 <b> Required Interface:</b>
813 \code
814 ImageIterator src_upperleft, src_lowerright;
815 ImageIterator dest_upperleft;
816
817 SrcAccessor src_accessor;
818 DestAccessor dest_accessor;
819
820 SrcAccessor::value_type u = src_accessor(src_upperleft);
821
822 u != u
823
824 DestValue edge_marker;
825 dest_accessor.set(edge_marker, dest_upperleft);
826 \endcode
827 \deprecatedEnd
828
829 <b> Preconditions:</b>
830
831 The destination image must have twice the size of the source:
832 \code
833 w_dest = 2 * w_src - 1
834 h_dest = 2 * h_src - 1
835 \endcode
836 */
837 doxygen_overloaded_function(template <...> void regionImageToCrackEdgeImage)
838
839 template <class SrcIterator, class SrcAccessor,
840 class DestIterator, class DestAccessor, class DestValue>
841 void regionImageToCrackEdgeImage(
842 SrcIterator sul, SrcIterator slr, SrcAccessor sa,
843 DestIterator dul, DestAccessor da,
844 DestValue edge_marker)
845 {
846 int w = slr.x - sul.x;
847 int h = slr.y - sul.y;
848 int x,y;
849
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);
855
856 SrcIterator iy = sul;
857 DestIterator dy = dul;
858
859 for(y=0; y<h-1; ++y, ++iy.y, dy.y+=2)
860 {
861 SrcIterator ix = iy;
862 DestIterator dx = dy;
863
864 for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
865 {
866 da.set(sa(ix), dx);
867 da.set(sa(ix), dx, bottomright);
868
869 if(sa(ix, right) != sa(ix))
870 {
871 da.set(edge_marker, dx, right);
872 }
873 else
874 {
875 da.set(sa(ix), dx, right);
876 }
877 if(sa(ix, bottom) != sa(ix))
878 {
879 da.set(edge_marker, dx, bottom);
880 }
881 else
882 {
883 da.set(sa(ix), dx, bottom);
884 }
885
886 }
887
888 da.set(sa(ix), dx);
889 if(sa(ix, bottom) != sa(ix))
890 {
891 da.set(edge_marker, dx, bottom);
892 }
893 else
894 {
895 da.set(sa(ix), dx, bottom);
896 }
897 }
898
899 SrcIterator ix = iy;
900 DestIterator dx = dy;
901
902 for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
903 {
904 da.set(sa(ix), dx);
905 if(sa(ix, right) != sa(ix))
906 {
907 da.set(edge_marker, dx, right);
908 }
909 else
910 {
911 da.set(sa(ix), dx, right);
912 }
913 }
914 da.set(sa(ix), dx);
915
916 dy = dul + Diff2D(1,1);
917
918 const Diff2D dist[] = {right, top, left, bottom };
919 // find missing 0-cells
920 for(y=0; y<h-1; ++y, dy.y+=2)
921 {
922 DestIterator dx = dy;
923
924 for(x=0; x<w-1; ++x, dx.x+=2)
925 {
926 int i;
927 for(i=0; i<4; ++i)
928 {
929 if(da(dx, dist[i]) == edge_marker) break;
930 }
931
932 if(i < 4) da.set(edge_marker, dx);
933 }
934 }
935 }
936
937 template <class SrcIterator, class SrcAccessor,
938 class DestIterator, class DestAccessor, class DestValue>
939 inline void
940 regionImageToCrackEdgeImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
941 pair<DestIterator, DestAccessor> dest,
942 DestValue edge_marker)
943 {
944 regionImageToCrackEdgeImage(src.first, src.second, src.third,
945 dest.first, dest.second,
946 edge_marker);
947 }
948
949 template <class T1, class S1,
950 class T2, class S2, class DestValue>
951 inline void
952 regionImageToCrackEdgeImage(MultiArrayView<2, T1, S1> const & src,
953 MultiArrayView<2, T2, S2> dest,
954 DestValue edge_marker)
955 {
956 vigra_precondition(2*src.shape()-Shape2(1) == dest.shape(),
957 "regionImageToCrackEdgeImage(): shape mismatch between input and output.");
958 regionImageToCrackEdgeImage(srcImageRange(src),
959 destImage(dest),
960 edge_marker);
961 }
962
963 /********************************************************/
964 /* */
965 /* regionImageToEdgeImage */
966 /* */
967 /********************************************************/
968
969 /** \brief Transform a labeled image into an edge image.
970
971 <b> Declarations:</b>
972
973 pass 2D array views:
974 \code
975 namespace vigra {
976 template <class T1, class S1,
977 class T2, class S2, class DestValue>
978 void
979 regionImageToEdgeImage(MultiArrayView<2, T1, S1> const & src,
980 MultiArrayView<2, T2, S2> dest,
981 DestValue edge_marker);
982 }
983 \endcode
984
985 \deprecatedAPI{regionImageToEdgeImage}
986 pass \ref ImageIterators and \ref DataAccessors :
987 \code
988 namespace vigra {
989 template <class SrcIterator, class SrcAccessor,
990 class DestIterator, class DestAccessor, class DestValue>
991 void regionImageToEdgeImage(
992 SrcIterator sul, SrcIterator slr, SrcAccessor sa,
993 DestIterator dul, DestAccessor da,
994 DestValue edge_marker)
995 }
996 \endcode
997 use argument objects in conjunction with \ref ArgumentObjectFactories :
998 \code
999 namespace vigra {
1000 template <class SrcIterator, class SrcAccessor,
1001 class DestIterator, class DestAccessor, class DestValue>
1002 void regionImageToEdgeImage(
1003 triple<SrcIterator, SrcIterator, SrcAccessor> src,
1004 pair<DestIterator, DestAccessor> dest,
1005 DestValue edge_marker)
1006 }
1007 \endcode
1008 \deprecatedEnd
1009
1010 This algorithm marks all pixels with the given <TT>edge_marker</TT>
1011 which belong to a different region (label) than their right or lower
1012 neighbors:
1013
1014 \code
1015 original image edges
1016 (assuming edge_marker == 1)
1017
1018 a c c 1 1 *
1019 a a c => * 1 1
1020 a a a * * *
1021 \endcode
1022
1023 The non-edge pixels of the destination image will not be touched.
1024 The source value type <TT>T1</TT> must be
1025 equality-comparable.
1026
1027 <b> Usage:</b>
1028
1029 <b>\#include</b> <vigra/labelimage.hxx><br>
1030 Namespace: vigra
1031
1032 \code
1033 MultiArray<2, unsigned char> src(w,h),
1034 edges(w,h);
1035 MultiArray<2, unsigned int> labels(w,h);
1036
1037 edges = 255; // init background (non-edge) to 255
1038
1039 // threshold at 128
1040 transformImage(src, src, Threshold<int, int>(128, 256, 0, 255));
1041
1042 // find 4-connected regions
1043 labelImage(src, labels, false);
1044
1045 // create edge image, mark edges with 0
1046 regionImageToEdgeImage(labels, edges, 0);
1047 \endcode
1048
1049 \deprecatedUsage{regionImageToEdgeImage}
1050 \code
1051 vigra::BImage src(w,h);
1052 vigra::IImage labels(w,h);
1053 vigra::IImage edges(w, h);
1054 edges = 255; // init background (non-edge) to 255
1055
1056 // threshold at 128
1057 vigra::transformImage(srcImageRange(src), destImage(src),
1058 vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
1059 128, 256, 0, 255));
1060
1061 // find 4-connected regions
1062 vigra::labelImage(srcImageRange(src), destImage(labels), false);
1063
1064 // create edge image, mark edges with 0
1065 vigra::regionImageToEdgeImage(srcImageRange(labels), destImage(edges), 0);
1066 \endcode
1067 <b> Required Interface:</b>
1068 \code
1069 ImageIterator src_upperleft, src_lowerright;
1070 ImageIterator dest_upperleft;
1071
1072 SrcAccessor src_accessor;
1073 DestAccessor dest_accessor;
1074
1075 SrcAccessor::value_type u = src_accessor(src_upperleft);
1076
1077 u != u
1078
1079 DestValue edge_marker;
1080 dest_accessor.set(edge_marker, dest_upperleft);
1081 \endcode
1082 \deprecatedEnd
1083 */
1084 doxygen_overloaded_function(template <...> void regionImageToEdgeImage)
1085
1086 template <class SrcIterator, class SrcAccessor,
1087 class DestIterator, class DestAccessor, class DestValue>
1088 void regionImageToEdgeImage(
1089 SrcIterator sul, SrcIterator slr, SrcAccessor sa,
1090 DestIterator dul, DestAccessor da,
1091 DestValue edge_marker)
1092 {
1093 int w = slr.x - sul.x;
1094 int h = slr.y - sul.y;
1095 int x,y;
1096
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);
1102
1103 SrcIterator iy = sul;
1104 DestIterator dy = dul;
1105
1106 for(y=0; y<h-1; ++y, ++iy.y, ++dy.y)
1107 {
1108 SrcIterator ix = iy;
1109 DestIterator dx = dy;
1110
1111 for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
1112 {
1113 if(sa(ix, right) != sa(ix))
1114 {
1115 da.set(edge_marker, dx);
1116 }
1117 if(sa(ix, bottom) != sa(ix))
1118 {
1119 da.set(edge_marker, dx);
1120 }
1121 }
1122
1123 if(sa(ix, bottom) != sa(ix))
1124 {
1125 da.set(edge_marker, dx);
1126 }
1127 }
1128
1129 SrcIterator ix = iy;
1130 DestIterator dx = dy;
1131
1132 for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
1133 {
1134 if(sa(ix, right) != sa(ix))
1135 {
1136 da.set(edge_marker, dx);
1137 }
1138 }
1139 }
1140
1141 template <class SrcIterator, class SrcAccessor,
1142 class DestIterator, class DestAccessor, class DestValue>
1143 inline void
1144 regionImageToEdgeImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
1145 pair<DestIterator, DestAccessor> dest,
1146 DestValue edge_marker)
1147 {
1148 regionImageToEdgeImage(src.first, src.second, src.third,
1149 dest.first, dest.second,
1150 edge_marker);
1151 }
1152
1153 template <class T1, class S1,
1154 class T2, class S2, class DestValue>
1155 inline void
1156 regionImageToEdgeImage(MultiArrayView<2, T1, S1> const & src,
1157 MultiArrayView<2, T2, S2> dest,
1158 DestValue edge_marker)
1159 {
1160 vigra_precondition(src.shape() == dest.shape(),
1161 "regionImageToEdgeImage(): shape mismatch between input and output.");
1162 regionImageToEdgeImage(srcImageRange(src),
1163 destImage(dest),
1164 edge_marker);
1165 }
1166
1167 //@}
1168
1169 } // namespace vigra
1170
1171 #endif // VIGRA_LABELIMAGE_HXX
vigra::labelImage
unsigned int labelImage(...)
Find the connected components of a segmented image.
vigra
Definition: accessor.hxx:43
vigra::doxygen_overloaded_function
doxygen_overloaded_function(template<... > void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
vigra::labelImageWithBackground
unsigned int labelImageWithBackground(...)
Find the connected components of a segmented image, excluding the background from labeling...
vigra::regionImageToEdgeImage
void regionImageToEdgeImage(...)
Transform a labeled image into an edge image.
utilities.hxx
vigra::Shape2
MultiArrayShape< 2 >::type Shape2
shape type for MultiArray<2, T>
Definition: multi_shape.hxx:254
vigra::regionImageToCrackEdgeImage
void regionImageToCrackEdgeImage(...)
Transform a labeled image into a crack edge (interpixel edge) image.
vigra::IntBiggest
detail::SelectBiggestIntegerType< detail::SignedIntTypes >::type IntBiggest
the biggest signed integer type of the system
Definition: sized_int.hxx:188

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.11.0