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