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,
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;
161 Label unmerged_label_number;
163 DataBlocksIterator data_blocks_it = data_blocks_begin;
164 LabelBlocksIterator label_blocks_it = label_blocks_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);
203 offsets_it != label_offsets.end();
206 global_unions.makeUnion(0, *offsets_it);
211 typedef typename Graph::edge_iterator EdgeIterator;
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],
230 Label last_label = global_unions.makeContiguous();
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>
409 using namespace blockwise_labeling_detail;
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,
429 using namespace blockwise_labeling_detail;
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>
456 template <
unsigned int N,
class Data,
class Label,
class Equal,
class S3>
463 using namespace blockwise_labeling_detail;
466 "labelMultiArrayBlockwise(ChunkedArray, ...): custom block shapes not supported " 467 "(always uses the array's chunk 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>
488 using namespace blockwise_labeling_detail;
496 template <
unsigned int N,
class Data,
class Label>
508 #endif // VIGRA_BLOCKWISE_LABELING_HXX chunk_iterator chunk_end(shape_type const &start, shape_type const &stop)
Create the end iterator for iteration over all chunks intersected by the given ROI.
Definition: multi_array_chunked.hxx:2437
Define a grid graph in arbitrary dimensions.
Definition: multi_fwd.hxx:217
Sequential iterator for MultiArrayView.
Definition: multi_fwd.hxx:161
Option object for labelMultiArray().
Definition: multi_labeling.hxx:309
TinyVector< MultiArrayIndex, N > getBlockShapeN() const
Definition: multi_blockwise.hxx:89
chunk_iterator chunk_begin(shape_type const &start, shape_type const &stop)
Create an iterator over all chunks intersected by the given ROI.
Definition: multi_array_chunked.hxx:2428
NeighborhoodType getNeighborhood() const
Query the neighborhood type (direct or indirect).
Definition: multi_labeling.hxx:334
Main MultiArray class containing the memory management.
Definition: multi_array.hxx:2474
Interface and base class for chunked arrays.
Definition: multi_array_chunked.hxx:463
bool hasBackgroundValue() const
Check if some background value is to be ignored.
Definition: multi_labeling.hxx:359
doxygen_overloaded_function(template<... > void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
virtual shape_type chunkArrayShape() const
Number of chunks along each coordinate direction.
Definition: multi_array_chunked.hxx:1688
Definition: blockwise_labeling.hxx:66
Definition: multi_blockwise.hxx:54
unsigned int labelMultiArrayBlockwise(...)
Connected components labeling for MultiArrays and ChunkedArrays.
shape_type const & shape() const
Return the shape in this array.
Shape const & getBlockShape() const
Definition: multi_blockwise.hxx:71
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
Base class for, and view to, vigra::MultiArray.
Definition: multi_array.hxx:704
LabelOptions & ignoreBackgroundValue(T const &t)
Set background value.
Definition: multi_labeling.hxx:351
size_type size() const
Definition: array_vector.hxx:358
Node u(Edge const &e) const
Get the start node of the given edge e (API: LEMON, the boost::graph API provides the free function ...
Definition: multi_gridgraph.hxx:2382
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
int getNumThreads() const
Get desired number of threads.
Definition: threadpool.hxx:85