Abstract: In the image inpainting algorithm based on texture synthesis,the matching accuracy of optimal exemplar matching is not high but its time complexity is too high,which eventually leads to errors in image inpainting．Focusing on these two issues,firstly,the block matching algorithm was constructed and the matching degree between template and exemplars was measured by using matrix similarity,so,the candidate set of optimal exemplar was preliminarily determined in relatively coarse granularity．Secondly,the pixel matching algorithm was constructed and the matching degree between corresponding pixels was measured by inner product of error matrix between template and candidate exemplar,so,the final optimal exemplar was determined in fine granularity．The block matching algorithm can reduce the time complexity while the pixel matching algorithm can improve matching accuracy,therefore,the optimal exemplar matching algorithm based on matrix similarity can improve matching accuracy without raising time complexity．The experimental results demonstrate that,compared with current texture-based inpainting algorithm,the proposed algorithm can improve matching accuracy and reduce time complexity.

Key words: Image inpainting,Block matching,Matrix similarity,Pixel matching