36#ifndef VIGRA_MULTI_LABELING_HXX
37#define VIGRA_MULTI_LABELING_HXX
39#include "multi_array.hxx"
40#include "multi_gridgraph.hxx"
41#include "union_find.hxx"
46namespace labeling_equality{
60struct SizeToType<sizeof(Yes)>
62 typedef VigraTrueType type;
65struct SizeToType<sizeof(No)>
67 typedef VigraFalseType type;
71class TakesThreeArguments
75 static Yes check(
typename T::WithDiffTag*);
79 typedef typename SizeToType<sizeof(check<Equal>(0))>::type type;
80 static const unsigned int value = type::asBool;
83template <
class Equal,
class Data,
class Shape>
84bool callEqualImpl(Equal& equal,
const Data& u_data,
const Data& v_data,
const Shape& diff, VigraTrueType)
86 return equal(u_data, v_data, diff);
88template <
class Equal,
class Data,
class Shape>
89bool callEqualImpl(Equal& equal,
const Data& u_data,
const Data& v_data,
const Shape&, VigraFalseType)
91 return equal(u_data, v_data);
94template<
class Equal,
class Data,
class Shape>
95bool callEqual(Equal& equal,
const Data& u_data,
const Data& v_data,
const Shape& diff)
97 return callEqualImpl(equal, u_data, v_data, diff,
typename TakesThreeArguments<Equal>::type());
107namespace lemon_graph {
109template <
class Graph,
class T1Map,
class T2Map,
class Equal>
110typename T2Map::value_type
111labelGraph(Graph
const & g,
116 typedef typename Graph::NodeIt graph_scanner;
117 typedef typename Graph::OutBackArcIt neighbor_iterator;
118 typedef typename T2Map::value_type LabelType;
120 vigra::UnionFindArray<LabelType> regions;
123 for (graph_scanner node(g); node != INVALID; ++node)
125 typename T1Map::value_type center = data[*node];
128 LabelType currentIndex = regions.nextFreeIndex();
130 for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
133 if(equal(center, data[g.target(*arc)]))
135 currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
139 labels[*node] = regions.finalizeIndex(currentIndex);
142 LabelType count = regions.makeContiguous();
145 for (graph_scanner node(g); node != INVALID; ++node)
147 labels[*node] = regions.findLabel(labels[*node]);
152template <
unsigned int N,
class DirectedTag,
class T1Map,
class T2Map,
class Equal>
153typename T2Map::value_type
154labelGraph(GridGraph<N, DirectedTag>
const & g,
159 typedef GridGraph<N, DirectedTag> Graph;
160 typedef typename Graph::NodeIt graph_scanner;
161 typedef typename Graph::OutBackArcIt neighbor_iterator;
162 typedef typename T2Map::value_type LabelType;
163 typedef typename Graph::shape_type Shape;
165 vigra::UnionFindArray<LabelType> regions;
168 for (graph_scanner node(g); node != INVALID; ++node)
170 typename T1Map::value_type center = data[*node];
173 LabelType currentIndex = regions.nextFreeIndex();
175 for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
177 Shape diff = g.neighborOffset(arc.neighborIndex());
179 if(labeling_equality::callEqual(equal, center, data[g.target(*arc)], diff))
181 currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
185 labels[*node] = regions.finalizeIndex(currentIndex);
188 LabelType count = regions.makeContiguous();
191 for (graph_scanner node(g); node != INVALID; ++node)
193 labels[*node] = regions.findLabel(labels[*node]);
199template <
class Graph,
class T1Map,
class T2Map,
class Equal>
200typename T2Map::value_type
201labelGraphWithBackground(Graph
const & g,
204 typename T1Map::value_type backgroundValue,
207 typedef typename Graph::NodeIt graph_scanner;
208 typedef typename Graph::OutBackArcIt neighbor_iterator;
209 typedef typename T2Map::value_type LabelType;
211 vigra::UnionFindArray<LabelType> regions;
214 for (graph_scanner node(g); node != INVALID; ++node)
216 typename T1Map::value_type center = data[*node];
219 if(equal(center, backgroundValue))
226 LabelType currentIndex = regions.nextFreeIndex();
228 for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
231 if(equal(center, data[g.target(*arc)]))
233 currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
237 labels[*node] = regions.finalizeIndex(currentIndex);
240 LabelType count = regions.makeContiguous();
243 for (graph_scanner node(g); node != INVALID; ++node)
245 labels[*node] = regions.findLabel(labels[*node]);
250template <
unsigned int N,
class DirectedTag,
class T1Map,
class T2Map,
class Equal>
251typename T2Map::value_type
252labelGraphWithBackground(GridGraph<N, DirectedTag>
const & g,
255 typename T1Map::value_type backgroundValue,
258 typedef GridGraph<N, DirectedTag> Graph;
259 typedef typename Graph::NodeIt graph_scanner;
260 typedef typename Graph::OutBackArcIt neighbor_iterator;
261 typedef typename T2Map::value_type LabelType;
262 typedef typename Graph::shape_type Shape;
264 vigra::UnionFindArray<LabelType> regions;
267 for (graph_scanner node(g); node != INVALID; ++node)
269 typename T1Map::value_type center = data[*node];
272 if(labeling_equality::callEqual(equal, center, backgroundValue, Shape()))
279 LabelType currentIndex = regions.nextFreeIndex();
281 for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
284 Shape diff = g.neighborOffset(arc.neighborIndex());
285 if(labeling_equality::callEqual(equal, center, data[g.target(*arc)], diff))
287 currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
291 labels[*node] = regions.finalizeIndex(currentIndex);
294 LabelType count = regions.makeContiguous();
297 for (graph_scanner node(g); node != INVALID; ++node)
299 labels[*node] = regions.findLabel(labels[*node]);
311 Any background_value_;
336 return neighborhood_;
353 background_value_ = t;
361 return bool(background_value_);
372 if(background_value_.
empty())
374 vigra_precondition(background_value_.template is_readable<T>(),
375 "LabelOptions::getBackgroundValue<T>(): stored background value is not convertible to T.");
376 return background_value_.template read<T>();
472template <
unsigned int N,
class T,
class S1,
473 class Label,
class S2,
481 vigra_precondition(data.
shape() == labels.
shape(),
482 "labelMultiArray(): shape mismatch between input and output.");
485 return lemon_graph::labelGraph(graph, data, labels, equal);
488template <
unsigned int N,
class T,
class S1,
489 class Label,
class S2>
492 MultiArrayView<N, Label, S2> labels,
495 return labelMultiArray(data, labels, neighborhood, std::equal_to<T>());
498template <
unsigned int N,
class T,
class S1,
499 class Label,
class S2>
502 MultiArrayView<N, Label, S2> labels,
503 LabelOptions
const & options)
505 if(options.hasBackgroundValue())
507 options.template getBackgroundValue<T>());
512template <
unsigned int N,
class T,
class S1,
513 class Label,
class S2,
517 MultiArrayView<N, Label, S2> labels,
518 LabelOptions
const & options,
521 if(options.hasBackgroundValue())
523 options.template getBackgroundValue<T>(),
526 return labelMultiArray(data, labels, options.getNeighborhood(), equal);
601template <
unsigned int N,
class T,
class S1,
602 class Label,
class S2,
611 vigra_precondition(data.
shape() == labels.
shape(),
612 "labelMultiArrayWithBackground(): shape mismatch between input and output.");
615 return lemon_graph::labelGraphWithBackground(graph, data, labels, backgroundValue, equal);
618template <
unsigned int N,
class T,
class S1,
619 class Label,
class S2>
622 MultiArrayView<N, Label, S2> labels,
624 T backgroundValue = T())
Typesafe storage of arbitrary values.
Definition: any.hxx:231
bool empty() const
Definition: any.hxx:339
Option object for labelMultiArray().
Definition: multi_labeling.hxx:310
NeighborhoodType getNeighborhood() const
Query the neighborhood type (direct or indirect).
Definition: multi_labeling.hxx:334
LabelOptions & neighborhood(NeighborhoodType n)
Choose direct or indirect neighborhood.
Definition: multi_labeling.hxx:326
bool hasBackgroundValue() const
Check if some background value is to be ignored.
Definition: multi_labeling.hxx:359
LabelOptions & ignoreBackgroundValue(T const &t)
Set background value.
Definition: multi_labeling.hxx:351
T getBackgroundValue() const
Get the background value to be ignored.
Definition: multi_labeling.hxx:370
LabelOptions()
Set default options.
Definition: multi_labeling.hxx:318
Base class for, and view to, vigra::MultiArray.
Definition: multi_array.hxx:705
const difference_type & shape() const
Definition: multi_array.hxx:1648
unsigned int labelMultiArray(...)
Find the connected components of a MultiArray with arbitrary many dimensions.
unsigned int labelMultiArrayWithBackground(...)
Find the connected components of a MultiArray with arbitrary many dimensions, excluding the backgroun...
doxygen_overloaded_function(template<... > void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
NeighborhoodType
Choose the neighborhood system in a dimension-independent way.
Definition: multi_fwd.hxx:186
@ DirectNeighborhood
use only direct neighbors
Definition: multi_fwd.hxx:187