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