bwdist

Distance transform of binary image

Syntax

D = bwdist(BW)

[D,idx] = bwdist(BW)

[D,idx] = 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.

[D,idx] = bwdist(BW) also computes the closest-pixel map in the form of an index array, idx. Each element of idx contains the linear index of the nearest nonzero pixel of BW. The closest-pixel map is also called the feature map, feature transform, or nearest-neighbor transform.

[D,idx] = bwdist(BW,method) computes the distance transform using an alternate distance metric, specified by method.

Examples

Compute the Euclidean Distance Transform

This example shows how to compute the Euclidean distance transform of a binary image, and the closest-pixel map of the image.

Create a binary image.

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

bw = 5×5

     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

Calculate the distance transform.

[D,IDX] = bwdist(bw)

D = 5x5 single matrix

    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

IDX = 5x5 uint32 matrix

    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 IDX 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 2-D Distance Transforms for Supported Distance Methods

This example shows how to compare the 2-D distance transforms for 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');
RGB1 = repmat(rescale(D1), [1 1 3]);
RGB2 = repmat(rescale(D2), [1 1 3]);
RGB3 = repmat(rescale(D3), [1 1 3]);
RGB4 = repmat(rescale(D4), [1 1 3]);

figure
subplot(2,2,1), imshow(RGB1), title('Euclidean')
hold on, imcontour(D1)
subplot(2,2,2), imshow(RGB2), title('Cityblock')
hold on, imcontour(D2)
subplot(2,2,3), imshow(RGB3), title('Chessboard')
hold on, imcontour(D3)
subplot(2,2,4), imshow(RGB4), title('Quasi-Euclidean')
hold on, imcontour(D4)

Compare Isosurface Plots for Distance Transforms of 3-D Image

This example shows how to 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')

Input Arguments

BW — Binary image

numeric array | logical array

Binary image, specified as a numeric or logical array of any dimension. For numeric input, any nonzero pixels are considered to be 1 (true).

Data Types: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | logical

method — Distance metric

'euclidean' (default) | 'chessboard' | 'cityblock' | 'quasi-euclidean'

Distance metric, specified as one of these values.

Method	Description
'chessboard'	In 2-D, the chessboard distance between (x1,y1) and (x2,y2) is max(│x1 – x2│,│y1 – y2│).
'cityblock'	In 2-D, the cityblock distance between (x1,y1) and (x2,y2) is │x1 – x2│ + │y1 – y2│
'euclidean'	In 2-D, the Euclidean distance between (x1,y1) and (x2,y2) is $$\sqrt{{(x_1-x_2)}^2+{(y_1-y_2)}^2}.$$
'quasi-euclidean'	In 2-D, the quasi-Euclidean distance between (x1,y1) and (x2,y2) is $$\left|x_1-x_2\right|+(\sqrt{2}-1)\left|y_1-y_2\right|,\left|x_1-x_2\right|>\left|y_1-y_2\right|$$ $$(\sqrt{2}-1)\left|x_1-x_2\right|+\left|y_1-y_2\right|,\text{ otherwise}\text{.}$$

For more information, see Distance Transform of a Binary Image.

Data Types: char | string

Output Arguments

D — Distance array

numeric array

Distance, returned as a numeric array of the same size as BW. The value of each element is the distance between that pixel and the nearest nonzero pixel in BW, as defined by the distance metric, method.

Data Types: single

idx — Index array

numeric array

Index array, returned as a numeric array of the same size as BW. Each element of idx contains the linear index of the nearest nonzero pixel of BW. The class of idx depends on the number of elements in the input image, and is determined as follows.

Class	Range
'uint32'	numel(BW) <= 232 − 1
'uint64'	numel(BW) >= 232

Data Types: uint32 | uint64

Tips

• 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.

• The function bwdist changed in version 6.4 (R2009b). Previous versions of the Image Processing Toolbox used different algorithms for computing the Euclidean distance transform and the associated label matrix. If you need the same results produced by the previous implementation, use the function bwdist_old.

Algorithms

• For Euclidean distance transforms, bwdist uses the fast algorithm. [1]

• For cityblock, chessboard, and quasi-Euclidean distance transforms, bwdist uses the two-pass, sequential scanning algorithm. [2]

• The different distance measures are achieved by using different sets of weights in the scans, as described in [3].

References

[1] Maurer, Calvin, Rensheng Qi, and Vijay Raghavan, "A Linear Time Algorithm for Computing Exact Euclidean Distance Transforms of Binary Images in Arbitrary Dimensions," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 25, No. 2, February 2003, pp. 265-270.

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

[3] Paglieroni, David, "Distance Transforms: Properties and Machine Vision Applications," Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing, Vol. 54, No. 1, January 1992, pp. 57-58.

Extended Capabilities

C/C++ Code Generation

Generate C and C++ code using MATLAB® Coder™.

Usage notes and limitations:

• bwdist supports the generation of C code (requires MATLAB^® Coder™). Note that if you choose the generic MATLAB Host Computer target platform, bwdist generates code that uses a precompiled, platform-specific shared library. Use of a shared library preserves performance optimizations but limits the target platforms for which code can be generated. For more information, see Types of Code Generation Support in Image Processing Toolbox.

• When generating code, the optional second input argument, method, must be a compile-time constant. Input images must have less than 2³² pixels.

GPU Code Generation

Generate CUDA® code for NVIDIA® GPUs using GPU Coder™.

Usage notes and limitations:

• When generating code, the optional second input argument, method, must be a compile-time constant. Input images must have fewer than 2³² pixels.

Thread-Based Environment

Run code in the background using MATLAB® backgroundPool or accelerate code with Parallel Computing Toolbox™ ThreadPool.

This function fully supports thread-based environments. For more information, see Run MATLAB Functions in Thread-Based Environment.

GPU Arrays

Accelerate code by running on a graphics processing unit (GPU) using Parallel Computing Toolbox™.

Usage notes and limitations:

• Input images must be 2-D and have less than 2³² elements.

• The method argument only supports the 'euclidean' distance metric.

For more information, see Image Processing on a GPU.

Version History

Introduced before R2006a

R2022b: Support for thread-based environments

bwdist now supports thread-based environments.