Distance Transform

Classes
struct	SkeletonOptions
	Option object for skeletonizeImage() More...

Enumerations
enum	BoundaryDistanceTag { OuterBoundary, InterpixelBoundary, InnerBoundary }
	Specify which boundary is used for boundaryMultiDistance(). More...

Functions
template<... >
void	boundaryMultiDistance (...)
	Euclidean distance to the implicit boundaries of a multi-dimensional label array. More...
template<... >
void	boundaryVectorDistance (...)
	Compute the vector distance transform to the implicit boundaries of a multi-dimensional label array. More...
template<... >
void	distanceTransform (...)
template<unsigned int N, class T , class S , class Array >
void	eccentricityCenters (const MultiArrayView< N, T, S > &src, Array &centers)
	Find the (approximate) eccentricity center in each region of a labeled image. More...
template<unsigned int N, class T , class S , class Array >
void	eccentricityTransformOnLabels (MultiArrayView< N, T > const &src, MultiArrayView< N, S > dest, Array &centers)
	Computes the (approximate) eccentricity transform on each region of a labeled image. More...
template<... >
void	separableMultiDistance (...)
	Euclidean distance on multi-dimensional arrays. More...
template<... >
void	separableMultiDistSquared (...)
	Euclidean distance squared on multi-dimensional arrays. More...
template<... >
void	separableVectorDistance (...)
	Compute the vector distance transform of a N-dimensional binary array. More...
template<... >
void	skeletonizeImage (...)
	Skeletonization of all regions in a labeled 2D image. More...

Detailed Description

The functions in this group perfrom Euclidean distance transforms in arbitrary dimensions, as well Manhattan and chessboard distance transforms in 2D (this can easily be extended to nD if need arises). In addition, a number of related transforms such as vector distance transforms, eccentricity transforms, and 2D skeleton computations are offered.

Enumeration Type Documentation

enum BoundaryDistanceTag

Specify which boundary is used for boundaryMultiDistance().

Enumerator
OuterBoundary	Pixels just outside of each region.
InterpixelBoundary	Half-integer points between pixels of different labels.
InnerBoundary	Pixels just inside of each region.

Function Documentation

void vigra::distanceTransform

(

...

)

For all background pixels, calculate the distance to the nearest object or contour. The label of the pixels to be considered background in the source image is passed in the parameter 'background'. Source pixels with other labels will be considered objects. In the destination image, all pixels corresponding to background will be assigned the their distance value, all pixels corresponding to objects will be assigned 0.

The parameter 'norm' gives the distance norm to be used:

• norm == 0: use chessboard distance (L-infinity norm)
• norm == 1: use Manhattan distance (L1 norm)

• norm == 2: use Euclidean distance (L2 norm)

If you use the L2 norm, the destination pixels must be real valued to give correct results.

Declarations:

pass 2D array views:

namespace vigra {
    template <class T1, class S1,
              class T2, class S2,
              class ValueType>
    void
    distanceTransform(MultiArrayView<2, T1, S1> const & src,
                      MultiArrayView<2, T2, S2> dest,
                      ValueType background, int norm);
}

show deprecated declarations

pass Image Iterators and Data Accessors :

namespace vigra {
    template <class SrcImageIterator, class SrcAccessor,
              class DestImageIterator, class DestAccessor,
              class ValueType>
    void distanceTransform(SrcImageIterator src_upperleft,
                           SrcImageIterator src_lowerright, SrcAccessor sa,
                           DestImageIterator dest_upperleft, DestAccessor da,
                           ValueType background, int norm);
}

use argument objects in conjunction with Argument Object Factories :

namespace vigra {
    template <class SrcImageIterator, class SrcAccessor,
              class DestImageIterator, class DestAccessor,
              class ValueType>
    void distanceTransform(triple<SrcImageIterator, SrcImageIterator, SrcAccessor> src,
                           pair<DestImageIterator, DestAccessor> dest,
                           ValueType background, int norm);
}

Usage:

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

MultiArray<2, unsigned char> src(w,h), edges(w,h);
MultiArray<2, float>         distance(w, h);
...

// detect edges in src image (edges will be marked 1, background 0)
differenceOfExponentialEdgeImage(src, edges, 0.8, 4.0);

// find distance of all pixels from nearest edge
distanceTransform(edges, distance, 0,                   2);
//                                 ^ background label   ^ norm (Euclidean)

show deprecated examples

vigra::BImage src(w,h), edges(w,h);
vigra::FImage distance(w, h);

// empty edge image
edges = 0;
...

// detect edges in src image (edges will be marked 1, background 0)
vigra::differenceOfExponentialEdgeImage(srcImageRange(src), destImage(edges),
                                 0.8, 4.0);

// find distance of all pixels from nearest edge
vigra::distanceTransform(srcImageRange(edges), destImage(distance),
                         0,                   2);
//                       ^ background label   ^ norm (Euclidean)

Required Interface:

SrcImageIterator src_upperleft, src_lowerright;
DestImageIterator dest_upperleft;

SrcAccessor sa;
DestAccessor da;

ValueType background;
float distance;

sa(src_upperleft) != background;
da(dest_upperleft) < distance;
da.set(distance, dest_upperleft);

Examples:

voronoi.cxx.

void vigra::eccentricityCenters	(	const MultiArrayView< N, T, S > &	src,
		Array &	centers
	)

Find the (approximate) eccentricity center in each region of a labeled image.

Declarations:

pass arbitrary-dimensional array views:

namespace vigra {
    template <unsigned int N, class T, class S, class Array>
    void
    eccentricityCenters(MultiArrayView<N, T, S> const & src,
                        Array & centers);
}

Parameters

[in]	src	: labeled array
[out]	centers	: list of eccentricity centers (required interface: centers[k] = TinyVector<int, N>() must be supported)

Usage:

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

Shape3 shape(width, height, depth);
MultiArray<3, UInt32> labels(shape);
ArrayVector<TinyVector<Int32, N> > centers;
...

eccentricityCenters(labels, centers);

void vigra::eccentricityTransformOnLabels	(	MultiArrayView< N, T > const &	src,
		MultiArrayView< N, S >	dest,
		Array &	centers
	)

Computes the (approximate) eccentricity transform on each region of a labeled image.

Declarations:

pass arbitrary-dimensional array views:

namespace vigra {
    // compute only the accentricity transform
    template <unsigned int N, class T, class S>
    void
    eccentricityTransformOnLabels(MultiArrayView<N, T> const & src,
                                  MultiArrayView<N, S> dest);

    // also return the eccentricity center of each region
    template <unsigned int N, class T, class S, class Array>
    void
    eccentricityTransformOnLabels(MultiArrayView<N, T> const & src,
                                  MultiArrayView<N, S> dest,
                                  Array & centers);
}

Parameters

[in]	src	: labeled array
[out]	dest	: eccentricity transform of src
[out]	centers	: (optional) list of eccentricity centers (required interface: centers[k] = TinyVector<int, N>() must be supported)

Usage:

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

Shape3 shape(width, height, depth);
MultiArray<3, UInt32> labels(shape);
MultiArray<3, float> dest(shape);
ArrayVector<TinyVector<Int32, N> > centers;
...

eccentricityTransformOnLabels(labels, dest, centers);

void vigra::separableMultiDistSquared

(

...

)

Euclidean distance squared on multi-dimensional arrays.

The algorithm is taken from Donald Bailey: "An Efficient Euclidean Distance Transform", Proc. IWCIA'04, Springer LNCS 3322, 2004.

Declarations:

pass arbitrary-dimensional array views:

namespace vigra {
    // explicitly specify pixel pitch for each coordinate
    template <unsigned int N, class T1, class S1,
                              class T2, class S2,
              class Array>
    void
    separableMultiDistSquared(MultiArrayView<N, T1, S1> const & source,
                              MultiArrayView<N, T2, S2> dest,
                              bool background,
                              Array const & pixelPitch);

    // use default pixel pitch = 1.0 for each coordinate
    template <unsigned int N, class T1, class S1,
                              class T2, class S2>
    void
    separableMultiDistSquared(MultiArrayView<N, T1, S1> const & source,
                              MultiArrayView<N, T2, S2> dest,
                              bool background);
}

show deprecated declarations

pass MultiIterators and Data Accessors :

namespace vigra {
    // explicitly specify pixel pitch for each coordinate
    template <class SrcIterator, class SrcShape, class SrcAccessor,
              class DestIterator, class DestAccessor, class Array>
    void
    separableMultiDistSquared( SrcIterator s, SrcShape const & shape, SrcAccessor src,
                               DestIterator d, DestAccessor dest,
                               bool background,
                               Array const & pixelPitch);

    // use default pixel pitch = 1.0 for each coordinate
    template <class SrcIterator, class SrcShape, class SrcAccessor,
              class DestIterator, class DestAccessor>
    void
    separableMultiDistSquared(SrcIterator siter, SrcShape const & shape, SrcAccessor src,
                              DestIterator diter, DestAccessor dest,
                              bool background);

}

use argument objects in conjunction with Argument Object Factories :

namespace vigra {
    // explicitly specify pixel pitch for each coordinate
    template <class SrcIterator, class SrcShape, class SrcAccessor,
              class DestIterator, class DestAccessor, class Array>
    void
    separableMultiDistSquared( triple<SrcIterator, SrcShape, SrcAccessor> const & source,
                               pair<DestIterator, DestAccessor> const & dest,
                               bool background,
                               Array const & pixelPitch);

    // use default pixel pitch = 1.0 for each coordinate
    template <class SrcIterator, class SrcShape, class SrcAccessor,
              class DestIterator, class DestAccessor>
    void
    separableMultiDistSquared(triple<SrcIterator, SrcShape, SrcAccessor> const & source,
                              pair<DestIterator, DestAccessor> const & dest,
                              bool background);

}

This function performs a squared Euclidean squared distance transform on the given multi-dimensional array. Both source and destination arrays are represented by iterators, shape objects and accessors. The destination array is required to already have the correct size.

This function expects a mask as its source, where background pixels are marked as zero, and non-background pixels as non-zero. If the parameter background is true, then the squared distance of all background pixels to the nearest object is calculated. Otherwise, the distance of all object pixels to the nearest background pixel is calculated.

Optionally, one can pass an array that specifies the pixel pitch in each direction. This is necessary when the data have non-uniform resolution (as is common in confocal microscopy, for example).

This function may work in-place, which means that siter == diter is allowed. A full-sized internal array is only allocated if working on the destination array directly would cause overflow errors (i.e. if NumericTraits<typename DestAccessor::value_type>::max() < N * M*M, where M is the size of the largest dimension of the array.

Usage:

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

Shape3 shape(width, height, depth);
MultiArray<3, unsigned char> source(shape);
MultiArray<3, unsigned int> dest(shape);
...

// Calculate Euclidean distance squared for all background pixels
separableMultiDistSquared(source, dest, true);

See Also

vigra::distanceTransform(), vigra::separableMultiDistance()

void vigra::separableMultiDistance

(

...

)

Euclidean distance on multi-dimensional arrays.

Declarations:

pass arbitrary-dimensional array views:

namespace vigra {
    // explicitly specify pixel pitch for each coordinate
    template <unsigned int N, class T1, class S1,
              class T2, class S2, class Array>
    void
    separableMultiDistance(MultiArrayView<N, T1, S1> const & source,
                           MultiArrayView<N, T2, S2> dest,
                           bool background,
                           Array const & pixelPitch);

    // use default pixel pitch = 1.0 for each coordinate
    template <unsigned int N, class T1, class S1,
              class T2, class S2>
    void
    separableMultiDistance(MultiArrayView<N, T1, S1> const & source,
                           MultiArrayView<N, T2, S2> dest,
                           bool background);
}

show deprecated declarations

pass MultiIterators and Data Accessors :

namespace vigra {
    // explicitly specify pixel pitch for each coordinate
    template <class SrcIterator, class SrcShape, class SrcAccessor,
              class DestIterator, class DestAccessor, class Array>
    void
    separableMultiDistance( SrcIterator s, SrcShape const & shape, SrcAccessor src,
                            DestIterator d, DestAccessor dest,
                            bool background,
                            Array const & pixelPitch);

    // use default pixel pitch = 1.0 for each coordinate
    template <class SrcIterator, class SrcShape, class SrcAccessor,
              class DestIterator, class DestAccessor>
    void
    separableMultiDistance(SrcIterator siter, SrcShape const & shape, SrcAccessor src,
                           DestIterator diter, DestAccessor dest,
                           bool background);

}

use argument objects in conjunction with Argument Object Factories :

namespace vigra {
    // explicitly specify pixel pitch for each coordinate
    template <class SrcIterator, class SrcShape, class SrcAccessor,
              class DestIterator, class DestAccessor, class Array>
    void
    separableMultiDistance( triple<SrcIterator, SrcShape, SrcAccessor> const & source,
                            pair<DestIterator, DestAccessor> const & dest,
                            bool background,
                            Array const & pixelPitch);

    // use default pixel pitch = 1.0 for each coordinate
    template <class SrcIterator, class SrcShape, class SrcAccessor,
              class DestIterator, class DestAccessor>
    void
    separableMultiDistance(triple<SrcIterator, SrcShape, SrcAccessor> const & source,
                           pair<DestIterator, DestAccessor> const & dest,
                           bool background);

}

This function performs a Euclidean distance transform on the given multi-dimensional array. It simply calls separableMultiDistSquared() and takes the pixel-wise square root of the result. See separableMultiDistSquared() for more documentation.

Usage:

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

Shape3 shape(width, height, depth);
MultiArray<3, unsigned char> source(shape);
MultiArray<3, float> dest(shape);
...

// Calculate Euclidean distance for all background pixels
separableMultiDistance(source, dest, true);

See Also

vigra::distanceTransform(), vigra::separableMultiDistSquared()

void vigra::boundaryMultiDistance

(

...

)

Euclidean distance to the implicit boundaries of a multi-dimensional label array.

Declarations:

pass arbitrary-dimensional array views:

namespace vigra {
    template <unsigned int N, class T1, class S1,
              class T2, class S2>
    void
    boundaryMultiDistance(MultiArrayView<N, T1, S1> const & labels,
                          MultiArrayView<N, T2, S2> dest,
                          bool array_border_is_active=false,
                          BoundaryDistanceTag boundary=InterpixelBoundary);
}

This function computes the distance transform of a labeled image simultaneously for all regions. Depending on the requested type of boundary, three modes are supported:

• OuterBoundary: In each region, compute the distance to the nearest pixel not belonging to that regions. This is the same as if a normal distance transform where applied to a binary image containing just this region.
• InterpixelBoundary (default): Like OuterBoundary, but shift the distance to the interpixel boundary by subtractiong 1/2. This make the distences consistent accross boundaries.
• InnerBoundary: In each region, compute the distance to the nearest pixel in the region which is adjacent to the boundary.

If array_border_is_active=true, the outer border of the array (i.e. the interpixel boundary between the array and the infinite region) is also used. Otherwise (the default), regions touching the array border are treated as if they extended to infinity.

Usage:

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

Shape3 shape(width, height, depth);
MultiArray<3, unsigned char> source(shape);
MultiArray<3, UInt32> labels(shape);
MultiArray<3, float> dest(shape);
...

// find regions (interpixel boundaries are implied)
labelMultiArray(source, labels);

// Calculate Euclidean distance to interpixel boundary for all pixels
boundaryMultiDistance(labels, dest);

See Also

vigra::distanceTransform(), vigra::separableMultiDistance()

void vigra::skeletonizeImage

(

...

)

Skeletonization of all regions in a labeled 2D image.

Declarations:

namespace vigra {
    template <class T1, class S1,
              class T2, class S2>
    void
    skeletonizeImage(MultiArrayView<2, T1, S1> const & labels,
                     MultiArrayView<2, T2, S2> dest,
                     SkeletonOptions const & options = SkeletonOptions());
}

This function computes the skeleton for each region in the 2D label image labels and paints the results into the result image dest. Input label 0 is interpreted as background and always ignored. Skeletons will be marked with the same label as the corresponding region (unless options returnLength() or returnSalience() are selected, see below). Non-skeleton pixels will receive label 0.

For each region, the algorithm proceeds in the following steps:

1. Compute the boundaryVectorDistance() relative to the OuterBoundary of the region.
2. Mark the raw skeleton: find 4-adjacent pixel pairs whose nearest boundary points are neither equal nor adjacent and mark one pixel of the pair as a skeleton candidate. The resulting raw skeleton is 8-connected and thin. Skip the remaining steps when option dontPrune() is selected.
3. Compute the eccentricity transform of the raw skeleton and turn the skeleton into a tree whose root is the eccentricity center. When option pruneCenterLine() is selected, delete all skeleton points that do not belong to the two longest tree branches and skip the remaining steps.
4. For each pixel on the skeleton, compute its length attribute as the depth of the pixel's longest subtree. Compute its salience attribute as the ratio between length and distance, where distance is the pixel's distance to the nearest boundary point according to the distance transform. It holds that length >= 0.5 and salience >= 1.0.
5. Detect skeleton branching points and define skeleton segments as maximal connected pieces without branching points.
6. Compute length and salience of each segment as the maximum of these attributes among the pixels in the segment. When options returnLength() or returnSalience() are selected, skip the remaining steps and return the requested segment attribute in dest. In this case, dest's value_type should be a floating point type to exactly accomodate the attribute values.
7. Detect minimal cycles in the raw skeleton that enclose holes in the region (if any) and mark the corresponding pixels as critical for skeleton topology.
8. Prune skeleton segments according to the selected pruning strategy and return the result. The following pruning strategies are available:
   • pruneLength(threshold, preserve_topology): Retain only segments whose length attribute exceeds the given threshold. When preserve_topology is true (the defult), cycles around holes are preserved regardless of their length. Otherwise, they are pruned as well.
   • pruneLengthRelative(threshold, preserve_topology): Like pruneLength(), but the threshold is specified as a fraction of the maximum segment length in the present region.
   • pruneSalience(threshold, preserve_topology): Retain only segments whose salience attribute exceeds the given threshold. When preserve_topology is true (the defult), cycles around holes are preserved regardless of their salience. Otherwise, they are pruned as well.
   • pruneSalienceRelative(threshold, preserve_topology): Like pruneSalience(), but the threshold is specified as a fraction of the maximum segment salience in the present region.
   • pruneTopology(preserve_center): Retain only segments that are essential for the region's topology. If preserve_center is true (the default), the eccentricity center is also preserved, even if it is not essential. Otherwise, it might be removed. The eccentricity center is always the only remaining point when the region has no holes.

The skeleton has the following properties:

• It is 8-connected and thin (except when two independent branches happen to run alongside before they divert). Skeleton points are defined by rounding the exact Euclidean skeleton locations to the nearest pixel.
• Skeleton branches terminate either at the region boundary or at a cycle. There are no branch end points in the region interior.
• The salience threshold acts as a scale parameter: Large thresholds only retain skeleton branches characterizing the general region shape. When the threshold gets smaller, ever more detailed boundary bulges will be represented by a skeleton branch.

Remark: If you have an application where a skeleton graph would be more useful than a skeleton image, function skeletonizeImage() can be changed/extended easily.

Usage:

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

Shape2 shape(width, height);
MultiArray<2, UInt32> source(shape);
MultiArray<2, UInt32> dest(shape);
...

// Skeletonize and keep only those segments that are at least 10% of the maximum
// length (the maximum length is half the skeleton diameter).
skeletonizeImage(source, dest,
            SkeletonOptions().pruneLengthRelative(0.1));

See Also

vigra::boundaryVectorDistance()

void vigra::separableVectorDistance

(

...

)

Compute the vector distance transform of a N-dimensional binary array.

Declarations:

namespace vigra {
    template <unsigned int N, class T1, class S1,
              class T2, class S2, class Array>
    void
    separableVectorDistance(MultiArrayView<N, T1, S1> const & source,
                            MultiArrayView<N, T2, S2> dest,
                            bool background,
                            Array const & pixelPitch=TinyVector<double, N>(1));
}

This function works like separableMultiDistance() (see there for details), but returns in each pixel the vector to the nearest background pixel rather than the scalar distance. This enables much more powerful applications.

Usage:

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

Shape3 shape(width, height, depth);
MultiArray<3, unsigned char> source(shape);
MultiArray<3, Shape3> dest(shape);
...

// For each background pixel, find the vector to the nearest foreground pixel.
separableVectorDistance(source, dest, true);

See Also

vigra::separableMultiDistance(), vigra::boundaryVectorDistance()

void vigra::boundaryVectorDistance

(

...

)

Compute the vector distance transform to the implicit boundaries of a multi-dimensional label array.

Declarations:

namespace vigra {
    template <unsigned int N, class T1, class S1,
                              class T2, class S2,
              class Array>
    void
    boundaryVectorDistance(MultiArrayView<N, T1, S1> const & labels,
                           MultiArrayView<N, T2, S2> dest,
                           bool array_border_is_active=false,
                           BoundaryDistanceTag boundary=OuterBoundary,
                           Array const & pixelPitch=TinyVector<double, N>(1));
}

This function works like boundaryMultiDistance() (see there for details), but returns in each pixel the vector to the nearest boundary pixel rather than the scalar distance. This enables much more powerful applications. Additionally, it support a pixelPitch parameter which allows to adjust the distance calculations for anisotropic grid resolution.

Usage:

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

Shape3 shape(width, height, depth);
MultiArray<3, UInt32> labels(shape);
MultiArray<3, Shape3> dest(shape);
...

// For each region, find the vectors to the nearest boundary pixel, including the
// outer border of the array.
boundaryVectorDistance(labels, dest, true);

See Also

vigra::boundaryMultiDistance(), vigra::separableVectorDistance()