Image Completion Using Efficient Belief Propagation Via Priority Scheduling and Dynamic Pruning

In this paper, a new exemplar-based framework is presented, 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, we pose 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: ldquopriority-based message schedulingrdquo and ldquodynamic label pruning.rdquo 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. Moreover, both of our extensions are generic, since they do not rely on the use of domain-specific prior knowledge. 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. Experimental results on a wide variety of input images are presented, which demonstrate the effectiveness of our image-completion framework for tasks such as object removal, texture synthesis, text removal, and image inpainting.

I. Introduction

The problem of image completion can be loosely defined as follows: given an image which is incomplete, i.e., it has missing regions (e.g., see Fig. 1), try to fill its missing parts in such a way that a visually plausible outcome is obtained at the end. Although stating 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 is designed to solve the image completion problem should have the following characteristics: •

it should be able to successfully complete complex natural images;

•

it should also be able to handle incomplete images with (possibly) large missing parts;

•

all these should take place in a fully automatic manner, i.e., without intervention from the user.

Also, ideally, we would like any image completion algorithm to be able to handle the related problem of texture synthesis, as well. According to that problem, given a small texture as input, we are then asked to generate an arbitrarily large output texture, which maintains the visual characteristics of the input [e.g., see Fig. 2(a)]. It is exactly due to all of the above requirements that image completion is, in general, a very challenging problem. Nevertheless, it can be very useful in many areas, e.g., it can be important for computer graphics applications, image editing, film postproduction, image restoration, etc. Fig. 1.

Object removal is just one of the many cases where image completion needs to be applied. In the specific example shown, the user wants to remove a person from the input image on the left. He, therefore, simply marks a region around that person and that region must then be filled automatically so that a visually plausible outcome is obtained.

Fig. 2.

(a) Texture synthesis problem. (b) The three main approaches to image completion.