Object Removal and Filling by DWT Based Inpainting Technique

Department of Electronics & Telecommunication Dept., Sinhgad Academy of Engg, Pune, India

*Corresponding Author:

Vaibhav V Nalawade
Department of Electronics & Telecommunication Dept., Sinhgad Academy of Engg, Pune, India
E-mail:vaibhav_n2009@rediffmail.com

Visit for more related articles at International Journal of Advance Innovations, Thoughts & Ideas

Abstract

 Inpainting is the art of modifying an image in a form that is not detectable by an ordinary observer. There are numerous and different approaches to tackle the inpainting problem. The inpainting technique can be classified into two categories: (1) texture oriented and (2) structure oriented. Both the technique have their advantages and disadvantages. Wavelet transform has been used for various image analysis problems due to its nice multi-resolution properties and decoupling characteristics. We propose to utilize the advantages of wavelet transforms for image inpainting. A number of examples on real and synthetic images demonstrate the effectiveness of the algorithm. Unlike other inpainting algorithms, we can expect better global structure estimation of a damaged or target region in addition to shape and texture properties

Keywords

Wavelet transform, Object Removal, Image Inpainting, Texture Synthesis, Multi-resolution.

Introduction

The filling-in of missing region in an image is known as Image Inpainting. Inpainting is the art of modifying an image or video in a form that is not easily detectable by an ordinary observer. Image Inpainting has become a fundamental area of research in image processing. The modification of images in a way that is non-detectable for an observer who does not know the original image is a practice as old as artistic creation itself. Medieval artwork started to be restored as early as the renaissance. The motive was simple, to bring medieval pictures, ‘up to date’ as to fill any gaps. This practice is called ‘retouching’ or ‘inpainting’[9].

Also image inpainting has been widely investigated in the applications of digital effect (i.e. object removal, image editing, image resizing), image restoration (e.g. Scratch or text removal in photograph), image coding and transmission (e.g. recovery of missing blocks) etc.

This paper demonstrates a novel algorithm for removing large objects from digital photographs and replacing them with visually plausible backgrounds. Fig. 1 shows an example of this task, where the foreground tower (manually selected as the target region) is automatically replaced by data sampled from remainder of the image. The process of inpainting can be graphically represented as shown in fig.2.The input to the algorithm is an image to be inpainted i.e. painted image. The user selects the region to be inpainted i.e. the target region. Then the algorithm proceeds filling the target region with features around it. The output is an inpainted image.

Figure 1: Removing large objects from images.

Figure 2: Data flow diagram of inpainting process

The conventional schemes that are proposed for image inpainting can be divided into two categories:

• Texture oriented

• Structure oriented

Several researchers have considered texture synthesis as a way to fill large image regions with ‘pure’ textures-repetitive two dimensional textural patterns. This approach effectively generates new texture by sampling and copying color values from the source [9]. Though the techniques of texture synthesis are effective, they have difficulty in filling holes in photographs of real world scenes consisting of composite textures. However, the structure- oriented scheme obtains the missing region by propagating linear structure into the target region via diffusion. They are inspired by the partial differential equations. Their drawback is that the diffusion process introduces some blur, which becomes noticeable when filling larger regions.

M. Bertalimo is one of the legendary names in the field of Image Inpainting, proposed a simple algorithm (2000) where filling in the missing region is carried out by the property of Isophotes(lines of equal gray value) [6]. Also soon after this in 2001 Chan, Shen and coworkers proposed a variation model for filling in gray level and color images. Later Mumford-Shah model in 2002 has been adopted for good obtaining good approximations from mathematically neat image modeling. These proposed algorithms were structure oriented. These algorithms were able to keep good continuation smoothly however, broken edge estimation with large gap could fail and detail texture surface is not easily reproducible. Again in 2003 Bertalimo proposed to decompose each original image into two separate component images of different characteristics. One of them is processed by texture-oriented scheme and the other by structure-oriented one. In 2007 Ching and coworkers proposed an algorithm using wavelet. This algorithm could be applied to highly lose image. Also in 2008 Wong proposed nonlocal means approach for exemplar based Inpainting algorithm. The image patch is inferred by nonlocal means of a single best match patch. Also simultaneously Dongwook Cho, and Tien D. Bui in 2008 showed the use of advantages of wavelets to Image Inpainting [12]. The technique presented in this paper uses the advantages of wavelet transform for image inpainting.

Paper outline: Section II presents the main idea of this algorithm. The details of proposed algorithm are described in section III. Finally, a gallery of results on both synthetic images and real scene photographs is presented in section IV.

Main Idea

The target region (damaged or lost data or object to be removed) information of the image can be divided into two kinds of conditions. The first class, the distribution of the target information of the image is the local and concentrated. So the decision method of the image repair can depend on the characteristic and direction of the neighboring textures to decide. The second class, the distribution of the image target part is global and dispersion. Therefore, we can't clearly repair the repair image through the consult data of the neighboring district. . In the active areas, the image data is more localized in the spatial domain, while in the smooth areas, the image data is more localized in the frequency domain. With traditional transform coding, it is very hard to reach a good compromise.

To solve the problem, using the mankind's vision characteristic which is the basis of the repair. When the reference data shortage to repair the image, we zoom-out the distorting image can observe the image shape. Actually in the image processing, we use the down-sampling method to reach the visual effect. For the wavelet transform, the coefficients at the course level represent a larger time interval but a narrower band of frequencies. This feature of the wavelet transform is very important for image coding.

The original image was processed through a secondary-level wavelet transformation analysis, as illustrated in Fig. 2(c), where the highlighted image in the uppermost left hand corner is represented by the section LL2 illustrated in Fig. 2(d). Where analysis is concerned, the components of the overall image composition are all taken into consideration. This procedure can also be utilized as preliminary image analysis. The four components LL2, LH2, LH2, and HH2 are then processed through reversed wavelet transformations to heighten the resolution of the image. As shown in Fig. 2(a), where the highlighted image in the upper left hand corner is represented by the section LL1 illustrated in Fig. 2(b). This would result in the increasing of frequency components within the image, which would then contribute towards the depiction of local area textural features.

Region Filling Algorithm

The damaged of the color image will be divided into the color composition and the texture composition [16]. In fig 3(a), we can find the importance of the texture composition in color image reconstruction. We use n level wavelet transform to separate the texture image (Y) into different frequency compositions. The method repaired the distortion image from the low frequency composition repair to high frequency composition repair gradually. When we repair to the highest frequency layer in the wavelet domain, we will acquire the reconstruction image of the highest resolution. Besides in fig. 3(b) and 3(c), we can obviously find the color composition, Cb and Cr, has the highly neighboring relativity. So we only need to use the neighboring information of the valid pixel to repair the color image. According to the concept, we have to put the reference target on the neighboring district. So we choose the linear interpolation to be used as the repair method in the color distortion image [1].

Figure 3: Results of the wavelet transformation analysis derived from various layers of a given image (a) 1-Level DWT image (b) 1-Level DWT Resolution (c) 2-Level DWT image (d) 2-Level DWT Resolution

Algorithm

1) Take a damaged image.

2) Convert the color image to YCbCr by using conversion formulae.

3) For texture composition Y

I. Apply n-level wavelet transform (we have applied 2-level).

II. Analyze LLn wavelet coefficient (in our case LL2).

III. Apply direction texture decision law.

IV. Take a 1-level IDWT.

V. Repeat steps I to IV until n-level =0, now it provides image Y composition inpainted results.

4) For color composition

I. Perform color neighbor interpolation.

II. This provides the image Cb,Cr composition inpainted results.

5) Add both texture composition Y and Cb,Cr composition inpainted results.

6) Convert Y,Cb,Cr to RGB using conversion formulae.

7) Finally we get inpainted image.

Finally we get repaired image by converting YCbCr to RGB. This algorithm uses both texture composition image repair method and color composition image repair method. The texture composition image repair method uses wavelet domain to reconstruct characteristics of space frequency relativity. We analyze the multi-layers of the image from low frequency layer to high frequency layer with the help of wavelet transform. We should repair grand amount of losing pixels at the high frequency layer which will ultimately repair the pixels at low frequency layer. A layer number n to be reduced means performing 1-level inverse discrete wavelet transform (IDWT).

The Image Repairing Method in Texture Composition

In the human's vision, the texture composition of the color image has the important contribution. For repair the texture composition, we proposed the global and the multi-frequency method using wavelet transform to reconstruct the image. According to this concept, the repairing method must to decide the initial layer of the repairing pixel. When the layer number n be reduce by one which mean carrying out the 1-level inverse discrete wavelet transform (IDWT), the layer exists its relative sub-band n LL . We must calculate the relative amount of the valid pixels of the original image that exists around the target pixel included in the n LL. If the any pixel exists in the LL layer which relative the amount of the valid pixels is to satisfy the following equation, and the pixel in the n LL will start being repaired in this layer.

(1)

Where N V_p n , is the total number of the valid pixel in the layer n. In another condition,

(2)

The repair procedure of the pixel (i,j) will not carry out under the layer n. But the opposite pixel of the pixel (i,j)will be checked whether handle the repair procedure after the next layer by the IDWT. We use the different size of the damage block to explain which damage block should be repaired in which layer. If we decided the initial repair in which layer, after we must to decide how to repair the image. So we according to the characteristic of the tree structure of the wavelet domain decide the repairing coefficients [1], shown as the fig. 5. The tree structure includes the different repairing method of the four components (Mean, Vertical Branch, Horizontal Branch and Diagonal Branch). According to separate the idea of the repair, we consider the pixel value of the different direction to handle the repair procedure. The repair of the MEAN composition influence the shapes of the object therefore us consider the whole of the bigger area. Besides, the repair method of the directional branch will consider its corresponding directional reference coefficient. The best similar pixel search which using calculates the energy of the differential pixel by the following equation:

Figure 4: Image characteristic: (a)Texture composition (Y), (b) Color composition (Cb) (c) Color composition (Cr)

Figure 5: The “tree structure” correlation of wavelet Transformation

(3)

The Image Repairing Method In Color Composition

In the image in order to separate the texture composition and color composition, we have to use the color conversion formula to the process. Among them, the texture composition is importance than the color composition. The color conversion formula is as follows:

Y = 0.299 * R + 0.587 *G + 0.114 * B (4)

Cb = −0.169 * R − 0.331*G + 0.555* B (5)

Cr = 0.500 * R − 0.419 *G − 0.081* B (6)

Table 1: Related weighting value of the different distance

The algorithm makes use of the color composition of the image that have the regional characteristic. The proposed repair method defines different weighting values that consider the relating distance from the repair target P. If the most neighbouring district exist more than two reference pixel value, we will only consider the most neighbouring district pixel value to repair image. But if the reference pixel is not exists anyone or just only one, we must extensive the distance of the consideration [1]. Using this concept, we proposed the revised method of the linear interpolation for the color restoration repair method. The new linear interpolation function as the following equation (7) & (8).

(7)

(8)

Where pv is the valid pixel (i,j) value of the image, wi,j is the weighting value on (i,j), total w is the total weighting value of valid pixel value, ij C is the valid pixel value and new C is repair pixel value on the target T. The total w be calculated for normalize the repair value of the linear interpolation pixels, in function (8).

Table 2: PERFORMANCE EVALUATION FOR LONAVALA IMAGE

Finally we get repaired image by converting YCbCr to RGB. This algorithm uses both texture composition image repair method and color composition image repair method. The texture composition image repair method uses wavelet domain to reconstruct characteristics of space frequency relativity. We analyze the multi-layers of the image from low frequency layer to high frequency layer with the help of wavelet transform. We should repair grand amount of losing pixels at the high frequency layer which will ultimately repair the pixels at low frequency layer. A layer number n to be reduced means performing 1-level inverse discrete wavelet transform (IDWT). We have to decide initial layer of repair then we have to decide how to repair image. Here we use inter and intra scale dependency of the pixels. The tree structure includes four components (mean, horizontal, vertical, diagonal). Repairing is done by calculating differential energy of the damaged image and search image. In case of color composition image repair method we use linear interpolation technique. We define different weighting values that consider relative distance from the target T. The new linear interpolation is expressed by equation 7 and equation 8.

Results and Comparison

The algorithm can be applied to a variety of images ranging from purely synthetic images to full color photographs that includes complex textures. All the experiments are performed on a 2.5GHZ Pentium IV with 1GB of RAM. The performance of the Wavelet based algorithm can be evaluated by considering the parameters like PSNR and the time required to inpaint the image. Also by looking at the figure and the respective table one can decide the required Wavelet packet.

Figure 6: lonavala image

Figure 7: linc image

Figure 8: tower image

Table 3: performance evaluation for linc image

Table 4: Performance evaluation for tower image

Conclusion

The Wavelet based approach is used removing large objects from digital photographs. The technique is capable of propagating both linear structure and two-dimensional texture into the target region with a single, simple algorithm. A simple selection of the fill order is necessary and sufficient to handle robustness changes in shape and topology. The other advantages of the algorithm are: (i) preservation of edge sharpness, (ii) no dependency on image segmentation and (iii) balanced region filling to avoid over-shooting artifacts.

References

1. Dongwook Cho and Tien D. Bui, “Image Inpainting Using Wavelet-based Inter- and Intra-scale Dependency”, 2008, IEEE Trans. Image Processing.
2. Raymond H.Chan, You-Wei Wen and Andy M.Yip, “A Fast Optimization Transfer Algorithm for Image Inpainting in Wavelet Domains”, 2009, IEEE Transaction on Image processing Vol. 18, No.7, July 2009.
3. Wen Li, David Zhang, Zhiyong Liu and Xiangzhen Qiao, “Fast Block-Based Image Restoration Employing the Improved Best Neighborhood matching approach”, 2005, IEEE Transaction On System, Man And Cybernetics – Part A Systems And Humans, Vol. 35, No.4, July 2005.
4. M. Bartalmio, G. Sapiro, V. Caselles, and C. Ballester, “Image Inpainting”, SIGGRAPH, pp.417-424, July 2000.
5. Ching-Tang, “A New Hierarchical Image Inpainting Algorithm”, By HSIEH Dept. of Electrical Engineering Tamkang University, Taipei County, Taiwan 25137.
6. Bertalmio, M., Vese, L., Sapiro, G., Osher, S., 2003. “Simultaneous Structure and Texture Image Inpainting,” IEEE Transactionson Image Processing, 12(8):882-889
7. Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C., 2000. Image Inpainting ACM. Conference on Computer Graphics, SIGGRAPH 2000, p.417-424.
8. M. Bertalmio, L. Vese, G. Sapiro, and S. Osher. “Simultaneous structure and texture image inpainting” In Proc. Conference Computer Vision Pattern Recgonition., Madison, WI, 2003.
9. A. Criminisi, P. Perez, K. Toyama, “Region filling and object removal by exemplar-based inpainting”, IEEE Transactions on Image Processing, Vol. 13, No. 9, pages 1200-1212, 2004.
10. T. F. Chan, S. H. Kang, and J. Shen, “Euler’s elastica and curvature based inpaintings”, SIAM J. App. Math., Vol. 63, No. 2, pages 564-592, 2002
11. S. Esedoglu and J. Shen, “Digital inpainting based on the Mumford-Shah-Euler image model”, European J. Appl. Math., Vol.13, pp. 353-370, 2002.
12. Dongwook Cho, and Tien D. Bui, “Image Inpainting Using Wavelet-based Inter- and Intra-scale Dependency”, IEEE Transactions Image Processing, 978-1-4244-2175-6, 2008.
13. Zongben Xu and Jain Sun, “ Image Inpainting by Patch Propogation using Patch Sparsity”, IEEE Transactions on Image Processing, Vol 19. No. 5, May 2010
14. M. Bertalmio, G. Sapiro, V. Caselles, and C. Ballester, “Image Inpainting”, in Proc. SIGGRAPH, 2000, pp. 417-424
15. P. Harrison. “A non-hierarchical procedure for re-synthesis of complex texture” In Proc. Int. Conf. Central Europe Comp. Graphics, Visua. And Comp. Vision, Plzen, Czech Republic, February 2001.
16. M. Bertalmio, L. Vese, G. Sapiro, and S. Osher. “Simultaneous structure and texture image Inpainting.” In Proc. Conf. Comp. Vision Pattern Rec., Madison, WI, 2003.
17. J. Jia and C.-K. Tang. “Image repairing: Robust image synthesis by adaptive tensor voting.” In Proc. Conf. Comp. Vision Pattern Rec., Madison, WI, 2003.
18. Ching-tang HSIEH, Yen-Liang CHEN, and Huang Chien-Yi, “The Image Inpainting Method apply to the highly Lose image”, Proceedings of the 2007 WSEAS International Conference on Computer Engineering and Applications, Gold Coast, Australia, January 17-19, 2007 .