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

| vigra/localminmax.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_LOCALMINMAX_HXX
    00025 #define VIGRA_LOCALMINMAX_HXX
    00026
    00027 #include <vector>
    00028 #include "vigra/utilities.hxx"
    00029 #include "vigra/stdimage.hxx"
    00030 #include "vigra/initimage.hxx"
    00031 #include "vigra/labelimage.hxx"
    00032
    00033 namespace vigra {
    00034
    00035 /** \addtogroup LocalMinMax Local Minima and Maxima
    00036
    00037     Detect local minima and maxima of the gray level,
    00038     including extremal plateaus larger than 1 pixel
    00039 */
    00040 //@{
    00041
    00042 /********************************************************/
    00043 /*                                                      */
    00044 /*                       localMinima                    */
    00045 /*                                                      */
    00046 /********************************************************/
    00047
    00048 /** \brief Find local minima in an image.
    00049
    00050     The minima are found only when the have a size of one pixel.
    00051     Use \ref extendedLocalMinima() to find minimal plateaus. Minima are
    00052     marked in the destination image with the given marker value
    00053     (default is 1), all other destination pixels remain unchanged.
    00054     <TT>SrcAccessor::value_type</TT> must be less-comparable.
    00055     A pixel at the image border will never be marked as minimum.
    00056     The function uses accessors.
    00057
    00058     <b> Declarations:</b>
    00059
    00060     pass arguments explicitly:
    00061     \code
    00062     namespace vigra {
    00063         template <class SrcIterator, class SrcAccessor,
    00064               class DestIterator, class DestAccessor,
    00065               class DestValue = DestAccessor::value_type>
    00066         void
    00067         localMinima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00068             DestIterator dul, DestAccessor da,
    00069             DestValue marker = NumericTraits<DestValue>::one())
    00070     }
    00071     \endcode
    00072
    00073     use argument objects in conjunction with \ref ArgumentObjectFactories:
    00074     \code
    00075     namespace vigra {
    00076         template <class SrcIterator, class SrcAccessor,
    00077               class DestIterator, class DestAccessor,
    00078               class DestValue = DestAccessor::value_type>
    00079         void
    00080         localMinima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00081             pair<DestIterator, DestAccessor> dest,
    00082             DestValue marker = NumericTraits<DestValue>::one())
    00083     }
    00084     \endcode
    00085
    00086     <b> Usage:</b>
    00087
    00088         <b>\#include</b> "<a href="localminmax_8hxx-source.html">vigra/localminmax.hxx</a>"<br>
    00089     Namespace: vigra
    00090
    00091     \code
    00092     vigra::BImage src(w,h), minima(w,h);
    00093
    00094     // init destiniation image
    00095     minima = 0;
    00096
    00097     vigra::localMinima(srcImageRange(src), destImage(minima));
    00098     \endcode
    00099
    00100     <b> Required Interface:</b>
    00101
    00102     \code
    00103     SrcImageIterator src_upperleft, src_lowerright;
    00104     DestImageIterator dest_upperleft;
    00105
    00106     SrcAccessor src_accessor;
    00107     DestAccessor dest_accessor;
    00108
    00109     SrcAccessor::value_type u = src_accessor(src_upperleft);
    00110
    00111     u < u
    00112
    00113     DestValue marker;
    00114     dest_accessor.set(marker, dest_upperleft);
    00115     \endcode
    00116
    00117 */
    00118 template <class SrcIterator, class SrcAccessor,
    00119           class DestIterator, class DestAccessor, class DestValue>
    00120 void
    00121 localMinima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00122             DestIterator dul, DestAccessor da, DestValue marker)
    00123 {
    00124     int w = slr.x - sul.x - 2;
    00125     int h = slr.y - sul.y - 2;
    00126
    00127     static const Diff2D dist[] = {
    00128         Diff2D( 1, 0), Diff2D( 1, -1), Diff2D( 0, -1), Diff2D( -1, -1),
    00129         Diff2D( -1, 0), Diff2D( -1, 1), Diff2D( 0, 1), Diff2D( 1, 1)};
    00130
    00131     int i,x,y;
    00132
    00133     sul += Diff2D(1,1);
    00134     dul += Diff2D(1,1);
    00135
    00136     for(y=0; y<h; ++y, ++sul.y, ++dul.y)
    00137     {
    00138     SrcIterator  sx = sul;
    00139     DestIterator dx = dul;
    00140
    00141     for(x=0; x<w; ++x, ++sx.x, ++dx.x)
    00142     {
    00143         for(i=0; i<8; ++i)
    00144         {
    00145         if(!(sa(sx) < sa(sx, dist[i]))) break;
    00146         }
    00147
    00148         if(i == 8) da.set(marker, dx);
    00149     }
    00150     }
    00151 }
    00152
    00153 template <class SrcIterator, class SrcAccessor,
    00154           class DestIterator, class DestAccessor>
    00155 inline void
    00156 localMinima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00157             DestIterator dul, DestAccessor da)
    00158 {
    00159     localMinima(sul, slr, sa, dul, da,
    00160                 NumericTraits<typename DestAccessor::value_type>::one());
    00161 }
    00162
    00163 template <class SrcIterator, class SrcAccessor,
    00164           class DestIterator, class DestAccessor, class DestValue>
    00165 inline void
    00166 localMinima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00167             pair<DestIterator, DestAccessor> dest,
    00168         DestValue marker)
    00169 {
    00170     localMinima(src.first, src.second, src.third,
    00171                 dest.first, dest.second, marker);
    00172 }
    00173
    00174 template <class SrcIterator, class SrcAccessor,
    00175           class DestIterator, class DestAccessor>
    00176 inline void
    00177 localMinima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00178             pair<DestIterator, DestAccessor> dest)
    00179 {
    00180     localMinima(src.first, src.second, src.third,
    00181                 dest.first, dest.second,
    00182                 NumericTraits<typename DestAccessor::value_type>::one());
    00183 }
    00184
    00185 /********************************************************/
    00186 /*                                                      */
    00187 /*                       localMaxima                    */
    00188 /*                                                      */
    00189 /********************************************************/
    00190
    00191 /** \brief Find local maxima in an image.
    00192
    00193     The maxima are found only when the have a size of one pixel.
    00194     Use \ref extendedLocalMaxima() to find maximal plateaus. Maxima are
    00195     marked in the destination image with the given marker value
    00196     (default is 1), all other destination pixels remain unchanged.
    00197     <TT>SrcAccessor::value_type</TT> must be less-comparable.
    00198     A pixel at the image border will never be marked as maximum.
    00199     The function uses accessors.
    00200
    00201     <b> Declarations:</b>
    00202
    00203     pass arguments explicitly:
    00204     \code
    00205     namespace vigra {
    00206         template <class SrcIterator, class SrcAccessor,
    00207               class DestIterator, class DestAccessor,
    00208               class DestValue = DestAccessor::value_type>
    00209         void
    00210         localMaxima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00211             DestIterator dul, DestAccessor da,
    00212             DestValue marker = NumericTraits<DestValue>::one())
    00213     }
    00214     \endcode
    00215
    00216     use argument objects in conjunction with \ref ArgumentObjectFactories:
    00217     \code
    00218     namespace vigra {
    00219         template <class SrcIterator, class SrcAccessor,
    00220               class DestIterator, class DestAccessor,
    00221               class DestValue = DestAccessor::value_type>
    00222         void
    00223         localMaxima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00224             pair<DestIterator, DestAccessor> dest,
    00225             DestValue marker = NumericTraits<DestValue>::one())
    00226     }
    00227     \endcode
    00228
    00229     <b> Usage:</b>
    00230
    00231         <b>\#include</b> "<a href="localminmax_8hxx-source.html">vigra/localminmax.hxx</a>"<br>
    00232     Namespace: vigra
    00233
    00234     \code
    00235     vigra::BImage src(w,h), maxima(w,h);
    00236
    00237     // init destiniation image
    00238     maxima = 0;
    00239
    00240     vigra::localMaxima(srcImageRange(src), destImage(maxima));
    00241     \endcode
    00242
    00243     <b> Required Interface:</b>
    00244
    00245     \code
    00246     SrcImageIterator src_upperleft, src_lowerright;
    00247     DestImageIterator dest_upperleft;
    00248
    00249     SrcAccessor src_accessor;
    00250     DestAccessor dest_accessor;
    00251
    00252     SrcAccessor::value_type u = src_accessor(src_upperleft);
    00253
    00254     u < u
    00255
    00256     DestValue marker;
    00257     dest_accessor.set(marker, dest_upperleft);
    00258     \endcode
    00259
    00260 */
    00261 template <class SrcIterator, class SrcAccessor,
    00262           class DestIterator, class DestAccessor, class DestValue>
    00263 void
    00264 localMaxima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00265             DestIterator dul, DestAccessor da, DestValue marker)
    00266 {
    00267     int w = slr.x - sul.x - 2;
    00268     int h = slr.y - sul.y - 2;
    00269
    00270     static const Diff2D dist[] = {
    00271         Diff2D( 1, 0), Diff2D( 1, -1), Diff2D( 0, -1), Diff2D( -1, -1),
    00272         Diff2D( -1, 0), Diff2D( -1, 1), Diff2D( 0, 1), Diff2D( 1, 1)};
    00273
    00274     int i,x,y;
    00275
    00276     sul += Diff2D(1,1);
    00277     dul += Diff2D(1,1);
    00278
    00279     for(y=0; y<h; ++y, ++sul.y, ++dul.y)
    00280     {
    00281     SrcIterator  sx = sul;
    00282     DestIterator dx = dul;
    00283
    00284     for(x=0; x<w; ++x, ++sx.x, ++dx.x)
    00285     {
    00286         for(i=0; i<8; ++i)
    00287         {
    00288         if(!(sa(sx, dist[i]) < sa(sx))) break;
    00289         }
    00290
    00291         if(i == 8) da.set(marker, dx);
    00292     }
    00293     }
    00294 }
    00295
    00296 template <class SrcIterator, class SrcAccessor,
    00297           class DestIterator, class DestAccessor>
    00298 inline void
    00299 localMaxima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00300             DestIterator dul, DestAccessor da)
    00301 {
    00302     localMaxima(sul, slr, sa, dul, da,
    00303                 NumericTraits<typename DestAccessor::value_type>::one());
    00304 }
    00305
    00306 template <class SrcIterator, class SrcAccessor,
    00307           class DestIterator, class DestAccessor, class DestValue>
    00308 inline void
    00309 localMaxima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00310             pair<DestIterator, DestAccessor> dest,
    00311         DestValue marker)
    00312 {
    00313     localMaxima(src.first, src.second, src.third,
    00314                 dest.first, dest.second, marker);
    00315 }
    00316
    00317 template <class SrcIterator, class SrcAccessor,
    00318           class DestIterator, class DestAccessor>
    00319 inline void
    00320 localMaxima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00321             pair<DestIterator, DestAccessor> dest)
    00322 {
    00323     localMaxima(src.first, src.second, src.third,
    00324                 dest.first, dest.second,
    00325                 NumericTraits<typename DestAccessor::value_type>::one());
    00326 }
    00327
    00328 /********************************************************/
    00329 /*                                                      */
    00330 /*                 extendedLocalMinima                  */
    00331 /*                                                      */
    00332 /********************************************************/
    00333
    00334 /** \brief Find local minimal regions in an image.
    00335
    00336     This function finds regions of uniform pixel value
    00337     whose neighboring regions are all have larger values
    00338     (minimal plateaus of arbitrary size). Minimal regions are
    00339     marked in the destination image with the given marker value
    00340     (default is 1), all other destination pixels remain unchanged.
    00341     <TT>SrcAccessor::value_type</TT> must be equality-comparable and
    00342     less-comparable.
    00343     A pixel at the image border will never be marked as minimum or
    00344     minimal plateau.
    00345     The function uses accessors.
    00346
    00347     <b> Declarations:</b>
    00348
    00349     pass arguments explicitly:
    00350     \code
    00351     namespace vigra {
    00352         template <class SrcIterator, class SrcAccessor,
    00353               class DestIterator, class DestAccessor,
    00354               class DestValue = DestAccessor::value_type>
    00355         void
    00356         extendedLocalMinima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00357                     DestIterator dul, DestAccessor da,
    00358                     DestValue marker = NumericTraits<DestValue>::one())
    00359     }
    00360     \endcode
    00361
    00362     use argument objects in conjunction with \ref ArgumentObjectFactories:
    00363     \code
    00364     namespace vigra {
    00365         template <class SrcIterator, class SrcAccessor,
    00366               class DestIterator, class DestAccessor,
    00367               class DestValue = DestAccessor::value_type>
    00368         void
    00369         extendedLocalMinima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00370                     pair<DestIterator, DestAccessor> dest,
    00371                     DestValue marker = NumericTraits<DestValue>::one())
    00372     }
    00373     \endcode
    00374
    00375     <b> Usage:</b>
    00376
    00377         <b>\#include</b> "<a href="localminmax_8hxx-source.html">vigra/localminmax.hxx</a>"<br>
    00378     Namespace: vigra
    00379
    00380     \code
    00381     vigra::BImage src(w,h), minima(w,h);
    00382
    00383     // init destiniation image
    00384     minima = 0;
    00385
    00386     vigra::extendedLocalMinima(srcImageRange(src), destImage(minima));
    00387     \endcode
    00388
    00389     <b> Required Interface:</b>
    00390
    00391     \code
    00392     SrcImageIterator src_upperleft, src_lowerright;
    00393     DestImageIterator dest_upperleft;
    00394
    00395     SrcAccessor src_accessor;
    00396     DestAccessor dest_accessor;
    00397
    00398     SrcAccessor::value_type u = src_accessor(src_upperleft);
    00399
    00400     u == u
    00401     u < u
    00402
    00403     DestValue marker;
    00404     dest_accessor.set(marker, dest_upperleft);
    00405     \endcode
    00406
    00407 */
    00408 template <class SrcIterator, class SrcAccessor,
    00409           class DestIterator, class DestAccessor, class DestValue>
    00410 void
    00411 extendedLocalMinima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00412             DestIterator dul, DestAccessor da, DestValue marker)
    00413 {
    00414     int w = slr.x - sul.x;
    00415     int h = slr.y - sul.y;
    00416
    00417     static const Diff2D dist[] = {
    00418         Diff2D( 1, 0), Diff2D( 1, -1), Diff2D( 0, -1), Diff2D( -1, -1),
    00419         Diff2D( -1, 0), Diff2D( -1, 1), Diff2D( 0, 1), Diff2D( 1, 1),
    00420         Diff2D( 1, 0), Diff2D( 1, -1), Diff2D( 0, -1), Diff2D( -1, -1)};
    00421
    00422     int i,x,y;
    00423
    00424     BasicImage<int> labels(w,h);
    00425
    00426     labels = 0;
    00427
    00428     int number_of_regions =
    00429         labelImage(sul, slr, sa, labels.upperLeft(), labels.accessor(), true);
    00430
    00431     std::vector<unsigned char> processed(number_of_regions+1, (unsigned char)0);
    00432
    00433     SrcIterator ys = sul + Diff2D(1,1);
    00434     BasicImage<int>::Iterator lul = labels.upperLeft();
    00435     BasicImage<int>::Iterator ly = lul + Diff2D(1,1);
    00436
    00437     initImage(lul, lul+Diff2D(1,h), labels.accessor(), 0);
    00438
    00439     for(y=1; y<h-1; ++y, ++ys.y, ++ly.y)
    00440     {
    00441     SrcIterator  sx = ys;
    00442     BasicImage<int>::Iterator lx(ly);
    00443
    00444     for(x=1; x<w-1; ++x, ++sx.x, ++lx.x)
    00445     {
    00446         int lab = *lx;
    00447         typename SrcAccessor::value_type v = sa(sx);
    00448
    00449         if(processed[lab]) continue;
    00450
    00451         processed[lab] = 1; // assume minimum until opposite is proved
    00452
    00453         int is_plateau = 0;
    00454
    00455         for(i=11; i>3; --i)
    00456         {
    00457         if(lx[dist[i]] == lab)
    00458         {
    00459             is_plateau = i;
    00460         }
    00461         else if(sa(sx, dist[i]) < v)
    00462         {
    00463             break;
    00464         }
    00465         }
    00466
    00467         if(i > 3)
    00468         {
    00469             processed[lab] = 2;  // not a minimum
    00470         continue;
    00471         }
    00472
    00473         if(!is_plateau) continue;  // is a minimum
    00474
    00475         if((x == 1) && (is_plateau == 4) &&
    00476            (lx[dist[3]] == lab)) is_plateau = 3;
    00477
    00478         // is a plateau - do contour-following
    00479         int xa = x;
    00480         int ya = y;
    00481         int first_dir = is_plateau & 7;
    00482         int dir = first_dir;
    00483         int xc = xa;
    00484         int yc = ya;
    00485
    00486         do
    00487         {
    00488         xc = xc + dist[dir].x;
    00489         yc = yc + dist[dir].y;
    00490
    00491         dir = (dir + 6) & 7;
    00492
    00493         for (; true; dir = (dir + 1) & 7)
    00494         {
    00495             int xn = xc + dist[dir].x;
    00496             int yn = yc + dist[dir].y;
    00497                     Diff2D dn(xn, yn);
    00498
    00499             if((xn >= 0) && (xn < w) && (yn >= 0) && (yn < h))
    00500             {
    00501                 if(lul[dn] == lab) break;
    00502
    00503             if(dir & 1) continue;
    00504
    00505             if(sa(sul, dn) < v)
    00506             {
    00507                 processed[lab] = 2; // current region not a minimum
    00508             }
    00509             else
    00510             {
    00511                 processed[lul[dn]] = 2; // other region not
    00512                                             // a minimum
    00513             }
    00514             }
    00515         }
    00516             }
    00517         while((xc != xa) || (yc != ya) || (dir != first_dir));
    00518     }
    00519     }
    00520
    00521     for(y=0; y<h; ++y, ++dul.y, ++lul.y)
    00522     {
    00523     DestIterator  xd = dul;
    00524     BasicImage<int>::Iterator lx(lul);
    00525
    00526     for(x=0; x<w; ++x, ++xd.x, ++lx.x)
    00527     {
    00528         if(processed[*lx] == 1) da.set(marker, xd);
    00529     }
    00530     }
    00531 }
    00532
    00533 template <class SrcIterator, class SrcAccessor,
    00534           class DestIterator, class DestAccessor>
    00535 inline void
    00536 extendedLocalMinima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00537             DestIterator dul, DestAccessor da)
    00538 {
    00539     extendedLocalMinima(sul, slr, sa, dul, da,
    00540                 NumericTraits<typename DestAccessor::value_type>::one());
    00541 }
    00542
    00543 template <class SrcIterator, class SrcAccessor,
    00544           class DestIterator, class DestAccessor, class DestValue>
    00545 inline void
    00546 extendedLocalMinima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00547             pair<DestIterator, DestAccessor> dest,
    00548         DestValue marker)
    00549 {
    00550     extendedLocalMinima(src.first, src.second, src.third,
    00551                 dest.first, dest.second, marker);
    00552 }
    00553
    00554 template <class SrcIterator, class SrcAccessor,
    00555           class DestIterator, class DestAccessor>
    00556 inline void
    00557 extendedLocalMinima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00558             pair<DestIterator, DestAccessor> dest)
    00559 {
    00560     extendedLocalMinima(src.first, src.second, src.third,
    00561                 dest.first, dest.second,
    00562                 NumericTraits<typename DestAccessor::value_type>::one());
    00563 }
    00564
    00565 /********************************************************/
    00566 /*                                                      */
    00567 /*                 extendedLocalMaxima                  */
    00568 /*                                                      */
    00569 /********************************************************/
    00570
    00571 /** \brief Find local maximal regions in an image.
    00572
    00573     This function finds regions of uniform pixel value
    00574     whose neighboring regions are all have smaller values
    00575     (maximal plateaus of arbitrary size). Maximal regions are
    00576     marked in the destination image with the given marker value
    00577     (default is 1), all other destination pixels remain unchanged.
    00578     <TT>SrcAccessor::value_type</TT> must be equality-comparable and
    00579     less-comparable.
    00580     A pixel at the image border will never be marked as maximum or
    00581     maximal plateau.
    00582     The function uses accessors.
    00583
    00584     <b> Declarations:</b>
    00585
    00586     pass arguments explicitly:
    00587     \code
    00588     namespace vigra {
    00589         template <class SrcIterator, class SrcAccessor,
    00590               class DestIterator, class DestAccessor,
    00591               class DestValue = DestAccessor::value_type>
    00592         void
    00593         extendedLocalMaxima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00594                     DestIterator dul, DestAccessor da,
    00595                     DestValue marker = NumericTraits<DestValue>::one())
    00596     }
    00597     \endcode
    00598
    00599     use argument objects in conjunction with \ref ArgumentObjectFactories:
    00600     \code
    00601     namespace vigra {
    00602         template <class SrcIterator, class SrcAccessor,
    00603               class DestIterator, class DestAccessor,
    00604               class DestValue = DestAccessor::value_type>
    00605         void
    00606         extendedLocalMaxima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00607                     pair<DestIterator, DestAccessor> dest,
    00608                     DestValue marker = NumericTraits<DestValue>::one())
    00609     }
    00610     \endcode
    00611
    00612     <b> Usage:</b>
    00613
    00614         <b>\#include</b> "<a href="localminmax_8hxx-source.html">vigra/localminmax.hxx</a>"<br>
    00615     Namespace: vigra
    00616
    00617     \code
    00618     vigra::BImage src(w,h), maxima(w,h);
    00619
    00620     // init destiniation image
    00621     maxima = 0;
    00622
    00623     vigra::extendedLocalMaxima(srcImageRange(src), destImage(maxima));
    00624     \endcode
    00625
    00626     <b> Required Interface:</b>
    00627
    00628     \code
    00629     SrcImageIterator src_upperleft, src_lowerright;
    00630     DestImageIterator dest_upperleft;
    00631
    00632     SrcAccessor src_accessor;
    00633     DestAccessor dest_accessor;
    00634
    00635     SrcAccessor::value_type u = src_accessor(src_upperleft);
    00636
    00637     u == u
    00638     u < u
    00639
    00640     DestValue marker;
    00641     dest_accessor.set(marker, dest_upperleft);
    00642     \endcode
    00643
    00644 */
    00645 template <class SrcIterator, class SrcAccessor,
    00646           class DestIterator, class DestAccessor, class DestValue>
    00647 void
    00648 extendedLocalMaxima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00649             DestIterator dul, DestAccessor da, DestValue marker)
    00650 {
    00651     int w = slr.x - sul.x;
    00652     int h = slr.y - sul.y;
    00653
    00654     static const Diff2D dist[] = {
    00655         Diff2D( 1, 0), Diff2D( 1, -1), Diff2D( 0, -1), Diff2D( -1, -1),
    00656         Diff2D( -1, 0), Diff2D( -1, 1), Diff2D( 0, 1), Diff2D( 1, 1),
    00657         Diff2D( 1, 0), Diff2D( 1, -1), Diff2D( 0, -1), Diff2D( -1, -1)};
    00658
    00659     int i,x,y;
    00660
    00661     BasicImage<int> labels(w,h);
    00662
    00663     int number_of_regions =
    00664         labelImage(sul, slr, sa, labels.upperLeft(), labels.accessor(), true);
    00665
    00666     std::vector<unsigned char> processed(number_of_regions+1, (unsigned char)0);
    00667
    00668     SrcIterator ys = sul + Diff2D(1,1);
    00669     BasicImage<int>::Iterator lul = labels.upperLeft();
    00670     BasicImage<int>::Iterator ly = lul + Diff2D(1,1);
    00671
    00672     lul(0,1) = 0;
    00673
    00674     for(y=1; y<h-1; ++y, ++ys.y, ++ly.y)
    00675     {
    00676     SrcIterator  sx = ys;
    00677     BasicImage<int>::Iterator lx(ly);
    00678
    00679     for(x=1; x<w-1; ++x, ++sx.x, ++lx.x)
    00680     {
    00681         int lab = *lx;
    00682         typename SrcAccessor::value_type v = sa(sx);
    00683
    00684         if(processed[lab]) continue;
    00685
    00686         processed[lab] = 1; // assume maximum until opposite is proved
    00687
    00688         int is_plateau = 0;
    00689
    00690         for(i=11; i>3; --i)
    00691         {
    00692         if(lx[dist[i]] == lab)
    00693         {
    00694             is_plateau = i;
    00695         }
    00696         else if(v < sa(sx, dist[i]))
    00697         {
    00698             break;
    00699         }
    00700         }
    00701
    00702         if(i > 3)
    00703         {
    00704             processed[lab] = 2;  // not a maximum
    00705         continue;
    00706         }
    00707
    00708         if(!is_plateau) continue;  // is a maximum
    00709
    00710         if((x == 1) && (is_plateau == 4) &&
    00711            (lx[dist[3]] == lab)) is_plateau = 3;
    00712
    00713         // is a plateau - do contour-following
    00714         int xa = x;
    00715         int ya = y;
    00716         int first_dir = is_plateau & 7;
    00717         int dir = first_dir;
    00718         int xc = xa;
    00719         int yc = ya;
    00720
    00721         do
    00722         {
    00723         xc = xc + dist[dir].x;
    00724         yc = yc + dist[dir].y;
    00725
    00726         dir = (dir + 6) & 7;
    00727
    00728         for (; true; dir = (dir + 1) & 7)
    00729         {
    00730             int xn = xc + dist[dir].x;
    00731             int yn = yc + dist[dir].y;
    00732                     Diff2D dn(xn, yn);
    00733
    00734             if((xn >= 0) && (xn < w) && (yn >= 0) && (yn < h))
    00735             {
    00736                 if(lul[dn] == lab) break;
    00737
    00738             if(dir & 1) continue;
    00739
    00740             if(v < sa(sul, dn))
    00741             {
    00742                 processed[lab] = 2; // current region not a maximum
    00743             }
    00744             else
    00745             {
    00746                 processed[lul[dn]] = 2; // other region not
    00747                                             // a maximum
    00748             }
    00749             }
    00750         }
    00751             }
    00752         while((xc != xa) || (yc != ya) || (dir != first_dir));
    00753     }
    00754     }
    00755
    00756     for(y=0; y<h; ++y, ++dul.y, ++lul.y)
    00757     {
    00758     DestIterator  xd = dul;
    00759     BasicImage<int>::Iterator lx(lul);
    00760
    00761     for(x=0; x<w; ++x, ++xd.x, ++lx.x)
    00762     {
    00763         if(processed[*lx] == 1) da.set(marker, xd);
    00764     }
    00765     }
    00766 }
    00767
    00768 template <class SrcIterator, class SrcAccessor,
    00769           class DestIterator, class DestAccessor>
    00770 inline void
    00771 extendedLocalMaxima(SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00772             DestIterator dul, DestAccessor da)
    00773 {
    00774     extendedLocalMaxima(sul, slr, sa, dul, da,
    00775                 NumericTraits<typename DestAccessor::value_type>::one());
    00776 }
    00777
    00778 template <class SrcIterator, class SrcAccessor,
    00779           class DestIterator, class DestAccessor, class DestValue>
    00780 inline void
    00781 extendedLocalMaxima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00782             pair<DestIterator, DestAccessor> dest,
    00783         DestValue marker)
    00784 {
    00785     extendedLocalMaxima(src.first, src.second, src.third,
    00786                 dest.first, dest.second, marker);
    00787 }
    00788
    00789 template <class SrcIterator, class SrcAccessor,
    00790           class DestIterator, class DestAccessor>
    00791 inline void
    00792 extendedLocalMaxima(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00793             pair<DestIterator, DestAccessor> dest)
    00794 {
    00795     extendedLocalMaxima(src.first, src.second, src.third,
    00796                 dest.first, dest.second,
    00797                 NumericTraits<typename DestAccessor::value_type>::one());
    00798 }
    00799
    00800 //@}
    00801
    00802 } // namespace vigra
    00803
    00804 #endif // VIGRA_LOCALMINMAX_HXX

© 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)