Implementation of image dilation and erosion

Question

I am trying to figure out an efficient way of implementing image dilation and erosion for binary images. As far as I understand it, the naive way would be:

• loop through the image
• if pixel is 1
• loop through the neighborhood based on the structuring element's height and width
• (dilate) substitute each pixel of the image with the value in the corresponding location of the SE
• (erode) check if all neighborhood is equal to the SE, if so keep all the pixels, else delete the centre

so this means that for each pixel I have to loop through the SE as well making this a O(NMW*H).

Is there a more elegant way of doing this?

Answer 1

Yes there are!!!

First you want to decompose (if possible) your structuring element into segments (a square being composed by a vertical and an horizontal segment). And then you perform only erosion/dilation on segments, which already decreases the complexity.

Now for the erosion/dilation parts, you have different solutions:

• If you work only on 8-bits images and do not C/C++, you use an implementation with histograms in order to keep track of the minimum/maximum value. See this remarkable work here. He even adds "landmarks" in order to reduce the number of operations.
• If you use C/C++ and work on different types of image encodings, then you can use fast comparisons (SSE2, SSE4 and auto-vectorization), as it is the case in the SMIL library. In this case, you compare row with row, instead of working pixel by pixel, using material accelerations. It seems to be the fastest library ever.
• A last way to do, slower but works for all types of encoding, is to use the Lemmonier algorithm. It is implemented by the fulguro library.

For structuring elements of type disk, there is nothing "fast", you have to use the basic algorithm. For hexagonal structuring elements, you can work row by row, but it cannot be parallelized.