Distance Transform Module Reference
Distance transforms and Voronoi, Delauney and geodesic partitioning based there upon.
More...
#include <filters.h>
Routines
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
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.
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.
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.
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.
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.
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.
|