图像快速修复技术
1. 简介
图像修复(Image Inpainting)技术，又称为图像填充(Region Filling)或物体删除(Object Removal)技术，是一种通过背景填充、替换的方法，去除图像中指定区域的算法，最终目标是达到用户难以感知感知、效果自然的图像修复。
原始图片 | 指定删除区域(白色区域) | 修复结果 |
|---|---|---|
2. 相关研究
目前经过调研，已知的部分图像修复算法及其效果如下
算法 | 原始图 | 效果图 |
|---|---|---|
纹理合成 | ||
半自动修复 | ||
搜索采样修复 | ||
深度学习 |
各算法优缺点分析
算法 | 代表算法 | 优缺点 |
|---|---|---|
纹理合成 | Image Quilting | 适合小区域修复大区域存在模糊问题 |
半自动修复 | FMM InpaintOpenCV Inpaint | 处理速度快，小区域效果很好适合老旧非数字图像修复大区域存在模糊问题 |
基于采样 | Examplar Inpainting | 适合大、小区域填充没有模糊问题适合简单背景的图像修复修复速度慢 |
深度学习 | Generative inpainting | 修复效果自然，并且可以进行人脸五官填充没有模糊问题需要大量数据集进行针对性训练不可解释性，难以调参运行速度慢，模型大 |
针对以上这些算法，结合实际移动端业务场景，本文选择基于采样的图像修复算法，并在此基础上进行优化。主要原因有如下几点
- 纹理合成和半自动修复算法都存在图像模糊问题，不适合大区域图像修复。
- 基于深度学习的算法，模型文件在20M左右，不适合打包到App端，显著增大安装包大小；其次，模型计算量较大，在PC端运行时(非GPU运行，Mac不开放GPU资源)，正常iPhone X拍摄的图片模型算法需要处理约100s，移动端处理器难以支持；最后，模型使用了TensorFlow Lite不支持的OP运算，难以移植到客户端。
综上所述，最后本文采用Examplar Based Inpainting。
3. 算法原理
3.1 关键符号简介
原理比较复杂，需要先了解一些算法关键词语及数学符号，不感兴趣的同学可以跳过。
符号 | 含义 |
|---|---|
Ω | 要修复的图像区域，Target region |
δΩ | 要修复的图像区域边界 |
Φ | 已知的原始图像区域，Source region |
p、Ψp | 边界上要修复的某一点p，及其所确定的修复区域Ψp |
q、Ψq | 原始图片内潜在的匹配点q，及其所确定的匹配区域Ψq |
通过边界上选取某一点，确定修复区域，在原始图像内寻找最匹配的采样区域，进行拷贝修复，之后更新图像边界。重复以上流程直到区域被修复完毕。
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
测试原图 | mask | 原始效果 | 时间 |
|---|---|---|---|
54秒 |
基于样本的图像修复算法，修复速度非常慢，无法满足移动端业务场景，App不能阻塞长达54秒。
Goyal等人在2010年对该算法提出了一些优化方向，参考该论文，并结合我们自身的业务场景(优先保证匹配速率，允许适当降低修复效果)，尝试以下几种优化方案。
4.1 限制匹配区域半径
原文算法为全图寻找最佳匹配区域，现调整为仅在修复区域附近寻找最佳匹配区域。
附近区域半径 | 时间(秒) | 效果 |
|---|---|---|
全图像检索 | 52.58 | 原始效果图，作为基准 |
200 | 47.81 | |
150 | 37.04 |
4.2 调整匹配滑动窗口步长
原文算法在匹配时，不仅是全图检索，并且每次检索下一个待匹配区域时，仅在x、y方向移动一个像素(称为一个step)，可以尝试一次移动多个像素。
步长Step | 时间(秒) | 效果 |
|---|---|---|
Step=1 | 52.95 | 基准，halfPatchWidth=4 |
Step=2 | 13.53 | |
Step=3 | 6.26 |
4.3 大图裁剪
Criminisi和Goyal等人两篇论文的工作主要集中在300x400小尺寸图片的修复上，而在天天P图实际业务场景中，高端iOS、Android设备拍摄的图片尺寸可达3000x4000，其图像尺寸是原始论文的100倍。原始算法直接在大分辨率图像上运行时，等待数分钟也无法得到处理结果，程序直接阻塞，因此需要进行裁剪、缩放等优化处理。
4.4 Patch区域误差度量
原始Criminisi提出的寻找最佳Patch区域，是基于L2欧氏距离(最小平方误差)，而Qiang等人提出可以基于L1欧氏距离(最小绝对值误差)。采用L1欧氏距离，可以将寻找最佳匹配区域的计算量降低10%~20%，同时对效果的影响程度较小。
原图 | mask | L2(16.3s) | L1(15.2s) |
|---|---|---|---|
4.5 小结
本文通过借鉴Goyal等人的优化措施，并结合实际业务场景，提出自己的优化方案，提升修复速率。综合上述多种优化措施，现在对原始论文中的测试图片，其运行时间可以降到1s内(原始算法1/50时间)，对业务场景中的超大尺寸图片(3000x4000)可以控制在2s左右，1000x2000可以控制在1s左右。
5. 算法效果优化
5.1 Patch融合
原始算法中，对于Patch的修补，每次仅对Patch内的未修补Target区域进行拷贝，而Patch内已知区域不做处理，而Jino等人提出了一种鲁棒性更高的算法，即对于Source区域内的点，也进行融合，融合之后可以解决部分拷贝边界线过于明显的Artifact（人工修补痕迹）问题。
原图 | mask | 非融合 | 融合 |
|---|---|---|---|
融合之后，可以发现修补区域的边界Artifact问题得到了一定程度减弱。
5.2 N Best Match
Criminisi原始算法存在一个问题，即每次仅选取一块最佳匹配区域进行复制，鲁棒性较低，容易寻找到局部次优解。一旦最佳匹配区域选择错误，则导致整个修复区域存在明显的人为修复痕迹。如下图所示，原始算法会导致左上角的黑色圆修复失败。
Alexander等人提出了一种算法，即每次选取多块最佳匹配区域(N Best Match)，将多块最佳匹配区域进行融合，提升算法鲁棒性。
原图 | mask | 非融合 | 10次融合 |
|---|---|---|---|
使用N Best Match进行融合之后，复杂纹理复制错误的问题得到了一定程度上的解决。需要注意的是，如果N选择的过大，在进行融合的时候容易将纹理细节丢失，等效于N点加权均值平滑，所以N不能设置的过大。
6. 后期工作
目前还遗留的优化点有
- 寻找最佳匹配区域可以采用多线程并行计算，提升计算速度
- 针对小区域修复，主要是用户涂抹区域较狭窄、细长时，可采用FMM算法快速修复，提升计算速度
7. 参考文献
文献 | 引用次数 |
|---|---|
Criminisi A, Pérez P, Toyama K. Region filling and object removal by exemplar-based image inpainting[J]. IEEE Transactions on image processing, 2004, 13(9): 1200-1212. | 2752 |
Telea A. An image inpainting technique based on the fast marching method[J]. Journal of graphics tools, 2004, 9(1): 23-34. | 835 |
Wong A, Orchard J. A nonlocal-means approach to exemplar-based inpainting[C]//Image Processing, 2008. ICIP 2008. 15th IEEE International Conference on. IEEE, 2008: 2600-2603. | 218 |
Cheng W H, Hsieh C W, Lin S K, et al. Robust algorithm for exemplar-based image inpainting[C]//Proceedings of International Conference on Computer Graphics, Imaging and Visualization. 2005: 64-69. | 179 |
Liu Y, Caselles V. Exemplar-based image inpainting using multiscale graph cuts[J]. IEEE transactions on image processing, 2013, 22(5): 1699-1711. | 107 |
Goyal P, Diwakar S. Fast and enhanced algorithm for exemplar based image inpainting[C]//Image and Video Technology (PSIVT), 2010 Fourth Pacific-Rim Symposium on. IEEE, 2010: 325-330. | 75 |
Lee J, Lee D K, Park R H. Robust exemplar-based inpainting algorithm using region segmentation[J]. IEEE Transactions on Consumer Electronics, 2012, 58(2). | 50 |
Chen Q, Zhang Y, Liu Y. Image inpainting with improved exemplar-based approach[M]//Multimedia Content Analysis and Mining. Springer, Berlin, Heidelberg, 2007: 242-251. | 39 |
Patel P, Prajapati A, Mishra S. Review of different inpainting algorithms[J]. International Journal of Computer Applications, 2012, 59(18). | 14 |
作者简介：daniel，天天P图 iOS 工程师
文章后记 天天P图是由腾讯公司开发的业内领先的图像处理，相机美拍的APP。欢迎扫码或搜索关注我们的微信公众号：“天天P图攻城狮”，那上面将陆续公开分享我们的技术实践，期待一起交流学习！
腾讯云开发者
