IMAGE IMPAINTING BY PATCH PROPAGATION USING PATCH SPARSITY
seminarsonly Active In SP Posts: 126 Joined: Sep 2010 
24092010, 04:24 PM
IMAGE IMPAINTING BY PATCH PROPAGATION USING PATCH SPARSITY Presented By: Tiya Cyriac S7 AE Roll No:68 College Of Engineering , Trivandrum 200711 batch OVER VIEW Introduction . Algorithm overview. Inpainting by patch sparsity. Experiments and comparison. Conclusion. IMAGE INPAINTING Filling of missing region of an image. Used widely in the field of computer vision & image processing. Wide applications of digital effects(eg:object removal),image restoration(eg: scratch or text removal in photograph),image coding& transmission(recovery of missing blocks). DIFFUSION BASED APPROACH Missing region filled by diffusing image information from known region at pixel level. Based on theory of PDE . Isophotes propagated into missing regions. Smooth effect in larger missing regions. EXAMPLAR BASED APPROACH Propagates image information from known region at patch level. Based on texture synthesis technique. Texture synthesized by sampling best match patch from known region. Plausible results for filling large missing regions. PROPOSED APPROACH Examplar based image inpainting through patch propagation. Basic procedures of patch propagation patch selection and patch inpainting. Patch selection : patch on missing region boundary, highest priority. Patch inpainting : best match patch from a set of candidate patches for robust inpainting. PATCH SPARSITY Patches distributed sparsely over a region. Two concepts of patch sparsity. Patch structure sparsity. Patch sparse representation. PATCH STRUCTURE SPARSITY Sparseness of patch’s nonzero similarities with neighbouring patches. Greater for patch on structure than texture. PATCH SPARSE REPRESENTATION: Missing patch represented as a linear combination of candidate patches. ALGORITHM OVERVIEW INPAINTING USING PATCH SPARSE REPRESENTATION CONSTRAINTS INPAINTING EXAMPLES PATCH SELECTION Number of nonzero components varies for each patch SCRATCH AND TEXT REMOVAL Inpainting algorithm can be used to remove scratches and text on an image. PSNR values between original and inpainted image, used for quantitative comparison. IMPLEMENTATION Small subset of candidate patches decreases computational overhead. Takes 103 secs to fill missing region with 5310 missing pixels using C++ programming language on intel 2 GHz cpu. CONCLUSION IIP algorithm can be used for text removal, object removal, missing block completion. Two types of patch sparsity proposed. Patch with larger structure sparsity at structure inpainted with higher priority. Human labeled structures can be incorporated to recover totally removed structures in future. REFERENCES A. Wong and J. Orchard, “A nonlocalmeans approach to examplar based inpainting,” presented at the IEEE Int. Conf. Image Processing, 2008. B. Shen, W. Hu, Y. Zhang, and Y. Zhang, “Image inpainting via sparse representation,” in Proc. IEEE Int. Conf. Acoustics, Speech and Signal Processing, 2009, pp. 697–700. J. C. Yang, J. Wright, T. Huang, and Y. Ma, “Image superresolution as sparse representation of raw image patches,” presented at the IEEE Computer Society Conf. Computer Vision and Pattern Recogition, 2008 M. J. Fadili, J. L. Starck, and F. Murtagh, “Inpainting and zooming using sparse representations,” The Comput. J., vol. 52, no. 1, pp. 64–79, 2009. dowload the ppt here: filesonicfile/21413165/IMAGE IMPAINTING_2003.ppt Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion



Wifi Active In SP Posts: 158 Joined: Oct 2010 
01112010, 12:05 AM
ABSTRACT This report introduces a novel examplarbased inpainting algorithm through investigating the sparsity of natural image patches. Two novel concepts of sparsity at the patch level are proposed for modeling the patch priority and patch representation, which are two crucial steps for patch propagation in the examplarbased inpainting approach. First, patch structure sparsity is designed to measure the confidence of a patch located at the image structure (e.g., the edge or corner) by the sparseness of its nonzero similarities to the neighboring patches. The patch with larger structure sparsity will be assigned higher priority for further inpainting. Second, it is assumed that the patch to be filled can be represented by the sparse linear combination of candidate patches under the local patch consistency constraint in a framework of sparse representation. Compared with the traditional examplarbased inpainting approach, structure sparsity enables better discrimination of structure and texture, and the patch sparse representation forces the newly inpainted regions to be sharp and consistent with the surrounding textures. Experiments on synthetic and natural images show the advantages of the proposed approach. report: mediafire?hux1nnglhgs448f CHAPTER 1 INTRODUCTION The fillingin of missing region in an image, which is called image inpainting, is an important topic in the field of computer vision and image processing. Image inpainting has been widely investigated in the applications of digital effect (e.g., object removal), image restoration (e.g., scratch or text removal in photograph), image coding and transmission (e.g., recovery of the missing blocks), etc. 1.1. DIFFUSION BASED APPROACH The most fundamental inpainting approach is the diffusion based approach, in which the missing region is filled by diffusing the image information from the known region into the missing region at the pixel level. These algorithms are well founded on the theory of partial differential equation (PDE) and variational method. Bertalmio filled in holes by continuously propagating the isophote (i.e., lines of equal gray values) into the missing region. They further introduced the Navier–Strokes equation in fluid dynamics into the task of inpainting. Chan and Shen proposed a variational framework based on total variation (TV) to recover the missing information.Then a curvaturedriven diffusion equation was proposed to realize the connectivity principle which does not hold in the TV model. A joint interpolation of isophote directions and graylevels was also designed to incorporate the principle of continuity in a variational framework. Recently, image statistics learned from the natural images are applied to the task of image inpainting. The diffusionbased inpainting algorithms have achieved convincingly excellent results for filling the nontextured or relatively smaller missing region. However, they tend to introduce smooth effect in the textured region or larger missing region. 1.2 EXAMPLAR BASED APPROACH The second category of approaches is the examplarbased inpainting algorithm. This approach propagates the image information from the known region into the missing region at the patch level. This idea stems from the texture synthesis technique proposed, in which the texture is synthesized by 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 of an image (e.g., the edges, corners, etc.) and the textures are image regions with homogenous patterns or feature statistics (including the flat patterns). Pure texture synthesis technique cannot handle the missing region with composite textures and structures. Bertalmio proposed to decompose the image into structure and texture layers, then inpaint the structure layer using diffusionbased method and texture layer using texture synthesis technique. It overcomes the smooth effect of the diffusionbased inpainting algorithm; however, it is still hard to recover larger missing structures. Criminisi designed an examplarbased inpainting algorithm by propagating the known patches (i.e., examplars) into the missing patches gradually. To handle the missing region with composite textures and structures, patch priority is defined to encourage the fillingin of patches on the structure. Wu proposed a crossisophotes examplarbased inpainting algorithm, in which a crossisophotes patch priority term was designed based on the analysis of anisotropic diffusion. Wong proposed a nonlocal means approach for the examplarbased inpainting algorithm. The image patch is inferred by the nonlocal means of a set of candidate patches in the known region instead of a single best match patch. More examplarbased inpainting algorithms were also proposed for image completion. Compared with the diffusionbased inpainting algorithm, the examplarbased inpainting algorithms have performed plausible results for inpainting the large missing region. 1.3 RELATED APPROACHES Recently, image sparse representation is also introduced to the inpainting problem. The basic idea of this approach is to represent image by sparse combination of an overcomplete set of transforms (e.g., wavelet, contourlet, DCT, etc.), then the missing pixels are inferred by adaptively updating this sparse representation. Guleryuz proposed an image inpainting algorithm using adaptive sparse representation of image. Elad improved this approach by separating the image into cartoon and texture layers, and sparsely represented these two layers by two incoherent overcomplete transforms. This approach can effectively fill in the region with composite textures and structures, especially in the application of missing block completion. However, similar to the diffusion based approach, it may fail to recover structure or introduce smooth effect when filling large missing region. 1.4 PROPOSED APPROACH This report focuses on the examplarbased inpainting algorithm through patch propagation. The two basic procedures of patch propagation are patch selection and patch inpainting. In the patch selection, a patch on the missing region boundary with the highest priority is selected for further inpainting. The priority is defined to encourage the fillingin of patches on structure such that the structures are more quickly filled than the textures, then missing region with composite structures and textures can be better inpainted . Traditionally, the patch priority is defined based on the inner product between isophote direction and the normal direction of the missing region boundary. In the patch inpainting, the selected patch is inpainted by the candidate patches (i.e., examplars) in the known region. To better address the problems of patch selection and patch inpainting, two novel concepts of patch sparsity of natural image, i.e., patch structure sparsity and patch sparse representation, are proposed and applied to the examplarbased inpainting algorithm. First, we define a novel patch priority based on the sparseness of the patch’s nonzero similarities to its neighboring patches. This sparseness is called structure sparsity. It is based on the observation that a patch on the structure has sparser nonzero similarities with its neighboring patches compared with the patch within a textured region. Compared with the priority defined on isophote, this definition can better distinguish the texture and structure, and be more robust to the orientation of the boundary of missing region. Second, to inpaint a selected patch on the boundary of missing region, a sparse linear combination of examplars is used to infer the patch in a framework of sparse representation. This linear combination of patches are regularized by the sparseness prior (l° regularization) on the combination coefficients. It means that only very few examplars contribute to the linear combination of patches with nonzero coefficients. This representation is called patch sparse representation. The patch sparse representation is also constrained by the local patch consistency constraint. This model extends the patch diversity by linear combination and preserves texture without introducing smooth effect by sparseness assumption. More importantly, the inpainted patches are more consistent with their surrounding textures or structures due to the local patch consistency constraint. In summary, the structure sparsity and patch sparse representation at the patch level constitute the patch sparsity. The patch structure sparsity is inspired by the recent progress on the research of sparseness prior of natural image. The previous sparseness prior generally models the sparseness of image’s nonzero features, e.g., gradients or filter responses. This kind of sparseness prior has been successfully applied to the image denoising, superresolution, inpainting, deblurring and so on. The structure sparsity also models the sparsity of natural image. However, it models the sparseness of nonzero similarities of a patch with its neighboring patches instead of highfrequency features. The patch sparse representation is inspired by the recent progress on sparse representation, which assumes that the image or signal is represented by the sparse linear combination of an overcomplete library of bases or transforms under sparseness regularization. This framework has been widely applied to image denoising, edge detection , recognition, superresolution, texture synthesis, etc., and achieved stateoftheart performance. The idea of sparse representation is introduced to the examplarbased inpainting algorithm under the assumption that the missing patch can be represented by the sparse linear combination of candidate patches. Then a novel constrained optimization model is designed for patch inpainting. CHAPTER 2 ALGORITHM OVERVIEW Given an image I with the missing region Ω and the known region Ω̄, the task of image inpainting is to fill in the target region (i.e., the missing region Ω) using the image information in the source region (i.e., the known region Ω̄). The boundary of the target region is denoted by δΩ, which is called the fillfront in the examplarbased inpainting algorithm. Ψp is a patch centered at a pixel p . The main procedures of the proposed examplarbased inpainting algorithm are illustrated in Fig. 1. This algorithm is based on patch propagation by inwardly propagating the image patches from the source region into the interior of the target region patch by patch. In each iteration of patch propagation, the algorithm is decomposed into two procedures: patch selection and patch inpainting. Fig 1 In the procedure of patch selection, patch priority should be defined to encourage the fillingin of patches on the structure with higher priority. Structure sparsity is defined by measuring the sparseness of the similarities of a patch with its neighboring patches. Then patch priority is defined using the structure sparsity. In the example shown in Fig. 1(a), the patches Ψp and Ψp are centered at pixel p and p which lie in the edge structure and the flat texture region respectively. The leftdown part of Fig. 1(a) shows the maps of their similarities with neighboring known patches. Obviously, the patch Ψp has sparser nonzero similarities; therefore, it has larger patch priority. The patch on the fillfront with the highest priority is selected to be inpainted firstly. In the procedure of patch inpainting, the selected patch on the fillfront should be filled in. Instead of using a single best match examplar or a certain number of examplars in the known region to infer the missing patch, it is assumed that the selected patch on the fillfront is the sparse linear combination of the patches in the source region regularized by l° sparseness prior. In the example shown in Fig. 1(b), the patch on the fillfront is inpainted by the sparse linear combination of candidate patches {Ψqk}k=1 to N weighted by coefficients {αk}k=1 to N, in which only very sparse nonzero elements exist. The neighboring patches in N(p)∩ Ω̄ are also used to constrain the appearance of patch Ψp by local patch consistency constraint. CHAPTER 3 INPAINTING BY PATCH SPARSITY 3.1 PATCH PRIORITY USING STRUCTURE SPARSITY The natural images are generally composed of structures and textures. A good definition of patch priority should be able to better distinguish the structures and textures, and also be robust to the orientation of the fillfront. A novel definition of patch priority is proposed to meet these requirements. We now introduce the key component of our definition of patch priority, i.e., structure sparsity. 3.1.1 STRUCTURE SPARSITY The structure sparsity is defined to measure the confidence of a patch located at structure instead of texture. Structure sparsity is inspired by the following observations: structures are sparsely distributed in the image domain, e.g., the edges and corners are distributed as 1D curves or 0D points in the 2D image domain. Nevertheless, the textures are distributed in 2D subregions of the image domain, which are less sparsely distributed. On the other hand, for a certain patch, its neighboring patches with larger similarities are also distributed in the same structure or texture as the patch of interest. Therefore, we can model the confidence of structure for a patch by measuring the sparseness of its nonzero similarities to the neighboring patches. The patch with more sparsely distributed nonzero similarities are prone to be located at structure due to the high sparseness of structures. Suppose Ψp is a patch on the fillfront δΩ, its neighboring patch Ψpj is defined as the patch that is in the known region and with the center pj in the neighborhood of pixel p , i.e., belongs to the set N(p) is a neighborhood window centered at p, which is set to be larger than the size of patch Ψp. Suppose P is a matrix to extract the missing pixels of Ψp , and P extracts the already known pixels of Ψp , then the similarity between Ψp and Ψpj is defined as where d(.,.) measures the mean squared distance, Z(p) is a normalization constant such that and is σ is set to 5.0 in this implementation. For the patch Ψp , we measure the sparseness of its similarities to the neighboring patches in region Ns(p) by (3) where . means the number of elements. N(p)is incorporated to restrict ρ(p) in the interval (0,1] , though its value is same for different patches. This definition embodies the fact that the larger sum of squared similarities in the larger region Ns means larger sparseness. We call the sparseness of patch similarities as the structure sparsity. Structure sparsity values of (a) Patch on corner. (b) Patch on edge. © Patch in texture. (d) Patch in flat region. For the definition of structure sparsity , the following conclusion is proved. Theorem 1: The structure sparsity ρ(p) for patch Ψp achieves the maximal value √(Ns(p)/N(p)) if a single nonzero similarity exists, and it achieves the minimal value √1/N(p) if all the similarities are same and equal to 1/Ns(p). Proof: It is observed that ρ(p) consistently increases with respect to W= Σ pj Є Ns(p) ωp,pj². To find the maximum and minimum values of ρ(p), we only need to compute the maximum and minimum values of W. Firstly, to find the minimum value of W, we minimize W under the normalization constraint Σ pj Є Ns(p) ωp,pj=1 . This can be achieved by Lagrangian multiplier method, i.e., maximizing: E(p) = W+λ(Σ pj Є Ns(p) ωp,pj²1) . It is easy to prove that W achieves minimal value when ωp,pj=1/Ns(p) for each pj є Ns(p). Then we maximize W . Due to the fact that 0≤ ωp,pj ≤1, so W≤1 . The equality holds when only a single ωp,pj equals to 1, and all the other similarities equal to 0. So W achieves its maximal value 1 when only a single similarity is nonzero and equals to 1. Finally, it is easy to derive the maximal and minimal values of ρ(p) by inserting the maximum and minimum values of W into equation 3. This theorem tells us that the structure sparsity achieves its maximum and minimum values when the patch similarities are distributed in the sparsest and smoothest fashion respectively, and the structure sparsity increases with respect to the sparseness of patch’s nonzero similarities to its neighboring patches. It is now investigated how the structure sparsity measures the structure confidence for different types of patches in the natural images. For the patch on the 0D corners [e.g., Fig. 2(a)], it is saliently distributed within the local region; therefore, it has the highest structure sparsity. Due to the sparsity of image edges, the patch on 1D edge [e.g., Fig. 2(b)] has similar patches sparsely distributed along the same edge; therefore, they have higher structure sparsity. However, for the texture patches [e.g., Fig. 2© and (d)], they have similar patches in the 2D local regions; therefore, they have smaller structure sparsity values. Under the guidance of structure sparsity, the patches located at structures (e.g., edges and corners) have higher priority for patch inpainting compared with the patches in texture regions. Fig. 3. Comparison of patch priority. (a) Process of inpainting using isophotebased priority . (b) Process of inpainting using structure sparsity based priority. 3.1.2 PATCH PRIORITY The final patch priority is defined by multiplying the transformed structure sparsity term with patch confidence term: P(p) = T[ζ,1] (ρ(p)).C(p). C(p) is the confidence of patch Ψp , which specifies the reliability of color or intensity in the patch. C(p)= ΣqΨp∩ Ω c(q)/Ψ(p) , where c(q) is the confidence of the color or intensity of pixel q , and initialized to 0 in the missing region or 1 in the known region. After each procedure of patch inpainting, the confidence of the newly filled pixels in the patch are updated by the confidence of the patch’s central pixel. T[ζ,1] is a linear transformation of from its original interval√(1/N(p),√Ns(p)/N(p) to the interval [ζ,1], where ζ is set to 0.2. This transformation is necessary to make the structure sparsity varies in a comparable scale with C(p). By multiplying these two terms in P(p) , the inpainting algorithm is encouraged to firstly inpaint the patch located at image structures (i.e., edges or corners) and with larger confidence of its colors or intensities, then the missing region with composite texture and structure can be more robustly inpainted . 3.2 COMPARISON WITH THE ISOPHOTE BASED PRIORITY It is shown here that structure sparsity based priority is more robust to identify the structure than the isophotebased definition , which uses the inner product of isophote direction and the normal direction of the fillfront. Fig. 3 presents an example of inpainting for an image with composite textures and illusory edge. Fig. 3(a) shows the process of inpainting using isophotebased priority, and Fig. 3(b) shows the process of inpainting using structure sparsity based priority. The texture synthesis technique is incorporated for both cases. Using isophotebased priority, the patch at the topright part of missing region has the larger priority because the isophote direction is nearly same to the orthogonal direction of the fillfront at its central pixel. For example, the patch Ψa in the texture region of the first image in Fig. 3(a) is with the highest priority, and the illusory edge is failed to be accurately recovered in the final result. However, structure sparsity based priority is able to robustly identify the structure regardless of the shape of fillfront. For example, the patch Ψb in Fig. 3(b) along structure is with the highest priority using structure sparsity based priority, and the missing region is inpainted perfectly in the final result. 3.3 PATCH INPAINTING USING PATCH SPARSE REPRESENTATION The patch Ψp on the fillfront with the highest patch priority is selected to be filled firstly. In the traditional examplarbased inpainting technique Ψp is filled by sampling the best match patch from the known region. Recently, a nonlocal means approach is proposed to fill in patch by the nonlocal means of several top similar patches instead of a single best match patch. Due to multiple samples are utilized, it can more robustly estimate the missing information and produce better result. However, it tends to introduce smooth effect in the recovered image. In this work, it is proposed a novel model to inpaint patch by the sparse combination of multiple examplars in the framework of sparse representation. This method achieves sharp inpainting result by sparseness prior on the combination coefficients, and achieves consistent inpainting results with the surrounding textures by the constraints on the patch appearance in local neighborhood. 3.3.1 PATCH SPARSE REPRESENTATION Given the patch Ψp, to be inpainted, a set of candidate patches {Ψq}, q=1 to N are sampled from the image source region, where N is the number of candidate patches for Ψp. The candidate patches are selected as the top most similar patches. Denote P as a matrix to extract the unknown pixels in patch Ψp . Basically, Ψp is approximated as the linear combination of {(Ψq},q=1 to N,i.e., Then the unknown pixels in patch Ψp is filled by the corresponding pixels in ψp, i.e., The combination coefficients α = {α1,α2,…….αN}are inferred by minimizing a constrained optimization problem in the framework of sparse representation. Since we have assumed that the patch Ψp is the sparsest linear combination of {Ψq}, q=1 to N, the objective of this constrained optimization problem is to minimize the lo norm, i.e., the number of nonzero elements in vector α. Next the constraints for the linear combination are introduced. The first type of constraint on the appearance of ψp,is called local patch consistency constraint. Firstly, we constrain that the estimated patch ψp should approximate the target patch Ψp over the already known pixels, i.e., where є is a parameter to control the error tolerance of this approximation. Secondly, it is further assumed that the newly filled pixels in the estimated patch should be consistent with the neighboring patches in appearance, i.e., where ωp,pj is same defined before. This constraint measures the similarity between the estimated patch and the weighted mean of the neighboring patches over the missing pixels. β balances the strength of the constraints in (6) and (7). It is set to 0.25 in this implementation. The local patch consistency constraint can be rewritten in a more compact formulation where The second type of constraint is that the summation of the coefficients vector α equals to one: Σi=1 to N, αi=1 . This constraint is widely used in the local linear embedding literature for invariance to transform when reconstructing the target patch ΨT from its neighboring candidate patches Under this constraint, when only one element in α is nonzero, the coefficient of that element must be one. Then the model will degrade to the same fashion as traditional examplarbased inpainting method , in which a single best match patch is selected for filling in the patch to be inpainted.Finally, the linear combination coefficients can be inferred by optimizing the following constrained optimization problem: This constrained optimization model can also be formulated as an energy minimization problem It is equivalent to the constrained optimization problem in (10) when proper γ and η are selected. 3.3.2 OPTIMIZATION ALGORITHM Generally, the lo norm regularized reconstruction model is hard to be solved due to its combinatorial nature. Matching pursuit (MP) or orthogonal matching pursuit (OMP) algorithm and basis pursuit (BP) algorithm can efficiently retrieve the sparse representation and approximate the optimal solution in a greedy fashion. Another method for optimizing the l o norm regularized model is to convexify the problem by l¹norm regularization. The l¹norm regularized reconstruction model is the wellknown Lasso in the statistical literatures. In applications, due to the simplicity of OMP algorithm, it is widely used in image sparse representation, and applied to image denoising, coding, edge detection, audio source separation, and so on. For this optimization problem in a novel algorithm to derive the sparse linear combination coefficients in a greedy fashion is proposed. Similar to the Matching Pursuit Algorithm, nonzero elements are selscted from the candidate set of patches Q={(Ψq}q=1 to N step by step. Suppose we have selected m nonzero candidate patches in the step m (denoted as Sm ={Ψq1,Ψq2,…..Ψqm}), so the sparse representation in this step is In the next step m+1, we select a new candidate patch Ψqm+1 from the remaining candidate patches in Q Sm. The patch with the best Local Patch Consistency is selected as the newly selected nonzero element, i.e., For each candidate patch Ψ є Q Sm , the combination coefficients are derived by optimizing This optimization problem (14) is well studied in the literature of Locally Linear Embedding (LLE) in manifold learning. Gram matrix G, is defined as G = (ΨT1  X)( ΨT1  X), where X is a matrix with columns ,{DΨq1,……DΨqm, DΨ}, and is a column vector of ones. Then it has a close form solution The procedure of selecting a patch in each step is iterated until the Local Patch Consistency Constraint (8) is satisfied or the value of ξ increases. Fig.6 Fig. 6 presents three examples in which the top corner region of pyramid, the crossing structure of window frame and the curved missing structures are removed. As shown in Fig. 6(b)–(d), the missing regions are gradually completed by the proposed method, and Fig. 6(d) are the inpainting results of proposed method, in which the removed structures are successfully filled in. In Fig. 6(e), present the results of the most related algorithm .The structures in rectangles are not perfectly recovered compared with our results. The keys to the success of proposed method in completing the complex structures are that, first, the sparsitybased priority better controls the filling order of patches. Second, the patch sparse representation improves the generalization ability of examplars over the single best match examplar . Fig. 7. Number of nonzero components for 200 patches in the second example of Fig. 8. Fig. 7 gives an example to illustrate the number of nonzero coefficients for 200 patches in the missing region of the second example in Fig. 8. It is shown that only sparse number of candidate patches are selected adaptively due to the sparseness constraint on the coefficients. That is the key difference to the previous work that a single best match patch or the combination of constant number of patches are used. CHAPTER 4 EXPERIMENTS AND COMPARISONS In this section, the proposed examplarbased patch propagation algorithm is tested on a variety of natural images. The algorithm is applied to the applications of scratch/text removal, object removal and block completion. The algorithm is compared with diffusionbased, examplarbased, and sparsitybased inpainting algorithms. In the following examples, the size of patch is set to 7×7, the size of neighborhood (i.e.,N(p) around in (1)) for computing patch similarities is set to 51×51, the error tolerance є is set to 25 times of the number of pixels in a patch, and the number of candidate patches is set to 25. 4.1 SCRATCH AND TEXT REMOVAL The proposed inpainting algorithm is compared with the diffusionbased and examplarbased inpainting algorithms for scratch and text removal. Due to the oversmoothing effect of diffusionbased approach for texture inpainting, the simultaneous texture and structure inpainting algorithm is selected as an improved version of the diffusionbased approach for comparison. The simultaneous texture and structure inpainting algorithm performs inpainting in the texture layer and structure layer simultaneously. In our implementation, the structure/texture decomposition method and the inpainting method in the structure layer are chosen as the same methods in the original paper. However, the texture layer is inpainted by Criminisi’s examplarbased algorithm , which is better for texture inpainting than the texture synthesis method. This algorithm is also compared with Criminisi’s examplarbased algorithm and Wong’s examplarbased algorithm, which are most related to this work. Fig. 8 presents five examples for scratch and text removal. The first row are the original nondegraded images. In the remaining rows, from the first to the fifth columns are the degraded images, results of simultanous texture and structure inpainting algorithm, examplarbased inpainting algorithm, Wong’s examplarbased inpainting algorithm and the proposed algorithm. Peak signaltonoise ratio (PSNR) between the inpainted images and the original images are measured for qualitative comparison. Furthermore, PSNR values in each color channel(R,G,B) are presented in the brackets. As shown in Fig. 8, the Criminisi’s algorithm produces sharp inpainting results shown in the third column. However, due to the fact that only a single best match patch is used, some unpleasant artifacts are introduced in the results. For example, the unwanted structure appears within the red rectangle of Criminisi’s result in the second row of Fig. 8. The Wong’s algorithm produces more pleasant results because more candidate patches are combined. For example, the unwanted structure shown in the red rectangle is alleviated in the result of Wong’s algorithm. The simultaneous texture and structure inpainting algorithm well recovers the texture and structure of the images, and achieves high PSNR values. However, it introduces blurring effect along structure caused by diffusion, For the proposed algorithm, the patch priority is defined more robustly, and the candidate patches are adaptively combined in the framework of sparse representation, it achieves sharp and consistently better inpainting results with the best PSNR values. 4.2 EFFECT OF PATCH SPARSITY ON INPAINTING PERFORMANCE In this section, it is quantitatively justified the improvement of inpainting performance caused by structure sparsity and patch sparse representation. Traditional Criminisi’s examplarbased inpainting algorithm is used as the baseline,then the performance improvement is measured after replacing isophotebased priority by structure sparsity based priority or(and) replacing the texture synthesis based patch inpainting by the sparse representation based patch inpainting. TABLE 1 Table I presents the performances of six inpainting algorithms: Wong’s examplarbased algorithm [13] (Wong), Crimimisi’s examplarbased algorithm (Crim), the approach using isophotebased priority and sparse representation based patch inpainting model in (Crim_Spar1), the approach using isophotebased priority and sparse representation based patch inpainting model in (Crim_Spar2), the approach using structure sparsity based priority and texture synthesis based patch inpainting (Spar_Crim), and the proposed inpainting algorithm using patch sparsity (Spar). It is shown that, the mean performances of Spar_Crim and Crim_Spar2 gain 1.27 and 3.27 dB over the baseline respectively. This implies that the patch inpainting using sparse representation model contributes more to the performance improvement than the structure sparsity based priority. If updating both of patch priority and patch inpaining by the proposed patch sparsity, the performance of Spar gains 4.16 dB over the baseline. The results of Wong’s algorithm ,gain 2.55 dB in mean performance over the baseline which is lower than (Crim_Spar2). The inpainting model in fourth column utilizes the isophotebased priority and the sparse representation model without local patch consistency constraint, so the performances of Crim_Spar1 are significantly worse than the performance of Crim_Spar2 and Spar. 4.3 OBJECT REMOVAL The proposed algorithm is now applied to inpaint the missing region after object removal. The proposed algorithm is also compared with the related examplarbased inpainting algorithms. Fig.9 Fig.9 shows examples. The first and second columns are the original images and the degraded images. The third to the fifth columns are the results of Criminisi’s algorithm, Wong’s algorithm and our proposed algorithm. In the results of Criminisi’s algorithm, the inpainted patches are not always consistent with the surrounding textures, for example the texture of trees occurs in the texture of water in the first example, and texture of grass appears in the texture of rock in the third example. The Wong’s algorithm uses several top best examplars to infer the unknown patch, so the results have less effect of patch inconsistency. However, it introduces smooth effect as shown in the results. As for the proposed algorithm, local patch consistency is constrained, so the inpainted patches are more consistent with the surrounding textures. In addition, the patch is inferred by the sparse combination of candidate patches, so the results have rare smooth effect in appearance. Fig.10 In Fig. 10, the proposed algorithm is compared with the semiautomatic inpainting algorithm and the Criminisi’s algorithm .The semiautomatic inpainting algorithm resolves the structure ambiguity in the missing region by utilizing the humanlabeled structures as the guidance, and achieves stateoftheart results for completing the highly complex structures. In the first example, our method automatically completes the large missing region after removing the car, and the result is comparable to the result, which uses humanlabeled structures as guidance. In the second example, the structures hidden by the horse are reasonably recovered by the algorithm guided by the labeled structures. However, the proposed algorithm only recovers the horizontal structures and fails to recover the vertical fence structures which are totally hidden by the object. This shows a limitation of proposed algorithm, i.e., it cannot recover the missing structures without any structure cue in the known region. In both examples, our results are significantly better than the results of other algorithms in which the completion results are not visually pleasant. Fig 11 The proposecd algorithm is also compared with the fragmentbased method. Both of the fragmentbased method and the proposed method achieve visually pleasant results in the first example. In the second example, the contour of apple is blurry and not visually pleasant. However, the proposed method recovers sharp and reasonable contour of apple compared with the original image before removal. The reason is that the sparse combination of patch examplars extends the representation ability of examplars and preserves the sharpness of structure at the same time. 4.4 MISSING BLOCK COMPLETION The proposed algorithm is also compared with the other sparse representation based inpainting algorithms. Guleryuz recovered the missing blocks by adaptively updating image sparse representation in the transform domain. Elad improved the approach by decomposing image into texture and structure layers, and recover each layer by sparse representation. Fadili proposed an expectation minimization (EM) based Bayesian model for inpainting using sparse representation. They have achieved excellent inpainiting results for completion of missing blocks, especially the blocks with size not larger than 16×16. Fig. 12 shows four examples for missing block completion. The first column shows the input images, and the second to the fifth columns show the results of Guleryuz’s algorithm, Elad’s algorithm and Fadili’s algorithm and the proposed algorithm. PSNR values are presented for performance comparison. All of these examples are with complicated missing structures, e.g., the structure of eaves in the second example, and the crossing of textures in the third and fourth examples. Generally, Elad’s algorithm performs better than Guleryuz’s algorithm due to the texture and structure decomposition. Fadili’s algorithm well recovers the structures; however, the inpainting results are blurry in appearance. In contrast, the proposed algorithm is an examplarbased approach, which is more powerful for recovering large missing regions with complicated structures, so it better recovers missing regions appeared in these examples. 4.5 EFFECT OF NUMBER OF CANDIDATE PATCHES The effect of the number of candidate patches on inpainting results is tested. The five test images in Fig. 8 are taken as examples, and measure the inpainting quality in PSNR with the increasing N from 10 to 55. The inpainting quality results are shown in Fig. 13. It is observed that, the mean PSNR values vary within a limited range of [24.28 , 24.42]; therefore, the inpainting quality is relatively stable to the number of candidate patches. Second, the algorithm performs best when N=25, and larger does not always mean higher performance. The reason might be that the candidate patches provide a subspace for the sparse linear combination in patch inpainting model. Setting larger N will include more irrelevant patches as candidate patches which may decrease the generalization ability of the model when inferring the unknown pixels of patches. Based on the above observations, the number of candidate patches in the inpainting model is set to 25 in this implementation. CHAPTER 5 IMPLEMENTATION DETAILS AND COMPUTATION TIME In this implementation, the patch similarities are incrementally computed only for the newly introduced patches on the fillfront in each iteration, and the similarities are also used for the computation of local patch consistency constraint in (7). On the other hand, only a small subset of candidate patches are used for the optimization of sparse representation model, which deceases its computational overhead. It takes 103 s to fill in the missing region with 5310 missing pixels in the first example of Fig. 6 using C++ programming language on Intel 2.0GHz CPU. CHAPTER 6 CONCLUSION A novel patch propagation based inpainting algorithm was proposed for scratch or text removal, object removal and missing block completion. The major novelty is that two types of patch sparsity were proposed and introduced into the examplarbased inpainting algorithm. Structure sparsity was designed by measuring the sparseness of the patch similarities in the local neighborhood. The patch with larger structure sparsity, which is generally located at the structure, tends to be selected for further inpainting with higher priority. On the other hand, the patch sparse representation was proposed to synthesize the selected patch by the sparsest linear combination of candidate patches under the local consistency constraint. Experiments and comparisons showed that the proposed examplarbased patch propagation algorithm can better infer the structures and textures of the missing region, and produce sharp inpainting results consistent with the surrounding textures. In the future, the humanlabeled structures can be incorporated into this framework in order to recover the totally removed structures CHAPTER 7 REFERENCES 1. “Image Inpainting by Patch Propagation Using Patch Sparsity” by Zongben Xu and Jian Sun. IEEE transactions on image processing, Vol 19, May 2010 Wong and J. Orchard, “A nonlocalmeans approach to examplar based inpainting,” presented at the IEEE Int. Conf. Image Processing, 2008. 2. B. Shen, W. Hu, Y. Zhang, and Y. Zhang, “Image inpainting via sparse representation,” in Proc. IEEE Int. Conf. Acoustics, Speech and Signal Processing, 2009, pp. 697–700. 3. J. C. Yang, J. Wright, T. Huang, and Y. Ma, “Image superresolution as sparse representation of raw image patches,” presented at the IEEE Computer Society Conf. Computer Vision and Pattern Recogition, 2008 4. M. J. Fadili, J. L. Starck, and F. Murtagh, “Inpainting and zooming using sparse representations,” The Comput. J., vol. 52, no. 1, pp. 64–79, 2009. Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion



seminar class Active In SP Posts: 5,361 Joined: Feb 2011 
05052011, 12:11 PM
Abstract
This paper introduces a novel examplarbased 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 examplarbased 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 traditionalexamplarbased 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 fillingin 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 curvaturedriven diffusion equation was proposedto realize the connectivity principle which does not holdin the TV model [4]. A joint interpolation of isophote directionsand graylevels 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 diffusionbased 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 examplarbasedinpainting 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 diffusionbased method and texture layerusing texture synthesis technique [9]. It overcomes the smootheffect of the diffusionbased inpainting algorithm; however, itis still hard to recover larger missing structures. Criminisi et al.[11] designed an examplarbased 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 fillingin of patches on the structure. Wu [12] proposed acrossisophotes examplarbased inpainting algorithm, in whicha crossisophotes patch priority term was designed based onthe analysis of anisotropic diffusion. Wong [13] proposed anonlocal means approach for the examplarbased 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 examplarbased inpaintingalgorithms [14]–[16]were also proposed for image completion.Compared with the diffusionbased inpainting algorithm, theexamplarbased inpainting algorithms have performed plausibleresults for inpainting the large missing region. Download full report gr.xjtu.edu.cn:8080/upload/PUB.3251.2/inpainting_TIP.pdf 


