37 #ifndef VIGRA_DISTANCETRANSFORM_HXX
38 #define VIGRA_DISTANCETRANSFORM_HXX
41 #include "stdimage.hxx"
52 struct InternalDistanceTransformLInifinityNormFunctor
54 float operator()(
float dx,
float dy)
const
56 return (dx < dy) ? dy : dx;
61 struct InternalDistanceTransformL1NormFunctor
63 float operator()(
float dx,
float dy)
const
70 struct InternalDistanceTransformL2NormFunctor
72 float operator()(
float dx,
float dy)
const
79 template <
class SrcImageIterator,
class SrcAccessor,
80 class DestImageIterator,
class DestAccessor,
81 class ValueType,
class NormFunctor>
83 internalDistanceTransform(SrcImageIterator src_upperleft,
84 SrcImageIterator src_lowerright, SrcAccessor sa,
85 DestImageIterator dest_upperleft, DestAccessor da,
86 ValueType background, NormFunctor
norm)
88 int w = src_lowerright.x - src_upperleft.x;
89 int h = src_lowerright.y - src_upperleft.y;
91 FImage xdist(w,h), ydist(w,h);
96 SrcImageIterator sy = src_upperleft;
97 DestImageIterator ry = dest_upperleft;
100 SrcImageIterator sx = sy;
101 DestImageIterator rx = ry;
105 static const Diff2D left(-1, 0);
106 static const Diff2D right(1, 0);
107 static const Diff2D top(0, -1);
108 static const Diff2D bottom(0, 1);
111 if(sa(sx) != background)
119 da.set(
norm(*xdx, *ydx), rx);
123 for(x=1, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x;
125 ++x, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x)
127 if(sa(sx) != background)
135 *xdx = xdx[left] + 1.0f;
137 da.set(
norm(*xdx, *ydx), rx);
140 for(x=w-2, xdx.x -= 2, ydx.x -= 2, sx.x -= 2, rx.x -= 2;
142 --x, --xdx.x, --ydx.x, --sx.x, --rx.x)
144 float d =
norm(xdx[right] + 1.0f, ydx[right]);
146 if(da(rx) < d)
continue;
148 *xdx = xdx[right] + 1.0f;
152 for(y=1, ++xdy.y, ++ydy.y, ++sy.y, ++ry.y;
154 ++y, ++xdy.y, ++ydy.y, ++sy.y, ++ry.y)
161 if(sa(sx) != background)
170 *ydx = ydx[top] + 1.0f;
171 da.set(
norm(*xdx, *ydx), rx);
174 for(x=1, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x;
176 ++x, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x)
178 if(sa(sx) != background)
186 float d1 =
norm(xdx[left] + 1.0f, ydx[left]);
187 float d2 =
norm(xdx[top], ydx[top] + 1.0f);
191 *xdx = xdx[left] + 1.0f;
198 *ydx = ydx[top] + 1.0f;
203 for(x=w-2, xdx.x -= 2, ydx.x -= 2, sx.x -= 2, rx.x -= 2;
205 --x, --xdx.x, --ydx.x, --sx.x, --rx.x)
207 float d1 =
norm(xdx[right] + 1.0f, ydx[right]);
209 if(da(rx) < d1)
continue;
211 *xdx = xdx[right] + 1.0f;
216 for(y=h-2, xdy.y -= 2, ydy.y -= 2, sy.y -= 2, ry.y -= 2;
218 --y, --xdy.y, --ydy.y, --sy.y, --ry.y)
225 float d =
norm(xdx[bottom], ydx[bottom] + 1.0f);
229 *ydx = ydx[bottom] + 1.0f;
233 for(x=1, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x;
235 ++x, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x)
237 float d1 =
norm(xdx[left] + 1.0f, ydx[left]);
238 float d2 =
norm(xdx[bottom], ydx[bottom] + 1.0f);
242 if(da(rx) < d1)
continue;
243 *xdx = xdx[left] + 1.0f;
249 if(da(rx) < d2)
continue;
251 *ydx = ydx[bottom] + 1.0f;
255 for(x=w-2, xdx.x -= 2, ydx.x -= 2, sx.x -= 2, rx.x -= 2;
257 --x, --xdx.x, --ydx.x, --sx.x, --rx.x)
259 float d1 =
norm(xdx[right] + 1.0f, ydx[right]);
261 if(da(rx) < d1)
continue;
262 *xdx = xdx[right] + 1.0f;
379 template <
class SrcImageIterator,
class SrcAccessor,
380 class DestImageIterator,
class DestAccessor,
384 SrcImageIterator src_lowerright, SrcAccessor sa,
385 DestImageIterator dest_upperleft, DestAccessor da,
386 ValueType background,
int norm)
390 internalDistanceTransform(src_upperleft, src_lowerright, sa,
391 dest_upperleft, da, background,
392 InternalDistanceTransformL1NormFunctor());
396 internalDistanceTransform(src_upperleft, src_lowerright, sa,
397 dest_upperleft, da, background,
398 InternalDistanceTransformL2NormFunctor());
402 internalDistanceTransform(src_upperleft, src_lowerright, sa,
403 dest_upperleft, da, background,
404 InternalDistanceTransformLInifinityNormFunctor());
408 template <
class SrcImageIterator,
class SrcAccessor,
409 class DestImageIterator,
class DestAccessor,
413 triple<SrcImageIterator, SrcImageIterator, SrcAccessor> src,
414 pair<DestImageIterator, DestAccessor> dest,
415 ValueType background,
int norm)
418 dest.first, dest.second, background, norm);
425 #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< PIXELTYPE, PIXELTYPE ** > Iterator
Definition: basicimage.hxx:530
SquareRootTraits< FixedPoint< IntBits, FracBits > >::SquareRootResult sqrt(FixedPoint< IntBits, FracBits > v)
square root.
Definition: fixedpoint.hxx:616
PIXELTYPE value_type
Definition: basicimage.hxx:479