IMAGE INPAINTING USING MULTISCALE SALIENT STRUCTURE PROPAGATION

SHETE R.M.¹*, KITEY S.W.²*
¹M.E. Computer Science Engineering Department, Sant Gadge Baba Amravati University, MS, India.
²M.tech Computer Science and Engineering Dept., RTM Nagpur University, MS, India.
* Corresponding Author : suruchi227@gmail.com

Received : 15-03-2012     Accepted : 12-04-2012     Published : 16-04-2012
Volume : 3     Issue : 2       Pages : 81 - 84
J Signal Image Process 3.2 (2012):81-84

In this study, a new image inpainting approach using multiscale salient structure propagation is proposed. The proposed approach consists of four stages, namely, (1) detection of salient structure(s), (2) inpainting of salient structure(s), (3) inpainting of surrounding areas of salient structure(s) by modified ant colony optimization (ACO), and (4) inpainting of remaining missing regions. Based on the experimental results obtained in this study, as compared with four comparison approaches, the proposed approach provides the better image inpainting results. Image inpainting can be roughly defined as: for an image containing missing regions, we want to fill the missing regions so that a visually plausible outcome is obtained. Image inpainting has developed very quickly and becomes one of the important contents of Digital Image Processing. Image inpainting can be employed in various applications, such as repairing aged images and multimedia editing. It is highly valuable in the protection of culture relic, movie and video special effect making .

Image inpainting, multiscale salient structure propagation, patch priority computation, ant colony optimization (ACO), pheromone update rule.

Image inpainting can be roughly defined as: for an image containing missing regions, we want to fill the missing regions so that a visually plausible outcome is obtained [1] . inpainting can be employed in various applications, such as repairing aged images and multimedia editing, removal of overlaid text, logos from image and removal of object from image. Image inpainting approaches can be roughly divided into four categories, PDEbased approaches feature-based approaches, exemplar-based approaches, and global optimization based approaches. PDEbased approaches try to fill missing regions of an image through diffusion process. Chan and Shen [3] minimized the total variation in the processed image, while maintaining the fidelity to the input image. PDE-based approaches are effective for narrow missing regions, but not effective for large missing regions. For feature-based approaches, Rares et al. [4] used different edge properties to reconstruct missing structures and filled areas between reconstructed borders by smooth continuation of surrounding image data. Chen et al. [5] used a primal sketch model to catch the global image structure, and then reconstructed the missing structure by using the sketch lines. The inpainted results of feature-based approaches depend on precisely-detected image features. For exemplar-based approaches, Criminisi et al. [6] determined the synthesis priority of a patch as the product of two terms, namely, the confidence and data terms. In Shen et al. [7] , the gradient maps in the missing regions and color are completed through a patch-based filling algorithm, and then the image is inpainted from the gradient maps by solving a Poisson equation. Note that exemplar-based approaches do not ensure good structure continuation inside a large missing region. For global optimization based approaches, Sun et al. [8] synthesized image patches along the user-specified curves in a missing region using patches selected around the curves in a source region. Structure propagation is formulated as a global optimization problem by enforcing the structure and consistency constraints. Komodakis et al. [1] presented an exemplar-based framework, which treats image completion, texture synthesis, and image inpainting in a unified manner. They treated all the above image-editing tasks as discrete global optimizations. The paper is organized as follows. The proposed image inpainting approach is addressed in Section III. Simulation results are addressed in Section IV, followed by concluding remarks.

The concept of digital inpainting was first proposed by Bertalmio et al. The algorithm they presented was based on the idea of extending both geometric and photometric information that hits the border of the occluded area into the area itself. This is done through the continuation of these so called ‘isophote’ lines, which try to capture the direction of minimal change. This requirement ultimately leads to the blurring of the content within the occluded area and thus this algorithm isn’t suited for filling large areas.

The algorithm looking at is based on continuing edges through the occluded area. The algorithm consists of three core steps; edge-detection, edge-matching, and an inpainting process (these steps have been summarized in [Fig-3] . This algorithm is generally based on Rare¸ s et all’s algorithm presented in [4] . There is however some distinct differences between the method they proposed and the method I have implemented, but these differences will be highlighted throughout this section. As with the previous algorithms, it is assumed that the input to this restoration algorithm is the image itself and a mask containing the location of the occluded area.

The algorithm that was implemented was of Efros and Leungs texture synthesis algorithm. It was expected that the results for highly textured images would be extremely good, but it would fail at reconstructing structure. Before the algorithm was tested, it was unsure how dependent the algorithm would be on its input parameters. Efros and Leung mention in [7] that the size of should be such that it entirely encompasses the largest ‘texel’ in the source image. This would require some prior knowledge about the image which was not attainable when developing a general inpainting algorithm.

As the illustrated example shown in Fig. 9 [2] , an image I contains a target (missing) region Ω, the boundary of the missing region ∂Ω, and a source region φ with φ = I − Ω. Image inpainting is to fill Ω in a visually plausible way by simply pasting various patches Ψ from φ. The proposed image inpainting approach consists of four stages, namely, 1) detection of salient structure(s); 2) inpainting of salient structure(s); 3) inpainting of surrounding areas of salient structure(s); and 4) inpainting of remaining missing regions.

For a small missing region, existing inpainting approaches usually produce good inpainting results. For a large missing region containing a salient structure, existing inpainting approaches, lacking of the global salient structure of the large missing region, usually produce smooth, but poor inpainting results. Thus, the global salient structure(s) of an image containing missing region(s) should be detected first. To detect the global salient structure(s), an anisotropic diffusion algorithm [9] is employed. Each image pixel I(x,y) at (x,y) is iteratively updated.

In this study, gradient-based salient structure inpainting is proposed. Here, to speedup the salient structure inpainting process, if dmax exceeds a threshold, gradient-based salient structure inpainting will be performed on the multi-scale image pyramid of the image. Otherwise, gradient-based salient structure inpainting will be performed directly on the original image. Here, a multi-scale (two-scale) image pyramid contains the original image and the quarter-size image (half-resolution in the x and y directions). The gradient map (GM) of the salient structure (SS) of the quarter-size image is generated by ▽SS=(GSSx,GSSy)= where GSSx and GSSy are the gradients of SS in the x and y directions, respectively. The binary salient structure map of the quarter-size image is obtained by applying (1) gradient magnitude thresholding, and (2) thinning on GM. The binary salient structure map is then processed by morphological dilation with a 3×3 structure element, which is used to select the corresponding gradient magnitudes in GM by point wise multiplication.
Patch priority computation. For each pixel p on the boundary ∂Ω of a missing region in the quarter-size image, a patch Ψp is constructed with pixel p being its center. The priority of the patch Ψp is given. by
P( p) = Gval ( p) â‹…C( p),
Where Gval (p) and C(p), the gradient and confidence terms.
Structure information propagation. For each missing region in the quarter-size image, the target patch Ψpˆ having the highest priority is found. Then, we search the source patch Ψqˆ in the source region φ of the quarter-size image such that the sum of square differences (SSD) between Ψpˆ and Ψqˆ is minimum.
Priority computation of new boundary pixels of the missing region. After the target patch Ψpˆ is filled with gradient values, the priorities of the pixels on the new boundary ∂Ω′ of the missing region in the “selected” GM are computed, as the illustrated example shown in [Fig-5] .
Checking of structure completion. If all the salient structure(s) in the quarter-size image are completed, the salient structure inpainting process will terminate; otherwise, continue. Based on the reconstructed salient structure(s) (RSS) of the quarter-size image, the least-squared curve fitting technique is adopted to reconstruct the salient structure(s) of the original image.

Based on the reconstructed salient structure(s) (RSS) of the original image, each of three consecutive pixels on a RSS is selected as an anchor point. Let the set of h anchor points of a RSS in the missing region Ω. To achieve visually plausible results, the candidate source patch set Ψ C containing Ch candidate source patches for the h anchor points will be constructed. In Ψ C, each candidate source patch Ψq in ΨC is a patch containing at least an edge point, which are the “white” points of the binary salient structure map. For each anchor point pi, one source patches Ψqˆ in Ψ C can be selected as the target patch of pi. The surrounding area of a RSS containing h anchor points will be well reconstructed if the total cost C(RSS,ΨC) of all overlapping parts for a RSS containing h anchor points is minimized. This is a combinational optimization problem, which can be solved by ant colony optimization (ACO), a population-based iterative optimization algorithm. For ACO, ants leave their searching rewards, pheromone, on their passed paths, which may attract other ants to follow partially with a probabilistic selection rule. Low-cost and ant-experienced paths will attract more ants to pass through. The modified ACO AS (ant system) algorithm proposed for inpainting the surrounding area of a RSS is described as follows.
• Problem formulation. For a RSS containing h anchor points, to assign a candidate source patch Ψ pˆ i from ΨC to the i-th anchor point pi is equivalent to a node (the i-th node) in ACO, and a feasible solution containing h candidate source patches from ΨC for the RSS containing h anchor points is equivalent an ant tour containing h nodes for an ant.
• Initial parameters of ants. Initially, τij 0.000001= τijint i=1,2,…,h and j=1,2,…,Ch. The number of ants, K, is set to 60 and the number of iterations, M, is set to 20.
• Selection rule. Initially, for anchor point pi, each ant selects randomly a candidate source patch from ΨC using a probabilistic selection rule, called random proportional rule.

For remaining missing regions, the modified exemplar based texture synthesis approach [6] is employed to find the “optimal” source patch of a target patch in its neighboring region. To avoid disturbance of structure edges, the priority of each target patch is determined by the product of the confidence value of all the undamaged and inpainted pixels in the patch. And the distance between the central pixel of the patch and the nearest edge is calculated. Then, the target patch with the highest priority will be synthesized first. The search region for the target patch is bounded within a 15×15 region and the boundary of the nearest edge. If the best candidate patch for the target patch (the SSD between them is less than a threshold, Th1) is found, the target patch is inpainted by the best candidate patch.

To evaluate the performance of the proposed approach, four image inpainting approaches, namely, the PDE-based [2] , sketch-based [5] , exemplar-based [6] , and gradientbased [7] approaches are implemented in this study and test images are employed. Here, Th1 = 3500 and Th2 = 5. Fig.12 shows the results for the test image “race” (500×351 in size) with structure patch size = 9×9 and texture patch size = 11×11.
The PDE-based approach produces blurring artifacts in [Fig-6] (c), in [Fig-6] (d)-(f), the sketchbased, examplar-based, and gradient-based approaches do not effectively inpaint both the structure and texture parts of the image, whereas the proposed approach well inpaints both the structure and texture parts of the image in [Fig-6] (g).

In this study, a new image inpainting approach using multiscale salient structure propagation is proposed, which consists of four stages: (1) detection of salient structure(s), (2) inpainting of salient structure(s), (3) inpainting of surrounding areas of salient structure(s), and (4) inpainting of remaining missing regions. Based on the experimental results obtained in this study, as compared with four comparison approaches, the proposed approach provides the better image inpainting results.

I express my sincere gratitude to Resp. Dr. A.D. Gawande Head of the Department, Computer Science & Engineering & Resp. Prof V. S. Gulhane for providing their valuable guidance and necessary facilities needed for the successful completion of this seminar throughout. I am also obliged to our principal, Resp. Dr. S. A. Ladhake who has been a constant source of inspiration throughout.
Lastly, but not least, I thank all my friends and well-wishers who were a constant source of inspiration.

[1] Komodakis N. and Tziritas G. (2007) IEEE Trans. on Image Processing, 16 (11), 2649-2661.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Bertalmío M. Sapiro G. Caselles V. and Ballester C. (2000) ACM Int. Conf. on Computer Graphics and Interactive Techniques, 417-424.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] Chan T.F. and Shen J. (2002) SIAM J. Appl. Math., 62 (3), 1019-1043.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] Rares A. Reinders M.J.T. and Biemond J. (2005) IEEE Trans. on Image Processing, 14 (10), 1454-1468.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[5] Chen Y., Luan Q. Li H. and Oscar Au (2000) IEEE Int. Conf. on Image Processing, 1997-2000.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[6] Criminisi A., P´erez P. and Toyama K. (2004) IEEE Trans. on Image Processing, 13 (9), 1200-1212.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[7] Shen J. Jin X. Zhou C. and Wang C.C.L. (2007) Computers and Graphics, 319 (1), 119-126.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[8] Sun J., Yuan L., Jia J. and Shum H.Y. (2005) ACM Int. Conf. on Computer Graphics and Interactive Techniques, 861-868.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

	Fig. 1- (a) the masked image; (b) the image inpainting results by PDE-based
	Fig. 2- (a) the masked image; (b) the image inpainting results by Feature-based
	Fig. 3- (a) the masked image; (b) the image inpainting results by Exemplar-based
	Fig. 4- (a) An illustrated image I contains a target (missing) region Ω, the boundary of the missing region ∂Ω, and a source region φ with φ = I − Ω. (b) Ψp and Ψq represent a target patch and a source patch, respectively [6].
	Fig. 5- An illustrated example: (a) the missing salient structure of the target patch Ψpˆ is filled by the corresponding gradient values of the “optimal” source patch Ψqˆ; (b) priority computation of the pixels on the new boundary ∂Ω′ of the target (missing) region Ω in the “selected” GM.
	Fig. 6- (a) The original image, “Race;” (b) the masked image; (c)-(g) the image inpainting results by PDE-based [2], sketch-based [5], exemplar-based [6], gradient-based [7], and the proposed approach, respectively.