I want to perform the following operation on an image: consider a square window around every pixel, find the maximum value in this window, and replace the central pixel value with this maximum value. If I consider a $n \times n$ square window around every pixel, this becomes the morphological dilation operation (with a square $n \times n$ structuring element).

In my work I need to have windows of different sizes around every pixel, i.e. I might need a $n \times n$ window around pixel $A$ and a $m \times m$ window around pixel $B$.


(1) Does this operation have a name? Is it widely used?

(2) Do you know of any fast algorithm to perform this operation?

Relevant info: For fixed window sizes, there does exist a fast algorithm, for example Algorithm 1 in the following paper (which in fact requires just a constant number of operations per pixel, regardless of window size):

Chaudhury, K. N. "Acceleration of the Shiftable O(1) Algorithm for Bilateral Filtering and Nonlocal Means." IEEE Transactions on image processing, 22.4 (2013): 1291-1300.

  • $\begingroup$ How large is this data task that existing methods seem slow (?). Can you provide an indication of image size and range of window sizes please? $\endgroup$ – A_A Oct 3 '18 at 12:41
  • $\begingroup$ @A_A The Image size is typically 2 megapixels. The window sizes can vary from $11 \times 11$ to, say $101 \times 101$. $\endgroup$ – EpsilonDelta Oct 4 '18 at 6:57
  • $\begingroup$ Search for adaptive morphological filter. This is a good review paper: doi.org/10.1016/j.patrec.2014.02.022 $\endgroup$ – Cris Luengo Dec 9 '18 at 19:13

The trick when using masks is that if the window is shifted one to the left, only one row is added and one removed. Therefore one can e.g. calculate the mean of a 5x5 window quicker, as if all 25 values needed to be added and divided again.

In erosion or dilation this fact could be used to, if one would store the max of each row. Then only the maxes of one new row would be needed and a comparison between all rows. However I guess nobody does that, since the overhead is quite big and big windows would need additional space for each row's max...

Your problem however couldn't even use this, since the window size is changing. I assume the changes are random. Therefore there will be no quicker way than moving from pixel to pixel and apply the different window sizes.

But why would someone use different windows for different pixels?


It is easy to do it in MATLAB (https://www.mathworks.com/help/images/sliding-neighborhood-operations.html)

f = @(x) sqrt(min(x(:)));
I2 = nlfilter(I,[3 3],f);

Your Answer

