05-05-2011, 12:11 PM
Abstract
This paper introduces a novel examplar-based inpaintingalgorithm through investigating the sparsity of naturalimage patches. Two novel concepts of sparsity at the patch levelare proposed for modeling the patch priority and patch representation,which are two crucial steps for patch propagation inthe examplar-based inpainting approach. First, patch structuresparsity is designed to measure the confidence of a patch locatedat the image structure (e.g., the edge or corner) by the sparsenessof its nonzero similarities to the neighboring patches. The patchwith larger structure sparsity will be assigned higher priorityfor further inpainting. Second, it is assumed that the patch tobe filled can be represented by the sparse linear combination ofcandidate patches under the local patch consistency constraint ina framework of sparse representation. Compared with the traditionalexamplar-based inpainting approach, structure sparsityenables better discrimination of structure and texture, and thepatch sparse representation forces the newly inpainted regions tobe sharp and consistent with the surrounding textures. Experimentson synthetic and natural images show the advantages of theproposed approach.
Index Terms—Image inpainting, patch propagation, patch sparsity,sparse representation, texture synthesis.
I. INTRODUCTION
THE filling-in of missing region in an image, which iscalled image inpainting, is an important topic in the fieldof computer vision and image processing. Image inpainting hasbeen widely investigated in the applications of digital effect(e.g., object removal), image restoration (e.g., scratch or textremoval in photograph), image coding and transmission (e.g.,recovery of the missing blocks), etc.The most fundamental inpainting approach is the diffusionbasedapproach [1]–[3], in which the missing region is filledby diffusing the image information from the known region intothe missing region at the pixel level. These algorithms are wellfounded on the theory of partial differential equation (PDE)and variational method. Bertalmio et al. [1] filled in holes bycontinuously propagating the isophote (i.e., lines of equal grayvalues) into the missing region. They further introduced the Navier–Strokes equation in fluid dynamics into the task of inpainting[2]. Chan and Shen [3] proposed a variational frameworkbased on total variation (TV) to recover the missing information.Then a curvature-driven diffusion equation was proposedto realize the connectivity principle which does not holdin the TV model [4]. A joint interpolation of isophote directionsand gray-levels was also designed to incorporate the principle ofcontinuity in a variational framework [5]. Recently, image statisticslearned from the natural images are applied to the task ofimage inpainting [6]–[8]. The diffusion-based inpainting algorithmshave achieved convincingly excellent results for fillingthe nontextured or relatively smaller missing region. However,they tend to introduce smooth effect in the textured region orlarger missing region.The second category of approaches is the examplar-basedinpainting algorithm. This approach propagates the imageinformation from the known region into the missing regionat the patch level. This idea stems from the texture synthesistechnique proposed in [9], in which the texture is synthesizedby sampling the best match patch from the known region.However, natural images are composed of structures and textures,in which the structures constitute the primal sketches ofan image (e.g., the edges, corners, etc.) and the textures areimage regions with homogenous patterns or feature statistics(including the flat patterns). Pure texture synthesis techniquecannot handle the missing region with composite texturesand structures. Bertalmio et al. [10] proposed to decomposethe image into structure and texture layers, then inpaint thestructure layer using diffusion-based method and texture layerusing texture synthesis technique [9]. It overcomes the smootheffect of the diffusion-based inpainting algorithm; however, itis still hard to recover larger missing structures. Criminisi et al.[11] designed an examplar-based inpainting algorithm by propagatingthe known patches (i.e., examplars) into the missingpatches gradually. To handle the missing region with compositetextures and structures, patch priority is defined to encouragethe filling-in of patches on the structure. Wu [12] proposed across-isophotes examplar-based inpainting algorithm, in whicha cross-isophotes patch priority term was designed based onthe analysis of anisotropic diffusion. Wong [13] proposed anonlocal means approach for the examplar-based inpaintingalgorithm. The image patch is inferred by the nonlocal meansof a set of candidate patches in the known region instead ofa single best match patch. More examplar-based inpaintingalgorithms [14]–[16]were also proposed for image completion.Compared with the diffusion-based inpainting algorithm, theexamplar-based inpainting algorithms have performed plausibleresults for inpainting the large missing region.
Download full report
http://gr.xjtu.edu.cn:8080/upload/PUB.32...ng_TIP.pdf
This paper introduces a novel examplar-based inpaintingalgorithm through investigating the sparsity of naturalimage patches. Two novel concepts of sparsity at the patch levelare proposed for modeling the patch priority and patch representation,which are two crucial steps for patch propagation inthe examplar-based inpainting approach. First, patch structuresparsity is designed to measure the confidence of a patch locatedat the image structure (e.g., the edge or corner) by the sparsenessof its nonzero similarities to the neighboring patches. The patchwith larger structure sparsity will be assigned higher priorityfor further inpainting. Second, it is assumed that the patch tobe filled can be represented by the sparse linear combination ofcandidate patches under the local patch consistency constraint ina framework of sparse representation. Compared with the traditionalexamplar-based inpainting approach, structure sparsityenables better discrimination of structure and texture, and thepatch sparse representation forces the newly inpainted regions tobe sharp and consistent with the surrounding textures. Experimentson synthetic and natural images show the advantages of theproposed approach.
Index Terms—Image inpainting, patch propagation, patch sparsity,sparse representation, texture synthesis.
I. INTRODUCTION
THE filling-in of missing region in an image, which iscalled image inpainting, is an important topic in the fieldof computer vision and image processing. Image inpainting hasbeen widely investigated in the applications of digital effect(e.g., object removal), image restoration (e.g., scratch or textremoval in photograph), image coding and transmission (e.g.,recovery of the missing blocks), etc.The most fundamental inpainting approach is the diffusionbasedapproach [1]–[3], in which the missing region is filledby diffusing the image information from the known region intothe missing region at the pixel level. These algorithms are wellfounded on the theory of partial differential equation (PDE)and variational method. Bertalmio et al. [1] filled in holes bycontinuously propagating the isophote (i.e., lines of equal grayvalues) into the missing region. They further introduced the Navier–Strokes equation in fluid dynamics into the task of inpainting[2]. Chan and Shen [3] proposed a variational frameworkbased on total variation (TV) to recover the missing information.Then a curvature-driven diffusion equation was proposedto realize the connectivity principle which does not holdin the TV model [4]. A joint interpolation of isophote directionsand gray-levels was also designed to incorporate the principle ofcontinuity in a variational framework [5]. Recently, image statisticslearned from the natural images are applied to the task ofimage inpainting [6]–[8]. The diffusion-based inpainting algorithmshave achieved convincingly excellent results for fillingthe nontextured or relatively smaller missing region. However,they tend to introduce smooth effect in the textured region orlarger missing region.The second category of approaches is the examplar-basedinpainting algorithm. This approach propagates the imageinformation from the known region into the missing regionat the patch level. This idea stems from the texture synthesistechnique proposed in [9], in which the texture is synthesizedby sampling the best match patch from the known region.However, natural images are composed of structures and textures,in which the structures constitute the primal sketches ofan image (e.g., the edges, corners, etc.) and the textures areimage regions with homogenous patterns or feature statistics(including the flat patterns). Pure texture synthesis techniquecannot handle the missing region with composite texturesand structures. Bertalmio et al. [10] proposed to decomposethe image into structure and texture layers, then inpaint thestructure layer using diffusion-based method and texture layerusing texture synthesis technique [9]. It overcomes the smootheffect of the diffusion-based inpainting algorithm; however, itis still hard to recover larger missing structures. Criminisi et al.[11] designed an examplar-based inpainting algorithm by propagatingthe known patches (i.e., examplars) into the missingpatches gradually. To handle the missing region with compositetextures and structures, patch priority is defined to encouragethe filling-in of patches on the structure. Wu [12] proposed across-isophotes examplar-based inpainting algorithm, in whicha cross-isophotes patch priority term was designed based onthe analysis of anisotropic diffusion. Wong [13] proposed anonlocal means approach for the examplar-based inpaintingalgorithm. The image patch is inferred by the nonlocal meansof a set of candidate patches in the known region instead ofa single best match patch. More examplar-based inpaintingalgorithms [14]–[16]were also proposed for image completion.Compared with the diffusion-based inpainting algorithm, theexamplar-based inpainting algorithms have performed plausibleresults for inpainting the large missing region.
Download full report
http://gr.xjtu.edu.cn:8080/upload/PUB.32...ng_TIP.pdf