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");
153 static const unsigned int Dimensions = DataBlocksIterator::dimension + 1;
159 Label unmerged_label_number;
161 DataBlocksIterator data_blocks_it = data_blocks_begin;
162 LabelBlocksIterator label_blocks_it = label_blocks_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);
201 offsets_it != label_offsets.end();
204 global_unions.makeUnion(0, *offsets_it);
209 typedef typename Graph::edge_iterator EdgeIterator;
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],
228 Label last_label = global_unions.makeContiguous();
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>
403 using namespace blockwise_labeling_detail;
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,
423 using namespace blockwise_labeling_detail;
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>
450 template <
unsigned int N,
class Data,
class Label,
class Equal,
class S3>
457 using namespace blockwise_labeling_detail;
460 "labelMultiArrayBlockwise(ChunkedArray, ...): custom block shapes not supported " 461 "(always uses the array's chunk 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>
482 using namespace blockwise_labeling_detail;
490 template <
unsigned int N,
class Data,
class Label>
502 #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:2439
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
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:2430
int getNumThreads() const
Get desired number of threads.
Definition: threadpool.hxx:85
Main MultiArray class containing the memory management.
Definition: multi_array.hxx:2422
shape_type const & shape() const
Return the shape in this array.
Interface and base class for chunked arrays.
Definition: multi_array_chunked.hxx:470
Definition: accessor.hxx:43
doxygen_overloaded_function(template<... > void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
bool hasBackgroundValue() const
Check if some background value is to be ignored.
Definition: multi_labeling.hxx:359
Definition: blockwise_labeling.hxx:66
TinyVector< MultiArrayIndex, N > getBlockShapeN() const
Definition: multi_blockwise.hxx:89
Definition: multi_blockwise.hxx:54
unsigned int labelMultiArrayBlockwise(...)
Connected components labeling for MultiArrays and ChunkedArrays.
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
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
NeighborhoodType getNeighborhood() const
Query the neighborhood type (direct or indirect).
Definition: multi_labeling.hxx:334
Shape const & getBlockShape() const
Definition: multi_blockwise.hxx:71
virtual shape_type chunkArrayShape() const
Number of chunks along each coordinate direction.
Definition: multi_array_chunked.hxx:1691
Base class for, and view to, vigra::MultiArray.
Definition: multi_array.hxx:652
LabelOptions & ignoreBackgroundValue(T const &t)
Set background value.
Definition: multi_labeling.hxx:351
size_type size() const
Definition: array_vector.hxx:358
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