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

| vigra/labelimage.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.5.0, Dec 07 2006 )                                    */
    00008 /*    The VIGRA Website is                                              */
    00009 /*        http://kogs-www.informatik.uni-hamburg.de/~koethe/vigra/      */
    00010 /*    Please direct questions, bug reports, and contributions to        */
    00011 /*        koethe@informatik.uni-hamburg.de          or                  */
    00012 /*        vigra@kogs1.informatik.uni-hamburg.de                         */
    00013 /*                                                                      */
    00014 /*    Permission is hereby granted, free of charge, to any person       */
    00015 /*    obtaining a copy of this software and associated documentation    */
    00016 /*    files (the "Software"), to deal in the Software without           */
    00017 /*    restriction, including without limitation the rights to use,      */
    00018 /*    copy, modify, merge, publish, distribute, sublicense, and/or      */
    00019 /*    sell copies of the Software, and to permit persons to whom the    */
    00020 /*    Software is furnished to do so, subject to the following          */
    00021 /*    conditions:                                                       */
    00022 /*                                                                      */
    00023 /*    The above copyright notice and this permission notice shall be    */
    00024 /*    included in all copies or substantial portions of the             */
    00025 /*    Software.                                                         */
    00026 /*                                                                      */
    00027 /*    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND    */
    00028 /*    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES   */
    00029 /*    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND          */
    00030 /*    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT       */
    00031 /*    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,      */
    00032 /*    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING      */
    00033 /*    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR     */
    00034 /*    OTHER DEALINGS IN THE SOFTWARE.                                   */
    00035 /*                                                                      */
    00036 /************************************************************************/
    00037
    00038
    00039 #ifndef VIGRA_LABELIMAGE_HXX
    00040 #define VIGRA_LABELIMAGE_HXX
    00041
    00042 #include <vector>
    00043 #include <functional>
    00044 #include "utilities.hxx"
    00045 #include "stdimage.hxx"
    00046
    00047 namespace vigra {
    00048
    00049 /** \addtogroup Labeling Connected Components Labeling
    00050      The connected components algorithm may use either 4 or 8 connectivity.
    00051      By means of a functor the merge criterium can be defined arbitrarily.
    00052 */
    00053 //@{
    00054
    00055 /********************************************************/
    00056 /*                                                      */
    00057 /*                        labelImage                    */
    00058 /*                                                      */
    00059 /********************************************************/
    00060
    00061 /** \brief Find the connected components of a segmented image.
    00062
    00063     Connected components are defined as regions with uniform pixel
    00064     values. Thus, <TT>SrcAccessor::value_type</TT> either must be
    00065     equality comparable (first form), or an EqualityFunctor must be
    00066     provided that realizes the desired predicate (second form). The
    00067     destination's value type should be large enough to hold the labels
    00068     without overflow. Region numbers will be a consecutive sequence
    00069     starting with one and ending with the region number returned by
    00070     the function (inclusive). The parameter '<TT>eight_neighbors</TT>'
    00071     determines whether the regions should be 4-connected or
    00072     8-connected. The function uses accessors.
    00073
    00074     <b> Declarations:</b>
    00075
    00076     pass arguments explicitly:
    00077     \code
    00078     namespace vigra {
    00079         template <class SrcIterator, class SrcAccessor,
    00080                   class DestIterator, class DestAccessor>
    00081         unsigned int labelImage(SrcIterator upperlefts,
    00082                                 SrcIterator lowerrights, SrcAccessor sa,
    00083                                 DestIterator upperleftd, DestAccessor da,
    00084                                 bool eight_neighbors);
    00085
    00086         template <class SrcIterator, class SrcAccessor,
    00087                   class DestIterator, class DestAccessor,
    00088                   class EqualityFunctor>
    00089         unsigned int labelImage(SrcIterator upperlefts,
    00090                                 SrcIterator lowerrights, SrcAccessor sa,
    00091                                 DestIterator upperleftd, DestAccessor da,
    00092                                 bool eight_neighbors, EqualityFunctor equal);
    00093     }
    00094     \endcode
    00095
    00096     use argument objects in conjunction with \ref ArgumentObjectFactories:
    00097     \code
    00098     namespace vigra {
    00099         template <class SrcIterator, class SrcAccessor,
    00100                   class DestIterator, class DestAccessor>
    00101         unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00102                                 pair<DestIterator, DestAccessor> dest,
    00103                                 bool eight_neighbors);
    00104
    00105         template <class SrcIterator, class SrcAccessor,
    00106                   class DestIterator, class DestAccessor,
    00107                   class EqualityFunctor>
    00108         unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00109                                 pair<DestIterator, DestAccessor> dest,
    00110                                 bool eight_neighbors, EqualityFunctor equal)
    00111     }
    00112     \endcode
    00113
    00114     Return:  the number of regions found (= largest region label)
    00115
    00116     <b> Usage:</b>
    00117
    00118         <b>\#include</b> "<a href="labelimage_8hxx-source.html">vigra/labelimage.hxx</a>"<br>
    00119     Namespace: vigra
    00120
    00121     \code
    00122     vigra::BImage src(w,h);
    00123     vigra::IImage labels(w,h);
    00124
    00125     // threshold at 128
    00126     vigra::transformImage(srcImageRange(src), destImage(src),
    00127        vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
    00128                                                     128, 256, 0, 255));
    00129
    00130     // find 4-connected regions
    00131     vigra::labelImage(srcImageRange(src), destImage(labels), false);
    00132     \endcode
    00133
    00134     <b> Required Interface:</b>
    00135
    00136     \code
    00137     SrcImageIterator src_upperleft, src_lowerright;
    00138     DestImageIterator dest_upperleft;
    00139
    00140     SrcAccessor src_accessor;
    00141     DestAccessor dest_accessor;
    00142
    00143     SrcAccessor::value_type u = src_accessor(src_upperleft);
    00144
    00145     u == u                  // first form
    00146
    00147     EqualityFunctor equal;      // second form
    00148     equal(u, u)                 // second form
    00149
    00150     int i;
    00151     dest_accessor.set(i, dest_upperleft);
    00152     \endcode
    00153
    00154 */
    00155 template <class SrcIterator, class SrcAccessor,
    00156           class DestIterator, class DestAccessor,
    00157           class EqualityFunctor>
    00158 unsigned int labelImage(SrcIterator upperlefts,
    00159                         SrcIterator lowerrights, SrcAccessor sa,
    00160                         DestIterator upperleftd, DestAccessor da,
    00161                         bool eight_neighbors, EqualityFunctor equal)
    00162 {
    00163     int w = lowerrights.x - upperlefts.x;
    00164     int h = lowerrights.y - upperlefts.y;
    00165     int x,y,i;
    00166
    00167     static const Diff2D neighbor[] = {
    00168         Diff2D(-1,0),  // left
    00169         Diff2D(-1,-1), // topleft
    00170         Diff2D(0,-1),  // top
    00171         Diff2D(1,-1)   // topright
    00172     };
    00173
    00174     static const int left = 0, /* unused:  topleft = 1, */ top = 2, topright = 3;
    00175     int step = eight_neighbors ? 1 : 2;
    00176
    00177     SrcIterator ys(upperlefts);
    00178     SrcIterator xs(ys);
    00179
    00180     // temporary image to store region labels
    00181     IImage labelimage(w, h);
    00182
    00183     IImage::Iterator yt = labelimage.upperLeft();
    00184     IImage::Iterator xt(yt);
    00185
    00186     // Kovalevsky's clever idea to use
    00187     // image iterator and scan order iterator simultaneously
    00188     IImage::ScanOrderIterator label = labelimage.begin();
    00189
    00190     // pass 1: scan image from upper left to lower right
    00191     // to find connected components
    00192
    00193     // Each component will be represented by a tree of pixels. Each
    00194     // pixel contains the scan order address of its parent in the
    00195     // tree.  In order for pass 2 to work correctly, the parent must
    00196     // always have a smaller scan order address than the child.
    00197     // Therefore, we can merge trees only at their roots, because the
    00198     // root of the combined tree must have the smallest scan order
    00199     // address among all the tree's pixels/ nodes.  The root of each
    00200     // tree is distinguished by pointing to itself (it contains its
    00201     // own scan order address). This condition is enforced whenever a
    00202     // new region is found or two regions are merged
    00203
    00204
    00205     for(y = 0; y != h; ++y, ++ys.y, ++yt.y)
    00206     {
    00207         xs = ys;
    00208         xt = yt;
    00209
    00210         int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top);
    00211
    00212         for(x = 0; x != w; ++x, ++xs.x, ++xt.x)
    00213         {
    00214             int beginNeighbor = (x == 0) ? top : left;
    00215             if(x == w-1 && endNeighbor == topright) endNeighbor = top;
    00216
    00217             for(i=beginNeighbor; i<=endNeighbor; i+=step)
    00218             {
    00219                 if(equal(sa(xs), sa(xs, neighbor[i])))
    00220                 {
    00221                     int neighborLabel = xt[neighbor[i]];
    00222
    00223                     for(int j=i+2; j<=endNeighbor; j+=step)
    00224                     {
    00225                         if(equal(sa(xs), sa(xs, neighbor[j])))
    00226                         {
    00227                             int neighborLabel1 = xt[neighbor[j]];
    00228
    00229                             if(neighborLabel != neighborLabel1)
    00230                             {
    00231                                 // find roots of the region trees
    00232                                 while(neighborLabel != label[neighborLabel])
    00233                                 {
    00234                                     neighborLabel = label[neighborLabel];
    00235                                 }
    00236                                 while(neighborLabel1 != label[neighborLabel1])
    00237                                 {
    00238                                     neighborLabel1 = label[neighborLabel1];
    00239                                 }
    00240
    00241                                 // merge the trees
    00242                                 if(neighborLabel1 < neighborLabel)
    00243                                 {
    00244                                     label[neighborLabel] = neighborLabel1;
    00245                                     neighborLabel = neighborLabel1;
    00246                                 }
    00247                                 else if(neighborLabel < neighborLabel1)
    00248                                 {
    00249                                     label[neighborLabel1] = neighborLabel;
    00250                                 }
    00251                             }
    00252                             break;
    00253                         }
    00254                     }
    00255                     *xt = neighborLabel;
    00256                     break;
    00257                 }
    00258
    00259             }
    00260             if(i > endNeighbor)
    00261             {
    00262                 // new region
    00263                 // The initial label of a new region equals the
    00264                 // scan order address of it's first pixel.
    00265                 // This is essential for correct operation of the algorithm.
    00266                 *xt = x + y*w;
    00267             }
    00268         }
    00269     }
    00270
    00271     // pass 2: assign one label to each region (tree)
    00272     // so that labels form a consecutive sequence 1, 2, ...
    00273     DestIterator yd(upperleftd);
    00274
    00275     unsigned int count = 0;
    00276     i = 0;
    00277     for(y=0; y != h; ++y, ++yd.y)
    00278     {
    00279         DestIterator xd(yd);
    00280         for(x = 0; x != w; ++x, ++xd.x, ++i)
    00281         {
    00282             if(label[i] == i)
    00283             {
    00284                 label[i] = ++count;
    00285             }
    00286             else
    00287             {
    00288                 label[i] = label[label[i]];
    00289             }
    00290             da.set(label[i], xd);
    00291         }
    00292     }
    00293     return count;
    00294 }
    00295
    00296 template <class SrcIterator, class SrcAccessor,
    00297           class DestIterator, class DestAccessor,
    00298           class EqualityFunctor>
    00299 inline
    00300 unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00301                         pair<DestIterator, DestAccessor> dest,
    00302                         bool eight_neighbors, EqualityFunctor equal)
    00303 {
    00304     return labelImage(src.first, src.second, src.third,
    00305                       dest.first, dest.second, eight_neighbors, equal);
    00306 }
    00307
    00308 template <class SrcIterator, class SrcAccessor,
    00309           class DestIterator, class DestAccessor>
    00310 inline
    00311 unsigned int labelImage(SrcIterator upperlefts,
    00312                         SrcIterator lowerrights, SrcAccessor sa,
    00313                         DestIterator upperleftd, DestAccessor da,
    00314                         bool eight_neighbors)
    00315 {
    00316     return labelImage(upperlefts, lowerrights, sa,
    00317                  upperleftd, da, eight_neighbors,
    00318                  std::equal_to<typename SrcAccessor::value_type>());
    00319 }
    00320
    00321 template <class SrcIterator, class SrcAccessor,
    00322           class DestIterator, class DestAccessor>
    00323 inline
    00324 unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00325                         pair<DestIterator, DestAccessor> dest,
    00326                         bool eight_neighbors)
    00327 {
    00328     return labelImage(src.first, src.second, src.third,
    00329                  dest.first, dest.second, eight_neighbors,
    00330                  std::equal_to<typename SrcAccessor::value_type>());
    00331 }
    00332
    00333 /********************************************************/
    00334 /*                                                      */
    00335 /*             labelImageWithBackground                 */
    00336 /*                                                      */
    00337 /********************************************************/
    00338
    00339 /** \brief Find the connected components of a segmented image,
    00340     excluding the background from labeling.
    00341
    00342     Connected components are defined as regions with uniform pixel
    00343     values. Thus, <TT>SrcAccessor::value_type</TT> either must be
    00344     equality comparable (first form), or an EqualityFunctor must be
    00345     provided that realizes the desired predicate (second form). All
    00346     pixel equal to the given '<TT>background_value</TT>' are ignored
    00347     when determining connected components and remain untouched in the
    00348     destination image and
    00349
    00350     The destination's value type should be large enough to hold the
    00351     labels without overflow. Region numbers will be a consecutive
    00352     sequence starting with one and ending with the region number
    00353     returned by the function (inclusive). The parameter
    00354     '<TT>eight_neighbors</TT>' determines whether the regions should
    00355     be 4-connected or 8-connected. The function uses accessors.
    00356
    00357     <b> Declarations:</b>
    00358
    00359     pass arguments explicitly:
    00360     \code
    00361     namespace vigra {
    00362         template <class SrcIterator, class SrcAccessor,
    00363                   class DestIterator, class DestAccessor,
    00364                   class ValueType>
    00365         int labelImageWithBackground(SrcIterator upperlefts,
    00366                        SrcIterator lowerrights, SrcAccessor sa,
    00367                        DestIterator upperleftd, DestAccessor da,
    00368                        bool eight_neighbors,
    00369                        ValueType background_value );
    00370
    00371         template <class SrcIterator, class SrcAccessor,
    00372                   class DestIterator, class DestAccessor,
    00373                   class ValueType, class EqualityFunctor>
    00374         int labelImageWithBackground(SrcIterator upperlefts,
    00375                        SrcIterator lowerrights, SrcAccessor sa,
    00376                        DestIterator upperleftd, DestAccessor da,
    00377                        bool eight_neighbors,
    00378                        ValueType background_value, EqualityFunctor equal);
    00379     }
    00380     \endcode
    00381
    00382     use argument objects in conjunction with \ref ArgumentObjectFactories:
    00383     \code
    00384     namespace vigra {
    00385         template <class SrcIterator, class SrcAccessor,
    00386                   class DestIterator, class DestAccessor,
    00387                   class ValueType>
    00388         inline
    00389         int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00390                                      pair<DestIterator, DestAccessor> dest,
    00391                                      bool eight_neighbors,
    00392                                      ValueType background_value);
    00393
    00394         template <class SrcIterator, class SrcAccessor,
    00395                   class DestIterator, class DestAccessor,
    00396                   class ValueType, class EqualityFunctor>
    00397         inline
    00398         int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00399                                      pair<DestIterator, DestAccessor> dest,
    00400                                      bool eight_neighbors,
    00401                                      ValueType background_value, EqualityFunctor equal);
    00402     }
    00403     \endcode
    00404
    00405     Return:  the number of regions found (= largest region label)
    00406
    00407     <b> Usage:</b>
    00408
    00409         <b>\#include</b> "<a href="labelimage_8hxx-source.html">vigra/labelimage.hxx</a>"<br>
    00410     Namespace: vigra
    00411
    00412     \code
    00413     vigra::BImage src(w,h);
    00414     vigra::IImage labels(w,h);
    00415
    00416     // threshold at 128
    00417     vigra::transformImage(srcImageRange(src), destImage(src),
    00418         vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
    00419                                                     128, 256, 0, 255));
    00420
    00421     // find 4-connected regions of foreground (= white pixels) only
    00422     vigra::labelImageWithBackground(srcImageRange(src), destImage(labels),
    00423                              false, 0);
    00424     \endcode
    00425
    00426     <b> Required Interface:</b>
    00427
    00428     \code
    00429     SrcImageIterator src_upperleft, src_lowerright;
    00430     DestImageIterator dest_upperleft;
    00431
    00432     SrcAccessor src_accessor;
    00433     DestAccessor dest_accessor;
    00434
    00435     SrcAccessor::value_type u = src_accessor(src_upperleft);
    00436     ValueType background_value;
    00437
    00438     u == u                  // first form
    00439     u == background_value   // first form
    00440
    00441     EqualityFunctor equal;      // second form
    00442     equal(u, u)                 // second form
    00443     equal(u, background_value)  // second form
    00444
    00445     int i;
    00446     dest_accessor.set(i, dest_upperleft);
    00447     \endcode
    00448
    00449 */
    00450 template <class SrcIterator, class SrcAccessor,
    00451           class DestIterator, class DestAccessor,
    00452           class ValueType, class EqualityFunctor>
    00453 unsigned int labelImageWithBackground(
    00454     SrcIterator upperlefts,
    00455     SrcIterator lowerrights, SrcAccessor sa,
    00456     DestIterator upperleftd, DestAccessor da,
    00457     bool eight_neighbors,
    00458     ValueType background_value, EqualityFunctor equal)
    00459 {
    00460     int w = lowerrights.x - upperlefts.x;
    00461     int h = lowerrights.y - upperlefts.y;
    00462     int x,y,i;
    00463
    00464     static const Diff2D neighbor[] = {
    00465         Diff2D(-1,0),  // left
    00466         Diff2D(-1,-1), // topleft
    00467         Diff2D(0,-1),  // top
    00468         Diff2D(1,-1)   // topright
    00469     };
    00470
    00471     static const int left = 0, /* unused:  topleft = 1,*/ top = 2, topright = 3;
    00472     int step = eight_neighbors ? 1 : 2;
    00473
    00474     SrcIterator ys(upperlefts);
    00475     SrcIterator xs(ys);
    00476
    00477     // temporary image to store region labels
    00478     IImage labelimage(w, h);
    00479     IImage::ScanOrderIterator label = labelimage.begin();
    00480     IImage::Iterator yt = labelimage.upperLeft();
    00481     IImage::Iterator  xt(yt);
    00482
    00483     // pass 1: scan image from upper left to lower right
    00484     // find connected components
    00485
    00486     for(y = 0; y != h; ++y, ++ys.y, ++yt.y)
    00487     {
    00488         xs = ys;
    00489         xt = yt;
    00490
    00491         int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top);
    00492
    00493         for(x = 0; x != w; ++x, ++xs.x, ++xt.x)
    00494         {
    00495             if(equal(sa(xs), background_value))
    00496             {
    00497                 *xt = -1;
    00498             }
    00499             else
    00500             {
    00501                 int beginNeighbor = (x == 0) ? top : left;
    00502                 if(x == w-1 && endNeighbor == topright) endNeighbor = top;
    00503
    00504                 for(i=beginNeighbor; i<=endNeighbor; i+=step)
    00505                 {
    00506                     if(equal(sa(xs), sa(xs, neighbor[i])))
    00507                     {
    00508                         int neighborLabel = xt[neighbor[i]];
    00509
    00510                         for(int j=i+2; j<=endNeighbor; j+=step)
    00511                         {
    00512                             if(equal(sa(xs), sa(xs, neighbor[j])))
    00513                             {
    00514                                 int neighborLabel1 = xt[neighbor[j]];
    00515
    00516                                 if(neighborLabel != neighborLabel1)
    00517                                 {
    00518                                     // find roots of the region trees
    00519                                     while(neighborLabel != label[neighborLabel])
    00520                                     {
    00521                                         neighborLabel = label[neighborLabel];
    00522                                     }
    00523                                     while(neighborLabel1 != label[neighborLabel1])
    00524                                     {
    00525                                         neighborLabel1 = label[neighborLabel1];
    00526                                     }
    00527
    00528                                     // merge the trees
    00529                                     if(neighborLabel1 < neighborLabel)
    00530                                     {
    00531                                         label[neighborLabel] = neighborLabel1;
    00532                                         neighborLabel = neighborLabel1;
    00533                                     }
    00534                                     else if(neighborLabel < neighborLabel1)
    00535                                     {
    00536                                         label[neighborLabel1] = neighborLabel;
    00537                                     }
    00538                                 }
    00539                                 break;
    00540                             }
    00541                         }
    00542                         *xt = neighborLabel;
    00543                         break;
    00544                     }
    00545
    00546                 }
    00547                 if(i > endNeighbor)
    00548                 {
    00549                     // new region
    00550                     // The initial label of a new region equals the
    00551                     // scan order address of it's first pixel.
    00552                     // This is essential for correct operation of the algorithm.
    00553                     *xt = x + y*w;
    00554                 }
    00555             }
    00556         }
    00557     }
    00558
    00559     // pass 2: assign contiguous labels to the regions
    00560     DestIterator yd(upperleftd);
    00561
    00562     int count = 0;
    00563     i = 0;
    00564     for(y=0; y != h; ++y, ++yd.y)
    00565     {
    00566         DestIterator xd(yd);
    00567         for(x = 0; x != w; ++x, ++xd.x, ++i)
    00568         {
    00569             if(label[i] == -1) continue;
    00570
    00571             if(label[i] == i)
    00572             {
    00573                 label[i] = count++;
    00574             }
    00575             else
    00576             {
    00577                 label[i] = label[label[i]];
    00578             }
    00579             da.set(label[i]+1, xd);
    00580         }
    00581     }
    00582
    00583     return count;
    00584 }
    00585 template <class SrcIterator, class SrcAccessor,
    00586           class DestIterator, class DestAccessor,
    00587           class ValueType, class EqualityFunctor>
    00588 inline
    00589 unsigned int labelImageWithBackground(
    00590     triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00591     pair<DestIterator, DestAccessor> dest,
    00592     bool eight_neighbors,
    00593     ValueType background_value, EqualityFunctor equal)
    00594 {
    00595     return labelImageWithBackground(src.first, src.second, src.third,
    00596                                     dest.first, dest.second,
    00597                                     eight_neighbors, background_value, equal);
    00598 }
    00599
    00600 template <class SrcIterator, class SrcAccessor,
    00601           class DestIterator, class DestAccessor,
    00602           class ValueType>
    00603 inline
    00604 unsigned int labelImageWithBackground(
    00605     triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00606     pair<DestIterator, DestAccessor> dest,
    00607     bool eight_neighbors,
    00608     ValueType background_value)
    00609 {
    00610     return labelImageWithBackground(src.first, src.second, src.third,
    00611                             dest.first, dest.second,
    00612                             eight_neighbors, background_value,
    00613                             std::equal_to<typename SrcAccessor::value_type>());
    00614 }
    00615
    00616 template <class SrcIterator, class SrcAccessor,
    00617           class DestIterator, class DestAccessor,
    00618           class ValueType>
    00619 inline
    00620 unsigned int labelImageWithBackground(
    00621     SrcIterator upperlefts,
    00622     SrcIterator lowerrights, SrcAccessor sa,
    00623     DestIterator upperleftd, DestAccessor da,
    00624     bool eight_neighbors,
    00625     ValueType background_value)
    00626 {
    00627     return labelImageWithBackground(upperlefts, lowerrights, sa,
    00628                             upperleftd, da,
    00629                             eight_neighbors, background_value,
    00630                             std::equal_to<typename SrcAccessor::value_type>());
    00631 }
    00632
    00633 /********************************************************/
    00634 /*                                                      */
    00635 /*            regionImageToCrackEdgeImage               */
    00636 /*                                                      */
    00637 /********************************************************/
    00638
    00639 /** \brief Transform a labeled image into a crack edge image.
    00640
    00641     This algorithm inserts border pixels (so called "crack edges")
    00642     between regions in a labeled image like this (<TT>a</TT> and
    00643     <TT>c</TT> are the original labels, and <TT>0</TT> is the value of
    00644     <TT>edge_marker</TT> and denotes the inserted edges):
    00645
    00646     \code
    00647        original image     insert zero- and one-cells
    00648
    00649                                          a 0 c c c
    00650           a c c                          a 0 0 0 c
    00651           a a c               =>         a a a 0 c
    00652           a a a                          a a a 0 0
    00653                                          a a a a a
    00654     \endcode
    00655
    00656     The algorithm assumes that the original labeled image contains
    00657     no background. Therefore, it is suitable as a post-processing
    00658     operation of \ref labelImage() or \ref seededRegionGrowing().
    00659
    00660     The destination image must be twice the size of the original
    00661     (precisely, <TT>(2*w-1)</TT> by <TT>(2*h-1)</TT> pixels). The
    00662     source value type (<TT>SrcAccessor::value-type</TT>) must be
    00663     equality-comparable.
    00664
    00665     <b> Declarations:</b>
    00666
    00667     pass arguments explicitly:
    00668     \code
    00669     namespace vigra {
    00670         template <class SrcIterator, class SrcAccessor,
    00671                   class DestIterator, class DestAccessor, class DestValue>
    00672         void regionImageToCrackEdgeImage(
    00673                        SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00674                        DestIterator dul, DestAccessor da,
    00675                        DestValue edge_marker)
    00676     }
    00677     \endcode
    00678
    00679     use argument objects in conjunction with \ref ArgumentObjectFactories:
    00680     \code
    00681     namespace vigra {
    00682         template <class SrcIterator, class SrcAccessor,
    00683                   class DestIterator, class DestAccessor, class DestValue>
    00684         inline
    00685         void regionImageToCrackEdgeImage(
    00686                    triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00687                    pair<DestIterator, DestAccessor> dest,
    00688                    DestValue edge_marker)
    00689     }
    00690     \endcode
    00691
    00692     <b> Usage:</b>
    00693
    00694         <b>\#include</b> "<a href="labelimage_8hxx-source.html">vigra/labelimage.hxx</a>"<br>
    00695     Namespace: vigra
    00696
    00697     \code
    00698     vigra::BImage src(w,h);
    00699     vigra::IImage labels(w,h);
    00700     vigra::IImage cellgrid(2*w-1, 2*h-1);
    00701
    00702     // threshold at 128
    00703     vigra::transformImage(srcImageRange(src), destImage(src),
    00704        vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
    00705                                                     128, 256, 0, 255));
    00706
    00707     // find 4-connected regions
    00708     vigra::labelImage(srcImageRange(src), destImage(labels), false);
    00709
    00710     // create cell grid image, mark edges with 0
    00711     vigra::regionImageToCrackEdgeImage(srcImageRange(labels), destImage(cellgrid), 0);
    00712     \endcode
    00713
    00714     <b> Required Interface:</b>
    00715
    00716     \code
    00717     ImageIterator src_upperleft, src_lowerright;
    00718     ImageIterator dest_upperleft;
    00719
    00720     SrcAccessor src_accessor;
    00721     DestAccessor dest_accessor;
    00722
    00723     SrcAccessor::value_type u = src_accessor(src_upperleft);
    00724
    00725     u != u
    00726
    00727     DestValue edge_marker;
    00728     dest_accessor.set(edge_marker, dest_upperleft);
    00729     \endcode
    00730
    00731     <b> Preconditions:</b>
    00732
    00733     The destination image must have twice the size of the source:
    00734     \code
    00735     w_dest = 2 * w_src - 1
    00736     h_dest = 2 * h_src - 1
    00737     \endcode
    00738 */
    00739 template <class SrcIterator, class SrcAccessor,
    00740           class DestIterator, class DestAccessor, class DestValue>
    00741 void regionImageToCrackEdgeImage(
    00742                SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00743                DestIterator dul, DestAccessor da,
    00744                DestValue edge_marker)
    00745 {
    00746     int w = slr.x - sul.x;
    00747     int h = slr.y - sul.y;
    00748     int x,y;
    00749
    00750     static const Diff2D right(1,0);
    00751     static const Diff2D left(-1,0);
    00752     static const Diff2D bottomright(1,1);
    00753     static const Diff2D bottom(0,1);
    00754     static const Diff2D top(0,-1);
    00755
    00756     SrcIterator iy = sul;
    00757     DestIterator dy = dul;
    00758
    00759     for(y=0; y<h-1; ++y, ++iy.y, dy.y+=2)
    00760     {
    00761         SrcIterator ix = iy;
    00762         DestIterator dx = dy;
    00763
    00764         for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
    00765         {
    00766             da.set(sa(ix), dx);
    00767             da.set(sa(ix), dx, bottomright);
    00768
    00769             if(sa(ix, right) != sa(ix))
    00770             {
    00771                 da.set(edge_marker, dx, right);
    00772             }
    00773             else
    00774             {
    00775                 da.set(sa(ix), dx, right);
    00776             }
    00777             if(sa(ix, bottom) != sa(ix))
    00778             {
    00779                 da.set(edge_marker, dx, bottom);
    00780             }
    00781             else
    00782             {
    00783                 da.set(sa(ix), dx, bottom);
    00784             }
    00785
    00786         }
    00787
    00788         da.set(sa(ix), dx);
    00789         if(sa(ix, bottom) != sa(ix))
    00790         {
    00791             da.set(edge_marker, dx, bottom);
    00792         }
    00793         else
    00794         {
    00795             da.set(sa(ix), dx, bottom);
    00796         }
    00797     }
    00798
    00799     SrcIterator ix = iy;
    00800     DestIterator dx = dy;
    00801
    00802     for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
    00803     {
    00804         da.set(sa(ix), dx);
    00805         if(sa(ix, right) != sa(ix))
    00806         {
    00807             da.set(edge_marker, dx, right);
    00808         }
    00809         else
    00810         {
    00811             da.set(sa(ix), dx, right);
    00812         }
    00813     }
    00814     da.set(sa(ix), dx);
    00815
    00816     dy = dul + Diff2D(1,1);
    00817
    00818     // find missing 0-cells
    00819     for(y=0; y<h-1; ++y, dy.y+=2)
    00820     {
    00821         DestIterator dx = dy;
    00822
    00823         for(x=0; x<w-1; ++x, dx.x+=2)
    00824         {
    00825             static const Diff2D dist[] = {right, top, left, bottom };
    00826
    00827             int i;
    00828             for(i=0; i<4; ++i)
    00829             {
    00830                 if(da(dx, dist[i]) == edge_marker) break;
    00831             }
    00832
    00833             if(i < 4) da.set(edge_marker, dx);
    00834         }
    00835     }
    00836 }
    00837
    00838 template <class SrcIterator, class SrcAccessor,
    00839           class DestIterator, class DestAccessor, class DestValue>
    00840 inline
    00841 void regionImageToCrackEdgeImage(
    00842            triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00843            pair<DestIterator, DestAccessor> dest,
    00844            DestValue edge_marker)
    00845 {
    00846     regionImageToCrackEdgeImage(src.first, src.second, src.third,
    00847                                         dest.first, dest.second,
    00848                                         edge_marker);
    00849 }
    00850
    00851 /********************************************************/
    00852 /*                                                      */
    00853 /*                regionImageToEdgeImage                */
    00854 /*                                                      */
    00855 /********************************************************/
    00856
    00857 /** \brief Transform a labeled image into an edge image.
    00858
    00859     This algorithm marks all pixels with the given <TT>edge_marker</TT>
    00860     which belong to a different region (label) than their right or lower
    00861     neighbors:
    00862
    00863     \code
    00864        original image                     edges
    00865                                  (assuming edge_marker == 1)
    00866
    00867           a c c                            1 1 *
    00868           a a c               =>           * 1 1
    00869           a a a                            * * *
    00870     \endcode
    00871
    00872     The non-edge pixels of the destination image will not be touched.
    00873     The source value type (<TT>SrcAccessor::value-type</TT>) must be
    00874     equality-comparable.
    00875
    00876     <b> Declarations:</b>
    00877
    00878     pass arguments explicitly:
    00879     \code
    00880     namespace vigra {
    00881         template <class SrcIterator, class SrcAccessor,
    00882                   class DestIterator, class DestAccessor, class DestValue>
    00883         void regionImageToEdgeImage(
    00884                        SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00885                        DestIterator dul, DestAccessor da,
    00886                        DestValue edge_marker)
    00887     }
    00888     \endcode
    00889
    00890     use argument objects in conjunction with \ref ArgumentObjectFactories:
    00891     \code
    00892     namespace vigra {
    00893         template <class SrcIterator, class SrcAccessor,
    00894                   class DestIterator, class DestAccessor, class DestValue>
    00895         inline
    00896         void regionImageToEdgeImage(
    00897                    triple<SrcIterator, SrcIterator, SrcAccessor> src,
    00898                    pair<DestIterator, DestAccessor> dest,
    00899                    DestValue edge_marker)
    00900     }
    00901     \endcode
    00902
    00903     <b> Usage:</b>
    00904
    00905         <b>\#include</b> "<a href="labelimage_8hxx-source.html">vigra/labelimage.hxx</a>"<br>
    00906     Namespace: vigra
    00907
    00908     \code
    00909     vigra::BImage src(w,h);
    00910     vigra::IImage labels(w,h);
    00911     vigra::IImage edges(w, h);
    00912     edges = 255;  // init background (non-edge) to 255
    00913
    00914     // threshold at 128
    00915     vigra::transformImage(srcImageRange(src), destImage(src),
    00916       vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
    00917                                                     128, 256, 0, 255));
    00918
    00919     // find 4-connected regions
    00920     vigra::labelImage(srcImageRange(src), destImage(labels), false);
    00921
    00922     // create edge image, mark edges with 0
    00923     vigra::regionImageToEdgeImage(srcImageRange(labels), destImage(edges), 0);
    00924     \endcode
    00925
    00926     <b> Required Interface:</b>
    00927
    00928     \code
    00929     ImageIterator src_upperleft, src_lowerright;
    00930     ImageIterator dest_upperleft;
    00931
    00932     SrcAccessor src_accessor;
    00933     DestAccessor dest_accessor;
    00934
    00935     SrcAccessor::value_type u = src_accessor(src_upperleft);
    00936
    00937     u != u
    00938
    00939     DestValue edge_marker;
    00940     dest_accessor.set(edge_marker, dest_upperleft);
    00941     \endcode
    00942
    00943 */
    00944 template <class SrcIterator, class SrcAccessor,
    00945           class DestIterator, class DestAccessor, class DestValue>
    00946 void regionImageToEdgeImage(
    00947                SrcIterator sul, SrcIterator slr, SrcAccessor sa,
    00948                DestIterator dul, DestAccessor da,
    00949                DestValue edge_marker)
    00950 {
    00951     int w = slr.x - sul.x;
    00952     int h = slr.y - sul.y;
    00953     int x,y;
    00954
    00955     static const Diff2D right(1,0);
    00956     static const Diff2D left(-1,0);
    00957     static const Diff2D bottomright(1,1);
    00958     static const Diff2D bottom(0,1);
    00959     static const Diff2D top(0,-1);
    00960
    00961     SrcIterator iy = sul;
    00962     DestIterator dy = dul;
    00963
    00964     for(y=0; y<h-1; ++y, ++iy.y, ++dy.y)
    00965     {
    00966         SrcIterator ix = iy;
    00967         DestIterator dx = dy;
    00968
    00969         for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
    00970         {
    00971             if(sa(ix, right) != sa(ix))
    00972             {
    00973                 da.set(edge_marker, dx);
    00974             }
    00975             if(sa(ix, bottom) != sa(ix))
    00976             {
    00977                 da.set(edge_marker, dx);
    00978             }
    00979         }
    00980
    00981         if(sa(ix, bottom) != sa(ix))
    00982         {
    00983             da.set(edge_marker, dx);
    00984         }
    00985     }
    00986
    00987     SrcIterator ix = iy;
    00988     DestIterator dx = dy;
    00989
    00990     for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
    00991     {
    00992         if(sa(ix, right) != sa(ix))
    00993         {
    00994             da.set(edge_marker, dx);
    00995         }
    00996     }
    00997 }
    00998
    00999 template <class SrcIterator, class SrcAccessor,
    01000           class DestIterator, class DestAccessor, class DestValue>
    01001 inline
    01002 void regionImageToEdgeImage(
    01003            triple<SrcIterator, SrcIterator, SrcAccessor> src,
    01004            pair<DestIterator, DestAccessor> dest,
    01005            DestValue edge_marker)
    01006 {
    01007     regionImageToEdgeImage(src.first, src.second, src.third,
    01008                                         dest.first, dest.second,
    01009                                         edge_marker);
    01010 }
    01011
    01012 //@}
    01013
    01014 } // namespace vigra
    01015
    01016 #endif // VIGRA_LABELIMAGE_HXX

© Ullrich Köthe (koethe@informatik.uni-hamburg.de) Cognitive Systems Group, University of Hamburg, Germany | html generated using doxygen and Python VIGRA 1.5.0 (7 Dec 2006)