36 #ifndef VIGRA_BLOCKWISE_LABELING_HXX
37 #define VIGRA_BLOCKWISE_LABELING_HXX
39 #include "multi_gridgraph.hxx"
40 #include "multi_labeling.hxx"
41 #include "union_find.hxx"
42 #include "multi_array_chunked.hxx"
43 #include "metaprogramming.hxx"
45 #include "visit_border.hxx"
46 #include "blockify.hxx"
57 namespace blockwise_labeling_detail
60 template <
class Equal,
class Label>
65 UnionFindArray<Label>* global_unions;
68 template <
class Data,
class Shape>
69 void operator()(
const Data& u_data, Label& u_label,
const Data& v_data, Label& v_label,
const Shape& diff)
71 if(labeling_equality::callEqual(*equal, u_data, v_data, diff))
73 global_unions->makeUnion(u_label + u_label_offset, v_label + v_label_offset);
79 template <
class LabelBlocksIterator>
80 struct BlockwiseLabelingResult
82 typedef typename LabelBlocksIterator::value_type::value_type type;
85 template <
class DataBlocksIterator,
class LabelBlocksIterator,
class Equal,
class Value,
class Mapping>
86 typename BlockwiseLabelingResult<LabelBlocksIterator>::type
87 blockwiseLabeling(DataBlocksIterator data_blocks_begin, DataBlocksIterator data_blocks_end,
88 LabelBlocksIterator label_blocks_begin, LabelBlocksIterator label_blocks_end,
90 const Value* background_value,
93 typedef typename LabelBlocksIterator::value_type::value_type Label;
94 typedef typename DataBlocksIterator::shape_type Shape;
96 Shape blocks_shape = data_blocks_begin.shape();
97 vigra_precondition(blocks_shape == label_blocks_begin.shape() &&
98 blocks_shape == mapping.shape(),
99 "shapes of blocks of blocks do not match");
101 static const unsigned int Dimensions = DataBlocksIterator::dimension + 1;
102 MultiArray<Dimensions, Label> label_offsets(label_blocks_begin.shape());
105 Label unmerged_label_number;
107 DataBlocksIterator data_blocks_it = data_blocks_begin;
108 LabelBlocksIterator label_blocks_it = label_blocks_begin;
109 typename MultiArray<Dimensions, Label>::iterator offsets_it = label_offsets.begin();
110 Label current_offset = 0;
111 for( ; data_blocks_it != data_blocks_end; ++data_blocks_it, ++label_blocks_it, ++offsets_it)
113 vigra_assert(label_blocks_it != label_blocks_end && offsets_it != label_offsets.end(),
"");
114 *offsets_it = current_offset;
118 neighborhood, *background_value, equal);
123 neighborhood, equal);
126 unmerged_label_number = current_offset;
127 if(!background_value)
128 ++unmerged_label_number;
132 UnionFindArray<Label> global_unions(unmerged_label_number);
136 for(
typename MultiArray<Dimensions, Label>::iterator offsets_it = label_offsets.begin();
137 offsets_it != label_offsets.end();
140 global_unions.makeUnion(0, *offsets_it);
144 typedef GridGraph<Dimensions, undirected_tag> Graph;
145 typedef typename Graph::edge_iterator EdgeIterator;
146 Graph blocks_graph(blocks_shape, neighborhood);
147 for(EdgeIterator it = blocks_graph.get_edge_iterator(); it != blocks_graph.get_edge_end_iterator(); ++it)
149 Shape u = blocks_graph.u(*it);
150 Shape v = blocks_graph.v(*it);
151 Shape difference = v - u;
153 BorderVisitor<Equal, Label> border_visitor;
154 border_visitor.u_label_offset = label_offsets[u];
155 border_visitor.v_label_offset = label_offsets[v];
156 border_visitor.global_unions = &global_unions;
157 border_visitor.equal = &equal;
158 visitBorder(data_blocks_begin[u], label_blocks_begin[u],
159 data_blocks_begin[v], label_blocks_begin[v],
160 difference, neighborhood, border_visitor);
164 Label last_label = global_unions.makeContiguous();
166 typename MultiArray<Dimensions, Label>::iterator offsets_it = label_offsets.begin();
167 Label offset = *offsets_it;
169 typename Mapping::iterator mapping_it = mapping.begin();
170 for( ; offsets_it != label_offsets.end(); ++offsets_it, ++mapping_it)
173 Label next_offset = *offsets_it;
176 for(Label current_label = offset; current_label != next_offset; ++current_label)
178 mapping_it->push_back(global_unions.findLabel(current_label));
183 mapping_it->push_back(0);
184 for(Label current_label = offset + 1; current_label != next_offset + 1; ++current_label)
186 mapping_it->push_back(global_unions.findLabel(current_label));
190 offset = next_offset;
197 for(Label current_label = offset; current_label != unmerged_label_number; ++current_label)
199 mapping_it->push_back(global_unions.findLabel(current_label));
204 mapping_it->push_back(0);
205 for(Label current_label = offset + 1; current_label != unmerged_label_number; ++current_label)
207 mapping_it->push_back(global_unions.findLabel(current_label));
215 template <
class LabelBlocksIterator,
class MappingIterator>
216 void toGlobalLabels(LabelBlocksIterator label_blocks_begin, LabelBlocksIterator label_blocks_end,
217 MappingIterator mapping_begin, MappingIterator mapping_end)
219 typedef typename LabelBlocksIterator::value_type LabelBlock;
220 for( ; label_blocks_begin != label_blocks_end; ++label_blocks_begin, ++mapping_begin)
222 vigra_assert(mapping_begin != mapping_end,
"");
223 for(
typename LabelBlock::iterator labels_it = label_blocks_begin->begin();
224 labels_it != label_blocks_begin->end();
227 vigra_assert(*labels_it < mapping_begin->size(),
"");
228 *labels_it = (*mapping_begin)[*labels_it];
237 const T* getBackground(
const LabelOptions& options);
239 const T* getBlockShape(
const LabelOptions& options);
247 struct type_erasure_base
249 virtual ~type_erasure_base()
256 type_erasure(
const T& contained_obj)
262 VIGRA_UNIQUE_PTR<type_erasure_base> background_value_;
263 VIGRA_UNIQUE_PTR<type_erasure_base> block_shape_;
270 LabelOptions(
const LabelOptions&);
271 LabelOptions& operator=(
const LabelOptions&);
274 LabelOptions& background(
const T& background_value)
276 vigra_precondition(background_value_.get() == 0,
"background set twice");
277 background_value_ = VIGRA_UNIQUE_PTR<type_erasure_base>(
new type_erasure<T>(background_value));
281 LabelOptions& blockShape(
const TinyVector<MultiArrayIndex, N>& block_shape)
283 vigra_precondition(block_shape_.get() == 0,
"block shape set twice");
284 block_shape_ = VIGRA_UNIQUE_PTR<type_erasure_base>(
new type_erasure<TinyVector<MultiArrayIndex, N> >(block_shape));
296 friend const T* blockwise_labeling_detail::getBackground(
const LabelOptions& options);
298 friend const T* blockwise_labeling_detail::getBlockShape(
const LabelOptions& options);
299 friend NeighborhoodType blockwise_labeling_detail::getNeighborhood(
const LabelOptions& options);
302 namespace blockwise_labeling_detail
306 const T* getBackground(
const LabelOptions& options)
308 if(options.background_value_.get() == 0)
311 LabelOptions::type_erasure<T>* background =
dynamic_cast<LabelOptions::type_erasure<T>*
>(options.background_value_.get());
312 vigra_precondition(background != 0,
"background value type and data type do not match");
313 return &background->obj;
316 const T* getBlockShape(
const LabelOptions& options)
318 if(options.block_shape_.get() == 0)
321 LabelOptions::type_erasure<T>* block_shape =
dynamic_cast<LabelOptions::type_erasure<T>*
>(options.block_shape_.get());
322 vigra_precondition(block_shape != 0,
"shape type has invalid dimension");
323 return &block_shape->obj;
328 return options.neighborhood_;
335 template <
unsigned int N,
class Data,
class S1,
336 class Label,
class S2,
337 class Equal,
class S3>
338 Label labelMultiArrayBlockwise(
const MultiArrayView<N, Data, S1>& data,
339 MultiArrayView<N, Label, S2> labels,
340 const LabelOptions& options,
341 Equal equal, MultiArrayView<N, std::vector<Label>, S3>& mapping)
343 using namespace blockwise_labeling_detail;
344 TinyVector<MultiArrayIndex, N> block_shape(default_block_side_length);
345 const TinyVector<MultiArrayIndex, N>* options_block_shape = getBlockShape<TinyVector<MultiArrayIndex, N> >(options);
346 if(options_block_shape)
347 block_shape = *options_block_shape;
348 const Data* background_value = getBackground<Data>(options);
351 MultiArray<N, MultiArrayView<N, Data, S1> > data_blocks = blockify(data, block_shape);
352 MultiArray<N, MultiArrayView<N, Label, S2> > label_blocks = blockify(labels, block_shape);
353 return blockwiseLabeling(data_blocks.begin(), data_blocks.end(),
354 label_blocks.begin(), label_blocks.end(),
355 neighborhood, equal, background_value, mapping);
357 template <
unsigned int N,
class Data,
class S1,
358 class Label,
class S2,
360 Label labelMultiArrayBlockwise(
const MultiArrayView<N, Data, S1>& data,
361 MultiArrayView<N, Label, S2> labels,
const LabelOptions& options, Equal equal) {
362 using namespace blockwise_labeling_detail;
363 TinyVector<MultiArrayIndex, N> block_shape(default_block_side_length);
364 const TinyVector<MultiArrayIndex, N>* options_block_shape = getBlockShape<TinyVector<MultiArrayIndex, N> >(options);
365 if(options_block_shape)
366 block_shape = *options_block_shape;
367 const Data* background_value = getBackground<Data>(options);
370 MultiArray<N, MultiArrayView<N, Data, S1> > data_blocks = blockify(data, block_shape);
371 MultiArray<N, MultiArrayView<N, Label, S2> > label_blocks = blockify(labels, block_shape);
372 MultiArray<N, std::vector<Label> > mapping(data_blocks.shape());
373 Label last_label = blockwiseLabeling(data_blocks.begin(), data_blocks.end(),
374 label_blocks.begin(), label_blocks.end(),
375 neighborhood, equal, background_value, mapping);
378 toGlobalLabels(label_blocks.begin(), label_blocks.end(), mapping.begin(), mapping.end());
381 template <
unsigned int N,
class Data,
class S1,
382 class Label,
class S2>
383 Label labelMultiArrayBlockwise(
const MultiArrayView<N, Data, S1>& data,
384 MultiArrayView<N, Label, S2> labels,
385 const LabelOptions& options = LabelOptions())
387 return labelMultiArrayBlockwise(data, labels, options, std::equal_to<Data>());
467 template <
unsigned int N,
class Data,
class Label,
class Equal,
class S3>
468 Label labelMultiArrayBlockwise(
const ChunkedArray<N, Data>& data,
469 ChunkedArray<N, Label>& labels,
470 const LabelOptions& options,
471 Equal equal, MultiArrayView<N, std::vector<Label>, S3> mapping)
473 using namespace blockwise_labeling_detail;
474 const TinyVector<MultiArrayIndex, N>* options_block_shape = getBlockShape<TinyVector<MultiArrayIndex, N> >(options);
475 vigra_precondition(options_block_shape == 0,
"block shape not supported for chunked arrays, uses chunk size per default");
477 typedef typename ChunkedArray<N, Data>::shape_type Shape;
479 const Data* background_value = getBackground<Data>(options);
482 typedef typename ChunkedArray<N, Data>::chunk_const_iterator DataChunkIterator;
483 typedef typename ChunkedArray<N, Label>::chunk_iterator LabelChunkIterator;
485 DataChunkIterator data_chunks_begin = data.chunk_begin(Shape(0), data.shape());
486 LabelChunkIterator label_chunks_begin = labels.chunk_begin(Shape(0), labels.shape());
488 return blockwiseLabeling(data_chunks_begin, data_chunks_begin.getEndIterator(),
489 label_chunks_begin, label_chunks_begin.getEndIterator(),
490 neighborhood, equal, background_value, mapping);
492 template <
unsigned int N,
class Data,
class Label,
class Equal>
493 Label labelMultiArrayBlockwise(
const ChunkedArray<N, Data>& data,
494 ChunkedArray<N, Label>& labels,
495 const LabelOptions& options, Equal equal)
497 using namespace blockwise_labeling_detail;
498 MultiArray<N, std::vector<Label> > mapping(data.chunkArrayShape());
499 Label result = labelMultiArrayBlockwise(data, labels, options, equal, mapping);
500 typedef typename ChunkedArray<N, Data>::shape_type Shape;
501 toGlobalLabels(labels.chunk_begin(Shape(0), data.shape()), labels.chunk_end(Shape(0), data.shape()), mapping.begin(), mapping.end());
504 template <
unsigned int N,
class Data,
class Label>
505 Label labelMultiArrayBlockwise(
const ChunkedArray<N, Data>& data,
506 ChunkedArray<N, Label>& labels,
507 const LabelOptions& options = LabelOptions())
509 return labelMultiArrayBlockwise(data, labels, options, std::equal_to<Data>());
516 #endif // VIGRA_BLOCKWISE_LABELING_HXX