# Patent

## Title
Removal of image artifacts from sensor dust

## Abstract

Removal of the effects of dust or other impurities on image data is described. In one example, a model of artifact formation from sensor dust is determined. From the model of artifact formation, contextual information in the image and a color consistency constraint may be applied on the dust to remove the dust artifacts. Artifacts may also be removed from multiple images from the same or different cameras or camera settings.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This application claims benefit to U.S. Provisional Patent Application No. 60/942,431, filed on Jun. 6, 2007.


BACKGROUND
In photography or image acquisition and/or processing techniques, impurities can cause imperfections in any images produced. For example, if dust is introduced into a camera or image processing system, such dust can cause obstructions, shadows or other extraneous or undesired artifacts in any images that are ultimately produced. Such impurities may enter the system by any number of ways including, for example, when lenses are interchanged.
During lens exchange, sensors may become exposed to the environment while dust may gain entry into the system through any openings created by removal or displacement of the lens. The result is that the impurities may block light entering the system and may create dark spots on images.
Dust or other impurities or the effects caused by the presence of such impurities may be decreased or removed from an image processing or image capturing system. In one example, the impurities may be physically removed from a sensor. For example, cleaning liquids, brushes, vacuums, and/or dust adhesives may be applied to the sensor to remove any impurities on the sensor. In another example, images may be captured with the impurities in place and the effects of the impurities on the images that are captured may be removed via photo software. For example, dust particles may be not be noticed until after the images are captured and produced. In such processes, a cloning tool may be used to manipulate the image such that the effects of the dust particles are reduced in the final image. In another example, manual cloning may be performed or image inpainting and texture synthesis may be utilized to reduce the effects created by the impurities or dust in the system.
SUMMARY
The following presents a simplified summary of the disclosure in order to provide a basic understanding to the reader. This summary is not an extensive overview of the disclosure and it does not identify key/critical elements of the invention or delineate the scope of the invention. Its sole purpose is to present some concepts disclosed herein in a simplified form as a prelude to the more detailed description that is presented later.
Removal of effects of impurities, such as dust particles, from an image is described. In one example, an artifact model is determined. Additional contextual information in the image and/or a color consistency constraint on the impurities may be identified. Artifacts from the impurities are removed from identified dust regions on the image.
Many of the attendant features will be more readily appreciated as the same becomes better understood by reference to the following detailed description considered in connection with the accompanying drawings.



DESCRIPTION OF THE DRAWINGS
The present description will be better understood from the following detailed description read in light of the accompanying drawings, wherein:
FIGS. 1A-1I illustrate one example of dust regions in an image.
FIG. 2 illustrates one example of projecting dust transparency.
FIG. 3 illustrates examples of results of candidate detection.
FIG. 4 illustrates another example of results of candidate detection.
FIGS. 5A, 5B, and 5C illustrate optimization energies.
FIGS. 6A and 6B illustrate recovered functions for dust regions.
FIGS. 7A-7G illustrate another example of dust removal and candidate detection for a single image.
FIGS. 8A-8K illustrate another example of results for complex input images.
FIGS. 9A-9D illustrate artifacts resulting from impurities.
FIG. 10 is a block diagram showing an example method for recovering a dust-free image.
FIG. 11 is a block diagram showing an example computing environment in which the technologies described herein may be implemented.



Like reference numerals are used to designate like parts in the accompanying drawings.
DETAILED DESCRIPTION
The detailed description provided below in connection with the appended drawings is intended as a description of the present examples and is not intended to represent the only forms in which the present example may be constructed or utilized. The description sets forth the functions of the example and the sequence of steps for constructing and operating the example. However, the same or equivalent functions and sequences may be accomplished by different examples.
Formation of Dust Artifacts
FIGS. 1A-1I illustrate one example of dust regions in an image. In this example, an image of a leaf (FIG. 1A) is provided. The leaf in the image contains background information within dust regions. FIGS. 1B and 1C illustrate an example of identified dust regions that contain background information. This background information may be utilized in conjunction with an artifact formation model to obtain images with minimized or removed dust effects. In this example, texture synthesis is performed (FIGS. 1D and 1E) to obtain an image in which the dust effects have been removed. In FIGS. 1F and 1G, an alternate process of dust/impurity effect removal as described herein below is applied to the dust regions of the image. As FIGS. 1F and 1G illustrate, image results are obtained that are more similar to the ground truth (FIGS. 1H and 1I) than texture synthesis (FIGS. 1D and 1E). The term “image” and “digital image” as used herein typically refer to all or a portion of a digital photograph, typically embodied as a file comprising data in a digital image format. The term “ground truth” as used herein typically refers to the actual or original scene being photographed or digitally imaged.
In another example, sensor dust may accumulate on a low-pass filter resting upon or in front of a sensor array. Such a low-pass filter is typically a thin layer that slightly blurs the light reaching the sensor array so as to reduce Moiré effects and the like. Attenuation of light may be observed in an image as a result of the accumulated sensor dust on the filter. In addition, attenuation of light may also be related to imaging geometry specified by camera settings such as described in connection with FIG. 2. Thus, in this example, a space of image artifacts (e.g., the range of possible image effects caused by a particle of dust) may be identified in an image with respect to camera settings and possible solutions (e.g., possible appearances of the scene that is occluded by the dust) for the dust background may be determined corresponding to the identified space. For example, a darkened region may be identified within an image. The darkened region may represent a portion of the actual image or may alternatively represent dust or other impurities. In this example, candidate dust regions may be determined in the image based on adherence to image context and/or a dust artifact model. Certain regions of the image may be determined to contain dust effects.
Dust particles (or other impurities) may attenuate light and cause a corresponding alteration in an image. In one example, the light attenuation from dust particles may be represented as follows:

I(x)=U(x)·α(x)

where I(x) represents a recorded image intensity at a pixel x of a sensor array, U represents a dust-free image to be recovered (e.g., how the image would appear if there was no dust on the filter and/or sensor), and α models the attenuation due to sensor dust. In one example, the dust may lie on a low-pass filter rather than directly on the sensor. In this case, the artifact function α may represent a projection of the dust's transparency function β. The geometry of this projection may be dependent upon camera settings. Also, light passing through dust particles may undergo some amount of scattering that may be not be modeled by a transparency function as such scattering is typically considered to have a negligible effect. The geometry of this projection may also depend on camera settings, which may substantially affect α for a given β. FIGS. 9A-9D illustrate examples of light attenuation in two dimensions resulting from impurities such as dust with different camera settings. In these examples, greater height represents greater light attenuation. In FIG. 9A, an artifact is produced with the F-number of the camera set to F/22. In FIG. 9B, the camera is set to F/19. In FIG. 9C, the camera is set to F/16 and in FIG. 9D, the camera is set to F/11. As FIGS. 9A-9D illustrate, an artifact produced by a given dust may appear differently under different camera settings. In this example, artifact functions a may be estimated from a uniform scene and may further contain image noise. The term “uniform scene” as used herein typically refers to a scene consisting of a single constant color. The dust artifact function a typically describes the effects of dust and the like on a dust-free image. In one example, it describes the percentage of light transmitted though the dust at each pixel of the image.
Projection of Dust Effects
FIG. 2 illustrates an example model of projected dust artifacts including one example of projecting dust transparency. This model tends to describe how dust effects are projected onto a sensor according to camera geometries. Dust transparency may be projected from a low-pass filter 205 to a camera sensor 204. As FIG. 2 illustrates, light may be transmitted via an aperture A from a lens 201. The light may strike a dust particle 202 on the low-pass filter 205. The light may further be detected on a sensor 204. As a result of the effect of the dust particle 202 on the incoming light, the image on the sensor 204 may further contain an artifact 203 (α(x)). The dust transparency function may be represented as follows:

β:L2→[0,1]

where L2 represents the set of image pixels. The dust transparency function may manifest itself as an artifact function in the image as follows:

α:L2→[0,1]

α(x) in this example may represent the proportion of scene radiance that passes through the dust 202 and reaches a pixel x of sensor array 204.
If the camera has a focal length f that is larger than the offset d of the low-pass filter from the sensor, and the dust size is smaller than the aperture size A, the effect of an arbitrary point on the dust particle 202 may be spread over the sensor 204 according to a conventional rectangular or rect function. The rect function may be defined in one example as follows:




  
    
      
        
          
            ⊓
            τ
          
          ⁢
          
            (
            x
            )
          
        
        =
        
          
            
              0
            
            
              
                
                  if
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                    
                      x
                      /
                      τ
                    
                    
                  
                
                >
                
                  1
                  /
                  2
                
              
            
          
          
            
              
                1
                /
                2
              
            
            
              
                
                  if
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                    
                      x
                      /
                      τ
                    
                    
                  
                
                =
                
                  1
                  /
                  2
                
              
            
          
          
            
              1
            
            
              
                
                  if
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                    
                      x
                      /
                      τ
                    
                    
                  
                
                <
                
                  1
                  /
                  2
                
              
            
          
        
      
    
    
      
        Eqn
        .
        
          
        
        ⁢
        
          (
          1
          )
        
      
    
  




Based on triangle similarity (e.g., as illustrated in FIG. 2), the scale τ of the rect pulse may be calculated as follows:

τ=d·A/f 

In another example, the value of f/A may be equal to the camera's F-number setting, which may be recorded in an image file (e.g., in an exchangeable image file format (“EXIF”) data of the image file).
In another example, the projection from β to α may be expressed as a convolution operation as follows:

α=β*τ

If the sensor dust lies on a low-pass filter, blurring from the filter may also have an effect on the formation of α. Even so, such an effect is typically considered negligible.
Artifact Formation Model
An artifact formation model may be constructed based on a function space of possible dust artifacts α. A function space of possible dust artifacts α may be determined with respect to the projection geometry factor τ and the bounds of dust transparency β. The functions space typically provides a range of light attenuation functions for a given dust particle or the like. As FIG. 9 illustrates, as values of τ increase, dust artifacts may become additionally blurred. For example, a broader conventional convolution kernel as described in Eqn. (1) may produce an essentially more blurred image from dust artifacts. Also, if β:L2→[0,1] then a function space Dτ of valid artifacts a with respect to τ may be expressed as follows:

Dτ={α:β*τ=α, 0≦β≦1}  Eqn. (2)

Together with the image information within a dust region, this function space may implicitly define a space of possible dust backgrounds, which may further serve as a constraint on the dust removal solution.
Recovering a Dust-Free Region
Given dust region DεΩ where Ω is typically the set of all image pixels, dust removal may be performed to recover a dust-free appearance UD. In one example, UD may be further characterized as follows:

ID=UD·(β*τ)+n 

where n typically represents a noise level (e.g., intensity perturbations at an image pixel that may be caused by a variety of factors such as electronic and photometric fluctuations or the like).
The dust transparency function β and the geometry factor τ may be unknown since the low-pass filter displacement d may not be provided with a camera. In this case, contextual information IΩ/D from outside the dust region may be utilized in conjunction with the artifact formation model to recover the actual scene appearance that is occluded by dust or the like.
Energy Function Formulation
For example, the recovery may be formulated as the following Maximum A Posteriori (“MAP”) estimation:




  
    
      
        
          
            U
            ^
          
          D
        
        =
        
          arg
          ⁢
          
            
          
          ⁢
          max
          ⁢
          
            
          
          ⁢
          
            P
            ⁡
            
              (
              
                
                  U
                  D
                
                ,
                
                  α
                  |
                  I
                
              
              )
            
          
        
      
    
  
  
    
      
        =
        
          arg
          ⁢
          
            
          
          ⁢
          max
          ⁢
          
            
          
          ⁢
          
            P
            ⁡
            
              (
              
                
                  U
                  D
                
                ,
                α
                ,
                
                  U
                  D
                
                ,
                
                  I
                  
                    Ω
                    /
                    D
                  
                
              
              )
            
          
        
      
    
  
  
    
      
        =
        
          arg
          ⁢
          
            
          
          ⁢
          max
          ⁢
          
            
          
          ⁢
          
            
              P
              ⁡
              
                (
                
                  
                    
                      I
                      D
                    
                    |
                    
                      U
                      D
                    
                  
                  ,
                  α
                  ,
                  
                    I
                    
                      Ω
                      /
                      D
                    
                  
                
                )
              
            
            ·
            
              P
              ⁡
              
                (
                
                  
                    U
                    D
                  
                  ,
                  
                    α
                    |
                    
                      I
                      
                        Ω
                        /
                        D
                      
                    
                  
                
                )
              
            
            ·
            
              (
              
                I
                
                  Ω
                  /
                  D
                
              
              )
            
          
        
      
    
  
  
    
      
        =
        
          arg
          ⁢
          
            
          
          ⁢
          max
          ⁢
          
            
          
          ⁢
          
            
              P
              ⁡
              
                (
                
                  
                    
                      I
                      D
                    
                    |
                    
                      U
                      D
                    
                  
                  ,
                  α
                  ,
                  
                    I
                    
                      Ω
                      /
                      D
                    
                  
                
                )
              
            
            ·
            
              P
              ⁡
              
                (
                
                  
                    U
                    D
                  
                  ,
                  
                    α
                    |
                    
                      I
                      
                        Ω
                        /
                        D
                      
                    
                  
                
                )
              
            
          
        
      
    
  




If α is independent of UD and IΩ/D, and ID is conditionally independent of IΩ/D given UD and α, then:

ÛD=arg max P(ID|UD,α)·P(UD|IΩ/D)·P(α)

Expressed as a logarithmic energy function with minimization of:

E(UD,α|I)=λ1E1(ID|UD,α)+λ2E2(UD|IΩ/D)+λ3E3(α)  Eqn (3)

where the terms λ1, λ2, and λ3 are typically weights for their corresponding constraints E1, E2, and E3.
In one example, the term E1 is derived from the relationship ID=UD·α, which typically describes the basic relationship between a dust artifact, a corresponding recovered region, and a corresponding dusted region of an image
In one example, the term E2 is derived by comparison of sub-regions in an undusted region to sub-regions of equal size in the surrounding image areas. This energy term favors solutions whose sub-regions are similar to the surrounding image context. Basically, this is evaluated by taking each sub-region and comparing it with sub-blocks outside the dust region to find the sub-region that is most similar to it; then the difference between these sub-regions is the energy contributed to this energy term. As used herein, the term “sub-region” typically refers to a portion of a region (e.g., a 7 by 7 pixel sub-region of a 15 by 15 pixel region, or the like).
In one example, the term E3 is derived as the distance between the converged solution for alpha and the space of possible alphas determined from the model of projected dust artifacts. To compute this distance, we typically find the closest point in the subspace to alpha by computing PD(α)εDτ as described herein below, and then by calculating the distance between alpha and the closest point according to equation 6.
In another example, the energy term E1 is the energy function constraint from artifact formation, which penalizes solutions according to how different the dust-free image multiplied by the dust artifact function α is from the observed image or ground truth. The term E1 may use the artifact formation model for image information in the dust region. E1 may further be defined as the L2 distance between ID and UD·α as follows:




  
    
      
        
          
            E
            1
          
          ⁡
          
            (
            
              
                
                  I
                  D
                
                |
                
                  U
                  D
                
              
              ,
              α
            
            )
          
        
        =
        
          
            1
            2
          
          ⁢
          
            
              
              
                
                  I
                  D
                
                -
                
                  
                    U
                    D
                  
                  ·
                  α
                
              
              
            
            2
          
        
      
    
    
      
        Eqn
        .
        
          
        
        ⁢
        
          (
          4
          )
        
      
    
  




The coefficient λ1 is related to the noise level of n and may be large and/or proportional to the signal-to-noise ratio. For example, the noise level n may be large if the signal-to-noise ratio is large. In one example, the relation between λ1 and the noise level of n is described by T. F. Chan and C. K. Wong in “Total variation blind deconvolution,” IEEE Trans. Image Proc., 7(3):370-375, 1998, which is incorporated herein by reference in its entirety.
In another example, the term E2 is the contextual constraint of the energy function, which penalizes solutions according to how different the appearance of a sub-region of a recovered region is from the surrounding image areas. Thus, the term E2 may utilize contextual constraints from the surrounding image (e.g., the context is the surrounding image areas and provides an indication of what the undusted region should look like and serves as a constraint for the algorithm). The recovered region represented by the parameter UD may have local appearance features that may be consistent with those in neighboring areas, and image transitions may be smooth at the region boundaries. The energy may further be defined as follows:




  
    
      
        
          
            E
            2
          
          ⁡
          
            (
            
              
                U
                D
              
              |
              
                I
                
                  Ω
                  /
                  D
                
              
            
            )
          
        
        =
        
          
            ∑
            
              
                D
                i
              
              ∈
              D
            
          
          ⁢
          
            dist
            ⁢
            
              
            
            ⁢
            
              
                (
                
                  
                    U
                    
                      D
                      i
                    
                  
                  ,
                  
                    I
                    
                      Ω
                      /
                      D
                    
                  
                
                )
              
              2
            
          
        
      
    
    
      
        Eqn
        .
        
          
        
        ⁢
        
          (
          5
          )
        
      
    
  




where Di may be a member of a set of overlapped sub-blocks D, and:



  
    
      dist
      ⁢
      
        
      
      ⁢
      
        (
        
          
            U
            
              D
              i
            
          
          ,
          
            I
            
              Ω
              /
              D
            
          
        
        )
      
    
    =
    
      
        1
        2
      
      ⁢
      
        
          
          
            
              U
              
                D
                i
              
            
            -
            
              I
              
                B
                i
              
            
          
          
        
        2
      
      ⁢
      
        
      
      ⁢
      with
    
  




  
    
      B
      i
    
    =
    
      
        
          arg
          ⁢
          
            
          
          ⁢
          min
        
        
          B
          ∈
          
            Ω
            /
            D
          
        
      
      ⁢
      
        
          
            
            
              
                U
                
                  D
                  i
                
              
              -
              
                I
                B
              
            
            
          
          2
        
        .
      
    
  



In one example, the energy defined by equation 5 is similar to that described by N. Komodakis and G. Tziritas in “Image completion using global optimization,” Proc. IEEE Computer Vision and Pattern Recognition, pages 442-452, 2006, which is incorporated herein by reference in its entirety.
In another example, the term E3 is the function space constraint of the energy function, which penalizes solutions according to how different the recovered artifact function is from the space of possible artifact functions (as expressed by equation 2) from the model of projected dust artifacts. Thus, the term E3 may represent a constraint from the function space of α. For an estimated α, E3(α) may be defined as the minimal L2 distance to the function space Dτ as follows:




  
    
      
        
          
            E
            3
          
          ⁡
          
            (
            α
            )
          
        
        =
        
          
            1
            2
          
          ⁢
          
            
              
              
                α
                -
                
                  
                    P
                    
                      D
                      τ
                    
                  
                  ⁡
                  
                    (
                    α
                    )
                  
                
              
              
            
            2
          
        
      
    
    
      
        Eqn
        .
        
          
        
        ⁢
        
          (
          6
          )
        
      
    
  




where PDτ(α) may include the projection of α onto the space Dτ:




  
    
      P
      
        D
        τ
      
    
    ⁡
    
      (
      α
      )
    
  
  =
  
    arg
    ⁢
    
      
    
    ⁢
    
      
        min
        
          u
          ∈
          
            D
            τ
          
        
      
      ⁢
      
        
        
          α
          -
          u
        
        
      
    
  




In one example, computing PDτ(α)εDτ is equivalent to finding β* where (0<β*<1) that minimizes where




  F
  =
  
    
      1
      2
    
    ⁢
    
      
        
        
          α
          -
          
            β
            *
            
              M
              τ
            
          
        
        
      
      2
    
  




where Mτ=τ. Also, β* may further be solved using a partial derivative:





  
    
      ∂
      F
    
    
      ∂
      β
    
  
  =
  
    
      (
      
        α
        -
        
          β
          *
          
            M
            τ
          
        
      
      )
    
    *
    
      
        M
        _
      
      τ
    
  




where Mτ=τ(x, y) and Mτ=τ(−x, −y) and where estimating the value of the projection geometry factor τ is described herein below.
The term E2 may be any texture synthesis or inpainting objective function to propagate contextual information from the surrounding image. In one example, a patch-based texture synthesis may be used, such as described by A. A. Efros and W. T. Freeman in “Image quilting for texture synthesis and transfer,” ACM SIGGRAPH, pages 341-346, 2001, in conjunction with a global optimization procedure, such as by N. Komodakis and G. Tziritas in “Image completion using global optimization,” incorporated by reference herein above. The synthesis may be regulated by physical knowledge on artifact formation (E3) together with observed image information within the dust region (E1).
Energy Function Optimization
Optimization of an energy function may be performed. For example, the energy function of equation (3) may be optimized in which estimation of or may be correlated with a prediction of UD. Similarly, UD may depend on an accurate function α. Thus, an alternating minimization approach may be used to optimize the energy function E(UD,α|I). This iterative optimization technique alternately solves for α and UD. During the iterations, once the value of α converges, the corresponding minimized value of UD is taken as the solution. Minimizing the energy function in this manner directly yields the value of UD, which is the dust-free image and the final output of the algorithm. In one example, an appropriate alternating minimization approach is described by T. F. Chan and C. K. Wong in “Total variation blind deconvolution,” incorporated by reference herein above.
For example, texture synthesis may be applied to a set of candidate dust regions. In this example, an initialization parameter may be determined such as UD(0) via the texture synthesis. In addition, initialization parameters may be determined by fitting two-dimensional (“2D”) Gaussians on small overlapping image patches and evaluating concavity. An alternating sequence of conditional minimizers may then be determined as follows:

uD(0)→α(0)→uD(1)→ . . . →uD(n)→α(n)→ . . .

according to:

α(n)=arg min E(α|I,UD(n))

UD(n+1)=arg min E(U|I,α(n))

where partial derivatives of E can be computed from equations (3), (4), (5), and/or (6) as follows:



  
    
      
        ∂
        E
      
      /
      
        ∂
        
          U
          D
        
      
    
    =
    
      
        
          λ
          1
        
        ⁢
        
          
            α
            ′
          
          ⁡
          
            (
            
              
                
                  U
                  D
                
                ·
                α
              
              -
              
                I
                D
              
            
            )
          
        
      
      +
      
        
          λ
          2
        
        ⁢
        
          
            ∑
            
              
                D
                i
              
              ∈
              D
            
          
          ⁢
          
            (
            
              
                U
                
                  D
                  i
                
              
              -
              
                I
                
                  
                    B
                    i
                  
                  ⁢
                  
                    
                  
                
              
            
            )
          
        
      
    
  




  
    
      
        ∂
        E
      
      /
      
        ∂
        α
      
    
    =
    
      
        
          λ
          1
        
        ⁢
        
          
            U
            D
            ′
          
          ⁡
          
            (
            
              
                
                  U
                  D
                
                ·
                α
              
              -
              
                I
                D
              
            
            )
          
        
      
      +
      
        
          λ
          3
        
        ⁡
        
          (
          
            α
            -
            
              
                P
                
                  D
                  τ
                
              
              ⁡
              
                (
                α
                )
              
            
          
          )
        
      
    
  



The sequence may further be iteratively computed until α converges, or until ∥α(n)−α(n+1)∥<ε where ε is an arbitrary small number. At this point, values UD and α of the energy function are considered minimized. The converged or minimized value of α is also known herein as the “recovered artifact function”.
Evaluation of Color Consistency Constraints
Color consistency constraints may be evaluated to further improve recovery. For example, the process may be applied to each color channel of an image independently and correlations between channels may be identified and applied as additional constraints for radiometrically calibrated cameras. A dust particle may be composed of any number of materials but are typically composed of a single material. In one example, one may generally assume that a dust particle is composed of a single material that is monochromatic or of uniform color. Upon normalization, the α may be proportional in multiple channels (e.g., three channels such as red, green, and blue or “r, g, b”), such that:

αr(x)/Σxαr(x)=αg(x)/Σxαg(x)/Σxαb(x)

The normalized α functions in the multiple channels (e.g., three channels such as r, g, b) may have a minimal Kullback-Leibler (“K-L” or “KL”) divergence to an optimized α* as follows:




  
    
      
        
          
            α
            *
          
          =
          
            
              
                arg
                ⁢
                
                  
                
                ⁢
                min
              
              
                
                  ∑
                  
                    α
                    ⁡
                    
                      (
                      x
                      )
                    
                  
                
                =
                1
              
            
            ⁢
            
              
                ∑
                
                  
                    i
                    =
                    r
                  
                  ,
                  g
                  ,
                  b
                
              
              ⁢
              
                KL
                (
                
                  α
                  ⁢
                  
                    
                    
                  
                  ⁢
                  
                    
                      α
                      i
                    
                    /
                    
                      
                        ∑
                        x
                      
                      ⁢
                      
                        α
                        i
                      
                    
                  
                
                )
              
            
          
        
        )
      
    
    
      
        Eqn
        .
        
          
        
        ⁢
        7
      
    
  




where KL() represents the K-L divergence:




  
    KL
    ⁡
    
      (
      
        P
        ||
        Q
      
      )
    
  
  =
  
    
      ∑
      x
    
    ⁢
    
      
        P
        ⁡
        
          (
          x
          )
        
      
      ⁢
      log
      ⁢
      
        
          P
          ⁡
          
            (
            x
            )
          
        
        
          Q
          ⁡
          
            (
            x
            )
          
        
      
    
  




From equation 7, an energy function may be derived that may represent a color consistency constraint on dust as follows:




  
    
      E
      4
    
    ⁡
    
      (
      
        
          α
          r
        
        ,
        
          α
          g
        
        ,
        
          α
          b
        
      
      )
    
  
  =
  
    
      1
      2
    
    ⁢
    
      
        ∑
        
          
            c
            =
            r
          
          ,
          g
          ,
          b
        
      
      ⁢
      
        
          
          
            
              α
              c
            
            -
            
              
                α
                *
              
              ·
              
                
                  ∑
                  x
                
                ⁢
                
                  α
                  c
                
              
            
          
          
        
        2
      
    
  




This energy term may further be integrated with eqn. 3 such that:

E=λ1E1+λ2E2+λ3E3+λ4E4 

Alternatively or additionally, in a minimization algorithm, a partial derivative of E with respect to α for each channel c=r,g,b may be given as follows:




  
    
      ∂
      E
    
    /
    
      ∂
      
        α
        c
      
    
  
  =
  
    
      
        λ
        1
      
      ·
      
        ∑
        
          
            U
            D
            ′
          
          ⁡
          
            (
            
              
                
                  U
                  D
                
                ·
                
                  α
                  c
                
              
              -
              
                I
                D
              
            
            )
          
        
      
    
    +
    
      
        λ
        3
      
      ·
      
        (
        
          
            α
            c
          
          -
          
            
              P
              
                D
                τ
              
            
            ⁡
            
              (
              
                α
                c
              
              )
            
          
        
        )
      
    
    +
    
      
        λ
        4
      
      ·
      
        (
        
          
            α
            c
          
          -
          
            
              α
              *
            
            ·
            
              
                ∑
                x
              
              ⁢
              
                α
                c
              
            
          
        
        )
      
    
  




Estimation of Projection Geometry Factor τ

In one example, the value of τ may be unknown. For example, a low-pass filter displacement d may be unavailable from a sensor. If τ defines a function space Dτ of α, the energy term E3 may be affected (e.g., eqn. (6)). For example, the volume of space Dτ may be negatively related to the value of τ. When τ approaches zero in this case, Dτ may accommodate any function 0≦α≦1. As τ increases, the space of valid artifact functions may become constricted. Thus, values of τ that are greater than the actual value τ* have a corresponding Dτ that may not admit true artifact functions in an image. As a result, the optimization energy E computed for τ≧τ* may tend to increase sharply with respect to τ. Alternatively, a space Dτ for τ≦τ* may admit valid artifacts, and hence may have optimization energies that decrease less rapidly with respect to τ. Thus, in this example, some decrease in energy may exist because a broader range of artifact functions may allow more flexible use of contextual data.
Based on this characteristic, τ may be estimated by examining the optimization energy E computed for sampled values of τ. FIGS. 5A, 5B, and 5C illustrate optimization energies. In this example, optimization energy Ed is illustrated against low-pass filter displacement d for twelve dust regions in an imaging system. In FIG. 5A, results for a single input image at F/11 are provided. In FIG. 5B, results for two images at F/11 and F/22 are provided. FIG. 5C illustrates results of four images at F/11, F/16, F/19, and F/22. For a single image, d may be estimated from second derivatives, and for multiple images, d may be determined from the minimum energy.
FIG. 5A further illustrates estimating τ by examining the optimization energy E for sampled values of τ. If E changes rapidly for τ>τ* and slowly for τ≦τ*, r may be estimated as arg maxτ∂2E/∂τ2. In another example, discrepancies between τ and τ* are small, for example, when valid artifacts still lie in Dτ for an underestimated τ, and dust particles without sharp edges are still admissible for a slightly overestimated τ. Dust particles typically do not have sharp edges but, if they do, they may not be admissible if the value of τ is overestimated.
In another example, d includes a fixed value for a given camera or imaging system. In this example, if the distance d is recovered for a camera or imaging system (e.g., using multiple images), then other users of the system may utilize the value to determine τ as d·A/f where f/A is the F-number setting.
Detection of Candidate Dust Regions
Candidate dust regions may be detected using the estimated value of τ. For example, when τ is set, optimization energy values for regions in an image may be determined. Since lower energies indicate a recovery result that is more consistent with image context and the dust artifact model in this example, the corresponding regions may be more likely candidates to contain dust. FIG. 3 and FIG. 4 illustrate examples of results of candidate detection. In FIG. 3, candidate dust regions are detected based on optimization energy in which the only true dust regions are E=0.07. In FIG. 4, candidate dust regions are detected based on optimization energy in which the only true dust region is E=0.06. Additional candidates in FIG. 4 are part of the image texture and have less color consistency in their estimated artifact functions.
As illustrated in FIGS. 3 and 4, dust artifacts may often be distinguished from dark scene spots because of dust projection characteristics and color consistency. In another example, a list of candidate regions ordered by increasing energy may be presented to the user to aid in dust detection.
Example Recovered Dust-Free Images
In FIGS. 1A-1I of example recovered dust-free images, energy function coefficients were set to λ1=0.9, λ2=0.4, λ3=0.9, and λ4=0.9 and the value of τ may be determined to be, for example, 10. From an ordered list of candidate dust regions, candidate dust regions were selected for image recovery as illustrated in FIGS. 1A-1I. Comparison between the results of texture synthesis and ground truth indicate that texture synthesis generates leaf structures and texture details that are different from the ground truth. Also, some leaf details appear slightly blurred due to texture irregularity and patch blending. In contrast, the present examples yield results that recover most of the original leaf appearance, as exhibited in FIGS. 1F and 1G. With the present examples, there is less susceptibility to blurring at least because of the use of structural constraints provided by the dust region and artifact formation modeling.
FIGS. 7A-7G illustrate another example of dust removal and candidate detection for a single image. FIG. 7A illustrates 17 actual dust regions among the top 18 candidates. Certain actual dust regions may be missing from the candidate list and other regions may include non-dust regions that are included among the candidates. The candidate list may aid a user in dust detection. FIG. 7B illustrates the recovered image, FIG. 7C illustrates the ground truth, FIG. 7D illustrates the original patch, FIG. 7E illustrates the resulting image, FIG. 7F illustrates texture synthesis of the image, and FIG. 7G illustrates the ground truth. The ground truth image in FIG. 7C is obtained with a camera that is free of sensor dust. For clearer examination of recovery quality, one dust region is enlarged for examination of recovery quality in comparison to texture synthesis and the ground truth.
As FIGS. 7A-7G illustrate, in the evaluation of dust candidates (τ determined to be 4), 17 of the 20 actual dust regions in the image appear among the top 18 candidates in the ordered list. The actual dust regions are determined manually from a photo of a uniform scene. The three overlooked dust regions are also indicated and one incorrect candidate of the 18 is also identified. Thus, the user is provided with a tool for dust detection.
Multiple-Image Input
Multiple input images may be examined. Also, any of the different images may be obtained at different camera settings. Having multiple input images, even with different camera settings, detection and removal of dust artifacts may be improved as described. The dust transparency function β may be considered fixed among images captured within a single session, for example, and this additional constraint may enable estimation of β as well as a more reliable determination of d.
In one example, consider a set of images (e.g., Ii,i=1,2,5,m) and their corresponding F-numbers, ρ1,ρ2,5,ρm. Similar to the formulation of color consistency in dust, α functions in these images may closely correspond to a common β as follows:




  
    
      
        β
        =
        
          
            
              arg
              ⁢
              
                
              
              ⁢
              min
            
            β
          
          ⁢
          
            
              ∑
              i
            
            ⁢
            
              
                
                
                  
                    β
                    *
                    
                      M
                      
                        τ
                        i
                      
                    
                  
                  -
                  
                    α
                    i
                  
                
                
              
              2
            
          
        
      
    
    
      
        eqn
        .
        
          
        
        ⁢
        
          (
          8
          )
        
      
    
  




where Mτi=τi and τi=d/ρi. Thus, an energy term may be defined that represents consistency of β among multiple images as follows:




  
    
      
        
          E
          5
        
        =
        
          
            E
            ⁡
            
              (
              
                
                  α
                  1
                
                ,
                
                  α
                  2
                
                ,
                5
                ,
                
                  α
                  n
                
                ,
                d
              
              )
            
          
          =
          
            
              1
              2
            
            ⁢
            
              
                ∑
                i
              
              ⁢
              
                
                  
                  
                    
                      β
                      *
                      
                        M
                        
                          τ
                          i
                        
                      
                    
                    -
                    
                      α
                      i
                    
                  
                  
                
                2
              
            
          
        
      
    
    
      
        eqn
        .
        
          
        
        ⁢
        
          (
          9
          )
        
      
    
  




in which Mτi=τi and which has a derivative:

∂E5/∂αi=β*Mτi−αi 

Thus, the overall energy function for multiple-image input may be represented as follows:




  
    
      
        
          E
          multi
        
        =
        
          
            
              ∑
              
                i
                =
                1
              
              m
            
            ⁢
            
              E
              d
              i
            
          
          +
          
            
              λ
              5
            
            ·
            
              E
              5
            
          
        
      
    
    
      
        eqn
        .
        
          
        
        ⁢
        
          (
          10
          )
        
      
    
  




where Edi denotes a single-image energy for each Ii.
Estimation of d and β
Values of d and β may be estimated. For example, d may be estimated with a larger number of input images. In this example, among m images, a set of α functions (e.g., α1,5 αm) may be compared for each dust region. If the α functions arise from the same dust, they should satisfy m equations αi=β*Md/ρi, i=1,5,m, where Md/ρi=d/ρi, the correct value of d in this example providing the same β when deconvolving the functions αi by n d/ρi otherwise, the inconsistency in β may lead to a high energy (see, e.g., equation 9).
Returning to FIGS. 5A-5C, greater reliability in estimating d may be demonstrated. For sampled values of d, the optimization energy may be denoted as Ed, and may be plotted with respect to d. In this example, λ5 may be set to 0.6. With two images as input, a minimum in Ed is noticeable. With four images the minimum becomes clearer. Simultaneously, an estimate of β may be computed from eqn. (8). Given α1, α2,5,αn, the function β can be solved by setting the partial derivative of Σi∥β*Mτi−αi∥2, Mτi=ti, with respect to β to zero. Thus, recovered β functions may be expressed as:

β=deconv(Σ(αi* Mτi), Σ(Mτi* Mτi))

where C=deconv(A,B) is the deconvolution operation to seek a C that satisfies A=B*C.
Recovered β functions for two of the dust regions are further illustrated in FIGS. 6A and 6B. In FIGS. 6A and 6B, two β functions are derived from multiple-image input. In this example, with multiple input images, candidate dust regions may be more reliably detected. For example, a powerful constraint is that the multiple input images must have similar β functions in solving for β.
In another example, a low-pass filter in a camera blurs a photograph by one or two pixels in order to prevent aliasing and Moiré effects. Since sensor dust lies on this filter, the blurring it induces may also influence the formation of a dust artifact. For a low-pass filter that blurs an image by one pixel in one dimension (“1D”) in this example, an image may be obtained as follows:

I=(U·α)*1 

where U is the dust-free image prior to filtering. If the dust were not present, then the low-pass filtered image may instead be I′=U*1. The original artifact function α without low-pass filtering may thus be transformed to α′=I/I′ by the low-pass filter. In the discrete case, (f*1)(x)=[f(x)+f(x+1))]/2, such that the artifact function may be expressed as follows:




  
    
      α
      ′
    
    ⁡
    
      (
      x
      )
    
  
  =
  
    
      α
      ⁡
      
        (
        x
        )
      
    
    +
    
      
        
          U
          ⁡
          
            (
            
              x
              +
              1
            
            )
          
        
        
          
            U
            ⁡
            
              (
              x
              )
            
          
          +
          
            U
            ⁡
            
              (
              
                x
                +
                1
              
              )
            
          
        
      
      ·
      
        [
        
          
            α
            ⁡
            
              (
              
                x
                +
                1
              
              )
            
          
          -
          
            α
            ⁡
            
              (
              x
              )
            
          
        
        ]
      
    
  




The transformed artifact α′(x) may be bounded by α(x) and α(x+1). In another example, because of image noise and a smoothness of α=β*τ, α and α may be approximated to ignore the effect of the low-pass filter on dust artifacts.
FIGS. 8A-8K illustrate another example of results for complex input images. In this example, images were obtained by an imaging device (e.g., camera). In FIGS. 8A-8C, pictures were obtained at F/16, F/14, and F/11 respectively. FIG. 8A illustrates candidate detection results using only one image. There exists only two actual dust regions on the sensor. Using the photos (FIGS. 8A, 8B, and 8C) yields two actual dust regions as the top two candidates. In FIGS. 8D and 8E, close-ups of the dust regions in the images of FIGS. 8A-8C are presented. In FIGS. 8F and 8G, texture synthesis results are presented containing a synthesis region. FIGS. 8H and 8I illustrate results of single-image dust removal and FIGS. 8J and 8K illustrate the result of dust removal using all three images (FIGS. 8A-8C) together.
Two dust regions were examined although the photographs also contain additional small dark regions. Detection of candidate dust regions is performed in which each image may be processed independently. Alternatively or additionally, a single-image method may be performed. For example, applying the single-image method on the image of FIG. 8A, two true dust regions appear among the top 11 candidates. Similar results may be obtained when processing the other images (e.g., FIG. 8B and 8C) individually. When using all three images as input, the two dust regions become the top two candidates. In the close up images, the recovery results (FIGS. 8H-8K) are improved when compared to that of texture synthesis (FIGS. 8F-8G).
Thus, a system and method is described in which an approach to sensor dust removal is applied that may utilize image information inside a damaged region, or region occluded by an artifact. To effectively utilize this data in one example, an artifact formation model for sensor dust is provided in which the dust region information, together with the artifact model, jointly provides a constraint on the possible dust removal solutions. Image context and color consistency of dust are additionally utilized to recover an image that closely matches the actual scene. When multiple images are available, the method and system can offer a more reliable list of candidate dust regions from which to choose.
In another example, the system and method may be applied to other applications. For example, similar artifacts may appear in scanned images due to fingerprints or smudges on the apparatus (e.g., scanner glass). The use of contextual information in the dust removal technique may be applied to such images as well. Accordingly, the term “dust” as used herein typically refers to dust, particles, fingerprints, smudges, and/or any other object(s), substance(s), or the like that may occlude the original scene or ground truth in an image. The term “artifact” as used herein typically refers to the occlusive effect of such dust on an image. The term “recovering a dust-free image” or “recovering an artifact-free image” or the like typically refers to processing an image as described herein resulting in an image wherein the effects of such artifacts are minimized or removed from the image such that the image very closely reflects the ground truth. Such a recovered image (or region) may be described as “undusted” or “dust-free”. Note that the ground truth may be an actual scene, such as a landscape, and/or another image, as in the case of scanning and the like.
FIG. 10 is a block diagram showing an example method 1000 for recovering a dust-free image. Method 1000 may be performed in a computing environment such as that described in connection with FIG. 11. Such a computing environment may exist within a digital camera, such as a digital camera producing an original image, or may alternatively be a computing device such as a personal computer or the like.
Block 1010 typically indicates obtaining a digital image that may include dust artifacts. Such artifacts may be the result of dust or the like located on the sensor array of the digital camera producing the image or on a low-pass filter or the like, or on any other surface, positioned in front of the sensor. The digital image may be an original image, such as one just produced by a digital camera by a user taking a picture, or it may be any digital image that may or may not have undergone previous processing for any purpose, including a copied image, a scanned image, a video frame, or the like. Once an image has been obtained, then method 1000 typically continues at block 1020a. 
Block 1020a typically indicates detecting a dust artifact in the image. In general, this is done as described herein above by partitioning the image into small overlapping regions, fitting a Gaussian function to each region and determining if the Gaussian function indicates a dust artifact. In one example, the partitions may be 15 by 15 pixels in size. In other examples, the size of the regions may vary one from another and/or the regions may be rectangular rather than square. An example method 1020b for detecting a dust artifact in an image is described in more detail in connection with block 1020b. Once a dust artifact has been detected, then method 1000 typically continues at block 1030a. 
Block 1030 typically indicates processing a dust artifact to recover a dust-free region. In one example, this processing may include formulating an energy function, evaluating color consistency constraints, and optimizing the energy function. In another example, these steps may have already been performed during the detecting step as described in connection with block 1020a. The final aspect of processing typically includes recovering a dust-free region according to the minimized values of the corresponding selected region's energy function as described herein above. Once all dust artifacts in an image have been detected and the dust-free region recovered, method 1000 is typically complete.
Block 1020b provides an example method 1020b for detecting a dust artifact in a region of the digital image. In general, an image is partitioned into small overlapping regions and each region is analyzed for evidence of a dust artifact or the like. Each region, or candidate region, including such an artifact may be processed if selected (see block 1025) to recover a dust-free region.
Block 1021 typically indicates partitioning the image into small overlapping regions. In one example, a region may be 15 by 15 pixels in size. The exact size of a region may be selected to best detect dust artifacts on an expected size. The exact overlap of a region may be selected to avoid missing artifacts located on region boundaries. Once an image has been partitioned onto small overlapping regions, then method 1020b typically continues for each such region at block 1022.
Block 1022 typically indicates fitting a Gaussian function to a region. In one example, the fitting of a Gaussian function to a region is done in a conventional manner. Once fitted to a region, the Gaussian function is evaluated for indication of a dust artifact in the region. In one example, such may be indicated by a concave brightness structure suggesting attenuation caused by a possible dust particle or the like. Regions with dust artifacts are considered candidate regions; iterative optimization as described herein above and in connection with blocks 1024b and 1024b is then used to select regions considered to include artifacts. Once the fitting and evaluation have been completed, then method 1020b typically continues at block 1023.
Block 1023 typically indicates computing a projection geometry factor τ. In general, additionally considering FIG. 2, the actual projection geometry factor τ* may not be known when the distance d between low-pass filter 205 and sensor array 204 is not known. Thus the projection geometry factor τ is estimated as described herein above and then method 1020b typically continues at block 1024.
Block 1024a typically indicates iteratively optimizing an energy function of a region including formulating the energy function. Optimizing the energy function typically includes evaluating constraints based on artifact formation, context, dust characteristics, and color consistency constraints as described herein above. An example method 1024b for optimizing an energy function is described in more detail in connection with block 1024b. Once optimized, then method 1020b typically continues at block 1025.
Block 1025 typically indicates selecting a dust region based on energy value. In one example, this is done by showing a user the candidate regions with the lowest energy values and allowing the user to decide which regions contain dust or the like. In another example, selection may be made by method 1020b based on the optimization energy value of a candidate region being below a certain value (such as a value established by a user or the like). Once a candidate region is selected as including a dust artifact, the selected region is processed to recover a dust-free region as per block 1030.
Block 1024b provides an example method 1024b for iteratively optimizing an energy function used in recovering a dust-free region. Once all regions including artifacts have been recovered, then the image is considered recovered and dust-free.
Block 1041 typically indicates formulating an energy function to be used in recovering a dust-free region. In one example, an energy function for recovery is formulated as described herein above. Such an energy function may utilize an artifact formation model, contextual constraints from the image surrounding the region, and constraints from the function space of α. Once the energy function is formulated, then method 1024b typically continues at block 1042.
Block 1042 typically indicates evaluating color consistency constraints. In one example, color constraints may be evaluated as described herein above. In another example, color consistency constraints may not be evaluated. In yet another example, the evaluating may be performed as part of the optimizing. Once color consistency constraints have been evaluated, then method 1024b typically continues at block 1043.
Block 1043 typically indicates computing the optimization energy of a region using the formulated energy function. In one example, the energy function is optimized as described herein above. Once the energy function is optimized, then method 1024b is typically complete.
Once method 1024b is completed for all selected regions then the image is considered recovered and dust-free.
FIG. 11 is a block diagram showing an example computing environment 1100 in which the technologies described herein may be implemented. A suitable computing environment may be implemented with numerous general purpose or special purpose systems. Examples of well known systems may include, but are not limited to, cell phones, personal digital assistants (“PDA”), personal computers (“PC”), hand-held or laptop devices, microprocessor-based systems, multiprocessor systems, servers, workstations, consumer electronic devices, set-top boxes, and the like.
Computing environment 1100 typically includes a general-purpose computing system in the form of a computing device 1101 coupled to various components, such as peripheral devices 1102, 1103, 1104 and the like. System 1100 may couple to various other components, such as input devices 1103, including voice recognition, touch pads, buttons, keyboards and/or pointing devices, such as a mouse or trackball, via one or more input/output (“I/O”) interfaces 1112. The components of computing device 1101 may include one or more processors (including central processing units (“CPU”), graphics processing units (“GPU”), microprocessors (“μP”), and the like) 1107, system memory 1109, and a system bus 1108 that typically couples the various components. Processor 1107 typically processes or executes various computer-executable instructions to control the operation of computing device 1101 and to communicate with other electronic and/or computing devices, systems or environment (not shown) via various communications connections such as a network connection 1114 or the like. System bus 1108 represents any number of several types of bus structures, including a memory bus or memory controller, a peripheral bus, a serial bus, an accelerated graphics port, a processor or local bus using any of a variety of bus architectures, and the like.
System memory 1109 may include computer readable media in the form of volatile memory, such as random access memory (“RAM”), and/or non-volatile memory, such as read only memory (“ROM”) or flash memory (“FLASH”). A basic input/output system (“BIOS”) may be stored in non-volatile or the like. System memory 1109 typically stores data, computer-executable instructions and/or program modules comprising computer-executable instructions that are immediately accessible to and/or presently operated on by one or more of the processors 1107.
Mass storage devices 1104 and 1110 may be coupled to computing device 1101 or incorporated into computing device 1101 via coupling to the system bus. Such mass storage devices 1104 and 1110 may include non-volatile RAM, a magnetic disk drive which reads from and/or writes to a removable, non-volatile magnetic disk (e.g., a “floppy disk”) 1105, and/or an optical disk drive that reads from and/or writes to a non-volatile optical disk such as a CD ROM, DVD ROM 1106. Alternatively, a mass storage device, such as hard disk 1110, may include non-removable storage medium. Other mass storage devices may include memory cards, memory sticks, tape storage devices, and the like.
Any number of computer programs, files, data structures, and the like may be stored in mass storage 1110, other storage devices 1104, 1105, 1106 and system memory 1109 (typically limited by available space) including, by way of example and not limitation, operating systems, application programs, data files, directory structures, computer-executable instructions, and the like.
Output components or devices, such as display device 1102, may be coupled to computing device 1101, typically via an interface such as a display adapter 1111. Output device 1102 may be a liquid crystal display (“LCD”). Other example output devices may include printers, audio outputs, voice outputs, cathode ray tube (“CRT”) displays, tactile devices or other sensory output mechanisms, or the like. Output devices may enable computing device 1101 to interact with human operators or other machines, systems, computing environments, or the like. A user may interface with computing environment 1100 via any number of different I/O devices 1103 such as a touch pad, buttons, keyboard, mouse, joystick, game pad, data port, and the like. These and other I/O devices may be coupled to processor 1107 via I/O interfaces 1112 which may be coupled to system bus 1108, and/or may be coupled by other interfaces and bus structures, such as a parallel port, game port, universal serial bus (“USB”), fire wire, infrared (“IR”) port, and the like.
Computing device 1101 may operate in a networked environment via communications connections to one or more remote computing devices through one or more cellular networks, wireless networks, local area networks (“LAN”), wide area networks (“WAN”), storage area networks (“SAN”), the Internet, radio links, optical links and the like. Computing device 1101 may be coupled to a network via network adapter 1113 or the like, or, alternatively, via a modem, digital subscriber line (“DSL”) link, integrated services digital network (“ISDN”) link, Internet link, wireless link, or the like.
Communications connection 1114, such as a network connection, typically provides a coupling to communications media, such as a network. Communications media typically provide computer-readable and computer-executable instructions, data structures, files, program modules and other data using a modulated data signal, such as a carrier wave or other transport mechanism. The term “modulated data signal” typically means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communications media may include wired media, such as a wired network or direct-wired connection or the like, and wireless media, such as acoustic, radio frequency, infrared, or other wireless communications mechanisms.
Power source 1190, such as a battery or a power supply, typically provides power for portions or all of computing environment 1100. In the case of the computing environment 1100 being a mobile device or portable device or the like, power source 1190 may be a battery. Alternatively, in the case computing environment 1100 is a desktop computer or server or the like, power source 1190 may be a power supply designed to connect to an alternating current (“AC”) source, such as via a wall outlet.
Some mobile devices may not include many of the components described in connection with FIG. 11. For example, an electronic badge may be comprised of a coil of wire along with a simple processing unit 1107 or the like, the coil configured to act as power source 1190 when in proximity to a card reader device or the like. Such a coil may also be configure to act as an antenna coupled to the processing unit 1107 or the like, the coil antenna capable of providing a form of communication between the electronic badge and the card reader device. Such communication may not involve networking, but may alternatively be general or special purpose communications via telemetry, point-to-point, RF, IR, audio, or other means. An electronic card may not include display 1102, I/O device 1103, or many of the other components described in connection with FIG. 11. Other mobile devices that may not include many of the components described in connection with FIG. 11, by way of example and not limitation, include electronic bracelets, electronic tags, implantable devices, and the like.
Those skilled in the art will realize that storage devices utilized to provide computer-readable and computer-executable instructions and data can be distributed over a network. For example, a remote computer or storage device may store computer-readable and computer-executable instructions in the form of software applications and data. A local computer may access the remote computer or storage device via the network and download part or all of a software application or data and may execute any computer-executable instructions. Alternatively, the local computer may download pieces of the software or data as needed, or distributively process the software by executing some of the instructions at the local computer and some at remote computers and/or devices.
Those skilled in the art will also realize that, by utilizing conventional techniques, all or portions of the software's computer-executable instructions may be carried out by a dedicated electronic circuit such as a digital signal processor (“DSP”), programmable logic array (“PLA”), discrete circuits, and the like. The term “electronic apparatus” may include computing devices or consumer electronic devices comprising any software, firmware or the like, or electronic devices or circuits comprising no software, firmware or the like.
The term “firmware” typically refers to executable instructions, code, data, applications, programs, or the like maintained in an electronic device such as a ROM. The term “software” generally refers to executable instructions, code, data, applications, programs, or the like maintained in or on any form of computer-readable media. The term “computer-readable media” typically refers to system memory, storage devices and their associated media, and the like.
In view of the many possible embodiments to which the principles of the present invention and the forgoing examples may be applied, it should be recognized that the examples described herein are meant to be illustrative only and should not be taken as limiting the scope of the present invention. Therefore, the invention as described herein contemplates all such embodiments as may come within the scope of the following claims and any equivalents thereto.
It is understood that aspects of the present invention can take many forms and embodiments. The embodiments shown herein are intended to illustrate rather than to limit the invention, it being appreciated that variations may be made. Although illustrative embodiments have been shown and described, a wide range of modification, change and substitution is intended in the foregoing disclosure and in some instances some features may be employed without a corresponding use of the other features. Accordingly, it is appropriate that the appended embodiments be construed broadly and in a manner consistent with the scope of the description.

## Claims

1. A method of processing an image including an artifact, the method comprising:
partitioning an image into a plurality of overlapping regions;
fitting a Gaussian function to each of the plurality of overlapping regions;
optimizing an energy function for each of the plurality of overlapping regions, the energy function based at least in part on an estimated projection geometry factor;
selecting a candidate region based at least in part on the corresponding optimized energy function and the corresponding fitting of the Gaussian function; and
processing, by a computing device, the image based at least in part on an artifact formation model wherein processing results in the artifact being removed from the image.

2. The method of claim 1 wherein the artifact formation model is defined by




  
    
      E
      1
    
    ⁡
    
      (
      
        
          
            I
            D
          
          ❘
          
            U
            D
          
        
        ,
        α
      
      )
    
  
  =
  
    
      1
      2
    
    ⁢
    
      
        
        
          
            I
            D
          
          -
          
            
              U
              D
            
            ·
            α
          
        
        
      
      2
    
  




wherein ID represents a region of the image including the artifact and wherein UD represents the region of the image without the artifact and wherein a represents light attenuation caused by dust responsible for the artifact.

3. The method of claim 2 wherein the fitting of a Gaussian function to each of the plurality of overlapping regions includes evaluating the concavity of each of the plurality of overlapping regions indicated by the Gaussian function.

4. The method of claim 2 wherein the projection geometry factor is defined by τ=d·A/f wherein d is an estimated distance between a low-pass filter and a sensor array of a camera used to create the image, and wherein A/f is equal to an F-number setting of the camera used to create the image.

5. The method of claim 2 wherein the energy function utilizes the artifact formation model, contextual constraints, and constraints from a function space.

6. The method of claim 5 wherein the contextual constraints are defined by




  
    
      E
      2
    
    ⁡
    
      (
      
        
          U
          D
        
        |
        
          I
          
            Ω
            /
            D
          
        
      
      )
    
  
  =
  
    
      ∑
      
        
          D
          i
        
        ∈
        D
      
    
    ⁢
    
      
        dist
        ⁡
        
          (
          
            
              U
              
                D
                i
              
            
            ,
            
              I
              
                Ω
                /
                D
              
            
          
          )
        
      
      2
    
  




wherein UD represents a region D of the plurality of overlapping regions of the image without the artifact and IΩ/D represents image area outside of the region D.

7. The method of claim 5 wherein the constraints from a function space are defined by




  
    
      E
      3
    
    ⁡
    
      (
      α
      )
    
  
  =
  
    
      1
      2
    
    ⁢
    
      
        
        
          α
          -
          
            
              P
              
                D
                τ
              
            
            ⁡
            
              (
              α
              )
            
          
        
        
      
      2
    
  




wherein α represents light attenuation caused by dust responsible for the artifact and wherein PD represents the projection of α onto the space Dτ and is expressed as




  
    
      P
      
        D
        τ
      
    
    ⁡
    
      (
      α
      )
    
  
  =
  
    arg
    ⁢
    
      
    
    ⁢
    
      
        min
        
          u
          ∈
          
            D
            τ
          
        
      
      ⁢
      
        
          
          
            α
            -
            u
          
          
        
        .

8. The method of claim 2 wherein the energy function is a logarithmic function defined by E(UD,α|I)=λ1E1(ID|UD,α)+λ2E2(UD|IΩ/D)+λ3E3(α) wherein the E1 term represents the artifact formation model and wherein the E2 term represents contextual constraints and wherein the term E3 represents constraints from a function space.

9. The method of claim 2 wherein the optimizing the energy function includes evaluating color consistency constraints.

10. The method of claim 1 wherein the processing comprises:
formulating an energy function for each of one or more selected regions of a plurality of overlapping regions of the image;
evaluating color consistency constraints for each of the one or more selected regions of the plurality of overlapping regions of the image; and
optimizing the energy function for each of the one or more selected regions of the plurality of overlapping regions of the image,
wherein after the processing a dust-free image is recovered from the image.

11. The method of claim 10 wherein the energy function is a logarithmic function defined by


E(UD,α|I)=λ1E1(ID|UD,α)+λ2E2(UD|IΩ/D)+λ3E3(α).

12. The method of claim 10 wherein a Gaussian function is fitted to each of the one or more selected regions including evaluating the concavity of each of the one or more selected regions indicated by the Gaussian function.

13. The method of claim 12 wherein the optimization of the energy function includes utilizing alternating minimization on E(UD,α|I) wherein a sequence of each of the one or more selected regions is iteratively computed until a value of α from one iteration to the next iteration results in a change in α that is smaller than an arbitrary small number ε.

14. The method of claim 10 wherein the evaluating color consistency constraints includes a normalized function α for each of a red, green, and blue color channel, each of the normalized functions α having a minimal Kullback-Leibler divergence to an optimized α* wherein α* represents an average attenuation of light over the red, green, and blue color channels.

15. The method of claim 10 wherein the processing includes recovering a dust-free region for each of the one or more selected regions of the plurality of overlapping regions of the image by iterating a sequence until a value of α converges.

16. A method of constructing an artifact formation model over an image region, the method comprising:
defining, by a computing device, a function space of possible dust artifacts a determined at least in part based on a projection geometry factor τ and bounds of dust transparency β, where the function space of the possible dust artifacts α is defined by Dτ={α:β*τ=α, 0≦β≦1} where τrepresents a rectangular function solved for each pixel of the image region; and
decreasing effects of the possible dust artifacts on the image region based on the defined function space.

17. The method of claim 16 wherein the bounds of dust transparency β is defined as β: L2→[0,1] where L2 represents a set of pixels of the image region.

18. At least one storage device having computer-executable instructions stored thereon, the computer-executable instructions embodying a method of recovering a dust-free image from an image, the method comprising:
partitioning the image into a plurality of overlapping regions;
fitting of a Gaussian function to each of the plurality of overlapping regions;
evaluating the concavity of each of the fitted Gaussian functions wherein one or more of the overlapping regions become candidate regions based on the corresponding concavity;
estimating a projection geometry factor;
optimizing an energy function for the candidate regions, the energy function based at least in part on the projection geometry factor;
selecting one or more of the candidate region based at least in part on the corresponding energy function; and
recovering a dust-free region for each of the one or more selected candidate regions according to minimized values of each of the corresponding one or more selected candidate region's energy function.