[ 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
52namespace vigra
53{
54
55
56template <class Graph, class WeightType,
57 class EdgeMap, class Shape>
58TinyVector<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
78template <unsigned int N, class T, class S, class Graph,
79 class ACCUMULATOR, class DIJKSTRA, class Array>
80void
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 */
172template <unsigned int N, class T, class S, class Array>
173void
175 Array & centers)
176{
177 using namespace acc;
178 typedef GridGraph<N> Graph;
179 typedef float WeightType;
180
181 Graph g(src.shape(), IndirectNeighborhood);
183
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 */
234template <unsigned int N, class T, class S, class Array>
235void
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);
252
253 using namespace acc;
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 }
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
279template <unsigned int N, class T, class S>
280inline void
281eccentricityTransformOnLabels(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
TinyVector< MultiArrayIndex, N > type
Definition multi_shape.hxx:272
Class for a single RGB value.
Definition rgbvalue.hxx:128
iterator end()
Definition tinyvector.hxx:864
iterator begin()
Definition tinyvector.hxx:861
Class for fixed size vectors.
Definition tinyvector.hxx:1008
void extractFeatures(...)
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
void boundaryMultiDistance(...)
Euclidean distance to the implicit boundaries of a multi-dimensional label array.
FFTWComplex< R >::NormType norm(const FFTWComplex< R > &a)
norm (= magnitude)
Definition fftw3.hxx:1037
Int32 roundi(FixedPoint16< IntBits, OverflowHandling > v)
rounding to the nearest integer.
Definition fixedpoint.hxx:1775
@ IndirectNeighborhood
use direct and indirect neighbors
Definition multi_fwd.hxx:188
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.2