发布时间: 2018-09-16 摘要点击次数: 全文下载次数: DOI: 10.11834/jig.180006 2018 | Volume 23 | Number 9 图像处理和编码

1. 西南交通大学信息科学与技术学院, 成都 610031;
2. 西藏大学工学院, 拉萨 850000
 收稿日期: 2018-01-18; 修回日期: 2018-04-04 基金项目: 国家自然科学基金项目（61461048）；西藏自治区科技厅科技计划重点项目（Z2013B28G28/02） 第一作者简介: 王心怡, 1994年生, 女, 西南交通大学计算机科学与技术专业在读硕士研究生, 主要研究方向为数字图像修复。E-mail:xinyiwangsc@qq.com. 中图法分类号: TP305.6 文献标识码: A 文章编号: 1006-8961(2018)09-1293-12

# 关键词

Image completion method with irregular patch
Wang Xinyi1, Zhai Donghai1,2
1. School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China;
2. School of Engineering, Tibet University, Lhasa 850000, China
Supported by: National Natural Science Foundation of China(61461048)

# Abstract

Objective The highlight and difficult point of the current research in terms of image completion is to complete the image of a large damaged region with complex structure and rich texture information. Traditional exemplar-based completion algorithms mainly adapt the regular sample and matching patches to complete the damaged region. During the completion process, the irregular information, especially the local irregular information, of the image structure and texture cannot be fully used. This condition affects the accuracy and efficiency of the algorithm. To solve this problem, an image completion method with irregular patch is proposed in this paper. Method In our approach, the structure sparsity is used to distinguish the structure information and texture information of the input image first. Thus, a patch with a structure sparsity higher than a threshold is marked as a structural patch, and a patch with a structure sparsity lower than a threshold is regarded as a texture patch. Moreover, the patch priority of pixels on the boundary of the damaged region is calculated on the basis of the structure sparsity and confidence terms. Then, the pixel of the highest priority is selected as the center of the sample patch. If the neighborhood of a sample patch, which is in the complex structure area of the image, contains the known structure information, then this regular patch is dilated to construct its corresponding irregular sample patch by using structure information in its neighborhood. Then, the matching patch is being searched in the known part of the image. If the neighborhood of this matching patch contains a valid structure information, then the matching patch is dilated, and the structure information in its neighborhood is supplemented to construct its corresponding irregular matching patch. Finally, this irregular matching patch is used to complete its corresponding damaged region. The steps of constructing irregular patches specifically include transforming the inspection patch into the grayscale patch, using Gaussian blurring to denoise, extracting the structural information by using the Canny operator, integrating the structural information and original image patch to form an irregular mask, and picking the mask into the source image to obtain the irregular patch. In terms of the problem of visual disconnectivity, which is caused by seams during the completion process, the texture information of the image is used for modification in the proposed algorithm. The specific method aims to map the overlapping region of the texture patches into a network, and then, the graph cut algorithm is used to cut the network to generate a new optimal seam. Result Our approach and four other completion algorithms, three of which are based on the regular patch and one is based on sensitive hash, are used to complete eight classic image benchmarks. The efforts of these algorithms are evaluated by objective and subjective evaluation, which are the peak signal-to-noise ratio (PSNR) and visual connectivity. In comparison with these four completion algorithms, the results show that the proposed algorithm can achieve a better result in the fineness of the completion as well as the visual connectivity. Moreover, the PSNR of the proposed algorithm is improved by 0 dB to 4 dB. Conclusion The proposed algorithm improves the traditional exemplar-based completion algorithms, which cannot fully use the image irregularity information, and enhances the accuracy. Simultaneously, the texture information of the image is used to modify the visual disconnectivity so the visual effect of the image is improved. The proposed algorithm has a good application in the restoration of damaged natural images and cultural relics with both geometric structure and rich texture as well as the removal of target objects. Thus, the proposed algorithm is generalizable.

# Key words

image completion; structure sparsity; irregular patch; seam rectify; local consistency; adaptivity

# 1 基于块结构稀疏度计算优先级

 ${\mathit{\boldsymbol{N}}_s}\left( p \right) = \left\{ {{p_j}:{p_j} \in N\left( p \right),{\mathit{\Psi }_{{p_j}}} \in \bar \Omega } \right\}$ (1)

 $\rho \left( p \right) = \sqrt {\left[ {\sum\limits_{{p_j} \in {N_s}\left( p \right)} {W_{p,{p_j}}^2} } \right] \cdot \frac{{\left| {{N_s}\left( p \right)} \right|}}{{\left| {N\left( p \right)} \right|}}}$ (3)

 $P\left( p \right) = S\left( p \right) \times C\left( p \right)$ (4)

 $C\left( p \right) = \frac{{\sum\limits_{q \in {\mathit{\Psi }_p} \cap \bar \Omega } {C\left( q \right)} }}{{\left| {{\mathit{\Psi }_p}} \right|}}$ (5)

# 2 构造不规则块

 $\left\{ \begin{array}{l} {\mathit{\boldsymbol{H}}_{\rm{S}}} = \left\{ {{\mathit{\Psi }_p}\left| {S\left( p \right) \ge T} \right.,p \in \partial \mathit{\Omega }} \right\}\\ {\mathit{\boldsymbol{H}}_{\rm{T}}} = \left\{ {{\mathit{\Psi }_p}\left| {S\left( p \right) < T} \right.,p \in \partial \mathit{\Omega }} \right\} \end{array} \right.$ (6)

1) 在待修复块${\mathit{\Psi }_p}$上覆盖一块面积略大于其自身的正方形检测块${{\mathit{\Psi '}}_p}$，如图 2(a)(2)中蓝色虚线方形区域(也可以视作将待修复块进行膨胀处理)，该检测块的面积为原待修复块${\mathit{\Psi }_p}$$\alpha 倍(本文中通过实验统计得知\alpha =1.5效果最好)。 2) 将彩色的检测块{{\mathit{\Psi '}}_p}的完好部分转化为灰度图像，然后对其做高斯模糊化处理进行去噪(如图 2(b)(3)所示)，再利用Canny边缘检测算法[17]提取模糊化处理后的检测块{{\mathit{\Psi '}}_p}完好部分的结构信息(如图 2(b)(4)所示)。值得注意的是，图 2\mathit{\Omega }表示破损区域，不参与不规则块的构造，不需要对其进行以上处理。 3) 通过将检测块{{\mathit{\Psi '}}_p}中的结构信息与待修复块{\mathit{\Psi }_p}进行合成，也就是把图 2(b)(4)中的白色结构区域(不包括破损区域\mathit{\Omega })和规则块{\mathit{\Psi }_p}合并，来构造不规则的块掩膜M(如图 2(c)(5)中红框所示)。 4) 将块掩膜M覆盖在源图上以得到新的不规则待修复块{{\mathit{\Psi ''}}_p}(如图 2(c)(6)所示)。 # 2.1.2 构造不规则的匹配块 通过上述步骤取得不规则待修复块{{\mathit{\Psi ''}}_p}后，需利用基于PatchMatch方法来快速搜索其最佳匹配块，详情请见第3节。然后根据匹配块邻域的结构信息来重新构造不规则的匹配块来修复破损区域，构造过程类似于不规则待修复块的构造过程，具体如下: 1) 在找到的最佳匹配块{\mathit{\Psi }_q} (如图 3(a)(1)绿色方框所示)上覆盖一块面积略大于其自身的正方形检测块{{\mathit{\Psi '}}_q} (如图 3(a)(2)蓝色虚线方框所示)，该检测块的面积为原最佳匹配块{\mathit{\Psi }_q}$$\alpha$倍(本文中通过实验统计得知$\alpha$=1.5效果最好)。

2) 将彩色的检测块${{\mathit{\Psi '}}_q}$转化为灰度图像，然后对其做高斯模糊化处理进行去噪(如图 3(b)(3)所示)，再利用Canny边缘检测算法[17]提取模糊化处理后的检测块${{\mathit{\Psi '}}_q}$的结构信息(如图 3(b)(4)所示)。

3) 通过将最佳匹配块${\mathit{\Psi }_q}$与检测块${{\mathit{\Psi '}}_q}$中的结构信息进行合成，也就是把图 3(b)(4)中的白色结构区域和匹配块${\mathit{\Psi }_q}$相并，来构造不规则的块掩膜$M$(如图 3(c)(5)绿框所示)。

4) 将块掩膜$M$覆盖在源图上以得到新的不规则最佳匹配块${{\mathit{\Psi ''}}_q}$(如图 3(c)(6)所示)。

# 2.2 构造不规则纹理块

 $\begin{array}{*{20}{c}} {M\left( {s,t,A,B} \right) = }\\ {\left\| {A\left( s \right) - B\left( s \right)} \right\| + \left\| {A\left( t \right) - B\left( t \right)} \right\|} \end{array}$ (7)

 $cut\left( {s,t,A,B} \right) = \sum\limits_{s,t \in o\left( {A,B} \right)} {M\left( {s,t,A,B} \right)}$ (8)

$cut$值越小，说明被切割开的节点间的相似度之和越小，同一区域内的节点相似度越大，映射到图像中切割开的新的接缝两侧区域给人造成的视觉差异越不明显，一定程度上保证了图像的视觉连通性，达到了接缝修饰的目的。

# 3 搜索方式

 ${u_i} = {v_0} + w{\alpha ^i}{R_i}$ (9)

 $W\left( q \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 1\\ {{\rm{e}}^{ - \frac{{dist\left( {q,\partial {\mathit{\Omega }_{{\rm{org}}}}} \right)}}{{2{\sigma ^2}}}}} \end{array}&\begin{array}{l} q \in {{\mathit{\bar \Omega }}_{{\rm{org}}}}\\ q \in \mathit{\bar \Omega } - {{\mathit{\bar \Omega }}_{{\rm{org}}}} \end{array} \end{array}} \right.$ (10)

# 5 实例验证

Table 1 Comparison of PSNR results among five inpainting algorithms

 算法 图 6 图 7 图 8 图 9 图 10 文献[12] 36.170 9 27.788 3 36.837 9 33.305 7 32.296 3 文献[16] 36.403 4 27.887 6 36.247 5 33.912 6 32.276 8 文献[21] 33.469 8 27.278 8 36.682 3 33.003 8 32.388 1 文献[23] 32.452 8 24.845 1 32.348 3 31.680 3 34.345 6 本文 36.618 1 28.358 6 37.329 2 34.146 4 34.878 2 注：加粗字体表示最优结果。

PSNR是最大值信号和背景噪声之间的比率，可以衡量经处理后图像的品质。表 1中用PSNR来量化5种算法的修复结果，其对应的柱状图如图 11所示，可以看出，本文算法对图 610(图 1214为目标移除，其PSNR值没有意义)中存在不同程度破损的图像修复后计算得到的PSNR均为最大，表明修复效果最优，同时也符合人的主观视觉判断。

# 参考文献

• [1] Zhang H Y, Peng Q C. A survey on digital image inpainting[J]. Journal of Image and Graphics, 2007, 12(1): 1–10. [张红英, 彭启琮. 数字图像修复技术综述[J]. 中国图象图形学报, 2007, 12(1): 1–10. ] [DOI:10.3969/j.issn.1006-8961.2007.01.001]
• [2] Bertalmio M, Sapiro G, Caselles V, et al. Image inpainting[C]//Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 2000: 417-424. [DOI:10.1145/344779.344972]
• [3] Chan T F, Shen J H. Mathematical models for local nontexture inpaintings[J]. SIAM Journal on Applied Mathematics, 2002, 62(3): 1019–1043. [DOI:10.1137/S0036139900368844]
• [4] Chan T F, Shen J H. Nontexture inpainting by curvature-driven diffusions[J]. Journal of Visual Communication and Image Representation, 2001, 12(4): 436–449. [DOI:10.1006/jvci.2001.0487]
• [5] Tsai A, Yezzi A, Willsky A S. Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification[J]. IEEE Transactions on Image Processing, 2001, 10(8): 1169–1186. [DOI:10.1109/83.935033]
• [6] Drori I, Cohen-Or D, Yeshurun H. Fragment-based image completion[J]. ACM Transactions on Graphics, 2003, 22(3): 303–312. [DOI:10.1145/1201775.882267]
• [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. [DOI:10.1109/tip.2004.833105]
• [8] Kwatra V, Essa I, Bobick A, et al. Texture optimization for example-based synthesis[J]. ACM Transactions on Graphics, 2005, 24(3): 795–802. [DOI:10.1145/1186822.1073263]
• [9] Kuo T Y, Su P C, Kuan Y P. SIFT-guided multi-resolution video inpainting with innovative scheduling mechanism and irregular patch matching[J]. Information Sciences, 2016, 373: 95–109. [DOI:10.1016/j.ins.2016.08.091]
• [10] Sun J, Yuan L, Jia J Y, et al. Image completion with structure propagation[C]//Proceeding SIGGRAPH '05 ACM SIGGRAPH 2005 Papers. Los Angeles, California: ACM Press, 2005: 861-868. [DOI:10.1145/1073204.1073274]
• [11] Tang C W, Hu X, Chen L, et al. Sample-based image completion using structure synthesis[C]//Proceedings of the 20th IEEE International Conference on Image Processing. Melbourne, VIC, Australia: IEEE, 2013: 1336-1340. [DOI:10.1109/icip.2013.6738275]
• [12] Wang M, Zhai D H, Nie H Y, et al. Image inpainting with weight variation of neighborhood window[J]. Journal of Image and Graphics, 2015, 20(8): 1000–1007. [王猛, 翟东海, 聂洪玉, 等. 邻域窗口权重变分的图像修复[J]. 中国图象图形学报, 2015, 20(8): 1000–1007. ] [DOI:10.11834/jig.20150802]
• [13] Zeng J X, Wang C. Image completion based on redefined priority and image division[J]. Journal of Image and Graphics, 2017, 22(9): 1183–1193. [曾接贤, 王璨. 基于优先权改进和块划分的图像修复[J]. 中国图象图形学报, 2017, 22(9): 1183–1193. ] [DOI:10.11834/jig.170054]
• [14] Mairal J, Elad M, Sapiro G. Sparse representation for color image restoration[J]. IEEE Transactions on Image Processing, 2008, 17(1): 53–69. [DOI:10.1109/TIP.2007.911828]
• [15] Shen B, Hu W, Zhang Y M, et al. Image inpainting via sparse representation[C]//IEEE International Conference on Acoustics, Speech and Signal Processing. Taipei, Taiwan: IEEE, 2009: 697-700. [DOI:10.1109/icassp.2009.4959679]
• [16] Xu Z B, Sun J. Image inpainting by patch propagation using patch sparsity[J]. IEEE Transactions on Image Processing, 2010, 19(5): 1153–1165. [DOI:10.1109/tip.2010.2042098]
• [17] Canny J. A computational approach to edge detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986, PAMI-8(6): 679–698. [DOI:10.1109/TPAMI.1986.4767851]
• [18] Kwatra V, Essa I, Turk G, et al. Graphcut textures: image and video synthesis using graph cuts[C]//Proceedings SIGGRAPH'03. San Diego, California: ACM, 2003: 277-286. [DOI:10.1145/1201775.882264]
• [19] Greig D M, Porteous B T, Seheult A H. Exact Maximum A Posteriori Estimation for Binary Images[J]. Journal of the Royal Statistical Society, 1989, 51(2): 271–279.
• [20] Boykov Y, Kolmogorov V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(9): 1124–1137. [DOI:10.1109/TPAMI.2004.60]
• [21] Barnes C, Shechtman E, Finkelstein A, et al. PatchMatch:a randomized correspondence algorithm for structural image editing[J]. ACM Transactions on Graphics, 2009, 28(3): 24. [DOI:10.1145/1531326.1531330]
• [22] Shih T K, Chang R C, Lu L C, et al. Adaptive digital image inpainting[C]//Proceedings of the 18th International Conference on Advanced Information Networking and Applications. Fukuoka, Japan: IEEE Computer Society, 2004: 71-76. [ DOI:10.1109/AINA.2004.1283890]
• [23] Patil B C, Mahajan P K J. Image inpainting using coherent sensitive hashing[J]. International Journal of Advance Engineering and Research Development, 2015, 2(10): 47–51. [DOI:10.21090/ijaerd.02109]