Image Inpainting Using Mathematical Algorithms

Image Inpainting – Filling in the gaps.

Abstract

Inpainting is the process of rebuilding lost or damaged parts of images and videos. Image inpainting, also called hole filling, is the technique of image reconstruction by filling or replacing the region where there is damage or intentional removal of objects. The outcome is to make the observer unaware of the restoration process. In ancient times, restoration of paintings was done by hand and was time-consuming. With the invention of computers and mathematics, image inpainting has become automated and faster for primarily digital imagery. There are three main documented methods for performing image inpainting using mathematical algorithms. Namely, partial differentiation equations, exemplar-based, and convolution-filter based equations. In this proposal, we recommend reintroducing and enhancing a novel way of performing image inpainting that uses scene matching with a larger source of image dataset to perform image inpainting.

Introduction

Image inpainting plays an essential role in the restoration of digital images by way of filling in holes or gaps left by damage. This reconstruction is for replacing regions where distortions or undesired objects. With a high interest in this area, there has been a considerable amount of research carried out with several reviews done on the plethora of proposed algorithms. Most literature surveyed identified three main types of image inpainting algorithms. Namely, partial differentiation equation-based (PDE), exemplar-based, and convolution-filter based algorithms. In one review (Vreja & Brad, 2014), five different methods were evaluated using a standard benchmark by measuring the peak signal-to-noise ratio (PSNR). That is PSNR shows how much an algorithm can enhance a deteriorated image to more closely resemble the original (Hore & Ziou, 2010). Thus, accurately concluding the effectiveness of the equation. There are also hybrid methods that use a combination of the three methods listed above.

Literature Review

PDE algorithms work by propagating or diffusing a target region with data from a known region pixel by pixel. With several variants including linear, non-linear, isotropic (parallel diffusion), anisotropic (diffusion varies with direction), this method works well for the completion of lines and curves  (Telea, 2004). Bertalmio, Sapiro, Caselles, and Ballester (2000) used an algorithm based on fluid dynamics theories. Derived from the Navier-Stokes equation, images are restored using this approach.  PDE is suitable for filling in small, nontextured target regions but does not fare well with more significant regions as it produces blurring.

Get Help With Your Essay
If you need assistance with writing your essay, our professional essay writing service is here to help!
Essay Writing Service

Exemplar based methods use a texture synthesis process whereby unknown patches in the target regions are patched using similar patches in known regions (Criminisi, Perez, & Toyama, 2004). This method has two critical phases: determining the fill-in order and choosing good exemplars (Deng, Huang, & Zhao, 2015).  Exemplar based algorithms perform exceptionally well with restoring large regions; however, the only drawback is the high computational cost it incurs (Criminisi et al., 2004).

Convolution-filter based algorithm inpaints a target image by convolving a proper kernel with the neighbourhoods damaged pixels. Oliveira Richard and Chang (2001) presented a fast image algorithm that works by convolving an image with a Gaussian kernel (i.e., computing the weighted averages of pixels’ neighbourhoods).  Equivalent to isotropic diffusion (linear heat equation). The algorithm uses a weighted average matrix that only considers contributions from the neighbour pixels. Hadhoud, Moustafa, and Shenoda (2005) modified the Oliveira algorithm by implementing time reduction. Both the above convolution- based algorithms are quick inpainting techniques. However, they produce poor results in damaged edges with high contrast.

Hybrid methods take the strengths of both the PDE and exemplar-based algorithms. Bertalmio, Vese, Sapiro, and Osher (2003)  proposed an algorithm using both PDE and exemplar inpainting missing regions on images. The technique decomposes the main image into two images, image structure, and image texture. The combination of these two processed images is the result of both images inpainted by their methods. Another method proposed filled in smaller regions by copying blocks from the outside, which was preceded by matching contours that cross the edge of the occluded area in its interior (Efros & Leung, 1999). All methods described above involve complex algorithms with each having benefits over another. Although the results produced were sometimes impressive, each method has its drawbacks and generally all take longer times to perform the restoration.

 Methodology

We propose to build and enhance a model first introduced by Hays and Efros (2007). Their research involved a method that patches up holes in images based on searching for and finding similar images in a dataset of 2 million images. The dataset used was a collection of images from Flickr groups. A low dimensional scene descriptor is then used to find similar images (Oliva & Torralba, 2006), which was relatively fast to find the nearest scenes. After finding a match or matches, using a graph cut (Boykov, Veksler, & Zabih, 1999), they added the source images to the target image then the Poisson solver of (Agarwala et al., 2004) is used to blend the edges. Their method falls under the classification of learning-based imaging inpainting techniques. The method they employed produced believable results; however, due to the limited number of images used, some did not produce realistic results. We also replace their scene matching algorithm with a faster and more accurate one.

To improve the accuracy of matching images required for the region in a target image that needs inpainting, we will firstly download a more extensive collection of images from the ImageNet dataset which are then indexed by assigning a unique signature to every entry (Wong et al., 2002). These images get saved to a backend MySQL database. For scene matching images, we employ the Image-Match technique (EdjoLabs, 2018), which compares the source with the database collection. Once we identify a match, the area matching the region required for inpainting on the target image is cut and patched onto this area. The added patch is then blended using the Poisson solver.

Timetable for Completion

Task

Deadline

The final decision on the topic, create research questions

February 1st, 2020

Literature review

March 1st, 2020

Experimentation

April 1st, 2020

Analyse, collate and compare new results to previous ones

May 30th, 2020

Present final results and report

July 4th, 2020

References

Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., . . . Cohen, M. (2004). Interactive digital photomontageACM. Symposium conducted at the meeting of the ACM Transactions on Graphics (TOG)

Bertalmio, M., Sapiro, G., Caselles, V., & Ballester, C. (2000). Image inpainting. presented at the meeting of the Proceedings of the 27th annual conference on Computer graphics and interactive techniques,  https://doi.org/10.1145/344779.344972

Bertalmio, M., Vese, L., Sapiro, G., & Osher, S. (2003). Simultaneous structure and texture image inpainting. IEEE Transactions on Image Processing, 12(8), 882-889.

Boykov, Y., Veksler, O., & Zabih, R. (1999). Fast approximate energy minimization via graph cutsIEEE. Symposium conducted at the meeting of the Proceedings of the Seventh IEEE International Conference on Computer Vision

Criminisi, A., Perez, P., & Toyama, K. (2004). Region filling and object removal by exemplar-based image inpainting. IEEE Transactions on Image Processing, 13(9), 1200-1212. https://doi.org/10.1109/TIP.2004.833105

Deng, L.-J., Huang, T.-Z., & Zhao, X.-L. (2015). Exemplar-Based Image Inpainting Using a Modified Priority Definition. PLoS ONE, 10(10), e0141199. https://doi.org/10.1371/journal.pone.0141199

Efros, A. A., & Leung, T. K. (1999). Texture synthesis by non-parametric samplingIEEE. Symposium conducted at the meeting of the Proceedings of the seventh IEEE international conference on computer vision

Hadhoud, M. M., Moustafa, K. A., & Shenoda, S. Z. (2005). Digital images inpainting using modified convolution based method. Int. J. Signal Process. Image Process. Pattern Recogn, 1-10.

Hays, J., & Efros, A. A. (2007). Scene completion using millions of photographs. ACM Transactions on Graphics (TOG), 26(3), 4.

Hore, A., & Ziou, D. (2010, 23-26 Aug. 2010). Image Quality Metrics: PSNR vs. SSIM Symposium conducted at the meeting of the 2010 20th International Conference on Pattern Recognition https://doi.org/10.1109/ICPR.2010.579

Oliva, A., & Torralba, A. (2006). Building the gist of a scene: The role of global image features in recognition. Progress in brain research, 155, 23-36.

Richard, M. M. O. B. B., & Chang, M. Y.-S. (2001). Fast digital image inpainting Symposium conducted at the meeting of the Appeared in the Proceedings of the International Conference on Visualization, Imaging and Image Processing (VIIP 2001), Marbella, Spain

Telea, A. (2004). An Image Inpainting Technique Based on the Fast Marching Method. Journal of Graphics Tools, 9(1), 23-34. https://doi.org/10.1080/10867651.2004.10487596

Vreja, R., & Brad, R. (2014). Image inpainting methods evaluation and improvement. TheScientificWorldJournal, 2014, 937845-937845. https://doi.org/10.1155/2014/937845