IMAGE IMPAINTING BY PATCH PROPAGATION USING PATCH SPARSITY
#1

IMAGE IMPAINTING BY PATCH PROPAGATION USING PATCH SPARSITY


Presented By:
Tiya Cyriac
S7 AE
Roll No:68
College Of Engineering , Trivandrum
2007-11 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 non-zero 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 nonlocal-means 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 super-resolution
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:
http://filesonicfile/21413165/IMAGE IMPAINTING_2003.ppt
Reply
#2

ABSTRACT

This report introduces a novel examplar-based 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 examplar-based 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 examplar-based 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:
http://mediafire?hux1nnglhgs448f

CHAPTER 1
INTRODUCTION

The filling-in 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 curvature-driven diffusion equation was proposed to realize the connectivity principle which does not hold in the TV model. A joint interpolation of isophote directions and gray-levels 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 diffusion-based 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 examplar-based 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 diffusion-based method and texture layer using texture synthesis technique. It overcomes the smooth effect of the diffusion-based inpainting algorithm; however, it is still hard to recover larger missing structures. Criminisi designed an examplar-based 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 filling-in of patches on the structure. Wu proposed a cross-isophotes examplar-based inpainting algorithm, in which a cross-isophotes patch priority term was designed based on the analysis of anisotropic diffusion. Wong proposed a nonlocal means approach for the examplar-based 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 examplar-based inpainting algorithms were also proposed for image completion. Compared with the diffusion-based inpainting algorithm, the examplar-based 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 over-complete 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 examplar-based 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 filling-in 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 examplar-based 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, super-resolution, 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 high-frequency 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 over-complete library of bases or transforms under sparseness regularization. This framework has been widely applied to image denoising, edge detection , recognition, super-resolution, texture synthesis, etc., and achieved state-of-the-art performance. The idea of sparse representation is introduced to the examplar-based 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 fill-front in the examplar-based inpainting algorithm. Ψp is a patch centered at a pixel p .
The main procedures of the proposed examplar-based 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 filling-in 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 left-down 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 fill-front with the highest priority is selected to be inpainted firstly.
In the procedure of patch inpainting, the selected patch on the fill-front 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 fill-front 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 fill-front 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 fill-front. 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 1-D curves or 0-D points in the 2-D image domain. Nevertheless, the textures are distributed in 2-D sub-regions 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 fill-front δΩ, 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 0-D 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 1-D 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 2-D 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 isophote-based definition , which uses the inner product of isophote direction
and the normal direction of the fill-front.
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 isophote-based 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 isophote-based priority, the patch at the top-right part of missing region has the larger priority because the isophote direction is nearly same to the orthogonal direction of the fill-front 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 fill-front. 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 fill-front with the highest patch priority is selected to be filled firstly. In the traditional examplar-based 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 examplar-based 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 well-known 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 sparsity-based 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 examplar-based 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 diffusion-based, examplar-based, and sparsity-based 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 diffusion-based and examplar-based inpainting algorithms for scratch and text removal. Due to the over-smoothing effect of diffusion-based approach for texture inpainting, the simultaneous texture and structure inpainting algorithm is selected as an improved version of the diffusion-based 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 examplar-based algorithm , which is better for texture inpainting than the texture synthesis method. This algorithm is also compared with Criminisi’s examplar-based algorithm and Wong’s examplar-based 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, examplar-based inpainting algorithm, Wong’s examplar-based inpainting algorithm
and the proposed algorithm. Peak signal-to-noise 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
examplar-based inpainting algorithm is used as the baseline,then the performance improvement is measured after replacing isophote-based 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 examplar-based algorithm [13] (Wong), Crimimisi’s examplar-based algorithm (Crim), the approach using isophote-based priority and sparse representation based patch inpainting model in (Crim_Spar1), the approach using isophote-based 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 isophote-based 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 examplar-based 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 semi-automatic inpainting algorithm and the Criminisi’s algorithm .The semi-automatic inpainting algorithm resolves the structure ambiguity in the missing region by utilizing the human-labeled structures as the guidance, and achieves state-of-the-art 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 human-labeled 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 fragment-based method.
Both of the fragment-based 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 examplar-based 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 fill-front 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 examplar-based 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 examplar-based 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 human-labeled 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 nonlocal-means 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 super-resolution 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.
Reply
#3

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
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page
Popular Searches: survival project download patch, yubashree from fill up, ppt on rectangular patch antenna, oxford university patch, image completion with structure propagation, download patch implementation of saodv, project patch family,

[-]
Quick Reply
Message
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  A Digital Watermark Based on The Wavelet Transform and its Robustness on Image project topics 1 2,343 19-12-2012, 11:48 AM
Last Post: seminar details
  IMAGE AUTHENTICATION TECHNIQUES seminars report electronics seminars 6 8,553 15-11-2012, 12:24 PM
Last Post: seminar details
  Seminar Report on Image Authentication Techniques mechanical wiki 1 3,636 15-11-2012, 12:24 PM
Last Post: seminar details
  Digital image watermarking capacity and detection error rate computer science crazy 1 2,534 20-10-2012, 01:27 PM
Last Post: seminar details
  AN APPLICATION OF MORPHOLOGICAL IMAGE PROCESSING TO FORENSICS project topics 3 5,388 18-10-2012, 12:53 PM
Last Post: seminar details
  Image Steganography Technique Based on Wavelet Transform science projects buddy 2 3,062 06-10-2012, 01:25 PM
Last Post: seminar details
  Introduction of Digital Image Processing: computer girl 0 836 07-06-2012, 05:54 PM
Last Post: computer girl
  An Application of Image Processing For EYE WRITER computer girl 0 1,136 07-06-2012, 01:07 PM
Last Post: computer girl
  An Image Secret Sharing Method computer girl 0 878 04-06-2012, 05:26 PM
Last Post: computer girl
  REAL TIME IMAGE PROCESSING APPLIED TO TRAFFIC QUEUE DETECTION ALGORITHM Full report computer science technology 15 17,175 06-03-2012, 12:05 PM
Last Post: ravikumar.r

Forum Jump: