图像快速修复技术

1. 简介

图像修复(Image Inpainting)技术，又称为图像填充(Region Filling)或物体删除(Object Removal)技术，是一种通过背景填充、替换的方法，去除图像中指定区域的算法，最终目标是达到用户难以感知感知、效果自然的图像修复。

2. 相关研究

目前经过调研，已知的部分图像修复算法及其效果如下

各算法优缺点分析

针对以上这些算法，结合实际移动端业务场景，本文选择基于采样的图像修复算法，并在此基础上进行优化。主要原因有如下几点

• 纹理合成和半自动修复算法都存在图像模糊问题，不适合大区域图像修复。
• 基于深度学习的算法，模型文件在20M左右，不适合打包到App端，显著增大安装包大小；其次，模型计算量较大，在PC端运行时(非GPU运行，Mac不开放GPU资源)，正常iPhone X拍摄的图片模型算法需要处理约100s，移动端处理器难以支持；最后，模型使用了TensorFlow Lite不支持的OP运算，难以移植到客户端。

综上所述，最后本文采用Examplar Based Inpainting。

3. 算法原理

3.1 关键符号简介

原理比较复杂，需要先了解一些算法关键词语及数学符号，不感兴趣的同学可以跳过。

通过边界上选取某一点，确定修复区域，在原始图像内寻找最匹配的采样区域，进行拷贝修复，之后更新图像边界。重复以上流程直到区域被修复完毕。

3.2 修复顺序

基于采样的修复算法，其核心思想是提出一种图像修复顺序的算法，主要是修复顺序会严重影响修复结果，传统基于Onion Peel，由外向内的修复顺序的容易导致图像边界模糊。

Criminisi等人提出了一种基于置信度(Confidence)和数据项(Data Term)的方法，计算边界点的修复优先级。

P(p) = C(p) * D(p)

其中P(p)表示一个point像素点的修复优先级，C(p)表示该点的Confidence，D(p)表示该点的Data Term。

C(p)的含义是，修复区域内有多少像素点是属于已修复图像区域。

D(p)的含义是，该点边界法线np方向与梯度方向的偏差。

图a：C(p)，绿色区域表示高Confidence修复区域，红色区域表示低Confidence修复区域。

图b：D(p)，绿色区域表示高Data Term修复区域。

可以看出，Confidence偏向优先修复“突出区域”，偏向于将Target region修成圆形，然后按照同心圆进行修复；而Data Term偏向优先修复“边界区域”，即优先修复高频、复杂纹理区域，保留边界信息，避免出现修复后的图像模糊。

3.3 最佳匹配区域

已经确定边界修复的优先级，如何在原始图像区域内寻找最佳匹配区域？Criminisi等人提出一种基于最小SSD(sum of squared differences)的方法。

通过计算修复区域Ψp和原始图像Ψq的像素值平方误差，在原始图像中寻找最小误差区域。像素误差可以用RGB的几何距离衡量，但原文中推荐使用CIE Lab Colour进行距离衡量。

3.4 算法流程

综上所述，该算法的主要流程是

• 提取修复区域边界
• 确定边界点的修复顺序
• 寻找最佳匹配区域，进行修复
• 更新边界，更新Confidence、Data Term
• 重复步骤一，直到全部区域修复完成

4. 算法速度优化

测试环境：iMac 2017，4.2 GHz Intel Core i7，CPU环境单线程运行

测试图片：尺寸302x402

基于样本的图像修复算法，修复速度非常慢，无法满足移动端业务场景，App不能阻塞长达54秒。

Goyal等人在2010年对该算法提出了一些优化方向，参考该论文，并结合我们自身的业务场景(优先保证匹配速率，允许适当降低修复效果)，尝试以下几种优化方案。

4.1 限制匹配区域半径

原文算法为全图寻找最佳匹配区域，现调整为仅在修复区域附近寻找最佳匹配区域。

4.2 调整匹配滑动窗口步长

原文算法在匹配时，不仅是全图检索，并且每次检索下一个待匹配区域时，仅在x、y方向移动一个像素(称为一个step)，可以尝试一次移动多个像素。

4.3 大图裁剪

Criminisi和Goyal等人两篇论文的工作主要集中在300x400小尺寸图片的修复上，而在天天P图实际业务场景中，高端iOS、Android设备拍摄的图片尺寸可达3000x4000，其图像尺寸是原始论文的100倍。原始算法直接在大分辨率图像上运行时，等待数分钟也无法得到处理结果，程序直接阻塞，因此需要进行裁剪、缩放等优化处理。

4.4 Patch区域误差度量

原始Criminisi提出的寻找最佳Patch区域，是基于L2欧氏距离(最小平方误差)，而Qiang等人提出可以基于L1欧氏距离(最小绝对值误差)。采用L1欧氏距离，可以将寻找最佳匹配区域的计算量降低10%~20%，同时对效果的影响程度较小。

4.5 小结

本文通过借鉴Goyal等人的优化措施，并结合实际业务场景，提出自己的优化方案，提升修复速率。综合上述多种优化措施，现在对原始论文中的测试图片，其运行时间可以降到1s内(原始算法1/50时间)，对业务场景中的超大尺寸图片(3000x4000)可以控制在2s左右，1000x2000可以控制在1s左右。

5. 算法效果优化

5.1 Patch融合

原始算法中，对于Patch的修补，每次仅对Patch内的未修补Target区域进行拷贝，而Patch内已知区域不做处理，而Jino等人提出了一种鲁棒性更高的算法，即对于Source区域内的点，也进行融合，融合之后可以解决部分拷贝边界线过于明显的Artifact（人工修补痕迹）问题。

融合之后，可以发现修补区域的边界Artifact问题得到了一定程度减弱。

5.2 N Best Match

Criminisi原始算法存在一个问题，即每次仅选取一块最佳匹配区域进行复制，鲁棒性较低，容易寻找到局部次优解。一旦最佳匹配区域选择错误，则导致整个修复区域存在明显的人为修复痕迹。如下图所示，原始算法会导致左上角的黑色圆修复失败。

Alexander等人提出了一种算法，即每次选取多块最佳匹配区域(N Best Match)，将多块最佳匹配区域进行融合，提升算法鲁棒性。

使用N Best Match进行融合之后，复杂纹理复制错误的问题得到了一定程度上的解决。需要注意的是，如果N选择的过大，在进行融合的时候容易将纹理细节丢失，等效于N点加权均值平滑，所以N不能设置的过大。

6. 后期工作

目前还遗留的优化点有

• 寻找最佳匹配区域可以采用多线程并行计算，提升计算速度
• 针对小区域修复，主要是用户涂抹区域较狭窄、细长时，可采用FMM算法快速修复，提升计算速度

7. 参考文献

作者简介：daniel，天天P图 iOS 工程师

文章后记 天天P图是由腾讯公司开发的业内领先的图像处理，相机美拍的APP。欢迎扫码或搜索关注我们的微信公众号：“天天P图攻城狮”，那上面将陆续公开分享我们的技术实践，期待一起交流学习！