本文復現的是CVPR2019 Oral論文Side Window Filtering。
作者：梁德澎
首發知乎：https://zhuanlan.zhihu.com/p/79254846

論文：Side Window Filtering（文末可以直接下載）
鏈接：https://arxiv.org/pdf/1905.07177.pdf

剛開始看到這篇論文的時候，我就很感興趣想去復現一把看看效果。這篇論文是 CVPR2019 oral 且不是深度學習方向的，其核心貢獻點就是：不管原來的濾波器保不保邊，運用了side-window思想之后，都可以讓它變成保邊濾波！

于是利用業余時間，參考作者開源的matlab代碼，我用C++實現了一下Side-window 盒子濾波，其他濾波器有時間再試下，下面是github的鏈接，讀者可以去跑下代碼看看效果玩下，從實驗結果上看我覺得算是復現了論文的效果：

• side window 盒子濾波C++復現代碼：
• side window 中值濾波C++復現代碼

我們來看下復現論文的效果，對于一張普通圖片，經典的盒子濾波和side-window 盒子濾波的效果對比：

從濾波結果對比上可以看到，經典的盒子濾波隨著對同一張圖片反復應用盒子濾波的迭代次數的增加，視覺效果是越來越模糊，到了30次迭代的時候已經糊的沒法看了，但是Side-window盒子濾波即使迭代了30次，對于邊緣的保持還很好，和原圖基本看不出大的區別，就是邊緣細節有些丟失。

然后對原圖加上椒鹽噪聲，再對比下濾波效果：

從濾波結果對比上可以看到，經典的盒子濾波到了10次迭代的時候，雖然椒鹽噪聲已經很好的消除了，但是圖片也變得很模糊，邊緣都細節都丟失了，但是Side-window盒子濾波卻能很好的消除椒鹽噪聲的同時，對于邊緣的保持還很好，基本上算是還原了原圖。

下面從我的理解上去簡單解讀下這篇論文的核心思想，還有我在復現過程中的一些實現細節介紹。

目前的經典濾波算法基本都是，以某個像素點為中心，按照濾波半徑，把這個包括像素點和其鄰域加權線性組合得到輸出，一般公式如下：

Ω是以像素點 i 為中心的濾波窗口，w是濾波權值，q是原圖像素值，I'是輸出結果。但是這樣以一個像素為中心去濾波會導致的問題是，如果一個像素點處在邊緣位置（這里的邊緣不是指圖片的大小邊界，而是指圖像中物體的邊緣）的話，以像素為中心去濾波會導致濾波結果的邊緣部分變模糊。具體是為什么，論文中給出了分析過程。

首先來看下，論文中的一張圖：

文中提到為了分析方便只討論3種典型的邊緣，分別是圖中的 (a)階梯狀邊緣、(b)斜坡狀邊緣和(c)屋頂狀邊緣。論文中也給出了這3三種邊緣的形象展示：

然后文中采用了泰勒展開去分析，首先假定，圖像上(x, y)坐標點的像素值為g(x, y)，對于圖中展示的情況來看，函數 g(x, y)是連續但不可導的。對于(a)階梯狀邊緣的 'a' (藍色方框那個點)點來說，文中定義 'a-' 和 'a+' 來分別表示 'a' 點左極限 (x - ε, y)，和右極限 (x + ε, y)，且 ε > 0。 很明顯從圖中可以看出來 g(x - ε, y) ≠ g(x + ε, y) 且/或（文中的用詞是"and (or)"）g'(x - ε, y) ≠ g'(x + ε, y)，導數也不等是由于邊緣部分的跳躍。因此對于這兩塊區域的泰勒展開也是不一樣的，首先來看下泰勒展開的一般公式：

“泰勒公式是將一個在 x=x0 處具有n階導數的函數 f(x) 利用關于 (x - x0) 的n次多項式來逼近函數的方法。”----百度百科

根據文中的分析，這里設定 f(x) = g(x - 2ε, y)，x0 = x - ε，則根據泰勒展開公式：

g(x - 2ε, y) ≈ f(x0) + f'(x0)(x - x0)
= g(x - ε, y) + g'(x - ε, y)(x - 2ε - (x - ε))
= g(x - ε, y) + g'(x - ε, y)(- ε)

同理，設 f(x) = g(x + 2ε, y)，x0 = x + ε，則泰勒展開得：

g(x + 2ε, y) ≈ f(x0) + f'(x0)(x - x0)
= g(x + ε, y) + g'(x + ε, y)(x + 2ε - (x + ε))
= g(x + ε, y) + g'(x + ε, y)ε

所以從兩邊的泰勒展開式可以得出結論，對于 'a-' 區域的濾波估計肯定是來自區域 'a' 的左邊，而對于 'a+' 估計是來自于 'a' 的右邊，然后類比分析區域 'b'，'c' 和 'd' 都可以得到類似的結論。

因此分析得到的結論是，如果一個像素點處于圖像中的邊緣位置，那么濾波的時候就應該把濾波器的邊緣和該像素點對齊，而不是把濾波器的中心和該像素點對齊。受該發現的啟發，文中提出了一個新的保邊濾波策略，就是把每個濾波像素點都當成是潛在的邊緣點，然后對于每個待濾波的像素點，生成幾種不同的濾波子窗口，然后把這些濾波窗口的邊緣或者角點位置和該像素點對齊，然后濾波得到結果，最后根據把這些子窗口的濾波之后的最佳重構結果作為最終的濾波結果。以上就是side window 濾波的思想。

然后文中提出了8個方向的濾波窗口，分別是上、下，左、右、左上、右上、左下和右下，最后就得到了 side window filter 的核心算法流程：

其實從核心算法邏輯來看，對原來濾波算法的改動其實不大，就是濾波的窗口位置和大小需要改動下，然后把8次的結果每個位置取重構誤差最小的。然后論文中又詳細分析了 box filter 和 side window box filter 對于上面提到的三種經典邊緣的濾波之后的保留情況。文中給出分析的圖表如下：

總的來說結論就是 side window box filter 對于階梯和斜坡狀的邊緣都能完整的保留，而對于屋頂狀邊緣雖然不能完整的保留邊緣，但是也比經典的盒子濾波要好很多。

在復現過程中，本來一開始是想對文中提到的8種side window去分別寫對應的盒子濾波的，因為盒子濾波有個經典的優化思路，可以讓運行時間不受濾波半徑的影響，具體可以參考我之前寫得一篇博客：

梁德澎：移動端arm cpu優化學習筆記----一步步優化盒子濾波（Box Filter）

后來仔細想了下，這8個side window其實也就是邊界處理不同，核心運算邏輯都是一致的，最后就是抽象成一個函數，對于不同的side window傳不同的邊界參數，就不需要每個窗口寫一個函數了，具體可以看看github上的代碼。

然后在實現side window中值濾波的時候針對移動端想了一個加速方案，因為求中值需要對窗口內元素排序，這里直觀上感覺是沒什么辦法加速的，不過我嘗試了一個方案，利用neon指令相對原來提速了不少，有空的話可以寫一篇小博客去解釋，這里先埋一個彩蛋。

最后看看幾組對比結果，看看在迭代10次的情況下，經典box filter 和 side window box filter的結果對比：

熊貓寶寶原圖

濾波結果, box filter, iteration = 10

濾波結果, side window box filter, iteration = 10

熊貓寶寶原圖+椒鹽噪聲

去噪結果, box filter, iteration = 10

去噪結果, side window box filter, iteration = 10

然后在迭代10次的情況下，經典中值 filter 和 side window 中值濾波的結果對比：

殲20+椒鹽噪聲

去噪結果, median filter, iteration = 10

去噪結果, side window median filter, iteration = 10

相關資料：

• AI雞蛋：CVPR2019 Oral論文 #5176 Side Window Filtering介紹
• AI雞蛋：Sub-window Box Filter論文介紹

推薦文章

• 移動端arm cpu優化學習筆記（一）——一步步優化盒子濾波（Box Filter）
• 移動端arm cpu優化學習筆記第2彈--常量階時間復雜度中值濾波

更多AI移動端優化的請關注專欄嵌入式AI以及知乎（@梁德澎）。

審核編輯：符乾江