[ VIGRA Homepage | Class Index | Function Index | File Index | Main Page ]
![]() |
vigra/distancetransform.hxx | ![]() |
---|
00001 /************************************************************************/ 00002 /* */ 00003 /* Copyright 1998-2002 by Ullrich Koethe */ 00004 /* Cognitive Systems Group, University of Hamburg, Germany */ 00005 /* */ 00006 /* This file is part of the VIGRA computer vision library. */ 00007 /* ( Version 1.2.0, Aug 07 2003 ) */ 00008 /* You may use, modify, and distribute this software according */ 00009 /* to the terms stated in the LICENSE file included in */ 00010 /* the VIGRA distribution. */ 00011 /* */ 00012 /* The VIGRA Website is */ 00013 /* http://kogs-www.informatik.uni-hamburg.de/~koethe/vigra/ */ 00014 /* Please direct questions, bug reports, and contributions to */ 00015 /* koethe@informatik.uni-hamburg.de */ 00016 /* */ 00017 /* THIS SOFTWARE IS PROVIDED AS IS AND WITHOUT ANY EXPRESS OR */ 00018 /* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ 00019 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. */ 00020 /* */ 00021 /************************************************************************/ 00022 00023 00024 #ifndef VIGRA_DISTANCETRANSFORM_HXX 00025 #define VIGRA_DISTANCETRANSFORM_HXX 00026 00027 #include <cmath> 00028 #include "vigra/stdimage.hxx" 00029 00030 namespace vigra { 00031 00032 /* 00033 * functors to determine the distance norm 00034 * these functors assume that dx and dy are positive 00035 * (this is OK for use in internalDistanceTransform()) 00036 */ 00037 00038 // chessboard metric 00039 struct InternalDistanceTransformLInifinityNormFunctor 00040 { 00041 float operator()(float dx, float dy) const 00042 { 00043 return (dx < dy) ? dy : dx; 00044 } 00045 }; 00046 00047 // Manhattan metric 00048 struct InternalDistanceTransformL1NormFunctor 00049 { 00050 float operator()(float dx, float dy) const 00051 { 00052 return dx + dy; 00053 } 00054 }; 00055 00056 // Euclidean metric 00057 struct InternalDistanceTransformL2NormFunctor 00058 { 00059 float operator()(float dx, float dy) const 00060 { 00061 return VIGRA_CSTD::sqrt(dx*dx + dy*dy); 00062 } 00063 }; 00064 00065 00066 template <class SrcImageIterator, class SrcAccessor, 00067 class DestImageIterator, class DestAccessor, 00068 class ValueType, class NormFunctor> 00069 void 00070 internalDistanceTransform(SrcImageIterator src_upperleft, 00071 SrcImageIterator src_lowerright, SrcAccessor sa, 00072 DestImageIterator dest_upperleft, DestAccessor da, 00073 ValueType background, NormFunctor norm) 00074 { 00075 int w = src_lowerright.x - src_upperleft.x; 00076 int h = src_lowerright.y - src_upperleft.y; 00077 00078 FImage xdist(w,h), ydist(w,h); 00079 00080 xdist = w; // init x and 00081 ydist = h; // y distances with 'large' values 00082 00083 SrcImageIterator sy = src_upperleft; 00084 DestImageIterator ry = dest_upperleft; 00085 FImage::Iterator xdy = xdist.upperLeft(); 00086 FImage::Iterator ydy = ydist.upperLeft(); 00087 SrcImageIterator sx = sy; 00088 DestImageIterator rx = ry; 00089 FImage::Iterator xdx = xdy; 00090 FImage::Iterator ydx = ydy; 00091 00092 static const Diff2D left(-1, 0); 00093 static const Diff2D right(1, 0); 00094 static const Diff2D top(0, -1); 00095 static const Diff2D bottom(0, 1); 00096 00097 int x,y; 00098 if(sa(sx) != background) // first pixel 00099 { 00100 *xdx = 0.0; 00101 *ydx = 0.0; 00102 da.set(0.0, rx); 00103 } 00104 else 00105 { 00106 da.set(norm(*xdx, *ydx), rx); 00107 } 00108 00109 00110 for(x=1, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x; 00111 x<w; 00112 ++x, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x) // first row left to right 00113 { 00114 if(sa(sx) != background) 00115 { 00116 *xdx = 0.0; 00117 *ydx = 0.0; 00118 da.set(0.0, rx); 00119 } 00120 else 00121 { 00122 *xdx = xdx[left] + 1.0; // propagate x and 00123 *ydx = ydx[left]; // y components of distance from left pixel 00124 da.set(norm(*xdx, *ydx), rx); // calculate distance from x and y components 00125 } 00126 } 00127 for(x=w-2, xdx.x -= 2, ydx.x -= 2, sx.x -= 2, rx.x -= 2; 00128 x>=0; 00129 --x, --xdx.x, --ydx.x, --sx.x, --rx.x) // first row right to left 00130 { 00131 float d = norm(xdx[right] + 1.0, ydx[right]); 00132 00133 if(da(rx) < d) continue; 00134 00135 *xdx = xdx[right] + 1.0; 00136 *ydx = ydx[right]; 00137 da.set(d, rx); 00138 } 00139 for(y=1, ++xdy.y, ++ydy.y, ++sy.y, ++ry.y; 00140 y<h; 00141 ++y, ++xdy.y, ++ydy.y, ++sy.y, ++ry.y) // top to bottom 00142 { 00143 sx = sy; 00144 rx = ry; 00145 xdx = xdy; 00146 ydx = ydy; 00147 00148 if(sa(sx) != background) // first pixel of current row 00149 { 00150 *xdx = 0.0; 00151 *ydx = 0.0; 00152 da.set(0.0, rx); 00153 } 00154 else 00155 { 00156 *xdx = xdx[top]; 00157 *ydx = ydx[top] + 1.0; 00158 da.set(norm(*xdx, *ydx), rx); 00159 } 00160 00161 for(x=1, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x; 00162 x<w; 00163 ++x, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x) // current row left to right 00164 { 00165 if(sa(sx) != background) 00166 { 00167 *xdx = 0.0; 00168 *ydx = 0.0; 00169 da.set(0.0, rx); 00170 } 00171 else 00172 { 00173 float d1 = norm(xdx[left] + 1.0, ydx[left]); 00174 float d2 = norm(xdx[top], ydx[top] + 1.0); 00175 00176 if(d1 < d2) 00177 { 00178 *xdx = xdx[left] + 1.0; 00179 *ydx = ydx[left]; 00180 da.set(d1, rx); 00181 } 00182 else 00183 { 00184 *xdx = xdx[top]; 00185 *ydx = ydx[top] + 1.0; 00186 da.set(d2, rx); 00187 } 00188 } 00189 } 00190 for(x=w-2, xdx.x -= 2, ydx.x -= 2, sx.x -= 2, rx.x -= 2; 00191 x>=0; 00192 --x, --xdx.x, --ydx.x, --sx.x, --rx.x) // current row right to left 00193 { 00194 float d1 = norm(xdx[right] + 1.0, ydx[right]); 00195 00196 if(da(rx) < d1) continue; 00197 00198 *xdx = xdx[right] + 1.0; 00199 *ydx = ydx[right]; 00200 da.set(d1, rx); 00201 } 00202 } 00203 for(y=h-2, xdy.y -= 2, ydy.y -= 2, sy.y -= 2, ry.y -= 2; 00204 y>=0; 00205 --y, --xdy.y, --ydy.y, --sy.y, --ry.y) // bottom to top 00206 { 00207 sx = sy; 00208 rx = ry; 00209 xdx = xdy; 00210 ydx = ydy; 00211 00212 float d = norm(xdx[bottom], ydx[bottom] + 1.0); 00213 if(d < da(rx)) // first pixel of current row 00214 { 00215 *xdx = xdx[bottom]; 00216 *ydx = ydx[bottom] + 1.0; 00217 da.set(d, rx); 00218 } 00219 00220 for(x=1, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x; 00221 x<w; 00222 ++x, ++xdx.x, ++ydx.x, ++sx.x, ++rx.x) // current row left to right 00223 { 00224 float d1 = norm(xdx[left] + 1.0, ydx[left]); 00225 float d2 = norm(xdx[bottom], ydx[bottom] + 1.0); 00226 00227 if(d1 < d2) 00228 { 00229 if(da(rx) < d1) continue; 00230 *xdx = xdx[left] + 1.0; 00231 *ydx = ydx[left]; 00232 da.set(d1, rx); 00233 } 00234 else 00235 { 00236 if(da(rx) < d2) continue; 00237 *xdx = xdx[bottom]; 00238 *ydx = ydx[bottom] + 1.0; 00239 da.set(d2, rx); 00240 } 00241 } 00242 for(x=w-2, xdx.x -= 2, ydx.x -= 2, sx.x -= 2, rx.x -= 2; 00243 x>=0; 00244 --x, --xdx.x, --ydx.x, --sx.x, --rx.x) // current row right to left 00245 { 00246 float d1 = norm(xdx[right] + 1.0, ydx[right]); 00247 00248 if(da(rx) < d1) continue; 00249 *xdx = xdx[right] + 1.0; 00250 *ydx = ydx[right]; 00251 da.set(d1, rx); 00252 } 00253 } 00254 } 00255 00256 /********************************************************/ 00257 /* */ 00258 /* distanceTransform */ 00259 /* */ 00260 /********************************************************/ 00261 00262 /** \addtogroup DistanceTransform Distance Transform 00263 Perform a distance transform using either the Euclidean, Manhattan, 00264 or chessboard metrics. 00265 */ 00266 //@{ 00267 00268 /** For all background pixels, calculate the distance to 00269 the nearest object or contour. The label of the pixels to be considered 00270 background in the source image is passed in the parameter 'background'. 00271 Source pixels with other labels will be considered objects. In the 00272 destination image, all pixels corresponding to background will be assigned 00273 the their distance value, all pixels corresponding to objects will be 00274 assigned 0. 00275 00276 The parameter 'norm' gives the distance norm to be used: 00277 00278 <ul> 00279 00280 <li> norm == 0: use chessboard distance (L-infinity norm) 00281 <li> norm == 1: use Manhattan distance (L1 norm) 00282 <li> norm == 2: use Euclidean distance (L2 norm) 00283 00284 </ul> 00285 00286 If you use the L2 norm, the destination pixels must be real valued to give 00287 correct results. 00288 00289 <b> Declarations:</b> 00290 00291 pass arguments explicitly: 00292 \code 00293 namespace vigra { 00294 template <class SrcImageIterator, class SrcAccessor, 00295 class DestImageIterator, class DestAccessor, 00296 class ValueType> 00297 void distanceTransform(SrcImageIterator src_upperleft, 00298 SrcImageIterator src_lowerright, SrcAccessor sa, 00299 DestImageIterator dest_upperleft, DestAccessor da, 00300 ValueType background, int norm) 00301 } 00302 \endcode 00303 00304 00305 use argument objects in conjuction with \ref ArgumentObjectFactories: 00306 \code 00307 namespace vigra { 00308 template <class SrcImageIterator, class SrcAccessor, 00309 class DestImageIterator, class DestAccessor, 00310 class ValueType> 00311 void distanceTransform( 00312 triple<SrcImageIterator, SrcImageIterator, SrcAccessor> src, 00313 pair<DestImageIterator, DestAccessor> dest, 00314 ValueType background, int norm) 00315 } 00316 \endcode 00317 00318 <b> Usage:</b> 00319 00320 <b>\#include</b> "<a href="distancetransform_8hxx-source.html">vigra/distancetransform.hxx</a>"<br> 00321 Namespace: vigra 00322 00323 00324 \code 00325 00326 vigra::BImage src(w,h), edges(w,h); 00327 vigra::FImage distance(w, h); 00328 00329 // empty edge image 00330 edges = 0; 00331 ... 00332 00333 // detect edges in src image (edges will be marked 1, background 0) 00334 vigra::differenceOfExponentialEdgeImage(srcImageRange(src), destImage(edges), 00335 0.8, 4.0); 00336 00337 // find distance of all pixels from nearest edge 00338 vigra::distanceTransform(srcImageRange(edges), destImage(distance), 00339 0, 2); 00340 // ^ background label ^ norm (Euclidean) 00341 \endcode 00342 00343 <b> Required Interface:</b> 00344 00345 \code 00346 00347 SrcImageIterator src_upperleft, src_lowerright; 00348 DestImageIterator dest_upperleft; 00349 00350 SrcAccessor sa; 00351 DestAccessor da; 00352 00353 ValueType background; 00354 float distance; 00355 00356 sa(src_upperleft) != background; 00357 da(dest_upperleft) < distance; 00358 da.set(distance, dest_upperleft); 00359 00360 \endcode 00361 */ 00362 template <class SrcImageIterator, class SrcAccessor, 00363 class DestImageIterator, class DestAccessor, 00364 class ValueType> 00365 inline void 00366 distanceTransform(SrcImageIterator src_upperleft, 00367 SrcImageIterator src_lowerright, SrcAccessor sa, 00368 DestImageIterator dest_upperleft, DestAccessor da, 00369 ValueType background, int norm) 00370 { 00371 if(norm == 1) 00372 { 00373 internalDistanceTransform(src_upperleft, src_lowerright, sa, 00374 dest_upperleft, da, background, 00375 InternalDistanceTransformL1NormFunctor()); 00376 } 00377 else if(norm == 2) 00378 { 00379 internalDistanceTransform(src_upperleft, src_lowerright, sa, 00380 dest_upperleft, da, background, 00381 InternalDistanceTransformL2NormFunctor()); 00382 } 00383 else 00384 { 00385 internalDistanceTransform(src_upperleft, src_lowerright, sa, 00386 dest_upperleft, da, background, 00387 InternalDistanceTransformLInifinityNormFunctor()); 00388 } 00389 } 00390 00391 template <class SrcImageIterator, class SrcAccessor, 00392 class DestImageIterator, class DestAccessor, 00393 class ValueType> 00394 inline void 00395 distanceTransform( 00396 triple<SrcImageIterator, SrcImageIterator, SrcAccessor> src, 00397 pair<DestImageIterator, DestAccessor> dest, 00398 ValueType background, int norm) 00399 { 00400 distanceTransform(src.first, src.second, src.third, 00401 dest.first, dest.second, background, norm); 00402 } 00403 00404 //@} 00405 00406 } // namespace vigra 00407 00408 #endif // VIGRA_DISTANCETRANSFORM_HXX 00409
© Ullrich Köthe (koethe@informatik.uni-hamburg.de) |
html generated using doxygen and Python
|