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

vigra/labelimage.hxx

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

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
VIGRA 1.6.0 (5 Nov 2009)