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

eccentricitytransform.hxx
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
56 template <class Graph, class WeightType,
57 class EdgeMap, class Shape>
58 TinyVector<MultiArrayIndex, Shape::static_size>
59eccentricityCentersOneRegionImpl(ShortestPathDijkstra<Graph, WeightType> & pathFinder,
60 const EdgeMap & weights, WeightType maxWeight,
61 Shape anchor, Shape const & start, Shape const & stop)
62{
63 int maxIterations = 4;
64 for(int k=0; k < maxIterations; ++k)
65 {
66 pathFinder.run(start, stop, weights, anchor, lemon::INVALID, maxWeight);
67 anchor = pathFinder.target();
68 // FIXME: implement early stopping when source and target don't change anymore
69 }
70
71 Polygon<TinyVector<float, Shape::static_size> > path;
72 path.push_back_unsafe(anchor);
73 while(pathFinder.predecessors()[path.back()] != path.back())
74 path.push_back_unsafe(pathFinder.predecessors()[path.back()]);
75 return path[roundi(path.arcLengthQuantile(0.5))];
76}
77
78 template <unsigned int N, class T, class S, class Graph,
79 class ACCUMULATOR, class DIJKSTRA, class Array>
80 void
81eccentricityCentersImpl(const MultiArrayView<N, T, S> & src,
82 Graph const & g,
83 ACCUMULATOR const & r,
84 DIJKSTRA & pathFinder,
85 Array & centers)
86{
87 using namespace acc;
88 typedef typename MultiArrayShape<N>::type Shape;
89 typedef typename Graph::Node Node;
90 typedef typename Graph::EdgeIt EdgeIt;
91 typedef float WeightType;
92
93 typename Graph::template EdgeMap<WeightType> weights(g);
94 WeightType maxWeight = 0.0,
95 minWeight = N;
96 {
97 AccumulatorChainArray<CoupledArrays<N, WeightType, T>,
98 Select< DataArg<1>, LabelArg<2>, Maximum> > a;
99
100 MultiArray<N, WeightType> distances(src.shape());
101 boundaryMultiDistance(src, distances, true);
102 extractFeatures(distances, src, a);
103 for (EdgeIt edge(g); edge != lemon::INVALID; ++edge)
104 {
105 const Node u(g.u(*edge)), v(g.v(*edge));
106 const T label = src[u];
107 if(label != src[v])
108 {
109 weights[*edge] = NumericTraits<WeightType>::max();
110 }
111 else
112 {
113 WeightType weight = norm(u - v) *
114 (get<Maximum>(a, label) + minWeight - 0.5*(distances[u] + distances[v]));
115 weights[*edge] = weight;
116 maxWeight = std::max(weight, maxWeight);
117 }
118 }
119 }
120 maxWeight *= src.size();
121
122 T maxLabel = r.maxRegionLabel();
123 centers.resize(maxLabel+1);
124
125 for (T i=0; i <= maxLabel; ++i)
126 {
127 if(get<Count>(r, i) == 0)
128 continue;
129 centers[i] = eccentricityCentersOneRegionImpl(pathFinder, weights, maxWeight,
130 get<RegionAnchor>(r, i),
131 get<Coord<Minimum> >(r, i),
132 get<Coord<Maximum> >(r, i) + Shape(1));
133 }
134}
135
136/** \addtogroup DistanceTransform
137*/
138//@{
139
140 /** \brief Find the (approximate) eccentricity center in each region of a labeled image.
141
142 <b> Declarations:</b>
143
144 pass arbitrary-dimensional array views:
145 \code
146 namespace vigra {
147 template <unsigned int N, class T, class S, class Array>
148 void
149 eccentricityCenters(MultiArrayView<N, T, S> const & src,
150 Array & centers);
151 }
152 \endcode
153
154 \param[in] src : labeled array
155 \param[out] centers : list of eccentricity centers (required interface:
156 <tt>centers[k] = TinyVector<int, N>()</tt> must be supported)
157
158 <b> Usage:</b>
159
160 <b>\#include</b> <vigra/eccentricitytransform.hxx><br/>
161 Namespace: vigra
162
163 \code
164 Shape3 shape(width, height, depth);
165 MultiArray<3, UInt32> labels(shape);
166 ArrayVector<TinyVector<Int32, N> > centers;
167 ...
168
169 eccentricityCenters(labels, centers);
170 \endcode
171 */
172 template <unsigned int N, class T, class S, class Array>
173 void
174 eccentricityCenters(const MultiArrayView<N, T, S> & src,
175 Array & centers)
176{
177 using namespace acc;
178 typedef GridGraph<N> Graph;
179 typedef float WeightType;
180
181 Graph g(src.shape(), IndirectNeighborhood);
182 ShortestPathDijkstra<Graph, WeightType> pathFinder(g);
183
184 AccumulatorChainArray<CoupledArrays<N, T>,
185 Select< DataArg<1>, LabelArg<1>,
186 Count, BoundingBox, RegionAnchor> > a;
187 extractFeatures(src, a);
188
189 eccentricityCentersImpl(src, g, a, pathFinder, centers);
190}
191
192 /** \brief Computes the (approximate) eccentricity transform on each region of a labeled image.
193
194 <b> Declarations:</b>
195
196 pass arbitrary-dimensional array views:
197 \code
198 namespace vigra {
199 // compute only the accentricity transform
200 template <unsigned int N, class T, class S>
201 void
202 eccentricityTransformOnLabels(MultiArrayView<N, T> const & src,
203 MultiArrayView<N, S> dest);
204
205 // also return the eccentricity center of each region
206 template <unsigned int N, class T, class S, class Array>
207 void
208 eccentricityTransformOnLabels(MultiArrayView<N, T> const & src,
209 MultiArrayView<N, S> dest,
210 Array & centers);
211 }
212 \endcode
213
214 \param[in] src : labeled array
215 \param[out] dest : eccentricity transform of src
216 \param[out] centers : (optional) list of eccentricity centers (required interface:
217 <tt>centers[k] = TinyVector<int, N>()</tt> must be supported)
218
219 <b> Usage:</b>
220
221 <b>\#include</b> <vigra/eccentricitytransform.hxx><br/>
222 Namespace: vigra
223
224 \code
225 Shape3 shape(width, height, depth);
226 MultiArray<3, UInt32> labels(shape);
227 MultiArray<3, float> dest(shape);
228 ArrayVector<TinyVector<Int32, N> > centers;
229 ...
230
231 eccentricityTransformOnLabels(labels, dest, centers);
232 \endcode
233 */
234 template <unsigned int N, class T, class S, class Array>
235 void
236 eccentricityTransformOnLabels(MultiArrayView<N, T> const & src,
237 MultiArrayView<N, S> dest,
238 Array & centers)
239{
240 using namespace acc;
241 typedef typename MultiArrayShape<N>::type Shape;
242 typedef GridGraph<N> Graph;
243 typedef typename Graph::Node Node;
244 typedef typename Graph::EdgeIt EdgeIt;
245 typedef float WeightType;
246
247 vigra_precondition(src.shape() == dest.shape(),
248 "eccentricityTransformOnLabels(): Shape mismatch between src and dest.");
249
250 Graph g(src.shape(), IndirectNeighborhood);
251 ShortestPathDijkstra<Graph, WeightType> pathFinder(g);
252
253 using namespace acc;
254 AccumulatorChainArray<CoupledArrays<N, T>,
255 Select< DataArg<1>, LabelArg<1>,
256 Count, BoundingBox, RegionAnchor> > a;
257 extractFeatures(src, a);
258
259 eccentricityCentersImpl(src, g, a, pathFinder, centers);
260
261 typename Graph::template EdgeMap<WeightType> weights(g);
262 for (EdgeIt edge(g); edge != lemon::INVALID; ++edge)
263 {
264 const Node u(g.u(*edge)), v(g.v(*edge));
265 const T label = src[u];
266 if(label != src[v])
267 weights[*edge] = NumericTraits<WeightType>::max();
268 else
269 weights[*edge] = norm(u - v);
270 }
271 ArrayVector<Shape> filtered_centers;
272 for (T i=0; i <= a.maxRegionLabel(); ++i)
273 if(get<Count>(a, i) > 0)
274 filtered_centers.push_back(centers[i]);
275 pathFinder.runMultiSource(weights, filtered_centers.begin(), filtered_centers.end());
276 dest = pathFinder.distances();
277}
278
279 template <unsigned int N, class T, class S>
280 inline void
281 eccentricityTransformOnLabels(MultiArrayView<N, T> const & src,
282 MultiArrayView<N, S> dest)
283{
284 ArrayVector<TinyVector<MultiArrayIndex, N> > centers;
285 eccentricityTransformOnLabels(src, dest, centers);
286}
287
288//@}
289
290} // namespace vigra
291
292
293#endif // VIGRA_ECCENTRICITYTRANSFORM_HXX
vigra::ArrayVectorView::begin
const_iterator begin() const
Definition array_vector.hxx:223
vigra::ArrayVectorView::end
const_iterator end() const
Definition array_vector.hxx:237
vigra::ArrayVector
Definition array_vector.hxx:514
vigra::GridGraph
Define a grid graph in arbitrary dimensions.
Definition multi_gridgraph.hxx:1429
vigra::MultiArrayShape::type
TinyVector< MultiArrayIndex, N > type
Definition multi_shape.hxx:272
vigra::MultiArrayView
Base class for, and view to, MultiArray.
Definition multi_array.hxx:705
vigra::MultiArrayView::shape
const difference_type & shape() const
Definition multi_array.hxx:1650
vigra::MultiArray
Main MultiArray class containing the memory management.
Definition multi_array.hxx:2483
vigra::Polygon
Definition polygon.hxx:80
vigra::ShortestPathDijkstra
shortest path computer
Definition graph_algorithms.hxx:297
vigra::ShortestPathDijkstra::runMultiSource
void runMultiSource(const WEIGHTS &weights, ITER source_begin, ITER source_end, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
run shortest path with given edge weights from multiple sources.
Definition graph_algorithms.hxx:391
vigra::ShortestPathDijkstra::distances
const DistanceMap & distances() const
get the distances node map (after a call of run)
Definition graph_algorithms.hxx:447
vigra::TinyVector
Class for fixed size vectors.
Definition tinyvector.hxx:1008
vigra::acc
Efficient computation of object statistics.
Definition accumulator-grammar.hxx:48
vigra::acc::extractFeatures
void extractFeatures(...)
vigra
vigra::eccentricityCenters
void eccentricityCenters(const MultiArrayView< N, T, S > &src, Array &centers)
Find the (approximate) eccentricity center in each region of a labeled image.
Definition eccentricitytransform.hxx:174
vigra::boundaryMultiDistance
void boundaryMultiDistance(...)
Euclidean distance to the implicit boundaries of a multi-dimensional label array.
vigra::norm
FFTWComplex< R >::NormType norm(const FFTWComplex< R > &a)
norm (= magnitude)
Definition fftw3.hxx:1037
vigra::roundi
Int32 roundi(FixedPoint16< IntBits, OverflowHandling > v)
rounding to the nearest integer.
Definition fixedpoint.hxx:1775
vigra::IndirectNeighborhood
@ IndirectNeighborhood
use direct and indirect neighbors
Definition multi_fwd.hxx:188
vigra::eccentricityTransformOnLabels
void eccentricityTransformOnLabels(MultiArrayView< N, T > const &src, MultiArrayView< N, S > dest, Array &centers)
Computes the (approximate) eccentricity transform on each region of a labeled image.
Definition eccentricitytransform.hxx:236

© 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.12.4