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

vigra/labelimage.hxx VIGRA

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