《一种基于Level》doc版.doc

薄羈膇薈蒀羇艿莀蝿羇罿膃螅羆膁葿蚁羅芄芁薇羄羃蒇蒃羃肆芀螂羂膈蒅蚈肁芀芈薄肁羀蒄蒀肀肂芆袈聿芅薂螄肈莇莅蚀肇肇薀薆蚄腿莃蒂蚃芁薈螁螂羁莁蚇螁肃薇薃螀膅荿蕿蝿莈膂袇螈肇蒈螃螈膀芁虿螇节蒆薅螆羂艿蒁袅肄蒄螀袄膆芇蚆袃荿蒃蚂袂肈莅薈袂膁薁蒄袁芃莄螂袀羃蕿蚈衿肅莂薄羈膇薈蒀羇艿莀蝿羇罿膃螅羆膁葿蚁羅芄芁薇羄羃蒇蒃羃肆芀螂羂膈蒅蚈肁芀芈薄肁羀蒄蒀肀肂芆袈聿芅薂螄肈莇莅蚀肇肇薀薆蚄腿莃蒂蚃芁薈螁螂羁莁蚇螁肃薇薃螀膅荿蕿蝿莈膂袇螈肇蒈螃螈膀芁虿螇节蒆薅螆羂艿蒁袅肄蒄螀袄膆芇蚆袃荿蒃蚂袂肈莅薈袂膁薁蒄袁芃莄螂袀羃蕿蚈衿肅莂薄羈膇薈蒀羇艿莀蝿羇罿膃螅羆膁葿蚁羅芄芁薇羄羃蒇蒃羃肆芀螂羂膈蒅蚈肁芀芈薄肁羀蒄蒀肀肂芆袈聿芅薂螄肈莇莅蚀肇肇薀薆蚄腿莃蒂蚃芁薈螁螂羁莁蚇螁肃薇薃螀膅荿蕿蝿莈膂袇螈肇蒈螃螈膀芁虿螇节蒆薅螆羂艿蒁袅肄蒄螀袄膆芇蚆袃荿蒃蚂袂肈莅薈袂膁薁蒄袁芃莄螂袀羃蕿蚈衿肅莂薄羈膇薈蒀羇艿莀蝿羇罿膃螅羆膁葿蚁羅芄芁薇羄羃蒇蒃羃肆芀螂羂膈蒅蚈肁芀 一种基于Level Set 方法的图像修补技术图像修补是图像恢复研究中的一个重要内容,它的目的是根据图像的现有信息来自动恢复丢失的信息.虽然图像修补的基本思想十分简单,但是许多的图像修补算法都十分复杂,而且难于实现.快速行进算法(FMM)与水平集法(Level Set)相结合进行曲线进化是一种高效的曲线进化算法,该算法的时间复杂度是O(NlbN).Kim提出了另一种水平集的曲线进化算法-分组行进算法(GMM),该算法的时间复杂度是O(N).受其启发,为了更快地进行图像修补,提出了一种基于GMM算法的图像修补的新算法,并研究了对GMM算法的细节改进.为了验证算法的快速性,还给出了使用Bertalmio提出的算法、Telea提出的算法以及新算法对同一幅图片进行修补的实验结果.通过比较发现,该新算法在大幅度提高修补速度的同时,仍能保持较好的修补效果.Level Set方法简介： Level Set方法是由Sethian和Osher于1988年提出，最近十几年得到广泛的推广与应用。简单的说来，Level Set方法把低维的一些计算上升到更高一维，把N维的描述看成是N1维的一个水平。举个例子来说，一个二维平面的圆，如x2+y2=1可以看成是二元函数f(x,y)=x2+y2的1水平，因此，计算这个圆的变化时就可以先求f(x,y)的变化，再求其1水平集。这样做的好处是，第一，低维时的拓扑变化在高维中不再是一个难题；第二，低维需要不时的重新参数化，高维中不需要；第三，高维的计算更精确，更鲁棒；第四，Level Set方法可以非常容易的向更高维推广；最后，也是非常重要的一点就是，上升到高维空间中后，许多已经成熟的算法可以拿过了直接用，并且在这方面有非常成熟的分析工具，譬如偏微分方程的理论及其数值化等。当然，这种方法最为诟病的就是他增加了计算量，但新的快速算法不断出现，使得这也不是个大问题。 Level Set的适用范围： 这儿只是列举一些经典的领域，但并不完全，如果你能在自己的领域找到新的应用，祝贺你。 Level Set最初始的应用领域就是隐含曲线（曲面）的运动，现在Level Set已经广泛应用于图像恢复、图像增强、图像分割、物体跟踪、形状检测与识别、曲面重建、最小曲面、最优化以及流体力学中的一些东西。 图像修补技术是一项古老的艺术, 欧洲文艺复兴时期, 为了恢复美术作品中丢失或被损坏的部分, 同时保持作品的整体效果, 开始进行对中世纪的美术品的修复, 这些工作被称为Retouching( 润饰) 或者Inpainting( 修补) 。同样, 该方法也可应用到数字图像的修补中, 这就是数字图像修补技术( Digital Inpainting)。从数学的角度来看, 图像修补就是根据空白区域周围的信息将图像添入空白区域中, 因此, 图像修补属于图像恢复的研究。在进行图像修补时, 通常先用掩码( Mask) 确定需要修补的区域, 然后根据修补区域周围的信息用图像修补算法自动恢复区域中的信息。数字图像修补技术的应用非常广泛, 如修复破旧照片、恢复破损的影片、去除图片中添加的文字( 如出版信息、拍摄日期) , 删除图像中的某个物体以及光影效果去除和纹理填充等。因此, 该技术已经引起了众多学者的关注, 从20 世纪90 年代末提出Digital Inpainting 的概念到现在已经出现了很多成功的算法。Bertalmio 等人提出了一种基于偏微分方程的BSCB 算法 1 , 利用待修补区域的边缘信息, 将待修补区域外的信息沿梯度的垂直方向扩散到修补区域内, 取得了很好的效果。受到Bertalmio 等人工作的启发, Chan 等人提出了将整体变分( TV)模型 2 用于图像修补, 整体变分算法是一种较好的异向扩散算法, 该算法可以在保持边缘的同时达到去噪的目的。Crimimisi 等人提出了一种基于纹理生成的修复方法 3 , 在待修补区域的边界通过块匹配的方法选择合适的纹理填充, 对纹理修复有较好的效果, 但对结构信息修复效果较差。针对TV模型的缺点, Chan 和Shen 提出的基于曲率扩散的CDD 修补模型 4 , 能对较大破损区域进行修补, 但是造成了一定程度的模糊。以上的这些方法在修补某一类图像时都能取得较好的效果, 但都存在明显的局限性, 即不能对每一种情况都修补得很好, 而且, 它们大都利用迭代公式, 修复一个点往往要迭代几千次才能得到差不多的效果, 所以运行时间较长, 修补一幅图要用3 4 分钟才能完成, 这就限制了它们推广和应用。针对这种情况, 本文提出了一种基于Level Set 方法的新算法, 能在保持修复效果的基础上大大缩短修补时间。1 Level Set 方法及Fast Marching 方法( FMM)水平集( Level Set) 方法主要是从界面传播等研究领域中逐步发展起来的, 它是处理封闭运动界面随时间演化过程中几何拓扑变化的有效的计算工具, 由Osher 和Sethian 5 首先提出。Level Set 方法的基本思想是将平面闭合曲线隐含地表达为二维曲面函数的水平集, 即具有相同函数值的点集, 通过Level Set 函数曲面的进化隐含地求解曲线的运动。尽管这种转换使得问题在形式上变得复杂, 但在问题的求解上带来很多优点, 其最大的优点在于曲线的拓扑变化能够得到很自然的处理, 而且可以获得唯一的满足熵条件的弱解。Level Set 函数的演化满足如下的基本方程:t + F | |= 0 ( 1 )其中, 为Level Set 函数, 其零水平集表示目标轮廓曲线, 即( t) = x |( x, t) =0 , 表示Level Set 函数的梯度范数; F为曲面法线方向上的速度函数, 控制曲线的运动。一般F 包括与图像有关的项( 如梯度信息等) 以及与曲线的几何形状有关的项( 如曲线的曲率等) 。虽然上述思想很好, 但是对所有的Level Sets 都要进行计算, 而不单是对与传播前沿相关的零Level Set 进行计算, 所以它存在一个很大的缺点是运算量很大, 对一个NN的图像进行运算, 每一步的运算复杂度为O( N2 ) 。如果传播前沿的法向速度总是保持全正或全负, 那么就可以把上面的问题转换为寻求每个Level Set 到达的时间, 把问题转换为可大大提高运算速度的Fast Marching 方法。Fast Marching 方法把问题变为求解方程 Tv( x) = ( x) ( 2)这是一个表示曲线随时间进化的Eikonal 方程。假设T( x, y) 为曲线穿越点( x, y) 的时间, 式( 2) 可以转换为|T|F = 1 ( 3)从式( 3) 可知: 到达时间梯度曲面与传播前沿的速度成反比。Sethian 6 指出, 要得到式( 3) 中的到达时间T, 等价于求解下面的二次方程( 具体的近似解决方案见文献 6,7 ) max( D - xij T, 0) 2 + min( D +xij , 0 ) 2 + max( D- yij T, 0 ) 2 + min( D +yij ,0) 2 12= 1Fij( 4)这里, D- 和D+ 分别是后向差分和前向差分算子。下面, 给出Fast Marching 方法的具体步骤:( 1) 初始化选定种子点标记为Alive, 构_成Alive 点集, 且每一点的T值为0;紧邻种子点的网格点( 多选4 邻域) 构成Narrowband 点集, 每一点的T值为dx2 +dy2 /F;其他的网格点组成Faraway 点集, 每一点的T值为+。( 2) 快进从Narrowband 点集中选择具有最小T 值的点, 设为( imin, jmin) ;将( imin, jmin) 点加入到Alive 点集, 并将它从Narrowband点集中删除;在非Alive 的邻域点( imin - 1 , jmin) , ( imin+ 1 , jmin ) , ( imin,jmin - 1 ) , ( imin, jmin+1 ) 中将Faraway 点集加入到Narrowband 点集,并将它们从Faraway 点集中删除;根据式( 4) 更新邻域点的T 值;转。2 利用FMM 进行图像修补2. 1 修补算法如图1( a) 所示, 首先从待修补区域的边界开始修补, 对于要修复的点p, 我们选取待修补区域外距离p 较近的一组像素Bn( 选择修补区域之外的像素, n 代表像素) 来修补它。当只考虑p 外一点q 对它的影响时( 图1( b) ) , 可用下式表示:Iq ( p) = I( q) + I( q) ( p - q) ( 5)当将p 点周围所有点考虑进去时, 我们设计了一个权函数W( p, q) 来确定各点的影响程度。p 点的像素值就由选定点的像素值乘以各自的权重后相加得到, 可以用以下公式表示:I( p) =6ni = 1qBnw( p, q) I( q) + I( q) ( p- q) 6ni= 1qBnw( p, q)( 6)对W( p, q) 的设计, 将在第2. 3 节中详细介绍。2. 2 将修补过程加入到FMM中考虑到修补区域内外的特征, 改进FMM算法, 将式( 3) 简化为|T|= 1( 在边界上T = 0) ( 7 )从上式可知这相当于令速度函数F = 1, 也就是修补区域边界上各点以相同速度向内收缩, 这就保证了图像的修补顺序与手工修补图像的顺序很类似, 不会出现修补区域中一部分已修补完, 而另一部分还没开始修补的现象。这里, 我们把T 定义为像素与修补区域边界的距离函数。这样的话, T 的水平集恰恰是修补区域的边界, 而修补区域边界的法线方向则是T。在修补之前先对图像进行预处理, 对于图像中的每一点设定三个值, 即T, f 和I。其中, T是该点到修补边界的距离; I 为该点的像素值; f 为该点的标志, 可以取为Alive, Narrowband 和Faraway 三个值, 其意义如下: Alive 说明该点在修补边界外部, 是修补时利用的点, 它的T 值和I 值已知; Narrowband 说明该点在修补区域的边界上, 属于待修补的点, 其T 值和I 值正待更新; Faraway 说明该点在修补区域内部, 其T 值和I 值未知。利用FMM进行图像修补的基本思想, 即修复工作一直在待修补区域的边界上进行, 通过控制修补区域边界的向内收缩来达到修补整个区域的目的。修补过程如下:( 1) 初始化首先对要修补的图像手制工作二值模板, 要修补的区域在模板上对应位置为黑色( 像素值为0) , 不需要修补部分为白色( 像素值为1) ;对于模板图像, 若I( x, y) = 0, 说明该点在要修补的区域内, 令f( x, y) = Faraway, T( x, y) = + 若I( x, y) =1, 说明该点在要修补的区域外, 令f( x, y) = Alive, T( x, y) = 0若I( x, y) =0 且点( x, y) 的四邻域中存在点( i, j) 满足I( i, j) =1, 这说明该点为修补区域的边界上一点, 令f( x, y) = Narrowband, T( x, y) = 0将f 值为Narrowband 的像素放入一个名为Band 的栈中, 它们按照T值从小到大的顺序排列。( 2) 修补从Band 中选择具有最小T 值的点, 设为( imin, jmin) ; 对点( imin, jmin ) 利用修补算法修补, 并将其f 值改为Alive, 从Band 点集中删除;将( imin, jmin ) 的邻域点( imin - 1 , jmin ) , ( imin+ 1 , jmin) , ( imin,jmin - 1 ) , ( imin, jmin+1 ) 中f 值为Faraway 的点加入到Band 中;根据式( 4) 更新邻域点的T 值;转;当Band 中没有新的像素加入时, 说明修补区域已经填图员修补原则修补多个点边界啄赘对p 修补利用的像素Bn修补区域赘PN修补一个点qIPN充好, 结束循环。2. 3 权值的设计及分析为了保留图像的边缘特性和尽量减少模糊, 要使得模板中位置不同的各点对应权重也不同。由于把图像的修补过程设计成了修补区域边界的向内演化过程, 所以我们要综合考虑p, q 点位置, 修补区域轮廓以及q 点颜色变化等信息, 来设计各点的权重W( p, q) 。W( p, q) = dir( p, q) dst( p, q) lev( p, q) ( 8)设p 点坐标为( i, j) , q 点坐标为( i - ii, j - jj) , 则式( 8) 中的三个分量分别为dir( p, q) = ( p - q)|p - q| T( p) = 1ii2 + jj2( iig T( p)x) + ( jjg T( p)y)dst( p, q) = 1|p - q|2 = 1ii2 + jj2 ( 9)lev( p, q) =11 + |T( p) + T( q) |2这里, dir( p, q) 的作用是控制修补区域边界法线方向上的点对修补点的影响, 也就是说距离T( p) 方向近的点对p 的贡献大; dst ( p, q) 是p, q 两点之间几何距离的倒数, 这很容易理解,即在几何距离上较远的点对s 的影响相对小; lev( p, q) 描述了q 点与修补区域边界距离对p 点的影响, 也就说明了距离修补区域轮廓线越近, 对p 点的贡献越大。我们用图2 来表示三个分量的效果。在图2( a) 中, 白色环形为修补区域, 其宽度大于30 个像素。图2( c) 只用dir 分量, 图2( d) 用dir 和dst 分量, 图2( e) 用dir 和lev 分量, 图2( f)用dir, dst 和lev。图2 为四种情况的修复效果。可见, 只用dir分量时, 造成的模糊很明显; 用dir 和另外一个分量时, 模糊程度减小; 三个分量全用时效果最好。3 总结与讨论下面将设计的新修补算法同Bertalmio 等的BSCB 算法进行比较。如图3 所示, 对同一幅图( 图3( a) ) 用BSCB 和我们的算法修补, 得到的效果图如图3( b) 和图3( c) 所示, 可以看出两者的效果相差不大, 但是我们设计的算法速度要快很多。在文献 1 中, 用CPU为300MHz 的电脑修补该图要用5 分钟左右, 而本文的算法用Visual C + 编程在CPU 为1GHz 的电脑上只需3 秒左右。显然, 该算法可以节省大量时间, 提高效率。所以, 它不像现在的BSCB, TV, CDD 等算法由于太耗时经常造成电脑无响应、死机等现象, 该算法不太耗资源, 一般能将修补时间控制在5 秒之内, 所以非常适合作为图像处理软件的插件使用。参考文献: 1 arcelo Bertalmio, Guillermo Sapiro, Vicent Caselles. Image Inpainting J . SIGGRAPH, 2000, ( 1) : 417 - 424. 2 T F Chan, J Shen. Mathematical Models for Local Non-texture Inpaintings J . SIAM Journal on Applied Mathematics, 2002, 62: 1019-1043. 3 Criminisi A, Perez P, Toyama K. Objects Removal by ExemplarbasedInpainting J . IEEE Proc. CVPR, 2003, 2 : 721- 728. 4 T F Chan, J Shen. Non-Texture Inpainting by Curvature-Driven Diffusion( CDD) J . Journal of Visual Communication and Image Representation,2001, 12 : 436- 449. 5 Osher, S Sethian J. Fronts Propagating with Curvature Dependentspeed: Algorithms Based on the Hamilton-Jacobi Formulation J .Journal of Computational Physics, 1988, 79: 12- 49 . 6 Sethian J A. Fast Marching Methods J . SIAM Review, 1999, 41:199- 235 . 7 Sethian, J. A Fast Marching Level Set Method for Monotonically AdvancingFronts J . Proceedings of the National Academy of Sciences,1996 , 93: 1591-1595.参考文献: 1 laus Hansen, Jens Damgaard Andersen. Understanding the HoughTransform: Hough Cell Support and Its Utilisation J . Image andVision Computing, 1997, 15 ( 3) : 205- 218. 2 John Immerkr. Some Remarks on the Straight Line Hough Transform J . Pattern Recognition Letters, 1998, 19( 12 ) : 1133-1135. 3 H Freeman. Boundary Encoding and Processing A . B S Lipkin, ARosenfeld C . Picture Processing and Psychopictorics, Academic,New York, 1970. 241- 266. 4 顾创, 翁富良