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

vigra/labelvolume.hxx |

    00001 /************************************************************************/
    00002 /*                                                                      */
    00003 /*     Copyright 2006-2007 by F. Heinrich, B. Seppke, 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 #ifndef VIGRA_LABELVOLUME_HXX
    00037 #define VIGRA_LABELVOLUME_HXX
    00038
    00039
    00040 #include "voxelneighborhood.hxx"
    00041 #include "multi_array.hxx"
    00042 #include "union_find.hxx"
    00043
    00044 namespace vigra{
    00045
    00046 /** \addtogroup Labeling Connected Components Labeling
    00047      The 3-dimensional connected components algorithms may use either 6 or 26 connectivity.
    00048      By means of a functor the merge criterium can be defined arbitrarily.
    00049 */
    00050 //@{
    00051
    00052 /********************************************************/
    00053 /*                                                      */
    00054 /*                        labelVolume                   */
    00055 /*                                                      */
    00056 /********************************************************/
    00057
    00058 /** \brief Find the connected components of a segmented volume.
    00059
    00060     <b> Declarations:</b>
    00061
    00062     pass arguments explicitly:
    00063     \code
    00064     namespace vigra {
    00065
    00066         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00067                   class DestIterator, class DestAccessor,
    00068                   class Neighborhood3D>
    00069         unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00070                                  DestIterator d_Iter, DestAccessor da,
    00071                                  Neighborhood3D neighborhood3D);
    00072
    00073         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00074                           class DestIterator, class DestAccessor,
    00075                           class Neighborhood3D, class EqualityFunctor>
    00076         unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00077                                  DestIterator d_Iter, DestAccessor da,
    00078                                  Neighborhood3D neighborhood3D, EqualityFunctor equal);
    00079
    00080     }
    00081     \endcode
    00082
    00083     use argument objects in conjunction with \ref ArgumentObjectFactories :
    00084     \code
    00085     namespace vigra {
    00086
    00087         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00088                   class DestIterator, class DestAccessor,
    00089                   class Neighborhood3D>
    00090         unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00091                                  pair<DestIterator, DestAccessor> dest,
    00092                                  Neighborhood3D neighborhood3D);
    00093
    00094         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00095                  class DestIterator, class DestAccessor,
    00096                  class Neighborhood3D, class EqualityFunctor>
    00097         unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00098                                  pair<DestIterator, DestAccessor> dest,
    00099                                  Neighborhood3D neighborhood3D, EqualityFunctor equal);
    00100
    00101     }
    00102     \endcode
    00103
    00104     use with 3D-Six-Neighborhood:
    00105     \code
    00106     namespace vigra {
    00107
    00108         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00109                   class DestIterator, class DestAccessor>
    00110         unsigned int labelVolumeSix(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00111                                     pair<DestIterator, DestAccessor> dest);
    00112
    00113     }
    00114     \endcode
    00115
    00116     Connected components are defined as regions with uniform voxel
    00117     values. Thus, <TT>SrcAccessor::value_type</TT> either must be
    00118     equality comparable (first form), or an EqualityFunctor must be
    00119     provided that realizes the desired predicate (second form). The
    00120     destination's value type should be large enough to hold the labels
    00121     without overflow. Region numbers will be a consecutive sequence
    00122     starting with one and ending with the region number returned by
    00123     the function (inclusive).
    00124
    00125     Return:  the number of regions found (= largest region label)
    00126
    00127     <b> Usage:</b>
    00128
    00129     <b>\#include</b> <<a href="labelvolume_8hxx-source.html">vigra/labelvolume.hxx</a>><br>
    00130     Namespace: vigra
    00131
    00132     \code
    00133     typedef vigra::MultiArray<3,int> IntVolume;
    00134     IntVolume src(IntVolume::difference_type(w,h,d));
    00135     IntVolume dest(IntVolume::difference_type(w,h,d));
    00136
    00137     // find 6-connected regions
    00138     int max_region_label = vigra::labelVolumeSix(srcMultiArrayRange(src), destMultiArray(dest));
    00139
    00140     // find 26-connected regions
    00141     int max_region_label = vigra::labelVolume(srcMultiArrayRange(src), destMultiArray(dest), NeighborCode3DTwentySix());
    00142     \endcode
    00143
    00144     <b> Required Interface:</b>
    00145
    00146     \code
    00147     SrcIterator src_begin;
    00148     SrcShape shape;
    00149     DestIterator dest_begin;
    00150
    00151     SrcAccessor src_accessor;
    00152     DestAccessor dest_accessor;
    00153
    00154     SrcAccessor::value_type u = src_accessor(src_begin);
    00155
    00156     u == u                      // first form
    00157
    00158     EqualityFunctor equal;      // second form
    00159     equal(u, u)                 // second form
    00160
    00161     int i;
    00162     dest_accessor.set(i, dest_begin);
    00163     \endcode
    00164
    00165 */
    00166 doxygen_overloaded_function(template <...> unsigned int labelVolume)
    00167
    00168 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00169           class DestIterator, class DestAccessor,
    00170           class Neighborhood3D>
    00171 unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00172                          DestIterator d_Iter, DestAccessor da,
    00173                          Neighborhood3D neighborhood3D)
    00174 {
    00175         return labelVolume(s_Iter, srcShape, sa, d_Iter, da, neighborhood3D, std::equal_to<typename SrcAccessor::value_type>());
    00176 }
    00177
    00178 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00179           class DestIterator, class DestAccessor,
    00180           class Neighborhood3D>
    00181 unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00182                          pair<DestIterator, DestAccessor> dest,
    00183                          Neighborhood3D neighborhood3D)
    00184 {
    00185     return labelVolume(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, std::equal_to<typename SrcAccessor::value_type>());
    00186 }
    00187
    00188 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00189           class DestIterator, class DestAccessor,
    00190           class Neighborhood3D, class EqualityFunctor>
    00191 unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00192                          pair<DestIterator, DestAccessor> dest,
    00193                          Neighborhood3D neighborhood3D, EqualityFunctor equal)
    00194 {
    00195     return labelVolume(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, equal);
    00196 }
    00197
    00198 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00199           class DestIterator, class DestAccessor,
    00200           class Neighborhood3D, class EqualityFunctor>
    00201 unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00202                          DestIterator d_Iter, DestAccessor da,
    00203                          Neighborhood3D, EqualityFunctor equal)
    00204 {
    00205     typedef typename DestAccessor::value_type LabelType;
    00206
    00207     //basically needed for iteration and border-checks
    00208     int w = srcShape[0], h = srcShape[1], d = srcShape[2];
    00209     int x,y,z;
    00210
    00211     // temporary image to store region labels
    00212     detail::UnionFindArray<LabelType>  label;
    00213
    00214     //Declare traversers for all three dims at target
    00215     SrcIterator zs = s_Iter;
    00216     DestIterator zd = d_Iter;
    00217
    00218     // initialize the neighborhood traversers
    00219     NeighborOffsetCirculator<Neighborhood3D> nce(Neighborhood3D::CausalLast);
    00220     ++nce;
    00221     // pass 1: scan image from upper left front to lower right back
    00222     // to find connected components
    00223
    00224     // Each component will be represented by a tree of pixels. Each
    00225     // pixel contains the scan order address of its parent in the
    00226     // tree.  In order for pass 2 to work correctly, the parent must
    00227     // always have a smaller scan order address than the child.
    00228     // Therefore, we can merge trees only at their roots, because the
    00229     // root of the combined tree must have the smallest scan order
    00230     // address among all the tree's pixels/ nodes.  The root of each
    00231     // tree is distinguished by pointing to itself (it contains its
    00232     // own scan order address). This condition is enforced whenever a
    00233     // new region is found or two regions are merged
    00234     for(z = 0; z != d; ++z, ++zs.dim2(), ++zd.dim2())
    00235     {
    00236         SrcIterator ys(zs);
    00237         DestIterator yd(zd);
    00238
    00239         for(y = 0; y != h; ++y, ++ys.dim1(), ++yd.dim1())
    00240         {
    00241             SrcIterator xs(ys);
    00242             DestIterator xd(yd);
    00243
    00244             for(x = 0; x != w; ++x, ++xs.dim0(), ++xd.dim0())
    00245             {
    00246                 LabelType currentLabel = label.nextFreeLabel();
    00247
    00248                 //queck whether there is a special border treatment to be used or not
    00249                 AtVolumeBorder atBorder = isAtVolumeBorderCausal(x,y,z,w,h,d);
    00250
    00251                 //We are not at the border!
    00252                 if(atBorder == NotAtBorder)
    00253                 {
    00254                     NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::CausalFirst);
    00255
    00256                     do
    00257                     {
    00258                         // if colors are equal
    00259                         if(equal(sa(xs), sa(xs, *nc)))
    00260                         {
    00261                             currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
    00262                         }
    00263                         ++nc;
    00264                     }
    00265                     while(nc!=nce);
    00266                 }
    00267                 else //we are at a border - handle this!!
    00268                 {
    00269                     NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::nearBorderDirectionsCausal(atBorder,0));
    00270                     int j=0;
    00271                     while(nc.direction() != Neighborhood3D::Error)
    00272                     {
    00273                         //   colors equal???
    00274                         if(equal(sa(xs), sa(xs, *nc)))
    00275                         {
    00276                             currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
    00277                         }
    00278                         nc.turnTo(Neighborhood3D::nearBorderDirectionsCausal(atBorder,++j));
    00279                     }
    00280                 }
    00281                 da.set(label.finalizeLabel(currentLabel), xd);
    00282             }
    00283         }
    00284     }
    00285
    00286     LabelType count = label.makeContiguous();
    00287
    00288     // pass 2: assign one label to each region (tree)
    00289     // so that labels form a consecutive sequence 1, 2, ...
    00290     zd = d_Iter;
    00291     for(z=0; z != d; ++z, ++zd.dim2())
    00292     {
    00293         DestIterator yd(zd);
    00294
    00295         for(y=0; y != h; ++y, ++yd.dim1())
    00296         {
    00297             DestIterator xd(yd);
    00298
    00299             for(x = 0; x != w; ++x, ++xd.dim0())
    00300             {
    00301                 da.set(label[da(xd)], xd);
    00302             }
    00303         }
    00304     }
    00305     return count;
    00306 }
    00307
    00308 /********************************************************/
    00309 /*                                                      */
    00310 /*                    labelVolumeSix                    */
    00311 /*                                                      */
    00312 /********************************************************/
    00313
    00314 /** \brief Find the connected components of a segmented volume
    00315      using the 6-neighborhood.
    00316
    00317      See \ref labelVolume() for detailed documentation.
    00318
    00319 */
    00320 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00321           class DestIterator, class DestAccessor>
    00322 unsigned int labelVolumeSix(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00323                             pair<DestIterator, DestAccessor> dest)
    00324 {
    00325     return labelVolume(src.first, src.second, src.third, dest.first, dest.second, NeighborCode3DSix(), std::equal_to<typename SrcAccessor::value_type>());
    00326 }
    00327
    00328
    00329
    00330
    00331 /********************************************************/
    00332 /*                                                      */
    00333 /*               labelVolumeWithBackground              */
    00334 /*                                                      */
    00335 /********************************************************/
    00336
    00337 /** \brief Find the connected components of a segmented volume,
    00338      excluding the background from labeling.
    00339
    00340     <b> Declarations:</b>
    00341
    00342     pass arguments explicitly:
    00343     \code
    00344     namespace vigra {
    00345
    00346         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00347                           class DestIterator, class DestAccessor,
    00348                           class Neighborhood3D, class ValueType>
    00349         unsigned int labelVolumeWithBackground(    SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00350                                                           DestIterator d_Iter, DestAccessor da,
    00351                                                           Neighborhood3D neighborhood3D, ValueType background_value);
    00352
    00353         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00354                           class DestIterator, class DestAccessor,
    00355                           class Neighborhood3D, class ValueType, class EqualityFunctor>
    00356         unsigned int labelVolumeWithBackground(    SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00357                                                             DestIterator d_Iter, DestAccessor da,
    00358                                                           Neighborhood3D neighborhood3D, ValueType background_value,
    00359                                                             EqualityFunctor equal);
    00360
    00361     }
    00362     \endcode
    00363
    00364     use argument objects in conjunction with \ref ArgumentObjectFactories :
    00365     \code
    00366     namespace vigra {
    00367
    00368         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00369                           class DestIterator, class DestAccessor,
    00370                           class Neighborhood3D, class ValueType>
    00371         unsigned int labelVolumeWithBackground(    triple<SrcIterator, SrcShape, SrcAccessor> src,
    00372                                                           pair<DestIterator, DestAccessor> dest,
    00373                                                           Neighborhood3D neighborhood3D, ValueType background_value);
    00374
    00375         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00376                           class DestIterator, class DestAccessor,
    00377                           class Neighborhood3D, class ValueType, class EqualityFunctor>
    00378         unsigned int labelVolumeWithBackground(    triple<SrcIterator, SrcShape, SrcAccessor> src,
    00379                                                         pair<DestIterator, DestAccessor> dest,
    00380                                                         Neighborhood3D neighborhood3D, ValueType background_value,
    00381                                                         EqualityFunctor equal);
    00382
    00383     }
    00384     \endcode
    00385
    00386     Connected components are defined as regions with uniform voxel
    00387     values. Thus, <TT>SrcAccessor::value_type</TT> either must be
    00388     equality comparable (first form), or an EqualityFunctor must be
    00389     provided that realizes the desired predicate (second form). All
    00390     voxel equal to the given '<TT>background_value</TT>' are ignored
    00391     when determining connected components and remain untouched in the
    00392     destination volume.
    00393
    00394     The destination's value type should be large enough to hold the
    00395     labels without overflow. Region numbers will be a consecutive
    00396     sequence starting with one and ending with the region number
    00397     returned by the function (inclusive).
    00398
    00399     Return:  the number of regions found (= largest region label)
    00400
    00401     <b> Usage:</b>
    00402
    00403     <b>\#include</b> <<a href="labelvolume_8hxx-source.html">vigra/labelvolume.hxx</a>><br>
    00404     Namespace: vigra
    00405
    00406     \code
    00407     typedef vigra::MultiArray<3,int> IntVolume;
    00408     IntVolume src(IntVolume::difference_type(w,h,d));
    00409     IntVolume dest(IntVolume::difference_type(w,h,d));
    00410
    00411     // find 6-connected regions
    00412     int max_region_label = vigra::labelVolumeWithBackground(
    00413     srcMultiArrayRange(src), destMultiArray(dest), NeighborCode3DSix(), 0);
    00414     \endcode
    00415
    00416     <b> Required Interface:</b>
    00417
    00418     \code
    00419     SrcIterator src_begin;
    00420     SrcShape shape;
    00421     DestIterator dest_begin;
    00422
    00423     SrcAccessor src_accessor;
    00424     DestAccessor dest_accessor;
    00425
    00426     SrcAccessor::value_type u = src_accessor(src_begin);
    00427
    00428     u == u                      // first form
    00429
    00430     EqualityFunctor equal;      // second form
    00431     equal(u, u)                 // second form
    00432
    00433     int i;
    00434     dest_accessor.set(i, dest_begin);
    00435     \endcode
    00436
    00437 */
    00438 doxygen_overloaded_function(template <...> unsigned int labelVolumeWithBackground)
    00439
    00440 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00441           class DestIterator, class DestAccessor,
    00442           class Neighborhood3D,
    00443           class ValueType>
    00444 unsigned int labelVolumeWithBackground(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00445                                        DestIterator d_Iter, DestAccessor da,
    00446                                        Neighborhood3D neighborhood3D, ValueType backgroundValue)
    00447 {
    00448     return labelVolumeWithBackground(s_Iter, srcShape, sa, d_Iter, da, neighborhood3D, backgroundValue, std::equal_to<typename SrcAccessor::value_type>());
    00449 }
    00450
    00451 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00452           class DestIterator, class DestAccessor,
    00453           class Neighborhood3D,
    00454           class ValueType>
    00455 unsigned int labelVolumeWithBackground(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00456                                        pair<DestIterator, DestAccessor> dest,
    00457                                        Neighborhood3D neighborhood3D, ValueType backgroundValue)
    00458 {
    00459     return labelVolumeWithBackground(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, backgroundValue, std::equal_to<typename SrcAccessor::value_type>());
    00460 }
    00461
    00462 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00463           class DestIterator, class DestAccessor,
    00464           class Neighborhood3D,
    00465           class ValueType, class EqualityFunctor>
    00466 unsigned int labelVolumeWithBackground(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00467                                        pair<DestIterator, DestAccessor> dest,
    00468                                        Neighborhood3D neighborhood3D, ValueType backgroundValue, EqualityFunctor equal)
    00469 {
    00470     return labelVolumeWithBackground(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, backgroundValue, equal);
    00471 }
    00472
    00473 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00474           class DestIterator, class DestAccessor,
    00475           class Neighborhood3D,
    00476           class ValueType, class EqualityFunctor>
    00477 unsigned int labelVolumeWithBackground(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00478                                        DestIterator d_Iter, DestAccessor da,
    00479                                        Neighborhood3D,
    00480                                        ValueType backgroundValue, EqualityFunctor equal)
    00481 {
    00482     typedef typename DestAccessor::value_type LabelType;
    00483
    00484     //basically needed for iteration and border-checks
    00485     int w = srcShape[0], h = srcShape[1], d = srcShape[2];
    00486     int x,y,z;
    00487
    00488     // temporary image to store region labels
    00489     detail::UnionFindArray<LabelType>  label;
    00490
    00491     //Declare traversers for all three dims at target
    00492     SrcIterator zs = s_Iter;
    00493     DestIterator zd = d_Iter;
    00494
    00495     // initialize the neighborhood traversers
    00496     NeighborOffsetCirculator<Neighborhood3D> nce(Neighborhood3D::CausalLast);
    00497     ++nce;
    00498     // pass 1: scan image from upper left front to lower right back
    00499     // to find connected components
    00500
    00501     // Each component will be represented by a tree of pixels. Each
    00502     // pixel contains the scan order address of its parent in the
    00503     // tree.  In order for pass 2 to work correctly, the parent must
    00504     // always have a smaller scan order address than the child.
    00505     // Therefore, we can merge trees only at their roots, because the
    00506     // root of the combined tree must have the smallest scan order
    00507     // address among all the tree's pixels/ nodes.  The root of each
    00508     // tree is distinguished by pointing to itself (it contains its
    00509     // own scan order address). This condition is enforced whenever a
    00510     // new region is found or two regions are merged
    00511     for(z = 0; z != d; ++z, ++zs.dim2(), ++zd.dim2())
    00512     {
    00513         SrcIterator ys(zs);
    00514         DestIterator yd(zd);
    00515
    00516         for(y = 0; y != h; ++y, ++ys.dim1(), ++yd.dim1())
    00517         {
    00518             SrcIterator xs(ys);
    00519             DestIterator xd(yd);
    00520
    00521             for(x = 0; x != w; ++x, ++xs.dim0(), ++xd.dim0())
    00522             {
    00523                 if(equal(sa(xs), backgroundValue))
    00524                 {
    00525                     da.set(label[0], xd);
    00526                     continue;
    00527                 }
    00528
    00529                 LabelType currentLabel = label.nextFreeLabel();
    00530
    00531                 //queck whether there is a special border treatment to be used or not
    00532                 AtVolumeBorder atBorder = isAtVolumeBorderCausal(x,y,z,w,h,d);
    00533
    00534                 //We are not at the border!
    00535                 if(atBorder == NotAtBorder)
    00536                 {
    00537                     NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::CausalFirst);
    00538
    00539                     do
    00540                     {
    00541                         // if colors are equal
    00542                         if(equal(sa(xs), sa(xs, *nc)))
    00543                         {
    00544                             currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
    00545                         }
    00546                         ++nc;
    00547                     }
    00548                     while(nc!=nce);
    00549                 }
    00550                 else //we are at a border - handle this!!
    00551                 {
    00552                     NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::nearBorderDirectionsCausal(atBorder,0));
    00553                     int j=0;
    00554                     while(nc.direction() != Neighborhood3D::Error)
    00555                     {
    00556                         //   colors equal???
    00557                         if(equal(sa(xs), sa(xs, *nc)))
    00558                         {
    00559                             currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
    00560                         }
    00561                         nc.turnTo(Neighborhood3D::nearBorderDirectionsCausal(atBorder,++j));
    00562                     }
    00563                 }
    00564                 da.set(label.finalizeLabel(currentLabel), xd);
    00565             }
    00566         }
    00567     }
    00568
    00569     LabelType count = label.makeContiguous();
    00570
    00571     // pass 2: assign one label to each region (tree)
    00572     // so that labels form a consecutive sequence 1, 2, ...
    00573     zd = d_Iter;
    00574     for(z=0; z != d; ++z, ++zd.dim2())
    00575     {
    00576         DestIterator yd(zd);
    00577
    00578         for(y=0; y != h; ++y, ++yd.dim1())
    00579         {
    00580             DestIterator xd(yd);
    00581
    00582             for(x = 0; x != w; ++x, ++xd.dim0())
    00583             {
    00584                 da.set(label[da(xd)], xd);
    00585             }
    00586         }
    00587     }
    00588     return count;
    00589 }
    00590
    00591 //@}
    00592
    00593 } //end of namespace vigra
    00594
    00595 #endif //VIGRA_LABELVOLUME_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.7.1 (3 Dec 2010)