algorithm - 2D 中的滑动窗口最小值/最大值

Question

假设我们给定了一个大小为 NxN 的像素的整数矩阵和一个整数 k - 窗口大小。我们需要使用滑动窗口找到矩阵中的所有局部最大值(或最小值)。这意味着如果一个像素与其周围窗口中的所有像素相比具有最小(最大值)值，则应将其标记为最小值(最大值)。
有一个众所周知的滑动窗口最小值算法，它可以在向量中找到局部最小值，而不是在矩阵中
http://home.tiac.net/~cri/2001/slidingmin.html

你知道可以解决这个问题的算法吗？

Answer 1

由于最小滤波器是可分离滤波器，因此可以通过计算每个维度的 1D 滑动窗口最小值来计算 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

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