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

labelimage.hxx VIGRA

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 */
838 
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)
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 */
1085 
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)
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
unsigned int labelImage(...)
Find the connected components of a segmented image.
Definition: accessor.hxx:43
doxygen_overloaded_function(template<... > void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
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: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

© 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