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

eccentricitytransform.hxx VIGRA

1 /************************************************************************/
2 /* */
3 /* Copyright 2014 by Philip Schill 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 
37 #ifndef VIGRA_ECCENTRICITYTRANSFORM_HXX
38 #define VIGRA_ECCENTRICITYTRANSFORM_HXX
39 
40 /*std*/
41 #include <algorithm>
42 #include <set>
43 
44 /*vigra*/
45 #include "accumulator.hxx"
46 #include "multi_labeling.hxx"
47 #include "multi_distance.hxx"
48 #include "multi_resize.hxx"
49 #include "graph_algorithms.hxx"
50 
51 
52 namespace vigra
53 {
54 
55 template <class Graph, class WeightType,
56  class EdgeMap, class Shape>
57 TinyVector<MultiArrayIndex, Shape::static_size>
58 eccentricityCentersOneRegionImpl(ShortestPathDijkstra<Graph, WeightType> & pathFinder,
59  const EdgeMap & weights, WeightType maxWeight,
60  Shape anchor, Shape const & start, Shape const & stop)
61 {
62  int maxIterations = 4;
63  for(int k=0; k < maxIterations; ++k)
64  {
65  pathFinder.run(start, stop, weights, anchor, lemon::INVALID, maxWeight);
66  anchor = pathFinder.target();
67  // FIXME: implement early stopping when source and target don't change anymore
68  }
69 
70  Polygon<TinyVector<float, Shape::static_size> > path;
71  path.push_back_unsafe(anchor);
72  while(pathFinder.predecessors()[path.back()] != path.back())
73  path.push_back_unsafe(pathFinder.predecessors()[path.back()]);
74  return path[roundi(path.arcLengthQuantile(0.5))];
75 }
76 
77 template <unsigned int N, class T, class S, class Graph,
78  class ACCUMULATOR, class DIJKSTRA, class Array>
79 void
80 eccentricityCentersImpl(const MultiArrayView<N, T, S> & src,
81  Graph const & g,
82  ACCUMULATOR const & r,
83  DIJKSTRA & pathFinder,
84  Array & centers)
85 {
86  using namespace acc;
87  typedef typename MultiArrayShape<N>::type Shape;
88  typedef typename Graph::Node Node;
89  typedef typename Graph::EdgeIt EdgeIt;
90  typedef float WeightType;
91 
92  typename Graph::template EdgeMap<WeightType> weights(g);
93  WeightType maxWeight = 0.0,
94  minWeight = N;
95  {
96  AccumulatorChainArray<CoupledArrays<N, WeightType, T>,
97  Select< DataArg<1>, LabelArg<2>, Maximum> > a;
98 
99  MultiArray<N, WeightType> distances(src.shape());
100  boundaryMultiDistance(src, distances, true);
101  extractFeatures(distances, src, a);
102  for (EdgeIt edge(g); edge != lemon::INVALID; ++edge)
103  {
104  const Node u(g.u(*edge)), v(g.v(*edge));
105  const T label = src[u];
106  if(label != src[v])
107  {
108  weights[*edge] = NumericTraits<WeightType>::max();
109  }
110  else
111  {
112  WeightType weight = norm(u - v) *
113  (get<Maximum>(a, label) + minWeight - 0.5*(distances[u] + distances[v]));
114  weights[*edge] = weight;
115  maxWeight = std::max(weight, maxWeight);
116  }
117  }
118  }
119  maxWeight *= src.size();
120 
121  T maxLabel = r.maxRegionLabel();
122  centers.resize(maxLabel+1);
123 
124  for (T i=0; i <= maxLabel; ++i)
125  {
126  if(get<Count>(r, i) == 0)
127  continue;
128  centers[i] = eccentricityCentersOneRegionImpl(pathFinder, weights, maxWeight,
129  get<RegionAnchor>(r, i),
130  get<Coord<Minimum> >(r, i),
131  get<Coord<Maximum> >(r, i) + Shape(1));
132  }
133 }
134 
135 /** \addtogroup MultiArrayDistanceTransform
136 */
137 //@{
138 
139  /** \brief Find the (approximate) eccentricity center in each region of a labeled image.
140 
141  <b> Declarations:</b>
142 
143  pass arbitrary-dimensional array views:
144  \code
145  namespace vigra {
146  template <unsigned int N, class T, class S, class Array>
147  void
148  eccentricityCenters(MultiArrayView<N, T, S> const & src,
149  Array & centers);
150  }
151  \endcode
152 
153  \param[in] src : labeled array
154  \param[out] centers : list of eccentricity centers (required interface:
155  <tt>centers[k] = TinyVector<int, N>()</tt> must be supported)
156 
157  <b> Usage:</b>
158 
159  <b>\#include</b> <vigra/eccentricitytransform.hxx><br/>
160  Namespace: vigra
161 
162  \code
163  Shape3 shape(width, height, depth);
164  MultiArray<3, UInt32> labels(shape);
165  ArrayVector<TinyVector<Int32, N> > centers;
166  ...
167 
168  eccentricityCenters(labels, centers);
169  \endcode
170  */
171 template <unsigned int N, class T, class S, class Array>
172 void
174  Array & centers)
175 {
176  using namespace acc;
177  typedef GridGraph<N> Graph;
178  typedef float WeightType;
179 
180  Graph g(src.shape(), IndirectNeighborhood);
182 
183  AccumulatorChainArray<CoupledArrays<N, T>,
184  Select< DataArg<1>, LabelArg<1>,
186  extractFeatures(src, a);
187 
188  eccentricityCentersImpl(src, g, a, pathFinder, centers);
189 }
190 
191  /** \brief Computes the (approximate) eccentricity transform on each region of a labeled image.
192 
193  <b> Declarations:</b>
194 
195  pass arbitrary-dimensional array views:
196  \code
197  namespace vigra {
198  // compute only the accentricity transform
199  template <unsigned int N, class T, class S>
200  void
201  eccentricityTransformOnLabels(MultiArrayView<N, T> const & src,
202  MultiArrayView<N, S> dest);
203 
204  // also return the eccentricity center of each region
205  template <unsigned int N, class T, class S, class Array>
206  void
207  eccentricityTransformOnLabels(MultiArrayView<N, T> const & src,
208  MultiArrayView<N, S> dest,
209  Array & centers);
210  }
211  \endcode
212 
213  \param[in] src : labeled array
214  \param[out] dest : eccentricity transform of src
215  \param[out] centers : (optional) list of eccentricity centers (required interface:
216  <tt>centers[k] = TinyVector<int, N>()</tt> must be supported)
217 
218  <b> Usage:</b>
219 
220  <b>\#include</b> <vigra/eccentricitytransform.hxx><br/>
221  Namespace: vigra
222 
223  \code
224  Shape3 shape(width, height, depth);
225  MultiArray<3, UInt32> labels(shape);
226  MultiArray<3, float> dest(shape);
227  ArrayVector<TinyVector<Int32, N> > centers;
228  ...
229 
230  eccentricityTransformOnLabels(labels, dest, centers);
231  \endcode
232  */
233 template <unsigned int N, class T, class S, class Array>
234 void
237  Array & centers)
238 {
239  using namespace acc;
240  typedef typename MultiArrayShape<N>::type Shape;
241  typedef GridGraph<N> Graph;
242  typedef typename Graph::Node Node;
243  typedef typename Graph::EdgeIt EdgeIt;
244  typedef float WeightType;
245 
246  vigra_precondition(src.shape() == dest.shape(),
247  "eccentricityTransformOnLabels(): Shape mismatch between src and dest.");
248 
249  Graph g(src.shape(), IndirectNeighborhood);
251 
252  using namespace acc;
253  AccumulatorChainArray<CoupledArrays<N, T>,
254  Select< DataArg<1>, LabelArg<1>,
256  extractFeatures(src, a);
257 
258  eccentricityCentersImpl(src, g, a, pathFinder, centers);
259 
260  typename Graph::template EdgeMap<WeightType> weights(g);
261  for (EdgeIt edge(g); edge != lemon::INVALID; ++edge)
262  {
263  const Node u(g.u(*edge)), v(g.v(*edge));
264  const T label = src[u];
265  if(label != src[v])
266  weights[*edge] = NumericTraits<WeightType>::max();
267  else
268  weights[*edge] = norm(u - v);
269  }
270  ArrayVector<Shape> filtered_centers;
271  for (T i=0; i <= a.maxRegionLabel(); ++i)
272  if(get<Count>(a, i) > 0)
273  filtered_centers.push_back(centers[i]);
274  pathFinder.runMultiSource(weights, filtered_centers.begin(), filtered_centers.end());
275  dest = pathFinder.distances();
276 }
277 
278 template <unsigned int N, class T, class S>
279 inline void
280 eccentricityTransformOnLabels(MultiArrayView<N, T> const & src,
281  MultiArrayView<N, S> dest)
282 {
283  ArrayVector<TinyVector<MultiArrayIndex, N> > centers;
284  eccentricityTransformOnLabels(src, dest, centers);
285 }
286 
287 //@}
288 
289 } // namespace vigra
290 
291 
292 #endif // VIGRA_ECCENTRICITYTRANSFORM_HXX

© 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.10.0 (Thu Jan 8 2015)