Learning How to Inpaint from Global Image Statistics

Abstract
Inpainting is the problem of filling in missing regions in images. Many techniques solve this problem in a local manner, using the boundary of the hole and assuming a prior model of the image.
In this project, we address the problem from a global approach based on the article of Levin, Zomet and Weiss, using the rest of the image in order to inpaint the missing hole. Given a training image, we use histograms of local features in order to build an exponential family distribution over the images. We then use the specific statistics of the training image in order to complete the missing region by finding the most probable image subject to the defined distribution, given the boundary conditions. The optimization process is done using loopy belief propagation. This method can successfully inpaint holes while taking into account global statistics of the image.

The Implementation
The implementation can be described by the following block diagram:

The inpainting process consists of three steps:

1. Learning the statistics of a training image of a similar “look”. In this project we learn the histograms of the gradient magnitude  and of the pairwise angles  between two gradients. We use a clustering algorithm in order to discretize the gradient field, and create the allowed states for the completion of the missing gradient field. Based on the empirical probabilities of the chosen gradients, the distribution is built
2. Finding the most probable gradient field given the boundary and the distribution. This is the most important and critical part of the project. In order to find the most probable filling-in, we must maximize the probability, subject to the boundary:
   The left product is taken over all pixels, based on the gradient magnitude probabilities, the middle product is taken over all neighboring pixels, using the angle probabilities, and the third product enforces integrability of the gradient field.
   We solve this optimization problem using the Max-Product Belief Propagation algorithm:
   Belief Propagation is a message-passing algorithm between nodes of a factor graph. These messages can intuitively be understood as a message from one node to another about what state the receiving node should be in. The messages are determined by message update rules. When the algorithm converges, the resulted assignment (in our case – the gradient field) is a “neighborhood maximum” of the posterior probability.
   We build the following graph: each pixel in the hole is represented by a node, as are groups of three pixels determining the integrability of the gradient field. Edges in the graph connect neighboring pixel nodes, as well as nodes which have “containment” relations. We define potentials on the nodes and the edges, based on the distribution. We set the messages of boundary nodes according to their fixed state, and then run this message-passing algorithm on the graph in order to find the most likely gradient field
3. Inpainting the hole by integrating the resulted gradient field , subject to the boundary. To do so, we minimize the integration error by the Least Mean Squares critiria:

Tools
Our project was programmed using Matlab 6.5.

Results
The algorithm successfully completes various holes in images. For example:

Inpainting a circle and a square: The results depend on the learned statistics. On the left are the images with the holes; in the middle, the images completed when learning the same image; on the right, the images completed when learning the other image. As we can see, the completion indeed depends on the learned statistics.

Inpainting a picassso image: appropriate training images were learned for each hole. The completions are successful.

Inpainting building windows: Again, the completion is successful.

Conclusions

• The algorithm can successfully complete missing regions in images which have well defined statistics, in a natural looking way
• The algorithm completes the missing information according to the statistics, as wanted. Thus, The inpainted region fits the global look of the image
• The level of complexity of the computation is high, resulting in memory and run-time constraints

Acknowledgment
We would like to thank our project supervisors Boaz Ofir and Dr. Yoav Schechner for their guidance throughout the project. In addition, we are very grateful to Dr. Asaf Zomet and Anat Levin for their assistance.
We are also grateful to the Ollendorff Minerva Center Fund for supporting this project.