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

labelvolume.hxx VIGRA

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 criterion 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  Connected components are defined as regions with uniform voxel
61  values. Thus, <TT>T1</TT> either must be equality comparable,
62  or an EqualityFunctor must be provided explicitly that realizes
63  the desired equivalence predicate. The destination's value type
64  <tt>T2</tt> should be large enough to hold the labels
65  without overflow. Region numbers will be a consecutive sequence
66  starting with one and ending with the region number returned by
67  the function (inclusive).
68 
69  Return: the number of regions found (= largest region label)
70 
71  See \ref labelMultiArray() for a dimension-independent implementation of
72  connected components labelling.
73 
74  <b> Declarations:</b>
75 
76  pass 3D array views:
77  \code
78  namespace vigra {
79  template <class T1, class S1,
80  class T2, class S2,
81  class Neighborhood3D,
82  class EqualityFunctor = std::equal_to<T1> >
83  unsigned int
84  labelVolume(MultiArrayView<3, T1, S1> const & source,
85  MultiArrayView<3, T2, S2> dest,
86  Neighborhood3D neighborhood3D,
87  EqualityFunctor equal = EqualityFunctor());
88 
89  }
90  \endcode
91 
92  \deprecatedAPI{labelVolume}
93  pass \ref MultiIteratorPage "MultiIterators" and \ref DataAccessors :
94  \code
95  namespace vigra {
96 
97  template <class SrcIterator, class SrcAccessor,class SrcShape,
98  class DestIterator, class DestAccessor,
99  class Neighborhood3D>
100  unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
101  DestIterator d_Iter, DestAccessor da,
102  Neighborhood3D neighborhood3D);
103 
104  template <class SrcIterator, class SrcAccessor,class SrcShape,
105  class DestIterator, class DestAccessor,
106  class Neighborhood3D, class EqualityFunctor>
107  unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
108  DestIterator d_Iter, DestAccessor da,
109  Neighborhood3D neighborhood3D, EqualityFunctor equal);
110 
111  }
112  \endcode
113  use argument objects in conjunction with \ref ArgumentObjectFactories :
114  \code
115  namespace vigra {
116 
117  template <class SrcIterator, class SrcAccessor,class SrcShape,
118  class DestIterator, class DestAccessor,
119  class Neighborhood3D>
120  unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
121  pair<DestIterator, DestAccessor> dest,
122  Neighborhood3D neighborhood3D);
123 
124  template <class SrcIterator, class SrcAccessor,class SrcShape,
125  class DestIterator, class DestAccessor,
126  class Neighborhood3D, class EqualityFunctor>
127  unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
128  pair<DestIterator, DestAccessor> dest,
129  Neighborhood3D neighborhood3D, EqualityFunctor equal);
130 
131  }
132  \endcode
133  use with 3D-Six-Neighborhood:
134  \code
135  namespace vigra {
136 
137  template <class SrcIterator, class SrcAccessor,class SrcShape,
138  class DestIterator, class DestAccessor>
139  unsigned int labelVolumeSix(triple<SrcIterator, SrcShape, SrcAccessor> src,
140  pair<DestIterator, DestAccessor> dest);
141 
142  }
143  \endcode
144  \deprecatedEnd
145 
146  <b> Usage:</b>
147 
148  <b>\#include</b> <vigra/labelvolume.hxx><br>
149  Namespace: vigra
150 
151  \code
152  typedef MultiArray<3,int> IntVolume;
153  IntVolume src(Shape3(w,h,d));
154  IntVolume dest(Shape3(w,h,d));
155 
156  // find 6-connected regions
157  int max_region_label = labelVolumeSix(src, dest);
158 
159  // find 26-connected regions
160  int max_region_label = labelVolume(src, dest, NeighborCode3DTwentySix());
161  \endcode
162 
163  \deprecatedUsage{labelVolume}
164  \code
165  typedef vigra::MultiArray<3,int> IntVolume;
166  IntVolume src(IntVolume::difference_type(w,h,d));
167  IntVolume dest(IntVolume::difference_type(w,h,d));
168 
169  // find 6-connected regions
170  int max_region_label = vigra::labelVolumeSix(srcMultiArrayRange(src), destMultiArray(dest));
171 
172  // find 26-connected regions
173  int max_region_label = vigra::labelVolume(srcMultiArrayRange(src), destMultiArray(dest), NeighborCode3DTwentySix());
174  \endcode
175  <b> Required Interface:</b>
176  \code
177  SrcIterator src_begin;
178  SrcShape shape;
179  DestIterator dest_begin;
180 
181  SrcAccessor src_accessor;
182  DestAccessor dest_accessor;
183 
184  SrcAccessor::value_type u = src_accessor(src_begin);
185 
186  u == u // first form
187 
188  EqualityFunctor equal; // second form
189  equal(u, u) // second form
190 
191  int i;
192  dest_accessor.set(i, dest_begin);
193  \endcode
194  \deprecatedEnd
195 */
196 doxygen_overloaded_function(template <...> unsigned int labelVolume)
197 
198 
199 template <class SrcIterator, class SrcAccessor,class SrcShape,
200  class DestIterator, class DestAccessor,
201  class Neighborhood3D, class EqualityFunctor>
202 unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
203  DestIterator d_Iter, DestAccessor da,
204  Neighborhood3D, EqualityFunctor equal)
205 {
206  typedef typename DestAccessor::value_type LabelType;
207 
208  //basically needed for iteration and border-checks
209  int w = srcShape[0], h = srcShape[1], d = srcShape[2];
210  int x,y,z;
211 
212  // temporary image to store region labels
213  detail::UnionFindArray<LabelType> label;
214 
215  //Declare traversers for all three dims at target
216  SrcIterator zs = s_Iter;
217  DestIterator zd = d_Iter;
218 
219  // initialize the neighborhood traversers
220  NeighborOffsetCirculator<Neighborhood3D> nce(Neighborhood3D::CausalLast);
221  ++nce;
222  // pass 1: scan image from upper left front to lower right back
223  // to find connected components
224 
225  // Each component will be represented by a tree of pixels. Each
226  // pixel contains the scan order address of its parent in the
227  // tree. In order for pass 2 to work correctly, the parent must
228  // always have a smaller scan order address than the child.
229  // Therefore, we can merge trees only at their roots, because the
230  // root of the combined tree must have the smallest scan order
231  // address among all the tree's pixels/ nodes. The root of each
232  // tree is distinguished by pointing to itself (it contains its
233  // own scan order address). This condition is enforced whenever a
234  // new region is found or two regions are merged
235  for(z = 0; z != d; ++z, ++zs.dim2(), ++zd.dim2())
236  {
237  SrcIterator ys(zs);
238  DestIterator yd(zd);
239 
240  for(y = 0; y != h; ++y, ++ys.dim1(), ++yd.dim1())
241  {
242  SrcIterator xs(ys);
243  DestIterator xd(yd);
244 
245  for(x = 0; x != w; ++x, ++xs.dim0(), ++xd.dim0())
246  {
247  LabelType currentLabel = label.nextFreeLabel();
248 
249  //check whether there is a special border treatment to be used or not
250  AtVolumeBorder atBorder = isAtVolumeBorderCausal(x,y,z,w,h,d);
251 
252  //We are not at the border!
253  if(atBorder == NotAtBorder)
254  {
255  NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::CausalFirst);
256 
257  do
258  {
259  // if colors are equal
260  if(equal(sa(xs), sa(xs, *nc)))
261  {
262  currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
263  }
264  ++nc;
265  }
266  while(nc!=nce);
267  }
268  else //we are at a border - handle this!!
269  {
270  NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::nearBorderDirectionsCausal(atBorder,0));
271  int j=0;
272  while(nc.direction() != Neighborhood3D::Error)
273  {
274 
275  SrcShape s(x,y,z), sn = s + *nc;
276 
277  if (sn[0]<0 || sn[0]>=w || sn[1]<0 || sn[1]>=h || sn[2]<0 || sn[2]>=d)
278  {
279  std::cerr << "coordinate error at " << s << ", offset " << *nc << ", index " << (nc).direction() << " at border " <<
280  atBorder << std::endl;
281 
282  }
283 
284  // colors equal???
285  if(equal(sa(xs), sa(xs, *nc)))
286  {
287  currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
288  }
289  nc.turnTo(Neighborhood3D::nearBorderDirectionsCausal(atBorder,++j));
290  }
291  }
292  da.set(label.finalizeLabel(currentLabel), xd);
293  }
294  }
295  }
296 
297  LabelType count = label.makeContiguous();
298 
299  // pass 2: assign one label to each region (tree)
300  // so that labels form a consecutive sequence 1, 2, ...
301  zd = d_Iter;
302  for(z=0; z != d; ++z, ++zd.dim2())
303  {
304  DestIterator yd(zd);
305 
306  for(y=0; y != h; ++y, ++yd.dim1())
307  {
308  DestIterator xd(yd);
309 
310  for(x = 0; x != w; ++x, ++xd.dim0())
311  {
312  da.set(label[da(xd)], xd);
313  }
314  }
315  }
316  return count;
317 }
318 
319 template <class SrcIterator, class SrcAccessor,class SrcShape,
320  class DestIterator, class DestAccessor,
321  class Neighborhood3D>
322 unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
323  DestIterator d_Iter, DestAccessor da,
324  Neighborhood3D neighborhood3D)
325 {
326  return labelVolume(s_Iter, srcShape, sa, d_Iter, da, neighborhood3D, std::equal_to<typename SrcAccessor::value_type>());
327 }
328 
329 template <class SrcIterator, class SrcShape, class SrcAccessor,
330  class DestIterator, class DestAccessor,
331  class Neighborhood3D>
332 unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
333  pair<DestIterator, DestAccessor> dest,
334  Neighborhood3D neighborhood3D)
335 {
336  return labelVolume(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, std::equal_to<typename SrcAccessor::value_type>());
337 }
338 
339 template <class SrcIterator, class SrcShape, class SrcAccessor,
340  class DestIterator, class DestAccessor,
341  class Neighborhood3D, class EqualityFunctor>
342 unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
343  pair<DestIterator, DestAccessor> dest,
344  Neighborhood3D neighborhood3D, EqualityFunctor equal)
345 {
346  return labelVolume(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, equal);
347 }
348 
349 template <class T1, class S1,
350  class T2, class S2,
351  class Neighborhood3D, class EqualityFunctor>
352 inline unsigned int
353 labelVolume(MultiArrayView<3, T1, S1> const & source,
354  MultiArrayView<3, T2, S2> dest,
355  Neighborhood3D neighborhood3D,
356  EqualityFunctor equal)
357 {
358  vigra_precondition(source.shape() == dest.shape(),
359  "labelVolume(): shape mismatch between input and output.");
360  return labelVolume(srcMultiArrayRange(source), destMultiArray(dest), neighborhood3D, equal);
361 }
362 
363 template <class T1, class S1,
364  class T2, class S2,
365  class Neighborhood3D>
366 inline unsigned int
367 labelVolume(MultiArrayView<3, T1, S1> const & source,
368  MultiArrayView<3, T2, S2> dest,
369  Neighborhood3D neighborhood3D)
370 {
371  vigra_precondition(source.shape() == dest.shape(),
372  "labelVolume(): shape mismatch between input and output.");
373  return labelVolume(srcMultiArrayRange(source), destMultiArray(dest), neighborhood3D, std::equal_to<T1>());
374 }
375 
376 /********************************************************/
377 /* */
378 /* labelVolumeSix */
379 /* */
380 /********************************************************/
381 
382 /** \brief Find the connected components of a segmented volume
383  using the 6-neighborhood.
384 
385  See \ref labelVolume() for detailed documentation.
386 
387 */
388 template <class SrcIterator, class SrcAccessor,class SrcShape,
389  class DestIterator, class DestAccessor>
390 unsigned int labelVolumeSix(triple<SrcIterator, SrcShape, SrcAccessor> src,
391  pair<DestIterator, DestAccessor> dest)
392 {
393  return labelVolume(src.first, src.second, src.third, dest.first, dest.second, NeighborCode3DSix(), std::equal_to<typename SrcAccessor::value_type>());
394 }
395 
396 template <class T1, class S1,
397  class T2, class S2>
398 unsigned int labelVolumeSix(MultiArrayView<3, T1, S1> const & source,
399  MultiArrayView<3, T2, S2> dest)
400 {
401  return labelVolume(srcMultiArrayRange(source), destMultiArray(dest),
402  NeighborCode3DSix(), std::equal_to<T1>());
403 }
404 
405 /********************************************************/
406 /* */
407 /* labelVolumeWithBackground */
408 /* */
409 /********************************************************/
410 
411 /** \brief Find the connected components of a segmented volume,
412  excluding the background from labeling.
413 
414  This function works like \ref labelVolume(), but considers all background voxels
415  (i.e. voxels having the given '<TT>background_value</TT>') as a single region that
416  is ignored when determining connected components and remains untouched in the
417  destination array. Usually, you will zero-initialize the output array, so that
418  the background gets label 0 (remember that actual region labels start at one).
419 
420  Return: the number of regions found (= largest region label)
421 
422  See \ref labelMultiArrayWithBackground() for a dimension-independent implementation
423  if this algorithm.
424 
425  <b> Declarations:</b>
426 
427  pass 3D array views:
428  \code
429  namespace vigra {
430  template <class T1, class S1,
431  class T2, class S2,
432  class Neighborhood3D,
433  class ValueType,
434  class EqualityFunctor = std::equalt_to<T1> >
435  unsigned int
436  labelVolumeWithBackground(MultiArrayView<3, T1, S1> const & source,
437  MultiArrayView<3, T2, S2> dest,
438  Neighborhood3D neighborhood3D,
439  ValueType backgroundValue,
440  EqualityFunctor equal = EqualityFunctor());
441  }
442  \endcode
443 
444  \deprecatedAPI{labelVolumeWithBackground}
445  pass \ref MultiIteratorPage "MultiIterators" and \ref DataAccessors :
446  \code
447  namespace vigra {
448 
449  template <class SrcIterator, class SrcAccessor,class SrcShape,
450  class DestIterator, class DestAccessor,
451  class Neighborhood3D, class ValueType>
452  unsigned int labelVolumeWithBackground( SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
453  DestIterator d_Iter, DestAccessor da,
454  Neighborhood3D neighborhood3D, ValueType background_value);
455 
456  template <class SrcIterator, class SrcAccessor,class SrcShape,
457  class DestIterator, class DestAccessor,
458  class Neighborhood3D, class ValueType, class EqualityFunctor>
459  unsigned int labelVolumeWithBackground( SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
460  DestIterator d_Iter, DestAccessor da,
461  Neighborhood3D neighborhood3D, ValueType background_value,
462  EqualityFunctor equal);
463 
464  }
465  \endcode
466  use argument objects in conjunction with \ref ArgumentObjectFactories :
467  \code
468  namespace vigra {
469 
470  template <class SrcIterator, class SrcAccessor,class SrcShape,
471  class DestIterator, class DestAccessor,
472  class Neighborhood3D, class ValueType>
473  unsigned int labelVolumeWithBackground( triple<SrcIterator, SrcShape, SrcAccessor> src,
474  pair<DestIterator, DestAccessor> dest,
475  Neighborhood3D neighborhood3D, ValueType background_value);
476 
477  template <class SrcIterator, class SrcAccessor,class SrcShape,
478  class DestIterator, class DestAccessor,
479  class Neighborhood3D, class ValueType, class EqualityFunctor>
480  unsigned int labelVolumeWithBackground( triple<SrcIterator, SrcShape, SrcAccessor> src,
481  pair<DestIterator, DestAccessor> dest,
482  Neighborhood3D neighborhood3D, ValueType background_value,
483  EqualityFunctor equal);
484 
485  }
486  \endcode
487  \deprecatedEnd
488 
489  <b> Usage:</b>
490 
491  <b>\#include</b> <vigra/labelvolume.hxx><br>
492  Namespace: vigra
493 
494  \code
495  typedef vigra::MultiArray<3,int> IntVolume;
496 
497  IntVolume src(Shape3(w,h,d));
498  IntVolume dest(Shape3(w,h,d));
499 
500  // find 6-connected regions
501  int max_region_label = labelVolumeWithBackground(src, dest, NeighborCode3DSix(), 0);
502  \endcode
503 
504  \deprecatedUsage{labelVolumeWithBackground}
505  \code
506  typedef vigra::MultiArray<3,int> IntVolume;
507  IntVolume src(IntVolume::difference_type(w,h,d));
508  IntVolume dest(IntVolume::difference_type(w,h,d));
509 
510  // find 6-connected regions
511  int max_region_label = vigra::labelVolumeWithBackground(
512  srcMultiArrayRange(src), destMultiArray(dest), NeighborCode3DSix(), 0);
513  \endcode
514  <b> Required Interface:</b>
515  \code
516  SrcIterator src_begin;
517  SrcShape shape;
518  DestIterator dest_begin;
519 
520  SrcAccessor src_accessor;
521  DestAccessor dest_accessor;
522 
523  SrcAccessor::value_type u = src_accessor(src_begin);
524 
525  u == u // first form
526 
527  EqualityFunctor equal; // second form
528  equal(u, u) // second form
529 
530  int i;
531  dest_accessor.set(i, dest_begin);
532  \endcode
533  \deprecatedEnd
534 */
535 doxygen_overloaded_function(template <...> unsigned int labelVolumeWithBackground)
536 
537 template <class SrcIterator, class SrcAccessor,class SrcShape,
538  class DestIterator, class DestAccessor,
539  class Neighborhood3D,
540  class ValueType, class EqualityFunctor>
541 unsigned int labelVolumeWithBackground(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
542  DestIterator d_Iter, DestAccessor da,
543  Neighborhood3D,
544  ValueType backgroundValue, EqualityFunctor equal)
545 {
546  typedef typename DestAccessor::value_type LabelType;
547 
548  //basically needed for iteration and border-checks
549  int w = srcShape[0], h = srcShape[1], d = srcShape[2];
550  int x,y,z;
551 
552  // temporary image to store region labels
553  detail::UnionFindArray<LabelType> label;
554 
555  //Declare traversers for all three dims at target
556  SrcIterator zs = s_Iter;
557  DestIterator zd = d_Iter;
558 
559  // initialize the neighborhood traversers
560  NeighborOffsetCirculator<Neighborhood3D> nce(Neighborhood3D::CausalLast);
561  ++nce;
562  // pass 1: scan image from upper left front to lower right back
563  // to find connected components
564 
565  // Each component will be represented by a tree of pixels. Each
566  // pixel contains the scan order address of its parent in the
567  // tree. In order for pass 2 to work correctly, the parent must
568  // always have a smaller scan order address than the child.
569  // Therefore, we can merge trees only at their roots, because the
570  // root of the combined tree must have the smallest scan order
571  // address among all the tree's pixels/ nodes. The root of each
572  // tree is distinguished by pointing to itself (it contains its
573  // own scan order address). This condition is enforced whenever a
574  // new region is found or two regions are merged
575  for(z = 0; z != d; ++z, ++zs.dim2(), ++zd.dim2())
576  {
577  SrcIterator ys(zs);
578  DestIterator yd(zd);
579 
580  for(y = 0; y != h; ++y, ++ys.dim1(), ++yd.dim1())
581  {
582  SrcIterator xs(ys);
583  DestIterator xd(yd);
584 
585  for(x = 0; x != w; ++x, ++xs.dim0(), ++xd.dim0())
586  {
587  if(equal(sa(xs), backgroundValue))
588  {
589  da.set(label[0], xd);
590  continue;
591  }
592 
593  LabelType currentLabel = label.nextFreeLabel();
594 
595  //check whether there is a special border treatment to be used or not
596  AtVolumeBorder atBorder = isAtVolumeBorderCausal(x,y,z,w,h,d);
597 
598  //We are not at the border!
599  if(atBorder == NotAtBorder)
600  {
601  NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::CausalFirst);
602 
603  do
604  {
605  // if colors are equal
606  if(equal(sa(xs), sa(xs, *nc)))
607  {
608  currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
609  }
610  ++nc;
611  }
612  while(nc!=nce);
613  }
614  else //we are at a border - handle this!!
615  {
616  NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::nearBorderDirectionsCausal(atBorder,0));
617  int j=0;
618  while(nc.direction() != Neighborhood3D::Error)
619  {
620  SrcShape s(x,y,z), sn = s + *nc;
621 
622  if (sn[0]<0 || sn[0]>=w || sn[1]<0 || sn[1]>=h || sn[2]<0 || sn[2]>=d)
623  {
624  std::cerr << "coordinate error at " << s << ", offset " << *nc << ", index " << (nc).direction() << " at border " <<
625  atBorder << std::endl;
626 
627  }
628  // colors equal???
629  if(equal(sa(xs), sa(xs, *nc)))
630  {
631  currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
632  }
633  nc.turnTo(Neighborhood3D::nearBorderDirectionsCausal(atBorder,++j));
634  }
635  }
636  da.set(label.finalizeLabel(currentLabel), xd);
637  }
638  }
639  }
640 
641  LabelType count = label.makeContiguous();
642 
643  // pass 2: assign one label to each region (tree)
644  // so that labels form a consecutive sequence 1, 2, ...
645  zd = d_Iter;
646  for(z=0; z != d; ++z, ++zd.dim2())
647  {
648  DestIterator yd(zd);
649 
650  for(y=0; y != h; ++y, ++yd.dim1())
651  {
652  DestIterator xd(yd);
653 
654  for(x = 0; x != w; ++x, ++xd.dim0())
655  {
656  da.set(label[da(xd)], xd);
657  }
658  }
659  }
660  return count;
661 }
662 
663 template <class SrcIterator, class SrcAccessor,class SrcShape,
664  class DestIterator, class DestAccessor,
665  class Neighborhood3D,
666  class ValueType>
667 inline unsigned int
668 labelVolumeWithBackground(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
669  DestIterator d_Iter, DestAccessor da,
670  Neighborhood3D neighborhood3D, ValueType backgroundValue)
671 {
672  return labelVolumeWithBackground(s_Iter, srcShape, sa, d_Iter, da, neighborhood3D, backgroundValue, std::equal_to<typename SrcAccessor::value_type>());
673 }
674 
675 template <class SrcIterator, class SrcShape, class SrcAccessor,
676  class DestIterator, class DestAccessor,
677  class Neighborhood3D,
678  class ValueType,
679  class EqualityFunctor>
680 inline unsigned int
681 labelVolumeWithBackground(triple<SrcIterator, SrcShape, SrcAccessor> src,
682  pair<DestIterator, DestAccessor> dest,
683  Neighborhood3D neighborhood3D, ValueType backgroundValue, EqualityFunctor equal)
684 {
685  return labelVolumeWithBackground(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, backgroundValue, equal);
686 }
687 
688 template <class SrcIterator, class SrcShape, class SrcAccessor,
689  class DestIterator, class DestAccessor,
690  class Neighborhood3D,
691  class ValueType>
692 inline unsigned int
693 labelVolumeWithBackground(triple<SrcIterator, SrcShape, SrcAccessor> src,
694  pair<DestIterator, DestAccessor> dest,
695  Neighborhood3D neighborhood3D, ValueType backgroundValue)
696 {
697  return labelVolumeWithBackground(src.first, src.second, src.third, dest.first, dest.second,
698  neighborhood3D, backgroundValue, std::equal_to<typename SrcAccessor::value_type>());
699 }
700 
701 template <class T1, class S1,
702  class T2, class S2,
703  class Neighborhood3D,
704  class ValueType,
705  class EqualityFunctor>
706 inline unsigned int
707 labelVolumeWithBackground(MultiArrayView<3, T1, S1> const & source,
708  MultiArrayView<3, T2, S2> dest,
709  Neighborhood3D neighborhood3D,
710  ValueType backgroundValue,
711  EqualityFunctor equal)
712 {
713  vigra_precondition(source.shape() == dest.shape(),
714  "labelVolumeWithBackground(): shape mismatch between input and output.");
715  return labelVolumeWithBackground(srcMultiArrayRange(source), destMultiArray(dest),
716  neighborhood3D, backgroundValue, equal);
717 }
718 
719 template <class T1, class S1,
720  class T2, class S2,
721  class Neighborhood3D,
722  class ValueType>
723 inline unsigned int
724 labelVolumeWithBackground(MultiArrayView<3, T1, S1> const & source,
725  MultiArrayView<3, T2, S2> dest,
726  Neighborhood3D neighborhood3D,
727  ValueType backgroundValue)
728 {
729  vigra_precondition(source.shape() == dest.shape(),
730  "labelVolumeWithBackground(): shape mismatch between input and output.");
731  return labelVolumeWithBackground(srcMultiArrayRange(source), destMultiArray(dest),
732  neighborhood3D, backgroundValue,
733  std::equal_to<T1>());
734 }
735 
736 //@}
737 
738 } //end of namespace vigra
739 
740 #endif //VIGRA_LABELVOLUME_HXX
vigra::GridGraph< N, DirectedTag >::vertex_descriptor source(typename vigra::GridGraph< N, DirectedTag >::edge_descriptor const &e, vigra::GridGraph< N, DirectedTag > const &g)
Get a vertex descriptor for the start vertex of edge e in graph g (API: boost).
Definition: multi_gridgraph.hxx:2786
unsigned int labelVolume(...)
Find the connected components of a segmented volume.
AtImageBorder AtVolumeBorder
Encode whether a voxel is near the volume border.
Definition: voxelneighborhood.hxx:72
AtVolumeBorder isAtVolumeBorderCausal(int x, int y, int z, int width, int height, int)
Find out whether a voxel is at a scan-order relevant volume border. This function checks if x == 0 or...
Definition: voxelneighborhood.hxx:112
unsigned int labelVolumeSix(triple< SrcIterator, SrcShape, SrcAccessor > src, pair< DestIterator, DestAccessor > dest)
Find the connected components of a segmented volume using the 6-neighborhood.
Definition: labelvolume.hxx:390
Definition: accessor.hxx:43
unsigned int labelVolumeWithBackground(...)
Find the connected components of a segmented volume, excluding the background from labeling...
Neighborhood3DSix::NeighborCode3D NeighborCode3DSix
Definition: voxelneighborhood.hxx:490
Encapsulation of direction management of neighbors for a 3D 6-neighborhood.
Definition: voxelneighborhood.hxx:163
 
Definition: pixelneighborhood.hxx:70

© 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