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.