2D窗口的最小/最大滑动窗口

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

你知道一个算法可以解决这个问题吗?

0
额外
意见: 1

1 答案

由于最小滤波器是可分离滤波器,因此可以通过计算每个维度的一维滑动窗口最小值来计算2D滑动窗口最小值。对于4x4矩阵和2x2窗口,算法的工作原理如下:

假设这是开始时的矩阵

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

首先,分别计算矩阵每一行的一维滑动窗口最小值

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

然后,计算先前结果每列的一维滑动窗口最小值。

1 2 1
1 4 2
2 2 2

结果与直接计算2D窗口的滑动窗口最小值相同。这样,您可以使用一维滑动窗口最小算法来解决任何nD滑动窗口的最小问题。

0
额外
值得添加这个适用于任意窗口大小。
额外 作者 Samizdis,