[ 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 criterion 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> <vigra/labelvolume.hxx><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
    00169 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00170           class DestIterator, class DestAccessor,
    00171           class Neighborhood3D>
    00172 unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00173                          DestIterator d_Iter, DestAccessor da,
    00174                          Neighborhood3D neighborhood3D)
    00175 {
    00176         return labelVolume(s_Iter, srcShape, sa, d_Iter, da, neighborhood3D, std::equal_to<typename SrcAccessor::value_type>());
    00177 }
    00178
    00179 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00180           class DestIterator, class DestAccessor,
    00181           class Neighborhood3D>
    00182 unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00183                          pair<DestIterator, DestAccessor> dest,
    00184                          Neighborhood3D neighborhood3D)
    00185 {
    00186     return labelVolume(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, std::equal_to<typename SrcAccessor::value_type>());
    00187 }
    00188
    00189 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00190           class DestIterator, class DestAccessor,
    00191           class Neighborhood3D, class EqualityFunctor>
    00192 unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00193                          pair<DestIterator, DestAccessor> dest,
    00194                          Neighborhood3D neighborhood3D, EqualityFunctor equal)
    00195 {
    00196     return labelVolume(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, equal);
    00197 }
    00198
    00199 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00200           class DestIterator, class DestAccessor,
    00201           class Neighborhood3D, class EqualityFunctor>
    00202 unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00203                          DestIterator d_Iter, DestAccessor da,
    00204                          Neighborhood3D, EqualityFunctor equal)
    00205 {
    00206     typedef typename DestAccessor::value_type LabelType;
    00207
    00208     //basically needed for iteration and border-checks
    00209     int w = srcShape[0], h = srcShape[1], d = srcShape[2];
    00210     int x,y,z;
    00211
    00212     // temporary image to store region labels
    00213     detail::UnionFindArray<LabelType>  label;
    00214
    00215     //Declare traversers for all three dims at target
    00216     SrcIterator zs = s_Iter;
    00217     DestIterator zd = d_Iter;
    00218
    00219     // initialize the neighborhood traversers
    00220     NeighborOffsetCirculator<Neighborhood3D> nce(Neighborhood3D::CausalLast);
    00221     ++nce;
    00222     // pass 1: scan image from upper left front to lower right back
    00223     // to find connected components
    00224
    00225     // Each component will be represented by a tree of pixels. Each
    00226     // pixel contains the scan order address of its parent in the
    00227     // tree.  In order for pass 2 to work correctly, the parent must
    00228     // always have a smaller scan order address than the child.
    00229     // Therefore, we can merge trees only at their roots, because the
    00230     // root of the combined tree must have the smallest scan order
    00231     // address among all the tree's pixels/ nodes.  The root of each
    00232     // tree is distinguished by pointing to itself (it contains its
    00233     // own scan order address). This condition is enforced whenever a
    00234     // new region is found or two regions are merged
    00235     for(z = 0; z != d; ++z, ++zs.dim2(), ++zd.dim2())
    00236     {
    00237         SrcIterator ys(zs);
    00238         DestIterator yd(zd);
    00239
    00240         for(y = 0; y != h; ++y, ++ys.dim1(), ++yd.dim1())
    00241         {
    00242             SrcIterator xs(ys);
    00243             DestIterator xd(yd);
    00244
    00245             for(x = 0; x != w; ++x, ++xs.dim0(), ++xd.dim0())
    00246             {
    00247                 LabelType currentLabel = label.nextFreeLabel();
    00248
    00249                 //check whether there is a special border treatment to be used or not
    00250                 AtVolumeBorder atBorder = isAtVolumeBorderCausal(x,y,z,w,h,d);
    00251
    00252                 //We are not at the border!
    00253                 if(atBorder == NotAtBorder)
    00254                 {
    00255                     NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::CausalFirst);
    00256
    00257                     do
    00258                     {
    00259                         // if colors are equal
    00260                         if(equal(sa(xs), sa(xs, *nc)))
    00261                         {
    00262                             currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
    00263                         }
    00264                         ++nc;
    00265                     }
    00266                     while(nc!=nce);
    00267                 }
    00268                 else //we are at a border - handle this!!
    00269                 {
    00270                     NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::nearBorderDirectionsCausal(atBorder,0));
    00271                     int j=0;
    00272                     while(nc.direction() != Neighborhood3D::Error)
    00273                     {
    00274                         /*
    00275                         SrcShape s(x,y,z), sn = s + *nc;
    00276
    00277                         if (sn[0]<0 || sn[0]>=w || sn[1]<0 || sn[1]>=h || sn[2]<0 || sn[2]>=d)
    00278                         {
    00279                           std::cerr << "coordinate error at " << s << ", offset " << *nc << ", index " << (nc).direction() << " at border " <<
    00280                                                                                                                               atBorder << std::endl;
    00281
    00282                         }
    00283                         */
    00284                         //   colors equal???
    00285                         if(equal(sa(xs), sa(xs, *nc)))
    00286                         {
    00287                             currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
    00288                         }
    00289                         nc.turnTo(Neighborhood3D::nearBorderDirectionsCausal(atBorder,++j));
    00290                     }
    00291                 }
    00292                 da.set(label.finalizeLabel(currentLabel), xd);
    00293             }
    00294         }
    00295     }
    00296
    00297     LabelType count = label.makeContiguous();
    00298
    00299     // pass 2: assign one label to each region (tree)
    00300     // so that labels form a consecutive sequence 1, 2, ...
    00301     zd = d_Iter;
    00302     for(z=0; z != d; ++z, ++zd.dim2())
    00303     {
    00304         DestIterator yd(zd);
    00305
    00306         for(y=0; y != h; ++y, ++yd.dim1())
    00307         {
    00308             DestIterator xd(yd);
    00309
    00310             for(x = 0; x != w; ++x, ++xd.dim0())
    00311             {
    00312                 da.set(label[da(xd)], xd);
    00313             }
    00314         }
    00315     }
    00316     return count;
    00317 }
    00318
    00319 /********************************************************/
    00320 /*                                                      */
    00321 /*                    labelVolumeSix                    */
    00322 /*                                                      */
    00323 /********************************************************/
    00324
    00325 /** \brief Find the connected components of a segmented volume
    00326      using the 6-neighborhood.
    00327
    00328      See \ref labelVolume() for detailed documentation.
    00329
    00330 */
    00331 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00332           class DestIterator, class DestAccessor>
    00333 unsigned int labelVolumeSix(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00334                             pair<DestIterator, DestAccessor> dest)
    00335 {
    00336     return labelVolume(src.first, src.second, src.third, dest.first, dest.second, NeighborCode3DSix(), std::equal_to<typename SrcAccessor::value_type>());
    00337 }
    00338
    00339
    00340
    00341
    00342 /********************************************************/
    00343 /*                                                      */
    00344 /*               labelVolumeWithBackground              */
    00345 /*                                                      */
    00346 /********************************************************/
    00347
    00348 /** \brief Find the connected components of a segmented volume,
    00349      excluding the background from labeling.
    00350
    00351     <b> Declarations:</b>
    00352
    00353     pass arguments explicitly:
    00354     \code
    00355     namespace vigra {
    00356
    00357         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00358                           class DestIterator, class DestAccessor,
    00359                           class Neighborhood3D, class ValueType>
    00360         unsigned int labelVolumeWithBackground(    SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00361                                                           DestIterator d_Iter, DestAccessor da,
    00362                                                           Neighborhood3D neighborhood3D, ValueType background_value);
    00363
    00364         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00365                           class DestIterator, class DestAccessor,
    00366                           class Neighborhood3D, class ValueType, class EqualityFunctor>
    00367         unsigned int labelVolumeWithBackground(    SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00368                                                             DestIterator d_Iter, DestAccessor da,
    00369                                                           Neighborhood3D neighborhood3D, ValueType background_value,
    00370                                                             EqualityFunctor equal);
    00371
    00372     }
    00373     \endcode
    00374
    00375     use argument objects in conjunction with \ref ArgumentObjectFactories :
    00376     \code
    00377     namespace vigra {
    00378
    00379         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00380                           class DestIterator, class DestAccessor,
    00381                           class Neighborhood3D, class ValueType>
    00382         unsigned int labelVolumeWithBackground(    triple<SrcIterator, SrcShape, SrcAccessor> src,
    00383                                                           pair<DestIterator, DestAccessor> dest,
    00384                                                           Neighborhood3D neighborhood3D, ValueType background_value);
    00385
    00386         template <class SrcIterator, class SrcAccessor,class SrcShape,
    00387                           class DestIterator, class DestAccessor,
    00388                           class Neighborhood3D, class ValueType, class EqualityFunctor>
    00389         unsigned int labelVolumeWithBackground(    triple<SrcIterator, SrcShape, SrcAccessor> src,
    00390                                                         pair<DestIterator, DestAccessor> dest,
    00391                                                         Neighborhood3D neighborhood3D, ValueType background_value,
    00392                                                         EqualityFunctor equal);
    00393
    00394     }
    00395     \endcode
    00396
    00397     Connected components are defined as regions with uniform voxel
    00398     values. Thus, <TT>SrcAccessor::value_type</TT> either must be
    00399     equality comparable (first form), or an EqualityFunctor must be
    00400     provided that realizes the desired predicate (second form). All
    00401     voxel equal to the given '<TT>background_value</TT>' are ignored
    00402     when determining connected components and remain untouched in the
    00403     destination volume.
    00404
    00405     The destination's value type should be large enough to hold the
    00406     labels without overflow. Region numbers will be a consecutive
    00407     sequence starting with one and ending with the region number
    00408     returned by the function (inclusive).
    00409
    00410     Return:  the number of regions found (= largest region label)
    00411
    00412     <b> Usage:</b>
    00413
    00414     <b>\#include</b> <vigra/labelvolume.hxx><br>
    00415     Namespace: vigra
    00416
    00417     \code
    00418     typedef vigra::MultiArray<3,int> IntVolume;
    00419     IntVolume src(IntVolume::difference_type(w,h,d));
    00420     IntVolume dest(IntVolume::difference_type(w,h,d));
    00421
    00422     // find 6-connected regions
    00423     int max_region_label = vigra::labelVolumeWithBackground(
    00424     srcMultiArrayRange(src), destMultiArray(dest), NeighborCode3DSix(), 0);
    00425     \endcode
    00426
    00427     <b> Required Interface:</b>
    00428
    00429     \code
    00430     SrcIterator src_begin;
    00431     SrcShape shape;
    00432     DestIterator dest_begin;
    00433
    00434     SrcAccessor src_accessor;
    00435     DestAccessor dest_accessor;
    00436
    00437     SrcAccessor::value_type u = src_accessor(src_begin);
    00438
    00439     u == u                      // first form
    00440
    00441     EqualityFunctor equal;      // second form
    00442     equal(u, u)                 // second form
    00443
    00444     int i;
    00445     dest_accessor.set(i, dest_begin);
    00446     \endcode
    00447
    00448 */
    00449 doxygen_overloaded_function(template <...> unsigned int labelVolumeWithBackground)
    00450
    00451 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00452           class DestIterator, class DestAccessor,
    00453           class Neighborhood3D,
    00454           class ValueType>
    00455 unsigned int labelVolumeWithBackground(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00456                                        DestIterator d_Iter, DestAccessor da,
    00457                                        Neighborhood3D neighborhood3D, ValueType backgroundValue)
    00458 {
    00459     return labelVolumeWithBackground(s_Iter, srcShape, sa, d_Iter, da, 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>
    00466 unsigned int labelVolumeWithBackground(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00467                                        pair<DestIterator, DestAccessor> dest,
    00468                                        Neighborhood3D neighborhood3D, ValueType backgroundValue)
    00469 {
    00470     return labelVolumeWithBackground(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, backgroundValue, std::equal_to<typename SrcAccessor::value_type>());
    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(triple<SrcIterator, SrcShape, SrcAccessor> src,
    00478                                        pair<DestIterator, DestAccessor> dest,
    00479                                        Neighborhood3D neighborhood3D, ValueType backgroundValue, EqualityFunctor equal)
    00480 {
    00481     return labelVolumeWithBackground(src.first, src.second, src.third, dest.first, dest.second, neighborhood3D, backgroundValue, equal);
    00482 }
    00483
    00484 template <class SrcIterator, class SrcAccessor,class SrcShape,
    00485           class DestIterator, class DestAccessor,
    00486           class Neighborhood3D,
    00487           class ValueType, class EqualityFunctor>
    00488 unsigned int labelVolumeWithBackground(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
    00489                                        DestIterator d_Iter, DestAccessor da,
    00490                                        Neighborhood3D,
    00491                                        ValueType backgroundValue, EqualityFunctor equal)
    00492 {
    00493     typedef typename DestAccessor::value_type LabelType;
    00494
    00495     //basically needed for iteration and border-checks
    00496     int w = srcShape[0], h = srcShape[1], d = srcShape[2];
    00497     int x,y,z;
    00498
    00499     // temporary image to store region labels
    00500     detail::UnionFindArray<LabelType>  label;
    00501
    00502     //Declare traversers for all three dims at target
    00503     SrcIterator zs = s_Iter;
    00504     DestIterator zd = d_Iter;
    00505
    00506     // initialize the neighborhood traversers
    00507     NeighborOffsetCirculator<Neighborhood3D> nce(Neighborhood3D::CausalLast);
    00508     ++nce;
    00509     // pass 1: scan image from upper left front to lower right back
    00510     // to find connected components
    00511
    00512     // Each component will be represented by a tree of pixels. Each
    00513     // pixel contains the scan order address of its parent in the
    00514     // tree.  In order for pass 2 to work correctly, the parent must
    00515     // always have a smaller scan order address than the child.
    00516     // Therefore, we can merge trees only at their roots, because the
    00517     // root of the combined tree must have the smallest scan order
    00518     // address among all the tree's pixels/ nodes.  The root of each
    00519     // tree is distinguished by pointing to itself (it contains its
    00520     // own scan order address). This condition is enforced whenever a
    00521     // new region is found or two regions are merged
    00522     for(z = 0; z != d; ++z, ++zs.dim2(), ++zd.dim2())
    00523     {
    00524         SrcIterator ys(zs);
    00525         DestIterator yd(zd);
    00526
    00527         for(y = 0; y != h; ++y, ++ys.dim1(), ++yd.dim1())
    00528         {
    00529             SrcIterator xs(ys);
    00530             DestIterator xd(yd);
    00531
    00532             for(x = 0; x != w; ++x, ++xs.dim0(), ++xd.dim0())
    00533             {
    00534                 if(equal(sa(xs), backgroundValue))
    00535                 {
    00536                     da.set(label[0], xd);
    00537                     continue;
    00538                 }
    00539
    00540                 LabelType currentLabel = label.nextFreeLabel();
    00541
    00542                 //check whether there is a special border treatment to be used or not
    00543                 AtVolumeBorder atBorder = isAtVolumeBorderCausal(x,y,z,w,h,d);
    00544
    00545                 //We are not at the border!
    00546                 if(atBorder == NotAtBorder)
    00547                 {
    00548                     NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::CausalFirst);
    00549
    00550                     do
    00551                     {
    00552                         // if colors are equal
    00553                         if(equal(sa(xs), sa(xs, *nc)))
    00554                         {
    00555                             currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
    00556                         }
    00557                         ++nc;
    00558                     }
    00559                     while(nc!=nce);
    00560                 }
    00561                 else //we are at a border - handle this!!
    00562                 {
    00563                     NeighborOffsetCirculator<Neighborhood3D> nc(Neighborhood3D::nearBorderDirectionsCausal(atBorder,0));
    00564                     int j=0;
    00565                     while(nc.direction() != Neighborhood3D::Error)
    00566                     {
    00567                         //   colors equal???
    00568                         if(equal(sa(xs), sa(xs, *nc)))
    00569                         {
    00570                             currentLabel = label.makeUnion(label[da(xd,*nc)], currentLabel);
    00571                         }
    00572                         nc.turnTo(Neighborhood3D::nearBorderDirectionsCausal(atBorder,++j));
    00573                     }
    00574                 }
    00575                 da.set(label.finalizeLabel(currentLabel), xd);
    00576             }
    00577         }
    00578     }
    00579
    00580     LabelType count = label.makeContiguous();
    00581
    00582     // pass 2: assign one label to each region (tree)
    00583     // so that labels form a consecutive sequence 1, 2, ...
    00584     zd = d_Iter;
    00585     for(z=0; z != d; ++z, ++zd.dim2())
    00586     {
    00587         DestIterator yd(zd);
    00588
    00589         for(y=0; y != h; ++y, ++yd.dim1())
    00590         {
    00591             DestIterator xd(yd);
    00592
    00593             for(x = 0; x != w; ++x, ++xd.dim0())
    00594             {
    00595                 da.set(label[da(xd)], xd);
    00596             }
    00597         }
    00598     }
    00599     return count;
    00600 }
    00601
    00602 //@}
    00603
    00604 } //end of namespace vigra
    00605
    00606 #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.9.0 (Tue Nov 6 2012)