算法介绍

$$之前做过最大值最小值滤波基本上复杂度是非常高的，因为涉及到遍历w*h的滑动窗口中的所有值然后求出这个窗口所有值的最大和最小值。尽管可以使用sse优化，但速度仍然快不起来，最近在ImageShop博主的一篇博客中遇见了这篇论文，https://files-cdn.cnblogs.com/files/Imageshop/O(1)最大值最小值算法.pdf ，讲的就是O(1)实现最大最小值滤波，所以希望与大家一起分享这个算法。

算法原理

$$具体的想法和细节可以查看论文，注意到作者给出了算法的伪代码：

代码实现

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
deque <int> U, L;
int maxval[maxn], minval[maxn];

int main(){
    int a[10] = {0, 1, 9, 8, 2, 3, 7, 6, 4, 5};
    int w = 3;
    for(int i = 1; i < 10; i++){
        if(i >= w){
            maxval[i - w] = a[U.size() > 0 ? U.front() : i-1];
            minval[i - w] = a[L.size() > 0 ? L.front() : i-1];
        }
        if(a[i] > a[i-1]){
            L.push_back(i - 1);
            if(i == w + L.front()) L.pop_front();
            while(U.size() > 0){
                if(a[i] <= a[U.back()]){
                    if(i == w + U.front()) U.pop_front();
                    break;
                }
                U.pop_back();
            }
        }
        else{
            U.push_back(i-1);
            if(i == w + U.front()) U.pop_front();
            while(L.size() > 0){
                if(a[i] >= a[L.back()]){
                    if(i == w + L.front()) L.pop_front();
                    break;
                }
                L.pop_back();
            }
        }
    }
    maxval[10 - w] = a[U.size() > 0 ? U.front() : 9];
    minval[10 - w] = a[L.size() > 0 ? L.front() : 9];
    for(int i = 0; i <= 10 - w; i++){
        printf("Min index %d is: %d\n", i, minval[i]);
        printf("Max index %d is: %d\n", i, maxval[i]);
    }
    return 0;
}

得到的结果展示：

关于最大最小值滤波

$$ 上面的算法是对一个序列进行求长度为w的一维窗口的最大最小值，我们只需要把2维的Mat看成2个一维的序列，分别求一下然后综合一下2个维度的结果即可。我们最后可以发现整个最大最小值滤波的算法复杂度和滤波的半径没有任何关系，确实是一个很优雅的算法。