# US 8,280,180 B2 · Method and system for image restoration in the spatial domain

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,180 B2
- Document ID: US8280180B2
- Status: Granted
- Kind: B2
- Application number: 12/745,799
- Filed: 2007-12-04
- Published: 2010-09-30
- Granted: 2012-10-02
- Earliest claimed: 2007-12-04
- Assignees: Hewlett-Packard Development Company, L.P.
- Inventors: Ron Banner; Michal Aharon; Carl Staelin
- Web page: https://patentgrep.com/patent/US8280180B2

## CPC

- G06T 5/70: Denoising; Smoothing
- G06T 5/73: Deblurring; Sharpening
- G06T 2207/20024: Filtering details
- G06T 2207/20182: Noise reduction or smoothing in the temporal domain; Spatio-temporal filtering
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

Method and system embodiments of the present invention are directed to restoration of corrupted images using spatial-domain image-processing methods that can effectively employ spatial-domain information both in order to avoid various types of artifacts and distortions produced by frequency-domain image-processing operations and to achieve computational efficiency. The various method and system embodiments of the present invention employ a family of penalty functions to constrain iterative restoration images corrupted by both deterministic corruptions, such as motion-induced blur and blurring due to optical misalignment, incorrect positioning of optical components, and defective optical components as well as essentially non-deterministic noise corruption introduced at various stages of image acquisition, image encoding, image storage, and image transmission.

## Claims

### Claim 1

A method for restoring a blurred and noise-corrupted image, the method comprising:
receiving the blurred and corrupted image B and a spatial-domain blur-operator matrix H that describes deterministic corruption in the blurred and corrupted image;
extending the blur-operator matrix H to produce a degradation matrix Ĥ by adding rows that specify particular restored-image values obtained from smooth regions of the blurred and corrupted image B;
iteratively deblurring and denoising the blurred and corrupted image B to produce a restored-image pair R and {tilde over (R)}; and
storing the restored-image pair R and {tilde over (R)} in a computer-readable memory for subsequent output to a user or for transmission to a restored-image-pair receiving device.

### Claim 2 (depends on 1)

The method of claim 1 wherein extending the blur-operator matrix H by adding rows that specify particular restored-image values obtained from smooth regions of the blurred and corrupted image B further comprises:
identifying neighborhoods in the blurred and corrupted image B with least pixel-value variation; and
while the blur-operator matrix H has fewer rows than columns,
selecting a next pixel value from a next identified neighborhood of blurred and corrupted image B,
inserting a corresponding row in the blur-operator matrix H to extend blur-operator matrix H by one row, and
removing the inserted row from the extended blur-operator matrix H when the determinant of the extended blur-operator matrix H is 0.

### Claim 3 (depends on 1)

The method of claim 1 wherein iteratively deblurring and denoising the blurred and corrupted image B to produce a restored-image pair R and {tilde over (R)} further comprises:
setting a first restored image {tilde over (R)} equal to B; and
iteratively generating next current values of a second restored image R and the first restored image {tilde over (R)} under a constraint that directs R towards a deblurred restored image of B, that directs the first restored image {tilde over (R)} towards a denoised restored image of B, and that minimizes a difference between the second restored image R and the first restored image {tilde over (R)}.

### Claim 4 (depends on 3)

A method of claim 3 wherein iteratively generating next current values of a second restored image R and the first restored image {tilde over (R)} under a constraint that directs R towards a deblurred restored image of B, that directs the first restored image {tilde over (R)} towards a denoised restored image of B, and that minimizes a difference between the second restored image R and the first restored image {tilde over (R)} further comprises:
for a number of iterations prior to occurrence of an iteration termination condition,
determining a next current value of the second restored image R by optimization of the second restored image R under a constraint that a difference between the second restored image R blurred by the blur operator H and the blurred and corrupted image B be minimized and a difference between the second restored image R and the current value of the first restored image {tilde over (R)} be minimized;
determining a next current value for the first restored image {tilde over (R)} under a constraint that a difference between the current value of the second restored image R and the first restored image {tilde over (R)} be minimized and that a weighted differential of the first restored image {tilde over (R)} be minimized; and
determining whether or not an iteration termination condition has occurred.

### Claim 5 (depends on 4)

The method of claim 4 wherein determining a next value of the second restored image R by optimization of the second restored image R under a constraint that a difference between the second restored image R blurred by the blur operator H and the blurred and corrupted image B be minimized and a difference between the second restored image R and the current value of the first restored image {tilde over (R)} be minimized further comprises generating a next current value for the second restored image R under a constraint as expressed by:
R
=
avgmin
R
⁢

H
^
·
R
-
B

2
+
λ
1
·

R
-
R
~

2
wherein λ1 is a constant.

### Claim 6 (depends on 4)

The method of claim 4 wherein determining a next value of the second restored image R by optimization of the second restored image R under a constraint that a difference between R blurred by the blur operator H and the blurred and corrupted image B be minimized and a difference between the second restored image R and the current value of the first restored image {tilde over (R)} be minimized further comprises determining the second restored image R by:
R=(Ĥ·ĤT+λ1·I)−1(ĤT·B+λ1·R)
wherein I is the identity matrix and λ1 is a constant.

### Claim 7 (depends on 4)

The method of claim 4 wherein determining a next current value for the first restored image {tilde over (R)} under a constraint that a difference between the current value of the second restored image R and the first restored image {tilde over (R)} be minimized and that a weighted differential of {tilde over (R)} be minimized further comprises generating a next current value for the first restored image {tilde over (R)} under a constraint as expressed by:
R
~
=
avgmin
R
~
⁢

R
-
R
~

2
2
+
λ
2
λ
1
⁢
∑
n
=
1
N
⁢
(
R
~
-
D
n
⁢
R
~
)
⁢
W
⁡
(
R
,
n
)
⁢
(
R
~
-
D
n
⁢
R
~
)
wherein
R is the more sharpened restored image;
{tilde over (R)} is the more denoised restored image;
λ1 and λ2 are constants;
D is a circulant difference matrix:
D
=
[
0
0
…
0
1
1
0
…
0
0
0
1
0
…
0
0
0
⋱
0
⋮
0
0
0
1
0
]
;
and
W(R,n) is a matrix obtained by applying a weighting function W(•) to each element of R using a neighborhood of size n.

### Claim 8 (depends on 4)

The method of claim 4 further including generating a next value of a penalty function Φ(R,{tilde over (R)}) following generation of a next current value of the second restored image R and a next current value of the first restored image {tilde over (R)}, wherein
Φ
(
R
,
R
~
)
=

H
^
⁢
R
-
B

2
2
+
λ
1
⁢

R
-
R
~

2
2
+
λ
2
⁢
∑
n
=
1
N
⁢
(
R
~
-
D
n
⁢
R
~
)
⁢
W
⁡
(
R
,
n
)
⁢
(
R
~
-
D
n
⁢
R
~
)
.

### Claim 9 (depends on 4)

The method of claim 4 wherein termination conditions include one or more of:
a number of iterations of computing next current values of the second restored image R and the first restored image {tilde over (R)} exceeding a threshold number of iterations;
a difference between a last generated value of the penalty function Φ(R,{tilde over (R)}) and a next most recently generated value of penalty function Φ(R,{tilde over (R)}) falling below a threshold value;
and the last generated value of the penalty function Φ(R,{tilde over (R)}) falling below a threshold value.

### Claim 10 (depends on 1)

The method of claim 1 wherein the blurred and corrupted image B and the restored-image pair R and {tilde over (R)} each comprises one of:
an array of scalar values representing spatial intensities;
an array of scalar, composite values representing spatial intensity and color;
an array of scalar values representing spatial components of color;
a matrix of scalar values representing spatial intensities;
a matrix of scalar, composite values representing spatial intensity and color; and
a matrix of scalar values representing spatial components of color.

### Claim 11

A system that restores a blurred and noise-corrupted image, the system comprising:
an electronic memory and mass-storage memory;
a processor that accesses the electronic memory and mass-storage memory; and
one or more executable routines that execute on the processor to restore the blurred and noise-corrupted image by
receiving the blurred and corrupted image B and a spatial-domain blur-operator matrix H that describes deterministic corruption in the blurred and corrupted image;
extending the blur-operator matrix H to produce a degradation matrix Ĥ by adding rows that specify particular restored-image values obtained from smooth regions of the blurred and corrupted image B;
iteratively deblurring and denoising the blurred and corrupted image B to produce a restored-image pair R and {tilde over (R)}; and
storing the restored-image pair R and {tilde over (R)} in a computer-readable memory for subsequent output to a user or for transmission to a restored-image-pair receiving device.

### Claim 12 (depends on 11)

The system of claim 11 wherein extending the blur-operator matrix H by adding rows that specify particular restored-image values obtained from smooth regions of the blurred and corrupted image B further comprises:
identifying neighborhoods in the blurred and corrupted image B with least pixel-value variation; and
while the blur-operator matrix H has fewer rows than columns,
selecting a next pixel value from a next identified neighborhood of blurred and corrupted image B,
inserting a corresponding row in the blur-operator matrix H to extend blur-operator matrix H by one row, and
removing the inserted row from the extended blur-operator matrix H when the determinant of the extended blur-operator matrix H is 0.

### Claim 13 (depends on 11)

The system of claim 11 wherein iteratively deblurring and denoising the blurred and corrupted image B to produce a restored-image pair R and {tilde over (R)} further comprises:
setting a first restored image {tilde over (R)} equal to B; and
iteratively generating next current values of a second restored image R and the first restored image {tilde over (R)} under a constraint that directs R towards a deblurred restored image of B, that directs the first restored image {tilde over (R)} towards a denoised restored image of B, and that minimizes a difference between the second restored image R and the first restored image {tilde over (R)}.

### Claim 14 (depends on 13)

A system of claim 13 wherein iteratively generating next current values of a second restored image R and the first restored image {tilde over (R)} under a constraint that directs R towards a deblurred restored image of B, that directs the first restored image {tilde over (R)} towards a denoised restored image of B, and that minimizes a difference between the second restored image R and the first restored image {tilde over (R)} further comprises:
for a number of iterations prior to occurrence of an iteration termination condition,
determining a next current value of the second restored image R by optimization of the second restored image R under a constraint that a difference between the second restored image R blurred by the blur operator H and the blurred and corrupted image B be minimized and a difference between the second restored image R and the current value of the first restored image {tilde over (R)} be minimized;
determining a next current value for the first restored image {tilde over (R)} under a constraint that a difference between the current value of the second restored image R and the first restored image {tilde over (R)} be minimized and that a weighted differential of the first restored image {tilde over (R)} be minimized; and
determining whether or not an iteration termination condition has occurred.

### Claim 15 (depends on 14)

The system of claim 14 wherein determining a next value of the second restored image R by optimization of the second restored image R under a constraint that a difference between the second restored image R blurred by the blur operator H and the blurred and corrupted image B be minimized and a difference between the second restored image R and the current value of the first restored image {tilde over (R)} be minimized further comprises generating a next current value for the second restored image R under a constraint as expressed by:
R
=
avgmin
R
⁢

H
^
·
R
-
B

2
+
λ
1
·

R
-
R
~

2
wherein λ1 is a constant.

### Claim 16 (depends on 14)

The system of claim 14 wherein determining a next value of the second restored image R by optimization of the second restored image R under a constraint that a difference between R blurred by the blur operator H and the blurred and corrupted image B be minimized and a difference between the second restored image R and the current value of the first restored image {tilde over (R)} be minimized further comprises determining the second restored image R by:
R=(Ĥ·ĤT+λ1·I)−1(ĤT·B+λ1·R)
wherein I is the identity matrix and λ1 is a constant.

### Claim 17 (depends on 14)

The system of claim 14 wherein determining a next current value for the first restored image {tilde over (R)} under a constraint that a difference between the current value of the second restored image R and the first restored image {tilde over (R)} be minimized and that a weighted differential of {tilde over (R)} be minimized further comprises generating a next current value for the first restored image {tilde over (R)} under a constraint as expressed by:
R
~
=
avgmin
R
~
⁢

R
-
R
~

2
2
+
λ
2
λ
1
⁢
∑
n
=
1
N
⁢
(
R
~
-
D
n
⁢
R
~
)
⁢
W
⁡
(
R
,
n
)
⁢
(
R
~
-
D
n
⁢
R
~
)
wherein
R is the more sharpened restored image;
{tilde over (R)} is the more denoised restored image;
λ1 and λ2 are constants;
D is a circulant difference matrix:
D
=
[
0
0
…
0
1
1
0
…
0
0
0
1
0
…
0
0
0
⋱
0
⋮
0
0
0
1
0
]
;
and
W(R,n) is a matrix obtained by applying a weighting function W(•) to each element of R using a neighborhood of size n.

### Claim 18 (depends on 14)

The system of claim 14 further including generating a next value of a penalty function Φ(R,{tilde over (R)}) following generation of a next current value of the second restored image R and a next current value of the first restored image {tilde over (R)}, wherein
Φ
(
R
,
R
~
)
=

H
^
⁢
R
-
B

2
2
+
λ
1
⁢

R
-
R
~

2
2
+
λ
2
⁢
∑
n
=
1
N
⁢
(
R
~
-
D
n
⁢
R
~
)
⁢
W
⁡
(
R
,
n
)
⁢
(
R
~
-
D
n
⁢
R
~
)
.

### Claim 19 (depends on 14)

The system of claim 14 wherein termination conditions include one or more of:
a number of iterations of computing next current values of the second restored image R and the first restored image {tilde over (R)} exceeding a threshold number of iterations;
a difference between a last generated value of the penalty function Φ(R,{tilde over (R)}) and a next most recently generated value of penalty function Φ(R,{tilde over (R)}) falling below a threshold value;
and the last generated value of the penalty function Φ(R,{tilde over (R)}) falling below a threshold value.

### Claim 20 (depends on 11)

The system of claim 11 wherein the blurred and corrupted image B and the restored-image pair R and {tilde over (R)} each comprises one of:
an array of scalar values representing spatial intensities;
an array of scalar, composite values representing spatial intensity and color;
an array of scalar values representing spatial components of color;
a matrix of scalar values representing spatial intensities;
a matrix of scalar, composite values representing spatial intensity and color; and
a matrix of scalar values representing spatial components of color.
