Abstract:
One embodiment of the present invention relates to a system for reconstructing an image. During operation, the system receives an original image, wherein the original image includes a defective area to be reconstructed. The system also receives a reference to a texture image, which contains a texture to be used during the reconstruction. The system then divides the values of pixels in the defective area and surrounding boundary pixels, by the values of corresponding pixels in the texture image to produce a first intermediate image. Next, the system solves a partial differential equation (PDE) for non-boundary pixels in the first intermediate image subject to values of the boundary pixels in the first intermediate image to produce a second intermediate image. The system then multiplies the values of pixels in the second intermediate image by the values of corresponding pixels in the texture image to produce a replacement image. Finally, the system substitutes the replacement image into the defective area of the original image.

Description:
BACKGROUND 
     1. Field of the Invention 
     The present invention relates to computer-based tools for manipulating digital images. More specifically, the present invention relates to an improved Poisson image-editing technique, which matches both pixel values and texture contrast while seamlessly reconstructing a region of an image. 
     2. Related Art 
     In recent years, a number of effective techniques have been developed to digitally remove scratches, wires and other objects from images and video. For example, U.S. Pat. No. 6,587,592, entitled “Generating Replacement Data Values for an Image Region,” describes a system that implements a Poisson image-editing technique which “heals” a defective region of an image using data from a texture area from the same image or from a different image. 
     In Poisson editing, the defective pixels are replaced with new pixels described by a function ƒ(x, y), which is a solution of the Poisson equation
 
Δƒ( x, y )=Δ g ( x, y )   (1)
 
with a Dirichlet boundary condition which constrains the new ƒ(x, y) to match the original image at the boundary. In equation (1), g(x, y) is the texture that is “seamlessly-cloned” into the reconstructed area, and
 
     
       
         
           
             
               
                 
                   Δ 
                   = 
                   
                     
                       
                         ∂ 
                         2 
                       
                       
                         ∂ 
                         
                           x 
                           2 
                         
                       
                     
                     + 
                     
                       
                         
                           ∂ 
                           2 
                         
                         
                           ∂ 
                           
                             y 
                             2 
                           
                         
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     This technique effectively clones texture, while changing the color/shading of the replacement pixels to seamlessly match surrounding pixels at every boundary point. 
     While this method works very well in many cases, it sometimes encounters problems. Consider the example illustrated in  FIGS. 1A ,  1 B and  1 C.  FIG. 1C  illustrates how the scratch in  FIG. 1A  is ultimately removed by Poisson cloning of pebbles from the illuminated area into the shadow area. This technique correctly matches pixel values at the boundary of the patch, but the cloned pebbles are still easy to spot because there is too much variation and too high contrast in the reconstructed area of the image. Note that this problem is inherent in the nature of the Poisson equation (1), which transfers variations of g directly, without modification. 
     What is needed is a technique for digitally removing scratches, wires and other objects from images, without the above-described problems in matching variation and contrast. 
     SUMMARY 
     One embodiment of the present invention relates to a system for reconstructing an image. During operation, the system receives an original image, wherein the original image includes a defective area to be reconstructed. The system also receives a reference to a texture image, which contains a texture to be used during the reconstruction. The system then divides the values of pixels in the defective area and surrounding boundary pixels, by the values of corresponding pixels in the texture image to produce a first intermediate image. Next, the system solves a partial differential equation (PDE) for non-boundary pixels in the first intermediate image subject to values of the boundary pixels in the first intermediate image to produce a second intermediate image. The system then multiplies the values of pixels in the second intermediate image by the values of corresponding pixels in the texture image to produce a replacement image. Finally, the system substitutes the replacement image into the defective area of the original image. 
     In a variation on this embodiment, solving the PDE for pixels in the first intermediate image involves iteratively applying a kernel to each non-boundary pixel in the first intermediate image to generate new a pixel value. 
     In a variation on this embodiment, the PDE is a Laplace equation, wherein a solution to the Laplace equation is continuous and has no lines of discontinuity in the solution&#39;s derivative. 
     In a variation on this embodiment, the PDE is a biharmonic PDE, wherein a solution to the biharmonic PDE is continuous, has no lines of discontinuity in the solution&#39;s derivative, and at the same time minimizes curvature. 
     In a variation on this embodiment, the original image is a color image, and the method is applied separately to each axis of a corresponding color space. 
     In a variation on this embodiment, the texture image is taken from: an area within the original image; or an area within another image, which is not the original image. 
     In a variation on this embodiment, the system subtracts the log of pixels in the texture image from the log of corresponding pixels in the defective area (including surrounding boundary pixels) to produce the first intermediate image. Moreover, after solving the PDE to produce the second intermediate image, the system adds the log of pixels in the texture image to corresponding pixels in the second intermediate image and exponentiates the resulting pixels to produce the replacement image. 
    
    
     
       BRIEF DESCRIPTION OF THE FIGURES 
       The patent or application file contains at least one drawing executed in color. Copies of this patent or patent application publication with color drawing(s) will be provided by the Office upon request and payment of the necessary fee. 
         FIG. 1A  illustrates an image of pebbles with a scratch. 
         FIG. 1B  illustrates the same image wherein the defective area and an associated texture region have been outlined. 
         FIG. 1C  illustrates how the scratch is removed by Poisson cloning from an illuminated area of the image. 
         FIG. 1D  illustrates how the scratch is removed by covariant reconstruction from the same illuminated area in accordance with an embodiment of the present invention. 
         FIG. 2  presents a flow chart illustrating the image reconstruction process in accordance with an embodiment of the present invention. 
         FIG. 3  presents a flow chart illustrating how a replacement image is generated through division and subsequent multiplication operations in accordance with an embodiment of the present invention. 
         FIG. 4  presents a flow chart illustrating how a replacement image is generated by performing log operations and subsequent exponentiation operations in accordance with an embodiment of the present invention. 
         FIG. 5  presents another comparison between covariant cloning and Poisson cloning in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein. 
     The data structures and code described in this detailed description are typically stored on a computer-readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices, such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs), and computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated). For example, the transmission medium may include a communications network, such as a LAN, a WAN, or the Internet. 
     Image Reconstruction 
     One embodiment of the present invention solves the problem of reconstruction based on a model of the internal mechanism of the human visual system. 
     There is a well-known (approximate) invariance of the internal image we see with respect to change of lighting conditions. This invariance, or “color constancy,” is due to the adaptation of the visual system. 
     We observe that it is possible to cast the adaptation problem into the mathematical framework of the vector-covector formalism. In our approach luminance is a vector, retina sensitivity is a covector, and the formalism automatically handles relighting invariance. 
     At each pixel (x, y) the image is a vector ƒ(x, y). For example, ƒ could be a vector describing the three color channels, ƒ=(R,G,B). Relighting transforms this vector ƒ multiplicatively. We say that ƒ changes covariantly with illumination. 
     In the case of grayscale images, ƒ is a 1-D vector. Note that a 1-D vector is different from a scalar. A scalar is an invariant quantity, while a vector changes covariantly with lighting. Unlike scalars, a 1-D vector does not have a numerical value until a basis, or a scale, is chosen. In our case this basis, or measure of scale at each point, is the retina sensitivity. The same vector can be seen as different lightness (perceived brightness) depending on adaptation to bright or dark environment. 
     Due to adaptation, at each pixel the retina sensitivity φ(x, y) transforms in opposition to, or contravariantly with, illumination. Adapted sensitivity is a covector in the sense that a contraction, or “dot product,” with the vector ƒ(x, y) must produce the invariant lightness that we see in the visual system. It is as a scalar invariant φ·ƒ. 
     The true luminance vector, ƒ(x, y) may be captured by the camera or other physical device with known sensitivity. But luminance is not observable by the human visual system. What we actually see is the scalar (i.e. invariant) quantity φ·ƒ, which is the luminance vector acting on the sensitivity covector. Sometimes we will denote this as &lt;φƒ&gt; in order to make the contraction of vector and covector explicit. 
     To avoid confusion, we note that in the case of grayscale images the only vector and covector properties that we are going to use are that ƒ transforms covariantly with lighting (i.e. as a vector), and φ transforms contravariantly with lighting (as a covector), due to adaptation. Lightness is a scalar &lt;φƒ&gt;, and as such it does not change with relighting. We observe only lightness; luminance and sensitivity are not observable independently. 
     Main Equations 
     The simplest way to reconstruct or inpaint the area of a scratch in an image is to replace defective pixels with a solution of the Laplace equation
 
Δƒ=0   (3)
 
with Dirichlet boundary conditions. This is equivalent to minimizing the energy expression
 
                     ∫       (       ∂   f       ∂   x       )     2       +         (       ∂   f       ∂   y       )     2     ⁢     ⅆ   x     ⁢     ⅆ   y               (   4   )               
in the selected area of the scratch, where we calculate pixel values representing smallest sum of the gradients squared. In other words, we are requiring that sum of the lengths squared of the gradients be minimal.
 
     The important observation here is that this energy is not invariant under relighting. As such, it is not appropriate as a model of the invariant (after adaptation) image that humans see. 
     Consider a related invariant expression, written in terms of lightness, which is a scalar (invariant) relative to relighting 
                     ∫       (       ∂     ∂   x       &lt;     φ   ⁢           ⁢   f     &gt;     )     2       +         (       ∂     ∂   y       &lt;     φ   ⁢           ⁢   f     &gt;     )     2     ⁢     ⅆ   x     ⁢       ⅆ   y     .               (   5   )               
Minimizing this energy means sum of the lengths squared of the perceived gradients is minimal. Writing the Euler-Lagrange equation (varying ƒ) we get:
 
                     Δ   ⁢           ⁢   f     +       2   φ     ⁢   grad   ⁢           ⁢     f   ·   grad     ⁢           ⁢   φ     +       f   φ     ⁢   Δ   ⁢           ⁢   φ             (   6   )               
where ƒ is pixel value (luminance) and φ is retina sensitivity. This can be written in a simpler form:
 Δ(φƒ)=0.   (7) 
     To find one possible φ, assume adaptation to a “neutral” area of pure texture g(x, y) in the image. Adaptation means φ·g=const. Since in equations (6) and (7) φ is defined up to a multiplicative constant, we can safely assume it to be 1, and then φ=1/g. 
     Substituting in (7), we get our main equation 
     
       
         
           
             
               
                 
                   
                     Δ 
                     ⁢ 
                     
                       f 
                       g 
                     
                   
                   = 
                   0. 
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     For theoretical reasons it is good to know that this equation is equivalent to 
                       Δ   ⁢           ⁢   f     -     2   ⁢   grad   ⁢           ⁢     f   ·       grad   ⁢           ⁢   g     g         -     f   ⁢         Δ   ⁢           ⁢   g     ⁢             g       +     2   ⁢           ⁢   f   ⁢         (     grad   ⁢           ⁢   g     )     ·     (     grad   ⁢           ⁢   g     )         g   2           =   0.           (   9   )               
In other words, we have found the correct right hand side for the relighting-covariant version of Poisson equation (1)
 
                       2   ⁢   grad   ⁢           ⁢     f   ·       grad   ⁢           ⁢   g     g         +     f   ⁢         Δ   ⁢           ⁢   g     ⁢             g       -     2   ⁢           ⁢   f   ⁢         (     grad   ⁢           ⁢   g     )     ·     (     grad   ⁢           ⁢   g     )         g   2           ,           (   10   )               
that replaces Δg.
 
     Also, note that equation (9) can be written as 
                           (       ∂     ∂   x       +     A   x       )     ⁢     (       ∂     ∂   x       +     A   x       )     ⁢   f     +       (       ∂     ∂   y       +     A   y       )     ⁢     (       ∂     ∂   y       +     A   y       )     ⁢   f       =   0     ,           (   11   )               
with a “guidance field,” similar to what is described in Perez P., Gangnet M., Blake A.: Poisson image editing. ACM Transactions on Computer Graphics 22, 3 (July 2003), 313-318.
 
     
       
         
           
             
               
                 
                   
                     A 
                     ⁡ 
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     - 
                     
                       
                         
                           grad 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           g 
                         
                         g 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
     In mathematics this is called the connection form and it defines a modified, covariant derivative, which replaces conventional derivatives as in (11). These generally describe perceived gradients as opposed to true gradients in images. 
     Implementation 
     The above-described technique can be implemented similarly to the system described in U.S. Pat. No. 6,587,592, entitled “Generating Replacement Data Values for an Image Region,” by inventors Todor G. Georgiev, Mark Hamburg and Jen-Chan Chien. This patent is hereby incorporated by reference to provide details of the implementation of such as system. Note that the present invention improves upon the system described in U.S. Pat. No. 6,587,592 because the present invention matches texture contrast as well as pixel values while seamlessly reconstructing a region of an image. 
     Referring to  FIG. 2 , at a high level, the system presents an image to a user (step  202 ). Next, the system allows the user to select a defective area within the image (step  204 ). The system then identifies boundary pixels surrounding the defective area (step  206 ). The system also allows the user to identify a texture area within the image (or possibly within another image.) (step  208 ). The system then generates a replacement image for the defective area using data from the texture area (step  210 ). (This process is described in more detail below with reference to  FIG. 3 .) Next, the system substitutes the replacement image into the defective area to complete the reconstruction process (step  212 ). 
     In one embodiment of the present invention, the replacement image is generated as follows. First, the system divides pixels in the defective area and boundary pixels by corresponding pixels in the texture image, in which pixel value zero is replaced with a small number. This produces the first intermediate image I 1 (x, y) (step  302 ). 
     
       
         
           
             
               
                 
                   
                     
                       I 
                       1 
                     
                     ⁡ 
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       f 
                       ⁡ 
                       
                         ( 
                         
                           x 
                           , 
                           y 
                         
                         ) 
                       
                     
                     
                       g 
                       ⁡ 
                       
                         ( 
                         
                           x 
                           , 
                           y 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
     Next, the system solves the Laplace equation for the second intermediate image
 
Δ I   2 ( x, y )=0,   (14)
 
with Dirichlet boundary conditions defined by I 1 (x, y) at the boundary of the reconstruction area. This produces the second intermediate image I 2 (x, y) (step  304 ).
 
     The system then multiples the result by the texture image g(x, y) to produce a replacement image (step  306 )
 
 h ( x, y )= I   2 ( x, y ) g ( x, y ).   (15)
 
Finally, the system substitutes the defective area ƒ(x, y) in the original image with the replacement image h(x, y).
 
Alternative Embodiment that Uses Logs and Exponentiation
 
     Referring to  FIG. 4 , in an alternative embodiment of the present invention, the replacement image is generated using as follows. Instead of dividing, the system subtracts the log of pixels in the texture image from the log of corresponding pixels in the defective area and associated boundary pixels to produce the first intermediate image
 
 I   1 ( x, y )=log(ƒ( x, y ))−log( g ( x, y )) (step  402 ).   (16)
 
     Next, the system solves the Laplace equation for the second intermediate image ΔI 2 (x, y)=0, with Dirichlet boundary conditions defined by I 1 (x, y) at the boundary of the reconstruction area. This produces the second intermediate image I 2 (x, y) (step  404 ). 
     The system then adds the log of the pixels in the texture image to corresponding pixels in the second intermediate image and exponentiates the resulting pixels to produce the replacement image (step  406 )
 
 h ( x, y )=exp( I   2 ( x, y )+log( g ( x, y )))   (17)
 
The system then substitutes the defective area ƒ(x, y) in the original image with the replacement image h(x, y).
 
Results
 
     Traditional Poisson cloning between areas of different illumination can be a problem. To provide a clean example, we have tried to remove the scratch from the shadow area in  FIG. 1A  using only source material from the illuminated area. 
     In  FIG. 1C , we see the result of Poisson cloning from the illuminated area into the shadow area. It correctly matches pixel values at the boundary of the patch, but the cloned pebbles are still easy to spot. However, there is too much contrast in the reconstructed area of the image. 
       FIG. 1D  shows the result of our proposed illumination invariant method, equation (8). We see that not only the lighting is correct, but the method was able to clone texture in a really seamless way. Our experiments show that in a wide range of images equation (8) performs much better than the Poisson equation in terms of producing seamless cloning. 
       FIG. 5  presents another comparison between covariant cloning and Poisson cloning. The cloned area on the left is the result of standard Poisson cloning from the selected area, while the cloned are on the right is the result of covariant cloning from the same area. 
     Conclusion and Future Work 
     We have been able to find energy expression for reconstruction, covariant with illumination. Our results are much better than Poisson cloning. The proposed invariant energy approach potentially applies to any image processing technique that can be defined in terms of energy and corresponding differential equations. We modify the energy to produce invariant energy and covariant equations. Results are better because now perception and adaptation are taken into account. In this way we have embedded adaptation of the visual system into the mathematical formalism of the problem. 
     The foregoing descriptions of embodiments of the present invention have been presented only for purposes of illustration and description. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.