37 #ifndef VIGRA_DISTANCETRANSFORM_HXX
38 #define VIGRA_DISTANCETRANSFORM_HXX
41 #include "stdimage.hxx"
42 #include "multi_shape.hxx"
53 struct InternalDistanceTransformLInifinityNormFunctor
55 float operator()(
float dx,
float dy)
const
57 return (dx < dy) ? dy : dx;
62 struct InternalDistanceTransformL1NormFunctor
64 float operator()(
float dx,
float dy)
const
71 struct InternalDistanceTransformL2NormFunctor
73 float operator()(
float dx,
float dy)
const
80 template <
class SrcImageIterator,
class SrcAccessor,
81 class DestImageIterator,
class DestAccessor,
82 class ValueType,
class NormFunctor>
84 internalDistanceTransform(SrcImageIterator src_upperleft,
85 SrcImageIterator src_lowerright, SrcAccessor sa,
86 DestImageIterator dest_upperleft, DestAccessor da,
87 ValueType background, NormFunctor
norm)
89 int w = src_lowerright.x - src_upperleft.x;
90 int h = src_lowerright.y - src_upperleft.y;
92 FImage xdist(w,h), ydist(w,h);
97 SrcImageIterator sy = src_upperleft;
98 DestImageIterator ry = dest_upperleft;
101 SrcImageIterator sx = sy;
102 DestImageIterator rx = ry;
106 const Diff2D left(-1, 0);
107 const Diff2D right(1, 0);
108 const Diff2D top(0, -1);
109 const Diff2D bottom(0, 1);
112 if(sa(sx) != background)
120 da.set(
norm(*xdx, *ydx), rx);
124 for(x=1, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x;
126 ++x, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x)
128 if(sa(sx) != background)
136 *xdx = xdx[left] + 1.0f;
138 da.set(
norm(*xdx, *ydx), rx);
141 for(x=w-2, xdx.x -= 2, ydx.x -= 2, sx.x -= 2, rx.x -= 2;
143 --x, --xdx.x, --ydx.x, --sx.x, --rx.x)
145 float d =
norm(xdx[right] + 1.0f, ydx[right]);
147 if(da(rx) < d)
continue;
149 *xdx = xdx[right] + 1.0f;
153 for(y=1, ++xdy.y, ++ydy.y, ++sy.y, ++ry.y;
155 ++y, ++xdy.y, ++ydy.y, ++sy.y, ++ry.y)
162 if(sa(sx) != background)
171 *ydx = ydx[top] + 1.0f;
172 da.set(
norm(*xdx, *ydx), rx);
175 for(x=1, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x;
177 ++x, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x)
179 if(sa(sx) != background)
187 float d1 =
norm(xdx[left] + 1.0f, ydx[left]);
188 float d2 =
norm(xdx[top], ydx[top] + 1.0f);
192 *xdx = xdx[left] + 1.0f;
199 *ydx = ydx[top] + 1.0f;
204 for(x=w-2, xdx.x -= 2, ydx.x -= 2, sx.x -= 2, rx.x -= 2;
206 --x, --xdx.x, --ydx.x, --sx.x, --rx.x)
208 float d1 =
norm(xdx[right] + 1.0f, ydx[right]);
210 if(da(rx) < d1)
continue;
212 *xdx = xdx[right] + 1.0f;
217 for(y=h-2, xdy.y -= 2, ydy.y -= 2, sy.y -= 2, ry.y -= 2;
219 --y, --xdy.y, --ydy.y, --sy.y, --ry.y)
226 float d =
norm(xdx[bottom], ydx[bottom] + 1.0f);
230 *ydx = ydx[bottom] + 1.0f;
234 for(x=1, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x;
236 ++x, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x)
238 float d1 =
norm(xdx[left] + 1.0f, ydx[left]);
239 float d2 =
norm(xdx[bottom], ydx[bottom] + 1.0f);
243 if(da(rx) < d1)
continue;
244 *xdx = xdx[left] + 1.0f;
250 if(da(rx) < d2)
continue;
252 *ydx = ydx[bottom] + 1.0f;
256 for(x=w-2, xdx.x -= 2, ydx.x -= 2, sx.x -= 2, rx.x -= 2;
258 --x, --xdx.x, --ydx.x, --sx.x, --rx.x)
260 float d1 =
norm(xdx[right] + 1.0f, ydx[right]);
262 if(da(rx) < d1)
continue;
263 *xdx = xdx[right] + 1.0f;
400 template <
class SrcImageIterator,
class SrcAccessor,
401 class DestImageIterator,
class DestAccessor,
405 SrcImageIterator src_lowerright, SrcAccessor sa,
406 DestImageIterator dest_upperleft, DestAccessor da,
407 ValueType background,
int norm)
411 internalDistanceTransform(src_upperleft, src_lowerright, sa,
412 dest_upperleft, da, background,
413 InternalDistanceTransformL1NormFunctor());
417 internalDistanceTransform(src_upperleft, src_lowerright, sa,
418 dest_upperleft, da, background,
419 InternalDistanceTransformL2NormFunctor());
423 internalDistanceTransform(src_upperleft, src_lowerright, sa,
424 dest_upperleft, da, background,
425 InternalDistanceTransformLInifinityNormFunctor());
429 template <
class SrcImageIterator,
class SrcAccessor,
430 class DestImageIterator,
class DestAccessor,
434 pair<DestImageIterator, DestAccessor> dest,
435 ValueType background,
int norm)
438 dest.first, dest.second, background, norm);
441 template <
class T1,
class S1,
446 MultiArrayView<2, T2, S2> dest,
447 ValueType background,
int norm)
449 vigra_precondition(src.shape() == dest.shape(),
450 "distanceTransform(): shape mismatch between input and output.");
452 destImage(dest), background, norm);
459 #endif // VIGRA_DISTANCETRANSFORM_HXX
BasicImage< float > FImage
Definition: stdimage.hxx:143
FFTWComplex< R >::NormType norm(const FFTWComplex< R > &a)
norm (= magnitude)
Definition: fftw3.hxx:1037
BasicImageIterator< float, float ** > Iterator
Definition: basicimage.hxx:532
doxygen_overloaded_function(template<...> void separableConvolveBlockwise) template< unsigned int N
Separated convolution on ChunkedArrays.
SquareRootTraits< FixedPoint< IntBits, FracBits > >::SquareRootResult sqrt(FixedPoint< IntBits, FracBits > v)
square root.
Definition: fixedpoint.hxx:616
float value_type
Definition: basicimage.hxx:481