Last update, August 4, 2004

BACK

References on Euclidean Distance Transforms (EDT) :

• Breu, H. et al.:
  • Linear Time Euclidean Distance Transform Algorithms, PAMI, 1995.
• Cuisenaire O. & Mack, B. :
  • Distance Transformations: Fast Algorithms and Applications to Medical Image Processing, PhD thesis, 1999.
  • Fast Euclidean distance transformations by propagation using multiple neighbourhoods, CVIU, 1999.
  • Fast and exact signed Euclidean distance transformation with linear complexity, ICASSP'99.
• Danielsson, P.-E. :
  • Euclidean Distance Mapping, 1980.
• Eggers, H. :
  • Two Fast Euclidean Distance Transformations in Z² Based on Sufficient Propagation, 1998.
  • Fast parallel Euclidean distance transformation in Z^n, 1997.
• Jackway, P.T., et al. :
  • On Computing the Exact Euclidean Distance Transform on Rectangular and Hexagonal Grids, 1999.
• Lee, Y.-H., et al. :
  • Parallel Computation of the Euclidean Distance Transform on the Mesh of Trees and the Hypercube Compute, 1997.
• Leymarie, F., et al. :
  • Fast Raster Scan Distance Propagation on the Discrete Rectangular Lattice, 1992.
• Ragnemalm, I. :
  • The Euclidean Distance Transform, 1993.
• Ye, Q.Z.:
  • The signed Euclidean distance transform and its applications, 1988.

BibTeX references .

URL's:

• Image processing toolbox of Mathworks: bwdist

Two linear time (and hence asymptotically optimal) algorithms for computing the Euclidean distance transform of a two-dimensional binary image are presented. The algorithms are based on the construction and regular sampling of the Voronoi diagram whose sites consist of the unit (feature) pixels in the image. The first algorithm, which is of primarily theoretical interest, constructs the complete Voronoi diagram. The second, more practical, algorithm constructs the Voronoi diagram where it intersects the horizontal lines passing through the image pixel centers. Extensions to higher dimensional images and to other distance functions are also discussed.

Index Terms: Distance transform, Voronoi diagram, algorithm, Euclidean distance.

Summary under:

• http://www.tele.ucl.ac.be/PEOPLE/OC/these/node19.html

Web links:

• On-line copy.
• At EPFL: http://itswww.epfl.ch/~cuisenai/dt.shtml

Medical image processing is a demanding domain, both in terms of CPU and memory requirements. The volume of data to be processed is often large (a typical MRI dataset requires 10 MBytes) and many processing tools are only useful to the physician if they are available as real-time applications, i.e. if they run in a few seconds at most. Of course, a large part of these demands are - and will be - handled by the development of more powerful hardware. On the other hand, when faced with non-linear computational complexity, the development of improved algorithms is obviously the best solution. Distance transformations, a powerful image analysis tool used in a number of problems such as image registration, requires such improvements.

A distance map is an image where the value of each pixel is the distance from this pixel to the nearest pixel belonging to a given set or object. A distance transformation (DT) is an algorithm that computes a distance map from a binary image representing this set of pixels. This definition is global in the sense that it requires finding the minimum on a set of distances computed between all image pixels and all object pixels. Therefore, a direct application of the definition usually leads to an unacceptable computational complexity. Numerous algorithms have been proposed to localize this definition of distance to the nearest pixel and allow a faster DT computation, but up to now, none of them combines both exactness and linear complexity.

Numerous applications of distance transformations to image analysis and pattern recognition have been reported and those related to medical image processing are explored in what follows.

Chapter 1 introduces a few basic concepts, a typical application of distance transformations in pattern recognition and the key challenges in producing a DT algorithm.

Chapter 2 contains an exhaustive critical review of published algorithms. The strong and weak points of the most popular ones are discussed and the core principles for our original algorithms are derived.

Chapters 3 (Euclidean distance transformation by propagation), 5 (Signed Euclidean DT with error detection and correction), 6 (Euclidean DT in 3 dimensions), 8 (Geodesic Distance Transformation) and 10 (k-NN classification and k-distance transformation) present original distance transformation algorithms. Each of those chapters is organized in a somewhat similar fashion. First we describe the algorithm. Then we evaluate its computational complexity and compare it to the state of the art.

Chapter 4 (Application: morphometry of nerve cross-sections), 7 (Application: registration of MR images), 9 (Application: Camera path-planning in virtual endoscopy) and 11 (Application: tissue classification in T1, T2 MR images) each present an application to a particular problem in medical image processing, using the algorithm developed in the previous chapter.

Ideally, the description of any medical image processing problem should include a medical justification of the need for an automated processing, a complete review of the state of the art in the field, a detailed description of the proposed processing method, and an evaluation of the accuracy of the results and their medical significance. Because of both time and space constraints in this thesis, such an exhaustive work will only be presented for the application in chapter 4, while the other applications will be described more briefly.

Chapter 3 describes a new exact Euclidean distance transformation using ordered propagation. It is based on a variation of Ragnelmam's [127] approximate Euclidean DT. We analyze the error patterns for approximate Euclidean DT using finite masks, and we derive a rule defining, for any pixel location, the size of the neighborhood that guarantees the exactness of the DT. This algorithm is particularly well-suited to implement mathematical morphology operations, which are examined in details.

In Chapter 4, we apply the algorithm of chapter 3 to the segmentation of neuronal fibers from microscopic images of the sciatic nerve. In particular, it is used to determine the thickness of the myelin sheath surrounding the center of the fiber. This study was carried out in collaboration with the Neural Rehabilitation Engineering Laboratory, UCL.

Chapter 5 proposes another exact Euclidean distance transformation, based on the explicit computation of the Voronoi division of the image. Possible error locations are detected at the corners of the Voronoi polygons and corrected if needed. This algorithm is shown to be the fastest exact EDT to date. It approaches the theoretical optimal complexity, a CPU time proportional to the number of pixels on which the distance is computed.

Chapter 6 investigates how the algorithms of chapters 3 and 5 can be extended to 3 dimensional images. It shows the limitations of both approaches and proposes an hybrid algorithm mixing the method of chapter 5 and Saito's.

In Chapter 7, the 3D Euclidean DT is applied to the registration of MR images of the brain where the matching criterion is the distance between the surfaces of similar objects (skin, cortex, ventricular system, ...) in both images. Examples are shown, from projects with the Neuro-physiology Laboratory, UCL, and with the Positron Tomography Laboratory, UCL.

Chapter 8 discusses an extension of the distance transformation concept: geodesic distances on non-convex domains. Because geodesic distances are based on the notion of paths, a trade-off has to be introduced between the accuracy with which straight lines are represented and the way curves of the domain are followed. It is shown that, whatever the trade-off chosen, there is an efficient implementation of the geodesic DT by propagation. By back-tracking the geodesic distance propagation, one can find the shortest path between a target and a starting point.

In chapter 9, this is used to plan the optimal path for the camera movements in virtual endoscopy, a work done in collaboration with the Surgical Planning Laboratory, Harvard Medical School, Boston.

Chapter 10 extends the Euclidean distance transformation from finding the nearest object pixel to finding the k nearest object pixels. It is shown that this can be done with a complexity increasing linearly with k.

In Chapter 11, the k-DT is used as a fast implementation of the k Nearest Neighbors (k-NN) classification between different tissue types in multi-modal MR imaging. This is illustrated through the classification of multiple sclerosis lesions from T1-T2 images, provided by the Radiology unit, St-Luc Hospital, UCL, via the Positron Tomography Laboratory, UCL.

Finally, a general conclusion is drawn. It reviews the main contributions of the thesis, its applications and explores some new domains in which their applications could also be useful. Ultimately, the publications related to this thesis are briefly reviewed.

We propose a new exact Euclidean distance transformation (DT) by propagation, using bucket sorting. A fast but approximate DT is first computed using a coarse neighborhood. A sequence of larger neighborhoods is then used to gradually improve this approximation. Computations are kept short by restricting the use of these large neighborhoods to the tile borders in the Voronoi diagram of the image. We assess the computational cost of this new algorithm and show that it is both smaller and less image-dependent than all other DTs recently proposed. Contrary to all other propagation DTs, it appears to remain o(n2) even in the worst-case scenario.

Paper on-line.

We propose a new signed or unsigned Euclidean distance transformation algorithm, based on the local corrections of the well-known 4SED algorithm of Danielsson. Those corrections are only applied to a small neighborhood of a small subset of pixels from the image, which keeps the cost of the operation low. In contrast with all fast algorithms previously published, our algorithm produces perfect Euclidean distance maps in a time linearly proportional to the number of pixels in the image. The computational cost is close to the cost of the 4SSED approximation.

Two new error-free sequential Euclidean distance transformations (EDT) for binary images in Z² are introduced: sufficient d_1-propagation and sufficient d_inf-propagation. Both methods use ordered propagation, i.e. iterative propagation via contour pixels. However, we restrict the propagation to unique shortest Euclidean paths, the sufficient propagation paths. Moreover, we ensure error-free direct pixel update by adding a distance suggestion to each propagation pixel. Using these ideas, we avoid many unneccesary calculations. The computational tests show that our algorithms, used as signed and as unsigned methods, are significantly faster than other well-known signed and unsigned EDTs. Comparing both methods, sufficient d_inf-propagation yields the better average performance.

We introduce a new Euclidian distance transformation (EDT) for binary images in Z^n, n>=3 by combining our sufficient propagation EDT with the method of Saito & Toriwaki. Test in Z³ show that this new method is always faster than the well known EDTs and, especially, faster than the raster-scanning chamfer distance transformation. Moreover, we can efficiently implement it in parallel using a divide-&-conquer strategy.

The distance transform is an operation that converts an image consisting of black and white pixels to an image where each pixel has a value or coordinate that represents the distance or location to the nearest black pixel. It is a basic operation in image processing and computer vision fields, used for expanding, shrinking, thinning, segmentation, clustering, computing shape, object reconstruction, etc. There are many approximate Euclidean distance transform algorithms in the literature, but finding the distance transform with respect to the Euclidean metric is rather time consuming. So, it is important to increase the computing speed. The parallel algorithms discussed are for the computation of exact Euclidean distance transform for all pixels with respect to black pixels in an N × N binary image. The object of this paper is to develop the time-optimal algorithms. O(log N) time-optimal algorithms are proposed for both mesh of trees and hypercube computer. The number of processors used to solve this problem for the former is N × N × N/log N and that for the latter is N2.5, respectively. A generalized algorithm is also proposed for a reduced three-dimensional mesh of trees and it can be computed in O(m log N) time using N × N × N/m log N processors, where m is a constant and 1 </= m </= N/log N. Compared to the previous result, the time complexity of the generalized algorithm is inversely proportional to the number of processors used by a factor of m times.

The main result of this paper is that simple (raster scan) sequential algorithms for computing Euclidean Distance Transforms can be implemented in an optimized manner from the point of view of numerical computations. We will show that these fast implementations have computational complexities comparable to the city block, chessboard and other simple chamfer Distance Transforms.

Keywords: Euclidean and pseudo-Euclidean Distance Transforms, discrete rectangular lattice, numerical complexity and accuracy.

Download paper.

Uses the method of Danielsson with signed vector valued masks.

Page created & maintained by Frederic Leymarie, 1998-2004.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu