Home · Pages · Index · Overviews

Distance Transform Module Reference

Distance transforms and Voronoi, Delauney and geodesic partitioning based there upon. More...

 #include <filters.h>

Routines

Float_Array * Squared_DistanceG (APart *image)
Float_Array * Manhattan_DistanceG (APart *image)
Float_Array * Binary_Euclidean_DistanceG (APart *image, int boundary)

Label_Array * Voronoi_LabelingG (int nseed, Indx_Type *seeds, Coordinate *shape F)
Partition * Delauney_PartitionG (int nseed, Indx_Type *seeds, Coordinate *shape F)

Label_Array * Geodesic_LabelingG (APart *image, boolean iscon2n, int *nregions O)
Partition * Geodesic_PartitionG (APart *image I, boolean iscon2n)

Detailed Description

The distance transform in its most common form is used to compute the distance of every foreground pixel from the nearest background pixel in a binary image (Binary_Euclidean_Distance). More generally, given a grey scale image, the transfrom computes:

     D[p] = minq ( I[q] + d(p,q) )

where D[p] is the distance transform of pixel p, I[q] is the value of the image at pixel q, and d(p,q) is a measure of distance between the coordinates of pixels p and q. Using the linear time algorithm of Fezenszwalb and Hutenlocher (Cornell Computing and Information Science Technical Report TR2004-1963, 2004) this module provides functions for the squared Euclidean distance (Squared_Distance) and Manhattan distance (Manhattan_Distance).

The Voronoi diagram and its dual Delauney triangulation are constructs that can be derived from a set of N real-valued points in O(NlogN) time. However, one can also, less efficiently compute these with respect to a set of N pixels using the distance transform in time proportional to the size of the array involved where in this form the Voroni diagram is returned by Voronoi_Labeling as a label array that indicates which point is closes to any given pixel, and the Delauney triangulation is returned by Delauney_Partition as a Partition that models the underlying partition of the Voronoi diagram.

Finally, given a collection of connected foreground objects, Geodesic_Labeling uses the distance transform to determine a labeling that gives the foreground object each pixel is closest to, and Geodesic_Partition returns a Partition that models the resulting partition.


Routine Documentation

Float_Array * Squared_DistanceG (APart *image)

Generates a FLOAT32_TYPE array with the same shape as array or slice image, that contains the distance transform of image with respect to the squared Euclidean metric. That is, if D[p] is the value of pixel p in the result, and I[q] is the value of image at a pixel q, then:

     D[p] = minq ( I[q] + d(p,q) )

where the minimum is conceptually over all pixels q in image, and d(p,q) is the square of the Euclidean distance between pixels p and q. That is, if the coordinates for p and q are (x1, x2, ... xn) and (y1, y2, ... yn), respectively, then:

     d(p,q) = Σi ( xi - yi )2

The routine take O(vn) time where v is the size of image and n is its dimensionality.

Float_Array * Manhattan_DistanceG (APart *image)

Generates a FLOAT32_TYPE array with the same shape as array or slice image, that contains the distance transform of image with respect to the Manhattan metric. That is, if D[p] is the value of pixel p in the result, and I[q] is the value of image at a pixel q, then:

     D[p] = minq ( I[q] + d(p,q) )

where the minimum is conceptually over all pixels q in image, and d(p,q) is the Manhattan distance between pixels p and q. That is, if the coordinates for p and q are (x1, x2, ... xn) and (y1, y2, ... yn), respectively, then:

     d(p,q) = Σi | xi - yi |

The routine take O(vn) time where v is the size of image and n is its dimensionality.

Float_Array * Binary_Euclidean_DistanceG (APart *image, int boundary)

Generates a FLOAT32_TYPE array with the same shape as array or slice image, that contains the Euclidean distance transform of the binarization of image where non-zero pixels are considered foreground and zero pixels are considered background. That is, if D[p] is the value of pixel p in the result, and B is the set of all pixels in image that are background (zero) then:

     D[p] = minq ∈ B d(p,q)

where d(p,q) is the Euclidean distance between pixels p and q. That is, if the coordinates for p is (x1, x2, ... xn) and the coordinate for q is (y1, y2, ... yn), then:

     d(p,q) = ( Σi ( xi - yi )2 ).5

The routine take O(vn) time where v is the size of image and n is its dimensionality.

Label_Array * Voronoi_LabelingG (int nseed, Indx_Type *seeds, Coordinate *shape F)

Creates an UINT32_TYPE array L of shape shape for which L[p] = i if and only if d(p,seeds[i-1] is minimal over all possible choices of i ∈ [1,nseed], where d is Euclidean distance. That is, L is a label field that for every pixel indicates which Voronoi region the pixel is in, where the Voronoi diagram is that induced by the nseed points given by seeds[0..nseed-1] with respect to the lattice of shape.

Partition * Delauney_PartitionG (int nseed, Indx_Type *seeds, Coordinate *shape F)

Returns a Partition graph that models the Delauney decomposition of the collection of points seeds[0..nseed-1] with respect to the lattice shape. This decomposition is effectively the partition graph of the Voronoi decomposition (see Voronoi_Labeling) of said points. The depth of each region in this partition is always 0, and the height of each edge between Voronoi regions is the distance between their foci.

Label_Array * Geodesic_LabelingG (APart *image, boolean iscon2n, int *nregions O)

Creates an UINT32_TYPE array L with the same shape as array or slice image that gives the labeling of pixels in the geodesic decomposition of image when it is interpreted as a binary foreground/background image, where non-zero pixels are considered foreground and zero pixels are considered background. Every iscon2n-connected set of foreground pixels is assigned an integer index from 1 to *nregion, and there after L[p] for each index p is set to the index of the foreground region that is closest to it.

Partition * Geodesic_PartitionG (APart *image I, boolean iscon2n)

Returns a Partition graph that models the partitioning of image described in Geodesic_Labeling immediately above. The depth of each region in this partition is always 0, and the height of an edge is the distance between the two foreground objects of the regions.