Side Window Filtering 論文解讀和C++實現(xiàn)

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

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

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

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

• side window 盒子濾波C++復(fù)現(xiàn)代碼：
• side window 中值濾波C++復(fù)現(xiàn)代碼

我們來看下復(fù)現(xiàn)論文的效果，對于一張普通圖片，經(jīng)典的盒子濾波和side-window 盒子濾波的效果對比：

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

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

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

下面從我的理解上去簡單解讀下這篇論文的核心思想，還有我在復(fù)現(xiàn)過程中的一些實現(xiàn)細(xì)節(jié)介紹。

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

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

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

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

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

“泰勒公式是將一個在 x=x0 處具有n階導(dǎo)數(shù)的函數(shù) f(x) 利用關(guān)于 (x - x0) 的n次多項式來逼近函數(shù)的方法?！?---百度百科

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

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)(- ε)

同理，設(shè) 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)ε

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

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

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

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

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

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

梁德澎：移動端arm cpu優(yōu)化學(xué)習(xí)筆記----一步步優(yōu)化盒子濾波（Box Filter）

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

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

最后看看幾組對比結(jié)果，看看在迭代10次的情況下，經(jīng)典box filter 和 side window box filter的結(jié)果對比：

熊貓寶寶原圖

濾波結(jié)果, box filter, iteration = 10

濾波結(jié)果, side window box filter, iteration = 10

熊貓寶寶原圖+椒鹽噪聲

去噪結(jié)果, box filter, iteration = 10

去噪結(jié)果, side window box filter, iteration = 10

然后在迭代10次的情況下，經(jīng)典中值 filter 和 side window 中值濾波的結(jié)果對比：

殲20+椒鹽噪聲

去噪結(jié)果, median filter, iteration = 10

去噪結(jié)果, side window median filter, iteration = 10

相關(guān)資料：

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

推薦文章

• 移動端arm cpu優(yōu)化學(xué)習(xí)筆記（一）——一步步優(yōu)化盒子濾波（Box Filter）
• 移動端arm cpu優(yōu)化學(xué)習(xí)筆記第2彈--常量階時間復(fù)雜度中值濾波

更多AI移動端優(yōu)化的請關(guān)注專欄嵌入式AI以及知乎（@梁德澎）。

審核編輯：符乾江