“ParXII: optimized, data-parallel exemplar-based image inpainting” by Yousef and Hussien

Completing unknown parts of a damaged input image, or removing objects from photographs and replacing them with visually plausible backgrounds is an important task in photo editing and video processing with a wide range of applications from the reconstruction of missing blocks introduced by packet loss during wireless transmission, reversing of impairments, removal of image objects such as logos, stamped dates, text, and persons, to completing panoramas. The problem with most of existing inpainting methods is the balance between efficiency and accuracy, one of the most accurate methods is exemplar-based image inpainting [Criminisi, et al. 2004], the problem with this method is that it’s very slow and inefficient due to the fact that it needs to scan the whole image before inpaiting a certain block of pixels (every scan operation is called a query), this makes the algorithm take tens to hundreds of seconds on modern CPUs.

1. A. Criminisi, P. P’erez, and K. Toyama, “Region filling and object removal by exemplar-based image inpainting,” IEEE Transactions on Image Processing, vol. 13, pp. 1200–1212, September 2004.
2. Tsz-Ho Kwok, Hoi Sheung, and Charlie C. L. Wang. “Fast query for exemplar-based image completion”. IEEE Transactions on Image Processing, vol. 19, pp. 3106–3115. December 2010.