The Euclidean Distance Transform In Arbitrary Dimensions

290

The Euclidean Distance Transform in arbitrary dimensions I Ragnemalm Linkaping University, Sweden

Abst;ract

algorithms in 3 and higher dimensions by Mohr and Bajcsy [4] and Borgefors [I].

The sequential, raster scanning algorithm for performing Euclidean Distance Transformation of binary images

proposed by Danielsson is not separable. This makes them useful only on single processor systems. In this paper, we suggest variants for 2. 3 and arbitrary dimensions that are separable, which makes them suitable for many types of parallel architectures as well. The results include a 4-scan algorithm for 3-dimensional images.

-

v Mask l a

Mask l b

Intmdudon The Euclidean Distance Transform, (EDT) invented by Danielsson [3]. allows the generation of distance maps with no significant errors. Later versions of the algorithm generate completely error-free Euclidean distance maps [9.6]. The superior precision of the EDT over other distance transformation algorithms is possible due to the use of vectors instead of scalar values for the propagation of distance values. Pseudo-Euclidean algorithms [2. 51 can get close to Euclidean metric, but they always have errors proportional to distance. The generalization of distance maps, and Euclidean distance maps in particular, to 3 or arbitrary dimensions has received relatively little attention. Algorithms for 3D with some generalization has been described by Mohr and Bajcsy [4] and Borgefors [l].

In this paper, a number of new algorithms for EDT in 3 and higher dimensions are presented. We will not describe the processing of EDT in detail, but rather define algorithms with the neighbourhoods (masks) used. Detailed descriptions of the Euclidean distance transform are found in [3, 101. We limit the discussion to raster scanning, sequential algorithms, as proposed by Rosenfeld [8].

cMask 2a

Mask 2b

Figure I . The original 2-dimensional EDT.

In Figure 1. each mask pair la. l b resp. 2%2b result in propagations in half of all possible directions. Each pixel holds a two-component vector. These vectors, pointing to the center pixel (0.0). are the offset vectors used in the algorithm, These vectors will be omitted in the following figures. One separable Euclidean distance transform for 2dimensional images is the three-scan EDT suggested in 171 and illusbrated in Figure 2. .*,,I

+

................,

U

Separable Euclidean distance transforms We define a separable EDT algorithm as an algorithm where the scans can be applied independently, in any order. A non-separable EDT algorithm uses scans that are dependent of each other, combining several masks in one scan. The terms separable and non-separable are equivalent to single-scanning resp. double-scanning in [7]. In the original 8SSED algorithm, as proposed by Danielsson [3] and illustrated in Figure 1, each line is scanned back and forth, thereby makiig two scam of each line for each scan through the image. Hence, this algorithm is not separable. The same holds for the

Figure 2.3-scan EDT. Separable algorithms are useful for iniplernentation on parallel architectures, but they are also quite useful on single processor systems. In this paper, we will present separable algorithms for 3 and arbitrary dimensions. We will put the following constraints on our algorithms.

Authorized licensed use limited to: Isfahan University of Technology. Downloaded on May 25, 2009 at 07:49 from IEEE Xplore. Restrictions apply.

291

- We use only immediate neighbours, that is, for the voxel in position (x1.xZ.x3...) we may use neighbours at positions (x,+dl. xz+d2. x3+d3...) where di E ( -1.0.+1 1. - We use separable algorithms. since they can be implemented in parallel. - We try to minimize the number of scans.

The dimdon space In a separable Euclidean distance transform, each scan will support propagation over some part of the direction space, and the union of these parts should cover the entire direction space completely. This necessary requirement is discussed in 17).

In 2-dimensional images, the direction space is simple: a 1-dimensional unit circle. It is very simple to analyze algorithms to see what parts of the direction space are supported by each scan, and then confirm that the entire direction space is covered. Such a coverage check is easily done e.g. in Figure 2 above. The direction space for 3-dimensional images is a 2dimensional space, a unit sphere. In order to analyze and visualize this space, a seaightfonvard approach could be to map the directions on this sphere. However, a segmented sphere is hard to represent on a 2D plane.

From direction space to algorithms With the Unfolded Cube graph as a tool, we will now search for 3D operators useful for a 3D version of EDT. As previously stated. we are only interested in algorithms using neighbourhoods which are subsets within the 3.3.3 neighbourhood. It is of no use to include voxels forward in the scanning directions since they do not contribute to the directions supported. Hence, the largest reasonable mask within 3.3.3 is the one shown in Figure 4. It is not difficult to fmd that the Unfolded Cube Graph for such a mask, displaying the parts of the direction space where propagation is supported by the mask, is the one shown in Figure 5 . This Unfolded Cube Graph, as well as the following ones, can be found directly from the mask, but have also been verified with computer experiments.

Figure 4 . The fargest mark within a 3.3.3 neighbourhood rcseful for separable EDT algorithmr.

n

Instead, we will use a different method which we call Unfolded Cube Graphs. In this case, the direction space is mapped on a cube, which we can display unfolded in 2D. This kind of graph is more suitable than graphs using spheres, not only because it is easier to map on a 2D plane, but also because of the close relation between the Cartesian grid and the direction segments to be supported. Figure 3 illustrates how the Unfolded Cube Graph works. The needle in the figure defmes a direction from the center of the cube. This direction is mapped on a point in the Unfolded Cube Graph.

Figure 5 . The Unfolded Cube Graph corresponding to the mask in Figure 4 . The fewer scans we need, the faster the algorithm will run. By inspecting the Unfolded Cube Graphs, we have found a solution using only four scans. illustrated in Figure 6. The four scans are symmetrical. The Unfolded Cube Graph for one scan is shown in Figure 7.

U

Figure 3 . The Unfolded Cube Graph

Figure 6. The four m a s h in the 4-scan algorithm, the algorithm with the smallest possible number of scans.

Authorized licensed use limited to: Isfahan University of Technology. Downloaded on May 25, 2009 at 07:49 from IEEE Xplore. Restrictions apply.

292

n

Figure 7 . The correvonding Unfolded Cube Graphfor one of the masks in Figure 6. (Bottom lefi.) While it is possible to make mask sets of other shapes, it is not possible to make a 3 D algorithm of this kind with fewer than 4 scans. We will give a brief outline of a proof of this statement. Consider an arbitrarily small circle in the center of each of the six sides of the cube in the Unfolded Cube Graph. All circles (as well as the rest of the direction cube) must be covered by at least one of the scam used. See Figure 8.

n

Figure 10. The Unfolded Cube Graph corresponding to the mask in Figure 9.

Arbitrary dimensions The optimal solutions for 2D and 3 D (3-scan and 4scan, respectively) have proven difficult to generalize to higher dlnensions. However, we have found sub-optimal algorithms for which this is possible. While pixels in 3 D are generally called voxels. and Borgefors [ l ] suggests the name rexel for a pixel in 4dimensional space, there appears to exist no name in the literature for pixels in arbitrary dimensions. We suggest the name hoxel (high order pixel). We will describe one algorithm which is easy to generalize due to symmetry, and which can be modified for various neighbourhood sizes. We call it the Corner EDT. Though this is far from the optimal solution. it is reasonably fast. Its simplest 3 D version consists of eight masks. each with the shape shown in Figure 11.

Figure 8. The centers of each side of the cube

In Figure 8. we can

see that one single scan like the

1 3 7 . 1 - cucles out of the 2 8- 8

one in Figure 4 will cover 1 +-+--

six circles. Hence, it is impossible to fill the entire Unfolded Cube Graph with only three scam. We claim that larger neighbourhoods than 3.3.3 are not of practical interest. To motivate this claim, we examine the 5.5.5 case. The largest neighbourhood is shown in Figure 9. The mask demands significantly more processing time compared to the mask in Figure 4, but the gain in direction space is marginal. See Figure 10. In particular, the proof above still holds for this mask, so it is still impossible to make an algorithm with less than 4 scans.

Figure 11. One of eight masks needed for 6-neighbour Corner EDT. This is the minimal, 6-voxel neighbourhood version of the Comer EDT. It is easy to modify it to 18- or 26voxel neighbourhoods. In all these cases, the Unfolded Cube Graph will be identical. It is shown in Figure 12.

n

Figure 12. Unfolded Cube Graphfor Figure 11. Figure 9. The largest useful mask within a 5.55 neighbourhood.

The masks for each scan consists of the center voxel and each voxel on step backwards along each scanning direction. These masks can be realized in any dimension.

Authorized licensed use limited to: Isfahan University of Technology. Downloaded on May 25, 2009 at 07:49 from IEEE Xplore. Restrictions apply.

293

In 2D. we need four masks (and four scans), in 3D we need eight masks, in 4D 16 masks etc. The number of neighbours in each mask grows obviously from 2 to 3 to 4 etc. In n dimensions. we need 2” masks, each with center hoxel and n neighbours.

For each n-dimensional space, a number of different algorithms are possible, all with the high precision that the EDT gives, but still with a few small errors. The more neighbours we use, the fewer errors will we get. The extreme cases are n neighbours as mentioned above, which is the fastest. but with the lowest precision (a higher number of hoxek with a small error), and 3”-1 neighbours. which gives the highest precision. Since the precision of the fmt, simplest case is good enough for any reasonable application, we no not describe the other cases in detail. We end this section with a more compact definition of the U-neighbour Comer EDT.

r FDT. n n

m

We have a set of scan directions: (di, ic{l..n))c {-I, +I) For each set of di possible (2” different ones), we have one scan, where for each center hoxel (x, ... x n ) , the following neighbours are used: n

U (XI,

XZ,..., xi-I

I

xi + di,

I

xi+l ...,xn)

3”-neighbour EDT 2n-neighbour Corner EDT (S) 3”mighbour Corner EDT (S)

Conclusions We have presented separable algorithms for computing EDT in 3 or higher dimensions, as well as some principles behind the algorithm design. For this task, we use a new tool, the Unfolded Cube Graph, to visualize the 2dimensional direction space for 3-dimensional images. This graph proved to be very suitable for the kind of analysis needed. Among the results are a 4-scan algorithm for 3dimensional images and an algorithm for arbitrary dimensions,

References [l]

G. Borgefors. “Distance Transformations in Arbivary Dimensions”. Computer Graphics and Image Processing 27, 1984. pp. 321-345.

G. Borgefors, “Distance Transformations in Digital Images”. Computer Vision, Graphics and Image Processing 34. 1986. pp 344-371. [31 P.E. ~ ~ i “Euclidean ~ l Distance ~ ~Mapping”, ~ ~ Computer Graphics and Image Processing 14, 1980. pp. 227-248.

[2]

TO evaluate the performance of different algorithms, we should examine key operations m e the number of memory accesses and the number of arithmetic operations. An even simple measure is the number of masks, which

is he

of times the center pixel be As long as the mask sizes are reasonably small, this is an acceptable simplification.

141 R. Mob. R. Bajcsy. “Packing volumes by spheres”. IEEE Trans. on Pattern Analysis and Machine Infelligence, Vol PAMI-5, no 1 , 1983, pp 111-116. [5]

Another simple measure is the total number of members in all masks. For small masks, this is not so accurate since the processing of the center pixel takes more time than the processing of the neighbours. Below, a small collection of Euclidean distance transformation algorithms is listed, with the number of scam (number of masks) and the total number of members in all masks used. The calculation of the number of mask members is left out due to space limitations. Algorithms marked with (S) are separable.

[6]

[7]

[8]

Aborthm-S!a@sLPixel accesses 2 dimensions: BSSED 3-scan EDT (S) 3 dimensions: 6-neighbour EDT 26-neighbour EDT 6-neighbour Corner EDT (S) 26-neighbour Corner EDT (S) 4-scan (26-neighbour) EDT (S) Arbitrary (n) dimensions: 2n-neighbour EDT

2.3”-2” 2”(n+l) 4”

It is evident from the table that the non-separable algorithms have a considerable advantage over Comer EDT on single processor architectures. The algorithms using the smallest number of scans possible (3-scan and 4-scan in the table), however, have much better performance and are good choices for single processor and parallel systems alike.

i-1

Performance

2“ 2” 2“

4 3

14 14

8 8 8 8 4

22 32 64 52

2”

3.2” - 2

46

[9]

U. Montanari. “A Method for Obtaining Skeletons Using a Quasi-Euclidean Distance”. Journal of the ACM, vol 15 No 4 , 1968. pp 600-624. I. Ragnemalm, “Contour processing distance transforms”, in: Cantoni et. al., eds. Progress in Image Analysis and Processing, World Scientific, Singapore, 1990, pp 204-212. I. Ragnemalm, ‘The Euclidean Distance Transform and its implementation on SIMD architectures”. Proceedings, 6th Scandinavian Conf. on Image Analysis, 1989, pp 379-384. A. Rosenfeld, J.L.Pfaltz, “Sequential Operations in Digital Picture Processing”, Journal of the ACM, Vol 13, No 4, 1966, pp 471-494. H. Yamada, “Complete Euclidean Distance Transformation By Parallel Operation”, Proceedings, 7;th International Conference on Pattern Recognition, 1984. pp 69-71.

[ 101 Q.Z. Ye, ‘The Signed Euclidean Distance Transform and Its Applications”, Proceedings, 9:th International Conference on Pattern Recognition. 1988, pp 495-499.

Authorized licensed use limited to: Isfahan University of Technology. Downloaded on May 25, 2009 at 07:49 from IEEE Xplore. Restrictions apply.

,