[ 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.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)