基于自适应流形滤波的边缘感知编辑

周冠霖,胡 伟,张 帆,袁国栋

(1.北京化工大学信息科学与技术学院,北京100029;2.清华大学计算机科学与技术系,北京100084)

基于自适应流形滤波的边缘感知编辑

周冠霖1,胡 伟1,张 帆1,袁国栋2

(1.北京化工大学信息科学与技术学院,北京100029;2.清华大学计算机科学与技术系,北京100084)

边缘感知编辑是图像和视频编辑中运用非常广泛的编辑方法。全局优化计算是处理此类问题的最常用手段,但是在处理高分辨率图像视频时存在诸多性能问题。为此,提出一种采用自适应流形滤波的方法,用于处理多种边缘感知编辑。借助自适应流形滤波具有局部边缘感知以及全局影响扩散的特性,实现多种边缘感知编辑的处理效果,同时避免传统的全局优化方法所产生的时间损耗和较高的计算复杂度,得到较好的视觉效果。实验结果表明,该方法具有较好的边缘保持性和全局性,并能够实时处理高分辨率的视频图像。

编辑传播;上色;分割;抠图;自适应流形滤波;边缘保持滤波器

1 概述

边缘感知图像编辑已经在计算机图形和视觉领域被广泛地研究,这一类图像编辑的应用主要是将稀疏的笔画按照需要扩散到整个图像中。例如,图像上色、编辑传播、材质编辑、抠图和分割等。这些应用在人们日常的图像处理工作中发挥了重要作用。

边缘感知图像编辑一般采用能量优化的方法,例如:文献[1]认为在空间-时间域中具有相似强度的相邻像素也具有相似的颜色。在这个前提下,他们使用求解优化问题的方法来实现上色。文献[2]使用边缘保持的能量最小化方法来实现局部地改变图像的色调和其他视觉参数。文献[3]使用了能量优化的方法来实现编辑传播和材质编辑。类似于这些基于能量优化的方法都需要求解大型稀疏矩阵[4-6]。

为了能够完善这一类应用的效果,一些技术中应用到了近似的策略,例如:文献[7-8]将空间聚类算法应用于编辑传播,文献[9]采用了重复制定算法。

另一种常用的方法是各向异性扩散技术,如文献[10]使用这种技术实现了彩色图像分割,文献[11]提出了扩散性更好的四步算法用于各项异性扩散。

除了上述办法,基于边缘保持的滤波技术也可以取得较理想的效果。早期的边缘保持滤波器包括:双边滤波器[12]以及相关的加速改进技术[13-15],非局部均值算法[16],引导图像滤波[17]等。在最近的研究中,文献[18]提出了将域变换应用于减少输入图像维度的边缘感知图像处理技术,其中包括迭代滤波器。这一滤波器的边缘保持性和无限冲击响应可以解决图像的编辑传播[19]。

本文将自适应流形的滤波器应用于这一类图像处理任务。该滤波器是在迭代滤波器的基础上提出的实时高维的滤波器[20],表现出较好的全局扩散和强边缘保持的优点。

2 边缘感知编辑

边缘感知编辑的主要任务是能够将涂抹的笔画扩散到用户需要改变的地方,这种扩散具有全局性。为了能够清楚地区分所选中的区域与其他区域,需要获得每一笔的影响范围,这就是影响图(influence maps)。前人实现的边缘感知编辑都是首先获得预期的影响图,然后再对所选中的区域进行编辑。为了获得理想的影响图,边缘保持技术起到关键的作用。通常获得的影响图主要是通过求解大型的线性方程组或使用各向异性扩散技术。

另一类边缘感知技术是通过建立滤波内核来进行边缘保持滤波,目的就是在尽可能保持图像边缘的情况下平滑图像并去除夹杂在其中的噪声和干扰,使得图像效果达到人们预期的水平,这是图像预处理中重要的组成部分。在用于边缘感知的图像处理时,边缘保持滤波器通过滤波来扩散用户事先画在输入图像上的笔画,由于它可以保持输入图像的边缘信息,所以可以获得理想的影响图。

最经典的边缘保持滤波器是第一部分提到的双边滤波器[12],它综合考虑到图像像素在空间上的邻近程度和在亮度上的相似程度。然而双边滤波器都局限于计算相邻的像素值,而无法处理较远距离的像素。因此,这是一种非迭代的、局部的、简单的滤波方法。在后来出现的引导图像(guided image)滤波器[17]也是通过建立内核来实现滤波,与双边滤波器相比,它在保持图像边缘方面体现了较好的性能。这些经典的边缘保持滤波器在用于传播信息时均体现出了局部性,无法按照图像边缘信息将人为的笔画扩散到整个图像中。因此它们并不适用于进行这类边缘感知的图像处理应用。

近年来,Gastal和Oliveira提出了迭代滤波器,它是一种因果型的滤波器。它的每一次迭代的输出取决于上一次迭代的输入和输出信号,因此一次迭代滤波的冲击响应不均衡。所以通常的滤波过程需要从多个方向来实现。这样迭代滤波器具有无限冲击响应,可以将滤波的效果扩散到整个输入图像中,并且可以保持原图像中的较强边缘细节。Hu使用边缘感知的迭代滤波器(RF)获得了理想的影响图,并实现了以传播编辑为主的一类边缘感知的图像处理的应用。但是迭代滤波器是以水平(或者垂直)方向来扩散滤波效果,在遇到具有大面积不连续且复杂边缘的图像时,它的传播效果会有一些局限性。

本文使用自适应流形滤波器实现上述应用。简要介绍自适应流形滤波算法,并进一步描述采用自适应流形滤波进行边缘感知编辑的基本思想。

2.1 自适应流形滤波算法

自适应流形滤波需要从流形树的根节点开始,每计算出一个流形,就在这个流形上滤波,直至KD树上的最后一个节点。最后的得到的结果是每一次滤波结果的加权求和。

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

投射的主要任务是将图像中的像素值投射到当前流形上,投射方程可表示为:

其中,ΣR是一个dR×dR的对角协方差矩阵。

滤波使用递归型滤波器(RF),这一过程可表示为:

其中,σs和σr是在像素空间上和像素值上滤波的参数。这2个参数越大,流形越平缓,即与待滤波信号相似性越低。因此需要更多的流形来保证滤波的效果,由此算法复杂度增加。在第3节的应用中将介绍这2个参数的取值。

聚合是一个加权求和的过程,聚合的表达式为:

其中,K为滤波中将要使用到的自适应流形的总个数,wki为流形k所对应的权值。

综上所述,自适应流形滤波算法是一个递归的过程,递归的次数取决于停止标准(Stopping Criteria)[20]。

2.2 算法思想

相比与之前的边缘感知滤波器,自适应流形滤波器的滤波效果不但具有全局性,而且对于强边缘的保持效果也很好。首先,自适应流形滤波器采用以每个自适应流形为标准,对输入图像进行迭代滤波,并将所有的滤波结果加权求和,由于迭代滤波器可以产生无限冲击响应,这样得到的传播效果继承了迭代滤波器的这一优点,因此可以在整个图像的范围内获得良好的影响图。其次,自适应流形滤波器所生成的各个流形在高维空间中始终与输入的基准信号相适应,这使得流形可以很好地代表输入的基准信号,为相似颜色值的像素间交换信息定义了标准。以这样的具有自适应性的流形为标准来滤波,非常适用于传播需要的信息并保持清晰的边缘。再者,在上一部分的介绍中,可知自适应流形滤波器的滤波过程是一边建立流形树,一边进行滤波,即计算一个流形,便在该流形上对输入信号进行滤波,然后持续递归直至完成了在所有流形上的滤波。这比起迭代滤波器在水平(或垂直)方向上滤波,它具有更加多维的滤波方向,由此产生的效果可以在更为复杂的边缘处实现扩散,克服了迭代滤波器处理不连续的复杂边缘时体现的缺点。综上所述,自适应流形滤波在边缘保持方面的优越性可以获得理想的影响图,并实现边缘感知编辑的各种应用。

3 自适应流形滤波的应用

本节将介绍自适应流形滤波在包括上色、编辑传播、图像分割以及抠图中的具体实现思路。

3.1 上色

本文中利用自适应流形滤波的方法实现了对灰度图像的上色,其主要思想是对人为描绘的各种颜色的笔画按照图像的边缘进行扩散。此处将人为描绘的笔画记做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。由此可见,在图像边缘不连续且复杂的情况下,自适应流形滤波可以处理比较复杂的边缘,更适用于图像上色。

图2 2种滤波用于上色的效果比较

在这个应用中,为了在像素的空间位置和颜色值上都获得良好的扩散效果,参数取值范围为σs=5～20,σr=0.01～0.1。

因此,自适应流形滤波的全局扩散性以及边缘保持性适用于图像上色这一应用,并且由它得到的结果和优化方法得到的结果具有同样的效果。自适应流形滤波用于上色无需求解大型稀疏矩阵,具有更高的效率。

3.2 编辑传播

借助文献[19]提供的思路,自适应流形滤波器同样可用于图像的编辑传播。在这一应用中,用户只需在原图像中用笔画将需要编辑的地方进行选中,并制定需要改变的参数(如色调、饱和度、亮度),就可以得到预期的处理效果。

在生成影响图(Influence Maps)的过程中,需要多次使用自适应流形滤波器。对于每一次滤波,采用不同的滤波参数。首先,生成的初始响应图IIM (Initial Influence Map),参数 σs=100～150,σr=0.03～0.3,本文设置σs=100,σr=0.03。这里只需获得初始扩散效果,一定范围内的参数选取对最终影响图的效果影响不大。然后生成的颜色刷影响图BIM(Brush Influence Map),以及笔画颜色影响图SCM(Strokes Color Map),均设置参数σs=20,σr=0.03,这里的扩散在空间域和颜色值域的要求与上色应用中的一致,因此参数选取范围与上一节一致。

图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 抠图

抠图的过程同样是为了获得理想的影响图,在实现这一应用时,为了在边缘处获得良好的效果,在获得改良的颜色响应图(Refined Color Response Map, RCRM)之后采用了引导图像滤波器(其中r=20,ε=10-6)对边缘处进行优化,由图6可以看出,当图像边缘不太复杂时,本文方法可以获得较好的效果。

图6 本文方法与Ground Truth的结果对比图

4 性能分析

测试数据在操作系统为Windows 7旗舰版、CPU为Intel I7处理器、系统内存6 GB、显卡为Nvidia GTX 465的普通PC上获得。

已知自适应流形滤波的所需时间为O(dNK),其中,d为滤波器运行空间的维度,N为像素的总个数,K为滤波器所需流形的个数。对于上色的算法,本文在每一个维度上进行滤波,每次滤波时的d取值为1,即所需时间为O(NK)。图7比较了用Matlab 7.1实现的Levin的方法和本文方法所用的时间。图中的—○线表示Levin的方法(生成的图像为图1(c)),图中的虚线部分表示,当灰度图像分辨率较高时,Levin的方法已经无法计算出结果;—✕线表示本文方法计算结果所需的时间(生成的图像为图1(b))。由图7可知,当输入图像的分辨率相同时,本文方法的计算速度是Levin方法的4倍以上,这大大提高了运算效率。此外,鉴于自适应流形滤波非常适合使用GPU进行加速计算,本文使用CUDA 4.1实现了算法。

图7 2种上色方法的着色时间比较

在编辑传播等应用中,需要多次用到自适应流形滤波。以两笔为例,计算过程中分为3个阶段,表1给出了图3以及图4编辑计算所需的时间(图像分辨率均为720×576),包括3个阶段:计算初始响应图(Initial Response Map,IRM),RCRM以及最后合成处理。

表1 编辑传播3个阶段所需时间

在本文实现中,90%以上的时间用于完成自适应流形滤波。由文献[20]可知,基于GPU实现的自适应流形滤波器能够在1 ms～4 ms内处理1 M像素的图像(GTX 280 GPU),性能比本文的实现更高。因此,如果进一步优化CUDA程序,将能够实时处理1 080 p的图像和视频编辑。

5 结束语

本文提出采用自适应流形滤波的方法来实现关于边缘敏感的图像处理。这种滤波器具有较好的边缘保持效果和全局性,可以有效地扩散用户所预期的编辑结果,在灰度图像上色、图像编辑传播以及分割的应用上取得了较好的效果。用户无需求解大量的优化方程,只需对所要编辑的区域用笔画进行选定,就可以得到理想结果。这比起以往的能量最小化方法,大大减少了用户操作的难度。但是通过分析比较可知,自适应流形滤波更适合应用于边缘感知的图像和视频编辑。然而目前的算法仍然存在局限性,例如分割应用中,笔画影响图在图像细节处不够理想,需要采用引导图像滤波器来提高其视觉效果,因此有待进一步研究和改进。

[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-),女,硕士,主研方向:数字滤波技术;胡 伟、张 帆,副教授;袁国栋,讲师。

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.