周冠霖,胡 偉,張 帆,袁國棟

(1.北京化工大學信息科學與技術學院,北京100029;2.清華大學計算機科學與技術系,北京100084)

基于自適應流形濾波的邊緣感知編輯

周冠霖1,胡 偉1,張 帆1,袁國棟2

(1.北京化工大學信息科學與技術學院,北京100029;2.清華大學計算機科學與技術系,北京100084)

邊緣感知編輯是圖像和視頻編輯中運用非常廣泛的編輯方法。全局優(yōu)化計算是處理此類問題的最常用手段,但是在處理高分辨率圖像視頻時存在諸多性能問題。為此,提出一種采用自適應流形濾波的方法,用于處理多種邊緣感知編輯。借助自適應流形濾波具有局部邊緣感知以及全局影響擴散的特性,實現(xiàn)多種邊緣感知編輯的處理效果,同時避免傳統(tǒng)的全局優(yōu)化方法所產(chǎn)生的時間損耗和較高的計算復雜度,得到較好的視覺效果。實驗結果表明,該方法具有較好的邊緣保持性和全局性,并能夠實時處理高分辨率的視頻圖像。

編輯傳播;上色;分割;摳圖;自適應流形濾波;邊緣保持濾波器

1 概述

邊緣感知圖像編輯已經(jīng)在計算機圖形和視覺領域被廣泛地研究,這一類圖像編輯的應用主要是將稀疏的筆畫按照需要擴散到整個圖像中。例如,圖像上色、編輯傳播、材質編輯、摳圖和分割等。這些應用在人們?nèi)粘５膱D像處理工作中發(fā)揮了重要作用。

邊緣感知圖像編輯一般采用能量優(yōu)化的方法,例如:文獻[1]認為在空間-時間域中具有相似強度的相鄰像素也具有相似的顏色。在這個前提下,他們使用求解優(yōu)化問題的方法來實現(xiàn)上色。文獻[2]使用邊緣保持的能量最小化方法來實現(xiàn)局部地改變圖像的色調(diào)和其他視覺參數(shù)。文獻[3]使用了能量優(yōu)化的方法來實現(xiàn)編輯傳播和材質編輯。類似于這些基于能量優(yōu)化的方法都需要求解大型稀疏矩陣[4-6]。

為了能夠完善這一類應用的效果,一些技術中應用到了近似的策略,例如:文獻[7-8]將空間聚類算法應用于編輯傳播,文獻[9]采用了重復制定算法。

另一種常用的方法是各向異性擴散技術,如文獻[10]使用這種技術實現(xiàn)了彩色圖像分割,文獻[11]提出了擴散性更好的四步算法用于各項異性擴散。

除了上述辦法,基于邊緣保持的濾波技術也可以取得較理想的效果。早期的邊緣保持濾波器包括:雙邊濾波器[12]以及相關的加速改進技術[13-15],非局部均值算法[16],引導圖像濾波[17]等。在最近的研究中,文獻[18]提出了將域變換應用于減少輸入圖像維度的邊緣感知圖像處理技術,其中包括迭代濾波器。這一濾波器的邊緣保持性和無限沖擊響應可以解決圖像的編輯傳播[19]。

本文將自適應流形的濾波器應用于這一類圖像處理任務。該濾波器是在迭代濾波器的基礎上提出的實時高維的濾波器[20],表現(xiàn)出較好的全局擴散和強邊緣保持的優(yōu)點。

2 邊緣感知編輯

邊緣感知編輯的主要任務是能夠將涂抹的筆畫擴散到用戶需要改變的地方,這種擴散具有全局性。為了能夠清楚地區(qū)分所選中的區(qū)域與其他區(qū)域,需要獲得每一筆的影響范圍,這就是影響圖(influence maps)。前人實現(xiàn)的邊緣感知編輯都是首先獲得預期的影響圖,然后再對所選中的區(qū)域進行編輯。為了獲得理想的影響圖,邊緣保持技術起到關鍵的作用。通常獲得的影響圖主要是通過求解大型的線性方程組或使用各向異性擴散技術。

另一類邊緣感知技術是通過建立濾波內(nèi)核來進行邊緣保持濾波,目的就是在盡可能保持圖像邊緣的情況下平滑圖像并去除夾雜在其中的噪聲和干擾,使得圖像效果達到人們預期的水平,這是圖像預處理中重要的組成部分。在用于邊緣感知的圖像處理時,邊緣保持濾波器通過濾波來擴散用戶事先畫在輸入圖像上的筆畫,由于它可以保持輸入圖像的邊緣信息,所以可以獲得理想的影響圖。

最經(jīng)典的邊緣保持濾波器是第一部分提到的雙邊濾波器[12],它綜合考慮到圖像像素在空間上的鄰近程度和在亮度上的相似程度。然而雙邊濾波器都局限于計算相鄰的像素值,而無法處理較遠距離的像素。因此,這是一種非迭代的、局部的、簡單的濾波方法。在后來出現(xiàn)的引導圖像(guided image)濾波器[17]也是通過建立內(nèi)核來實現(xiàn)濾波,與雙邊濾波器相比,它在保持圖像邊緣方面體現(xiàn)了較好的性能。這些經(jīng)典的邊緣保持濾波器在用于傳播信息時均體現(xiàn)出了局部性,無法按照圖像邊緣信息將人為的筆畫擴散到整個圖像中。因此它們并不適用于進行這類邊緣感知的圖像處理應用。

近年來,Gastal和Oliveira提出了迭代濾波器,它是一種因果型的濾波器。它的每一次迭代的輸出取決于上一次迭代的輸入和輸出信號,因此一次迭代濾波的沖擊響應不均衡。所以通常的濾波過程需要從多個方向來實現(xiàn)。這樣迭代濾波器具有無限沖擊響應,可以將濾波的效果擴散到整個輸入圖像中,并且可以保持原圖像中的較強邊緣細節(jié)。Hu使用邊緣感知的迭代濾波器(RF)獲得了理想的影響圖,并實現(xiàn)了以傳播編輯為主的一類邊緣感知的圖像處理的應用。但是迭代濾波器是以水平(或者垂直)方向來擴散濾波效果,在遇到具有大面積不連續(xù)且復雜邊緣的圖像時,它的傳播效果會有一些局限性。

本文使用自適應流形濾波器實現(xiàn)上述應用。簡要介紹自適應流形濾波算法,并進一步描述采用自適應流形濾波進行邊緣感知編輯的基本思想。

2.1 自適應流形濾波算法

自適應流形濾波需要從流形樹的根節(jié)點開始,每計算出一個流形,就在這個流形上濾波,直至KD樹上的最后一個節(jié)點。最后的得到的結果是每一次濾波結果的加權求和。

濾波主要分三部分進行:投射(Splatting),平滑(Blurring)和聚合(Slicing)。

投射的主要任務是將圖像中的像素值投射到當前流形上,投射方程可表示為:

其中,ΣR是一個dR×dR的對角協(xié)方差矩陣。

濾波使用遞歸型濾波器(RF),這一過程可表示為:

其中,σs和σr是在像素空間上和像素值上濾波的參數(shù)。這2個參數(shù)越大,流形越平緩,即與待濾波信號相似性越低。因此需要更多的流形來保證濾波的效果,由此算法復雜度增加。在第3節(jié)的應用中將介紹這2個參數(shù)的取值。

聚合是一個加權求和的過程,聚合的表達式為:

其中,K為濾波中將要使用到的自適應流形的總個數(shù),wki為流形k所對應的權值。

綜上所述,自適應流形濾波算法是一個遞歸的過程,遞歸的次數(shù)取決于停止標準(Stopping Criteria)[20]。

2.2 算法思想

相比與之前的邊緣感知濾波器,自適應流形濾波器的濾波效果不但具有全局性,而且對于強邊緣的保持效果也很好。首先,自適應流形濾波器采用以每個自適應流形為標準,對輸入圖像進行迭代濾波,并將所有的濾波結果加權求和,由于迭代濾波器可以產(chǎn)生無限沖擊響應,這樣得到的傳播效果繼承了迭代濾波器的這一優(yōu)點,因此可以在整個圖像的范圍內(nèi)獲得良好的影響圖。其次,自適應流形濾波器所生成的各個流形在高維空間中始終與輸入的基準信號相適應,這使得流形可以很好地代表輸入的基準信號,為相似顏色值的像素間交換信息定義了標準。以這樣的具有自適應性的流形為標準來濾波,非常適用于傳播需要的信息并保持清晰的邊緣。再者,在上一部分的介紹中,可知自適應流形濾波器的濾波過程是一邊建立流形樹,一邊進行濾波,即計算一個流形,便在該流形上對輸入信號進行濾波,然后持續(xù)遞歸直至完成了在所有流形上的濾波。這比起迭代濾波器在水平(或垂直)方向上濾波,它具有更加多維的濾波方向,由此產(chǎn)生的效果可以在更為復雜的邊緣處實現(xiàn)擴散,克服了迭代濾波器處理不連續(xù)的復雜邊緣時體現(xiàn)的缺點。綜上所述,自適應流形濾波在邊緣保持方面的優(yōu)越性可以獲得理想的影響圖,并實現(xiàn)邊緣感知編輯的各種應用。

3 自適應流形濾波的應用

本節(jié)將介紹自適應流形濾波在包括上色、編輯傳播、圖像分割以及摳圖中的具體實現(xiàn)思路。

3.1 上色

本文中利用自適應流形濾波的方法實現(xiàn)了對灰度圖像的上色,其主要思想是對人為描繪的各種顏色的筆畫按照圖像的邊緣進行擴散。此處將人為描繪的筆畫記做S,N定義為被筆畫覆蓋的像素為1,否則為0。每個像素所獲得的顏色值定義為C(p):

圖1所示為本文與Levin等的上色效果的比較。2種方法的輸入圖像均為第1幅圖(分辨率為320× 265),其中,第4幅圖的最大值為0.102 5。σs=7.5,σr=0.02。從中可以看出本文的上色方法可以獲得與Levin方法同樣好的效果。

圖1 圖像上色的效果比較

圖2所示為本文與迭代濾波的上色效果比較。圖2(a)中,σs=20,σr=0.03;圖2(b)中,σs=100, σr=0.03。由此可見,在圖像邊緣不連續(xù)且復雜的情況下,自適應流形濾波可以處理比較復雜的邊緣,更適用于圖像上色。

圖2 2種濾波用于上色的效果比較

在這個應用中,為了在像素的空間位置和顏色值上都獲得良好的擴散效果,參數(shù)取值范圍為σs=5～20,σr=0.01～0.1。

因此,自適應流形濾波的全局擴散性以及邊緣保持性適用于圖像上色這一應用,并且由它得到的結果和優(yōu)化方法得到的結果具有同樣的效果。自適應流形濾波用于上色無需求解大型稀疏矩陣,具有更高的效率。

3.2 編輯傳播

借助文獻[19]提供的思路,自適應流形濾波器同樣可用于圖像的編輯傳播。在這一應用中,用戶只需在原圖像中用筆畫將需要編輯的地方進行選中,并制定需要改變的參數(shù)(如色調(diào)、飽和度、亮度),就可以得到預期的處理效果。

在生成影響圖(Influence Maps)的過程中,需要多次使用自適應流形濾波器。對于每一次濾波,采用不同的濾波參數(shù)。首先,生成的初始響應圖IIM (Initial Influence Map),參數(shù) σs=100～150,σr=0.03～0.3,本文設置σs=100,σr=0.03。這里只需獲得初始擴散效果,一定范圍內(nèi)的參數(shù)選取對最終影響圖的效果影響不大。然后生成的顏色刷影響圖BIM(Brush Influence Map),以及筆畫顏色影響圖SCM(Strokes Color Map),均設置參數(shù)σs=20,σr=0.03,這里的擴散在空間域和顏色值域的要求與上色應用中的一致,因此參數(shù)選取范圍與上一節(jié)一致。

圖3所示為筆畫的影響圖以及最后的效果圖。在圖4中給出了本文的方法與文獻[21]方法效果的對比,視覺上兩者的結果基本無差異,差異圖從上至下的最大值依次為0.136 5,0.176 5,0.230 6。從中可以看出本文方法的效果與文獻[21]方法效果基本一致。因此,自適應流形濾波可以生成理想的編輯效果。

圖3 筆畫影響圖及其效果圖

圖4 本文方法與文獻[21]方法對比圖

3.3 分割

這部分展示了自適應流形濾波應用于圖像分割的效果。為了得到理想的效果,此應用中需要改變HSV直方圖和閾值的大小,并且當各個像素點處的影響圖的值大于或者等于0.5,則該像素點歸為前景,反之則為背景。從圖5的結果可以看出,本文方法可以得到理想的視覺效果。

圖5 本文方法與文獻[22]方法對比圖

3.4 摳圖

摳圖的過程同樣是為了獲得理想的影響圖,在實現(xiàn)這一應用時,為了在邊緣處獲得良好的效果,在獲得改良的顏色響應圖(Refined Color Response Map, RCRM)之后采用了引導圖像濾波器(其中r=20,ε=10-6)對邊緣處進行優(yōu)化,由圖6可以看出,當圖像邊緣不太復雜時,本文方法可以獲得較好的效果。

圖6 本文方法與Ground Truth的結果對比圖

4 性能分析

測試數(shù)據(jù)在操作系統(tǒng)為Windows 7旗艦版、CPU為Intel I7處理器、系統(tǒng)內(nèi)存6 GB、顯卡為Nvidia GTX 465的普通PC上獲得。

已知自適應流形濾波的所需時間為O(dNK),其中,d為濾波器運行空間的維度,N為像素的總個數(shù),K為濾波器所需流形的個數(shù)。對于上色的算法,本文在每一個維度上進行濾波,每次濾波時的d取值為1,即所需時間為O(NK)。圖7比較了用Matlab 7.1實現(xiàn)的Levin的方法和本文方法所用的時間。圖中的—○線表示Levin的方法(生成的圖像為圖1(c)),圖中的虛線部分表示,當灰度圖像分辨率較高時,Levin的方法已經(jīng)無法計算出結果;—?線表示本文方法計算結果所需的時間(生成的圖像為圖1(b))。由圖7可知,當輸入圖像的分辨率相同時,本文方法的計算速度是Levin方法的4倍以上,這大大提高了運算效率。此外,鑒于自適應流形濾波非常適合使用GPU進行加速計算,本文使用CUDA 4.1實現(xiàn)了算法。

圖7 2種上色方法的著色時間比較

在編輯傳播等應用中,需要多次用到自適應流形濾波。以兩筆為例,計算過程中分為3個階段,表1給出了圖3以及圖4編輯計算所需的時間(圖像分辨率均為720×576),包括3個階段:計算初始響應圖(Initial Response Map,IRM),RCRM以及最后合成處理。

表1 編輯傳播3個階段所需時間

在本文實現(xiàn)中,90%以上的時間用于完成自適應流形濾波。由文獻[20]可知,基于GPU實現(xiàn)的自適應流形濾波器能夠在1 ms～4 ms內(nèi)處理1 M像素的圖像(GTX 280 GPU),性能比本文的實現(xiàn)更高。因此,如果進一步優(yōu)化CUDA程序,將能夠實時處理1 080 p的圖像和視頻編輯。

5 結束語

本文提出采用自適應流形濾波的方法來實現(xiàn)關于邊緣敏感的圖像處理。這種濾波器具有較好的邊緣保持效果和全局性,可以有效地擴散用戶所預期的編輯結果,在灰度圖像上色、圖像編輯傳播以及分割的應用上取得了較好的效果。用戶無需求解大量的優(yōu)化方程,只需對所要編輯的區(qū)域用筆畫進行選定,就可以得到理想結果。這比起以往的能量最小化方法,大大減少了用戶操作的難度。但是通過分析比較可知,自適應流形濾波更適合應用于邊緣感知的圖像和視頻編輯。然而目前的算法仍然存在局限性,例如分割應用中,筆畫影響圖在圖像細節(jié)處不夠理想,需要采用引導圖像濾波器來提高其視覺效果,因此有待進一步研究和改進。

[1] Levin A,Lischinski D,Weiss Y.Colorization Using Optimization[J].ACM Transactions on Graphics,2004, 23(3):689-694.

[2] Lischinski D,Farbman Z,Uyttendaele M,etal. Interactive Local Adjustment of Tonal Values[J].ACM Transactions on Graphics,2006,25(3):646-653.

[3] Pellacini F,Lawrence J.Appward:Editing Measured Materials Using Appearance-driven Optimization[J]. ACM Transactions on Graphics,2007,26(3).

[4] Farbman Z,Fattal R,Lischinski D,et al.Edit-preserving Decompositions for Multi-scale Tone and Detail Manipulation[J].ACM Transactions on Graphics,2008,27(3).

[5] Farbman Z,Fattal R,Lischinski D.Diffusion Maps for Edge-aware Image Editing[J].ACM Transactions on Graphics,2010,29(6).

[6] Levin A,Lischinski D,Weiss Y.A Closed-form Solution to Natural Image Matting[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(2): 228-242.

[7] Xu K,Li Y,Ju T,et al.Efficient Affinity-based Edit Propagation Using K-D Tree[J].ACM Transactions on Graphics,2009,28(5).

[8] Xiao Chunxia,Nie Yongwei,Tang Feng.Efficient Edit Propagation Using Hierarchical Data Structure[J].IEEE Transactions on Visualization and Computer Graphics, 2011,17(8):1135-1147.

[9] Li Yong,Ju Tao,Hu S M.Instant Propagation of Sparse Edits on Images and Videos[J].Computer Graphics Forum,2010,29(7):2049-2054.

[10] 黃 敦,游志勝.對彩色和亮度通道進行各向異性擴散的彩色圖像分割[J].計算機工程,2002,28(6): 166-169.

[11] 喬 剛.基于各向異性擴散的圖像處理技術及其應用[D].成都:電子科技大學,2012.

[12] Tomasi C,Manduchi R.Bilateral Filtering for Gray and Color Images[C]//Proceedings of the 6th International Conference on Computer Vision.[S.l.]:IEEE Press, 1998:839-846.

[13] Eisemann E,Durand F.Flash Photography Enhancement via Intrinsic Relighting[J].ACM Transactions on Graphics,2004,23(3).

[14] Petschnigg G,Szeliski R,Agrawala M,et al.Digital Photography with Flash and No-flash Image Pairs[J]. ACM Transactions on Graphics,2004,23(3).

[15] Weber M,Milch M,Myszkowski K,et al.Spatio-temporal Photon Density Estimation Using Bilateral Filtering[C]// Proceedings of International Conference on Computer Graphics.[S.l.]:IEEE Press,2004:120-127.

[16] Buades A,Coll B,Morel J.A Non-local Algorithm for Image Denoising[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.[S.l.]:IEEE Press,2005:60-65.

[17] He Kaiming,Sun Jian,Tang Xiaoou.Guided Image Filtering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(6):1397-1409.

[18] Gastal E S L,Oliveira M M.Domain Transform for Edge-aware Image and Video Processing[J].ACM Transactions on Graphics,2011,30(4).

[19] Wei Hu,Zhao Dong,Yuan Guodong.Edit Propagation via Edge-aware Filtering[J].Journal of Computer Science and Technology,2012,27(4):830-840.

[20] Gastal E S L,Oliveira M M.Adaptive Manifolds for Real-time High-dimensional Filtering[J].ACM Transactions on Graphics,2012,31(4).

[21] An Xiaobo,Pellacini F.Appprop:All-pairs Appearancespace Edit Propagation[J].ACM Transactions on Graphics,2008,27(3).

[22] Rother C,Kolmogorov V,Blake A.Grabcut——Interactive Foreground Extraction Using Iterated Graph Cuts[J].ACM Transactions on Graphics,2004,23(3).

編輯 顧逸斐

Edge-aware Editing Based on Adaptive Manifolds Filtering

ZHOU Guanlin1,HU Wei1,ZHANG Fan1,YUAN Guodong2
(1.School of Information Science and Technology,Beijing University of Chemical Technology,Beijing 100029,China; 2.Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China)

Edge-aware editing is the most widely used method in image and video editing.Global optimization is commonly used to solve these problems.There are still some problems in processing high resolution image and video.So this paper presents a scheme using adaptive manifolds filtering for edge-aware editing.Instead of using the traditional optimization which may bring the time-consume and the high computational complexity,it utilizes adaptive manifolds filter,which is an edge-preserve filter with the local edge-aware and global influence to propagation the edits.A good visually result can be

with better performance.Experimental results demonstrate the good edge-preserving, globalization influences of the approach.

editing propagation;colorization;segmentation;matting;adaptive manifold filtering;edge-preserving filter

1000-3428(2015)01-0231-05

A

TP391.41

10.3969/j.issn.1000-3428.2015.01.043

國家自然科學基金青年基金資助項目(61003132)。

周冠霖(1988-),女,碩士,主研方向:數(shù)字濾波技術;胡 偉、張 帆,副教授;袁國棟,講師。

2014-03-13

2014-04-09 E-mail:zhouguan.lin@163.com

中文引用格式:周冠霖,胡 偉,張 帆,等.基于自適應流形濾波的邊緣感知編輯[J].計算機工程,2015,41(1):231-235.

英文引用格式:Zhou Guanlin,Hu Wei,Zhang Fan,et al.Edge-aware Editing Based on Adaptive Manifolds Filtering[J]. Computer Engineering,2015,41(1):231-235.