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"
46 namespace labeling_equality{
60 struct SizeToType<sizeof(Yes)>
62 typedef VigraTrueType type;
65 struct SizeToType<sizeof(No)>
67 typedef VigraFalseType type;
70 template <
class Equal>
71 class 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;
83 template <
class Equal,
class Data,
class Shape>
84 bool callEqualImpl(Equal& equal,
const Data& u_data,
const Data& v_data,
const Shape& diff, VigraTrueType)
86 return equal(u_data, v_data, diff);
88 template <
class Equal,
class Data,
class Shape>
89 bool callEqualImpl(Equal& equal,
const Data& u_data,
const Data& v_data,
const Shape&, VigraFalseType)
91 return equal(u_data, v_data);
94 template<
class Equal,
class Data,
class Shape>
95 bool 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());
107 namespace lemon_graph {
109 template <
class Graph,
class T1Map,
class T2Map,
class Equal>
110 typename T2Map::value_type
111 labelGraph(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]);
152 template <
unsigned int N,
class DirectedTag,
class T1Map,
class T2Map,
class Equal>
153 typename T2Map::value_type
154 labelGraph(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]);
199 template <
class Graph,
class T1Map,
class T2Map,
class Equal>
200 typename T2Map::value_type
201 labelGraphWithBackground(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]);
250 template <
unsigned int N,
class DirectedTag,
class T1Map,
class T2Map,
class Equal>
251 typename T2Map::value_type
252 labelGraphWithBackground(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>();
472 template <
unsigned int N,
class T,
class S1,
473 class Label,
class S2,
477 MultiArrayView<N, Label, S2> labels,
481 vigra_precondition(data.shape() == labels.shape(),
482 "labelMultiArray(): shape mismatch between input and output.");
484 GridGraph<N, undirected_tag> graph(data.shape(), neighborhood);
485 return lemon_graph::labelGraph(graph, data, labels, equal);
488 template <
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>());
498 template <
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>());
512 template <
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);
601 template <
unsigned int N,
class T,
class S1,
602 class Label,
class S2,
606 MultiArrayView<N, Label, S2> labels,
611 vigra_precondition(data.shape() == labels.shape(),
612 "labelMultiArrayWithBackground(): shape mismatch between input and output.");
614 GridGraph<N, undirected_tag> graph(data.shape(), neighborhood);
615 return lemon_graph::labelGraphWithBackground(graph, data, labels, backgroundValue, equal);
618 template <
unsigned int N,
class T,
class S1,
619 class Label,
class S2>
622 MultiArrayView<N, Label, S2> labels,
624 T backgroundValue = T())
633 #endif //VIGRA_MULTI_LABELING_HXX
Option object for labelMultiArray().
Definition: multi_labeling.hxx:309
bool hasBackgroundValue() const
Check if some background value is to be ignored.
Definition: multi_labeling.hxx:359
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.
Typesafe storage of arbitrary values.
Definition: any.hxx:230
LabelOptions & neighborhood(NeighborhoodType n)
Choose direct or indirect neighborhood.
Definition: multi_labeling.hxx:326
T getBackgroundValue() const
Get the background value to be ignored.
Definition: multi_labeling.hxx:370
NeighborhoodType getNeighborhood() const
Query the neighborhood type (direct or indirect).
Definition: multi_labeling.hxx:334
LabelOptions & ignoreBackgroundValue(T const &t)
Set background value.
Definition: multi_labeling.hxx:351
bool empty() const
Definition: any.hxx:339
use only direct neighbors
Definition: multi_fwd.hxx:187
LabelOptions()
Set default options.
Definition: multi_labeling.hxx:318
unsigned int labelMultiArray(...)
Find the connected components of a MultiArray with arbitrary many dimensions.
NeighborhoodType
Choose the neighborhood system in a dimension-independent way.
Definition: multi_fwd.hxx:186