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

multi_labeling.hxx VIGRA

1 /************************************************************************/
2 /* */
3 /* Copyright 2012-2013 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 #ifndef VIGRA_MULTI_LABELING_HXX
37 #define VIGRA_MULTI_LABELING_HXX
38 
39 #include "multi_array.hxx"
40 #include "multi_gridgraph.hxx"
41 #include "union_find.hxx"
42 
43 namespace vigra{
44 
45 namespace labeling_equality{
46 
47 struct Yes
48 {
49  char d[100];
50 };
51 struct No
52 {
53  char d[1];
54 };
55 
56 template <size_t>
57 struct SizeToType;
58 template <>
59 struct SizeToType<sizeof(Yes)>
60 {
61  typedef VigraTrueType type;
62 };
63 template <>
64 struct SizeToType<sizeof(No)>
65 {
66  typedef VigraFalseType type;
67 };
68 
69 template <class Equal>
70 class TakesThreeArguments
71 {
72 public:
73  template <class T>
74  static Yes check(typename T::WithDiffTag*);
75  template <class T>
76  static No check(...);
77 
78  typedef typename SizeToType<sizeof(check<Equal>(0))>::type type;
79  static const unsigned int value = type::asBool;
80 };
81 
82 template <class Equal, class Data, class Shape>
83 bool callEqualImpl(Equal& equal, const Data& u_data, const Data& v_data, const Shape& diff, VigraTrueType)
84 {
85  return equal(u_data, v_data, diff);
86 }
87 template <class Equal, class Data, class Shape>
88 bool callEqualImpl(Equal& equal, const Data& u_data, const Data& v_data, const Shape& diff, VigraFalseType)
89 {
90  return equal(u_data, v_data);
91 }
92 
93 template< class Equal, class Data, class Shape>
94 bool callEqual(Equal& equal, const Data& u_data, const Data& v_data, const Shape& diff)
95 {
96  return callEqualImpl(equal, u_data, v_data, diff, typename TakesThreeArguments<Equal>::type());
97 }
98 
99 }
100 
101 
102 /** \addtogroup Labeling
103 */
104 //@{
105 
106 namespace lemon_graph {
107 
108 template <class Graph, class T1Map, class T2Map, class Equal>
109 typename T2Map::value_type
110 labelGraph(Graph const & g,
111  T1Map const & data,
112  T2Map & labels,
113  Equal const & equal)
114 {
115  typedef typename Graph::NodeIt graph_scanner;
116  typedef typename Graph::OutBackArcIt neighbor_iterator;
117  typedef typename T2Map::value_type LabelType;
118 
119  vigra::UnionFindArray<LabelType> regions;
120 
121  // pass 1: find connected components
122  for (graph_scanner node(g); node != INVALID; ++node)
123  {
124  typename T1Map::value_type center = data[*node];
125 
126  // define tentative label for current node
127  LabelType currentIndex = regions.nextFreeIndex();
128 
129  for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
130  {
131  // merge regions if colors are equal
132  if(equal(center, data[g.target(*arc)]))
133  {
134  currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
135  }
136  }
137  // set label of current node
138  labels[*node] = regions.finalizeIndex(currentIndex);
139  }
140 
141  LabelType count = regions.makeContiguous();
142 
143  // pass 2: make component labels contiguous
144  for (graph_scanner node(g); node != INVALID; ++node)
145  {
146  labels[*node] = regions.findLabel(labels[*node]);
147  }
148  return count;
149 }
150 
151 template <unsigned int N, class DirectedTag, class T1Map, class T2Map, class Equal>
152 typename T2Map::value_type
153 labelGraph(GridGraph<N, DirectedTag> const & g,
154  T1Map const & data,
155  T2Map & labels,
156  Equal const & equal)
157 {
158  typedef GridGraph<N, DirectedTag> Graph;
159  typedef typename Graph::NodeIt graph_scanner;
160  typedef typename Graph::OutBackArcIt neighbor_iterator;
161  typedef typename T2Map::value_type LabelType;
162  typedef typename Graph::shape_type Shape;
163 
164  vigra::UnionFindArray<LabelType> regions;
165 
166  // pass 1: find connected components
167  for (graph_scanner node(g); node != INVALID; ++node)
168  {
169  typename T1Map::value_type center = data[*node];
170 
171  // define tentative label for current node
172  LabelType currentIndex = regions.nextFreeIndex();
173 
174  for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
175  {
176  Shape diff = g.neighborOffset(arc.neighborIndex());
177  // merge regions if colors are equal
178  if(labeling_equality::callEqual(equal, center, data[g.target(*arc)], diff))
179  {
180  currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
181  }
182  }
183  // set label of current node
184  labels[*node] = regions.finalizeIndex(currentIndex);
185  }
186 
187  LabelType count = regions.makeContiguous();
188 
189  // pass 2: make component labels contiguous
190  for (graph_scanner node(g); node != INVALID; ++node)
191  {
192  labels[*node] = regions.findLabel(labels[*node]);
193  }
194  return count;
195 }
196 
197 
198 template <class Graph, class T1Map, class T2Map, class Equal>
199 typename T2Map::value_type
200 labelGraphWithBackground(Graph const & g,
201  T1Map const & data,
202  T2Map & labels,
203  typename T1Map::value_type backgroundValue,
204  Equal const & equal)
205 {
206  typedef typename Graph::NodeIt graph_scanner;
207  typedef typename Graph::OutBackArcIt neighbor_iterator;
208  typedef typename T2Map::value_type LabelType;
209 
210  vigra::UnionFindArray<LabelType> regions;
211 
212  // pass 1: find connected components
213  for (graph_scanner node(g); node != INVALID; ++node)
214  {
215  typename T1Map::value_type center = data[*node];
216 
217  // background always gets label zero
218  if(equal(center, backgroundValue))
219  {
220  labels[*node] = 0;
221  continue;
222  }
223 
224  // define tentative label for current node
225  LabelType currentIndex = regions.nextFreeIndex();
226 
227  for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
228  {
229  // merge regions if colors are equal
230  if(equal(center, data[g.target(*arc)]))
231  {
232  currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
233  }
234  }
235  // set label of current node
236  labels[*node] = regions.finalizeIndex(currentIndex);
237  }
238 
239  LabelType count = regions.makeContiguous();
240 
241  // pass 2: make component labels contiguous
242  for (graph_scanner node(g); node != INVALID; ++node)
243  {
244  labels[*node] = regions.findLabel(labels[*node]);
245  }
246  return count;
247 }
248 
249 template <unsigned int N, class DirectedTag, class T1Map, class T2Map, class Equal>
250 typename T2Map::value_type
251 labelGraphWithBackground(GridGraph<N, DirectedTag> const & g,
252  T1Map const & data,
253  T2Map & labels,
254  typename T1Map::value_type backgroundValue,
255  Equal const & equal)
256 {
257  typedef GridGraph<N, DirectedTag> Graph;
258  typedef typename Graph::NodeIt graph_scanner;
259  typedef typename Graph::OutBackArcIt neighbor_iterator;
260  typedef typename T2Map::value_type LabelType;
261  typedef typename Graph::shape_type Shape;
262 
263  vigra::UnionFindArray<LabelType> regions;
264 
265  // pass 1: find connected components
266  for (graph_scanner node(g); node != INVALID; ++node)
267  {
268  typename T1Map::value_type center = data[*node];
269 
270  // background always gets label zero
271  if(labeling_equality::callEqual(equal, center, backgroundValue, Shape()))
272  {
273  labels[*node] = 0;
274  continue;
275  }
276 
277  // define tentative label for current node
278  LabelType currentIndex = regions.nextFreeIndex();
279 
280  for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
281  {
282  // merge regions if colors are equal
283  Shape diff = g.neighborOffset(arc.neighborIndex());
284  if(labeling_equality::callEqual(equal, center, data[g.target(*arc)], diff))
285  {
286  currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
287  }
288  }
289  // set label of current node
290  labels[*node] = regions.finalizeIndex(currentIndex);
291  }
292 
293  LabelType count = regions.makeContiguous();
294 
295  // pass 2: make component labels contiguous
296  for (graph_scanner node(g); node != INVALID; ++node)
297  {
298  labels[*node] = regions.findLabel(labels[*node]);
299  }
300  return count;
301 }
302 
303 
304 } // namespace lemon_graph
305 
306 /********************************************************/
307 /* */
308 /* labelMultiArray */
309 /* */
310 /********************************************************/
311 
312 /** \brief Find the connected components of a MultiArray with arbitrary many dimensions.
313 
314  <b> Declaration:</b>
315 
316  \code
317  namespace vigra {
318 
319  template <unsigned int N, class T, class S1,
320  class Label, class S2,
321  class EqualityFunctor = std::equal_to<T> >
322  Label
323  labelMultiArray(MultiArrayView<N, T, S1> const & data,
324  MultiArrayView<N, Label, S2> labels,
325  NeighborhoodType neighborhood = DirectNeighborhood,
326  EqualityFunctor equal = std::equal_to<T>())
327 
328  }
329  \endcode
330 
331  Connected components are defined as regions with uniform values.
332  Thus, the value type <tt>T</tt> of the input array \a data either
333  must be equality comparable, or an EqualityFunctor must be
334  provided that realizes the desired predicate. The destination
335  array's value type <tt>Label</tt> should be large enough to hold
336  the labels without overflow. Region numbers will form a consecutive
337  sequence starting at <b>one</b> and ending with the region number
338  returned by the function (inclusive).
339 
340  Argument \a neighborhood specifies the type of connectivity used. It can
341  take the values <tt>DirectNeighborhood</tt> (which corresponds to
342  4-neighborhood in 2D and 6-neighborhood in 3D, default) or
343  <tt>IndirectNeighborhood</tt> (which corresponds to
344  8-neighborhood in 2D and 26-neighborhood in 3D).
345 
346  Return: the number of regions found (= highest region label, because labeling starts at 1)
347 
348  <b> Usage:</b>
349 
350  <b>\#include</b> <vigra/multi_labeling.hxx><br>
351  Namespace: vigra
352 
353  \code
354  MultiArray<3,int> src(Shape3(w,h,d));
355  MultiArray<3,int> dest(Shape3(w,h,d));
356 
357  // find 6-connected regions
358  int max_region_label = labelMultiArray(src, dest);
359 
360  // find 26-connected regions
361  max_region_label = labelMultiArray(src, dest, IndirectNeighborhood);
362  \endcode
363 
364  <b> Required Interface:</b>
365 
366  \code
367  T t;
368  t == t // T is equality comparable
369 
370  EqualityFunctor equal; // or a suitable functor is supplied
371  equal(t, t)
372  \endcode
373 */
374 doxygen_overloaded_function(template <...> unsigned int labelMultiArray)
375 
376 template <unsigned int N, class T, class S1,
377  class Label, class S2,
378  class Equal>
379 inline Label
380 labelMultiArray(MultiArrayView<N, T, S1> const & data,
381  MultiArrayView<N, Label, S2> labels,
382  NeighborhoodType neighborhood,
383  Equal equal)
384 {
385  vigra_precondition(data.shape() == labels.shape(),
386  "labelMultiArray(): shape mismatch between input and output.");
387 
388  GridGraph<N, undirected_tag> graph(data.shape(), neighborhood);
389  return lemon_graph::labelGraph(graph, data, labels, equal);
390 }
391 
392 template <unsigned int N, class T, class S1,
393  class Label, class S2>
394 inline Label
395 labelMultiArray(MultiArrayView<N, T, S1> const & data,
396  MultiArrayView<N, Label, S2> labels,
397  NeighborhoodType neighborhood = DirectNeighborhood)
398 {
399  return labelMultiArray(data, labels, neighborhood, std::equal_to<T>());
400 }
401 
402 /********************************************************/
403 /* */
404 /* labelMultiArrayWithBackground */
405 /* */
406 /********************************************************/
407 
408 /** \brief Find the connected components of a MultiArray with arbitrary many dimensions,
409  excluding the background from labeling.
410 
411  <b> Declaration:</b>
412 
413  \code
414  namespace vigra {
415 
416  template <unsigned int N, class T, class S1,
417  class Label, class S2
418  class Equal = std::equal<T> >
419  Label
420  labelMultiArrayWithBackground(MultiArrayView<N, T, S1> const & data,
421  MultiArrayView<N, Label, S2> labels,
422  NeighborhoodType neighborhood = DirectNeighborhood,
423  T backgroundValue = T(),
424  Equal equal = std::equal<T>());
425 
426  }
427  \endcode
428 
429  This function is the same as \ref labelMultiArray(), except for
430  the additional parameter \a backgroundValue. Points in the input
431  array \a data with this value (which default to zero) are ignored
432  during labeling, and their output label is automatically set to
433  zero. Region numbers will be a consecutive sequence starting at
434  zero (when background was present) or at one (when no background
435  was present) and ending with the region number returned by the
436  function (inclusive).
437 
438  Return: the number of non-background regions found (= highest region label,
439  because background has label 0)
440 
441  <b> Usage:</b>
442 
443  <b>\#include</b> <vigra/multi_labeling.hxx><br>
444  Namespace: vigra
445 
446  \code
447  MultiArray<3, int> src(Shape3(w,h,d));
448  MultiArray<3, int> dest(Shape3(w,h,d));
449 
450  // find 6-connected regions, ignoring background value zero (the default)
451  int max_region_label = labelMultiArrayWithBackground(src, dest);
452 
453  // find 26-connected regions, using -1 as the background value
454  max_region_label = labelMultiArrayWithBackground(src, dest, IndirectNeighborhood, -1);
455  \endcode
456 
457  <b> Required Interface:</b>
458 
459  \code
460  T t, backgroundValue;
461  t == backgroundValue // T is equality comparable
462 
463  EqualityFunctor equal; // or a suitable functor is supplied
464  equal(t, backgroundValue)
465  \endcode
466 */
468 
469 template <unsigned int N, class T, class S1,
470  class Label, class S2,
471  class Equal>
472 inline Label
473 labelMultiArrayWithBackground(MultiArrayView<N, T, S1> const & data,
474  MultiArrayView<N, Label, S2> labels,
475  NeighborhoodType neighborhood,
476  T backgroundValue,
477  Equal equal)
478 {
479  vigra_precondition(data.shape() == labels.shape(),
480  "labelMultiArrayWithBackground(): shape mismatch between input and output.");
481 
482  GridGraph<N, undirected_tag> graph(data.shape(), neighborhood);
483  return lemon_graph::labelGraphWithBackground(graph, data, labels, backgroundValue, equal);
484 }
485 
486 template <unsigned int N, class T, class S1,
487  class Label, class S2>
488 inline Label
489 labelMultiArrayWithBackground(MultiArrayView<N, T, S1> const & data,
490  MultiArrayView<N, Label, S2> labels,
491  NeighborhoodType neighborhood = DirectNeighborhood,
492  T backgroundValue = T())
493 {
494  return labelMultiArrayWithBackground(data, labels, neighborhood, backgroundValue, std::equal_to<T>());
495 }
496 
497 //@}
498 
499 } // namespace vigra
500 
501 #endif //VIGRA_MULTI_LABELING_HXX

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.10.0 (Thu Jan 8 2015)