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

© 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.10.0 (Mon Nov 18 2013)