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");
153 static const unsigned int Dimensions = DataBlocksIterator::dimension + 1;
154 MultiArray<Dimensions, Label> label_offsets(label_blocks_begin.shape());
156 bool has_background = options.hasBackgroundValue();
159 Label unmerged_label_number;
161 DataBlocksIterator data_blocks_it = data_blocks_begin;
162 LabelBlocksIterator label_blocks_it = label_blocks_begin;
163 typename MultiArray<Dimensions, Label>::iterator offsets_it = label_offsets.begin();
164 Label current_offset = 0;
167 auto d = std::distance(data_blocks_begin, data_blocks_end);
170 std::vector<Label> nSeg(d);
175 [&](
const int threadId,
const uint64_t i){
184 for(
int i=0; i<d;++i){
185 offsets_it[i] = current_offset;
186 current_offset+=nSeg[i];
190 unmerged_label_number = current_offset;
192 ++unmerged_label_number;
196 UnionFindArray<Label> global_unions(unmerged_label_number);
200 for(
typename MultiArray<Dimensions, Label>::iterator offsets_it = label_offsets.begin();
201 offsets_it != label_offsets.end();
204 global_unions.makeUnion(0, *offsets_it);
208 typedef GridGraph<Dimensions, undirected_tag> Graph;
209 typedef typename Graph::edge_iterator EdgeIterator;
210 Graph blocks_graph(blocks_shape, options.getNeighborhood());
211 for(EdgeIterator it = blocks_graph.get_edge_iterator(); it != blocks_graph.get_edge_end_iterator(); ++it)
213 Shape u = blocks_graph.u(*it);
214 Shape v = blocks_graph.v(*it);
215 Shape difference = v - u;
217 BorderVisitor<Equal, Label> border_visitor;
218 border_visitor.u_label_offset = label_offsets[u];
219 border_visitor.v_label_offset = label_offsets[v];
220 border_visitor.global_unions = &global_unions;
221 border_visitor.equal = &equal;
222 visitBorder(data_blocks_begin[u], label_blocks_begin[u],
223 data_blocks_begin[v], label_blocks_begin[v],
224 difference, options.getNeighborhood(), border_visitor);
228 Label last_label = global_unions.makeContiguous();
230 typename MultiArray<Dimensions, Label>::iterator offsets_it = label_offsets.begin();
231 Label offset = *offsets_it;
233 typename Mapping::iterator mapping_it = mapping.begin();
234 for( ; offsets_it != label_offsets.end(); ++offsets_it, ++mapping_it)
237 Label next_offset = *offsets_it;
240 for(Label current_label = offset; current_label != next_offset; ++current_label)
242 mapping_it->push_back(global_unions.findLabel(current_label));
247 mapping_it->push_back(0);
248 for(Label current_label = offset + 1; current_label != next_offset + 1; ++current_label)
250 mapping_it->push_back(global_unions.findLabel(current_label));
254 offset = next_offset;
261 for(Label current_label = offset; current_label != unmerged_label_number; ++current_label)
263 mapping_it->push_back(global_unions.findLabel(current_label));
268 mapping_it->push_back(0);
269 for(Label current_label = offset + 1; current_label != unmerged_label_number; ++current_label)
271 mapping_it->push_back(global_unions.findLabel(current_label));
279 template <
class LabelBlocksIterator,
class MappingIterator>
280 void toGlobalLabels(LabelBlocksIterator label_blocks_begin, LabelBlocksIterator label_blocks_end,
281 MappingIterator mapping_begin, MappingIterator mapping_end)
283 typedef typename LabelBlocksIterator::value_type LabelBlock;
284 for( ; label_blocks_begin != label_blocks_end; ++label_blocks_begin, ++mapping_begin)
286 vigra_assert(mapping_begin != mapping_end,
"");
287 for(
typename LabelBlock::iterator labels_it = label_blocks_begin->begin();
288 labels_it != label_blocks_begin->end();
291 vigra_assert(*labels_it < mapping_begin->size(),
"");
292 *labels_it = (*mapping_begin)[*labels_it];
394 template <
unsigned int N,
class Data,
class S1,
395 class Label,
class S2,
396 class Equal,
class S3>
398 MultiArrayView<N, Label, S2> labels,
399 const BlockwiseLabelOptions& options,
401 MultiArrayView<N, std::vector<Label>, S3>& mapping)
403 using namespace blockwise_labeling_detail;
405 typedef typename MultiArrayShape<N>::type Shape;
406 Shape block_shape(options.getBlockShapeN<N>());
408 MultiArray<N, MultiArrayView<N, Data, S1> > data_blocks = blockify(data, block_shape);
409 MultiArray<N, MultiArrayView<N, Label, S2> > label_blocks = blockify(labels, block_shape);
410 return blockwiseLabeling(data_blocks.begin(), data_blocks.end(),
411 label_blocks.begin(), label_blocks.end(),
412 options, equal, mapping);
415 template <
unsigned int N,
class Data,
class S1,
416 class Label,
class S2,
419 MultiArrayView<N, Label, S2> labels,
420 const BlockwiseLabelOptions& options,
423 using namespace blockwise_labeling_detail;
425 typedef typename MultiArrayShape<N>::type Shape;
426 Shape block_shape(options.getBlockShapeN<N>());
428 MultiArray<N, MultiArrayView<N, Data, S1> > data_blocks = blockify(data, block_shape);
429 MultiArray<N, MultiArrayView<N, Label, S2> > label_blocks = blockify(labels, block_shape);
430 MultiArray<N, std::vector<Label> > mapping(data_blocks.shape());
431 Label last_label = blockwiseLabeling(data_blocks.begin(), data_blocks.end(),
432 label_blocks.begin(), label_blocks.end(),
433 options, equal, mapping);
436 toGlobalLabels(label_blocks.begin(), label_blocks.end(), mapping.begin(), mapping.end());
440 template <
unsigned int N,
class Data,
class S1,
441 class Label,
class S2>
443 MultiArrayView<N, Label, S2> labels,
444 const BlockwiseLabelOptions& options = BlockwiseLabelOptions())
450 template <
unsigned int N,
class Data,
class Label,
class Equal,
class S3>
452 ChunkedArray<N, Label>& labels,
453 const BlockwiseLabelOptions& options,
455 MultiArrayView<N, std::vector<Label>, S3> mapping)
457 using namespace blockwise_labeling_detail;
459 vigra_precondition(options.getBlockShape().size() == 0,
460 "labelMultiArrayBlockwise(ChunkedArray, ...): custom block shapes not supported "
461 "(always uses the array's chunk shape).");
463 typedef typename ChunkedArray<N, Data>::shape_type Shape;
465 typedef typename ChunkedArray<N, Data>::chunk_const_iterator DataChunkIterator;
466 typedef typename ChunkedArray<N, Label>::chunk_iterator LabelChunkIterator;
468 DataChunkIterator data_chunks_begin = data.chunk_begin(Shape(0), data.shape());
469 LabelChunkIterator label_chunks_begin = labels.chunk_begin(Shape(0), labels.shape());
471 return blockwiseLabeling(data_chunks_begin, data_chunks_begin.getEndIterator(),
472 label_chunks_begin, label_chunks_begin.getEndIterator(),
473 options, equal, mapping);
476 template <
unsigned int N,
class Data,
class Label,
class Equal>
478 ChunkedArray<N, Label>& labels,
479 const BlockwiseLabelOptions& options,
482 using namespace blockwise_labeling_detail;
483 MultiArray<N, std::vector<Label> > mapping(data.chunkArrayShape());
485 typedef typename ChunkedArray<N, Data>::shape_type Shape;
486 toGlobalLabels(labels.chunk_begin(Shape(0), data.shape()), labels.chunk_end(Shape(0), data.shape()), mapping.begin(), mapping.end());
490 template <
unsigned int N,
class Data,
class Label>
492 ChunkedArray<N, Label>& labels,
493 const BlockwiseLabelOptions& options = BlockwiseLabelOptions())
502 #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