快速雙邊濾波器

1、空間領(lǐng)域通過二次采樣的低存儲、簡單、快速雙邊濾波器摘要：文章提出一個算法，來加速基于二次采樣的策略的彩色雙邊濾波器，工作在空間領(lǐng)域。基本思路是使用一個合適樣本子集來獲得一個準確濾波器的好的估計，方法的優(yōu)點是在視覺質(zhì)量和加速之間有一個很好的權(quán)衡，需要一個小的內(nèi)存開銷和非常簡單的在GPU上實現(xiàn)實時濾波，論文展示了濾波器的不同應(yīng)用，特別是高效的交叉濾波器，實時識別邊的圖像編輯和快速視頻去噪，我們從時間性能，內(nèi)存使用，圖像質(zhì)量和前沿方法比較。介紹：領(lǐng)域處理包括：1. 定義中心點（x，y）2. 僅對定義的以（x，y）為中心的領(lǐng)域進行運算，3. 運算結(jié)果為該點處處理的響應(yīng)，4 . 對圖像上的每一點做相同的

2、操作。移動中心會產(chǎn)生新的領(lǐng)域，每個領(lǐng)域?qū)?yīng)與輸入圖像上的一個像素。線性濾波的概念源于頻域中信號處理所使用的傅利葉變換。線性運算包括將領(lǐng)域中的每一個像素與相應(yīng)的系數(shù)相乘，然后將結(jié)果進行累加，從而得到（x，y）處的響應(yīng)，若領(lǐng)域的大小是m*n，則總共需要mn個系數(shù)。這些系數(shù)排列成矩陣，我們稱為濾波器、掩模、濾波掩模、核、模板或者窗口。為簡便起見，我們通常稱為卷積濾波、掩?；蚝说刃g(shù)語。非線性空間濾波也是基于領(lǐng)域操作，和線性濾波不一樣，它是基于非線性操作，令每一點處的響應(yīng)等于其領(lǐng)域的最大像素值的操作就是非線性濾波。非線性濾波器廣泛使用在計算機圖論、圖像和視覺，用作不同的應(yīng)用，特別指出，雙邊濾波器是一個非

3、常流行的非線性濾波器，由Tomansi和Manduchi兩人提出的，因為過濾圖像的區(qū)域同時保持完整的邊。而且它簡單的公式和靈活性使得它應(yīng)用在不同的問題上，例如：消除圖像噪音、圖像視頻格式化、高動態(tài)范圍色調(diào)映射、頻閃攝影術(shù)、邊清晰的二次采樣等等，根據(jù)Tomansi和Manduchi公式，雙邊濾波器定義如下： I 表示一個k維圖像，表示像素xi的一個集合，fr和gs分別表示范圍衰減函數(shù)和空間衰減函數(shù)，這些函數(shù)都是權(quán)值函數(shù)，典型的高斯函數(shù)，Adams 提出了公式1的一個簡潔形式：p是多維像素，例如pi=ri,gi,bi,xi,yiT , (ri , gi , bi )T是RGB顏色，（xi，yi）是

4、像素的空間坐標位置，pi乘以高斯函數(shù)的一個標準方差（r , g , b , x , y )T，方程2認為權(quán)值函數(shù)是高斯函數(shù)，在我們的方法中，我們沒有作出太多的假設(shè)，保持了原有的公式，方程1的計算復雜度非常高，圖像的每一個像素的時間復雜度是O(N k），這些年，在算法的改進方面激發(fā)了大量的研究工作，來加快計算速度。一些改進的技術(shù)也可以用來加速高維的非線性的濾波器，例如non-local means，是目前比較流行的去噪算法，被廣泛應(yīng)用于高分辨率圖像顯示。圖1 ：取左邊圖像中的一個子集樣本samples，通過加權(quán)值weight累加得到最終的值reault。這篇論文的主要貢獻就是實現(xiàn)雙邊濾波器的加速

5、技術(shù)，很容易在一個計算性能高、內(nèi)存小，不許要預處理的Gpu上執(zhí)行。對于彩色雙邊濾波提供一個高質(zhì)量結(jié)果，我們技術(shù)的主要思路是提供一個二次采樣策略加速方程1的計算。換句話說，為了提供準確濾波器值的估計，濾波器核是通過空間域的一個子集來計算。每一個像素采取不同的采樣模式，避免已經(jīng)過濾過的圖像產(chǎn)生結(jié)構(gòu)噪音。這種方法不能加速高維的濾波，不管怎樣，它能夠在GPU和CPU上執(zhí)行，能夠提供高質(zhì)量結(jié)果。盡管如上提到的局限性，但是這方法能夠用在交叉雙邊濾波器，而且很容易推廣在視頻處理中，算法的時間復雜度是O(mN k），N是核的半徑，k是圖像維數(shù)，m是圖像像素的總數(shù)，這改善了方程1的蠻力計算，其時間復雜度O(mN

6、 k），而且我們的方法不需要預處理特征，空間復雜度O（1）。2 相關(guān)工作最近提研發(fā)了幾種方法加速不同類型的雙邊濾波器，例如灰度級濾波器、彩色濾波器或者交叉雙邊濾波器。這些方法也能夠有效計算高維非線性濾波器，例如non-local means。這兒討論最先進的方法。一個最簡單的加速計算雙邊濾波器的方法，如果是圖像，則把濾波器分離成兩個一維濾波器，如果是視頻，則把濾波器分離成3個濾波器。這樣就可以把每個像素的時間復雜度從O（NK）降到O（NK），這是一個粗略的雙邊濾波器的近視值，但是它在視頻去噪方面能夠得到好的結(jié)果，技術(shù)的主要有點如下：對于中大內(nèi)核半徑（over 20 pixes）方法產(chǎn)生錯誤的結(jié)

7、果，而且空間復雜度從O（1）增加到O（m），因為圖像必須存儲第二次來估計濾波器 Paris和Durand提出一個新穎的方法計算雙邊濾波器，通過把它作為一個高維的卷積，在一個spatio-tonal空間，方法的第一步是splating （拋雪球算法）把數(shù)據(jù)轉(zhuǎn)換到高維空間(spatio-tonal)，這個時候數(shù)據(jù)通過標準卷積變得模糊，數(shù)據(jù)能夠高效計算，最后，濾波過的值通過空間插值被轉(zhuǎn)換到原來的域，算法的最后階段叫做splicing，Chen 提出了雙邊網(wǎng)格，一個GPU友好的數(shù)據(jù)結(jié)構(gòu)，方法的實現(xiàn)充分利用現(xiàn)在圖像硬件的并行性。這種方法能夠處理高階濾波器，但是需要消耗很大的內(nèi)存，而且，雙邊網(wǎng)格不是轉(zhuǎn)化不

8、變的，例如，濾波的結(jié)果依賴網(wǎng)格的階段，高斯KDTREE像雙邊網(wǎng)格一樣，但是使用了不同的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)splating、bluring和splicing。這種技術(shù)能夠有效的加速高維濾波器，前提是低的內(nèi)存消耗。最新的一個加速技術(shù)是Adams提出，方法的數(shù)據(jù)結(jié)構(gòu)有雙邊網(wǎng)格和高斯KD樹一樣的性能，它比高斯KD樹要稀疏，同時比雙邊網(wǎng)格消耗更低內(nèi)存，所以這種技術(shù)能夠有效計算高維濾波器。另一個不同的方法，加速雙邊濾波減少多余操作利用窗口的有序重疊，非常有名的例如中值濾波。Ben Weiss從中值濾波器基于直方圖的加速算法中獲得靈感，開發(fā)了對于中值濾波器的快速算法（每個像素的時間復雜度是O（logN），Ben

9、 Weiss使用同樣的方法加速雙邊濾波器，假設(shè)空加函數(shù)平均在一個正方形核中。Porikli使用直方圖開發(fā)灰度級雙邊濾波器的快速算法（每一次圖像的一個通道被處理），算法的時間復雜度O(1)，通過重新定義雙邊濾波器計算公式，fx（s）= c是線性濾波器的一個準確和，這個和可以通過積分直方圖在常時間內(nèi)計算不依賴核的大小，Porikli通過泰勒展開式把公式拓展到任意空間濾波器，這種情況，得到的結(jié)果非常接近真實的雙邊濾波器。Yang改進了這種方法（Porikli），量化放到一個范圍函數(shù)而不是圖像強度，獲得一系列線性濾波器，濾波過的圖像通過濾波器輸出的線性空間插入獲得，Yu優(yōu)化了yang的方法，引入一種權(quán)

10、衡優(yōu)化標準。Gunturk 改進了porikli的方法，采用盒子核，使用盒子核的加權(quán)和近似任意域核。而且Igarashi提出在一個算法中使用多層直方圖來減少這種濾波器的內(nèi)存需求，所有的這些基于直方圖的方法都適用于8位圖，而不適用于HDR圖像。evaluateYoshizawa提出一個基于快速高斯轉(zhuǎn)換（FGT）的加速算法。FGT是高斯加權(quán)和快速、錯誤控制計算的一種技術(shù)。主要想法是在一個高維域把雙邊濾波器作為一個高斯加權(quán)和處理。使用FGT計算結(jié)果的和。該算法有線性的時間復雜度。Fattal提出了一個加速策略，該方法重復使用j規(guī)模級來計算j+1級濾波器。我們的算法不同于以上提到的方法，因為它整個基于

11、二次采樣，直接執(zhí)行在空間域。使用二次采樣來加速處理的想法并不是最新的，從計算射線軌跡的呈現(xiàn)方程(使用不同采樣策略)到一個基于霍爾頓采樣的二次采樣策略被用來加速計算兩個圖像的相似信息，而且雙邊網(wǎng)格在它的構(gòu)造期間采用縮減采樣，高斯KD樹在節(jié)點構(gòu)造期間采用夢特卡羅采樣。此外，chen提出了一個應(yīng)用在spatial-tonal域的對視頻的泊松磁盤二次采樣優(yōu)化，不管咋樣，我們的二次采樣策略執(zhí)行在空間域（圖像在同樣的域下定義），不許要把樣本映射到其它域，這就容許在CPU和圖形硬件上簡單實現(xiàn)，盡管方法簡單，但是能夠提供圖像視頻的高質(zhì)量結(jié)果，正如敘述的，它只適用于一定階的濾波器，而不適用于高階濾波器，例如：雙

12、邊網(wǎng)格，高斯KD樹，F(xiàn)GT。無論如何，對于圖像的動態(tài)范圍、空間和范圍函數(shù)我們不做任何假設(shè)。3. 算法我們算法的主要思路是計算方程1（k維圖像NK核窗口的的一個子集），算法1 展示完整雙邊濾波器的偽代碼實現(xiàn)，算法2快速雙邊濾波器偽代碼。Brute force 算法要計算集的所有像素，我們的方法很簡單，只需要通過一個均勻分布的子集來計算方程1。算法的主要部分是getsample()函數(shù)，它返回樣本的坐標， 為了取得雙邊濾波器確切值的一個近似值，getsample（）必須小心取樣，對于getsample（），我們測試了不同的采樣策略，例如：規(guī)則采樣（RPS）， 夢特卡羅采樣（MCS），分層的夢特卡羅

13、采樣（SMS），泊松磁盤采樣（PDS），在我們測試中，我們使用Bridson算法產(chǎn)生泊松磁盤分布的樣本。為了避免結(jié)構(gòu)噪音和改善隨機性，不同部分的子集提前計算，至于PDS，就隨機性而言，64塊足夠獲得好的結(jié)果，模式集的存儲在內(nèi)存需要小的開銷，例如255*255的核需要64kb的內(nèi)存，與圖像原始大小無關(guān)，而且這些采樣模式的計算非?？?。Figure 3展示不同采樣策略的視覺對比，RPS產(chǎn)生結(jié)構(gòu)噪音，所以需要隨機性的刪除這些artefacts，無論如何，MCS也導致噪音，SMS也產(chǎn)生噪音，基于這些問題，我們選擇泊松磁盤分布來得到樣本，雖然有噪音，但這些噪音在人類視覺系統(tǒng)面前被模糊了。從理論觀點看，我們

14、可以通過使用最大泊松磁盤采樣程序使采樣處理變得沒有偏差。為了確保相符和的估計量保持無偏差，我們可以使用克蘭利帕特森旋轉(zhuǎn)(Cranley-Patterson rotaion)隨機移動集合， 使用移動策略點集的存儲就會降低，例如256*256核需要1kb內(nèi)存，我們方法的錯誤約束與圖像的變化有關(guān)，在平滑區(qū)域錯誤期待降到最低，錯誤增加依賴與區(qū)域的變化(中心、邊)，因為對于整個區(qū)域(N2)只有一些樣本(KN)被提取。提出的方法也可以處理視頻，2維圖像和視頻僅有的不同是泊松磁盤采樣分別在2維和3維中計算，它不能像其它方法一樣擴展到K維，因為不能保證泊松磁盤采樣很好的工作于任意維。由于方法的簡單性，我們直接

15、在OPENGL框架上使用GLSL著色器實現(xiàn)算法，即使在低檔的圖形硬件也能高效的實現(xiàn)。3.1 需要的樣本數(shù)的分析使用高斯函數(shù)作為衰減函數(shù)，gs with variance s , fr with variance r，我們通過不同的采樣密度測試我們采樣近視值的精確性，對于一個N*N像素的核，KN個樣本被使用(K=1、27)，6個HDR圖像隨著r or s變化，從Figure4中可以看到，一個N*N大小的核使用N或2N的樣本就質(zhì)量而言是合理的，N=3N，需要增加計算時間，3N和4N樣本之間的差異是1dB。在figure 4中，對于 固定的mPSNR值，需要的樣本減少，這種減少遵循矩形雙曲線的形狀隨

16、著坐標軸平行于他們的漸進線，從這些圖的濾波數(shù)據(jù)到雙曲線，可以推出:small kenerl （s<20pixes）需要2.5N樣本，medium kenerls （20<s<40）需要0.75N到2.5樣本，large kenerls （s>40）需要0. 75N樣本。4 應(yīng)用為了展示方法的有效性，我們現(xiàn)在可以把算法應(yīng)用在計算機圖像圖像處理中，包括圖像和視頻濾波，迭代濾波，交叉或者節(jié)點雙邊濾波，色調(diào)映射。4.1 視頻去噪： 雙邊濾波器的一個典型的應(yīng)用是圖像視頻去噪，因為濾波器刪除了高斯噪音同時保持了完整的邊，figure 5 是視頻去噪的一個應(yīng)用。我們的方法非常應(yīng)用于視

17、頻去噪，因為它需要的內(nèi)存比較小，對于高清視頻可以實現(xiàn)實時的幀速率。4.2 抽象我們的雙邊濾波器適合迭代濾波，因為它收斂與非常相近的參考結(jié)果，由于一個事實，每一次迭代，每個像素在空間位置中改變，迭代雙邊濾波器非常適用于圖像視頻抽象。4.3 閃光 非閃光攝影iso 高感光度和高速快門 2 使用閃光燈3 通過標準交叉雙邊濾波器使用閃光 非閃光攝影去噪 4 采用我們的算法4.4 邊識別圖像編輯雙邊濾波器可以用作邊識別圖像編輯。在一個選中區(qū)域圖像的參數(shù)被修改，通過畫刷描邊避免修改相領(lǐng)的區(qū)域，區(qū)域被邊分割開來。濾波器的輸出是邊識別畫刷，可以用來修改圖像的參數(shù)(色度、飽和度、亮度)。如Figure 8：4.

18、5 色調(diào)映射另一個應(yīng)用是HDR圖像的色調(diào)映射。使用雙邊濾波器把HDR圖像分割成基礎(chǔ)和細節(jié)圖像?；A(chǔ)分層是使用Reinhard的全局色調(diào)函數(shù)。最后，基礎(chǔ)色調(diào)映射和細節(jié)被結(jié)合來獲得最后的色調(diào)映射。如Figure 9：5. 擴展犧牲方法的簡潔性，通過使樣本處理過程對圖像信號適應(yīng)，我們的算法很容易被擴展，考慮到低頻區(qū)域需要少的樣本，然而在高頻區(qū)域需要更多的樣本。為了使樣本處理合適，我們用高清的方式重新安排預計算的塊，用越來越密集的泊松磁盤分布，為了使它符合圖像信號。在算法的實驗版本，樣本數(shù)目的選擇由基于圖像亮度通道的梯度大小的密度映射決定。see Figure 10：在這種情況下，需要的內(nèi)存的規(guī)模就從

19、O（1）增加到O（m），m是圖像的像素總數(shù)，因為我們需要存儲密度映射。6. 分析和結(jié)果這部分內(nèi)容，我們將評估雙邊濾波器來決定它多接近brute force 濾波。因此，我們通過和前沿的方法做對比， 對視覺質(zhì)量、數(shù)值精確性、算法的時間復雜度進行評估。雖然咋3.1部分對大核的圖像需要很少的樣本，倒是為了保守起見，在我們的算法中把樣本的數(shù)目固定在2N，N是半徑(in pixes of kenerl)。6.1 視覺質(zhì)量拿可分離雙邊濾波器、雙邊網(wǎng)格、高斯KD樹、permutohedral Lattice和我們方法對比，通過對比，我們的方法可以產(chǎn)生很好的視覺質(zhì)量。在對比中，I是原始圖像，I*是使用full bilateral filter的圖像，If 是使用上述方法之一的結(jié)果，對比結(jié)果在Figure 11，不同的圖像差異，對評估視覺差異有幫助，通過使用值差的絕對值來計算，為了增加可讀性，這些差異都被放大10倍。正如提到的，二次采樣雙邊濾波展示了很好的視覺質(zhì)量。Figure 11 s = 100 pixes r =0.196.2 精確估計為了精確估計，介紹幾個公式：EMAX ，E ，Er，RMSEm 是像素的總數(shù)，我們在HDR圖像上測試濾波器的精確度，采用多次曝光的峰值信噪比(mPSNR)，mPSNR是非常有名的測試HDR壓縮方法的標準，這個標準在使用r射線在色調(diào)映射的時候做一系列的曝