Method and system for robust universal denoising of noisy data sets

1. A method for denoising a noisy image z, the method comprising:

computing, by an electronic computer, a prefiltered image y from the noisy image z;

collecting, by an electronic computer, bias statistics for each prediction class in a context-by-context analysis of the prefiltered image y;

collecting, by the electronic computer, prediction-error distributions in a context-by-context analysis of the noisy image z in which prediction-errors z i −{tilde over (x)} i are used to generate prediction-error vectors e′ k that are added to prediction-error-statistics vectors e k ;

generating, by the electronic computer, normalized and smoothed prediction-error probability distributions {circumflex over (P)} E for each conditioning class;

computing, by the electronic computer, for each noisy-image pixel z i an estimated clean-image symbol x i by minimizing a computed distortion over all possible symbols a 0 -a M−1 of alphabet A and storing x i in a computer-readable memory for subsequent display and/or output to a user.

2. The method of claim 1 wherein collecting, by the electronic computer, bias statistics for each prediction class in a context-by-context analysis of the noisy image z further includes:

for each prefiltered-image pixel y i ,

determining a context S i y ;

predicting a clean-image symbol {tilde over (x)} for the prefiltered-image symbol y i embedded in the context, {tilde over (x)} i ={tilde over (x)}(S i y );

producing a differential representation S i y the context S i y by a difference operation D(S i y );

generating a canonical representation C i y from the differential representation S i y ;

determining a prediction class i y that corresponds to the canonical representation of the context C i y by applying the function to C i y , i y = (C i y ); and

using prediction class i y as an index into a table of ε and n values for each prediction class to update the table entries for prediction class i y by

ε( i y )=ε( L y )+ y i −{tilde over (x)} i

n ( i y )= n ( i y )+1; and

for each prediction class i y ,

computing a final prediction-error bias ε is computed for each prediction class i y as

ε( i y )=ε( i y )/ n ( i y ).

3. The method of claim 1 wherein collecting, by the electronic computer, prediction-error distributions in a context-by-context analysis of the noisy image z in which prediction-errors z i −{tilde over (x)} i are used to generate prediction-error vectors e′ k that are added to prediction-error-statistics vectors e k further includes:

for each prefiltered-image pixel y i ,

determining a context S i y ;

predicting a clean-image symbol x for the prefiltered-image symbol y i embedded in the context, {tilde over (x)} i ={tilde over (x)}(S i y );

producing a differential representation S i y of the context S i y by a difference operation D(S i y );

generating a canonical representation C i y from the differential representation S i y ;

determining a prediction class i y that corresponds to the canonical representation of the context C i y by applying the function to C i y , i y = (C i y );

determining a conditioning class Q i y that corresponds to the prediction class i y by applying the function Q to i y , Q i y =Q( i y );

computing a prediction-error vector e′ i for the noisy-image pixel z i corresponding to pixel y i ; and

adding the prediction-error vector e′ i to the prediction-error-statistics vector e k corresponding to conditioning class Q i y .

4. The method of claim 3 wherein computing a prediction-error vector e′ i for the prefiltered-image pixel y i further comprises:

multiplication of matrix M′ ({tilde over (x)} i ) by vector u M z i , wherein the matrix M′ ({tilde over (x)} i ) is a 2(M−1)×M matrix, with the first M−1−{tilde over (x)} rows and the final {tilde over (x)} rows having only zero-valued elements, and the interior M rows comprising matrix (π T ) −1 and wherein the vector u M z i is constructed by placing the value “1” in the element of u M z i corresponding to the value z i and placing the value “0” and all other elements of vector u M z i .

5. The method of claim 1 wherein generating, by the electronic computer, normalized and smoothed prediction-error probability distributions {circumflex over (P)} E for each conditioning class further includes:

computing normalized estimated probability distributions {circumflex over (P)} E (Q k ) of the prediction errors for each conditioning class Q k by:

P

^

E

⁡

(

Q

k

)

=

[

R

′

]

-

1

·

e

k

⁢

⁢

where

⁢

⁢

R

′

=

∑

i

:

Q

i

y

=

Q

k

⁢

M

(

x

^

i

)

′

⁢

∏

T

⁢

C

⁡

(

x

^

i

)

;

C({circumflex over (x)} i ) is constructed as shown in FIG. 30 ; and

e k are prediction-error-statistics vectors accumulated for each conditioning class k; and

smoothing the estimated probability distributions {circumflex over (P)} E (Q k ), and thereby eliminating negative entries in {circumflex over (P)} E (Q k ).

6. The method of claim 3 wherein generating, by the electronic computer, normalized and smoothed prediction-error probability distributions {circumflex over (P)} E for each conditioning class further includes:

computing normalized estimated probability distributions {circumflex over (P)} E (Q k ) of the prediction errors for each conditioning class Q k by:

{circumflex over (P)} E ( Q k )=[ R′] −1 ·e k

where R′=|Q k |I,

I is the identity matrix,

|Q k | is the number of occurrences of the conditioning class Q k , and

e k are prediction-error-statistics vectors accumulated for each conditioning class k; and

smoothing the estimated probability distributions {circumflex over (P)} E (Q k ), and thereby eliminating negative entries in {circumflex over (P)} E (Q k ).

7. The method of claim 1 wherein computing, by the electronic computer, for each noisy-image pixel z i an estimated clean-image symbol x i by minimizing a computed distortion over all possible symbols a 0 -a M−1 alphabet A further includes:

for each prefiltered-image pixel y i ,

computing a context-specific prediction-error probability distribution by {circumflex over (P)} x (S i y )=C({circumflex over (x)} i ){circumflex over (P)} E (Q i y ), wherein construction of the matrix C({circumflex over (x)} i ) is shown in FIG. 30 and wherein {circumflex over (P)} E (Q i y ) is a normalized and smoothed prediction-error probability distribution;

computing a clean-image symbol x i predicted for the currently considered noisy-image symbol z i and corresponding prefiltered image pixel y i as:

x

_

.

l

=

argmin

ɛ

∈

A

⁢

⁢

λ

ɛ

T

·

(

P

^

x

⁡

(

S

i

y

)

⁢

•

⁢

⁢

π

z

i

)

.

8. The method of claim 1 further comprising:

again denoising the noisy image z by

using the denoised image containing symbols x i as a next prefiltered image y;

collecting, by the electronic computer, bias statistics for each prediction class in a context-by-context analysis of the next prefiltered image y;

collecting, by the electronic computer, prediction-error distributions in a context-by-context analysis of the noisy image z in which prediction-errors z i −{tilde over (x)} i are used to generate prediction-error vectors e′ k that are added to prediction-error-statistics vectors e k ;

generating, by the electronic computer, normalized and smoothed prediction-error probability distributions {circumflex over (P)} E for each conditioning class;

computing, by the electronic computer, for each noisy-image pixel z i an estimated clean-image symbol x i by minimizing a computed distortion over all possible symbols a 0 -a M−1 of alphabet x i and storing x i in a computer-readable memory for subsequent display and/or output to the user.

9. The method of claim 8 further comprising iteratively denoising the noisy image z by iterating the steps of claim 8 until a convergence criterion or termination condition is met.

10. An electronic-computer-based image-denoising-system comprising:

an electronic computer; and

a control program that directs the electronic computer to denoise an input noisy image z by

computing, by the electronic computer, a prefiltered image y from the noisy image z;

collecting, by the electronic computer, bias statistics for each prediction class representing one or more contexts within each conditioning class in a context-by-context analysis of the noisy image z;

collecting, by the electronic computer, prediction-error distributions in a context-by-context analysis of the noisy image z in which prediction-errors y i −{tilde over (x)} i are used to generate prediction-error vectors e′ k that are added to prediction-error-statistics vectors e k ;

generating, by the electronic computer, normalized and smoothed prediction-error probability distributions {circumflex over (P)} E for each conditioning class; and

computing, by the electronic computer, for each noisy-image pixel z i an estimated clean-image symbol x i by minimizing a computed distortion over all possible symbols a 0 -a M−1 of alphabet A and storing x i in a computer-readable memory for subsequent display and/or output to a user.