CROSS REFERENCE TO RELATED APPLICATION

[0001] This application claims the benefit of U.S. Provisional Application No. 61/721 ,617 filed on November 2, 2012, the entirety of which is incorporated by reference herein.

STATEMENT AS TO RIGHTS TO INVENTIONS MADE UNDER FEDERALLY SPONSORED RESEARCH AND DEVELOPMENT

[0002] This invention was made with government support 2 R01EY1 1747 awarded by the National Insitutes of Health. The Government has certain rights in the invention.

BACKGROUND

[0003] Photon and sensor noise limit the performance of all imaging systems. Minimizing the effects of this noise is a universal and fundamental image processing task. Here, inter alia, this addresses the problem of denoising in still digital camera images, using a new approach that combines measurements of natural image statistics with measurements of the noise

characteristics of digital cameras.

[0004] In general, a noisy image can be represented as an unknown "true" image that has been corrupted by noise. Let z(x) represent the value of a pixel at location x = (x,y) in the true image. Without loss of generality, the observed value is given by z ₀ (x) = z(x) + n(x, z), wherein n(x, z) is the noise, which may be spatially correlated and/or dependent on the true image values z.

[0005] The goal of denoising is to estimate z(x) given the observed context of pixel values at and around the pixel location c(x).

[0006] Conceptually, the optimal estimate is given by the standard formula from Bayesian statistical decision theory: where γ[ζ(χ), z(x)] is the cost function, and /?[z(x)|c(x)]is the posterior probability of the true value given the observed context. [0007] A vast number of different denoising methods have been proposed over the past several decades (for recent summaries see, for example, Buades A., Coll B. & Morel J.M. (2010) Image Denoising Methods: A new non-local method, SIAM Review. 52, 113-147; P. Chatterjee & P. Milanfar (2010) Is Denoising Dead?, IEEE Trans, on Image Processing. 19, 895-911). They can all be viewed as providing some form of sub-optimal approximation to the Bayes optimal estimate given by equation (1).

[0008] Most often, the explicit (or implicit) cost function is the squared error between the estimated and true pixel values γ[ζ(χ), z(x)] = [z(x) — z(x)] ² . This cost function finds the estimate with the minimum mean squared error (MMSE) or equivalently the estimate with the maximum peak signal-to-noise ratio (PSNR). Other cost functions, such as those that are based on perceptual properties of the human visual system (see, e.g., Wang Z., Bovik A.C., Sheikh H.R., & Simoncelli E.P. (2004), Image quality assessment: From error visibility to structural similarity, IEEE Trans, on Image Processing), are worthy of consideration; however, as is common in the denoising literature, the present focuses on the squared-error cost function. For this cost function, equation (1) becomes:

[0009] In other words, the Bayes optimal estimate is simply the expected value of the true pixel value given the observed context (see, e.g., Bishop, C. M. (2006), Pattern recognition and machine learning; New York: Springer).

[0010] In order to develop an optimal denoising method for a specific application, one can characterize both the signal (the statistical structure of true images) and the noise (the statistical structure of the noise). The various denoising methods can be distinguished based on

assumptions they make about the structure of the signal and noise. Also important is the computational efficiency (speed and complexity). For a given application, the best method will be the one that jointly maximizes the approximation to equation (2) and the computational efficiency.

[0011] The earliest principled denoising method is known as the Wiener filter (Wiener, N. (1949). Extrapolation, Interpolation, and Smoothing of Stationary Time Series. New York:

Wiley), which is an exact implementation of equation (2), under the assumption that both the signal and the noise are described by stationary (not necessarily white) Gaussian processes. However, images are generally non-stationary and hence this method does not produce good results for most images (it blurs edges and texture). Subsequently, there have been many attempts to weaken the assumption of global stationarity. Adaptive Wiener filtering methods assume Gaussian noise and signal that is locally stationary; the methods estimate the Gaussian parameters at each pixel location and then apply the Wiener filter with those parameters (e.g., D. T. Kuan, A. A. Sawchuk, T. C. Strand, and P. Chavel (1985) Adaptive noise smoothing filter for images with signal dependent noise, IEEE Trans. PAMI, vol. 7, pp. 165-177). A closely related approach combines image segmentation and Bayesian MAP estimation (Liu C, Szeliski R., Kang, S.B., Zitnick C.L. & Freeman W.T. (2008) Automatic estimation and removal of noise from a single image. IEEE Trans. Pattern Anal. & Mach. Intell. 30, 299-314). The critical component of these methods is estimating the local Gaussian parameters; the less noisy the estimated parameters the more accurate the denoising. Simple non-iterative methods for estimating the parameters that use only pixels in the immediate neighborhood of the pixel being denoised can be computationally efficient.

[0012] Other recent methods do not make explicit formal assumptions about the structure of the noise or signal, but instead exploit heuristic intuitions to average out the noise and leave the signal. One simple and effective method of this type is bilateral filtering (Tomasi C. & Manduchi R. (1998) Bilateral filtering for gray and color images. Proceedings IEEE Conference in

Computer Vision, Bombay, India), which takes the weighted average of pixels in the local neighborhood, where the weights depend jointly on the spatial and gray-level (color) distance of the neighboring pixel from the pixel being denoised. The intuition is that spatially nearby pixels are positively correlated in gray level and can be averaged, but spatially nearby pixels that differ substantially in gray level usually contain strong signals (true image features) and should not be averaged. This method can be computationally efficient.

[0013] Related methods are those based on non-local averaging (A. Efros and T. Leung (1999) Texture synthesis by non-parametric sampling, Proceedings of the IEEE International

Conference on Computer Vision, 2, Corfu, Greece, 1033-1038). For example, the NL-Means algorithm (Buades A., Coll B. & Morel J.M. (2010) Image denoising methods: A new non-local method. SIAM Review. 52, 113-147) searches for pixels whose local neighborhood in the image is similar to the neighborhood of the pixel being denoised. It then averages all these pixels to obtain the estimate. The more similar is the local neighborhood the greater is the weight given to the pixel when computing the average. The intuition is that natural images are statistically regular and hence if two image patches are similar in structure it is likely that the center pixels are similar and hence can be averaged to estimate the true image value. To the extent that this assumption is valid for the kind of noise in an imaging system and for the kinds of images being captured, such averaging could provide a good approximation to the right side of equation (2).

Indeed, methods based on non-local averaging provide good results and are currently popular. However, these methods are less computationally efficient because of the need to make the neighborhood similarity measurements.

[0014] Another class of methods involves hard or soft thresholding following a linear transform, such as a wavelet or discrete cosine transform (R. R. Coifman and D. Donoho (1995) Translation-invariant de-noising, in Wavelets and Statistics, Lecture Notes in Statist., Springer- Verlag, New York, pp. 125-150; J. Portilla, V. Strela, M.J. Wainwright, and E.P. Simoncelli (2003) Image Denoising Using Scale Mixtures of Gaussians in the Wavelet Domain, IEEE Trans. Image Processing, 12, pp. 1338-1351). The intuition is that for appropriately chosen kernel shapes, the regular structure of natural images results in a very sparse representation (a few large kernel coefficients, with most near zero), whereas the much more random structure of noise results in a less sparse representation (many coefficients with modest values). Thus, thresholding out the smaller coefficients selectively removes the noise. These methods can be computationally efficient, but can be prone to producing ringing artifacts.

[0015] Currently denoising methods include hybrid methods (K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian (2007). Image denoising by sparse 3D transform-domain collaborative filtering. IEEE Trans. Image Process., 16, pp. 2080-2095; L. Zhang, W. Dong, D. Zhang & G. Shi (2010); Two-stage denoising by principle components analysis with pixel grouping, Pattern Recognition, 43, 1531-1549). For example the BM3D method combines non-local averaging, cooperative linear transform thresholding, and Wiener filtering (K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian (2007); Image denoising by sparse 3D transform-domain collaborative filtering; IEEE Trans. Image Process., 16, pp. 2080-2095).

[0016] In summary, most of the existing methods either assume Gaussian image and noise models, or principled heuristics based on qualitative properties of natural images. Further, the parameters of most denoising methods are estimated from the image being denoised. Thus, there is a need in the art for improved denoising methods.

SUMMARY

[0017] Provided herein, inter alia, are Recursive Conditional Means (RCM) denoising methods, that makes almost no assumptions about the underlying probability distributions, and that learn their estimates from the statistics of a large database of natural images. The

fundamental idea is to directly measure the conditional means on the right side of equation (2) recursively for a number of different small neighborhoods (context regions). During denoising, each of these different neighborhoods provides an improved estimate of the denoised image pixel. Previous work has indicated that for the task of upsampling (super resolution), this approach is every effective and computationally efficient (Geisler, W. S., & Perry, J. S. (2011). Statistics for optimal point prediction in natural images. Journal of Vision, 11(12): 14, 1-17, doi: 10.1167/11.12.14).

[0018] Conceptually, this approach is similar to non-local methods in that an estimate is based on the average across a large number of similar neighborhoods. The difference is that RCM neighborhoods are small enough that similar neighborhoods are identical, and hence there is no need for an arbitrary definition of similarity. Also, the neighborhoods are small enough that the conditional means can be learned precisely from a large set of natural images and then stored in tables. RCM denoising is extremely fast computationally because all the relevant statistics may be stored in fixed tables that can then be applied to any image.

BRIEF DESCRIPTION OF THE DRAWINGS

[0019] Fig. 1 shows a noise model fit for 14-bit flat-field red pixel image with mean value of 89.5.

[0020] Fig. 2 shows measured variances of Gaussian and Laplace distributions from flat field images.

[0021] Fig. 3 shows embodiments of synthesized noise.

[0022] Fig. 4 shows a comparison of ISO noise with traditional AWGN (additive white Gaussian noise).

[0023] Fig. 5 shows the noising contexts used in connection with a denoising algorithm.

[0024] Fig. 6 shows one embodiment of estimation tables for use with a denoising algorithm.

[0025] Fig. 7 illustrates the quantitative performance of denoising algorithms on 401 RGB test images.

[0026] Fig. 8 illustrates the computational time of different invoicing algorithms.

[0027] Fig. 9 shows one embodiment of a cropped region of the original standard peppers image together with result of AWF, C-BM3D, and RCM algorithms.

[0028] Fig. 10 depicts results of different algorithms from images containing additional multiplicative correlated Gaussian noise. [0029] Fig. 11 illustrates the results of the RCM algorithm.

[0030] Fig. 12 depicts the results of different algorithms from images containing multiplicative white Gaussian noise.

[0031] Fig. 13 is a block diagram showing details of a computer system configured in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION

[0032] Natural Image Point Prediction is used to estimate pixel values in digital images. It does this by finding the most likely estimate of the true or actual value of a pixel given its neighboring pixels.

[0033] Natural Image Point Prediction may be used whenever point prediction is desired in digital image processing. For example, point prediction is desired for image enlargement during the processes of interpolation and upsampling, which converts a digitized image to a higher sampling rate. Point prediction is used when an image is deblurred. In this case, existing pixels within an image are restored to near their true values: that is, their values before being blurred and/or downsampled. Point prediction is used to remove noise and artifacts from digital images. This image processing task is the emphasis of this disclosure. Point prediction is used to estimate pixel values in order to efficiently encode them during image compression.

[0034] Natural Image Point Prediction uses high order statistics to estimate pixel values, and it directly measures these statistics from natural images with no restrictive assumptions about underlying structure of images. Other methods either restrict their measurements to first and second order statistics, or they use models that make overly restrictive assumptions about the underlying structure of images. Provided herein are solutions to the problem of estimating original image pixel values given a digitized array of image pixel values.

[0035] Because natural image point prediction does not make the same assumptions as existing upsampling, interpolation and denoising methods, it is able to gain more insight into the structure of natural images and be more accurate, simpler and more direct than existing methods and therefore computationally more efficient than existing methods.

[0036] This invention may be used in conjunction with existing methods. For example, it can be used in conjunction with JPEG encoding for better JPEG encoding, it can be used in conjunction with almost any other interpolation method. Many digital image processing methods cannot be fruitfully combined with other methods. [0037] In some embodiments, the lookup tables used in the methods provide here are replaced with smooth functions fitted to the tables, resulting in substantially lower memory requirements.

[0038] In some embodiments, the methods herein provide an improved solution to the problem of estimating original image pixel values given a digitized array of image pixel values. This may be accomplished by first measuring, with a novel direct technique, the average local statistics in space and/or time of natural images captured with an arbitrary image-capture device of interest, such as a digital camera. These statistics are used to create look-up tables that provide optimal Bayesian estimates of point (pixel) values.

[0039] The method may be tailored to specific classes of image- capture device and image processing tasks, for improved performance. The method provides statistically optimal estimates given the local image properties considered, which guarantees better accuracy than all other methods that use those properties. The implementation only involves look up tables which allows good real time performance. The tables can be approximated with smooth functions to reduce storage.

[0040] In some embodiments, the methods provided herein are substantially faster and more accurate than standard methods.

[0041] An important general consideration is that denoising methods are almost always tested by adding constant- variance white Gaussian noise (AWGN) to gamma-compressed ground truth images. However, the noise in most digital cameras is more complex. The noise in the raw image from a CCD or CMOS sensor array is generally statistically independent and

multiplicative: the variance of the noise is proportional to the mean intensity falling on the pixel. This noise occurs prior to gamma compression, and thus differs from additive noise following gamma compression. Note, however, that additive noise following gamma compression is similar to multiplicative noise prior to gamma compression, explaining in part the popularity of AWGN. Further, the digital camera noise becomes spatially correlated after the standard image processing in the camera's hardware or firmware, which typically involves color interpolation (demosaicing) and conversion to a standard display format such as sRGB. Thus, even a

"lossless" tiff or png camera image contains spatially correlated noise. It is quite possible that methods that work well for AWGN will perform more poorly on noisy digital camera images. Therefore, both for training and testing denoising methods it is critical to consider the actual noise in digital cameras (Liu C, Szeliski R., Kang, S.B., Zitnick C.L. & Freeman W.T. (2008), Automatic estimation and removal of noise from a single image; IEEE Trans. Pattern Anal. & Mach. Intell. 30, 299-314; Danielyan A., Vehvilanien M., Foi A., Katkovnik V. & Egiazarian K.

(2009) Proc. Local and Non-Local Approx. in Image Process. 125-129.).

[0042] In what follows the noise in a high quality digital camera is first measured and characterized. This camera noise model is then used to simulate the effects of the camera's noise by adding model noise to a large set of ground-truth images to obtain training and test images. Next, details of RCM denoising are described. Finally, RCM denoising with other methods are compared, both in terms of mean squared error (MSE/PSNR) and subjective appearance.

Noise measurements

[0043] Noise was measured in a Nikon D700 camera. Images were captured of a fixed uniform light field created from a tungsten light source. The shutter speed was set at 1/60 sec. The camera's aperture was adjusted in small increments so that images varied from completely black fields to maximally white fields. Measurements were repeated for a range of ISO settings: 200, 400, 640, 800, 1000, and 3200. Note that ISO represents the gain applied to CCD/CMOS elements, and thus the greater the ISO, the noisier the images. Higher ISO values are typically needed for low light levels or for stop-action (fast shutter speeds).

[0044] With reference now to Fig. 1, a noise model fit for 14-bit flat-field red pixel image with mean value of 89.5 is shown. A Gaussian noise model does not fit well when the image pixel values are low because of the higher kurtosis of the image's noise distribution. A mixture of a Gaussian and Laplace distribution provides a better fit.

[0045] Statistical analysis was carried out separately for the R, G, and B pixel locations in the 14-bit raw images. In order to control for the effect of vignetting, only the center 128 x 128 patch of pixels from each image was analyzed. Fig 1 shows the distribution of R pixel values for one ISO and aperture setting. The distributions often differ slightly from Gaussian and are better described by a mixture of a Gaussian (normal) and a Laplace distribution (black curve in Fig 1):

[0046] Each measured distribution was fitted with this mixture function. Fig 2 plots the fitted variance parameters as a function of the mean pixel value, for R, G and B pixels, at ZS(¾oo. As can be seen, the variances increase approximately linearly. We used the best fitting linear functions to summarize the camera noise for each ISO setting. The camera noise increases with the ISO setting, and thus the plots in Fig 2 show the highest measured noise levels. [0047] As a check, the measurements were repeated with a shutter speed of 1/250 s (and larger aperture). As expected, the noise parameters were independent of the shutter speed.

[0048] With reference now to Fig. 2. measured variances of Gaussian and Laplace

distributions from flat field images are shown. The measurements were summarized with linear equations.

Noise simulation

[0049] ISO ₂ 00 is the lowest standard ISO setting (low noise) available in the D700 camera; thus, natural images captured with this ISO were taken to be ground truth images. Training and test images for higher ISO settings were then created by adding simulated camera noise. In particular, for any value z in the ground truth image a random value ΔΖ given by

(Aa i/. N. if U < &

ΔΖ : " _[ ^' , (4)

\ Δ σ\ ( z } I,. otherwise was added, where U is a random sample from a uniform distribution, N is a random sample from a standard normal distribution, L is a random sample from a standard Laplace distribution, and

(5)

[0050] The value of a was determined by averaging the value of a for all fits across all channels. The average value of a was 0.975, and the standard deviation of a was 0.027.

[0051] The variance of the simulated noise increases in proportion to the mean value and hence is "multiplicative" noise. Further, the simulated noise is generated independently for each pixel location. Because the noise is approximately Gaussian, the simulated noise in raw images is referred to as multiplicative white Gaussian noise (MWGN).

[0052] The above steps simulate the noise in raw images, but most applications involve denoising images that have been interpolated (demosaiced), converted to a standard color format (usually linear sRGB), gamma compressed, and finally quantized to 8-bits per color channel (24- bit sRGB). These cases can be simulated simply by processing the raw ground truth and the simulated raw test/training images through the standard processing steps (Liu C, Szeliski R., Kang, S.B., Zitnick C.L. & Freeman W.T. (2008) Automatic estimation and removal of noise from a single image. IEEE Trans. Pattern Anal. & Mach. Intell. 30, 299-314). For example, Fig 3 a shows a cropped region from an ISO 200 raw image, after conversion to standard 24-bit sRGB. Fig 3b shows a cropped image of the same scene taken at ISO ₃₂₀₀ - Fig 3c shows the result of adding simulated noise to the ISO 200 raw image.

[0053] With reference now to Fig. 3, different noise levels are shown in three images of the same object. The different noise levels shown in the images in Fig. 3, are either created by different camera ISO settings, or to simulate different camera ISO settings. Specifically, Fig. 3(a), shows a cropped region of an image taken with camera ISO200, Fig. 3(b), shows the cropped region of the image taken with camera ISO3200, and Fig. 3(c) shows the cropped region of the image with noise added to create a synthesized ISO3200 image.

[0054] The noise in the real and simulated sRGB images is clearly spatially correlated. We will call this multiplicative correlated Gaussian noise (MCGN). Fig 4 compares the synthesized noise in a sRGB camera image with that of standard additive white Gaussian noise (AWGN) of similar noise power. Note that the white noise was (as is standard) added after gamma compression. The RCM method of denoising can be applied to any kind of noise. The emphasis here is on denoising sRGB images (MCGN), but the present also considers multiplicative and additive white Gaussian noise (MWGN and AWGN).

RCM DENOISING

Recursive conditional means and variances

[0055] As mentioned earlier, the key concept of RCM denoising is to measure conditional means for different local contexts. As referred to herein, a conditional mean refers to a single conditional average and conditional means refers to a plurality of conditional averages. The conditional mean for each context provides the Bayes optimal (MMSE) estimate given that context. The number of variables constituting each local context is chosen to be small so that the conditional means can be measured accurately from training images without making assumptions about the underlying probability distributions. By measuring and applying the conditional means recursively the effective size of the context is expanded.

[0056] With reference now to Fig. 4, synthesized ISO noise versus traditional AWGN

(additive white Gaussian noise) is shown in three images of the same object. Fig. 4(a) shows the original image of the object, Fig. 4 (b) shows the same image with synthesized AWGN, MSE across entire image=55.8, and Fig. 4(c) shows the same image with synthesized MCGN

(ISO3200), MSE across entire image=56.3. [0057] To be more precise, let z ₀ (x) represent the input image, let c _; _ _/ (x) be the context vector used to obtain the 1 ^th recursively estimated image ¾(x), and let z(x) represent the ground truth image. Thus, the Bayes optimal estimate of z(x) on iteration i is given by

where the context vector on iteration i is obtained from image z;_i(x). The number of iterations n is set based on when the estimation accuracy reaches asymptote.

[0058] For symmetry, images can also be estimated with all the context vectors rotated by 90 deg. This slows the computation speed, but does not result in estimating additional tables. This second set of estimated images can be written as z {% ) =\ E \ z ( x i| c ^~ : _; (x) (J)

[0059] The last estimated images, z _n (x) and z _n ^l (x), can be combined using their reliabilities:

i ϊ z..., fsHr. (s)r„ fx - ru

z„| x | = -— ^{' "} ,. i b )

{ } ÷ ^' ( x }— r a ^■ = ETZ { X ) j . r„ f l = 1/ Far ∑{ x) ( x) ,

[0060] where . _ . ^J - ^{' !' L} and i i x ) = V Far\ r{ Hc ^" , { x L and r = VVar\∑i x)

Note that if the reliabilities of the two estimates are approximately equal and are much larger than r, then equation (8) reduces to the simple average:

. z, ( xj ÷ ^ )

½^ = W

Derivation of Rule Used for Combining Multiple Estimates of the True Pixel Value

[0061] As discussed above, in some embodiments, multiple estimates of the true pixel value can be combined into this last. Derivation of the rule used for combining multiple estimates of the true pixel value z into a single estimate is shown here. This rule is optimal given certain assumptions, and is closely related to standard rules for cue combination (Oruc, I., Maloney, L. T., & Landy, M. S. (2003), Weighted linear cue combination with possibly correlated error, Vision Research, 43, 2451-2468). Let c . ..,c _n represent n sets of known pixel values (sources of information) that are to be used in estimating a single unknown pixel value z. Using Bayes' rule, the posterior probability of z given the known pixel values can be written as:

[0062] The first assumption is that given the true value of z, Cj is independent of c ₃ for all i and j (i.e., the sources of information are statistically independent). In this case, this results in

[0063] Applying Bayes' rule or, p r e,

= i . A3

where

[0064] The second assumption is that the prior and posterior probability distributions Gaussian. In this case, this results in

(A4)

es i V -0.5 i - ii ) ^" r where w, and p _t are the conditional mean and reliability of posterior probability distribution of z given c„ and u and r are the mean and reliability of the prior probability distribution of z. (Note that reliability is the inverse of the variance.) Rearranging, gives

[0065] Consider the term inside the exponential. Because this term is quadratic in z it follows that ...,c„) is Gaussian. Expanding, collecting terms, and completing the square, shows that/?(z|c/, ...,c _n ) is the form:

=

where K is the constant that makes the right side of the equation a probability distribution.

[0066] The minimum mean squared error (MSSE) estimate is the expected value of the posterior probability distribution, and the maximum a posteriori (MAP) estimate is the mode of the posterior probability distribution. It follows from eq. (A5) that the MMSE and MAP estimates are the same and are given by

[0067] Finally, note that the entropy of p(z\ci) can be less than or equal to the entropy of p(z). Thus, r < , and hence the denominator is always positive. [0068] In using eq. (A6), u=z (the sample mean of the prior probability distribution of z), r=l/a ² (one over the sample variance of the prior probability distribution of z), = z (the sample mean of the posterior probability distribution of z given c _; ), and (one over the sample variance of the posterior probability distribution of z given ci). Eq. (A6) may not be valid if the two strong assumptions above do not hold, and thus should be regarded as an

approximation.

Application of Rule Used for Combining Multiple Estimates of the True Pixel Value

[0069] As it turned out, for the context vectors used here, the reliabilities are approximately equal and much larger than r; thus, all the results reported here are for equation (9).

[0070] To apply this estimation method, one can specify the conditional means, and if it is necessary to combine estimates with equation (8) rather than equation (9), then one can also specify the conditional variances. The approach taken here is to directly measure the conditional means and variances from a large set of training images. Let {z(x, 1), ... , z(x, k)} be a set of k ground truth images indexed by j, and let {z ₀ (x, 1), ... , z ₀ (x, k)} be the corresponding training images. The sample conditional mean for a specific context vector Ci_i is given by

where Ω^ _Μ ) is the set of locations in the training images with context c _i , and N(Ci_i) is the total number of locations in the set. Similarly, the sample variance (if needed) is given by

The values of and ν, [ο _Μ ] can be stored as tables (as done here), or potentially summarized with descriptive functions. If the set of training images is sufficiently large, then E[z(x)|c _; -_

(x)]-≤mi[c _; _ (x)] and Var[z(x)|c _; _ (x)] -≤Vi[c _; _ _/ (x)). In practice, it is generally found that the tables are the same for the rotated context vectors, and hence E[z(x)|c _; _ _/ (x)]-≤mi[c _; _ _/ (x)] and

Ground truth, training and test images [0071] The ground truth, training, and test images were obtained from a database of 1204 high resolution (4284 x 2844) 14-bit raw images captured with a calibrated Nikon D700 digital camera, at its lowest standard ISO setting (IS0 ₂ oo)- Care was taken to minimize clipping. From the 1204 images, 803 were randomly selected to be training images, and the remaining 401 were used as test images. The 803 training images provided approximately 10 ¹⁰ samples for learning each table of conditional means.

[0072] We considered three kinds of training and test images. For the first kind (MCGN), the following sequence of steps were performed: (1) addition of simulated camera noise (ISO3200) to ground truth raw images, (2) AHD interpolation (demosaicing), (3) conversion to linear sRGB, (4) gamma compression, (5) quantization to 24-bit (8 bits per channel) sRGB. For the second kind (MWGN) the steps were: (1) AHD interpolation, (2) conversion to linear sRGB, (3) addition of MWGN, (4) gamma compression, (5) quantization to 24-bit sRGB. For the third kind (AWGN) the steps were: (1) AHD interpolation, (2) conversion to linear sRGB, (3) gamma compression, (4) quantization to 24-bit sRGB, (5) addition of AWGN. The average noise power (mean squared error from the ground truth images) for the second and third kinds of images was set to match that of the first kind.

[0073] For more details about the natural images see, e.g., Geisler, W. S., & Perry, J. S.

(2011), Statistics for optimal point prediction in natural images, Journal of Vision, 11(12): 14, 1-

17, doi: 10.1167/11.12.14, where all the ground truth images are available.

Context vectors

[0074] Once the ground truth and training images have been specified, the only remaining steps are to specify the context vectors and measure the tables. In RCM denoising, all context vectors consist of three 8-bit variables.

[0075] For gray scale images there are five context vectors:

I _¾ {.x - 1 y K ¾ x. y ) _* z _% { x + L y )

C _j i X Ϊ ∑ ₂ ( x - 1. _: v I . z, { x, ) , ¾ i x ÷ L }

ζ,. { ₅ · - 1),ζ, s:. y),z _¾ f x. y ÷ l) \

z ₄ (x ,£? ₄ ( ), < , ( x ) I [0076] The first four contexts consist of the pixel location being estimated and two immediately neighboring pixel locations. The contexts alternate between the horizontal and vertical directions. As a result of applying tables for these contexts recursively, there are effectively 9 pixels in z ₀ (x) (the 3x3 neighborhood) that contribute to each estimated pixel in z ₂ (x), and 25 pixels (the 5x5 neighborhood) contributing to each estimated pixel in z ₄ (x) (see Fig. 5). Tables for these first four context vectors can be applied very efficiently— they are effectively 1x3 contexts that can be applied successively to the image, in place, with minimal buffering.

[0077] The final context vector consists of the pixel location being estimated, the average a ₄ (x) of the values in the surrounding 9x9 neighborhood of pixel locations (80 locations), and the standard deviation σ ₄ (χ) of the surrounding 80 pixel values from the regression plane. The rationale for this last context vector is that if the ground truth image is locally planar at some location, then the MMSE estimate is the average of the values in the neighborhood. The standard deviation from the regression plane measures how close the neighborhood is to being planar, allowing the table to know when to put the most weight on the local average.

Formulas Used for Planar Regression

[0078] The formulas used for planar regression are provided here. The equation of a plane is f(x,y) = Ax+By+C. Consider a square block of pixels of odd dimension n, where the center pixel is taken to be the origin. The least squares estimates of the parameters of the plane are

[0079] Where,

[0080] The standard deviation from the best fitting plane is given by

Denoising Contexts

[0081] With reference now to Fig. 5, one embodiment of denoising contexts are shown. The input image is z ₀ , and the recursively estimated images are z _\ to z ₅ . (a)-(d) The black pixels show the explicit context vector used from that image to obtain the next image. The grading pixels show the additional pixels effectively contributing to the estimate, (e) The context for estimating z ₅ consists of the center (black) pixel, the average of the surrounding (Ray) pixels, <¾, and the standard deviation of those pixels from the regression plane, σ ₄ .

[0082] For color images, the algorithm first converts the images from RGB to a perceptual color space (e.g., Rec 709 YCbCr, or a simple opponent color space (see, e.g., K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian (2007), Image denoising by sparse 3D transform-domain collaborative filtering, IEEE Trans. Image Process., 16, pp. 2080-2095), applies the tables, and then converts back to RGB. Converting to a perceptual color space significantly reduces visible color artifacts in the denoised images. Perceptual color spaces represent each pixel with a luminance value (e.g., Y) and two color-opponent values (e.g., Cb, Cr). Using the same context vectors described above, one set of tables for the luminance values is learned and another set for the color-opponent values is learned (the same tables are used for both color-opponent values). For the color-opponent channels, the fifth context vector uses an 11x11 neighborhood rather than 9x9. For color images, the algorithm also uses a final context vector consisting of the estimated RGB values in z ₅ (x):

RESULTS

Estimation tables

[0083] RCM denoising uses local contexts having only three elements. This makes it possible to visualize the statistical rules implicit in the MMSE estimates. For example, Fig. 6a-c shows the optimal estimates for context c ₀ (see Fig. 5a). In each plot, the horizontal and vertical axes give the values of the two context pixels surrounding the center context pixel (the location being denoised). The color scale gives the MMSE estimate of the gray level of the center pixel (i.e., the directly measured conditional mean). The upper plot is for when the value of the center context pixel is 64, the middle plot when the value is 128, and the bottom plot when the value is 192. In general, the MMSE estimates are smooth but non-trivial functions of the context vector. When the surrounding context pixels are nearly equal (i.e., near the main diagonal) and are lower in value than the center context pixel, then the estimate is strongly reduced. Similarly when the surrounding context pixels are nearly equal and greater than the center context pixel, then the estimate is strongly increased. On the other hand, when the two surrounding pixels differ there is greatly likelihood of structure in the ground truth image and hence more weight is put on the center context pixel. The tables for contexts Ci to c ₃ are qualitatively similar to that for c ₀ , but differ in detail.

[0084] With reference now to Fig. 6, estimation tables for RCM denoising are shown.

Horizontal and vertical axes give the two context variables that are not the center context pixel. The color axis gives the MMSE estimate, (a-c) Tables for context Co when the center context pixel z ₀ (x,y) has a value of (a) 64, (b) 128, and (c) 192. (d-f) Tables for context c ₄ when center context pixel z ₄ (x,y) has a value of (d) 64, (e) 128, and (f) 192.

[0085] Fig. 6d-f shows the optimal estimates for context c ₄ (see Fig. 5e). In each plot, the vertical axis gives the average gray level of the context pixels surrounding the center pixel (the pixel location being estimated), and the horizontal axis gives the standard deviation of the context pixel values from the regression plane. Again, the upper, middle, and lower plots are for when the value of center context pixel is 64, 128, and 192, respectively. When the standard deviation is low, the region is closer to planar and more weight is put on the average (the estimates change more as the average changes; note the bigger changes in color), whereas when the standard deviation is high the region is less planar and more weight is put on the center context pixel (the estimated value from the previous contexts).

Quantitative performance

[0086] To assess the performance of RCM denoising, it was compared with two standard algorithms, adaptive Wiener filtering (AWF; using the MATLAB® R2102a wiener! function) and ImageMagick® adaptive blur (IMAB; www.imagemagick.org, version 6.7), and with a state- of-the-art algorithm (C-BM3D (see, e.g., K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian (2007), Image denoising by sparse 3D transform-domain collaborative filtering, IEEE Trans. Image Process., 16, pp. 2080-2095)). Three different kinds of noise were tested: multiplicative correlated Gaussian noise (MCGN; i.e., realistic camera-image noise), multiplicative white Gaussian noise (MWGN; i.e., realistic raw-camera-image noise), and additive white Gaussian noise (AWGN). The MGCN corresponded to the noise in a Nikon D700 camera at ISO3200 (see Figs. 2 and 3). The MWGN and AWGN were set to have the same average noise power as the camera-image noise (MCGN). This noise level corresponded to σ = 13.21 for AWGN. This was the value of the noise parameter given to the three comparison algorithms.

[0087] Performance was compared on the 401 test RGB images and on several standard RGB images in the image processing literature. The black circles in Fig. 7 show the average MSE for the 401 test images after each step of RCM denoising. Recall that the result of applying the table for each context is a partially denoised image (indicated on the horizontal axis). The horizontal lines show the average MSE of the comparison algorithms. Also shown in the Fig is the average PSNR of the final estimates.

[0088] With reference now to Fig. 7, the quantitative performance of denoising algorithms on 401 RGB test images is shown. The vertical axis gives the average MSE of the denoised image. The horizontal axis indicates the successively denoised images produced by the proposed RCM algorithm. The black circles show the MSE of the successively denoised images by the RCM algorithm. The colored horizontal lines show the final MSE of the comparison algorithms. Also shown are the average final values of PSNR. (a) Results for realistic camera-image noise (MCGN). (b) Results for realistic raw-camera-image noise (MWGN). (c) Results for additive white Gaussian noise (AWGN).

[0089] Fig. 7a shows the results for noise that realistically mimics the noise in camera images (MCGN). The MSE drops rapidly as the successive tables are applied, dropping down to that of the AWF and IMAB algorithms after 1 step and below that of C-BM3D after 2 steps. Fig. 7b shows the results for noise that realistically mimics the noise in raw camera images (MWGN). Again, the MSE drops rapidly as the successive tables are applied, dropping below that of AWF and IMAB after 2 steps and below that of C-BM3D after 3 steps. Finally, Fig. 7c shows the results for additive white noise (AWGN). The MSE drops below AWF and IMAB at 2 steps and approaches but does not drop below C-BM3D. Denoising is generally easier with statistically independent noise and hence the final MSE is lower for MWGN and AWGN.

[0090] The black circles in Fig. 8 show the cumulative computation time in milliseconds per megapixel, at each successive step of the RCM algorithm. The final black circle and the horizontal lines show the total computation time of the algorithms. The algorithms were run on a single 3.1GHz Intel processor. Not surprisingly, given its simplicity and its use of tables, the RCM algorithm runs very quickly. The slowest step is application of the table for context c ₄ (see Fig. 5e). The next slowest step is repeating the first four steps with the orthogonal context vectors to obtain Interestingly, this step provides symmetry (which is good to have), but has a relatively minor effect on MSE (see Fig. 7). Thus under demanding conditions it could be dropped.

[0091] With reference now to Fig. 8, the computation time of denoising algorithms is shown. As seen in Fig. 8, the RCM algorithm outperforms the denoising algorithms for iterations up to z ₅ .

Qualitative performance

[0092] Many of the standard test images in the image processing literature already contain substantial camera noise and thus one way to compare denoising algorithms is simply to denoise the original image. For example, Fig. 9 shows a cropped region of the original standard peppers image together with the results of the AWF, C-BM3D and RCM algorithms. Qualitatively the quality of C-BM3D and RCM are similar with a little less chromatic aliasing for the RCM algorithm.

[0093] With reference now to Fig. 10, details of results from various algorithms from images containing additional multiplicative correlated Gaussian noise portion. The top image is from a natural scene taken from the CPS natural image database. The bottom image is not a natural scene and is not contained in the database.

[0094] Fig. 10 shows results for synthesized camera noise (MCGN). The upper image is cropped from one of the test images in the data set. The bottom image is of a human-made object and not in the data set. The values of PSNR are for the entire image. As can be seen RCM denoising removes much more of correlated spatio-chromatic noise. In the bottom image RCM denoise softens the edges slightly. If desired this effect can be lessened by eliminating or reducing the size of the surround in the context vector c ₄ (see Fig. 5e), with a minor effect on the MSE (see Fig. 7a). For example, Fig. 11 shows the RCM estimates without context vector c ₄ .

[0095] With reference now to Fig. 11, detail of results from RCM algorithm from images containing additional multiplicative correlated Gaussian noise are shown. In these examples, the RCM algorithm was modified to exclude the 5 ^th recursive step in which the estimates for z ₅ are computed using the average and standard deviation from the regression plane.

[0096] With reference now to Fig. 12, details of results from various algorithms from images containing additional multiplicative white Gaussian noise are shown. The top image is from a natural scene taken from the CPS natural image database. The middle image is not a natural scene and is not contained in the database. The bottom image is the standard Lena image. The standard deviation of the added noise was 13.21.

[0097] Fig. 12 shows results for noise that mimics adding independent multiplicative noise prior to gamma compression (MWGN). Recall that this noise is like the noise in raw camera images and is quite similar to additive independent noise following gamma compression

(AWGN). The upper image is cropped from one of the test images in the data set. The middle image contains human made objects and is not in the data set. The bottom image is cropped from the standard Lena image. Again the PSNR values are for the whole image. In general the C-BM3D and RCM results are similar in quality. C-BM3D produces slightly smoother contours (e.g., the contour inside the window of the middle Fig), but removes some image texture (e.g., the brick structure on the left in the middle Fig).

Limitations, Extensions, and Applications

[0098] Although RCM denoising is fast and simple computationally, it does use substantial memory to store the fixed tables. The memory requirements are not significant for most personal computers, but may be an issue for image-processing hardware or firmware in devices such as digital cameras. We note, however, that each table is just a list of 8-bit numbers (unsigned bytes) and hence could be stored and retrieved like an image. Also, the tables are relatively smooth and regular (see Fig. 6), and thus it should be possible to closely approximate them in some way; e.g., fitting them with a sum of appropriate basis functions).

[0099] As an immediate practical application, RCM denoising can be used to denoise standard 24-bit sRGB images and 8 -bit gray scale images. Another obvious application would be the denoising of raw camera images. We have not yet implemented this application, but comparison of Figs. 7a and 7b suggests that the RCM denoising may be more effective if applied to the raw image, before demosaicing, which creates correlated noise (note the lower final MSE in Fig. 7b). Of course, in many practical situations the raw image is not available.

[0100] RCM denoising gets most of its power by measuring very local statistical structure. The output of the 4th recursive step, z ₄ , is quite accurate (Fig. 7), and has a support region of only 5x5 pixels (Fig. 5). Other successful denoising algorithms generally have a larger support region, and thus it is possible that some hybrid approaches could produce better performance, assuming they capture more large scale information than the simple regression-plane measure (Fig. 5e). How much better image denoising can get is a matter of some debate (P. Chatterjee & P. Milanfar (2010) Is denoising dead?, IEEE Trans, on Image Processing, 19, 895-911; Levin, A., & Nadler, B. (2011) Natural image denoising: Optimality and inherent bounds. IEEE

Conference and Pattern Recognition and Computer Vision (CVPR). 2833-2940). We note, however, that attempts to set bounds on maximum possible denoising performance have assumed AWGN.

Systems for Performing RCM

[0101] Fig 13 is a block diagram showing details of a computer system configured in accordance with an embodiment of the present invention. Fig 13 illustrates an embodiment of a hardware configuration of a computer system 1300 that is representative of a hardware environment for practicing the present invention. In Fig 13, the computer system 1300 may include a processor 1301 coupled to various other components by a system bus 1302. An operating system 1303 may run on the processor 1301 so as to provide control and coordinate the functions of the various components of Fig 13. Program instructions may be executed by the processor 1301 through the operating system 1303 to provide an application 1304 in accordance with the principles of the present invention that implements the various functions or services to be performed in accordance with the description herein. The application 1304 may include, for example, functions and operations for estimating defocus in individual natural images as discussed further below.

[0102] Referring again to Fig. 13, a read-only memory ("ROM") 1305 may be coupled to the system bus 1302 and may include a basic input/output system ("BIOS") that controls certain basic functions of the computer system 1300. A random access memory ("RAM") 1306 and a disk adapter 1307 may also be coupled to the system bus 1302. It should be noted that software components including the operating system 1303 and application 1304 may be loaded into the RAM 1306, which may be the main memory of the computer system 1300 for execution. The disk adapter 1307 may be an integrated drive electronics ("IDE") adapter or the like that communicates with a storage unit 1308, e.g., a memory unit, hard disk drive, or solid state drive. It is noted that the program for estimating defocus in individual natural images as discussed further below may reside in the disk unit 1308 or in the application 1304. Data relating to processing operations, such as look-up tables, inputs, and output values, parameters, and the like, may be stored in the memory 1305, 1306, 1308.

[0103] The computer system 1300 may further include a communications adapter 1309 coupled to the bus 1302. A communications adapter 1309 may interconnect the bus 1302 with an outside network (not shown) through a network interface, thereby allowing the computer system 1300 to communicate with other similar devices. Alternatively, the computer system 1300 may be embedded within a device such as a camera or digital microscope, each having an optical system that directs light from an object onto a sensor array such that the optical system can be adjusted to proper focus in accordance with the description herein.

[0104] Input/output (I/O) devices may also be connected to the computer system 1300 via a user interface adapter 1310 and a display adapter 1311. A keyboard 1312, mouse 1313, and a speaker 1314 may all be interconnected to the bus 1302 through the user interface adapter 1310. Data may be input to the computer system 1300 through any of these devices. A display monitor 1315 may be connected to the system bus 1302 by the display adapter 1311. In this manner, a user can provide inputs to the computer system 1300 through the keyboard 1312 or mouse 1313, and can receive output from the computer system 1300 via the display 1315 or speaker 1314.

[0105] As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a "circuit", "module", or "system". Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.

[0106] Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer-readable signal medium or a non-transitory computer-readable storage medium. A computer-readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the non-transitory computer-readable storage medium would include the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), a data storage media such as a compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer-readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. [0107] A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus or device.

[0108] Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

[0109] Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++, or the like, and conventional procedural programming languages, such as the "C" programming language or similar programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

[0110] Aspects of the present invention may be described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the present invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to product a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the function/acts specified in the flowchart and/or block diagram block or blocks. [0111] These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks.

[0112] The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the function/acts specified in the flowchart and/or block diagram block or blocks.

CONCLUSION

[0113] RCM denoising is remarkably effective given its conceptual and computational simplicity. In this approach, recursive conditional means are measured directly (by simple averaging) from a large training set of natural images, for small (3 element) context vectors. Denoising with the resulting fixed set of tables exceeds state-of-the-art algorithms in accuracy for realistic camera noise and matches them for additive white Gaussian noise. RCM denoising is much faster than state-of-the-art algorithms. This speed allows the method to be applied to very large images and, with further optimization, should allow it to be applied to video in real time.

[0114] The recursive conditional means approach has also proved to be very effective for the task of upsampling (super resolution, see, e.g., Geisler, W. S., & Perry, J. S. (2011). Statistics for optimal point prediction in natural images, Journal of Vision, 11(12): 14, 1-17,

doi: 10.1167/11.12.14), and thus it is likely to be effective for a number of other basic image processing tasks.