Image Processing Toolbox™

bwdist - Distance transform of binary image

Syntax

D = bwdist(BW) [D,L] = bwdist(BW) [D,L] = bwdist(BW,method)

Description

D = bwdist(BW) computes the Euclidean distance transform of the binary image BW. For each pixel in BW, the distance transform assigns a number that is the distance between that pixel and the nearest nonzero pixel of BW. bwdist uses the Euclidean distance metric by default. BW can have any dimension. D is the same size as BW.

[D,L] = bwdist(BW) also computes the nearest-neighbor transform and returns it as label matrix L, which has the same size as BW and D. Each element of L contains the linear index of the nearest nonzero pixel of BW.

[D,L] = bwdist(BW,method) computes the distance transform, where method specifies an alternate distance metric. method can take any of the following values. The method string can be abbreviated.

Method	Description
`'chessboard'`	In 2-D, the chessboard distance between `(x`₁`,y`₁`)` and `(x`₂`,y`₂`)` is
`'cityblock'`	In 2-D, the cityblock distance between `(x`₁`,y`₁`)` and `(x`₂`,y`₂`)` is
`'euclidean'`	In 2-D, the Euclidean distance between `(x`₁`,y`₁`)` and `(x`₂`,y`₂`)` is This is the default method.
`'quasi-euclidean'`	In 2-D, the quasi-Euclidean distance between `(x`₁`,y`₁`)` and `(x`₂`,y`₂`)` is

Note bwdist uses fast algorithms to compute the true Euclidean distance transform, especially in the 2-D case. The other methods are provided primarily for pedagogical reasons. However, the alternative distance transforms are sometimes significantly faster for multidimensional input images, particularly those that have many nonzero elements.

Class Support

BW can be numeric or logical, and it must be nonsparse. D and L are double matrices with the same size as BW.

Examples

Compute the Euclidean distance transform.

bw = zeros(5,5); bw(2,2) = 1; bw(4,4) = 1
bw =
     0     0     0     0     0
     0     1     0     0     0
     0     0     0     0     0
     0     0     0     1     0
     0     0     0     0     0

[D,L] = bwdist(bw)

D =
    1.4142    1.0000    1.4142    2.2361    3.1623
    1.0000         0    1.0000    2.0000    2.2361
    1.4142    1.0000    1.4142    1.0000    1.4142
    2.2361    2.0000    1.0000         0    1.0000
    3.1623    2.2361    1.4142    1.0000    1.4142

L =
     7     7     7     7     7
     7     7     7     7    19
     7     7     7    19    19
     7     7    19    19    19
     7    19    19    19    19

In the nearest-neighbor matrix L the values 7 and 19 represent the position of the nonzero elements using linear matrix indexing. If a pixel contains a 7, its closest nonzero neighbor is at linear position 7.

Compare the 2-D distance transforms for each of the supported distance methods. In the figure, note how the quasi-Euclidean distance transform best approximates the circular shape achieved by the Euclidean distance method.

bw = zeros(200,200); bw(50,50) = 1; bw(50,150) = 1;
bw(150,100) = 1;
D1 = bwdist(bw,'euclidean');
D2 = bwdist(bw,'cityblock');
D3 = bwdist(bw,'chessboard');
D4 = bwdist(bw,'quasi-euclidean');
figure
subplot(2,2,1), subimage(mat2gray(D1)), title('Euclidean')
hold on, imcontour(D1)
subplot(2,2,2), subimage(mat2gray(D2)), title('City block')
hold on, imcontour(D2)
subplot(2,2,3), subimage(mat2gray(D3)), title('Chessboard')
hold on, imcontour(D3)
subplot(2,2,4), subimage(mat2gray(D4)), title('Quasi-Euclidean')
hold on, imcontour(D4)

Compare isosurface plots for the distance transforms of a 3-D image containing a single nonzero pixel in the center.

bw = zeros(50,50,50); bw(25,25,25) = 1;
D1 = bwdist(bw);
D2 = bwdist(bw,'cityblock');
D3 = bwdist(bw,'chessboard');
D4 = bwdist(bw,'quasi-euclidean');
figure
subplot(2,2,1), isosurface(D1,15), axis equal, view(3)
camlight, lighting gouraud, title('Euclidean')
subplot(2,2,2), isosurface(D2,15), axis equal, view(3)
camlight, lighting gouraud, title('City block')
subplot(2,2,3), isosurface(D3,15), axis equal, view(3)
camlight, lighting gouraud, title('Chessboard')
subplot(2,2,4), isosurface(D4,15), axis equal, view(3)
camlight, lighting gouraud, title('Quasi-Euclidean')

Algorithm

For two-dimensional Euclidean distance transforms, bwdist uses the second algorithm described in

[1] Breu, Heinz, Joseph Gil, David Kirkpatrick, and Michael Werman, "Linear Time Euclidean Distance Transform Algorithms," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, No. 5, May 1995, pp. 529-533.

For higher dimensional Euclidean distance transforms, bwdist uses a nearest-neighbor search on an optimized kd-tree, as described in

[1] Friedman, Jerome H., Jon Louis Bentley, and Raphael Ari Finkel, "An Algorithm for Finding Best Matches in Logarithmic Expected Time," ACM Transactions on Mathematics Software, Vol. 3, No. 3, September 1977, pp. 209-226.

For cityblock, chessboard, and quasi-Euclidean distance transforms, bwdist uses the two-pass, sequential scanning algorithm described in

[1] Rosenfeld, A. and J. Pfaltz, "Sequential operations in digital picture processing," Journal of the Association for Computing Machinery, Vol. 13, No. 4, 1966, pp. 471-494.

The different distance measures are achieved by using different sets of weights in the scans, as described in