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