For my series on dilation algorithms, I've followed my unfortunate custom of dragging a series out way too long. :-)
So let's wrap it up with a mention of the last key algorithmic idea implemented in the Image Processing Toolbox morphology functions: grayscale dilation and erosion with horizontal and vertical structuring elements.
Normally, the time required to perform dilation and erosion is proportional to the number of elements in the domain of the structuring element. But there are specialized algorithms that achieve better performance for certain classes of structuring elements. In particular, imdilate and imerode use the algorithm described in M. van Herk, "A fast algorithm for local minimum and maximum filters on rectangular and octagonal kernels," Pattern Recognition Letters, 13:517-521, 1992. There's a helpful description of this algorithm in P. Soille, Morphological Image Analysis: Principles and Applications, 2nd ed., 2007, 89-90.
This algorithm can perform flat grayscale dilation using horizontal and vertical linear structuring elements in time independent of the length of the strel.
Let's test that. (You can get timeit.m from the MATLAB Central File Exchange.)
I = imread('rice.png'); lengths = 5:2:31; times = zeros(size(lengths)); for k = 1:numel(lengths) se = strel(ones(1, lengths(k))); times(k) = timeit(@() imdilate(I, se)); end plot(lengths, 1000*times) ylim([0 max(1000*times)]) xlabel('Linear structuring element length') ylabel('Dilation time (milliseconds)')
For rectangular structuring elements, this algorithm interacts especially nicely with structuring element decomposition. The functions imdilate and imerode automatically detect flat, rectangular structuring elements and decompose them into horizontal and vertical line structuring elements. Therefore, grayscale dilation and erosion with flat, rectangular structuring elements can also be performed in time independent of the structuring element size.
Here's a test for square structuring elements.
lengths = 5:2:31; times = zeros(size(lengths)); for k = 1:numel(lengths) se = strel(ones(lengths(k), lengths(k))); times(k) = timeit(@() imdilate(I, se)); end plot(lengths, 1000*times) ylim([0 max(1000*times)]) xlabel('Square structuring element width') ylabel('Dilation time (milliseconds)')
That's a nice result, especially since using rectangular structuring elements is fairly common.
To recap, the main dilation and erosion algorithm ideas exploited by Image Processing Toolbox morphology functions are:
- structuring element decomposition
- binary bit packing
- specialized algorithms for horizontal and linear strels
You can see all the posts in the series by clicking on the "Dilation algorithms" category link on the right side of the page.
OK, that's it - I'm signing off for 2008.
Happy New Year, everyone!
Get
the MATLAB code
Published with MATLAB® 7.7
Hi Steve,
My query relates to your recent series on dilation algorithms with the comment that while the dilation/erode functions provide benefits associated with packing, this does not appear to have been incorporated in their combination function, imopen.
I am currently processing archived weather charts to record system movements. This entails locating the coordinates of High pressure weather systems by identifying the designating H together with the associated X located at the centroid of the system. The test uses imopen first with three H templates then the adjacent X with eight templates, the combination being necessary due to spurious H’s and X’s generated by land outlines, fronts, lat. and long. grid etc. in the chart layout.
As if that is not enough, both the H and X symbols also vary slightly from map to map due to hand-written insertions (early charts), changes in fonts (in later charts), missing pixels, background chart layout confusion etc. My present programming has about a 70% success rate but the real crunch comes in processing time if I attempt to apply it to approaching 15,000 images available for the past 10 years.
Do you have any advice regarding image searches under these conditions, please.
Rufus—I don’t understand your comment about imopen. If you look in the M-file, you’ll see that it does indeed do packing for 2-D binary images. I’m afraid I don’t have any other suggestions for your weather-chart analysis problem.
I want to automate the values used for structuring element.
I am using a structuring element of square. I am using it in motion detection.
My values should be automated based on the distance between the cameraand the object. How can i do it.Please post help to my mail.
Thank You..
Sunil—Sounds like you face some sort of camera calibration problem in order to determine the distance. Try search for “camera calibration MATLAB”.
Hi Steve
Could I please request a blog entry on 3D image (volume) dilation, perhaps as the first steps to a 3D flood filling algorithm? I’ve noticed a number of forum postings asking about 3D dilation and each time you mention that many of the image processing toolbox morphological functions support nD-images. My Matlab skills appear to be lacking as I am unable to puzzle through the strel and imdilate help files to achieve even a simple binary 3D dilation :(
Paul—Maybe you’re overanalyzing things? If you pass a 3-D input image to imdilate, it does 3-D dilation. For example:
performs 3-D dilation with a 3-by-3-by-3 structuring element.
The situation is similar for flood filling. If you want to do 3-D flood filling, just pass a 3-D image to imfill.
Thanks Steve! I was indeed overanalyzing things; you’ve saved my bacon. Hail to you champion!
Hi Steve,
I use hit-and-miss transform for corner detection. It require a lot of computing time. I want to speed it up by bit packing. How can I do it.
initial code:
final code:
Can I execute AND, OR operation without bwunpack and time missing?
Thank You.
Sergey—Try using bitand and bitor instead of & and |.
when i am using imerode function in .m file it give error as under
?? Error using ==> erode at 12
ERODE has been removed. Use IMERODE instead.
Nazish—The error message suggests that you were trying to use the function erode, which was removed from the toolbox years ago. Try using imerode instead.