Sliding window minimum/maximum in 2D

Question

Suppose we are given an integer matrix of pixels of size NxN and an integer k - window size. We need to find all local maximums (or minimums) in the matrix using the sliding window. It means that if a pixel has a minimum (maximum) value compared to all pixels in a window around it then it should be marked as minimum (maximum). There is a well-known sliding window minimum algorithm which finds local minimums in a vector, but not in a matrix http://home.tiac.net/~cri/2001/slidingmin.html

Do you know an algorithm which can solve this problem?

Answer 1

Since the minimum filter is a separable filter, you can calculate the 2D sliding window minimum by calculating the 1D sliding window minimum for each dimension. For a 4x4 matrix and a 2x2 window, the algorithms works as follows:

Assume this is the matrix at the beginning

3 4 2 1
1 5 4 6
3 6 7 2
3 2 5 4

First, you calculate the 1D sliding window minimum for each row of the matrix separately

3 2 1
1 4 4
3 6 2
2 2 4

Then, you calculate the 1D sliding window minimum of each column of the previous result.

1 2 1
1 4 2
2 2 2

The result is the same as if you calculate the sliding window minimum of a 2D window directly. This way, you can use the 1D sliding window minimum algorithm to solve any nD sliding window minimum problem.