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

details vigra/labelimage.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_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 conjuction 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 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 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 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 conjuction 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 int labelImageWithBackground(SrcIterator upperlefts,
00439                SrcIterator lowerrights, SrcAccessor sa,
00440                DestIterator upperleftd, DestAccessor da,
00441                bool eight_neighbors,
00442                ValueType background_value, EqualityFunctor equal)
00443 {
00444     int w = lowerrights.x - upperlefts.x;
00445     int h = lowerrights.y - upperlefts.y;
00446     int x,y,i;
00447 
00448     static const Diff2D neighbor[] = {
00449         Diff2D(-1,0),  // left
00450         Diff2D(-1,-1), // topleft
00451         Diff2D(0,-1),  // top
00452         Diff2D(1,-1)   // topright
00453     };
00454 
00455     static const int left = 0, /* unused:  topleft = 1,*/ top = 2, topright = 3;
00456     int step = eight_neighbors ? 1 : 2;
00457 
00458     SrcIterator ys(upperlefts);
00459     SrcIterator xs(ys);
00460 
00461     // temporary image to store region labels
00462     IImage labelimage(w, h);
00463     IImage::ScanOrderIterator label = labelimage.begin();
00464     IImage::Iterator yt = labelimage.upperLeft();
00465     IImage::Iterator  xt(yt);
00466 
00467     // pass 1: scan image from upper left to lower right
00468     // find connected components
00469 
00470     for(y = 0; y != h; ++y, ++ys.y, ++yt.y)
00471     {
00472         xs = ys;
00473         xt = yt;
00474 
00475         int endNeighbor = (y == 0) ? left : (eight_neighbors ? topright : top);
00476 
00477         for(x = 0; x != w; ++x, ++xs.x, ++xt.x)
00478         {
00479             if(equal(sa(xs), background_value))
00480             {
00481                 *xt = -1;
00482             }
00483             else
00484             {
00485                 int beginNeighbor = (x == 0) ? top : left;
00486                 if(x == w-1 && endNeighbor == topright) endNeighbor = top;
00487 
00488                 for(i=beginNeighbor; i<=endNeighbor; i+=step)
00489                 {
00490                     if(equal(sa(xs), sa(xs, neighbor[i])))
00491                     {
00492                         int neighborLabel = xt[neighbor[i]];
00493 
00494                         for(int j=i+2; j<=endNeighbor; j+=step)
00495                         {
00496                             if(equal(sa(xs), sa(xs, neighbor[j])))
00497                             {
00498                                 int neighborLabel1 = xt[neighbor[j]];
00499 
00500                                 if(neighborLabel != neighborLabel1)
00501                                 {
00502                                     // find roots of the region trees
00503                                     while(neighborLabel != label[neighborLabel])
00504                                     {
00505                                         neighborLabel = label[neighborLabel];
00506                                     }
00507                                     while(neighborLabel1 != label[neighborLabel1])
00508                                     {
00509                                         neighborLabel1 = label[neighborLabel1];
00510                                     }
00511 
00512                                     // merge the trees
00513                                     if(neighborLabel1 < neighborLabel)
00514                                     {
00515                                         label[neighborLabel] = neighborLabel1;
00516                                         neighborLabel = neighborLabel1;
00517                                     }
00518                                     else if(neighborLabel < neighborLabel1)
00519                                     {
00520                                         label[neighborLabel1] = neighborLabel;
00521                                     }
00522                                 }
00523                                 break;
00524                             }
00525                         }
00526                         *xt = neighborLabel;
00527                         break;
00528                     }
00529 
00530                 }
00531                 if(i > endNeighbor)
00532                 {
00533                     // new region
00534                     // The initial label of a new region equals the
00535                     // scan order address of it's first pixel.
00536                     // This is essential for correct operation of the algorithm.
00537                     *xt = x + y*w;
00538                 }
00539             }
00540         }
00541     }
00542 
00543     // pass 2: assign contiguous labels to the regions
00544     DestIterator yd(upperleftd);
00545 
00546     int count = 0;
00547     i = 0;
00548     for(y=0; y != h; ++y, ++yd.y)
00549     {
00550         DestIterator xd(yd);
00551         for(x = 0; x != w; ++x, ++xd.x, ++i)
00552         {
00553             if(label[i] == -1) continue;
00554 
00555             if(label[i] == i)
00556             {
00557                 label[i] = count++;
00558             }
00559             else
00560             {
00561                 label[i] = label[label[i]];
00562             }
00563             da.set(label[i]+1, xd);
00564         }
00565     }
00566 
00567     return count;
00568 }
00569 template <class SrcIterator, class SrcAccessor,
00570           class DestIterator, class DestAccessor,
00571           class ValueType, class EqualityFunctor>
00572 inline
00573 int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src,
00574                              pair<DestIterator, DestAccessor> dest,
00575                              bool eight_neighbors,
00576                              ValueType background_value, EqualityFunctor equal)
00577 {
00578     return labelImageWithBackground(src.first, src.second, src.third,
00579                                     dest.first, dest.second,
00580                                     eight_neighbors, background_value, equal);
00581 }
00582 
00583 template <class SrcIterator, class SrcAccessor,
00584           class DestIterator, class DestAccessor,
00585           class ValueType>
00586 inline
00587 int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src,
00588                              pair<DestIterator, DestAccessor> dest,
00589                              bool eight_neighbors,
00590                              ValueType background_value)
00591 {
00592     return labelImageWithBackground(src.first, src.second, src.third,
00593                             dest.first, dest.second,
00594                             eight_neighbors, background_value,
00595                             std::equal_to<typename SrcAccessor::value_type>());
00596 }
00597 
00598 template <class SrcIterator, class SrcAccessor,
00599           class DestIterator, class DestAccessor,
00600           class ValueType>
00601 inline
00602 int labelImageWithBackground(SrcIterator upperlefts,
00603                SrcIterator lowerrights, SrcAccessor sa,
00604                DestIterator upperleftd, DestAccessor da,
00605                bool eight_neighbors,
00606                ValueType background_value)
00607 {
00608     return labelImageWithBackground(upperlefts, lowerrights, sa,
00609                             upperleftd, da,
00610                             eight_neighbors, background_value,
00611                             std::equal_to<typename SrcAccessor::value_type>());
00612 }
00613 
00614 /********************************************************/
00615 /*                                                      */
00616 /*            regionImageToCrackEdgeImage               */
00617 /*                                                      */
00618 /********************************************************/
00619 
00620 /** \brief Transform a labeled image into a crack edge image.
00621 
00622     This algorithm inserts border pixels (so called "crack edges"
00623     between regions in a labeled image like this (<TT>a</TT> and
00624     <TT>c</TT> are the original labels, and <TT>0</TT> is the value of
00625     <TT>edge_marker</TT> and denotes the inserted edges):
00626 
00627     \code
00628        original image     insert zero- and one-cells
00629 
00630                                          a 0 c c c
00631           a c c                          a 0 0 0 c
00632           a a c               =>         a a a 0 c
00633           a a a                          a a a 0 0
00634                                          a a a a a
00635     \endcode
00636 
00637     The algorithm assumes that the original labeled image contains
00638     no background. Therefore, it is suitable as a post-processing
00639     operation of \ref labelImage() or \ref seededRegionGrowing().
00640 
00641     The destination image must be twice the size of the original
00642     (precisely, <TT>(2*w-1)</TT> by <TT>(2*h-1)</TT> pixels). The
00643     source value type (<TT>SrcAccessor::value-type</TT>) must be
00644     equality-comparable.
00645 
00646     <b> Declarations:</b>
00647 
00648     pass arguments explicitly:
00649     \code
00650     namespace vigra {
00651         template <class SrcIterator, class SrcAccessor,
00652                   class DestIterator, class DestAccessor, class DestValue>
00653         void regionImageToCrackEdgeImage(
00654                        SrcIterator sul, SrcIterator slr, SrcAccessor sa,
00655                        DestIterator dul, DestAccessor da,
00656                        DestValue edge_marker)
00657     }
00658     \endcode
00659 
00660     use argument objects in conjuction with \ref ArgumentObjectFactories:
00661     \code
00662     namespace vigra {
00663         template <class SrcIterator, class SrcAccessor,
00664                   class DestIterator, class DestAccessor, class DestValue>
00665         inline
00666         void regionImageToCrackEdgeImage(
00667                    triple<SrcIterator, SrcIterator, SrcAccessor> src,
00668                    pair<DestIterator, DestAccessor> dest,
00669                    DestValue edge_marker)
00670     }
00671     \endcode
00672 
00673     <b> Usage:</b>
00674 
00675         <b>\#include</b> "<a href="labelimage_8hxx-source.html">vigra/labelimage.hxx</a>"<br>
00676     Namespace: vigra
00677 
00678     \code
00679     vigra::BImage src(w,h);
00680     vigra::IImage labels(w,h);
00681     vigra::IImage cellgrid(2*w-1, 2*h-1);
00682 
00683     // threshold at 128
00684     vigra::transformImage(srcImageRange(src), destImage(src),
00685        vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
00686                                                     128, 256, 0, 255));
00687 
00688     // find 4-connected regions
00689     vigra::labelImage(srcImageRange(src), destImage(labels), false);
00690 
00691     // create cell grid image, mark edges with 0
00692     vigra::regionImageToCrackEdgeImage(srcImageRange(labels), destImage(cellgrid), 0);
00693     \endcode
00694 
00695     <b> Required Interface:</b>
00696 
00697     \code
00698     ImageIterator src_upperleft, src_lowerright;
00699     ImageIterator dest_upperleft;
00700 
00701     SrcAccessor src_accessor;
00702     DestAccessor dest_accessor;
00703 
00704     SrcAccessor::value_type u = src_accessor(src_upperleft);
00705 
00706     u != u
00707 
00708     DestValue edge_marker;
00709     dest_accessor.set(edge_marker, dest_upperleft);
00710     \endcode
00711 
00712     <b> Preconditions:</b>
00713 
00714     The destination image must have twice the size of the source:
00715     \code
00716     w_dest = 2 * w_src - 1
00717     h_dest = 2 * h_src - 1
00718     \endcode
00719 */
00720 template <class SrcIterator, class SrcAccessor,
00721           class DestIterator, class DestAccessor, class DestValue>
00722 void regionImageToCrackEdgeImage(
00723                SrcIterator sul, SrcIterator slr, SrcAccessor sa,
00724                DestIterator dul, DestAccessor da,
00725                DestValue edge_marker)
00726 {
00727     int w = slr.x - sul.x;
00728     int h = slr.y - sul.y;
00729     int x,y;
00730 
00731     static const Diff2D right(1,0);
00732     static const Diff2D left(-1,0);
00733     static const Diff2D bottomright(1,1);
00734     static const Diff2D bottom(0,1);
00735     static const Diff2D top(0,-1);
00736 
00737     SrcIterator iy = sul;
00738     DestIterator dy = dul;
00739 
00740     for(y=0; y<h-1; ++y, ++iy.y, dy.y+=2)
00741     {
00742         SrcIterator ix = iy;
00743         DestIterator dx = dy;
00744 
00745         for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
00746         {
00747             da.set(sa(ix), dx);
00748             da.set(sa(ix), dx, bottomright);
00749 
00750             if(sa(ix, right) != sa(ix))
00751             {
00752                 da.set(edge_marker, dx, right);
00753             }
00754             else
00755             {
00756                 da.set(sa(ix), dx, right);
00757             }
00758             if(sa(ix, bottom) != sa(ix))
00759             {
00760                 da.set(edge_marker, dx, bottom);
00761             }
00762             else
00763             {
00764                 da.set(sa(ix), dx, bottom);
00765             }
00766 
00767         }
00768 
00769         da.set(sa(ix), dx);
00770         if(sa(ix, bottom) != sa(ix))
00771         {
00772             da.set(edge_marker, dx, bottom);
00773         }
00774         else
00775         {
00776             da.set(sa(ix), dx, bottom);
00777         }
00778     }
00779 
00780     SrcIterator ix = iy;
00781     DestIterator dx = dy;
00782 
00783     for(x=0; x<w-1; ++x, ++ix.x, dx.x+=2)
00784     {
00785         da.set(sa(ix), dx);
00786         if(sa(ix, right) != sa(ix))
00787         {
00788             da.set(edge_marker, dx, right);
00789         }
00790         else
00791         {
00792             da.set(sa(ix), dx, right);
00793         }
00794     }
00795     da.set(sa(ix), dx);
00796 
00797     dy = dul + Diff2D(1,1);
00798 
00799     // find missing 0-cells
00800     for(y=0; y<h-1; ++y, dy.y+=2)
00801     {
00802         DestIterator dx = dy;
00803 
00804         for(x=0; x<w-1; ++x, dx.x+=2)
00805         {
00806             static const Diff2D dist[] = {right, top, left, bottom };
00807 
00808             int i;
00809             for(i=0; i<4; ++i)
00810             {
00811                 if(da(dx, dist[i]) == edge_marker) break;
00812             }
00813 
00814             if(i < 4) da.set(edge_marker, dx);
00815         }
00816     }
00817 }
00818 
00819 template <class SrcIterator, class SrcAccessor,
00820           class DestIterator, class DestAccessor, class DestValue>
00821 inline
00822 void regionImageToCrackEdgeImage(
00823            triple<SrcIterator, SrcIterator, SrcAccessor> src,
00824            pair<DestIterator, DestAccessor> dest,
00825            DestValue edge_marker)
00826 {
00827     regionImageToCrackEdgeImage(src.first, src.second, src.third,
00828                                         dest.first, dest.second,
00829                                         edge_marker);
00830 }
00831 
00832 /********************************************************/
00833 /*                                                      */
00834 /*                regionImageToEdgeImage                */
00835 /*                                                      */
00836 /********************************************************/
00837 
00838 /** \brief Transform a labeled image into an edge image.
00839 
00840     This algorithm marks all pixels with the given <TT>edge_marker</TT>
00841     which belong to a different region (label) than their right or lower
00842     neighbors:
00843 
00844     \code
00845        original image                     edges
00846                                  (assuming edge_marker == 1)
00847 
00848           a c c                            1 1 *
00849           a a c               =>           * 1 1
00850           a a a                            * * *
00851     \endcode
00852 
00853     The non-edge pixels of the destination image will not be touched.
00854     The source value type (<TT>SrcAccessor::value-type</TT>) must be
00855     equality-comparable.
00856 
00857     <b> Declarations:</b>
00858 
00859     pass arguments explicitly:
00860     \code
00861     namespace vigra {
00862         template <class SrcIterator, class SrcAccessor,
00863                   class DestIterator, class DestAccessor, class DestValue>
00864         void regionImageToEdgeImage(
00865                        SrcIterator sul, SrcIterator slr, SrcAccessor sa,
00866                        DestIterator dul, DestAccessor da,
00867                        DestValue edge_marker)
00868     }
00869     \endcode
00870 
00871     use argument objects in conjuction with \ref ArgumentObjectFactories:
00872     \code
00873     namespace vigra {
00874         template <class SrcIterator, class SrcAccessor,
00875                   class DestIterator, class DestAccessor, class DestValue>
00876         inline
00877         void regionImageToEdgeImage(
00878                    triple<SrcIterator, SrcIterator, SrcAccessor> src,
00879                    pair<DestIterator, DestAccessor> dest,
00880                    DestValue edge_marker)
00881     }
00882     \endcode
00883 
00884     <b> Usage:</b>
00885 
00886         <b>\#include</b> "<a href="labelimage_8hxx-source.html">vigra/labelimage.hxx</a>"<br>
00887     Namespace: vigra
00888 
00889     \code
00890     vigra::BImage src(w,h);
00891     vigra::IImage labels(w,h);
00892     vigra::IImage edges(w, h);
00893     edges = 255;  // init background (non-edge) to 255
00894 
00895     // threshold at 128
00896     vigra::transformImage(srcImageRange(src), destImage(src),
00897       vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
00898                                                     128, 256, 0, 255));
00899 
00900     // find 4-connected regions
00901     vigra::labelImage(srcImageRange(src), destImage(labels), false);
00902 
00903     // create edge image, mark edges with 0
00904     vigra::regionImageToEdgeImage(srcImageRange(labels), destImage(edges), 0);
00905     \endcode
00906 
00907     <b> Required Interface:</b>
00908 
00909     \code
00910     ImageIterator src_upperleft, src_lowerright;
00911     ImageIterator dest_upperleft;
00912 
00913     SrcAccessor src_accessor;
00914     DestAccessor dest_accessor;
00915 
00916     SrcAccessor::value_type u = src_accessor(src_upperleft);
00917 
00918     u != u
00919 
00920     DestValue edge_marker;
00921     dest_accessor.set(edge_marker, dest_upperleft);
00922     \endcode
00923 
00924 */
00925 template <class SrcIterator, class SrcAccessor,
00926           class DestIterator, class DestAccessor, class DestValue>
00927 void regionImageToEdgeImage(
00928                SrcIterator sul, SrcIterator slr, SrcAccessor sa,
00929                DestIterator dul, DestAccessor da,
00930                DestValue edge_marker)
00931 {
00932     int w = slr.x - sul.x;
00933     int h = slr.y - sul.y;
00934     int x,y;
00935 
00936     static const Diff2D right(1,0);
00937     static const Diff2D left(-1,0);
00938     static const Diff2D bottomright(1,1);
00939     static const Diff2D bottom(0,1);
00940     static const Diff2D top(0,-1);
00941 
00942     SrcIterator iy = sul;
00943     DestIterator dy = dul;
00944 
00945     for(y=0; y<h-1; ++y, ++iy.y, ++dy.y)
00946     {
00947         SrcIterator ix = iy;
00948         DestIterator dx = dy;
00949 
00950         for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
00951         {
00952             if(sa(ix, right) != sa(ix))
00953             {
00954                 da.set(edge_marker, dx);
00955             }
00956             if(sa(ix, bottom) != sa(ix))
00957             {
00958                 da.set(edge_marker, dx);
00959             }
00960         }
00961 
00962         if(sa(ix, bottom) != sa(ix))
00963         {
00964             da.set(edge_marker, dx);
00965         }
00966     }
00967 
00968     SrcIterator ix = iy;
00969     DestIterator dx = dy;
00970 
00971     for(x=0; x<w-1; ++x, ++ix.x, ++dx.x)
00972     {
00973         if(sa(ix, right) != sa(ix))
00974         {
00975             da.set(edge_marker, dx);
00976         }
00977     }
00978 }
00979 
00980 template <class SrcIterator, class SrcAccessor,
00981           class DestIterator, class DestAccessor, class DestValue>
00982 inline
00983 void regionImageToEdgeImage(
00984            triple<SrcIterator, SrcIterator, SrcAccessor> src,
00985            pair<DestIterator, DestAccessor> dest,
00986            DestValue edge_marker)
00987 {
00988     regionImageToEdgeImage(src.first, src.second, src.third,
00989                                         dest.first, dest.second,
00990                                         edge_marker);
00991 }
00992 
00993 //@}
00994 
00995 } // namespace vigra
00996 
00997 #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.2.0 (7 Aug 2003)