17-11-2012, 03:46 PM
IMAGE COMPLETION
[attachment=40029]
INRODUCTION
The removal of object or the retrieval of damaged portion in a given image, known as IMAGE COMPLETION, is an image portion task in photo editing and video post processing.
The problem of image completion can be loosely defined as follows:
Given an image which is incomplete, i.e., it has missing region ,try to fill its missing parts such a way that a visually plausible outcome is obtained at the end although starting the image completion problem is very simple, the task of actually trying to successfully solve it, is far from being a trivial thing to achieve. Ideally, any algorithm that designed to solve the image completion problem should have the following characteristics:
1. It should be able to successfully complete complex natural images.
2. It should also be able to handle incomplete images with large missing parts
3. All these should take place in a fully automatic manner, i.e., without intervention the user.
Also, ideally we would like any image completion algorithm to be able to handle the related problem of texture synthesis, as well.
We assume that foreground elements or background regions are roughly marked with an image editing tool, or a more accurate channel is extracted using a matting tool. This defines an inverse matte that partitions the image into three regions: the known region, where i =1; unknown region, where i =0; and, optionally, a gray region, where 0 <¯ i < 1 for each pixel i, and “inverts” the common definition of trimaps that are generated in the process of pulling a matte and foreground elements from an image. We require a conservative inverse matte that, at least, contains the entire extracted region. As in digital image matting, the regions of the inverse matte are not necessarily connected. The inverse matte defines a confidence value for each pixel. Initially, the confidence in the unknown area is low. However, the confidence of the pixels in the vicinity of the known region is higher. The confidence values increase as the completion process progresses. Our approach to image completion follows the principles of figural simplicity and figural familiarity. Thus, an approximation is generated by applying a simple smoothing process in the low confidence areas. The approximation is a rough classification of the pixels to some underlying structure that agrees with the parts of the image for which we have high confidence. Then the approximated region is augmented with familiar details taken by example from a region with higher confidence.
All of these processes are realized at the image fragment level. A fragment is defined in a circular neighborhood around a pixel. The image of the underlying structure. Image completion proceeds in a multiscale fashion from coarse to fine, where first, a low resolution image is generated and then the results serve as a coarse approximation to the finer level. For every scale we consider neighborhoods in level sets from high to low confidence. the confidence and color values at different time steps in each scale. At each step, a target fragment is completed by adding more detail to it from a source fragment with higher confidence. Typically, the target fragment consists of pixels with both low and high confidence. The pixel values which are based on the approximation generally have low confidence, while the rest of the fragment has higher confidence. For each target fragment we search for a suitable matching source fragment, as described in Section 5, to form a coherent region with parts of the image which already have high confidence. The search is performed under combinations of spatial transformations to extend the training set and make use of the symmetries inherent in images. The source and target fragments are composited into the image as described in Section 6. The algorithm updates the approximation after each fragment composition. As fragments are added, the mean confidence of the image converges to one, completing the image. A high-level description of our approach appears In the pseudocode, the following terms are emphasized:
(i) approximation,
(ii) confidence map,
(iii) level set,
(iv) adaptive neighborhood,
(v) search, and
(vi) composite.
These are the building blocks of our technique.
CHAPTER-2
DIFFERENT METHODS OF IMAGE COMPLETION
It has, thus, attracted a considerable amount of research over the last years. Roughly speaking, there have been three main approaches so far, for dealing with the image completion problem
1. Statistical-based method
2. PDE-based method
3. Exemplar-based method
4. Fast Query for exemplar based method
In order to briefly explain the main limitations of current state-of –the-art method for image completion. next we provide a short review of related work for each of three classes mentioned above.
2.1 STATISTICAL –BASED METHOD
These methods are mainly used for the case of texture synthesis. typically, what these methods do is that given an input texture, they try to describe it by extracting some statistical through the use of compact parameter statistical model eg., wave let coefficients, color histogram.
In order to synthesize a new texture, these methods typically start with an output image containing pure noise and keep perturbing that image until its statistical match the estimated statistics of the input texture.
The main draw back of this method is that are based on parametric statistical model is that, are applicable only to the problem of texture synthesis, and not to the general problem of image completion ,however, even in there stricter case of texture synthesis they can synthesis only texture which are highly stochastic, and usually fail to do so for texture containing structure ,as well. Nevertheless, in case where parametric models are applicable .
2.1.1ADVANTAGES:
1. It allow great flexibility with respect to the modification of texture properties
2. It can edit speed, as well as other properties of a video texture by modifying the parameters of the statistical model
3. this method s can be very useful for the process which is reverse to texture synthesis, i.e., the analysis of textures.
2.1.2DISADVANTAGES:
1. This method applicable only to the problem of texture synthesis, and not to the general problem of texture synthesis, and not to the general problem of image completion.
2. In the restricted case of texture synthesis, they can synthesize only textures which are highly stochastic, and usually fail to do so for textures containing structure.
2.2 PDE-BASED METHODS:
This method fill the missing region of an image through a diffusion process, by smoothly propagating information from the boundary towards the interior of the missing region. According to these techniques, the diffusion process is simulated by solving partial difference equations(PDE),which is typically nonlinear and of higher order. this class of method has been first introduced by BERTALMIO in which case author were trying to full a hole in an image by propagating image laplacians in the isophote direction. Their algorithm was trying to mimc the behavior of professional restores in image restoration. In another case, the partial differential equations, that have been employed for the image filling process
Recently Bertalmio have proposed to decompose an image into two components. The first component is representing structure and is filled by using a PDE based method . while the second component represents texture and is filled by use of texture synthesis method .
2.2.1 ADVANTAGES:
1. It able to handle image that contain possibly large missing parts.
2. it able to fill arbitrarily complex natural images, i.e., image containing texture, structure or even a combination of both.
DISADVANTAGES:
1. This method suitable for missing part of image consist of thin, elongated regions.
2. PDE-based method implicitly assume that the content of missing region is smooth and non textured, they usually over smooth and introduce blurring arifacts.
EXEMPLAR –BASED METHOD:
CRIMINISI proposed an exemplar-based image completion algorithm. This method computes the priority of patches to be synthesized through a best-first greedy strategy which depends upon the priority assigned to each patch on the filling-front,wher the patch filling order is determined by the angle between the isophote direction and normal direction of filling front. this algorithm works well in large missing region and texture region.
Exemplar based techniques for texture synthesis are either pixel-based or patch based, meaning that the final texture was synthesized one patch at a time .