vigra - Connected Components Labeling

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

| Connected Components Labeling |

## 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.9.0 (Tue Nov 6 2012)