Pixel and Patch Reordering for Fast Patch Selection in Exemplar-Based Image Inpainting

Baeksop KIM  Jiseong KIM  Jungmin SO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.12   pp.2892-2895
Publication Date: 2013/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.2892
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Image Processing and Video Processing
Keyword: 
image inpainting,  image completion,  exemplar-based,  bounding,  fast nearest-neighbor algorithm,  

Full Text: PDF>>
Buy this Article




Summary: 
This letter presents a scheme to improve the running time of exemplar-based image inpainting, first proposed by Criminisi et al. In the exemplar-based image inpainting, a patch that contains unknown pixels is compared to all the patches in the known region in order to find the best match. This is very time-consuming and hinders the practicality of Criminisi's method to be used in real time. We show that a simple bounding algorithm can significantly reduce number of distance calculations, and thus the running time. Performance of the bounding algorithm is affected by the order of patches that are compared, as well as the order of pixels in a patch. We present pixel and patch ordering schemes that improve the performance of bounding algorithms. Experiments with well-known images used in inpainting literature show that the proposed reordering scheme can reduce running time of the bounding algorithm up to 50%.