Object Removal by Hierarchical Super-Resolution Based Inpainting

Object Removal by Hierarchical Super-Resolution Based Inpainting

T. Vikram

Computers and Communications Jawaharlal Nehru Technological University Kakinada, India

Dr. A. M. Prasad

Professor, ECE Dept.

Jawaharlal Nehru Technological University Kakinada, India

Abstract This paper introduces novel frame work for Object Removal by means of inpainting. In this method, first the object in the required target area is removed by inpainting. The output thus obtained is given as input to a super-resolution algorithm to recover details on missing areas. Exemplar-based inpainting is used to remove objects that are not required. It is desirable to use a Super-resolution algorithm since inpainting produces a low resolution (LR) image. In this paper a regularization method based on morphologic operations is used for SR image reconstruction. It is always desirable to generate a high resolution (HR) image as it shows more intricate details.

Index TermsObject Removal, Inpainting, Exemplar, Super-resolution

1. INTRODUCTION

   Inpainting is the process of reconstructing lost or deteriorated parts of an image. The process of inpainting utilizes the background information to fill the missing or target region of image [1]. Initially inpainting is used for scratch removal. The other applications include object removal, text removal and other automatic modification of images. The idea of object removal is to remove objects from digital photographs and fill the hole with the information extracted from the surrounding area.

   Existing methods of inpainting can be classified into two main categories namely Diffusion and Exemplar based approaches [6].The diffusion based approach tends to introduce some blur when the target region or area of removal to be filled is large .Exemplar based approach uses the background information i.e. these methods sample and copy best matching texture patches from the known image neighborhood [2]-[5]. In this method diffusion based inpainting and texture synthesis are combined. Exemplar based techniques effectively generate new texture by sampling and copying color values from the source [2]. The technique presented here combines the strength of both approaches into a single efficient algorithm. Exemplar based inpainting is capable of propagating both structure and texture information.

   Although tremendous progress has been made in the past years on inpainting, difficulties exist when the hole or the area of object to be removed is very large and the computational time required in general is high. These two problems are addressed by considering a two-step or hierarchical approach [6] in which inpainting is performed

   on a input image and a super resolution algorithm is used to construct a high resolution (HR) image. Super-resolution (SR) imaging aims to overcome or compensate the limitation or shortcomings of the image acquisition device/system and/or possibly ill-posed acquisition conditions to produce a higher-resolution image based on a set of images that were acquired from the same scene. With rapid progress in image processing for visual communications and scene understanding, there is a strong demand for providing the viewer with high-resolution imaging not only for providing better visualization (fidelity issue) but also for extracting additional information details (recognition issue). A HR image makes it easy to achieve a better classification of regions in a multi-spectral remote sensing image or to assist radiologist for making diagnosis based on a medical imagery. Super-resolution refers to creating an enhanced high resolution (HR) image from one or more low resolution (LR) images [7]. The approach used in this paper is based on regularization frame work. Another class of super resolution methods generates an HR image from a single LR image or a frame [7]. These methods are referred to as Example-based SR or image hallucination. In example based SR, correspondences between HR and LR patches are learned [6] from a group of HR-LR patches known as Dictionary and then applied to a low resolution image to recover its higher

   resolution version.

   In this paper we use a non-linear regularization method based on multiscale morphology for edge preserving SR reconstruction [8]. In this method we consider Super Resolution image reconstruction as a deblurring problem and solve the inverse problem using Bregman iterations. The HR image is estimated based on some prior knowledge about the image in the form of regularization. A new regularization method based on multiscale morphological filters is proposed. Morphological operators are used for extracting structures from images. Image segmentation, image denoising and image fusion can be done successfully using morphological operations. Better results can be obtained by combining bregman iteration [9] and morphologic regularization.

   The rest of the paper is organized as follows. Section II gives the overview of algorithm for the proposed method. In Section III, algorithm for Exemplar-Based Inpainting is explained in detail. This section presents the different steps of

   Original Image

   LR image

   Exemplar based Inpainting

   Super Resolution using Morphologic Regularization

   Output (Inpainted) Image

   Image mask

   Fig.1. The frame work of the proposed method

   Exemplar-Based Inpainting . In Section IV, the problem of Super-resolution is formulated and the Super-resolution algorithm using Bregman iteration is presented. Section V presents the experimental results obtained by applying the proposed method on different natural images. The comparison of proposed method with Patch Match method is presented in this section. Finally, a conclusion is made in Section VI.

2. ALGORITHM OVERVIEW

The task of object removal becomes complicated when area of object to be removed or inpainted becomes large. So far a number of methods for inpainting had been proposed.

In this paper, we propose a new framework for inpainting which is a combination of low resolution picture inpainting and a super resolution algorithm based on multiscale

window must be specified. Each pixel maintains a color value and confidence value, which reflects our confidence in pixel.The patches in the filling region are given a temporary priority value which should be calculated in our algorithm.

The proposed inpainting i.e. Exemplar based inpainting method follows the following steps:

1.Filling order computation. 2.Texture synthesis.

3.Updating confidence values.

1. Filling order computation: In order to find the filling order we need to calculate the priority of patches in the filling region. The priority of a patch centered on p is calculated using confidence and data terms [2]. The priority is given by the product of these two terms.

   P(p) = C(p) D(p). (1)

   Where C(p) is the confidence term and D(p) is the data term[2].

   These are defined as follows:

   morphology.

   This process of inpainting is mainly divided into two sequential steps. The first one is a patch sampling method known as Exemplar based inpainting. The inpainting

   C(p)

   q p (I )

   p

   C(q)

   , D(p)

   I .n

   p p

   (2)

   is performed on a LR (resized) version of an input image. This is because a low resolution picture is less contaminated

   where is a normalization factor,

   p is the area of

   by noise and is composed of main scene structures. Also, as the picture to inpaint is smaller than the original one, the computation time is reduced ompared to the one necessary to inpaint the original image. The inpainted version of the image obtained is given as input to the Super Resolution algorithm. Its goal is to enhance the resolution of the image. Fig. 1 shows the frame work of the proposed method which is as follows:

   1. A low resolution picture is built from original image

   2. An exemplar based inpainting algorithm is applied to remove the object.

   3. Super Resolution algorithm is applied to the input image.

      p , np is a unit vector orthogonal to front in the point p

      and denotes orthogonal operator.

      During initialization C(p) is set to zero i.e. C(p) = 0 p ,

      and C(p) is set to 1 i.e. C(p)=1 p I , .

      The confidence term is a measure of amount of reliable information surrounding the pixel p [2]. The patches in which many of the pixels are already filled are considered to be filled first. For example, patches present at the corners and thin tendrils of target region are filled first because they provide more reliable information against which to match. The data term is a function of strength of isophotes hitting the fill front at each iteration.

2. Propagating information of texture and structure: First, the priorities for each patch in the filling region are computed. Hence the filling order is determined. The patch

   1. EXEMPLAR-BASED INPAINTING

      with highest priority

      p

      is found and it is filled with the

      Given an input image, we create an image mask for the object to be removed. This target region to be removed and filled should be selected by the user. The source region to be used denoted by is defined as original image minus target region . For texture synthesis, the size of the template

      information (data) from the source region. In traditional inpainting techniques, pixel value information is propagated via diffusion which leads to smoothness and blurring of image [6]. Propagation of image texture is done by direct sampling of the source region [5]. The patch q which is

      similar to patch with highest priority p in the source region is found .

      Ensembling all the available obtain Y such that

      Y k into a single HR grid we

      q

      arg min d ( p , q )

      q

      (3)

      Y = RHX + e . (8)

      Where d ( p , q ) is the similarity distance measured

      between patches centered at pixels p and q respectively. Similarity distance is defined as the sum of squared

      1. L2Error- based Estimation of the SR image

         The number of unknown pixels in HR grid in X is very large. Therefore a solution to obtain X by inversion may not be

         differences between already filled pixels in these two patches.

         The value of each pixel to be filled is copied from its corresponding position q (source exemplar).

3. Updating confidence values: After filling the patch

feasible. Therefore, an estimate of HR image X

i.e.,

X = arg min[ RHX- Y 2]

is found

(9)

p with new pixel values, the confidence term C(p) should X 2

be updated.

C( p) C( p)p p . (4)

The above three steps are repeated in an iterative manner until the target region is filled with the data from source region. After completion of inpainting the next step is applying super resolution algorithm on output LR image to obtain a HR image.

1. SUPER-RESOLUTION USING MORPHOLOGICAL REGULARIZATION AND BREGMAN ITERATION.

   2

   1. Problem Formulation: The observed images of a scene

      When K< N/M, the SR image reconstruction becomes an ill posed problem, and therefore, it becomes necessary to impose regularization to obtain a stable solution.

      1. Regularization for the SR Reconstruction Algorithm Regularization and iterative methods are used in conjunction for the restoration of noisy degraded images in order to solve

      an ill posed problem said above. To obtain a stable solution

      for above equation, we impose a regularization operator

      ¡ ( X ) on the estimated HR image X. Therefore, the SR image reconstruction problem can simply be formulated as

      are usually degraded by blurring due to atmospheric noise or inappropriate camera settings. Downsampling is also an important factor in degradation of images. HR and LR images

      X = arg min{¡ (X ) :

      X

      RHX – Y

      2 < }

      (10)

      can be related as follows:

      Yk = DFk Hk X + ek,

      " k = 1, 2…., K

      (5)

      where is a scalar constant depending on the noise variance in the LR images. The above equation (10) represents a constrained minimization problem. Unconstrained minimization problem is represented as follows:

      where Yk represents column vector of kth LR image of size

      M, X represents column vector of HR image of size N and

      X arg min 1 RHX Y 2 (X )

      (11)

      e represents column vector of additive noise. F is a

      X 2 2

      k k

      geometric warp matrix and Hk is the blurring matrix of size

      N ´ N . D is the downsampling matrix of size M ´ N and k

      where µ is the regularization parameter that controls emphasis between data error term and regularization term.

      is the index of the LR images. Assuming that Hk becomes same for all k, it may be simply denoted as H.

      The conventional regularization methods choose

      ( X ) as the high frequency energy and minimize its pth

      Yk = DFk HX + ek,

      " k = 1, 2…., K

      (6)

      form to ensure smoothness. In this paper ( X ) is defined

      based on morphological filters that suppress noise [8]. Bright and dark noise can be removed using morphological opening

      Applying upsampling and reverse shifting, Yk (6) becomes Y k which denotes upsampled and reverse shifted kth LR image. Thus from equation (6), we can write

      Y k = R k HX + ek , (7)

      and closing.

   2. Morphologic Regularization:

      Let B be disk of unit size with origin at its center and sB be a disk structuring element (SE) of size s. Then the morphologic dilation Ds ( X ) of an image X of size m n is given by

      where Y k

      = F- 1DTY

      and

      e = F- 1DT e

      . DT

      is the

      k k

      k k

      k

      upsampling operator matrix.

      maxr(sB)

      (1)

      {xr }

      (first step in equation (19) ) can be explicitly solved using the following two step algorithm.

      maxr(sB) {xr }

      D ( X ) ( 2 )

      U (k1) X (k) H T RT (RHX (k) Y )

      s

      (12)

      1 2

      (20)

      X (k1) arg min

      X U (k 1)

      ( X )

      max {x }

      X 2 2

      r(sB)

      (mn) r

      Similarly, the morphologic erosion Es ( X ) is given by

      minr(sB) {xr }

      (1)

      b)Proposed iterative SR algorithm:

      In this section the final proposed iterative algorithm for Super Resolution of LR image is defined using Bregman iteration

      minr(sB)

      Es ( X )

      ( 2 )

      {xr }

      (13)

      and operator splitting.

      The algorithm is as follows:

      U (n1) X (n) H T RT (RHX(n) Y n

      minr(sB)

      (mn)

      {xr }

      X (n1) arg min (X) 1

      X U (n1)

      2

      (21)

      Morphological opening Os ( X )

      and closing Cs ( X ) by

      X 2 2

      structuring element sB is given by

      O ( X ) D (E ( X ))

      Y (n1) Y (n) (Y RHX (n1) )

      s s s

      Cs ( X ) Es (Ds ( X ))

      (14)

      In above equation, substituting subgradients in place of gradients in second step, we have

      The regularization function based on multiscale morphology is formulated as

      S

      ( X ) 1 (X U(n1) ) 0.

      ( X )

      (22)

      ( X ) s1t [Cs ( X ) Os ( X )] ; 0&lt <1 (15)

      The second step in equation (21) can be modified as follows:

      s1

      where 1 is a column vector consisting of all the 1s and is the weighing coefficient. Therefore, the SR reconstruction

      . X (n1) U (n1)

      ( X )

      ( X )

      X ( n )

      (23)

      problem can be written as

      s s t

      Therefore, the final proposed SR image reconstruction

      algorithm by using Bregman iteration and operator splitting is as shown in Algorithm1.

      X min 1 [Cs ( X ) Os ( X )] : RHX Y 2

      (16)

      Y is a HR grid which consists of number of unknown

      X s1

   3. Subgradient Methods and Bregman Iteration :

   In this section we develop an algorithm for Super-Resolution through Bregman iteration using morphologic regularization. a)Bregman Iteration:

   The minimization problem can be formulated as follows:

   pixels. FillUnknown ( Y ) in Algorithm1 is used to fill these

   unknown pixels with their corresponding neighbor pixels. is a predefined value chosen depending on the variance of noise in LR images.

   The regularization function ( X ) consists of

   min( X ) : T ( X ) 0

   X

   (17)

   opening and closing operations which in turn uses morphologic operators dilation and erosion respectively.

   where and T are convex functions defined over

   Rn R .

   Bregman iteration proposed for minimization problem above is as follows:

   These operators are non-differentiable. Therefore , we compute the subgradients of the regularization function as in [8]

   Algorithm 1

   Let X 0 p0 0

   X (n1) arg min B p(n) ( X , X (n) ( X )

   Initialize

   Y (0) n 0, Y, X (0) FillUnknown(Y );

   X (18)

   (n)

   RHX Y

   2

   2

   While

   p(n1) p(n) T ( X (n1) )

   Here,

   B p(n) denotes Bregman distance related to convex

   U (n1) X (n) H T RT (RHX(n) Y n

   function. The iteration proposed in (18) can be simplified as follows:

   (n1) 1 2

   X arg min RHX Y 2 ( X )

   X (n1) U (n1) ( X )

   X 2

   (19)

   ( X ) X ( n )

   Y (n1) Y (n) (Y RHX (n1) )

   Y (n1) Y (n) (Y RHX (n1) )

   End

   (n) th

   In equation (19) (Y RHX ) is the error in the n

   estimation which is added to Y(n) such that

   RHX Y becomes zero. The unconstrained optimization

2. RESULTS

The proposed method is applied on different images and compared with the Patch Match method [4] which is available in Adobe Photoshop.

Fig. 2 shows the results obtained after applying super resolution based inpainting on different natural images. Column (a) gives the original images, column (b) gives the image masks (object to be removed) and column (c) gives the SR Inpainted images.

Fig. 3 shows the comparision beween the results obtained through proposed method and the Patch Match method available in Adobe Photoshop (one of the State-of-art

Methods). Column (a) shows the original images, column

1. shows the image obtained through Patch Match in Adobe Photoshop and (c) gives the output image obtained through proposed method.

   Table I shows the time taken for inpainting and super- resolution for some natural images. Simulation is performed on a laptop with configuration as follows: Intel i5 processor and 4Gb RAM .It is observed that inpainting process consumes more time.

   (c)

   (a)

   (b)

   1. (b) (c)

      (a)

      Fig.2. Results of the proposed method. (a) Original Picture, (b) Mask Image (image specifying the object to be removed), and (c) Output picture

      1. (b) (c)

Fig.3. Comparison of the proposed method. (a) Original Picture, (b) Patch Match in Adobe Photoshop, and (c) Proposed method

TABLE I. RUNNING TIME FOR INPAINTING AND SUPER- RESOLUTION PROCESSES

VI. CONCLUSION

A new approach for object removal using inpainting has been successfully implemented in this paper. Object removal is done in a hierarchical manner by combining inpainting and Super-resolution. Proposed method is applied on wide variety of images and the obtained results show the effectiveness of this method compared to other methods such as Patch Match. A scope for extension is to use a different SR method in order to improve the effectiveness.

REFERENCES

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

   .Tech.,Jul. 2000, pp. 417424.

2. A. Criminisi, P. Pérez, and K. Toyama, Region filling and object removal by examplar-based image inpainting, IEEE Trans. Image Process., vol. 13, no. 9, pp. 12001212, Sep. 2004.

3. O. Le Meur, J. Gautier, and C. Guillemot, Examplar-based inpainting based on local geometry, in Proc. 18th IEEE Int. Conf. Image Process.,

   Sep. 2011,pp.34013404.

4. C. Barnes, E. Shechtman, A. Finkelstein, and D. B. Goldman, Patch- Match: A randomized correspondence algorithm for structural image editing, ACM Trans. Graph., vol. 28, no. 3, p. 24, Aug. 2009.

5. A. A. Efros and T. K. Leung, Texture synthesis by non- parametric sampling, in Proc. 7th IEEE Comput. Vis. Pattern Recognit., Sep. 1999, pp. 10331038.

6. O. Le Meur and C. Guillemot, Super-resolution-based inpainting, in Proc. 12th Eur. Conf. Comput. Vis., 2012, pp. 554567.

7. D. Glasner, S. Bagon, and M. Irani, Super-resolution from a single image, in Proc. IEEE Int. Conf. Comput. Vis., vol. 10. Oct. 2009, pp. 349356.

8. Purkait, P., Chanda, B.: Super resolution image reconstruction through bregman iteration using morphologic regularization. IEEE Transactions on Image Processing 21, 40294039 (2012).

9. A. Marquina and S. J. Osher, Image super-resolution by TVregularization and Bregman iteration, J. Sci. Comput., vol. 37, no. 3, pp. 367382, Dec. 2008.