Today I want to know if you've heard of an operation sometimes called the feature transform, and whether you've had a particular application for it.
But first, greetings to those who attended the SPIE Electronic Imaging Conference in California last week. I heard yesterday that several people who stopped at the MathWorks booth mentioned the blog. Sorry I missed you! Your feedback has motivated me to get back to the keyboard and put up some new posts.
Now about the feature transform. I've been thinking about this operation because we've been having some design discussions recently about an Image Processing Toolbox function called bwdist, which computes the Euclidean distance transform. For each pixel in a binary image, bwdist computes the distance between that pixel and the nearest foreground (nonzero) pixel.
Here's a small example to show you what I mean.
bw = magic(5) > 21
bw =
0 1 0 0 0
1 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 1 0 0
D = bwdist(bw)
D =
1.0000 0 1.0000 2.0000 2.0000
0 1.0000 1.4142 1.4142 1.0000
1.0000 1.4142 2.0000 1.0000 0
2.0000 1.4142 1.0000 1.4142 1.0000
2.0000 1.0000 0 1.0000 2.0000
And here's a bigger example, where I display the distance transform as a false-color image.
bw2 = false(400, 400); bw2(200, 200) = true; bw2(100, 100:300) = true; bw2(300, 100:300) = true; bw2(100:300, 100) = true; bw2(100:300, 300) = true; imshow(bw2)
D2 = bwdist(bw2); imshow(D2, []) colormap(copper)
It seems that not many people (even at MathWorks!) know that bwdist has an optional second output that tells you, for each image pixel, which foreground pixel it is closest to. This is the thing that's sometimes called the feature transform, or closest feature transform. The second output is a matrix of linear indices. (See my linear indexing post.) Here's what it looks like for the small matrix I started with.
bw
bw =
0 1 0 0 0
1 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 1 0 0
[D, L] = bwdist(bw); L
L =
2 6 6 6 23
2 6 6 23 23
2 2 15 23 23
2 15 15 15 23
15 15 15 15 23
Looking at L tells us that the pixel with linear index 2 (2nd row, 1st column) is the closest foreground pixel to 5 image pixels, including itself. (Ties are broken in some arbitrary fashion.)
I've come across one user application for this capability: a 3-D blood vessel tracing algorithm that I mentioned in this old post from 2006.
Do you have an application for the feature transform? Let us know by commenting.
Get
the MATLAB code
Published with MATLAB® 7.7
Uncannily, I’ve just coded something that does roughly this for my print2im function. If only I’d known about bwdist!
My problem is slightly different in that I don’t care about background pixels that are too far away (> 4 pixels in x or y) from any foreground pixel. This allowed me to use convolution and powers of 2 to make it fast (without the IPT).
Steve, it’s hard to visualize the L matrix but even more so because it uses linear indexing. But basically it’s like a little vector pointing to the closest foreground pixel. It might be illustrative if we could visualize it like a vector field, like they use to show optical flow. Given that, potential applications might be easier to envision. For example, maybe it could be used to fill a hole in an object – with edge gray levels instead of uniform gray levels as is most common. The filled hole may look more smooth and natural than just a solid uniform patch. (Though this is probably not as smooth as a weighted average of all edge pixels.)
Mark—Visualizing the feature transform using something like a quiver plot is a good idea. I’ll put it on my list of blog ideas. As for filling holes smoothly, you should check out roifill, which does a kind of “soap-film” smooth interpolation from boundary pixels of arbitrary regions.
Hi Steve,
How to find out whether a pixel is foreground or backgroundin binary image using matlab
Thanks in advance
Sanjay—Zero-valued pixels are background. Nonzero-valued pixels are foreground.
Hi Steve,
What about classification of background and foreground pixels in images before the binarization in MATLAB? This would be helpful to binarize images in complex natural scene images..
Amey—Binarization is the classification of background and foreground pixels in images.
Hi Steve,
Are there any equivalents to bwdist in matlab that can find out the distance transform between two binary images??
Thanks
googleavi
Googleavi—Please define “distance transform between two binary images.”
Hi,
I am trying to find the length and location of the shortest path between objects. It seems like some application of bwdist should be able to do this. Any advice?
Example:
1 0 1
0 1 0
0 0 0
0 1 0
1 0 1
Should yield
0 0 0
0 0 0
0 p 0
0 0 0
0 0 0
With p = path length = 1
Thanks in advance
Bogdan—See my 01-Nov-2011 post.
Hi Steve,
Thanks for your super cool blog. I have nothing to do with image processing (that’s what I used to think!) as its’ traditional meaning. I am trying to model the propagation of some burning material using a cellular automaton. The conventional approach was based on neighbouring propagation but the new idea is based on the heat transfer rate, which means the distance matters as well. I think the transform feature could be the key to a massive code simplifications!!!
Thanks again and I would be grateful if you let me know of any reading references for CA design in MATLAB.
Cheers,
Mehdi,UCD,Ireland
Mehdi—Other than using makelut and applylut to play around with Conway’s Game of Life, I am not very familiar with the methods and applications of cellular automata. See my 20-May-2008 post.