[ VIGRA Homepage | Class Index | Function Index | File Index | Main Page ]

details vigra/distancetransform.hxx VIGRA

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.3.3, Aug 18 2005 )                                    */
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 conjunction 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)
Cognitive Systems Group, University of Hamburg, Germany

html generated using doxygen and Python
VIGRA 1.3.3 (18 Aug 2005)