【AI PC端演算法優化】五，常量階最大值最小值濾波演算法
論文獲取請在公眾號後台回復：MaxMin
1. 前言
最近有點忙，今天水一下。來為大家介紹一個之前看到的一個有趣的常量階最大值最小值濾波演算法，這個演算法可以在對每個元素的比較次數不超過 3 次的條件下獲得任意半徑區域內的最大值或者最小值，也即是說可以讓最大最小值濾波演算法的複雜度和半徑無關。
2. 演算法介紹
普通實現的最大最小值濾波複雜度是非常高的，因為涉及到遍歷r\times r的滑動窗口中的所有值然後求出這個窗口所有值的最大和最小值。儘管可以使用 sse 優化，但速度仍然快不了多少（後面會介紹這個演算法的 SSE 優化）。然後偶然看到了這篇論文，題目為：STREAMING MAXIMUM-MINIMUM FILTER USING NO MORE THAN THREE COMPARISONS PER ELEMENT。它介紹了一個最大最小值濾波的優化方法，使得這兩個濾波器演算法的複雜度可以和濾波半徑r無關。
3. 演算法原理
演算法的核心原理如下圖所示：
其實演算法也是比較好理解的，即動態維護一個長度為r（濾波窗口大小）的單調隊列，然後可以在任意位置獲取以當前點為結束點的濾波窗口中的最大值或者最小值。
4. 程式碼實現
#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;
}
5. 演算法結果
得到的結果如下入所示：
6. 總結
上面的演算法是對一個序列進行求長度為w的一維窗口的最大最小值，我們只需要把2維的 Mat 看成兩個一維的序列，分別求一下然後綜合一下兩個維度的結果即可。我們最後可以發現整個最大最小值濾波的演算法複雜度和濾波的半徑沒有任何關係，這確實是一個很優雅高效的演算法。
歡迎關注 GiantPandaCV, 在這裡你將看到獨家的深度學習分享，堅持原創，每天分享我們學習到的新鮮知識。( • ̀ ω•́ )✧
有對文章相關的問題，或者想要加入交流群，歡迎添加 BBuf 微信：
