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