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

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

Answer 2

这是上述方法的 c++ 实现。

class MaxQ {
public:
    queue<int>q;
    deque<int>dq;
    void push(int x)
    {
        q.push(x);
        while (!dq.empty() && x > dq.back())
        {
            dq.pop_back();
        }
        dq.push_back(x);

    }
    void pop()
    {
        if (q.front() == dq.front())
        {
            q.pop();
            dq.pop_front();
        }
        else q.pop();
    }
    int max()
    {
        return dq.front();
    }

};


vector<int> maxSliding_1d_Window(vector<int>& v, int k) {
    MaxQ q;
    int n = v.size();
    vector<int>ans;
    for (int i = 0; i < k; i++)
    {
        q.push(v[i]);
    }
    for (int i = k; i < n; i++)
    {
        ans.push_back(q.max());
        q.pop();
        q.push(v[i]);
    }
    ans.push_back(q.max());
    return ans;
}

vector < vector<int> > maxSliding_2d_Window( vector<vector<int>>v, int k)
{

    int n = v.size();
    int m = v[0].size();

    //caclulting sliding window horizontally
    vector<vector<int> > horizontal;
    for (int i = 0; i < v.size(); i++)
    {
        vector<int>part = maxSliding_1d_Window(v[i], k);
        horizontal.push_back(part);
    }

    vector< vector<int > >final(n - k + 1, vector<int>(m - k + 1, -3));
    int c = 0;

    //calculationg sliding window vertically
    for (int j = 0; j < horizontal[0].size() ; j++)
    {
        vector<int>v;
        for (int i = 0; i < horizontal.size(); i++)
        {
            v.push_back(horizontal[i][j]);
        }
        vector<int> tmp = maxSliding_1d_Window(v, k);

        // pushing the result in our resultant matrix
        for (int index = 0; index < n - k + 1; index++)
        {
            final[index][c] = tmp[index];
        }
        c++;


    }

    //return final matrix
    return final;

}