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