37#ifndef VIGRA_ECCENTRICITYTRANSFORM_HXX
38#define VIGRA_ECCENTRICITYTRANSFORM_HXX
45#include "accumulator.hxx"
46#include "multi_labeling.hxx"
47#include "multi_distance.hxx"
48#include "multi_resize.hxx"
49#include "graph_algorithms.hxx"
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)
63 int maxIterations = 4;
64 for(
int k=0; k < maxIterations; ++k)
66 pathFinder.run(start, stop, weights, anchor, lemon::INVALID, maxWeight);
67 anchor = pathFinder.target();
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))];
78template <
unsigned int N,
class T,
class S,
class Graph,
79 class ACCUMULATOR,
class DIJKSTRA,
class Array>
81eccentricityCentersImpl(
const MultiArrayView<N, T, S> & src,
83 ACCUMULATOR
const & r,
84 DIJKSTRA & pathFinder,
89 typedef typename Graph::Node Node;
90 typedef typename Graph::EdgeIt EdgeIt;
91 typedef float WeightType;
93 typename Graph::template EdgeMap<WeightType> weights(g);
94 WeightType maxWeight = 0.0,
97 AccumulatorChainArray<CoupledArrays<N, WeightType, T>,
98 Select< DataArg<1>, LabelArg<2>, Maximum> > a;
100 MultiArray<N, WeightType> distances(src.shape());
103 for (EdgeIt edge(g); edge != lemon::INVALID; ++edge)
105 const Node u(g.u(*edge)), v(g.v(*edge));
106 const T label = src[u];
109 weights[*edge] = NumericTraits<WeightType>::max();
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);
120 maxWeight *= src.size();
122 T maxLabel = r.maxRegionLabel();
123 centers.resize(maxLabel+1);
125 for (T i=0; i <= maxLabel; ++i)
127 if(get<Count>(r, i) == 0)
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));
172template <
unsigned int N,
class T,
class S,
class Array>
179 typedef float WeightType;
184 AccumulatorChainArray<CoupledArrays<N, T>,
185 Select< DataArg<1>, LabelArg<1>,
186 Count, BoundingBox, RegionAnchor> > a;
187 extractFeatures(src, a);
189 eccentricityCentersImpl(src, g, a, pathFinder, centers);
234template <
unsigned int N,
class T,
class S,
class Array>
243 typedef typename Graph::Node Node;
244 typedef typename Graph::EdgeIt EdgeIt;
245 typedef float WeightType;
247 vigra_precondition(src.
shape() == dest.
shape(),
248 "eccentricityTransformOnLabels(): Shape mismatch between src and dest.");
254 AccumulatorChainArray<CoupledArrays<N, T>,
255 Select< DataArg<1>, LabelArg<1>,
256 Count, BoundingBox, RegionAnchor> > a;
257 extractFeatures(src, a);
259 eccentricityCentersImpl(src, g, a, pathFinder, centers);
261 typename Graph::template EdgeMap<WeightType> weights(g);
262 for (EdgeIt edge(g); edge != lemon::INVALID; ++edge)
264 const Node u(g.u(*edge)), v(g.v(*edge));
265 const T label = src[u];
267 weights[*edge] = NumericTraits<WeightType>::max();
269 weights[*edge] =
norm(u - v);
272 for (T i=0; i <= a.maxRegionLabel(); ++i)
273 if(get<Count>(a, i) > 0)
274 filtered_centers.push_back(centers[i]);
279template <
unsigned int N,
class T,
class S>
282 MultiArrayView<N, S> dest)
284 ArrayVector<TinyVector<MultiArrayIndex, N> > centers;
const_iterator begin() const
Definition: array_vector.hxx:223
const_iterator end() const
Definition: array_vector.hxx:237
Definition: array_vector.hxx:514
Define a grid graph in arbitrary dimensions.
Definition: multi_gridgraph.hxx:1429
TinyVector< MultiArrayIndex, N > type
Definition: multi_shape.hxx:272
const difference_type & shape() const
Definition: multi_array.hxx:1648
shortest path computer
Definition: graph_algorithms.hxx:297
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
const DistanceMap & distances() const
get the distances node map (after a call of run)
Definition: graph_algorithms.hxx:447
Class for fixed size vectors.
Definition: tinyvector.hxx:1008
void extractFeatures(...)
void eccentricityCenters(const MultiArrayView< N, T, S > &src, Array ¢ers)
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 ¢ers)
Computes the (approximate) eccentricity transform on each region of a labeled image.
Definition: eccentricitytransform.hxx:236