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

details Connected Components Labeling VIGRA

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

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

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

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

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

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

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

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

show deprecated examples

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

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

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

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

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

© 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.11.1 (Fri May 19 2017)