1,228
12
Essay, 6 pages (1,409 words)

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.

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 1 st , 2020

Literature review

March 1 st , 2020

Experimentation

April 1 st , 2020

Analyse, collate and compare new results to previous ones

May 30 th , 2020

Present final results and report

July 4 th , 2020

References

  • Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., . . . Cohen, M. (2004). Interactive digital photomontage ACM. 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 cuts IEEE. 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 sampling IEEE. 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 Recognitionhttps://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
Thanks! Your votes help us become better!
Image inpainting using mathematical algorithms. Page 1
Image inpainting using mathematical algorithms. Page 2
Image inpainting using mathematical algorithms. Page 3
Image inpainting using mathematical algorithms. Page 4
Image inpainting using mathematical algorithms. Page 5
Image inpainting using mathematical algorithms. Page 6
Image inpainting using mathematical algorithms. Page 7
Image inpainting using mathematical algorithms. Page 8

This work "Image inpainting using mathematical algorithms" was written and submitted voluntarily by your fellow student. You can use this sample for research and reference purposes to help create your own paper. The use of any parts of the work without proper citation is forbidden.

If you are the owner of this work and don’t want it to be published on NerdySeal, request its removal.

Request Removal
Cite this Essay

References

NerdySeal. (2021) 'Image inpainting using mathematical algorithms'. 13 December.

Reference

NerdySeal. (2021, December 13). Image inpainting using mathematical algorithms. Retrieved from https://nerdyseal.com/image-inpainting-using-mathematical-algorithms/

References

NerdySeal. 2021. "Image inpainting using mathematical algorithms." December 13, 2021. https://nerdyseal.com/image-inpainting-using-mathematical-algorithms/.

1. NerdySeal. "Image inpainting using mathematical algorithms." December 13, 2021. https://nerdyseal.com/image-inpainting-using-mathematical-algorithms/.


Bibliography


NerdySeal. "Image inpainting using mathematical algorithms." December 13, 2021. https://nerdyseal.com/image-inpainting-using-mathematical-algorithms/.

Work Cited

"Image inpainting using mathematical algorithms." NerdySeal, 13 Dec. 2021, nerdyseal.com/image-inpainting-using-mathematical-algorithms/.

Contact Us

If you have any idea how best to write about Image inpainting using mathematical algorithms, please contact us immediately. We would like to know more: [email protected]