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

details Euclidean distance transform for multi-dimensional arrays. VIGRA

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

These functions perform variants of the Euclidean distance transform on arbitrary dimensional arrays.

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

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

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

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

© 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.0 (Thu Feb 4 2016)