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

© Ullrich Köthe (koethe@informatik.uni-hamburg.de)
Cognitive Systems Group, University of Hamburg, Germany

html generated using doxygen and Python
VIGRA 1.4.0 (21 Dec 2005)