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

blockwise_watersheds.hxx VIGRA

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 
49 namespace vigra
50 {
51 
52 /** \addtogroup Superpixels
53 */
54 //@{
55 
56 namespace blockwise_watersheds_detail
57 {
58 
59 template <class DataArray, class DirectionsBlocksIterator>
60 void 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);
66  typedef typename MultiArrayShape<DataArray::actual_dimension>::type Shape;
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 
114 template <unsigned int N>
115 struct 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  */
198 doxygen_overloaded_function(template <...> unsigned int unionFindWatershedsBlockwise)
199 
200 template <unsigned int N, class Data, class S1,
201  class Label, class S2>
202 Label unionFindWatershedsBlockwise(MultiArrayView<N, Data, S1> data,
203  MultiArrayView<N, Label, S2> labels,
204  BlockwiseLabelOptions const & options = BlockwiseLabelOptions())
205 {
206  using namespace blockwise_watersheds_detail;
207 
208  typedef typename MultiArrayView<N, Data, S1>::difference_type Shape;
209  Shape shape = data.shape();
210  vigra_precondition(shape == labels.shape(), "shapes of data and labels do not match");
211 
212  MultiArray<N, unsigned short> directions(shape);
213  Shape block_shape = options.getBlockShapeN<N>();
214 
215  MultiArray<N, MultiArrayView<N, unsigned short> > directions_blocks = blockify(directions, block_shape);
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 
224 template <unsigned int N, class Data, class Label>
225 Label 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 
249 template <unsigned int N, class Data,
250  class Label>
251 inline Label
252 unionFindWatershedsBlockwise(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
vigra::FourNeighborhood::Direction
NeighborCode::Direction Direction
Definition: pixelneighborhood.hxx:321
vigra::labelMultiArrayBlockwise
unsigned int labelMultiArrayBlockwise(...)
Connected components labeling for MultiArrays and ChunkedArrays.
vigra::doxygen_overloaded_function
doxygen_overloaded_function(template<...> void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
vigra::parallel_foreach
void parallel_foreach(...)
Apply a functor to all items in a range in parallel.
vigra::unionFindWatershedsBlockwise
unsigned int unionFindWatershedsBlockwise(...)
Blockwise union-find watersheds transform for MultiArrays and ChunkedArrays.

© 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.1 (Fri May 19 2017)