3

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?

FiReTiTi
  • 5,597
  • 12
  • 30
  • 58
tigeradol
  • 259
  • 2
  • 16
  • If your image has large background, one thought I have is to start with non-overlapping neighbourhoods since dilating only occurs in the presence of a `0` pixel, and then move to overlapping neighbourhoods only if `0` pixels are detected in a neighbourhood. As it is, erode/dilate filters are much quicker than most other image processing filters because they don't require any math (like blurring does, for example). – eigenchris Dec 03 '14 at 19:48
  • That can do. I have also read about shifting and using logical operations but I have never actually found anything detailed. What I understand is that the dilation can be done by copying and moving the image in directions based on the SE and performing AND with all the images – tigeradol Dec 04 '14 at 13:05
  • I just noticed a similar question here: http://stackoverflow.com/questions/21854594/efficiently-implementing-erode-dilate . One simple approach is to perform a 1D vertical dilation followed by a 1D horizontal dilation, but one answer describes an even more efficient solution. – eigenchris Dec 04 '14 at 15:11

1 Answers1

0

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.

FiReTiTi
  • 5,597
  • 12
  • 30
  • 58