36 #ifndef VIGRA_BLOCKWISE_LABELING_HXX
37 #define VIGRA_BLOCKWISE_LABELING_HXX
41 #include "threadpool.hxx"
42 #include "counting_iterator.hxx"
43 #include "multi_gridgraph.hxx"
44 #include "multi_labeling.hxx"
45 #include "multi_blockwise.hxx"
46 #include "union_find.hxx"
47 #include "multi_array_chunked.hxx"
48 #include "metaprogramming.hxx"
50 #include "visit_border.hxx"
51 #include "blockify.hxx"
94 template <
class T,
int N>
103 BlockwiseOptions::numThreads(n);
108 namespace blockwise_labeling_detail
111 template <
class Equal,
class Label>
114 Label u_label_offset;
115 Label v_label_offset;
116 UnionFindArray<Label>* global_unions;
119 template <
class Data,
class Shape>
120 void operator()(
const Data& u_data, Label& u_label,
const Data& v_data, Label& v_label,
const Shape& diff)
122 if(labeling_equality::callEqual(*equal, u_data, v_data, diff))
124 global_unions->makeUnion(u_label + u_label_offset, v_label + v_label_offset);
130 template <
class LabelBlocksIterator>
131 struct BlockwiseLabelingResult
133 typedef typename LabelBlocksIterator::value_type::value_type type;
136 template <
class DataBlocksIterator,
class LabelBlocksIterator,
137 class Equal,
class Mapping>
138 typename BlockwiseLabelingResult<LabelBlocksIterator>::type
139 blockwiseLabeling(DataBlocksIterator data_blocks_begin, DataBlocksIterator data_blocks_end,
140 LabelBlocksIterator label_blocks_begin, LabelBlocksIterator label_blocks_end,
141 BlockwiseLabelOptions
const & options,
145 typedef typename LabelBlocksIterator::value_type::value_type Label;
146 typedef typename DataBlocksIterator::shape_type Shape;
148 Shape blocks_shape = data_blocks_begin.shape();
149 vigra_precondition(blocks_shape == label_blocks_begin.shape() &&
150 blocks_shape == mapping.shape(),
151 "shapes of blocks of blocks do not match");
152 vigra_precondition(std::distance(data_blocks_begin,data_blocks_end) == std::distance(label_blocks_begin,label_blocks_end),
153 "the sizes of input ranges are different");
155 static const unsigned int Dimensions = DataBlocksIterator::dimension + 1;
156 MultiArray<Dimensions, Label> label_offsets(label_blocks_begin.shape());
158 bool has_background = options.hasBackgroundValue();
161 Label unmerged_label_number;
163 DataBlocksIterator data_blocks_it = data_blocks_begin;
164 LabelBlocksIterator label_blocks_it = label_blocks_begin;
165 typename MultiArray<Dimensions, Label>::iterator offsets_it = label_offsets.begin();
166 Label current_offset = 0;
169 auto d = std::distance(data_blocks_begin, data_blocks_end);
172 std::vector<Label> nSeg(d);
177 [&](
const int ,
const uint64_t i){
186 for(
int i=0; i<d;++i){
187 offsets_it[i] = current_offset;
188 current_offset+=nSeg[i];
192 unmerged_label_number = current_offset;
194 ++unmerged_label_number;
198 UnionFindArray<Label> global_unions(unmerged_label_number);
202 for(
typename MultiArray<Dimensions, Label>::iterator offsets_it = label_offsets.begin();
203 offsets_it != label_offsets.end();
206 global_unions.makeUnion(0, *offsets_it);
210 typedef GridGraph<Dimensions, undirected_tag> Graph;
211 typedef typename Graph::edge_iterator EdgeIterator;
212 Graph blocks_graph(blocks_shape, options.getNeighborhood());
213 for(EdgeIterator it = blocks_graph.get_edge_iterator(); it != blocks_graph.get_edge_end_iterator(); ++it)
215 Shape u = blocks_graph.u(*it);
216 Shape v = blocks_graph.v(*it);
217 Shape difference = v - u;
219 BorderVisitor<Equal, Label> border_visitor;
220 border_visitor.u_label_offset = label_offsets[u];
221 border_visitor.v_label_offset = label_offsets[v];
222 border_visitor.global_unions = &global_unions;
223 border_visitor.equal = &equal;
224 visitBorder(data_blocks_begin[u], label_blocks_begin[u],
225 data_blocks_begin[v], label_blocks_begin[v],
226 difference, options.getNeighborhood(), border_visitor);
230 Label last_label = global_unions.makeContiguous();
232 typename MultiArray<Dimensions, Label>::iterator offsets_it = label_offsets.begin();
233 Label offset = *offsets_it;
235 typename Mapping::iterator mapping_it = mapping.begin();
236 for( ; offsets_it != label_offsets.end(); ++offsets_it, ++mapping_it)
239 Label next_offset = *offsets_it;
242 for(Label current_label = offset; current_label != next_offset; ++current_label)
244 mapping_it->push_back(global_unions.findLabel(current_label));
249 mapping_it->push_back(0);
250 for(Label current_label = offset + 1; current_label != next_offset + 1; ++current_label)
252 mapping_it->push_back(global_unions.findLabel(current_label));
256 offset = next_offset;
263 for(Label current_label = offset; current_label != unmerged_label_number; ++current_label)
265 mapping_it->push_back(global_unions.findLabel(current_label));
270 mapping_it->push_back(0);
271 for(Label current_label = offset + 1; current_label != unmerged_label_number; ++current_label)
273 mapping_it->push_back(global_unions.findLabel(current_label));
281 template <
class LabelBlocksIterator,
class MappingIterator>
282 void toGlobalLabels(LabelBlocksIterator label_blocks_begin, LabelBlocksIterator label_blocks_end,
283 MappingIterator mapping_begin, MappingIterator mapping_end)
285 typedef typename LabelBlocksIterator::value_type LabelBlock;
286 for( ; label_blocks_begin != label_blocks_end; ++label_blocks_begin, ++mapping_begin)
288 vigra_assert(mapping_begin != mapping_end,
"");
289 for(
typename LabelBlock::iterator labels_it = label_blocks_begin->begin();
290 labels_it != label_blocks_begin->end();
293 vigra_assert(*labels_it < mapping_begin->size(),
"");
294 *labels_it = (*mapping_begin)[*labels_it];
400 template <
unsigned int N,
class Data,
class S1,
401 class Label,
class S2,
402 class Equal,
class S3>
404 MultiArrayView<N, Label, S2> labels,
405 const BlockwiseLabelOptions& options,
407 MultiArrayView<N, std::vector<Label>, S3>& mapping)
409 using namespace blockwise_labeling_detail;
411 typedef typename MultiArrayShape<N>::type Shape;
412 Shape block_shape(options.getBlockShapeN<N>());
414 MultiArray<N, MultiArrayView<N, Data, S1> > data_blocks = blockify(data, block_shape);
415 MultiArray<N, MultiArrayView<N, Label, S2> > label_blocks = blockify(labels, block_shape);
416 return blockwiseLabeling(data_blocks.begin(), data_blocks.end(),
417 label_blocks.begin(), label_blocks.end(),
418 options, equal, mapping);
421 template <
unsigned int N,
class Data,
class S1,
422 class Label,
class S2,
425 MultiArrayView<N, Label, S2> labels,
426 const BlockwiseLabelOptions& options,
429 using namespace blockwise_labeling_detail;
431 typedef typename MultiArrayShape<N>::type Shape;
432 Shape block_shape(options.getBlockShapeN<N>());
434 MultiArray<N, MultiArrayView<N, Data, S1> > data_blocks = blockify(data, block_shape);
435 MultiArray<N, MultiArrayView<N, Label, S2> > label_blocks = blockify(labels, block_shape);
436 MultiArray<N, std::vector<Label> > mapping(data_blocks.shape());
437 Label last_label = blockwiseLabeling(data_blocks.begin(), data_blocks.end(),
438 label_blocks.begin(), label_blocks.end(),
439 options, equal, mapping);
442 toGlobalLabels(label_blocks.begin(), label_blocks.end(), mapping.begin(), mapping.end());
446 template <
unsigned int N,
class Data,
class S1,
447 class Label,
class S2>
449 MultiArrayView<N, Label, S2> labels,
450 const BlockwiseLabelOptions& options = BlockwiseLabelOptions())
456 template <
unsigned int N,
class Data,
class Label,
class Equal,
class S3>
458 ChunkedArray<N, Label>& labels,
459 const BlockwiseLabelOptions& options,
461 MultiArrayView<N, std::vector<Label>, S3> mapping)
463 using namespace blockwise_labeling_detail;
465 vigra_precondition(options.getBlockShape().size() == 0,
466 "labelMultiArrayBlockwise(ChunkedArray, ...): custom block shapes not supported "
467 "(always uses the array's chunk shape).");
469 typedef typename ChunkedArray<N, Data>::shape_type Shape;
471 typedef typename ChunkedArray<N, Data>::chunk_const_iterator DataChunkIterator;
472 typedef typename ChunkedArray<N, Label>::chunk_iterator LabelChunkIterator;
474 DataChunkIterator data_chunks_begin = data.chunk_begin(Shape(0), data.shape());
475 LabelChunkIterator label_chunks_begin = labels.chunk_begin(Shape(0), labels.shape());
477 return blockwiseLabeling(data_chunks_begin, data_chunks_begin.getEndIterator(),
478 label_chunks_begin, label_chunks_begin.getEndIterator(),
479 options, equal, mapping);
482 template <
unsigned int N,
class Data,
class Label,
class Equal>
484 ChunkedArray<N, Label>& labels,
485 const BlockwiseLabelOptions& options,
488 using namespace blockwise_labeling_detail;
489 MultiArray<N, std::vector<Label> > mapping(data.chunkArrayShape());
491 typedef typename ChunkedArray<N, Data>::shape_type Shape;
492 toGlobalLabels(labels.chunk_begin(Shape(0), data.shape()), labels.chunk_end(Shape(0), data.shape()), mapping.begin(), mapping.end());
496 template <
unsigned int N,
class Data,
class Label>
498 ChunkedArray<N, Label>& labels,
499 const BlockwiseLabelOptions& options = BlockwiseLabelOptions())
508 #endif // VIGRA_BLOCKWISE_LABELING_HXX
Option object for labelMultiArray().
Definition: multi_labeling.hxx:309
Definition: blockwise_labeling.hxx:66
Definition: multi_blockwise.hxx:54
unsigned int labelMultiArrayBlockwise(...)
Connected components labeling for MultiArrays and ChunkedArrays.
doxygen_overloaded_function(template<...> void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
void parallel_foreach(...)
Apply a functor to all items in a range in parallel.
LabelOptions & neighborhood(NeighborhoodType n)
Choose direct or indirect neighborhood.
Definition: multi_labeling.hxx:326
LabelOptions & ignoreBackgroundValue(T const &t)
Set background value.
Definition: multi_labeling.hxx:351
BlockwiseOptions & blockShape(const Shape &blockShape)
Definition: multi_blockwise.hxx:114
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