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.

example

[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

collapse all

Compute the Euclidean Distance Transform

Open Live Script

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

Open Live Script

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)

Figure contains 4 axes objects. Hidden axes object 1 with title Euclidean contains 2 objects of type image, contour. Hidden axes object 2 with title Cityblock contains 2 objects of type image, contour. Hidden axes object 3 with title Chessboard contains 2 objects of type image, contour. Hidden axes object 4 with title Quasi-Euclidean contains 2 objects of type image, contour.

Compare Isosurface Plots for Distance Transforms of 3-D Image

Open Live Script

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')

Figure contains 4 axes objects. Axes object 1 with title Euclidean contains an object of type patch. Axes object 2 with title City block contains an object of type patch. Axes object 3 with title Chessboard contains an object of type patch. Axes object 4 with title Quasi-Euclidean contains an object of type patch.

Input Arguments

collapse all

`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).

`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 (x₁,y₁) and (x₂,y₂) is max(│x₁ – x₂│,│y₁ – y₂│).
`'cityblock'`	In 2-D, the cityblock distance between (x₁,y₁) and (x₂,y₂) is │x₁ – x₂│ + │y₁ – y₂│
`'euclidean'`	In 2-D, the Euclidean distance between (x₁,y₁) and (x₂,y₂) is $\sqrt{{(x_{1} - x_{2})}^{2} + {(y_{1} - y_{2})}^{2}} .$
`'quasi-euclidean'`	In 2-D, the quasi-Euclidean distance between (x₁,y₁) and (x₂,y₂) is $\| x_{1} - x_{2} \| + (\sqrt{2} - 1) \| y_{1} - y_{2} \|, \| x_{1} - x_{2} \| > \| y_{1} - y_{2} \|$ $(\sqrt{2} - 1) \| x_{1} - x_{2} \| + \| y_{1} - y_{2} \|, otherwise .$

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

Data Types: char | string

Output Arguments

collapse all

`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)` <= 2³² − 1
`'uint64'`	`numel(BW)` >= 2³²

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

expand all

R2022b: Support for thread-based environments

bwdist now supports thread-based environments.

bwdist

Syntax

Description

Examples

Compute the Euclidean Distance Transform

Compare 2-D Distance Transforms for Supported Distance Methods

Compare Isosurface Plots for Distance Transforms of 3-D Image

Input Arguments

`BW` — Binary image
numeric array | logical array

`method` — Distance metric
`'euclidean'` (default) | `'chessboard'` | `'cityblock'` | `'quasi-euclidean'`

Output Arguments

`D` — Distance array
numeric array

`idx` — Index array
numeric array

Tips

Algorithms

References

Extended Capabilities

C/C++ Code Generation
Generate C and C++ code using MATLAB® Coder™.

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

Thread-Based Environment
Run code in the background using MATLAB® `backgroundPool` or accelerate code with Parallel Computing Toolbox™ `ThreadPool`.

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

Version History

R2022b: Support for thread-based environments

See Also

Topics

bwdist

Syntax

Description

Examples

Compute the Euclidean Distance Transform

Compare 2-D Distance Transforms for Supported Distance Methods

Compare Isosurface Plots for Distance Transforms of 3-D Image

Input Arguments

BW — Binary image numeric array | logical array

method — Distance metric 'euclidean' (default) | 'chessboard' | 'cityblock' | 'quasi-euclidean'

Output Arguments

D — Distance array numeric array

idx — Index array numeric array

Tips

Algorithms

References

Extended Capabilities

C/C++ Code Generation Generate C and C++ code using MATLAB® Coder™.

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

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

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

Version History

R2022b: Support for thread-based environments

See Also

Topics

`BW` — Binary image
numeric array | logical array

`method` — Distance metric
`'euclidean'` (default) | `'chessboard'` | `'cityblock'` | `'quasi-euclidean'`

`D` — Distance array
numeric array

`idx` — Index array
numeric array

C/C++ Code Generation
Generate C and C++ code using MATLAB® Coder™.

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

Thread-Based Environment
Run code in the background using MATLAB® `backgroundPool` or accelerate code with Parallel Computing Toolbox™ `ThreadPool`.

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