[ 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.3.2, Jan 27 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.2 (27 Jan 2005)