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