CODEWITHSUNDEEP
algorithmminimumsliding-window
Andrei Baskakov
Andrei Baskakov

Reputation: 161

Sliding window minimum/maximum in 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

Do you know an algorithm which can solve this problem?

Upvotes: 7

Views: 6873

Answers (2)

Visluck
Visluck

Reputation: 47

This the c++ implementation of above approach .

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;

}

Upvotes: 1

Tom
Tom

Reputation: 518

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.

Upvotes: 20

Related Questions