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

details Connected Components Labeling VIGRA

Functions

template<... >
unsigned int labelImage (...)
 Find the connected components of a segmented image.
template<... >
unsigned int labelImageWithBackground (...)
 Find the connected components of a segmented image, excluding the background from labeling.
template<... >
unsigned int labelVolume (...)
 Find the connected components of a segmented volume.
template<class SrcIterator , class SrcAccessor , class SrcShape , class DestIterator , class DestAccessor >
unsigned int labelVolumeSix (triple< SrcIterator, SrcShape, SrcAccessor > src, pair< DestIterator, DestAccessor > dest)
 Find the connected components of a segmented volume using the 6-neighborhood.
template<... >
unsigned int labelVolumeWithBackground (...)
 Find the connected components of a segmented volume, excluding the background from labeling.
template<... >
void regionImageToCrackEdgeImage (...)
 Transform a labeled image into a crack edge image.
template<... >
void regionImageToEdgeImage (...)
 Transform a labeled image into an edge image.


Detailed Description

The 2-dimensional connected components algorithms may use either 4 or 8 connectivity. By means of a functor the merge criterion can be defined arbitrarily.

The 3-dimensional connected components algorithms may use either 6 or 26 connectivity. By means of a functor the merge criterion can be defined arbitrarily.


Function Documentation

unsigned int vigra::labelImage (   ...  ) 

Find the connected components of a segmented image.

Declarations:

pass arguments explicitly:

    namespace vigra {
        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor>
        unsigned int labelImage(SrcIterator upperlefts,
                                SrcIterator lowerrights, SrcAccessor sa,
                                DestIterator upperleftd, DestAccessor da,
                                bool eight_neighbors);

        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor,
                  class EqualityFunctor>
        unsigned int labelImage(SrcIterator upperlefts,
                                SrcIterator lowerrights, SrcAccessor sa,
                                DestIterator upperleftd, DestAccessor da,
                                bool eight_neighbors, EqualityFunctor equal);
    }

use argument objects in conjunction with Argument Object Factories :

    namespace vigra {
        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor>
        unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
                                pair<DestIterator, DestAccessor> dest,
                                bool eight_neighbors);

        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor,
                  class EqualityFunctor>
        unsigned int labelImage(triple<SrcIterator, SrcIterator, SrcAccessor> src,
                                pair<DestIterator, DestAccessor> dest,
                                bool eight_neighbors, EqualityFunctor equal)
    }

Connected components are defined as regions with uniform pixel values. Thus, SrcAccessor::value_type either must be equality comparable (first form), or an EqualityFunctor must be provided that realizes the desired predicate (second form). The destination's value type should be large enough to hold the labels without overflow. Region numbers will be a consecutive sequence starting with one and ending with the region number returned by the function (inclusive). The parameter 'eight_neighbors' determines whether the regions should be 4-connected or 8-connected. The function uses accessors.

Return: the number of regions found (= largest region label)

Usage:

#include <vigra/labelimage.hxx>
Namespace: vigra

    vigra::BImage src(w,h);
    vigra::IImage labels(w,h);

    // threshold at 128
    vigra::transformImage(srcImageRange(src), destImage(src),
       vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
                                                    128, 256, 0, 255));

    // find 4-connected regions
    vigra::labelImage(srcImageRange(src), destImage(labels), false);

Required Interface:

    SrcImageIterator src_upperleft, src_lowerright;
    DestImageIterator dest_upperleft;

    SrcAccessor src_accessor;
    DestAccessor dest_accessor;

    SrcAccessor::value_type u = src_accessor(src_upperleft);

    u == u                  // first form

    EqualityFunctor equal;      // second form
    equal(u, u)                 // second form

    int i;
    dest_accessor.set(i, dest_upperleft);
unsigned int vigra::labelImageWithBackground (   ...  ) 

Find the connected components of a segmented image, excluding the background from labeling.

Declarations:

pass arguments explicitly:

    namespace vigra {
        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor,
                  class ValueType>
        int labelImageWithBackground(SrcIterator upperlefts,
                       SrcIterator lowerrights, SrcAccessor sa,
                       DestIterator upperleftd, DestAccessor da,
                       bool eight_neighbors,
                       ValueType background_value );

        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor,
                  class ValueType, class EqualityFunctor>
        int labelImageWithBackground(SrcIterator upperlefts,
                       SrcIterator lowerrights, SrcAccessor sa,
                       DestIterator upperleftd, DestAccessor da,
                       bool eight_neighbors,
                       ValueType background_value, EqualityFunctor equal);
    }

use argument objects in conjunction with Argument Object Factories :

    namespace vigra {
        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor,
                  class ValueType>
        int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src,
                                     pair<DestIterator, DestAccessor> dest,
                                     bool eight_neighbors,
                                     ValueType background_value);

        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor,
                  class ValueType, class EqualityFunctor>
        int labelImageWithBackground(triple<SrcIterator, SrcIterator, SrcAccessor> src,
                                     pair<DestIterator, DestAccessor> dest,
                                     bool eight_neighbors,
                                     ValueType background_value, EqualityFunctor equal);
    }

Connected components are defined as regions with uniform pixel values. Thus, SrcAccessor::value_type either must be equality comparable (first form), or an EqualityFunctor must be provided that realizes the desired predicate (second form). All pixel equal to the given 'background_value' are ignored when determining connected components and remain untouched in the destination image and

The destination's value type should be large enough to hold the labels without overflow. Region numbers will be a consecutive sequence starting with one and ending with the region number returned by the function (inclusive). The parameter 'eight_neighbors' determines whether the regions should be 4-connected or 8-connected. The function uses accessors.

Return: the number of regions found (= largest region label)

Usage:

#include <vigra/labelimage.hxx>
Namespace: vigra

    vigra::BImage src(w,h);
    vigra::IImage labels(w,h);

    // threshold at 128
    vigra::transformImage(srcImageRange(src), destImage(src),
        vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
                                                    128, 256, 0, 255));

    // find 4-connected regions of foreground (= white pixels) only
    vigra::labelImageWithBackground(srcImageRange(src), destImage(labels),
                             false, 0);

Required Interface:

    SrcImageIterator src_upperleft, src_lowerright;
    DestImageIterator dest_upperleft;

    SrcAccessor src_accessor;
    DestAccessor dest_accessor;

    SrcAccessor::value_type u = src_accessor(src_upperleft);
    ValueType background_value;

    u == u                  // first form
    u == background_value   // first form

    EqualityFunctor equal;      // second form
    equal(u, u)                 // second form
    equal(u, background_value)  // second form

    int i;
    dest_accessor.set(i, dest_upperleft);
Examples:
watershed.cxx.
void vigra::regionImageToCrackEdgeImage (   ...  ) 

Transform a labeled image into a crack edge image.

Declarations:

pass arguments explicitly:

    namespace vigra {
        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor, class DestValue>
        void regionImageToCrackEdgeImage(
                       SrcIterator sul, SrcIterator slr, SrcAccessor sa,
                       DestIterator dul, DestAccessor da,
                       DestValue edge_marker)
    }

use argument objects in conjunction with Argument Object Factories :

    namespace vigra {
        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor, class DestValue>
        void regionImageToCrackEdgeImage(
                   triple<SrcIterator, SrcIterator, SrcAccessor> src,
                   pair<DestIterator, DestAccessor> dest,
                   DestValue edge_marker)
    }

This algorithm inserts border pixels (so called "crack edges") between regions in a labeled image like this (a and c are the original labels, and 0 is the value of edge_marker and denotes the inserted edges):

       original image     insert zero- and one-cells

                                         a 0 c c c
          a c c                          a 0 0 0 c
          a a c               =>         a a a 0 c
          a a a                          a a a 0 0
                                         a a a a a

The algorithm assumes that the original labeled image contains no background. Therefore, it is suitable as a post-processing operation of labelImage() or seededRegionGrowing().

The destination image must be twice the size of the original (precisely, (2*w-1) by (2*h-1) pixels). The source value type (SrcAccessor::value-type) must be equality-comparable.

Usage:

#include <vigra/labelimage.hxx>
Namespace: vigra

    vigra::BImage src(w,h);
    vigra::IImage labels(w,h);
    vigra::IImage cellgrid(2*w-1, 2*h-1);

    // threshold at 128
    vigra::transformImage(srcImageRange(src), destImage(src),
       vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
                                                    128, 256, 0, 255));

    // find 4-connected regions
    vigra::labelImage(srcImageRange(src), destImage(labels), false);

    // create cell grid image, mark edges with 0
    vigra::regionImageToCrackEdgeImage(srcImageRange(labels), destImage(cellgrid), 0);

Required Interface:

    ImageIterator src_upperleft, src_lowerright;
    ImageIterator dest_upperleft;

    SrcAccessor src_accessor;
    DestAccessor dest_accessor;

    SrcAccessor::value_type u = src_accessor(src_upperleft);

    u != u

    DestValue edge_marker;
    dest_accessor.set(edge_marker, dest_upperleft);

Preconditions:

The destination image must have twice the size of the source:

    w_dest = 2 * w_src - 1
    h_dest = 2 * h_src - 1
void vigra::regionImageToEdgeImage (   ...  ) 

Transform a labeled image into an edge image.

Declarations:

pass arguments explicitly:

    namespace vigra {
        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor, class DestValue>
        void regionImageToEdgeImage(
                       SrcIterator sul, SrcIterator slr, SrcAccessor sa,
                       DestIterator dul, DestAccessor da,
                       DestValue edge_marker)
    }

use argument objects in conjunction with Argument Object Factories :

    namespace vigra {
        template <class SrcIterator, class SrcAccessor,
                  class DestIterator, class DestAccessor, class DestValue>
        void regionImageToEdgeImage(
                   triple<SrcIterator, SrcIterator, SrcAccessor> src,
                   pair<DestIterator, DestAccessor> dest,
                   DestValue edge_marker)
    }

This algorithm marks all pixels with the given edge_marker which belong to a different region (label) than their right or lower neighbors:

       original image                     edges
                                 (assuming edge_marker == 1)

          a c c                            1 1 *
          a a c               =>           * 1 1
          a a a                            * * *

The non-edge pixels of the destination image will not be touched. The source value type (SrcAccessor::value-type) must be equality-comparable.

Usage:

#include <vigra/labelimage.hxx>
Namespace: vigra

    vigra::BImage src(w,h);
    vigra::IImage labels(w,h);
    vigra::IImage edges(w, h);
    edges = 255;  // init background (non-edge) to 255

    // threshold at 128
    vigra::transformImage(srcImageRange(src), destImage(src),
      vigra::Threshold<vigra::BImage::PixelType, vigra::BImage::PixelType>(
                                                    128, 256, 0, 255));

    // find 4-connected regions
    vigra::labelImage(srcImageRange(src), destImage(labels), false);

    // create edge image, mark edges with 0
    vigra::regionImageToEdgeImage(srcImageRange(labels), destImage(edges), 0);

Required Interface:

    ImageIterator src_upperleft, src_lowerright;
    ImageIterator dest_upperleft;

    SrcAccessor src_accessor;
    DestAccessor dest_accessor;

    SrcAccessor::value_type u = src_accessor(src_upperleft);

    u != u

    DestValue edge_marker;
    dest_accessor.set(edge_marker, dest_upperleft);
Examples:
voronoi.cxx, and watershed.cxx.
unsigned int vigra::labelVolume (   ...  ) 

Find the connected components of a segmented volume.

Declarations:

pass arguments explicitly:

    namespace vigra {

        template <class SrcIterator, class SrcAccessor,class SrcShape,
                  class DestIterator, class DestAccessor,
                  class Neighborhood3D>
        unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
                                 DestIterator d_Iter, DestAccessor da,
                                 Neighborhood3D neighborhood3D);

        template <class SrcIterator, class SrcAccessor,class SrcShape,
                          class DestIterator, class DestAccessor,
                          class Neighborhood3D, class EqualityFunctor>
        unsigned int labelVolume(SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
                                 DestIterator d_Iter, DestAccessor da,
                                 Neighborhood3D neighborhood3D, EqualityFunctor equal);

    }

use argument objects in conjunction with Argument Object Factories :

    namespace vigra {

        template <class SrcIterator, class SrcAccessor,class SrcShape,
                  class DestIterator, class DestAccessor,
                  class Neighborhood3D>
        unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
                                 pair<DestIterator, DestAccessor> dest,
                                 Neighborhood3D neighborhood3D);

        template <class SrcIterator, class SrcAccessor,class SrcShape,
                 class DestIterator, class DestAccessor,
                 class Neighborhood3D, class EqualityFunctor>
        unsigned int labelVolume(triple<SrcIterator, SrcShape, SrcAccessor> src,
                                 pair<DestIterator, DestAccessor> dest,
                                 Neighborhood3D neighborhood3D, EqualityFunctor equal);

    }

use with 3D-Six-Neighborhood:

    namespace vigra {    
    
        template <class SrcIterator, class SrcAccessor,class SrcShape,
                  class DestIterator, class DestAccessor>
        unsigned int labelVolumeSix(triple<SrcIterator, SrcShape, SrcAccessor> src,
                                    pair<DestIterator, DestAccessor> dest);
                                    
    }

Connected components are defined as regions with uniform voxel values. Thus, SrcAccessor::value_type either must be equality comparable (first form), or an EqualityFunctor must be provided that realizes the desired predicate (second form). The destination's value type should be large enough to hold the labels without overflow. Region numbers will be a consecutive sequence starting with one and ending with the region number returned by the function (inclusive).

Return: the number of regions found (= largest region label)

Usage:

#include <vigra/labelvolume.hxx>
Namespace: vigra

    typedef vigra::MultiArray<3,int> IntVolume;
    IntVolume src(IntVolume::difference_type(w,h,d));
    IntVolume dest(IntVolume::difference_type(w,h,d));
    
    // find 6-connected regions
    int max_region_label = vigra::labelVolumeSix(srcMultiArrayRange(src), destMultiArray(dest));

    // find 26-connected regions
    int max_region_label = vigra::labelVolume(srcMultiArrayRange(src), destMultiArray(dest), NeighborCode3DTwentySix());

Required Interface:

    SrcIterator src_begin;
    SrcShape shape;
    DestIterator dest_begin;

    SrcAccessor src_accessor;
    DestAccessor dest_accessor;

    SrcAccessor::value_type u = src_accessor(src_begin);

    u == u                      // first form

    EqualityFunctor equal;      // second form
    equal(u, u)                 // second form

    int i;
    dest_accessor.set(i, dest_begin);
unsigned int vigra::labelVolumeSix ( triple< SrcIterator, SrcShape, SrcAccessor >  src,
pair< DestIterator, DestAccessor >  dest 
)

Find the connected components of a segmented volume using the 6-neighborhood.

See labelVolume() for detailed documentation.

unsigned int vigra::labelVolumeWithBackground (   ...  ) 

Find the connected components of a segmented volume, excluding the background from labeling.

Declarations:

pass arguments explicitly:

    namespace vigra {

        template <class SrcIterator, class SrcAccessor,class SrcShape,
                          class DestIterator, class DestAccessor,
                          class Neighborhood3D, class ValueType>
        unsigned int labelVolumeWithBackground(    SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
                                                          DestIterator d_Iter, DestAccessor da,
                                                          Neighborhood3D neighborhood3D, ValueType background_value);

        template <class SrcIterator, class SrcAccessor,class SrcShape,
                          class DestIterator, class DestAccessor,
                          class Neighborhood3D, class ValueType, class EqualityFunctor>
        unsigned int labelVolumeWithBackground(    SrcIterator s_Iter, SrcShape srcShape, SrcAccessor sa,
                                                            DestIterator d_Iter, DestAccessor da,
                                                          Neighborhood3D neighborhood3D, ValueType background_value,
                                                            EqualityFunctor equal);

    }

use argument objects in conjunction with Argument Object Factories :

    namespace vigra {

        template <class SrcIterator, class SrcAccessor,class SrcShape,
                          class DestIterator, class DestAccessor,
                          class Neighborhood3D, class ValueType>
        unsigned int labelVolumeWithBackground(    triple<SrcIterator, SrcShape, SrcAccessor> src,
                                                          pair<DestIterator, DestAccessor> dest,
                                                          Neighborhood3D neighborhood3D, ValueType background_value);

        template <class SrcIterator, class SrcAccessor,class SrcShape,
                          class DestIterator, class DestAccessor,
                          class Neighborhood3D, class ValueType, class EqualityFunctor>
        unsigned int labelVolumeWithBackground(    triple<SrcIterator, SrcShape, SrcAccessor> src,
                                                        pair<DestIterator, DestAccessor> dest,
                                                        Neighborhood3D neighborhood3D, ValueType background_value,
                                                        EqualityFunctor equal);

    }

Connected components are defined as regions with uniform voxel values. Thus, SrcAccessor::value_type either must be equality comparable (first form), or an EqualityFunctor must be provided that realizes the desired predicate (second form). All voxel equal to the given 'background_value' are ignored when determining connected components and remain untouched in the destination volume.

The destination's value type should be large enough to hold the labels without overflow. Region numbers will be a consecutive sequence starting with one and ending with the region number returned by the function (inclusive).

Return: the number of regions found (= largest region label)

Usage:

#include <vigra/labelvolume.hxx>
Namespace: vigra

    typedef vigra::MultiArray<3,int> IntVolume;
    IntVolume src(IntVolume::difference_type(w,h,d));
    IntVolume dest(IntVolume::difference_type(w,h,d));

    // find 6-connected regions
    int max_region_label = vigra::labelVolumeWithBackground(
    srcMultiArrayRange(src), destMultiArray(dest), NeighborCode3DSix(), 0);

Required Interface:

    SrcIterator src_begin;
    SrcShape shape;
    DestIterator dest_begin;

    SrcAccessor src_accessor;
    DestAccessor dest_accessor;

    SrcAccessor::value_type u = src_accessor(src_begin);

    u == u                      // first form

    EqualityFunctor equal;      // second form
    equal(u, u)                 // second form

    int i;
    dest_accessor.set(i, dest_begin);

© 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)