Gradient based image completion by solving the poisson equation

Gradient based image completion by solving the Poisson equation
Jianbing Shen a, Xiaogang Jin a,∗ , Chuan Zhou a, Charlie C. L. Wang b
a State

Key Lab of CAD & CG, Zhejiang University, Hangzhou, 310027, China of Automation and Computer-Aided Engineering, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong, China

b Department

Abstract This paper presents a novel gradient-basedimage completion algorithm for removing significant objects from natural images or photographs. Our method reconstructs the region of removal in two phases. Firstly, the gradient maps in the removed area are completed through a patch based filling algorithm. After that, the image is reconstructed from the gradient maps by solving a Poisson equation. A new patch-matching criterion is developed in ourapproach to govern the completion of gradient maps. Both the gradient and the color information are incorporated in this new criterion, so a better image completion result is obtained. Several examples and comparisons are given at the end of the paper to demonstrate the performance of our gradient-based image completion approach. Key words: Image completion; Gradient; Filling order; Patchpropagating; Poisson equation

1

Introduction

The removal of objects or the recovery of the damaged portion in a given image, known as image completion, is an important task in the photo editing or the video post-processing. Given an input image I with a missing or unknown region Ω, the task of image completion is to propagate structure and texture
∗ Corresponding author. Tel.: +86-571-88206681ext 507; fax: +86-571-88206680. E-mail addresses: jin@cad.zju.edu.cn (X. Jin), shenjianbing@cad.zju.edu.cn (J. Shen), zhouchuan@cad.zju.edu.cn (C. Zhou), cwang@acae.cuhk.edu.hk (C.C.L. Wang).

Preprint submitted to Elsevier Science

25 May 2006

information from the known region I\Ω into Ω. The removed parts can be filled by various interactive tools such as clone brush strokes andcompositing processes. However, automatically and seamlessly filling Ω by the known region in I is still a problem under research. A number of approaches related to image completion have been proposed in computer graphics and computer vision literatures [2,4–6]. In [4], Bertalmio et al. conducted a PDE-based method to repair damaged images. The idea is to extend the structures inwards by satisfying somecontinuities across the boundaries of the damaged area. The recovered results are highly smooth. This works well for small damaged regions. However, when the reconstructed area is large, it will give a blurry artifact that lacks texture. Therefore this approach fails in reconstructing large regions. Levin et al. [2] extended the idea by measuring global image statistics based on the prior imageknowledge besides the local color information. Drori et al. [6] incorporated pyramid image approximation and adaptive image fragments to achieve impressive results. Nevertheless, all these approaches are extremely slow due to the high computational complexity. Recently, some researchers have considered exemplar-based methods to complete images with large portion removed [3,6,8,5,9,16,19]. The firstattempt to use exemplar-based synthesis for image completion was by Harrison [8], who filled the pixels in the target region by the level of “textureness” on the neighborhoods of a pixel. Although the intention sounds good, strong linear structures were often overruled by nearby noises in his approach. Jia and Tang [9] presented a technique for filling image regions by explicitly segmenting the unknownarea into different homogeneous texture areas with a tensor voting method. However, their approach requires both an expensive segmentation step and a difficult choice about how to stitch the boundary between two textures. More recently, Criminisi et al. [5] proposed an exemplar-based image completion algorithm through region filling, where the patch filling order is determined by the angle between...