基于改进优先权的对称相似图像修复算法

郑成松，李 琦

(福州大学 物理与信息技术学院，福建 福州 350108)

0 引言

许多艺术珍品在漫长的时间长河中会被慢慢侵蚀，图像修复是人们为了修复损坏的图像而兴起的一项技术。随着时代的变迁，数字图像修复的技术应声而出，它根据待修补区域图像的邻域信息来推算待修补区域中已损失的图像信息，进而达到修补图像的目的。数字图像修复是在2000年的一个学术会议上提出的术语。从那时起技术蓬勃发展，例如Gram-Schmidt融合算法[1]。这些图像修复的方法与手工修复相比更加快速、稳定，消耗的人力与物力大大减少。

BERTALIMIO M等人最早将高阶偏微分方程(PDE)引入图像处理中来估计等照线的方向，典型的PDE算法是BSCD模型[2]，利用三阶高阶微分方程模拟平滑传递的过程，保证了边缘的连续性。SHEN J等人提出变分(TV)模型，在修复小规模的破损方面表现良好，但是在修补区域的边界上有时不能修补得很自然[3]。CHAN T F等改进了TV模型[4]，在方程中加入了曲率，利用曲率更好地预测信息传递方向，这就是利用曲率驱动的修复模型(Curvature Driven Diffusion,CCD)。

基于纹理算法的代表之作是由CRIMINISI A[5]等人提出的。他们提出的算法是在整个图像内遍历搜索最合适匹配块，这个过程的时间消耗巨大。曾接贤等人[6]改进了基于样本块算法中置信因子的赋值方法，提高了该算法的修复效果，并较大程度地缩短了时间。Criminisi算法在处理结构相似性较大的图像时效果并不理想。因此本文针对Criminisi算法的缺点提出一种改进优先权的算法并针对对称结构的图像有更好的处理结果。

1 算法基础

Criminisi算法只包括三个步骤：计算优先级搜索最合适匹配块并填充以及更新置信度。该算法结合偏微分方程，利用图像块之间的相似，寻找最合适的匹配块并填充到相应位置，是一个比较经典的图像修复算法。算法过程如图1所示，循环该过程直至将待修复区域填充完整为止。

1.1 计算优先级

图1 Criminisi算法过程

图2 Criminisi算法符号示意图

计算优先级P(p)的公式为：

P(p)=C(p)·D(p)

(1)

其中C(p)、D(p)的计算过程如公式(2)所示：

(2)

式中|Ψp|表示样本块的数量，初始时，Φ中的C(p)值是1，Ω中的C(p)值是0，α是一个归一化的值，当图像为灰度图像的时候α的值为255。

1.2 搜索最佳样本块并填充

假设Ψp为经过计算后优先级最高的破损块，Ψq为找到的样本块，最优匹配应该满足公式(3)：

Ψq=argmin(D(Ψp,Ψq))

(3)

其中D函数为相似性度量，灰度图像可表示为:

(4)

彩色图像的计算公式与上式相差无二，计算差值时只计算RGB分量的差值即可。

1.3 更新置信度

循环一次后，原先未知的样本块已经变成确定的样本块，置信度也产生相应的变化。置信度的更新公式如下：

(5)

重复以上的步骤，直至待修复的区域面积为零，结束修复。

2 算法改进

2.1 改进优先权

Criminisi算法中的破损区域的修复顺序由优先权P(p)项决定，优先权的计算公式如式(1)所示，置信项C(p)和数据项D(p)乘积构成的。C(p)的值介于0和1之间，代表已知像素的比例，C(p)值越高，优先权越大。D(p)是等照线方向与边界方向的点积，保证了图像的修复方向是沿着等照度线的方向进行的。置信项C(p)与D(p)两项在修复过程中是一种相互制约又相互补充的关系。

C(p)在计算多次后出现了迅速下滑的情况，这导致了D(p)在优先权计算过程中发挥不了作用，效果如图3所示，因此计算出的优先权也变得不准确，将导致修补顺序的错乱。图4是采用Criminisi算法修复时，C(p)与D(p)的变化情况。可以从图4(a)中看出C(p)在200次迭代和400次迭代的时候出现了明显的下滑，接下来的数值即趋于0。再从图4(b)观察D(p)的走势，D(p)的整体比较稳定，在迭代700次左右时出现了下滑，P(p)受D(p)的影响因素较小。根本原因在于优先权的计算方式不合理，乘法运算在一项趋于0时，将直接忽视另一项的作用。文献[7]修改乘法运算为加法运算，并为D(p)与C(p)分别分配两个权重值α与β，使得P=αC(p)+βD(p)，这样D(p)项在优先权的计算中能够占到正常的权重，但是在图像结构复杂的破损区域会有断裂的情况。

图3 修复顺序错乱图

图4 置信项迅速下滑图

观察两个相同大小的待修复块，可以发现已知信息区域呈现包围情况比已知信息区域呈现半包围情况的修复效果更佳。为了更有利地获取呈包围情况的样本块，在已知像素相等的情况下，将已修复的像素q与中心位置的距离参考加入作为置信项C(p)，如此置信项的值越大说明已知像素对中心点的包围程度越大，越利于修复。重新定义得到的置信项为:

(6)

式中，n为样本块中的已知像素(除去中心点)，Distance(p，q)是已知像素点q到中心点p的棋盘距离，样本块中所有像素点的距离如图5所示。其中Distance()取得的为已知像素q点的x，y坐标与中心点的x，y坐标差值的最大值，定义为：

Dis(p,q)=max(|qi-pi|,|qj-pj|)

(7)

图5 样本块中所有像素点的距离

2.2 相似度

基于样本块的图像修复算法大都利用图像块之间的相似性。相似性分为两种，一种是正相似，另外一种是对称相似。Criminisi算法则利用图像样本块之间的正相似进行修复。正相似情况十分常见，但是对称相似的结构在图像中同样十分普遍，Criminisi等修复方法中并未有利用到图像之间的对称相似的方法。因此，本文将围绕图像的对称相似的特性，提出另外一种修复思路。

针对对称相似图像的特征，将对称相似的具体情况分析清楚，针对不同的对称相似图像需采用不同的处理方式。如水平方向的对称情况，图像的对称轴是垂直的，处理时则需将匹配图像块旋转后再与需匹配的样本块进行比较计算。这样水平方向的对称情况对于对称相似来说是一种特殊的情况，为了针对普遍的对称相似图像，需要计算出准确的图像对称相似角度之后将旋转后的图像块再与匹配块进行计算。计算准确的图像对称相似角度，循环多次，遍历整个图像区域，寻找出最合适的匹配块，会造成大量的时间消耗。本文采用的是八个方向的模板来寻找最佳的对称相似匹配块，再根据最佳匹配块的对应对称规则将纹理信息填充到待修复区域的图像块之中，按照这个规则循环直至待修复的图像区域为空为止。

为了方便快捷本文采用了八方向的对称算法。图6显示了待修复的区域块和匹配块之间的对应关系，是以3×3的图像模板为例，中间的图像块为破损的图像块，其他的八块从上到下、从左到右的关系分别表示左上方、上方、右上方、左方、右方、左下方、下方、右下方的匹配块，其中字母相同的代表像素所在的对应位置。之后根据公式(8)计算每个图像的相似度平均值，计算过程使用灰度图计算，若图像为真彩色，那便根据计算公式分别计算RGB三个颜色上的相似度值，最后再求去三个值的平均值。

(8)

其中，Ψp为破损的样本块，Ψq为匹配到的样本块，xi,j为破损块的像素值，yi0, j0为对应的匹配块处理后的像素值，处理过程类似图6的对应过程，将破损块对应的a块像素的坐标对应到匹配块的对应坐标。

图6 样本块对应规则

3 本文算法

综合上述修改，最终算法的流程如下。

(1)传入待修复的图像和确定好待修复区域范围。

(2)根据修改的置信项计算公式，更新图像置信项。

(3)利用优先级公式计算优先级，找到最高优先级的点，记为p点。

(4)以p为中心，确立破损块Ψp，根据修改的样本块匹配规则搜索最佳样本块，将样本块填入修复图像中。

(5)判断受损区域面积是否为零，是则结束算法，否则重复步骤(2)。

4 实验

本文为了验证算法的实践效果，在内存4 GB、处理器为i5-3210M、CPU主频为2.5 GHz的计算机上进行实验，通过实验得出的效果如图7～图9所示。

图7 对称相似图像图像修复效果

图8 去除骑手的修复效果

图9 移除人物图片

图7中，图(a)是将屋檐的一角移除作为待修复区域进行实验，图(b)为Criminisi的算法结果，因为只能搜索正相似的样本块，所以无法对这种对称结构的图片进行较好的修复。其中屋檐的结构是对称的，该算法在搜索到正相似中最为合适的样本块后填充，无法找到对称的另外一个屋檐样本块进行处理后填充，导致错误的样本块持续迭代而出现图(b)的效果。本文算法使用对称相似进行匹配样本块，最终效果比较理想。

图8的图像结构比较复杂，去除图中的骑手作为破损区域为实验，图(b)中的修复结果在草地上出现了些许栏杆处的样本块。本文在修改图像修复的优先权后，对图像沿着等照线的方向传递信息的准确度有所提高，达到了实验的预期效果。

图9是比较常规的图像，可以看出Criminisi算法的处理结果已达到一定效果，但是在中间房屋边缘的连续问题的处理上不够理想，本文算法虽不完美，但较前者也有一定提升。

表1是Criminisi算法与本文算法对各图的算法运行时间对比。从表格中可以看出本文在计算效率上略有逊色，原因在于本文在样本块匹配过程中消耗了较多的时间，但相应地在修复的效果上有较好的提升。

表1 算法运行时间比较 (s)

5 结论

本文的算法基础是Criminisi的基于样本块的修复方法，针对该算法存在的沿等照线传递信息方向错乱、只匹配正相似的问题提出了修改方法，并进行了实验验证。实验结果表明，本文的修复方法可以做出更好的视觉效果。但在针对图像上的适应性和运行效率上还有待提高。