O(1)最大值最小值的均值滤波算法

BBuf

发布于 2019-12-04 18:05:24

1.9K0

发布于 2019-12-04 18:05:24

算法介绍

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

算法原理

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

在这里插入图片描述

代码实现

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

int main(){
    int a[] = {, , , , , , , , , };
    int w = ;
    for(int i = ; i < ; i++){
        if(i >= w){
            maxval[i - w] = a[U.size() >  ? U.front() : i-1];
            minval[i - w] = a[L.size() >  ? L.front() : i-1];
        }
        if(a[i] > a[i-1]){
            L.push_back(i - );
            if(i == w + L.front()) L.pop_front();
            while(U.size() > ){
                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() > ){
                if(a[i] >= a[L.back()]){
                    if(i == w + L.front()) L.pop_front();
                    break;
                }
                L.pop_back();
            }
        }
    }
    maxval[ - w] = a[U.size() >  ? U.front() : ];
    minval[ - w] = a[L.size() >  ? L.front() : ];
    for(int i = ; i <=  - w; i++){
        printf("Min index %d is: %d\n", i, minval[i]);
        printf("Max index %d is: %d\n", i, maxval[i]);
    }
    return ;
}

得到的结果展示：

在这里插入图片描述

关于最大最小值滤波

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

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-11-07，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 GiantPandaCV 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度