Applications

In this section we present of few applications of distance transformations, within and without the medical image processing domain. This intends to illustrate their usefulness, but should by no means be considered as an exhaustive review of DT applications. Distance transformations are probably too generic a tool anyway for such an exhaustive review to be possible.

Borgefors [11,13] proposes to use distance transformations for pattern matching. In order to find an object in an image, she computes the chamfer DT from the edges of that image. The object is located at the minimum of the correlation between the edges of the object and the resulting distance map.

Paglieroni [118] studies the correlation properties of the Euclidean DT. He shows applications for pattern matching and for stereo vision. In stereo vision, one aims to find equivalent features in the right and left images. The distance between the locations of a feature in both images reveals its depth, i.e. its distance from the camera. The conjugate of a point in the right image is constrained, by camera parameters and geometry, to lie on a line in the right image. Its exact position must be determined by contextual information. For this, Paglieroni uses edge matching, i.e. he applies an edge detector on both images, then computes the Euclidean DT from both edge images. The matching criterion is a composition of the correlation of an edge image with the DT of the other, and vice-versa.

Mangin, Froin, Bloch, Bendriem and Lopez-Krahe [101] apply a similar method for the registration of 3D medical images of different modalities, i.e. Positron Emission Tomography (PET) and Magnetic Resonance Imaging (MRI).

Ragnelmam [126], Paglieroni [118] and Huang and Mitchell [77] use distance transformations in order to implement mathematical morphology operators. In mathematical morphology, the dilation of an object O by a structural element B is defined as

$$O \oplus B = \{ p+q \; \vert \; p \in O \; , \; q \in B \}$$ (2.32)

In the common case where the structural element is a ball, i.e.

$$B = \{ q \; \vert \; dist_M(q,(0.0)) \leq d_{\max} \}$$ (2.33)

the dilation can be efficiently implemented by thresholding the DT, i.e.

$$O \oplus B = \{ p \; \vert \; DT(p) \leq d_{\max} \}$$ (2.34)

In [126], Ragnelmam shows that his distance transformation by propagation is particularly well-suited to implement the morphological dilation since the DT can be stopped as soon as $d_{\max}$ is reached.

Danielsson [37], Niblack, Gibbons and Capson [114] and Ge and Fitzpatrick [64], among many others, show that the DT can be used to produce another useful morphological operator, the skeleton. Blum [6,7] defines the skeleton of an object as the locus where fire-fronts started from its edges meet. He shows that an equivalent definition is simply the locus of the centers of maximal disks contained in the object.

As illustrated at figure , Danielsson [37] finds an approximate skeleton with a local test on the Euclidean DT of the object's edges. A pixel belongs to the skeleton if the largest inscribed disk centered on it is included in none of the largest inscribed disks centered on one of its neighbors. The set of pixels he finds is redundant, both because some disks can be included inside disks centered on non-neighboring pixels, and because some disks can be included in the union of several disks. Niblack [114] uses chamfer DTs on which he detects local maxima, saddle points, and the steepest uphill paths from them. Ge [64] uses the Euclidean DT, detects the exact set of centers of maximal disks by performing additional tests on the set found by Danielsson's method. Then, he links the centers of maximal disks in order to produce connected skeletons. The resulting skeletons have all desirable properties: they have the same connectivity as the figure, they are well-centered, they are insensitive to rotation and they allow the exact reconstruction of the original object.

  

Figure 2.18: Skeleton of an object generated using Danielsson's method. Left: Original object Center: Distance transformation Right: Skeleton

Euclidean skeletons have a large variety of applications. For instance, in [15], Bourland uses a 3D skeleton computed from the Euclidean DT to plan the optimal location of the shots in a radio-surgical treatment. The optimal locations are either the end-points or cross-points of the skeleton of the targeted tumor.

Borgefors [14] uses the center of maximal disks as an efficient tool for shape representation.

In his paper about watershed segmentation, Vincent [170] suggests that overlapping objects can be separated by computing the watershed transformation on the negative DT of the edge of the compound object (Figure ). Thiran and Macq [153] obtain a similar result as they find the centers of the nuclei in images of cancerous tissues by applying the mathematical morphology ultimate erosion operator. Obviously, the local minima of the DT and the ultimate erosion are identical operators.

  

Figure 2.19: Separation of overlapping objects by applying the watershed segmentation to the distance transformation of the edges of the compound object

In [168], Vincent proposes several other applications, such as computing Delaunay triangulations, Gabriel graphs [61], relative neighborhood graphs [159], ...

Saito [140] uses the Euclidean DT to compute the 3D Voronoi diagram. Working on 3D microscopic images of a human liver, he proves that the shortest path from a portal vein to an hepatic vein is almost constant whatever point of the volume is considered. He also shows that the portal veins lie on or near the borders of the Voronoi diagram derived from the hepatic veins.

Starovoitov [149] and Warfield [175] use distance transformation for the analysis of multi-dimensional data-sets. Starovoitov defines an unsupervised clustering technique. Warfield uses the k-DT as a look-up table for k-NN classification, as discussed in section .

The main application of the geodesic distance transformation was described by Verbeek, Dorst, Verwer and Groen [165] and Lengyel, Reichert, Donald and Greenberg [93]. By backtracking the distance propagation, one can find the shortest path between any point and a single object pixel, the source of the propagation (Figure ). In particular, this can be used to control the motion of a robot. The geodesic DT is computed in the robot's multi-dimensional state space, where each dimension corresponds to a possible movement of the robot (translation, rotation, ...) and the propagation domain is restricted to possible robot locations.

  

Figure 2.20: Shortest path computation. Left: Original mask, source and target locations. Center: Geodesic distance from s, constrained by the mask. Right: Shortest Path between s and t, obtained by back-tracking the propagation of the Geodesic DT.

In [85], Jolesz, Lorensen, Shinmoto, Atsumi, Nakajima, Kava-naugh, Saiviroonporn, Seltzer, Silverman, Phillips and Kikinis apply Lengyel's method to generate the camera movements in an interactive virtual endoscopy application.

This concludes our short review of possible DT applications. Among them, several belonged to the field of medical image processing: those of Mangin [101], Bourland [15], Thiran [153], Saito [140], Warfield [175] and Jolesz [85].