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

labelvolume.hxx
1 /************************************************************************/
2 /* */
3 /* Copyright 2006-2007 by F. Heinrich, B. Seppke, 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 #ifndef VIGRA_LABELVOLUME_HXX
37 #define VIGRA_LABELVOLUME_HXX
38 
39 
40 #include "voxelneighborhood.hxx"
41 #include "multi_array.hxx"
42 #include "union_find.hxx"
43 
44 namespace vigra{
45 
46 /** \addtogroup Labeling Connected Components Labeling
47  The 3-dimensional connected components algorithms may use either 6 or 26 connectivity.
48  By means of a functor the merge criterium can be defined arbitrarily.
49 */
50 //@{
51 
52 /********************************************************/
53 /* */
54 /* labelVolume */
55 /* */
56 /********************************************************/
57 
58 /** \brief Find the connected components of a segmented volume.
59 
60  <b> Declarations:</b>
61 
62  pass arguments explicitly:
63  \code
64  namespace vigra {
65 
66  template <class SrcIterator, class SrcAccessor,class SrcShape,
67  class DestIterator, class DestAccessor,
68  class Neighborhood3D>
69  unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
70  DestIterator d_Iter, DestAccessor da,
71  Neighborhood3D neighborhood3D);
72 
73  template <class SrcIterator, class SrcAccessor,class SrcShape,
74  class DestIterator, class DestAccessor,
75  class Neighborhood3D, class EqualityFunctor>
76  unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
77  DestIterator d_Iter, DestAccessor da,
78  Neighborhood3D neighborhood3D, EqualityFunctor equal);
79 
80  }
81  \endcode
82 
83  use argument objects in conjunction with \ref ArgumentObjectFactories :
84  \code
85  namespace vigra {
86 
87  template <class SrcIterator, class SrcAccessor,class SrcShape,
88  class DestIterator, class DestAccessor,
89  class Neighborhood3D>
90  unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
91  pair<DestIterator, DestAccessor> dest,
92  Neighborhood3D neighborhood3D);
93 
94  template <class SrcIterator, class SrcAccessor,class SrcShape,
95  class DestIterator, class DestAccessor,
96  class Neighborhood3D, class EqualityFunctor>
97  unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
98  pair<DestIterator, DestAccessor> dest,
99  Neighborhood3D neighborhood3D, EqualityFunctor equal);
100 
101  }
102  \endcode
103 
104  use with 3D-Six-Neighborhood:
105  \code
106  namespace vigra {
107 
108  template <class SrcIterator, class SrcAccessor,class SrcShape,
109  class DestIterator, class DestAccessor>
110  unsigned int labelVolumeSix(triple<SrcIterator, SrcShape, SrcAccessor> src,
111  pair<DestIterator, DestAccessor> dest);
112 
113  }
114  \endcode
115 
116  Connected components are defined as regions with uniform voxel
117  values. Thus, <TT>SrcAccessor::value_type</TT> either must be
118  equality comparable (first form), or an EqualityFunctor must be
119  provided that realizes the desired predicate (second form). The
120  destination's value type should be large enough to hold the labels
121  without overflow. Region numbers will be a consecutive sequence
122  starting with one and ending with the region number returned by
123  the function (inclusive).
124 
125  Return: the number of regions found (= largest region label)
126 
127  <b> Usage:</b>
128 
129  <b>\#include</b> <<a href="labelvolume_8hxx-source.html">vigra/labelvolume.hxx</a>><br>
130  Namespace: vigra
131 
132  \code
133  typedef vigra::MultiArray<3,int> IntVolume;
134  IntVolume src(IntVolume::difference_type(w,h,d));
135  IntVolume dest(IntVolume::difference_type(w,h,d));
136 
137  // find 6-connected regions
138  int max_region_label = vigra::labelVolumeSix(srcMultiArrayRange(src), destMultiArray(dest));
139 
140  // find 26-connected regions
141  int max_region_label = vigra::labelVolume(srcMultiArrayRange(src), destMultiArray(dest), NeighborCode3DTwentySix());
142  \endcode
143 
144  <b> Required Interface:</b>
145 
146  \code
147  SrcIterator src_begin;
148  SrcShape shape;
149  DestIterator dest_begin;
150 
151  SrcAccessor src_accessor;
152  DestAccessor dest_accessor;
153 
154  SrcAccessor::value_type u = src_accessor(src_begin);
155 
156  u == u // first form
157 
158  EqualityFunctor equal; // second form
159  equal(u, u) // second form
160 
161  int i;
162  dest_accessor.set(i, dest_begin);
163  \endcode
164 
165 */
166 doxygen_overloaded_function(template <...> unsigned int labelVolume)
167 
168 template <class SrcIterator, class SrcAccessor,class SrcShape,
169  class DestIterator, class DestAccessor,
170  class Neighborhood3D>
171 unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
172  DestIterator d_Iter, DestAccessor da,
173  Neighborhood3D neighborhood3D)
174 {
175  return labelVolume(s_Iter, srcShape, sa, d_Iter, da, neighborhood3D, std::equal_to<typename SrcAccessor::value_type>());
176 }
177 
178 template <class SrcIterator, class SrcAccessor,class SrcShape,
179  class DestIterator, class DestAccessor,
180  class Neighborhood3D>
181 unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
182  pair<DestIterator, DestAccessor> dest,
183  Neighborhood3D neighborhood3D)
184 {
185  return labelVolume(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, std::equal_to<typename SrcAccessor::value_type>());
186 }
187 
188 template <class SrcIterator, class SrcAccessor,class SrcShape,
189  class DestIterator, class DestAccessor,
190  class Neighborhood3D, class EqualityFunctor>
191 unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
192  pair<DestIterator, DestAccessor> dest,
193  Neighborhood3D neighborhood3D, EqualityFunctor equal)
194 {
195  return labelVolume(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, equal);
196 }
197 
198 template <class SrcIterator, class SrcAccessor,class SrcShape,
199  class DestIterator, class DestAccessor,
200  class Neighborhood3D, class EqualityFunctor>
201 unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
202  DestIterator d_Iter, DestAccessor da,
203  Neighborhood3D, EqualityFunctor equal)
204 {
205  typedef typename DestAccessor::value_type LabelType;
206 
207  //basically needed for iteration and border-checks
208  int w = srcShape[0], h = srcShape[1], d = srcShape[2];
209  int x,y,z;
210 
211  // temporary image to store region labels
212  detail::UnionFindArray<LabelType> label;
213 
214  //Declare traversers for all three dims at target
215  SrcIterator zs = s_Iter;
216  DestIterator zd = d_Iter;
217 
218  // initialize the neighborhood traversers
219  NeighborOffsetCirculator<Neighborhood3D> nce(Neighborhood3D::CausalLast);
220  ++nce;
221  // pass 1: scan image from upper left front to lower right back
222  // to find connected components
223 
224  // Each component will be represented by a tree of pixels. Each
225  // pixel contains the scan order address of its parent in the
226  // tree. In order for pass 2 to work correctly, the parent must
227  // always have a smaller scan order address than the child.
228  // Therefore, we can merge trees only at their roots, because the
229  // root of the combined tree must have the smallest scan order
230  // address among all the tree's pixels/ nodes. The root of each
231  // tree is distinguished by pointing to itself (it contains its
232  // own scan order address). This condition is enforced whenever a
233  // new region is found or two regions are merged
234  for(z = 0; z != d; ++z, ++zs.dim2(), ++zd.dim2())
235  {
236  SrcIterator ys(zs);
237  DestIterator yd(zd);
238 
239  for(y = 0; y != h; ++y, ++ys.dim1(), ++yd.dim1())
240  {
241  SrcIterator xs(ys);
242  DestIterator xd(yd);
243 
244  for(x = 0; x != w; ++x, ++xs.dim0(), ++xd.dim0())
245  {
246  LabelType currentLabel = label.nextFreeLabel();
247 
248  //queck whether there is a special border treatment to be used or not
249  AtVolumeBorder atBorder = isAtVolumeBorderCausal(x,y,z,w,h,d);
250 
251  //We are not at the border!
252  if(atBorder == NotAtBorder)
253  {
254  NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::CausalFirst);
255 
256  do
257  {
258  // if colors are equal
259  if(equal(sa(xs), sa(xs, *nc)))
260  {
261  currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
262  }
263  ++nc;
264  }
265  while(nc!=nce);
266  }
267  else //we are at a border - handle this!!
268  {
269  NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::nearBorderDirectionsCausal(atBorder,0));
270  int j=0;
271  while(nc.direction() != Neighborhood3D::Error)
272  {
273  // colors equal???
274  if(equal(sa(xs), sa(xs, *nc)))
275  {
276  currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
277  }
278  nc.turnTo(Neighborhood3D::nearBorderDirectionsCausal(atBorder,++j));
279  }
280  }
281  da.set(label.finalizeLabel(currentLabel), xd);
282  }
283  }
284  }
285 
286  LabelType count = label.makeContiguous();
287 
288  // pass 2: assign one label to each region (tree)
289  // so that labels form a consecutive sequence 1, 2, ...
290  zd = d_Iter;
291  for(z=0; z != d; ++z, ++zd.dim2())
292  {
293  DestIterator yd(zd);
294 
295  for(y=0; y != h; ++y, ++yd.dim1())
296  {
297  DestIterator xd(yd);
298 
299  for(x = 0; x != w; ++x, ++xd.dim0())
300  {
301  da.set(label[da(xd)], xd);
302  }
303  }
304  }
305  return count;
306 }
307 
308 /********************************************************/
309 /* */
310 /* labelVolumeSix */
311 /* */
312 /********************************************************/
313 
314 /** \brief Find the connected components of a segmented volume
315  using the 6-neighborhood.
316 
317  See \ref labelVolume() for detailed documentation.
318 
319 */
320 template <class SrcIterator, class SrcAccessor,class SrcShape,
321  class DestIterator, class DestAccessor>
322 unsigned int labelVolumeSix(triple<SrcIterator, SrcShape, SrcAccessor> src,
323  pair<DestIterator, DestAccessor> dest)
324 {
325  return labelVolume(src.first, src.second, src.third, dest.first, dest.second, NeighborCode3DSix(), std::equal_to<typename SrcAccessor::value_type>());
326 }
327 
328 
329 
330 
331 /********************************************************/
332 /* */
333 /* labelVolumeWithBackground */
334 /* */
335 /********************************************************/
336 
337 /** \brief Find the connected components of a segmented volume,
338  excluding the background from labeling.
339 
340  <b> Declarations:</b>
341 
342  pass arguments explicitly:
343  \code
344  namespace vigra {
345 
346  template <class SrcIterator, class SrcAccessor,class SrcShape,
347  class DestIterator, class DestAccessor,
348  class Neighborhood3D, class ValueType>
349  unsigned int labelVolumeWithBackground( SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
350  DestIterator d_Iter, DestAccessor da,
351  Neighborhood3D neighborhood3D, ValueType background_value);
352 
353  template <class SrcIterator, class SrcAccessor,class SrcShape,
354  class DestIterator, class DestAccessor,
355  class Neighborhood3D, class ValueType, class EqualityFunctor>
356  unsigned int labelVolumeWithBackground( SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
357  DestIterator d_Iter, DestAccessor da,
358  Neighborhood3D neighborhood3D, ValueType background_value,
359  EqualityFunctor equal);
360 
361  }
362  \endcode
363 
364  use argument objects in conjunction with \ref ArgumentObjectFactories :
365  \code
366  namespace vigra {
367 
368  template <class SrcIterator, class SrcAccessor,class SrcShape,
369  class DestIterator, class DestAccessor,
370  class Neighborhood3D, class ValueType>
371  unsigned int labelVolumeWithBackground( triple<SrcIterator, SrcShape, SrcAccessor> src,
372  pair<DestIterator, DestAccessor> dest,
373  Neighborhood3D neighborhood3D, ValueType background_value);
374 
375  template <class SrcIterator, class SrcAccessor,class SrcShape,
376  class DestIterator, class DestAccessor,
377  class Neighborhood3D, class ValueType, class EqualityFunctor>
378  unsigned int labelVolumeWithBackground( triple<SrcIterator, SrcShape, SrcAccessor> src,
379  pair<DestIterator, DestAccessor> dest,
380  Neighborhood3D neighborhood3D, ValueType background_value,
381  EqualityFunctor equal);
382 
383  }
384  \endcode
385 
386  Connected components are defined as regions with uniform voxel
387  values. Thus, <TT>SrcAccessor::value_type</TT> either must be
388  equality comparable (first form), or an EqualityFunctor must be
389  provided that realizes the desired predicate (second form). All
390  voxel equal to the given '<TT>background_value</TT>' are ignored
391  when determining connected components and remain untouched in the
392  destination volume.
393 
394  The destination's value type should be large enough to hold the
395  labels without overflow. Region numbers will be a consecutive
396  sequence starting with one and ending with the region number
397  returned by the function (inclusive).
398 
399  Return: the number of regions found (= largest region label)
400 
401  <b> Usage:</b>
402 
403  <b>\#include</b> <<a href="labelvolume_8hxx-source.html">vigra/labelvolume.hxx</a>><br>
404  Namespace: vigra
405 
406  \code
407  typedef vigra::MultiArray<3,int> IntVolume;
408  IntVolume src(IntVolume::difference_type(w,h,d));
409  IntVolume dest(IntVolume::difference_type(w,h,d));
410 
411  // find 6-connected regions
412  int max_region_label = vigra::labelVolumeWithBackground(
413  srcMultiArrayRange(src), destMultiArray(dest), NeighborCode3DSix(), 0);
414  \endcode
415 
416  <b> Required Interface:</b>
417 
418  \code
419  SrcIterator src_begin;
420  SrcShape shape;
421  DestIterator dest_begin;
422 
423  SrcAccessor src_accessor;
424  DestAccessor dest_accessor;
425 
426  SrcAccessor::value_type u = src_accessor(src_begin);
427 
428  u == u // first form
429 
430  EqualityFunctor equal; // second form
431  equal(u, u) // second form
432 
433  int i;
434  dest_accessor.set(i, dest_begin);
435  \endcode
436 
437 */
438 doxygen_overloaded_function(template <...> unsigned int labelVolumeWithBackground)
439 
440 template <class SrcIterator, class SrcAccessor,class SrcShape,
441  class DestIterator, class DestAccessor,
442  class Neighborhood3D,
443  class ValueType>
444 unsigned int labelVolumeWithBackground(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
445  DestIterator d_Iter, DestAccessor da,
446  Neighborhood3D neighborhood3D, ValueType backgroundValue)
447 {
448  return labelVolumeWithBackground(s_Iter, srcShape, sa, d_Iter, da, neighborhood3D, backgroundValue, std::equal_to<typename SrcAccessor::value_type>());
449 }
450 
451 template <class SrcIterator, class SrcAccessor,class SrcShape,
452  class DestIterator, class DestAccessor,
453  class Neighborhood3D,
454  class ValueType>
455 unsigned int labelVolumeWithBackground(triple<SrcIterator, SrcShape, SrcAccessor> src,
456  pair<DestIterator, DestAccessor> dest,
457  Neighborhood3D neighborhood3D, ValueType backgroundValue)
458 {
459  return labelVolumeWithBackground(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, backgroundValue, std::equal_to<typename SrcAccessor::value_type>());
460 }
461 
462 template <class SrcIterator, class SrcAccessor,class SrcShape,
463  class DestIterator, class DestAccessor,
464  class Neighborhood3D,
465  class ValueType, class EqualityFunctor>
466 unsigned int labelVolumeWithBackground(triple<SrcIterator, SrcShape, SrcAccessor> src,
467  pair<DestIterator, DestAccessor> dest,
468  Neighborhood3D neighborhood3D, ValueType backgroundValue, EqualityFunctor equal)
469 {
470  return labelVolumeWithBackground(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, backgroundValue, equal);
471 }
472 
473 template <class SrcIterator, class SrcAccessor,class SrcShape,
474  class DestIterator, class DestAccessor,
475  class Neighborhood3D,
476  class ValueType, class EqualityFunctor>
477 unsigned int labelVolumeWithBackground(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
478  DestIterator d_Iter, DestAccessor da,
479  Neighborhood3D,
480  ValueType backgroundValue, EqualityFunctor equal)
481 {
482  typedef typename DestAccessor::value_type LabelType;
483 
484  //basically needed for iteration and border-checks
485  int w = srcShape[0], h = srcShape[1], d = srcShape[2];
486  int x,y,z;
487 
488  // temporary image to store region labels
489  detail::UnionFindArray<LabelType> label;
490 
491  //Declare traversers for all three dims at target
492  SrcIterator zs = s_Iter;
493  DestIterator zd = d_Iter;
494 
495  // initialize the neighborhood traversers
496  NeighborOffsetCirculator<Neighborhood3D> nce(Neighborhood3D::CausalLast);
497  ++nce;
498  // pass 1: scan image from upper left front to lower right back
499  // to find connected components
500 
501  // Each component will be represented by a tree of pixels. Each
502  // pixel contains the scan order address of its parent in the
503  // tree. In order for pass 2 to work correctly, the parent must
504  // always have a smaller scan order address than the child.
505  // Therefore, we can merge trees only at their roots, because the
506  // root of the combined tree must have the smallest scan order
507  // address among all the tree's pixels/ nodes. The root of each
508  // tree is distinguished by pointing to itself (it contains its
509  // own scan order address). This condition is enforced whenever a
510  // new region is found or two regions are merged
511  for(z = 0; z != d; ++z, ++zs.dim2(), ++zd.dim2())
512  {
513  SrcIterator ys(zs);
514  DestIterator yd(zd);
515 
516  for(y = 0; y != h; ++y, ++ys.dim1(), ++yd.dim1())
517  {
518  SrcIterator xs(ys);
519  DestIterator xd(yd);
520 
521  for(x = 0; x != w; ++x, ++xs.dim0(), ++xd.dim0())
522  {
523  if(equal(sa(xs), backgroundValue))
524  {
525  da.set(label[0], xd);
526  continue;
527  }
528 
529  LabelType currentLabel = label.nextFreeLabel();
530 
531  //queck whether there is a special border treatment to be used or not
532  AtVolumeBorder atBorder = isAtVolumeBorderCausal(x,y,z,w,h,d);
533 
534  //We are not at the border!
535  if(atBorder == NotAtBorder)
536  {
537  NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::CausalFirst);
538 
539  do
540  {
541  // if colors are equal
542  if(equal(sa(xs), sa(xs, *nc)))
543  {
544  currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
545  }
546  ++nc;
547  }
548  while(nc!=nce);
549  }
550  else //we are at a border - handle this!!
551  {
552  NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::nearBorderDirectionsCausal(atBorder,0));
553  int j=0;
554  while(nc.direction() != Neighborhood3D::Error)
555  {
556  // colors equal???
557  if(equal(sa(xs), sa(xs, *nc)))
558  {
559  currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
560  }
561  nc.turnTo(Neighborhood3D::nearBorderDirectionsCausal(atBorder,++j));
562  }
563  }
564  da.set(label.finalizeLabel(currentLabel), xd);
565  }
566  }
567  }
568 
569  LabelType count = label.makeContiguous();
570 
571  // pass 2: assign one label to each region (tree)
572  // so that labels form a consecutive sequence 1, 2, ...
573  zd = d_Iter;
574  for(z=0; z != d; ++z, ++zd.dim2())
575  {
576  DestIterator yd(zd);
577 
578  for(y=0; y != h; ++y, ++yd.dim1())
579  {
580  DestIterator xd(yd);
581 
582  for(x = 0; x != w; ++x, ++xd.dim0())
583  {
584  da.set(label[da(xd)], xd);
585  }
586  }
587  }
588  return count;
589 }
590 
591 //@}
592 
593 } //end of namespace vigra
594 
595 #endif //VIGRA_LABELVOLUME_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.7.1 (Thu Jun 14 2012)