Image Completion Approaches using Statistics of Pixel Matching

Download Full-Text PDF Cite this Publication

Text Only Version

Image Completion Approaches using Statistics of Pixel Matching

(Image Removal by Pixel Matching)

  1. T. Venkata Subramanian

    Computer Science And Engg Jeimathajee College Of Engg (Jmce) Kanchipuram

    Tamil Nadu

    B. Tamizh Selvan

    Computer Science And Engg

    Jei Mathajee College Of Engg (Jmce) Kanchipuram


    R. Prakash

    Computer Science And Engg

    Jei Mathajee College Of Engg (Jmce) Kanchipuram


    Abstract Image completion involves filling missing parts in images.In this paper we address this problem through novel statistics of similar patches.We observe that if we match similar patches in the image and obtain their offsets,the statistics of these offsets are sparsely distributed.We further observe that a few dominant offsets provide reliable information for completing the image.Such statistics can be incorporated into both matching-based and graph-based methods for image completion.Experiments show that our method yields better results in various challenging cases,and is faster than existing state-of-the-art methods.

    Keywords: Image completion, image inpainting, natural image statistics


IMAGE completion involves the issue of filling missing parts in images. This is a non-trivial task in computer vision/graphics: on one hand, the completed images are expected to be visually plausible and has little noticeable artifacts; on the other hand, the algorithm should be efficient,because in practice an image completion tool is often applied with user interactions and needs quick feedbacks.For

todays consumer-level multi-mega-pixel cameras,high- quality and fast image completion is still a challenging problem.

One category of image completion methods are diffusion- based . These methods solve Partial Differential Equations (PDE) or similar diffusion systems, so as to propagate colors into the missing regions.They are mainly designed for filling narrow or small holes (also known as inpainting ). They work less well for large missing regions due to the lack of semantic texture/structure synthesis.

Another category of image completion methods are exemplar-based. They perform more effectively for large

holes. In this paper, we further categorize exemplar-based methods into two groups: matching-based and graph-based.

Matching-based methods explicitly match the patches in the unknown region with the patches in the known region, and copy the known content to complete the unknown region.


Java is a programming language originally developed by James Gosling at Sun Microsystems now a subsidiary of Oracle Corporation, and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities. Java applications are typically compiled to bytecode (class file) that can run on any Java Virtual Machine (JVM) regardless of computer architecture. Java is general-purpose, concurrent, class-based, and object-oriented, and is specifically designed to have as few implementation dependencies as possible. It is intended to let application developers "write once, run anywhere".

The original and reference implementation Java compilers, virtual machines, and class libraries were developed by Sun from 1995. As of May 2007, in compliance with the specifications of the Java Community Process, Sun relicensed most of their Java technologies under the GNU General Public License. Others have also developed alternative implementations of these Sun technologies, such as the GNU Compiler for Java and GNU Classpath.


MySQL is a relational database management system (RDBMS) that runs as a server providing multi-user access to a number of databases. The MySQL development project has made its source code available under the terms of the GNU General Public License, as well as under a variety of proprietary agreements. MySQL is owned and sponsored by a single for-profit firm, the Swedish company MySQL AB,

now owned by Sun Microsystems, a subsidiary of Oracle Corporation.

Members of the MySQL community have created

Literature Survey


    several forks such as Drizzle and MariaDB. Both forks were in progress long before the Oracle acquisition (Drizzle was announced 8 months before the Sun acquisition).

    Free-software projects that require a full-featured database management system often use MySQL. Such projects include (for example) WordPress, phpBB and other software built on the LAMP software stack. MySQL is also used in many high-profile, large-scale World Wide Web products including Wikipedia, Google, Drupal and Face book.



    Existing methods can be classified into two main categories. The first category concerns diffusion-based approaches which propagate linear structures or level lines via diffusion based on partial differential equations and variation methods. Unfortunately, the diffusion-based methods tend to introduce some blur when the hole to be filled-in is large. The second family of approaches concerns exemplar-based methods which sample and copy best matches texture patches from the known image neighborhood. These methods have been inspired from texture synthesis techniques and are known to work well in cases of regular or repeatable textures. The first attempt to use exemplar-based techniques for object removal has been reported in. Authors in improve the search for similar patches by introducing an a priori rough estimate of the in painted values using a multi-scale approach which then results in an iterative approximation of the missing regions from coarse to fine levels.


    In this paper,we further categorize exemplar-based methods into two groups: matching-based and graph- based.Matching-based methods explicitly match the patches in the unknown region with the patches in the known region, and copy the known content to complete the unknown region. This strategy makes it possible to synthesize textures and more complex structures. Unlike many matching-based methods using greedy fashions, the method proposed by Wexler et al.optimizes a global cost function called the coherence measure. This cost function encourages that each patch in the filled region is as

    similar as possible to a certain known patch. It has been generalized for image retargeting/reshuffling.This measure helps to yield more coherent results for image completion. But because this cost function inherently has multiple local optima, this method is sensitive to initialization and optimization methods.

    The currently existing systems for image completion process are as follows:

    L. Alvarez, J. Weickert, and J. Sanchez. Reliable estimation of dense optical flow fields with large displacements.

    Optical flow estimation is classically marked by the requirement of dense sampling in time. While coarse-to-fine warping schemes have somehow relaxed this constraint, there is an inherent dependency between the scale of structures and the velocity that can be estimated. This particularly renders the estimation of detailed human motion problematic, as small body parts can move very fast.

    W. Andreas, D. Cremers, T. Pock, and H. Bischof. Structure and motion-adaptive regularization for high accuracy optic Flow.

    The accurate estimation of motion in image sequences is of central importance to numerous computer vision applications. Most competitive algorithms compute flow fields by minimizing an energy mad of a data and a regularity term. To date, the best performing methods rely on rather simple purely geometric regularizers favoring smooth motion. In this paper, we revisit regularization and show that appropriate adaptive regularization substantially improves the accuracy of estimated motion fields.

    M. Bleyer, C. Rhemann, and C. Rother. Patchmatch stereo – stereo matching with slanted support windows

    Common local stereo methods match support windows at integer-valued disparities.The implicit assumption that pixels within the support region have constant disparity does not hold for slanted surfaces and leads to a bias towards reconstructing frontoparallel surfaces. This work overcomes this bias by estimating an individual 3D plane at each pixel onto which the support region is projected. The major challenge of this approach is to find a pixels optimal 3D plane among all possible planes whose number is infinite. We show that an ideal algorithm to solve this problem is PatchMatch [1] that we extend to find an approximate nearest neighbor according to a plane.


    The feasibility of the project is analyzed in this phase and business proposal is put forth with a very general plan for the project and some cost estimates. During system analysis the feasibility study of the proposed system is to be carried out.


    This study is carried out to check the economic impact that the system will have on the organization. The amount of fund that the company can pour into the research and development of the system is limited. The expenditures must be justified. Thus the developed system as well within the budget and this was achieved because most of the technologies used are freely available. Only the customized products had to be purchased.


    This study is carried out to check the technical feasibility, that is, the technical requirements of the system. Any system developed must not have a high demand on the available technical resources.


    The aspect of study is to check the level of acceptance of the system by the user. This includes the process of training the user to use the system efficiently.


    Our method is less suitable for out painting.Our methods may also fail when the desired offsets do not form dominant a failure case.We can partially solve this problem by manually introducing offsets.we can paint an extra stroke on the image and treat this image as a new source for patch statistics.This stroke contributes to the statistics and overcomes the problem .Some other failure examples are in the supplementary materials, available online.


    NetBeans is a software development platform written in Java. The NetBeans Platform allows applications to be developed from a set of modular software components called modules. Applications based on the NetBeans Platform, including the NetBeans integrated development environment (IDE), can be extended by third party developers.

    The NetBeans IDE is primarily intended for development in Java, but also supports other languages, in particular PHP, C/C++, and HTML5. NetBeans is cross- platform and runs on Microsoft Windows, Mac OS X, Linux, Solaris and other platforms supporting a compatible JVM.The NetBeans Team actively support the product and seek feature suggestions from the wider community. Every release is preceded by a time for Community testing and feedback.

    NetBeans IDE is an open-source integrated development environment. NetBeans IDE supports development of all Java application types (Java SE (including JavaFX), Java ME, web, EJB and mobile applications) out of the box. Among other features are an Ant-based project system, Maven support, refactorings, version

    control (supporting CVS, Subversion, Git, Mercurial and Cle arcase).

    Modularity: All the functions of the IDE are provided by modules. Each module provides a well defined function, such as support for theJava language, editing, or support for the CVS versioning system, and SVN. NetBeans contains all the modules needed for Java development in a single download, allowing the user to start working immediately. Modules also allow NetBeans to be extended. New features, such as support for other programming languages, can be added by installing additional modules. For instance, Sun Studio, Sun Java Studio Enterprise, and Sun Java Studio

    Creator from Sun Microsystems are all based on the NetBeans IDE.

    License: From July 2006 through 2007, NetBeans IDE was licensed under Sun's Common Development and Distribution License (CDDL), a license based on the Mozilla Public License (MPL). In October 2007, Sun announced that NetBeans would henceforth be offered under a dual license of the CDDL and the GPL version 2 licenses, with the GPL linking exception for GNU Classpath[13]


    Net beans is the fromt end we use to develop this project


    MySQL, the most popular Open Source SQL database management system, is developed, distributed, and supported by MySQL AB. MySQL AB is a commercial company, founded by the MySQL developers, that builds its business by providing services around the MySQL database management system. The MySQL Web site ( provides the latest information about MySQL software and MySQL AB. MySQL is a database management system.


    Computing the Statistics: To efficiently matching the patches

    , we apply a nearest-neighbor field algorithm in [31] with a slight modification: to handle the non-nearby constraint (jsj > t),before computing the difference between a pair of patches we first check their spatial distance and reject them if the constraint is disobeyed.

    The Graph-Based Method: We adopt a two-scale solver in our graph-based method (Section 2.2.1). We first downsample the rectangular region (by a scale l) to 800_600 pixels if it is larger than this size.Then we build a graph as in Eq. (3) and optimize it using graph-cuts [21]. We use the public code of the multi-label graph-cuts in.



We would like to take this opportunity to express our sincere gratitude to our proposed system guide, Mr.NATARAJAN, Head of the Department, Information Technology and Computer science and engg, and our project guide Mrselva mani (M.E) dept of cse for their invaluable support and guidance throughout the process in spite of his busy schedule and appreciating our diligent efforts and providing valuable inputs which helped us to mitigate many problems faced in the software development process.

We are grateful to her for her feedback which helped us track and schedule the process effectively. The time, ideas and encouragement that she gave is appreciable.


In this project we have presented novel statistics of patch offsets.We have demonstrated the effects of these statistics for image completion using both graph-based and matching based methods.The usage of the patch offsets implies that we only consider shifts of patches for image completion.More complex transforms like scaling, rotation, reflection,and their combinations have been studied in Generalized Patch Match, Transforming Image Completion,and Image Melding.These transforms are necessary in case when shifting is not sufficient,e.g.,completing circles or reflection- symmetric objects).Since these transformations further increase the dimensionality of the search space, it could be useful to investigate the statistics and limit the search (some successful attempts have been shown in a recent work inspired by our method).Image Melding further improves Wexler et al.method by voting in the gradient domain.It is possible to combine this method with our matching-based solution.


  1. M. Bertalmio, G. Sapiro, V. Caselles, and C. Ballester, Image inpainting, in Proc. 27th Annu. Conf. Comput. Grah. Interact. Techn.

  2. C. Ballester, M. Bertalmio, V. Caselles, G. Sapiro, and J. Verdera, Filling-in by joint interpolation of vector fields and gray levels, IEEE Trans. Image Process.

  3. A. Levin, A. Zomet, and Y. Weiss, Learning how to inpaint from global image statistics, in Proc. 9th IEEE Int. Conf. Comput. Vis.

  4. M. Bertalmio, L. Vese, G. Sapiro, and S. Osher, Simultaneous structure and texture image inpainting, in Proc. IEEE Comput. Vis. Pattern Recog.

  5. S. Roth and M. J. Black, Fields of experts: A framework for learning image priors, in Proc. IEEE Comput. Vis. Pattern Recog.

  6. A. A. Efros and T. K. Leung, Texture synthesis by non-parametric sampling, in Proc. IEEE Int. Conf. Comput.

  7. A. Criminisi, P. Perez, and K. Toyama, Object removal by exemplar- based inpainting, in Proc. IEEE Comput. Vis. Pattern Recog.

  8. I. Drori, D. Cohen-Or, and H. Yeshurun, Fragment-based image completion, in Proc. Annu. Conf. Comput. Graph. Interact. Techn.

  9. J. Jia and C.-K. Tang, Image repairing: Robust image synthesis by adaptive ND tensor voting, in Proc. IEEE Comput. Vis. Pattern Recog.

  10. J. Jia and C.-K. Tang, Inference of segmented color and texture description by tensor voting, IEEE Trans. Pattern Anal. Mach. Intell.

Leave a Reply

Your email address will not be published. Required fields are marked *