针对基于样本的图像修复算法，在修复破损区域周围既包含较丰富的纹理信息又包含较丰富的几何结构信息时，由于不能很好地区分破损图像的纹理信息和几何结构信息而造成纹理错误延伸，致使修复结果出现结构断裂的问题。本文将图像的先验知识和轮廓特征以合理地方式引入到图像修复过程中，并以PatchMatch算法和Criminisi算法为例，提出了两种改进算法：
      首先，针对PatchMatch算法采用随机的方式来初始化图像的偏移映射以及利用相似最近邻的传播方式所造成的误匹配问题，本文将图像的纹理信息和几何结构信息等图像先验知识引入到PatchMatch算法对图像偏移映射的初始化中，将原算法的随机初始化改进为在图像先验知识约束下初始化，并引入能够区分图像几何结构信息和纹理信息的相似性度量公式来测量两个图像块之间的相似性，以提高算法的匹配精度。同时，引入相似块统计特性来裁剪用于修复的样本标签，以降低由于计算图像先验知识约束而造成的算法运算量增大的问题，提高算法的运行效率。最后，将梯度因子引入到算法的平滑项中以提高算法对结构信息敏感度，使得修复结果具有更好的结构一致性。
       其次，针对基于样本的修复算法在保持图像结构一致性方面有所欠缺，本文对基于轮廓重构的修复算法进行了改进。该改进以图像的全局自相似性的图像先验知识为依据，充分分析和利用图像轮廓特征来指导破损区域的轮廓重构，以恢复破损区域的轮廓信息，使得修复结果更好地满足视觉一致性。与此同时，引入轮廓丰富度来改进Criminisi算法的优先权，以保证破损区域边缘处的结构信息以合理的方式传播到破损区域内部。在样本块的搜索匹配方面，本文利用图像的轮廓信息来约束匹配块的搜索范围以提高算法的匹配精度。
       最后，通过仿真实验结果表明，在主观评价指标上，本文提出的改进算法修复效果相比于其它同类改进算法更能满足人类的视觉连通性要求。在客观评价指标上，本文提出的改进算法相比于其它同类改进算法具有更高的峰值信噪比PSNR（Peak Signal - to - Noise Ratio）和更大的结构相似性SSIM（Structural Similarity）

       When the damaged area of the image contains both rich texture information and geometric structure information, if the texture is incorrectly extended due to the texture information and geometric structure information of the damaged image can’t be properly distinguished by using exemplar based algorithm. The repair result will be structurally fractured. To solve the problems, two improved methods of PatchMatch algorithm and Criminisi algorithm are proposed, in this thesis, that are based on the prior knowledge and contour features of the repaired image.
      Firstly, in order to slove the mis-matching problems of the PatchMatch algorithm that caused by using random methods to initialize image offset mapping and emploing approximate nearest-neighbor propagation modes. The image prior information such as texture information and geometric structure information is introduced into the PatchMatch algorithm for initializing of the image offset mapping. The random initialization method of the PatchMatch algorithm is improved by using the image prior knowledge constraint. Furthermore, in order to improve the matching accuracy of the PatchMatch algorithm, a similarity measure formula that can distinguish image geometry information and texture information is used to measure the similarity of two image patches. To reduce the computational complexity of the proposed algorithm, the statistical acteristics of similar patches is introduced to cut the sample tags that are used for repairing demange image. At last, gradient factor is introduced into the smoothing term of the algorithm to improve the sensitivity of the algorithm to structural information.
         Secondly, for the purpose of solving the defect of the exemplar-based algorithm in the consistency of the image structure, an improved contour reconstruction algorithms is proposed for reconstructing the contour information of the damaged area based on the global self-similarity of image. The contour features of the image are used to guide the contour reconstruction of the damaged area in the proposed algorithm for improving the visual consistency of repaired results. The contour information is introduced to improve the priority of Criminisi algorithm for ensuring the propagation of structural information from the edge of the damaged area to the inside. For matching the sample patch, the matching accuracy of the algorithm can be improved by constraining the search range of the matching patch based on the contour information of the image.
        Finally, the simulation results show that the repaired effect of the proposed algorithm has a higher peak signal-to-noise ratio (PSNR) and structural similarity (SSIM) compared to other similar improved algorithms. Therefore, the visual connectivity requirements of human beings can be satisfied by adopting the proposed algorithm.。

[1] Bertalmio M, Sapiro G, Caselleset V et al. Image inpainting[C], Proceedings of the 27th annual conference on Computer graphics and interactive techniques, New Orleans, 2000, 417-424.

[2] Christine Guillemot, Olivier Le Meur. Image Inpainting：Overview and Recent Advances [J]. IEEE Signal Processing Magazine,2014,31(1):127-144.

[3] Telea A. An image inpainting technique based on the fast marching method[J]. Journals of Graphics Tools, 2004,9(1): 25–36.

[4] Chan T, Shen J. Local inpainting models and TV inpainting [J] SIAM Journal on Applied Mathematics, 2001, 62(3):1019–1043.

[5] L Rudin, S Osher, E Fatemi.Nonlinear total variation based noise removal algorithms [C]. Proceedings of the eleventh annual international conference of the Center for Nonlinear Studies on Experimental mathematics, Los Alamos, New Mexico, USA,1992, 60(1-4): 259–268.

[6] Chan T, Shen J. Non texture inpainting by curvature-driven diffusion[J]. Visual Commun. Image Representation, 2001,12(4):436–449.

[7] Chan T, Kang S, Shen J.Euler’s elastica and curvature-based inpainting[J].SIAM Journal on Applied Mathematics, 2003,63(2):564–592.

[8] A Tsai, A Yezzi Jr, A S Willsky. Curve evolution implementation of theMumford-Shah functional for image segmentation,denoising,interpolation, andmagnification[J]. IEEE Transactions Image Processing, 2001,10(8): 1169-1186.

[9] Mumford D, Shah J. Optimal approximations by piecewise smooth functions and associat-ed variational problems[J].Communications on Pureand Applied Mathematics,1989,42(5):

577-685.

[10] 赵颜伟, 李象霖 . 一种基于TV模型的快速图像修复算法[J].微电子学报与计算机2009, 26(2): 253-260.

[11] Peiying Chen, Yuandi Wang. Fourth order partial differential equations forimage inpainting[C].International Conference on Audio,Language and Image Processing, ICALIP, Shanghai, China ,2008:1713-1717.

[12] Zhongyu Xu, Xiaoli Lian, Lili Feng. Image Inpainting Algorithm Based on Partial Differential Equation[A].In:Proceedings of ISECS International Colloquium on Comput-ing,Communication,Control,and Management.2008,1:120- 124.

[13] 周廷方, 汤锋, 王进等. 基于径向基函数的图像修复技术[J].中国图象图形学报，2004,9(10):1190-1196.

[14] 邵肖伟, 刘政凯, 宋璧. 一种基于TV模型的自适应图像修复方法[J].电路与系统学报,2004,9(20):113-117.

[15] A Efros, T. Leung. Texture synthesis by non-parametric sampling[C]. In Proceedings of the International Conference on Computer Vision (ICCV), Washington, DC, USA. 1999: 1033–1038.

[16] K M He, J Sun. Image Completion Approaches Using the Statistics of Similar Patches [J] IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(12):2423- 2435.

[17] A Criminisi, P Pérez, K Toyama. Region filling and object removal by examplar-based inpainting[J].IEEE Transactions on Image Processing, 2004,13(9):1200–1212.

[18] Z B Xu, J Sun. Image inpainting by patch propagation using patch sparsity[J]. IEEE Tran-sactions on Image Processing, 2010,19(5):1153–1165.

[19] O Le Meur, J Gautier, C Guillemot. Examplar-based inpainting based on local geometry [C]. In Process IEEE Internal Conference on Image Processing (ICIP), Bangalore, karnat -aka, India .2011:3401–3404.

[20] Y Wexler, E Shechtman, M Irani. Space-time video completion[C]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), Washington, D.C., USA 2004 ,1:120–127.

[21] 任澎, 唐向宏, 康佳伦. 利用纹理和边缘特征Criminisi改进算法[J].中国图象图形学报, 2012, 17(9):1085-1091.

[22] Sun J, Yuan J. Image completion with structure propagation[C]. ACM SIGGRAPH Conference on Computer Graphics, Los Angeles, California, 2005, ACM SIGGRAPH, 2005:861-868.

[23] 李志丹, 和红杰, 尹忠科等. 基于 Curvelet 方向特征的样本块图像修复算法[J]. 电子学报,2016, 44(1): 150-154.

[24] 王猛, 翟东海, 聂洪玉等. 邻域窗口权重变分的图像修复[J]. 中国图象图形学报, 2015,20(8): 1000-1007.

[25] Cao F, Gousseau Y, Masnou S. Geometrically guided exemplar-based inpainting[J]. SIAM Journal on Imaging Sciences, 2011, 4(4): 1143-1170.

[26] Jia-Bin Huang, Sing Bing Kang, Narendra Ahuja etl.Image Completion using Planar Structure Guidance[J] ACM Transactions on Graphics (TOG) - Proceedings of ACM SI-GGRAPH 2014 , 33 (4) :1-10.

[27] Soomin Kim, Taeyoung Kim, Min H Kim, etal.Image Completion with Intrinsic Reflectance Guidance[C] British Machine Vision Conference, London, England,2017.

[28] Joo Ho Lee, Inchang Choi, Min H Kim.Laplacian Patch-Based Image Synthesis[C] IEEE Conference on Computer Vision and Pattern Recognition, Las Vegas,NV,USA 2016: 2727-2735.

[29] 孟春芝, 何凯, 焦青兰. 自适应样本块大小的图像修复方法[J].中国图像图形学报, 2012, 17(3):337-341.

[30] 李晋江, 张彩明, 范辉. 基于分形的图像修复算法[J].电子学报,2010,38(10):2430 - 2436.

[31] Nikos Komodakis. Image completion using global optimization[C]. IEEE Conference on Computer Vision and Pattern Recognition,Washington, DC, USA, 2006,1(1):442-452.

[32] Komodakis N, Tzirhas G. Image completion using efficient belief propagation via priority scheduling and dynamic pruning[J]. IEEE Transactions on Image Processing, 2007, 16 (11): 2649-2661.

[33] Pritch Y, Peleg S. Shift-map image editing[C]. The IEEE International Conference on Computer Vision, Kyoto, Japanese, 2009: 151-158.

[34] C Barnes, E Shechtman, A Finkelstein, etal. Patchmatch: A randomized correspondence algorithm for structural image editing[J]. ACM Transactions on Graphics-TOG 2009,28 (3):1-11.

[35] Taeg Sang Cho, Moshe Butman, Shai Avidan.The patch transform and its applications to image editing[C] IEEE Conference on Computer Vision and Pattern Recognition, Anch-orage, AK, USA, 2008,32(3):1-8.

[36] Yang Y, Zhu Y, Peng Q. Image completion using structural priority belief propagation[C]. International Conference on Multimedia, Vancouver, Canada, 2009:717-720.

[37] Hsin H F, Leou J J, Lin C S. Image Inpainting Using Structure Guided Priority Belief Propagation and Label Transformations[C]. International Conference on Pattern Recogn- ition, Istanbul, Turkey, 2010:4492-4495.

[38] Vivek Kwatra, Arno Schödl, Irfan Essa etal. Graphcut textures: image and video synthesis using graph cuts[C] Proceeding ACM SIGGRAPH 2003,22(3):277-286.

[39] 张红英, 彭启琮. 数字图像修复技术综述[J].中国图象图形学报,2007,12(1)：1-9.

[40] 岳晓菊. 基于样图纹理合成算法的研究及应用[D].西北大学硕士学位毕业论文, 2010.

[41] 林云莉. 数字图像修复算法的研究[D].华南理工大学硕士学位毕业论文, 2010.

[42] Julien Mairal, Michael Elad, Guillermo Sapiro. Sparse Representation for Color Image Restoration[J]. IEEE Transactions on Image Processing 2008,17(1):53-59.

[43] J Stark, M Elad, D Donoho. Image decomposition via the combination of sparse represe- ntations and variational approach[J].IEEE Transactions Image Processing, 2005, 14 (10):1570–1582.

[44] M Elad, J L Stark, P Querre, etal. Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA)[J]Applied & Computational Harmonic Analysis 2005,19(3). 340–358.

[45] X Li. Image recovery via hybrid sparse representations: A deterministic annealing appro- ach[J]. IEEE Journal of Selected Topics Signal Processing, 2011,5(5):953–962.

[46] M J Fadili, J L Starck, F Murtagh. Inpainting and Zooming Using Sparse Representations

[J]. Journal of The Computer Journal, 2009,52(1): 64–79.

[47] Peyr, Gabriel. Sparse Modeling of Textures[J] Journal of Mathematical Imaging & Vision, 2009 , 34 (1) :17-31.

[48] 胡正平, 刘文, 许成谦等. 局部自适应学习基稀疏约束结合信息优先权选择扩散的迭代图像修复算法研究[J] 仪器仪表学报, 2010,31(3):600-605.

[49] Jian Zhang, Debin Zhao, Ruiqin Xiong,etal. Image Res-toration Using Joint Statistical Modeling in Space-Transform Domain[J]. IEEE Transactions on Circuits System and Vi- deo Technology, 2014,24(6):915-928.

[50] Jian Zhang, Debin Zhao, Wen Gao.Group-based Sparse Represenation for Image Restor- ation[J]. IEEE Transactions on Image Processing, 2014,23(8):3336-3351.

[51] L Zhang, B Kang, B Liu etal. A new inpainting method for object removal based on patch local feature and sparse representation[J].International Journal of Innovative Computing -,Information and Control,2016,12(1):113-124.

[52] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, etal. Generative adversarial nets[C]. International Conference on Neural Information Processing Systems, Montreal, Canada, 2014,3:2672–2680.

[53] Raymond Yeh, C Chen, T Y Lim, etal. Semantic Image Inpainting with with Deep Gener-ative Models [C]. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Honolulu, Hawaii, USA ,2017: 6882-6890.

[54] Deepak Pathak, Philipp Krähenbühl, Jeff Donahue, etal. Context Encoders: Feature Learning by Inpainting[C]. IEEE Conference on Computer Vision and Pattern Recognit-ion, Las Vegas, NV, USA, 2016: 2536-2544.

[55] Chao Yang, Xin Lu, Zhe Lin, etal. High-Resolution Image Inpainting using Multi-Scale Neural Patch Synthesis[C].IEEE Conference on Computer Vision and Pattern Recognitio- n, Honolulu, Hawaii, USA,2017.

[56] A Radford,L Metz,S Chintala.Unsupervised Representation Learning with Deep Convol-utional Generative Adversarial Networks[C].In International Conference on Learning R-epresentations, Caribe Hilton, San Juan, Puerto Rico,2016.

[57] Satoshi Iizuka, Edgar Simo-Serra, Hiroshi Ishikawa. Globally and locally consistent ima-ge completion[J] Journal ACM Transactions on Graphics (TOG) 2017,36(4):107:2-107:13.

[58] Li Xu, Qiong Yan, Yang Xia et al.Structure Extraction from Texture via Relative Total Variation[J]. ACM Transactions on Graphics,2012,31(6):139:2-139:10.

[59] Carsten Rother, Vladimir Kolmogorov, Andrew Blake."GrabCut":Interactive Foreground Extraction using Iterated Graph Cuts[J].ACM SIGGRAPH,2004,23(3):309-314.

[60] 张健. 基于稀疏表示模型的图像复原技术研究[D]哈尔滨工业大学博士论文，2014.

[61] 李志丹，和红杰，尹忠科等. 基于块结构稀疏度的自适应图像修复算法[J].电子学报，2013,41(3):549-554.

[62] C Tang, X Hu, L Chen, etal. Sample-based image completion using structure synthesis[C]. IEEE International Conference on Image Processing, Melbourne, Australia,2014,24 (7):1115-1123.

[63] David Douglas.Thomas Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. The Canadian Cartographer,1973, 10(2):112–122.

[64] A El-Ghazal,O Basir,S Belkasim. Invariant curvature-based Fourier shape deors[J] Journal of Visual Communication & Image Representation,2012,23(4):622-633.

[65] 管伟光, 马颂德. 具有形变平面轮廓匹配问题[J].自动化学报,1996,22(6):666-670.

[66] S Paris,F Durand. A Topological Approach to Hierarchical Segmentation using Mean Shift[C].IEEE Conference on Computer Vision and Pattern Recognition, Minneapolis, MN, USA ,2008,27(6):1-8.

[67] Gary Bradski等著, 学习Opencv中文版[M].于仕琪等译, 北京：清华大学出版社, 2009.

[68] 吴晓军, 李功清. 基于样本和线性结构信息的大范围图像修复算法[J].电子学报，2012,40(8):1509-1514.