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"
45 namespace labeling_equality{
59 struct SizeToType<sizeof(Yes)>
61 typedef VigraTrueType type;
64 struct SizeToType<sizeof(No)>
66 typedef VigraFalseType type;
69 template <
class Equal>
70 class TakesThreeArguments
74 static Yes check(
typename T::WithDiffTag*);
78 typedef typename SizeToType<sizeof(check<Equal>(0))>::type type;
79 static const unsigned int value = type::asBool;
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)
85 return equal(u_data, v_data, diff);
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)
90 return equal(u_data, v_data);
93 template<
class Equal,
class Data,
class Shape>
94 bool callEqual(Equal& equal,
const Data& u_data,
const Data& v_data,
const Shape& diff)
96 return callEqualImpl(equal, u_data, v_data, diff,
typename TakesThreeArguments<Equal>::type());
106 namespace lemon_graph {
108 template <
class Graph,
class T1Map,
class T2Map,
class Equal>
109 typename T2Map::value_type
110 labelGraph(Graph
const & g,
115 typedef typename Graph::NodeIt graph_scanner;
116 typedef typename Graph::OutBackArcIt neighbor_iterator;
117 typedef typename T2Map::value_type LabelType;
119 vigra::UnionFindArray<LabelType> regions;
122 for (graph_scanner node(g); node != INVALID; ++node)
124 typename T1Map::value_type center = data[*node];
127 LabelType currentIndex = regions.nextFreeIndex();
129 for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
132 if(equal(center, data[g.target(*arc)]))
134 currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
138 labels[*node] = regions.finalizeIndex(currentIndex);
141 LabelType count = regions.makeContiguous();
144 for (graph_scanner node(g); node != INVALID; ++node)
146 labels[*node] = regions.findLabel(labels[*node]);
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,
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;
164 vigra::UnionFindArray<LabelType> regions;
167 for (graph_scanner node(g); node != INVALID; ++node)
169 typename T1Map::value_type center = data[*node];
172 LabelType currentIndex = regions.nextFreeIndex();
174 for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
176 Shape diff = g.neighborOffset(arc.neighborIndex());
178 if(labeling_equality::callEqual(equal, center, data[g.target(*arc)], diff))
180 currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
184 labels[*node] = regions.finalizeIndex(currentIndex);
187 LabelType count = regions.makeContiguous();
190 for (graph_scanner node(g); node != INVALID; ++node)
192 labels[*node] = regions.findLabel(labels[*node]);
198 template <
class Graph,
class T1Map,
class T2Map,
class Equal>
199 typename T2Map::value_type
200 labelGraphWithBackground(Graph
const & g,
203 typename T1Map::value_type backgroundValue,
206 typedef typename Graph::NodeIt graph_scanner;
207 typedef typename Graph::OutBackArcIt neighbor_iterator;
208 typedef typename T2Map::value_type LabelType;
210 vigra::UnionFindArray<LabelType> regions;
213 for (graph_scanner node(g); node != INVALID; ++node)
215 typename T1Map::value_type center = data[*node];
218 if(equal(center, backgroundValue))
225 LabelType currentIndex = regions.nextFreeIndex();
227 for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
230 if(equal(center, data[g.target(*arc)]))
232 currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
236 labels[*node] = regions.finalizeIndex(currentIndex);
239 LabelType count = regions.makeContiguous();
242 for (graph_scanner node(g); node != INVALID; ++node)
244 labels[*node] = regions.findLabel(labels[*node]);
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,
254 typename T1Map::value_type backgroundValue,
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;
263 vigra::UnionFindArray<LabelType> regions;
266 for (graph_scanner node(g); node != INVALID; ++node)
268 typename T1Map::value_type center = data[*node];
271 if(labeling_equality::callEqual(equal, center, backgroundValue, Shape()))
278 LabelType currentIndex = regions.nextFreeIndex();
280 for (neighbor_iterator arc(g, node); arc != INVALID; ++arc)
283 Shape diff = g.neighborOffset(arc.neighborIndex());
284 if(labeling_equality::callEqual(equal, center, data[g.target(*arc)], diff))
286 currentIndex = regions.makeUnion(labels[g.target(*arc)], currentIndex);
290 labels[*node] = regions.finalizeIndex(currentIndex);
293 LabelType count = regions.makeContiguous();
296 for (graph_scanner node(g); node != INVALID; ++node)
298 labels[*node] = regions.findLabel(labels[*node]);
376 template <
unsigned int N,
class T,
class S1,
377 class Label,
class S2,
381 MultiArrayView<N, Label, S2> labels,
385 vigra_precondition(data.shape() == labels.shape(),
386 "labelMultiArray(): shape mismatch between input and output.");
388 GridGraph<N, undirected_tag> graph(data.shape(), neighborhood);
389 return lemon_graph::labelGraph(graph, data, labels, equal);
392 template <
unsigned int N,
class T,
class S1,
393 class Label,
class S2>
396 MultiArrayView<N, Label, S2> labels,
399 return labelMultiArray(data, labels, neighborhood, std::equal_to<T>());
469 template <
unsigned int N,
class T,
class S1,
470 class Label,
class S2,
474 MultiArrayView<N, Label, S2> labels,
479 vigra_precondition(data.shape() == labels.shape(),
480 "labelMultiArrayWithBackground(): shape mismatch between input and output.");
482 GridGraph<N, undirected_tag> graph(data.shape(), neighborhood);
483 return lemon_graph::labelGraphWithBackground(graph, data, labels, backgroundValue, equal);
486 template <
unsigned int N,
class T,
class S1,
487 class Label,
class S2>
490 MultiArrayView<N, Label, S2> labels,
492 T backgroundValue = T())
501 #endif //VIGRA_MULTI_LABELING_HXX