Connected Components Labeling

Modules
	Parallel Processing

Classes
class	BlockwiseLabelOptions
class	LabelOptions
	Option object for labelMultiArray(). More...

Functions
template<... >
unsigned int	labelImage (...)
	Find the connected components of a segmented image. More...
template<... >
unsigned int	labelImageWithBackground (...)
	Find the connected components of a segmented image, excluding the background from labeling. More...
template<... >
unsigned int	labelMultiArray (...)
	Find the connected components of a MultiArray with arbitrary many dimensions. More...
template<... >
unsigned int	labelMultiArrayBlockwise (...)
	Connected components labeling for MultiArrays and ChunkedArrays. More...
template<... >
unsigned int	labelMultiArrayWithBackground (...)
	Find the connected components of a MultiArray with arbitrary many dimensions, excluding the background from labeling. More...
template<... >
unsigned int	labelVolume (...)
	Find the connected components of a segmented volume. More...
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. More...
template<... >
unsigned int	labelVolumeWithBackground (...)
	Find the connected components of a segmented volume, excluding the background from labeling. More...
template<... >
void	regionImageToCrackEdgeImage (...)
	Transform a labeled image into a crack edge (interpixel edge) image. More...
template<... >
void	regionImageToEdgeImage (...)
	Transform a labeled image into an edge image. More...

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::labelMultiArrayBlockwise

(

...

)

Connected components labeling for MultiArrays and ChunkedArrays.

Declarations:

namespace vigra {
    // assign local labels and generate mapping (local labels) -> (global labels) for each chunk
    template <unsigned int N, class Data, class S1,
                              class Label, class S2,
              class Equal, class S3>
    Label labelMultiArrayBlockwise(const MultiArrayView<N, Data, S1>& data,
                                   MultiArrayView<N, Label, S2> labels,
                                   const BlockwiseLabelOptions& options,
                                   Equal equal,
                                   MultiArrayView<N, std::vector<Label>, S3>& mapping);

    // assign local labels and generate mapping (local labels) -> (global labels) for each chunk
    template <unsigned int N, class T, class S1,
                              class Label, class S2,
              class EqualityFunctor>
    Label labelMultiArrayBlockwise(const ChunkedArray<N, Data>& data,
                                   ChunkedArray<N, Label>& labels,
                                   const BlockwiseLabelOptions& options,
                                   Equal equal,
                                   MultiArrayView<N, std::vector<Label>, S3>& mapping);

    // assign global labels
    template <unsigned int N, class Data, class S1,
                              class Label, class S2,
              class Equal>
    Label labelMultiArrayBlockwise(const MultiArrayView<N, Data, S1>& data,
                                   MultiArrayView<N, Label, S2> labels,
                                   const BlockwiseLabelOptions& options,
                                   Equal equal);

    // assign global labels
    template <unsigned int N, class T, class S1,
                              class Label, class S2,
              class EqualityFunctor = std::equal_to<T> >
    Label labelMultiArrayBlockwise(const ChunkedArray<N, Data>& data,
                                   ChunkedArray<N, Label>& labels,
                                   const BlockwiseLabelOptions& options = BlockwiseLabelOptions(),
                                   Equal equal = std::equal_to<T>());
}

The resulting labeling is equivalent to a labeling by labelMultiArray, that is, the connected components are the same but may have different ids. NeighborhoodType and background value (if any) can be specified with the LabelOptions object. If the mapping parameter is provided, each chunk is labeled seperately and contiguously (starting at one, zero for background), with mapping containing a mapping of local labels to global labels for each chunk. Thus, the shape of 'mapping' has to be large enough to hold each chunk coordinate.

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

Usage:

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

Shape3 shape = Shape3(10);
Shape3 chunk_shape = Shape3(4);
ChunkedArrayLazy<3, int> data(shape, chunk_shape);
// fill data ...

ChunkedArrayLazy<3, size_t> labels(shape, chunk_shape);

MultiArray<3, std::vector<size_t> > mapping(Shape3(3)); // there are 3 chunks in each dimension

labelMultiArrayBlockwise(data, labels, LabelOptions().neighborhood(DirectNeighborhood).background(0),
                         std::equal_to<int>(), mapping);

// check out chunk in the middle
MultiArray<3, size_t> middle_chunk(Shape3(4));
labels.checkoutSubarray(Shape3(4), middle_chunk);

// print number of non-background labels assigned in middle_chunk
cout << mapping[Shape3(1)].size() << endl;

// get local label for voxel
// this may be the same value assigned to different component in another chunk
size_t local_label = middle_chunk[Shape3(2)];
// get global label for voxel
// if another voxel has the same label, they are in the same connected component albeit they may be in different chunks
size_t global_label = mapping[Shape3(1)][local_label

unsigned int vigra::labelImage

(

...

)

Find the connected components of a segmented image.

Deprecated. Use labelMultiArray() instead.

Connected components are defined as regions with uniform pixel values. Thus, T1 either must be equality comparable, or a suitable EqualityFunctor must be provided that realizes the desired predicate. The destination's value type T2 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 (false) or 8-connected (true).

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

See labelMultiArray() for a dimension-independent implementation of connected components labelling.

Declarations:

pass 2D array views:

namespace vigra {
    template <class T1, class S1,
              class T2, class S2,
              class EqualityFunctor = std::equal_to<T1> >
    unsigned int
    labelImage(MultiArrayView<2, T1, S1> const & src,
               MultiArrayView<2, T2, S2> dest,
               bool eight_neighbors, EqualityFunctor equal = EqualityFunctor());
}

show deprecated declarations

pass Image Iterators and Data Accessors :

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

Usage:

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

MultiArray<2, unsigned char> src(w,h);
MultiArray<2, unsigned int>  labels(w,h);

// threshold at 128
transformImage(src, src, Threshold<int, int>(128, 256, 0, 255));

// find 4-connected regions
labelImage(src, labels, false);

show deprecated examples

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.

Deprecated. Use labelMultiArray() instead.

This function works like labelImage(), but considers all background pixels (i.e. pixels having the given 'background_value') as a single region that is ignored when determining connected components and remains untouched in the destination image. Usually, you will zero-initialize the output image, so that the background gets label 0 (remember that actual region labels start at one).

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

See labelMultiArrayWithBackground() for a dimension-independent implementation if this algorithm.

Declarations:

pass 2D array views:

namespace vigra {
    template <class T1, class S1,
              class T2, class S2,
              class ValueType,
              class EqualityFunctor = std::equal_to<T1> >
    unsigned int
    labelImageWithBackground(MultiArrayView<2, T1, S1> const & src,
                             MultiArrayView<2, T2, S2> dest,
                             bool eight_neighbors,
                             ValueType background_value,
                             EqualityFunctor equal = EqualityFunctor());
}

show deprecated declarations

pass Image Iterators and Data Accessors :

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);
}

Usage:

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

MultiArray<2, unsigned char> src(w,h);
MultiArray<2, unsigned int>  labels(w,h);

// threshold at 128
transformImage(src, src, Threshold<int, int>(128, 256, 0, 255));

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

show deprecated examples

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

void vigra::regionImageToCrackEdgeImage

(

...

)

Transform a labeled image into a crack edge (interpixel edge) image.

Declarations:

pass 2D array views:

namespace vigra {
    template <class T1, class S1,
              class T2, class S2, class DestValue>
    void
    regionImageToCrackEdgeImage(MultiArrayView<2, T1, S1> const & src,
                                MultiArrayView<2, T2, S2> dest,
                                DestValue edge_marker,
                                EdgeImageLabelPolicy labelPolicy = CopyRegionLabels);
}

show deprecated declarations

pass Image Iterators and Data Accessors :

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,
                   EdgeImageLabelPolicy labelPolicy = CopyRegionLabels)
}

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,
               EdgeImageLabelPolicy labelPolicy = CopyRegionLabels)
}

The destination image must be twice the size of the input image (precisely, (2*w-1) by (2*h-1) pixels) to have space for the so called "crack edges" or "interpixel edges" which are logically situated between pixels (at half-integer coordinates of the input image) and correspond to the odd-valued coordinates in the result image (see Crack Edge Image for more details).

When labelPolicy == CopyRegionLabels (the default), this algorithm transfers the labels of a labeled image to the output image (repeating them as appropriate to account for the output image size) and inserts border pixels when the label changes. For example, if a and c are the original labels, and 0 is the value of edge_marker, the transformation looks like this:

original image     copy labels and insert edges

                                  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

When labelPolicy == EdgeOverlayOnly, the region pixels of the output image remain untouched, and only the edge marker is inserted. This is especially useful for visualization, when the output is the interpolated original image:

original image     destination image       overlay edges only

                       d d d d d                 d 0 d d d
   a c c               d d d d d                 d 0 0 0 d
   a a c       +       d d d d d       =>        d d d 0 d
   a a a               d d d d d                 d d d 0 0
                       d d d d d                 d d d d d

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 source value type (SrcAccessor::value-type) must be equality-comparable.

Usage:

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

MultiArray<2, unsigned char> src(w,h);
MultiArray<2, unsigned int>  labels(w,h),
                             cellgrid(2*w-1, 2*h-1);

// threshold at 128
transformImage(src, src, Threshold<int, int>(128, 256, 0, 255));

// find 4-connected regions
labelImage(src, labels, false);

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

show deprecated examples

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

Examples:

graph_agglomerative_clustering.cxx.

void vigra::regionImageToEdgeImage

(

...

)

Transform a labeled image into an edge image.

Declarations:

pass 2D array views:

namespace vigra {
    template <class T1, class S1,
              class T2, class S2, class DestValue>
    void
    regionImageToEdgeImage(MultiArrayView<2, T1, S1> const & src,
                           MultiArrayView<2, T2, S2> dest,
                           DestValue edge_marker);
}

show deprecated declarations

pass Image Iterators and Data Accessors :

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 T1 must be equality-comparable.

Usage:

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

MultiArray<2, unsigned char> src(w,h),
                             edges(w,h);
MultiArray<2, unsigned int>  labels(w,h);

edges = 255;  // init background (non-edge) to 255

// threshold at 128
transformImage(src, src, Threshold<int, int>(128, 256, 0, 255));

// find 4-connected regions
labelImage(src, labels, false);

// create edge image, mark edges with 0
regionImageToEdgeImage(labels, edges, 0);

show deprecated examples

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.

Deprecated. Use labelMultiArray() instead.

Connected components are defined as regions with uniform voxel values. Thus, T1 either must be equality comparable, or an EqualityFunctor must be provided explicitly that realizes the desired equivalence predicate. The destination's value type T2 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)

See labelMultiArray() for a dimension-independent implementation of connected components labelling.

Declarations:

pass 3D array views:

namespace vigra {
    template <class T1, class S1,
              class T2, class S2,
              class Neighborhood3D,
              class EqualityFunctor = std::equal_to<T1> >
    unsigned int
    labelVolume(MultiArrayView<3, T1, S1> const & source,
                MultiArrayView<3, T2, S2> dest,
                Neighborhood3D neighborhood3D,
                EqualityFunctor equal  = EqualityFunctor());

}

show deprecated declarations

pass MultiIterators and Data Accessors :

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

}

Usage:

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

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

// find 6-connected regions
int max_region_label = labelVolumeSix(src, dest);

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

show deprecated examples

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.

Deprecated. Use labelMultiArray() instead.

This function works like labelVolume(), but considers all background voxels (i.e. voxels having the given 'background_value') as a single region that is ignored when determining connected components and remains untouched in the destination array. Usually, you will zero-initialize the output array, so that the background gets label 0 (remember that actual region labels start at one).

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

See labelMultiArrayWithBackground() for a dimension-independent implementation if this algorithm.

Declarations:

pass 3D array views:

namespace vigra {
    template <class T1, class S1,
              class T2, class S2,
              class Neighborhood3D,
              class ValueType,
              class EqualityFunctor = std::equalt_to<T1> >
    unsigned int
    labelVolumeWithBackground(MultiArrayView<3, T1, S1> const & source,
                              MultiArrayView<3, T2, S2> dest,
                              Neighborhood3D neighborhood3D,
                              ValueType backgroundValue,
                              EqualityFunctor equal = EqualityFunctor());
}

show deprecated declarations

pass MultiIterators and Data Accessors :

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

}

Usage:

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

typedef vigra::MultiArray<3,int> IntVolume;

IntVolume src(Shape3(w,h,d));
IntVolume dest(Shape3(w,h,d));

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

show deprecated examples

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

unsigned int vigra::labelMultiArray

(

...

)

Find the connected components of a MultiArray with arbitrary many dimensions.

See also labelMultiArrayBlockwise() for a parallel version of this algorithm.

By specifying a background value in the vigra::LabelOptions, this function can also realize the behavior of labelMultiArrayWithBackground().

Declaration:

namespace vigra {

    // specify parameters directly
    template <unsigned int N, class T, class S1,
                              class Label, class S2,
              class EqualityFunctor = std::equal_to<T> >
    Label
    labelMultiArray(MultiArrayView<N, T, S1> const & data,
                    MultiArrayView<N, Label, S2> labels,
                    NeighborhoodType neighborhood = DirectNeighborhood,
                    EqualityFunctor equal = std::equal_to<T>())

    // specify parameters via LabelOptions
    template <unsigned int N, class T, class S1,
                              class Label, class S2,
              class Equal = std::equal<T> >
    Label
    labelMultiArray(MultiArrayView<N, T, S1> const & data,
                    MultiArrayView<N, Label, S2> labels,
                    LabelOptions const & options,
                    Equal equal = std::equal<T>());

}

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

Argument neighborhood specifies the type of connectivity used. It can take the values DirectNeighborhood (which corresponds to 4-neighborhood in 2D and 6-neighborhood in 3D, default) or IndirectNeighborhood (which corresponds to 8-neighborhood in 2D and 26-neighborhood in 3D).

Return: the highest region label used

Usage:

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

MultiArray<3,int> src(Shape3(w,h,d));
MultiArray<3,int> dest(Shape3(w,h,d));

// find 6-connected regions
int max_region_label = labelMultiArray(src, dest);

// find 26-connected regions
max_region_label = labelMultiArray(src, dest, IndirectNeighborhood);

// find 6-connected regions, ignore the background value 0
// (i.e. call labelMultiArrayWithBackground() internally)
max_region_label = labelMultiArray(src, dest,
                                   LabelOptions().neighborhood(DirectNeighborhood)
                                                 .ignoreBackgroundValue(0));

Required Interface:

T t;
t == t                      // T is equality comparable

EqualityFunctor equal;      // or a suitable functor is supplied
equal(t, t)

unsigned int vigra::labelMultiArrayWithBackground

(

...

)

Find the connected components of a MultiArray with arbitrary many dimensions, excluding the background from labeling.

From a user's point of view, this function is no longer needed because labelMultiArray() can realizes the same behavior when an appropriate background value is specified in its vigra::LabelOptions. Similarly, labelMultiArrayBlockwise() implements a parallel version of this algorithm.

Declaration:

namespace vigra {

    template <unsigned int N, class T, class S1,
                              class Label, class S2
              class Equal = std::equal<T> >
    Label
    labelMultiArrayWithBackground(MultiArrayView<N, T, S1> const & data,
                                  MultiArrayView<N, Label, S2> labels,
                                  NeighborhoodType neighborhood = DirectNeighborhood,
                                  T backgroundValue = T(),
                                  Equal equal = std::equal<T>());

}

This function is the same as labelMultiArray(), except for the additional parameter backgroundValue. Points in the input array data with this value (which default to zero) are ignored during labeling, and their output label is automatically set to zero. Region numbers will be a consecutive sequence starting at zero (when background was present) or at one (when no background was present) and ending with the region number returned by the function (inclusive).

Return: the number of non-background regions found (= highest region label, because background has label 0)

Usage:

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

MultiArray<3, int> src(Shape3(w,h,d));
MultiArray<3, int> dest(Shape3(w,h,d));

// find 6-connected regions, ignoring background value zero (the default)
int max_region_label = labelMultiArrayWithBackground(src, dest);

// find 26-connected regions, using -1 as the background value
max_region_label = labelMultiArrayWithBackground(src, dest, IndirectNeighborhood, -1);

Required Interface:

T t, backgroundValue;
t == backgroundValue        // T is equality comparable

EqualityFunctor equal;      // or a suitable functor is supplied
equal(t, backgroundValue)