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

details vigra/localminmax.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_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.3 (18 Aug 2005)