快速雙邊濾波器

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、著坐標(biāo)軸平行于他們的漸進(jìn)線，從這些圖的濾波數(shù)據(jù)到雙曲線，可以推出:small kenerl （s20pixes）需要2.5N樣本，medium kenerls （20s40）需要0. 75N樣本。4 應(yīng)用為了展示方法的有效性，我們現(xiàn)在可以把算法應(yīng)用在計(jì)算機(jī)圖像圖像處理中，包括圖像和視頻濾波，迭代濾波，交叉或者節(jié)點(diǎn)雙邊濾波，色調(diào)映射。4.1 視頻去噪： 雙邊濾波器的一個(gè)典型的應(yīng)用是圖像視頻去噪，因?yàn)闉V波器刪除了高斯噪音同時(shí)保持了完整的邊，figure 5 是視頻去噪的一個(gè)應(yīng)用。我們的方法非常應(yīng)用于視頻去噪，因?yàn)樗枰膬?nèi)存比較小，對(duì)于高清視頻可以實(shí)現(xiàn)實(shí)時(shí)的幀速率。4.2 抽象我們的雙邊濾波器適合

17、迭代濾波，因?yàn)樗諗颗c非常相近的參考結(jié)果，由于一個(gè)事實(shí)，每一次迭代，每個(gè)像素在空間位置中改變，迭代雙邊濾波器非常適用于圖像視頻抽象。4.3 閃光 非閃光攝影iso 高感光度和高速快門 2 使用閃光燈3 通過(guò)標(biāo)準(zhǔn)交叉雙邊濾波器使用閃光 非閃光攝影去噪 4 采用我們的算法4.4 邊識(shí)別圖像編輯雙邊濾波器可以用作邊識(shí)別圖像編輯。在一個(gè)選中區(qū)域圖像的參數(shù)被修改，通過(guò)畫(huà)刷描邊避免修改相領(lǐng)的區(qū)域，區(qū)域被邊分割開(kāi)來(lái)。濾波器的輸出是邊識(shí)別畫(huà)刷，可以用來(lái)修改圖像的參數(shù)(色度、飽和度、亮度)。如Figure 8：4.5 色調(diào)映射另一個(gè)應(yīng)用是HDR圖像的色調(diào)映射。使用雙邊濾波器把HDR圖像分割成基礎(chǔ)和細(xì)節(jié)圖像?；A(chǔ)

18、分層是使用Reinhard的全局色調(diào)函數(shù)。最后，基礎(chǔ)色調(diào)映射和細(xì)節(jié)被結(jié)合來(lái)獲得最后的色調(diào)映射。如Figure 9：5. 擴(kuò)展?fàn)奚椒ǖ暮?jiǎn)潔性，通過(guò)使樣本處理過(guò)程對(duì)圖像信號(hào)適應(yīng)，我們的算法很容易被擴(kuò)展，考慮到低頻區(qū)域需要少的樣本，然而在高頻區(qū)域需要更多的樣本。為了使樣本處理合適，我們用高清的方式重新安排預(yù)計(jì)算的塊，用越來(lái)越密集的泊松磁盤分布，為了使它符合圖像信號(hào)。在算法的實(shí)驗(yàn)版本，樣本數(shù)目的選擇由基于圖像亮度通道的梯度大小的密度映射決定。see Figure 10：在這種情況下，需要的內(nèi)存的規(guī)模就從O（1）增加到O（m），m是圖像的像素總數(shù)，因?yàn)槲覀冃枰鎯?chǔ)密度映射。6. 分析和結(jié)果這部分內(nèi)容，

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