一种基于MRF 的快速图像修复算法

何 凯，沈成南，刘 坤，高圣楠

(天津大学电气自动化与信息工程学院，天津 300072)

图像修复技术是计算机视觉领域的研究热点，在文物保护、影视制作、老照片修复、目标移除等方面都得到了广泛的应用．数字图像修复技术大致可以分为2 类：①基于偏微分方程的小区域图像修复技术；②基于样本块的较大破损区域的纹理合成技术．

基于偏微分方程的图像修复，主要是利用热扩散方程来建立图像的偏微分方程，通过结合图像待修复区域附近的已知信息，按照一定的规则向待修复区域扩散，其代表算法主要有：BSCB 模型[1]，curvature driven diffusions(CDD)模型[2]，TV-Stocks 模型[3]，以及Mumford-Shah 模型[4]．

基于样本块的纹理合成，是利用图像破损区域附近完好的纹理信息，对待修复区域进行块匹配和复制，以达到图像修复的目的．纹理合成算法能够较好地解决纹理模糊问题，得到了广泛应用，其代表算法为Criminisi 算法[5]．各国学者在其基础上作了许多改进，如Siadati 等[6]利用图像的结构张量检测图像结构；Li 等[7]利用改进的全变差算法，根据破损像素和邻域像素之间的距离方向定义扩散系数，保持了图像的完整性；何凯等[8]通过改进SSIM 来衡量结构相似度，可自适应选取样本块大小，实现了图像结构的有效修复．Smith 等[9]提出利用具有互斥鉴别特性的字典对来改进稀疏形态成分分解法，能更好地提取图像的纹理和结构信息；Huang 等[10]引入了仿射变换矩阵，利用图像中的消失点和消失线等信息，实现了样本块的几何变换．此外，Newson 等[11]在变分框架下提出了一种改进的最近邻搜索算法，可以比较纹理的相似度．

传统基于样本块的纹理合成方法通常按照一定的顺序来进行修复，容易产生错误的纹理或结构传播．为此，Komodakis 等[12]提出基于MRF 的全局优化方法来解决这个问题；该方法采用优先级置信度传播(priority-belief propagation，p-BP)，即按照节点的优先级顺序，通过计算该节点与其相邻节点之间的消息值，来更新相邻节点的优先级，并根据每个节点候选块的置信度来确定最优候选块；该算法较好地解决了结构传播的问题，但算法计算量大，执行效率较低．Ruzic 等[13]在p-BP 的基础上引入了基于上下文感知的方法，并利用上下文的相似性来搜索候选块，在一定程度上改善了修复效果，但算法复杂度仍然较高．He 等[14]在MRF 的框架中利用块偏移量的统计量来解决图像修复问题．Meur 等[15]提出在不同尺度上使用MRF 框架，利用迭代的方法逐层进行修复，可在一定程度上减少置信度传播所需要的时间，但修复结果容易产生模糊现象．

本文提出了一种基于MRF 的快速图像修复算法，利用低分辨率图像的“预修复”结果，来粗略估计破损区域中MRF 内部节点的初始值，并利用改进的置信度计算公式对MRF 节点的候选块进行筛选，最后利用MRF 来确定最优匹配块．

1 传统基于MRF的图像修复算法

传统基于MRF 的图像修复模型如图1 所示，其中，源区域为φ，破损区域为Ω；与Ω有交集的块所包含的节点共同组成节点集合ζ，并由MRF 边缘ε组成一个4 邻域系统．

图1 MRF图像修复模型Fig.1 MRF-based image inpainting model

2 本文算法

传统基于MRF 的图像修复模型中，在初次迭代之前，只有部分节点(破损区域边缘附近)可以计算其初始信息；而计算其余节点与相邻节点的消息传递时，则需要遍历整幅图像中所有候选块，计算量很大．为此，本文在p-BP 算法[12]基础上，提出一种快速算法，即在初次迭代前，先对高金字塔顶层的低分辨率图像进行预处理，以获取内部节点的粗略初始值；再利用改进的置信度计算公式，以及纹理复杂度来确定候选块数量，对MRF 节点的候选块进行筛选；最后利用MRF 算法确定最优匹配块．

2.1 候选块筛选

设原始图像I为金字塔底层的高分辨率图像0G，对其进行下采样，得到顶层低分辨率图像GK，K代表金字塔层数．利用自适应样本块修复算法[8]对图像GK进行修复，得到预修复图像；由于图像GK尺寸很小，算法时间消耗很少，可近似忽略不计．对图像进行上采样，获得初始修复图像(尺寸与0G相同)．设预处理图像为I′，预处理示意图及其结果如图2 所示．

图2 预处理示意图及其结果Fig.2 Preprocessing illustration and its result

预处理图像I′可以为内部节点提供粗略的初始信息，相当于给定了消息传递之前的约束条件，有助于大大加快相邻节点间的消息传递及收敛速度．

根据预处理结果图I′，提出的改进置信度计算公式为

将节点p所有候选块的初始置信度值按降序排列，置信度最高的设为第一候选块．为了避免同一节点拥有大量相似的候选块，本文利用SSD 值对不同类别的候选块进行判别．代表块之间的相似程度，其中xN、xM分别代表第N个被选中的候选块和第M个待比较的候选块；tprune为相似度阈值，代表预定义的SSD 均值)，若则认为属于不同类别，此时保留xM为第N+1 个被选中的候选块．候选块数量L由图像本身的纹理复杂度决定，本文利用图像块直方图的2 阶矩[16]对其进行描述，即

式中Lmax表示最大候选块数量．对于内部节点，其候选块数量设为Lmax．在消息传递过程中，从节点p发送给其相邻节点q 的消息定义为

对于每一个节点p，其候选块的置信度可由式(4)定义，当所有消息值稳定或达到了预先设定的迭代次数，即可找到每一个节点候选块中置信度最大的样本块，即

2.2 算法流程

本文算法流程归纳如下．

步骤1采用自适应样本块算法[8]对高斯金字塔顶层图像进行修复，得到预处理图像I′．

步骤2计算任意节点p的初始置信度，计算节点p的候选块数量L，并利用 SSDN,M确定节点p的L个初始候选块．

步骤3计算每个节点的优先级将所有节点标记为未访问，设置迭代次数k，其中

步骤4执行前向消息传递．在未访问的节点中选取优先级最高的节点p，将其标记为已访问，计算该节点与所有相邻节点q的消息更新当前相邻节点q的置信度和优先级[12]，直至所有节点都被访问为止．

步骤5执行后向消息传递．按照步骤4 中的相反顺序，将节点p标记为未访问，再次计算节点p与其所有相邻节点q的消息更新当前相邻节点q的置信度和优先级，直至所有节点都标记为未访问．

步骤6重复步骤4、5 直至完成k次迭代；对所有节点p，利用式(9)，完成修复．

3 实验结果分析

本实验平台采用Matlab，计算机配置为CPU 处理器Core i7-6700，主频3.40 GHz，内存8.00 GB．采样过程中选用最近邻插值法，以减少预处理的时间消耗．本文图片分辨率介于240 ×160～400 ×360之间，参数选取为300 000}

将本文方法分别与p-BP 算法[12]、Meur 算法[15]和Non-Local 算法[11]进行比较；其中，p-BP 算法是在传统MRF 模型下的经典修复算法，Meur 算法是在改进MRF 框架下的多尺度超分辨率修复算法，Non-Local 算法是在变分框架下的最新改进算法．

为了对本文算法修复效果进行量化评价，选取了4 幅图像，人工标记破损区域，分别采用经典算法与本文算法进行处理，并采用峰值信噪比(PSNR)对几种算法的修复效果进行量化评估，如图3 所示．从图中可以看出，对上述几幅图像，采用本文算法进行修复，其PSNR 都高于传统算法，修复后图像视觉效果也更为合理，修复效果最佳．

图3 不同算法修复效果比较Fig.3 Comparison of different inpainting methods

为进一步分析本文算法性能，选取了2 幅具有不同纹理和结构的自然场景图像，对物体移除后图像进行修复，各种算法修复效果对比结果如图4、图5 所示．从图4 中可以看出，p-BP 算法较好地修复了水平粗栏杆，但在竖直细栏杆(红色圆圈表示)处出现了断裂；Meur 算法和Non-Local 算法在水平粗栏杆和竖直细栏杆处的修复结果产生了扭曲及断裂现象；而本文方法则比较理想地恢复了两部分的栏杆结构．将图5 中红色矩形区域放大后可以看出：p-BP 算法成功修复了灌木丛的结构，但在灰色墙壁的结构中有明显的断层；Meur 算法在修复灰色墙壁和灌木丛时均出现了模糊；Non-Local 算法合理修复了灰色墙壁的部分结构，但在墙壁和灌木丛交接处出现了结构不连续；而本文算法则有效改善了p-BP 算法中的部分断层现象，修复结果更为理想．

图4 图像“Horse”修复效果比较Fig.4 Comparison of inpainting results of the image“Horse”

图5 图像Statue”修复效果比较Fig.5 Comparison of inpainting results of the image“Statue”

表1 不同算法修复时间对比Tab.1 Comparison of different inpainting methods in terms of time

由此可以看出，与传统基于MRF 算法相比，本文算法的修复结果有了一定程度的提高，可以获得更加自然合理的修复效果．为了验证本文算法的鲁棒性，还对另外4 幅图像进行了修复，效果如图6 所示．从图6 中可以看出，对不同结构和纹理的图像，本文算法比传统算法的修复效果更为理想．

表1 列出了传统基于MRF 算法(p-BP)、Meur算法、Non-Local 算法，以及本文算法的运行时间对比结果(本文算法的运行时间包含了第2.1 节中预处理所需时间)．结合表1 和上述修复效果可以看出，p-BP 算法时间消耗过大；Meur 算法虽然大大减少了算法的时间消耗，但容易产生模糊现象；Non-Local算法的运行速度最快，但容易出现结构断层现象，修复效果不够理想；而本文算法在保证修复效果自然合理的同时，平均运行时间比p-BP 算法减少了75%以上，也少于Meur 算法，大大提高了运算效率．

图6 本文算法修复效果Fig.6 Inpainting results of the proposed method

4 结 语

本文提出了一种基于MRF 的快速图像修复算法，通过对低分辨率图像进行“预修复”来获取内部节点的粗略初始值，并利用改进的置信度计算公式对MRF 节点的候选块进行筛选，提高了所有节点交互运算的效率，有效减少了算法的时间消耗，同时，修复效果上也得到了一定程度的改善．仿真实验结果证明了本文方法的有效性．