CONTEXT-CLUSTER-LEVEL CONTROL OF FILTERING ITERATIONS IN AN ITERATIVE DISCRETE UNIVERSAL DENOISER

• US 20110026850A1
• Filed: 07/30/2009
• Published: 02/03/2011
• Est. Priority Date: 07/30/2009
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Weinberger, Marcelo, Ordentlich, Erik, Seroussi, Gadiel
• Granted Patent: US 8,385,676 B2
• Time in Patent Office: Days
• US Class Current: 382/261
• CPC Class Codes: G06T 2207/20076 Probabilistic image processing
• CPC Class Codes: G06T 5/002 Denoising; Smoothing noise processing or correction adapted to be used in an image pickup device containing and electronic image sensor H04N23/81, H04N25/60 - H04N25/67
• CPC Class Codes: G06T 5/70 Denoising; Smoothing
• CPC Class Codes: G06V 10/30 Noise filtering

Abstract

Embodiments of the present invention are directed to various enhanced discrete-universal denoisers that have been developed to denoise images and other one-dimensional, two-dimensional or higher-dimensional data sets in which the frequency of occurrence of individual contexts may be too low to gather efficient statistical data or context-based symbol prediction. In these denoisers, image quality, signal-to-noise ratios, or other measures of the effectiveness of denoising that would be expected to increase monotonically over a series of iterations may decrease, due to assumptions underlying the discrete-universal-denoising method losing validity. Embodiments of the present invention apply context-class-based statistics and statistical analysis to determine, on a per-context-class basis, when to at least temporarily terminate denoising iterations on each conditioning class. Each iteration of the iterative methods applies context-based denoising only for those conditioning classes that statistical analysis indicates remain valid for denoising purposes.

Claims

1. An iterative denoising method, carried out by an electronic computer or electronic device, the iterative denoising method comprising:

receiving, by the electronic computer or electronic device, a noisy dataset z; and

iteratively,

computing, by the electronic computer or electronic device, a next prefiltered dataset y,

for each noisy-dataset symbol z_i, computing, by the electronic computer or electronic device, an estimated denoised-dataset symbol {circumflex over (x)}_i by

when a conditioning class Q(z_i) for z_i remains valid for denoising, minimizing a computed distortion to determine {circumflex over (x)}_i, and

when a conditioning class Q(z_i) for z_i is not valid for denoising, determining {circumflex over (x)}_i to be the corresponding prefiltered-dataset symbol y_i.

until a convergence criterion is satisfied.

2. The iterative denoising method of claim 1 further comprising:

following computing a next prefiltered dataset y,

collecting, by the electronic computer or electronic device, prediction-error statistics in a context-by-context analysis of the prefiltered dataset y and generating prediction-error probability distributions {circumflex over (P)}_E for each conditioning class.

3. The iterative denoising method of claim 2 further comprising:

following generating normalized prediction-error probability distributions {circumflex over (P)}_E for each conditioning class,

collecting, by the electronic computer or electronic device, context-based prediction statistics for each conditioning class; and

based on context-based symbol-prediction statistics, determining, by the electronic computer or electronic device, which conditioning classes remain valid for denoising.

4. The iterative denoising method of claim 3 wherein collecting, by the electronic computer or electronic device, context-based symbol-prediction statistics for each conditioning class further comprises:

for each different conditioning class Q_k,

for each noisy-dataset symbol z_i that occurs in a context C_i^y of conditioning class Q_k,

incrementing t(Q_k, z_i);

when z_i is a white-noise symbol a_w,

predicting symbol {tilde over (x)}_i from context C_i^y,

when {tilde over (x)}_i, is less than a threshold value,

 

incrementing n(Q_k, z_i);

when z_i is a black-noise symbol a_b,

predicting symbol {tilde over (x)}_i from context C_i^y,

when {tilde over (x)}_i is greater than a threshold value,

 

incrementing n(Q_k, z_i); and

for each different conditioning class Q_k,

for each symbol a in an alphabet A that includes noisy-dataset symbols z_i and estimated denoised-dataset symbols {circumflex over (x)}_i,

for each symbol b in alphabet A distant from a currently considered symbol a,

adding t(Q_k, b) to nf(Q_k, a).

5. The iterative denoising method of claim 4 wherein determining, by the electronic computer or electronic device, which conditioning classes remain valid for denoising further comprises:

for each different conditioning class Q_k,

when

6. The iterative denoising method of claim 3 wherein collecting, by the electronic computer or electronic device, context-based symbol-prediction statistics for each conditioning class further comprises:

for each different conditioning class Q_k,

for all symbols a₀-a_M-1 of alphabet A, setting n(Q_k, a) equal to 0, setting t(Q_k, a) equal to 0, and setting nf(Q_k, a) equal to 0;

for each noisy-dataset symbol z_i that occurs in a context C_i^y of conditioning class Q_k,

incrementing t(Q_k, z_i);

predicting symbol {tilde over (x)}_i from context C_i^y,

computing a distance d from z_i to {tilde over (x)}_i within alphabet A; and

when d is greater than a threshold distance, incrementing n(Q_k, z_i).

7. The iterative denoising method of claim 6 wherein determining, by the electronic computer or electronic device, which conditioning classes remain valid for denoising further comprises:

for each different conditioning class Q_k,

setting num equal to 0;

for all symbols a₀-a_M-1 of alphabet A for which n(Q_k, a)>

0,

when

8. The iterative denoising method of claim 1 wherein computing, by the electronic computer or electronic device, a next prefiltered dataset y further comprises,

in a first iteration, filtering noisy dataset z by a context-based filtering method;

and

in all remaining iterations, setting prefiltered dataset y to a denoised dataset {circumflex over (x)} generated in a preceding iteration.

9. A denoiser implemented as a software program that executes on an electronic computer, as firmware within an electronic device, as logic circuits within an electronic device, or as a combination of two or more of software, firmware, and logic circuits, the denoiser comprising:

a noisy dataset z stored in an electronic memory;

control logic that iteratively

generates a next prefiltered dataset y,

for each noisy-dataset pixel z_i, determine an estimated denoised-dataset symbol {circumflex over (x)}_i by

when the conditioning class Q(z_i) for z_i remains valid for denoising, minimizing a computed distortion over all possible symbols a₀-a_M-1 of alphabet A to determine {circumflex over (x)}_i, and

when the conditioning class Q(z_i) for z_i is not valid for denoising, determining {circumflex over (x)}_i to be the corresponding prefiltered-dataset symbol y_i.

until a convergence criterion is satisfied; and

stores a predicted denoised dataset {circumflex over (x)} comprising the estimated denoised-dataset symbols.