[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

blockwise_watersheds.hxx
1/************************************************************************/
2/* */
3/* Copyright 2013-2014 by Martin Bidlingmaier and Ullrich Koethe */
4/* */
5/* This file is part of the VIGRA computer vision library. */
6/* The VIGRA Website is */
7/* http://hci.iwr.uni-heidelberg.de/vigra/ */
8/* Please direct questions, bug reports, and contributions to */
9/* ullrich.koethe@iwr.uni-heidelberg.de or */
10/* vigra@informatik.uni-hamburg.de */
11/* */
12/* Permission is hereby granted, free of charge, to any person */
13/* obtaining a copy of this software and associated documentation */
14/* files (the "Software"), to deal in the Software without */
15/* restriction, including without limitation the rights to use, */
16/* copy, modify, merge, publish, distribute, sublicense, and/or */
17/* sell copies of the Software, and to permit persons to whom the */
18/* Software is furnished to do so, subject to the following */
19/* conditions: */
20/* */
21/* The above copyright notice and this permission notice shall be */
22/* included in all copies or substantial portions of the */
23/* Software. */
24/* */
25/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27/* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28/* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29/* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30/* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32/* OTHER DEALINGS IN THE SOFTWARE. */
33/* */
34/************************************************************************/
35
36#ifndef VIGRA_BLOCKWISE_WATERSHEDS_HXX
37#define VIGRA_BLOCKWISE_WATERSHEDS_HXX
38
39#include "threadpool.hxx"
40#include "multi_array.hxx"
41#include "multi_gridgraph.hxx"
42#include "blockify.hxx"
43#include "blockwise_labeling.hxx"
44#include "metaprogramming.hxx"
45#include "overlapped_blocks.hxx"
46
47#include <limits>
48
49namespace vigra
50{
51
52/** \addtogroup Superpixels
53*/
54//@{
55
56namespace blockwise_watersheds_detail
57{
58
59template <class DataArray, class DirectionsBlocksIterator>
60void prepareBlockwiseWatersheds(const Overlaps<DataArray>& overlaps,
61 DirectionsBlocksIterator directions_blocks_begin,
62 BlockwiseLabelOptions const & options)
63{
64 static const unsigned int N = DataArray::actual_dimension;
65 ignore_argument(N);
67 typedef typename DirectionsBlocksIterator::value_type DirectionsBlock;
68 Shape shape = overlaps.shape();
69 vigra_assert(shape == directions_blocks_begin.shape(), "");
70
71 MultiCoordinateIterator<DataArray::actual_dimension> itBegin(shape);
72 MultiCoordinateIterator<DataArray::actual_dimension> end = itBegin.getEndIterator();
73 typedef typename MultiCoordinateIterator<DataArray::actual_dimension>::value_type Coordinate;
74
75 parallel_foreach(options.getNumThreads(),
76 itBegin,end,
77 [&](const int /*threadId*/, const Coordinate iterVal){
78
79 DirectionsBlock directions_block = directions_blocks_begin[iterVal];
80 OverlappingBlock<DataArray> data_block = overlaps[iterVal];
81
82 typedef GridGraph<DataArray::actual_dimension, undirected_tag> Graph;
83 typedef typename Graph::NodeIt GraphScanner;
84 typedef typename Graph::OutArcIt NeighborIterator;
85
86 Graph graph(data_block.block.shape(), options.getNeighborhood());
87 for(GraphScanner node(graph); node != lemon::INVALID; ++node)
88 {
89 if(within(*node, data_block.inner_bounds))
90 {
91 typedef typename DataArray::value_type Data;
92 Data lowest_neighbor = data_block.block[*node];
93
94 typedef typename DirectionsBlock::value_type Direction;
95 Direction lowest_neighbor_direction = std::numeric_limits<unsigned short>::max();
96
97 for(NeighborIterator arc(graph, *node); arc != lemon::INVALID; ++arc)
98 {
99 Shape neighbor_coordinates = graph.target(*arc);
100 Data neighbor_data = data_block.block[neighbor_coordinates];
101 if(neighbor_data < lowest_neighbor)
102 {
103 lowest_neighbor = neighbor_data;
104 lowest_neighbor_direction = arc.neighborIndex();
105 }
106 }
107 directions_block[*node - data_block.inner_bounds.first] = lowest_neighbor_direction;
108 }
109 }
110 }
111 );
112}
113
114template <unsigned int N>
115struct UnionFindWatershedsEquality
116{
117 // FIXME: this graph object shouldn't be necessary, most functions (and state) of graph are not used
118 // this probably needs some refactoring in GridGraph
119 GridGraph<N, undirected_tag>* graph;
120
121 template <class Shape>
122 bool operator()(unsigned short u, const unsigned short v, const Shape& diff) const
123 {
124 static const unsigned short plateau_id = std::numeric_limits<unsigned short>::max();
125 return (u == plateau_id && v == plateau_id) ||
126 (u != plateau_id && graph->neighborOffset(u) == diff) ||
127 (v != plateau_id && graph->neighborOffset(graph->oppositeIndex(v)) == diff);
128 }
129
130 struct WithDiffTag
131 {};
132};
133
134} // namespace blockwise_watersheds_detail
135
136/*************************************************************/
137/* */
138/* unionFindWatershedsBlockwise */
139/* */
140/*************************************************************/
141
142/** \weakgroup ParallelProcessing
143 \sa unionFindWatershedsBlockwise <B>(...)</B>
144*/
145
146/** \brief Blockwise union-find watersheds transform for MultiArrays and ChunkedArrays.
147
148 <b> Declaration:</b>
149
150 \code
151 namespace vigra { namespace blockwise {
152 template <unsigned int N, class Data, class S1,
153 class Label, class S2>
154 Label
155 unionFindWatershedsBlockwise(MultiArrayView<N, Data, S1> data,
156 MultiArrayView<N, Label, S2> labels,
157 BlockwiseLabelOptions const & options);
158
159 template <unsigned int N, class Data, class Label>
160 Label
161 unionFindWatershedsBlockwise(const ChunkedArray<N, Data>& data,
162 ChunkedArray<N, Label>& labels,
163 BlockwiseLabelOptions const & options = BlockwiseLabelOptions());
164
165 // provide temporary directions storage
166 template <unsigned int N, class Data, class Label>
167 Label
168 unionFindWatershedsBlockwise(const ChunkedArray<N, Data>& data,
169 ChunkedArray<N, Label>& labels,
170 BlockwiseLabelOptions const & options,
171 ChunkedArray<N, unsigned short>& temporary_storage);
172 }}
173 \endcode
174
175 The resulting labeling is equivalent to a labeling by \ref watershedsUnionFind, that is,
176 the components are the same but may have different ids.
177 If \a temporary_storage is provided, this array is used for intermediate result storage.
178 Otherwise, a newly created \ref vigra::ChunkedArrayLazy is used.
179
180 Return: the number of labels assigned (=largest label, because labels start at one)
181
182 <b> Usage: </b>
183
184 <b>\#include </b> <vigra/blockwise_watersheds.hxx><br>
185 Namespace: vigra
186
187 \code
188 Shape3 shape = Shape3(10);
189 Shape3 chunk_shape = Shape3(4);
190 ChunkedArrayLazy<3, int> data(shape, chunk_shape);
191 // fill data ...
192
193 ChunkedArrayLazy<3, size_t> labels(shape, chunk_shape);
194
195 unionFindWatershedsBlockwise(data, labels, IndirectNeighborhood);
196 \endcode
197 */
198doxygen_overloaded_function(template <...> unsigned int unionFindWatershedsBlockwise)
199
200template <unsigned int N, class Data, class S1,
201 class Label, class S2>
205{
206 using namespace blockwise_watersheds_detail;
207
209 Shape shape = data.shape();
210 vigra_precondition(shape == labels.shape(), "shapes of data and labels do not match");
211
213 Shape block_shape = options.getBlockShapeN<N>();
214
216
217 Overlaps<MultiArrayView<N, Data, S1> > overlaps(data, block_shape, Shape(1), Shape(1));
218 prepareBlockwiseWatersheds(overlaps, directions_blocks.begin(), options);
219 GridGraph<N, undirected_tag> graph(data.shape(), options.getNeighborhood());
220 UnionFindWatershedsEquality<N> equal = {&graph};
221 return labelMultiArrayBlockwise(directions, labels, options, equal);
222}
223
224template <unsigned int N, class Data, class Label>
225Label unionFindWatershedsBlockwise(const ChunkedArray<N, Data>& data,
226 ChunkedArray<N, Label>& labels,
227 BlockwiseLabelOptions const & options,
228 ChunkedArray<N, unsigned short>& directions)
229{
230 using namespace blockwise_watersheds_detail;
231
232 typedef typename ChunkedArray<N, Data>::shape_type Shape;
233 Shape shape = data.shape();
234 vigra_precondition(shape == labels.shape() && shape == directions.shape(),
235 "unionFindWatershedsBlockwise(): shapes of data and labels do not match");
236 Shape chunk_shape = data.chunkShape();
237 vigra_precondition(chunk_shape == labels.chunkShape() && chunk_shape == directions.chunkShape(),
238 "unionFindWatershedsBlockwise(): chunk shapes do not match");
239
240 Overlaps<ChunkedArray<N, Data> > overlaps(data, data.chunkShape(), Shape(1), Shape(1));
241
242 prepareBlockwiseWatersheds(overlaps, directions.chunk_begin(Shape(0), shape), options);
243
244 GridGraph<N, undirected_tag> graph(shape, options.getNeighborhood());
245 UnionFindWatershedsEquality<N> equal = {&graph};
246 return labelMultiArrayBlockwise(directions, labels, options, equal);
247}
248
249template <unsigned int N, class Data,
250 class Label>
251inline Label
252unionFindWatershedsBlockwise(const ChunkedArray<N, Data>& data,
253 ChunkedArray<N, Label>& labels,
254 BlockwiseLabelOptions const & options = BlockwiseLabelOptions())
255{
256 ChunkedArrayLazy<N, unsigned short> directions(data.shape(), data.chunkShape());
257 return unionFindWatershedsBlockwise(data, labels, options, directions);
258}
259
260//@}
261
262} // namespace vigra
263
264#endif // VIGRA_BLOCKWISE_WATERSHEDS_HXX
Definition blockwise_labeling.hxx:69
TinyVector< MultiArrayIndex, N > type
Definition multi_shape.hxx:272
Class for a single RGB value.
Definition rgbvalue.hxx:128
iterator begin()
Definition tinyvector.hxx:861
unsigned int labelMultiArrayBlockwise(...)
Connected components labeling for MultiArrays and ChunkedArrays.
unsigned int unionFindWatershedsBlockwise(...)
Blockwise union-find watersheds transform for MultiArrays and ChunkedArrays.
void parallel_foreach(...)
Apply a functor to all items in a range in parallel.

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.11.2