2D 中的滑动窗口最小值/最大值 [英] Sliding window minimum/maximum in 2D

问题描述

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

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?

推荐答案

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

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:

假设这是开头的矩阵

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

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

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.

这篇关于2D 中的滑动窗口最小值/最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！