International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering
MenuISSN ONLINE(2278-8875) PRINT (2320-3765)
ISSN ONLINE(2278-8875) PRINT (2320-3765)
Ashish Dewangan1, Indu Sahu2
|
| Related article at Pubmed, Scholar Google |
Visit for more related articles at International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering
Inpainting methods play a vital role in various applications such as object removal, scratch removal, Image restoration. The filling-in missing region in an image is called image Inpainting. Time to time different algorithms came into existence for Inpainting missing region of an image. This paper introduces a novel framework for examplar based Inpainting. This paper presents a novel combination of patch- based inpainting and single image superresolution algorithm. The advantage of this approach is that it is easier to inpaint low-resolution images than highresolution ones.
Keywords |
| Examplar-based, Filling-in, Image Inpainting, Patch-based Inpainting, super-resolution based inpainting. |
INTRODUCTION |
| Currently, the image inpainting technology is a hotspot in computer graphics and has many applications such as renovation of old films, object elimination in digital photos, red eye alteration, super- resolution, compression, image coding and transmission. Image Inpainting is the method of restoring lost/selected parts of an image based on the background information in a visually possible way. Therefore the objective for image inpainting is not to recover the original image, but to create some image that has a close resemblance with the original image. Image inpainting techniques can be classified into two main categories. The first category concern diffusion-based approaches which propagate level lines or linear structures via diffusion based on partial differential equations (PDE) [1, 2]. The second type of approach concerns exemplar-based methods which sample and copy best match texture patches from the known image neighbourhood [3-6]. |
| Some limitation of above approaches has lead to the development of hierarchical approach of super-resolution based inpainting. This paper briefly describes some image inpainting methods. This paper covers some selected research works published between 2007 and 2013 and ordered them chronologically in the following sections. |
LITERATURE REVIEW |
A. Olivier Le Meur and Christine Guillemot (2013) |
| Olivier Le Meur et al. proposed a framework which combines inpainting and super-resolution.Intially, a low-resolution image is built from the original picture. Then a non-parametric patch sampling method (inpainting algorithm) is used to fill-in the hole of the low-resolution picture. Then the quality of the inpainted regions is improved by using a singleimage SR method. The influence of different priority terms on the quality of inpainted images is first studied. A similarity metric based on a weighted Bhattacharya distance is proposed. |
| A low resolution image is inpainted using a K-NN (K Nearest Neighbours) examplar-based method [4]. Similarities between the K-NN low-resolution and high-resolution patches are first learnt from the input image and stored in a dictionary. These similarities are then used to find the missing pixels at the higher resolution following some principles used in single-image super-resolution methods. The proposed method framework thus allows reducing the computational complexity and allows working with dominant orientation of image structure. |
B. Yunquing Liu and Vicent Caselles (2013) |
| Yunqiang Liu et al. proposed a reformulation of the examplar-based approach as a discrete global optimization problem. The proposed energy functional is written in terms of the offset map (assigning to each point of the inpainting domain a corresponding point in the known part of the image). The energy term consists data attachment term to guarantee the continuity of the reconstruction at the boundary of the inpainting domain and a term that favours a spatially coherence in the image completion. |
| The proposed method use a multiscale graph cuts algorithm to solve the energy minimization problem in which a feature vector representation is introduced to compare patches at low resolution, to recompense the information loss. The proposed method reduces the computational cost, helps to eliminate ambiguities at low resolution and improves accuracy of offset map and show better performance for block recovery. |
C. R. Mart´inez Noriega, A. Roumy, G. Blanchard(2012) |
| R. Mart´Ãâñnez-Noriega et al. proposed an improvement to the priority order in addition with an edge detection algorithm. To solve the global inpainting optimization problem a scheduling is proposed that requires the computation of many distances at the initialization. For each patch located at the boundary between the known and the unknown region, the distance between this patch and all known patches are computed. This paper also concerns spatial coherence. It includes the probability density function (pdf) of the patches used for measuring the similarity. |
| The proposed method uses cross-validation to compute the threshold which distinguishes texture from structure patches, and the variance that controls the amplification of the data term. To choose K-similar patches it uses combination of sum of square distance (SSD) and the Hellinger distance. The pdfs of patches are computed with the normalized histograms of the patches. The normalization is given according to the number of elements of each patch and the number of color dimensions. Once the K nearest patches is found either using the texture or structure definition, it uses a linear combination of the patches to finally obtain the prediction of the missing pixels. |
| The proposed method provides a better completeness of linear edges and a more natural look of the missing region. Its result also provide more visual coherence image. Moreover, the proposed method has significant lower computation load than most of the algorithm. |
D. Olivier Le Meur, Josselin Gautier, Christine Guillemot (2011) |
| Olivier Le Meur et al. proposed a novel inpainting algorithm combining the advantages of PDE-based schemes and examplar-based approaches. The proposed algorithm based on the use of structure tensors to define the filling order priority and template matching. The structure tensors are computed in a hierarchic manner whereas the template matching is based on a K-nearest neighbour algorithm. |
| The main contribution of proposed method involves fourfold: the first one concerns the use of structure tensors to define the filling order. Second is to use a hierarchical approach to be less dependent on the singularities of local orientations. Third is related to constraining the template matching to search for best candidates in the isophote directions. Fourth is a K-nearest neighbour approach to compute the final candidate. Initially, a filling priority is computed for each patch to be filled. Once the priority has been computed for all unknown pixels located, pixels are processed in decreasing order of priority. This filling order is called percentile priority-based concentric filling (PPCF). Once the pixel having the highest priority is found, a template matching based on the sum of squared differences (SSD) is applied to find a plausible candidate. A K-nearest neighbour search algorithm is also used to compute the final candidate to improve the robustness. |
E. Mei Gong, Kun He1, Jiliu Zhou, Jian Zhang (2011) |
| Mei Gong el al. proposed a single colour image super-resolution algorithm through neighbour embedding [9] and construct a quaternion model (define complex form) to express colour image. When the elements of a matrix are quaternion, then the matrix is called a quaternion matrix. This quaternion matrix model of a colour image converts an original three-dimensional colour image matrix to a two-dimensional matrix. In this paper, the three imaginary parts of quaternion are taken to code the R, G, B colour components of an image, and a quaternion matrix model is adopted to represent a three-dimension colour image. |
| The overall algorithm is divided in to three phases, firstly, each quaternion matrix is divided into small overlapping patches, and each image patches is represented by a quaternion feature vector [10].Then find the set of K nearest neighbours among all patches from each low-resolution image and compute the optimal reconstruction weights that minimize the reconstruction error. Secondly, replace the feature vector of each low-resolution image by its corresponding high-resolution images and compute the estimated value. Finally, stitch all the patches of high resolution according to the corresponding coordinates, and enforce the local compatibility and smoothness constraints for the overlapping regions of patches to construct the target HR quaternion matrix model and convert the quaternion matrix model back to RGB space, and then the final HR target image is reconstructed. |
| The proposed algorithm through neighbour embedding [9] applied on quaternion matrix improve the correlation of the three components and preserve the complete information of the colour image, and avoid colour distortions to some extent. |
F. Zongben Xu,Jian sun(2010) |
| Zongben Xu et al. examplar based image inpainting algorithm through patch propagation. 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. For each iteration of patch propagation, the algorithm is decomposed into two procedures: patch selection and patch inpainting. In patch selection patch priority is defined using structure sparsity (measures the sparseness of the similarities of a patch with its neighbouring patches) to encourage the filling-in a patches on the structure with higher priority. In patch inpainting, the selected patch on the fill-front should be filled in. Selected patch on the fill-front is the sparse linear combination of the patches in the source region regularized by sparseness prior. This proposed structure sparsity based priority is able to robustly identify the structure regardless of shape of fill-front. 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. Also, patch-based filling helps achieve 1) speed efficiency, 2) accuracy in the synthesis of texture (less garbage growing), and, finally, 3) accurate propagation of linear structures. |
G. Aurélie Bugeau, Marcelo Bertalmío, Vicent Caselles (2010) |
| Aurélie Bugeau et al. proposed an algorithm by combining three basic techniques: copy-and-paste texture synthesis, geometric partial differential equations (PDEs), and coherence among neighbouring pixels and combines them in one energy function (variational model). This algorithm must be applied to an image where there are no valid values inside the mask image. To search the best patch among all the patches of the image, proposed a method called as pruning [11].The number of candidates kept for each pixel is a fixed parameter set by the user. These candidates are simply the ones that had the highest similarity to the pixel during the initialization step. The proposed method also introduces a multi-resolution scheme which works as follows: first, a Gaussian pyramid is built from the original image. Next, the iterative inpainting algorithm is applied on the smallest image. The result obtained on this image is then used as the initialization for the second level of the pyramid, and so on. The result obtained with these method contain less blur and able to correctly inpaint the covered lanterns, the text on these lanterns and red and white striped bars. |
H. Daniel Glasner, Shai Bagon, MIchal Irani (2009) |
| Daniel Glasner et al. proposed a two families of super resolution methods: classical multi-image super-resolution and example based super-resolution and show how this combined approach can be applied to obtain super resolution from as little as a single image low-resolution image, without any additional external observation. This approach is based on the observation that patches in a natural image tend to redundantly recur many times inside the image, both within the same scale, as well as across different scales. Recurrence of patches within the same image scale (at sub pixel misalignments) gives rise to the classical super-resolution, whereas recurrence of patches across different scales of the same image gives rise to example-based super-resolution. |
| Firstly, each low resolution image is assumed to have been generated from high-resolution source image by a blur and sub sampling process. Patches in the input low-res image are searched for in the down-scaled versions of low-res image. When a similar patch is found, its parent patch is copied to the appropriate location in the unknown highresolution image with the appropriate gap in scale. A learned (copied) high-res patch induces classical SR linear constraints on the unknown high res intensities in the target high-resolution image. The support of the corresponding blur kernels are determined by the residual gaps in scale between the resolution levels of the ’learned’ high-res patches and the target resolution level of high-res image. |
I. Shengyang Dai, Mei Han, Wei Xu, Ying Wu, YIhong Gong, Aggelos K. Katsaggelos (2009) |
| Shengyang Dai et al. presented an extended method for single image super-resolution based on interpolation technique which combines soft edge cuts method to measure the smoothness of soft edges in an intensity image and to handle various edges in color image and alpha matting technique for colour image super-resolution. It introduces a Geocuts method [13] which can approximate the Euclidean length of a hard edge with a cut metric on the image grid. The overall algorithm is divided into four phases: first, Decompose low-resolution image by using the spectral matting algorithm [14] to get its alpha-channel image description. Second, compute the low-resolution adaptive factor for each pixel in each colour channel. Third, compute the high-resolution adaptive factor by up-sampling with the bicubic interpolation and the scaling factor s. For each colour channel, optimize the adaptive Soft-cuts objective function to obtain the high resolution result. |
| The proposed SR algorithm has the following benefits: |
| 1. Due to the geometry property of the proposed Soft Cuts measure, the length of all image level lines can be minimized simultaneously for the super-resolution task. Thus, results with smooth edges can be obtained. |
| 2. All three colour channels are utilized simultaneously with the alpha- channel SR scheme, and the adaptive strategy provides a unified treatment of edges with different contrasts and scales. |
J. Ji Liu, Przemyslaw Musialski, Peter Wonkal, Jieping Ye (2009) |
| Ji Liu et al. proposed an algorithm to estimate missing values in tensors of visual data. The values can be missing due to problems in the acquisition process, or because the user manually identified unwanted outliers. The proposed methodology extend the matrix case to the tensor case by laying out the theoretical foundations for tensor completion together with a strong convex optimization algorithm, called LRTC(low rank tensor completion).Initially it introduce an original definition of the trace norm for tensors in order to define a convex optimization for tensor completion. Moreover it employs a relaxation technique to separate the dependant relationships and use the block coordinate descent (BCD) method to achieve a globally optimal solution. |
| This algorithm may be used for video compression and video in-painting. The core idea of video compression is to remove individual pixels and to use tensor completion to recover the missing information. Similarly, a user can eliminate unwanted pixels in the data and use the proposed algorithm to compute alternative values for the removed pixels. |
K. Julia A. Dobrosotskaya,, Andrea L. Bertozzi (2008) |
| Andrea L. Bertozzi et al. presented a new variational method for blind deconvolution of images and inpainting. This paper combines the basic geometric framework of diffuse interface methods with the nonlocality of wavelets. The main points of the algorithm are: Wavelet basis functions are natural candidates due to their localized structure and ability to represent images efficiently. In the wavelet-based technique, one can employ the discrete wavelet transform to speed up the method. |
| Wavelet techniques are common in signal processing making them a good candidate for implementation. Create a technique that can be easily extended from binary images to grayscale. It describes a model for inpainting binary images using a modified Cahn–Hilliard equation which has a number of applications for high contrast images, including inpainting of degraded text, super-resolution of images, and continuation of roads on aerial photographs. The model has two scales, the diffuse interface scale, on which it can accomplish topological transitions, and the feature scale of the image. |
L. Nikos Komodakis, Georgios Tziritas (2007) |
| Nikos Komodakis et al. (2007) presented a new exemplar-based framework which treats image completion, texture synthesis, and image inpainting in a unified manner. In order to be able to avoid the occurrence of visually inconsistent results, it poses all of the above image-editing tasks in the form of a discrete global optimization problem. The objective function of this problem is always well-defined, and corresponds to the energy of a discrete Markov random field (MRF). For efficiently optimizing this MRF, a novel optimization scheme, called priority belief propagation (BP), is then proposed, which carries two very important extensions over the standard BP algorithm: priority-based message scheduling and dynamic label pruning. These two extensions work in cooperation to deal with the intolerable computational cost of BP, which is caused by the huge number of labels associated with our MRF. They can, therefore, be applied to any MRF, i.e., to a very wide class of problems in image processing and computer vision, thus managing to resolve what is currently considered as one major limitation of the BP algorithm: its inefficiency in handling MRFs with very large discrete state spaces. |
CONCLUSION |
| In this paper we review the different algorithms for removing objects and inpainting damaged images. We discuss a variety of image Inpainting techniques such as texture synthesis based inpainting, PDE based inpainting, Exemplar based inpainting and semi-automatic and fast inpainting techniques. From this survey, a number of shortcomings and limitations were highlighted in each and every technique. The analysis proved that the exemplar based image inpainting will create better results for Inpainting the huge missing region also that these algorithms can inpaint both the formation and textured image efficiently. In this we also studied different kind of priors/regularization methods and corresponding optimization techniques for multi-frame and single-frame super resolution image reconstruction. This approach is numerically limited only to small increases in resolution .These limitations have lead to the development of Example- Based Super-Resolution algorithm. |
References |
|