US 8,014,616 B2 · System and method for fixed point continuation for total variation based compressed sensing imaging

Abstract

A method of compressed sensing imaging includes acquiring a sparse digital image b, said image comprising a plurality of intensities corresponding to an I-dimensional grid of points, initializing points (x(k), y(k)), wherein x(k) is an element of a first expanded image x defined by b=RΦ−1 x, wherein R is a Fourier transform matrix, Φ is a wavelet transform matrix, y(k) is a point in ∂ ( ∑ i = 1 l ⁢ ( ∇ i ⁢ Φ - 1 ⁢ x ( k ) ) 2 ) 1 / 2 , ∇i is a forward finite difference operator for a ith coordinate, and k is an iteration counter; calculating a first auxiliary variable s(k) from x ( k ) - τ 1 ( αΦ ⁢ ∑ n ⁢ L n * ⁢ y n ( k ) + Φ ⁢ ⁢ R * ( R ⁢ ⁢ Φ - 1 ⁢ x ( k ) - b ) ) , wherein τ1,α are predetermined positive scalar constants, the sum is over all points n in x, and L* is an adjoint of operator L=(∇1, . . . , ∇I); calculating a second auxiliary variable tn(k) from yn(k)+τ2LnΦ−1x(k), wherein τ2 is a predetermined positive scalar constant; updating x(k+1) from sign(s(k))max{0,|s(k)|−τ1β}, wherein β is a predetermined positive scalar constant; and updating yn(k+1) from min ⁢ { 1 τ 2 ,  t n ( k )  2 } ⁢ t n ( k )  t n ( k )  2 .

Claims18

Dependent claims

A computer-implemented method of expanding a sparsely sampled digitized image, the method performed by the computer comprising the steps of:

acquiring a sparse digital image b, said image comprising a plurality of intensities corresponding to an I-dimensional grid of points;
initializing points (x(k), y(k)), wherein x(k) is an initial approximation of a first expanded image x recovered from the sparse digital image b and defined by b=RΦ−1 x, wherein R is a Fourier transform matrix, Φ is a wavelet transform matrix, y(k) is a point in the set of subgradients
∂
(
∑
i
=
1
l
⁢
(
∇
i
⁢
Φ
-
1
⁢
x
(
k
)
)
2
)
1
/
2
,
∇i is a forward finite difference operator for an ith coordinate, and k is an iteration counter;
calculating a first auxiliary variable s(k) from
x
(
k
)
-
τ
1
(
α
⁢
⁢
Φ
⁢
∑
n
⁢
L
n
*
⁢
y
n
(
k
)
+
Φ
⁢
⁢
R
*
(
R
⁢
⁢
Φ
-
1
⁢
x
(
k
)
-
b
)
)
,
wherein τ1, α are predetermined positive scalar constants, the sum is over all points n in x, and L* is an adjoint of operator L=(∇1, . . . , ∇I);
calculating a second auxiliary variable tn(k) from yn(k)+τ2LnΦ−1x(k), wherein τ2 is a predetermined positive scalar constant;
updating x(k+1) from sign(s(k))max{0,|s(k)|−τ1β}, wherein β is a predetermined positive scalar constant, to provide an improved approximation to the first expanded image x;
and
updating yn(k+1) from
min
⁢
{
1
τ
2
,

t
n
(
k
)

2
}
⁢
t
n
(
k
)

t
n
(
k
)

2
.

112 more elements

A computer-implemented method of expanding a sparsely sampled digitized image, the method performed by the computer comprising the steps of:

acquiring a sparse digital image b, said image comprising a plurality of intensities corresponding to an I-dimensional grid of points;
providing a wavelet transform matrix Φ;
providing a non-invertible Fourier transform matrix R of size m×n, wherein m is a number of points in image b, n is a number of points in a first expanded image x recovered from the sparse digital image b and defined by b=RΦ−1x, and m<<n;
jointly minimizing an l1 norm, a total variation, and a least squares measure
min
x
⁢
(
α
⁢
⁢
TV
⁡
(
Φ
-
1
⁢
x
)
+
β
⁢

x

1
+
1
2
⁢

Ax
-
b

2
2
)
to solve for x using operator-splitting fixed point iterations, wherein x is said first expanded image, A=RΦ−1, α and β are predefined positive parameters,
TV
⁡
(
u
)
⁢
:
⁢
=
∑
n
⁢
(
∑
i
⁢
(
∇
i
⁢
u
n
)
2
)
1
/
2
is a total variation of Φ−1x, wherein the outer sum is over all points in x, the inner sum is over all dimensions, ∇i denotes the forward finite difference operators on the ith coordinate;
and
constructing a second expanded digitized image u from u=Φ−1x, to provide an improved approximation to the first expanded image x.

68 more elements

A non-transitory program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for expanding a sparsely sampled digitized image, said method comprising the steps of:

acquiring a sparse digital image b, said image comprising a plurality of intensities corresponding to an I-dimensional grid of points;
initializing points (x(k), y(k), wherein x(k) is an initial approximation of a first expanded image x recovered from the sparse digital image b and defined by b=RΦ−1 x, wherein R is a Fourier transform matrix, Φ is a wavelet transform matrix, y(k) is a point in the set of subgradients
∂
(
∑
i
=
1
l
⁢
(
∇
i
⁢
Φ
-
1
⁢
x
(
k
)
)
2
)
1
/
2
,
∇i is a forward finite difference operator for an ith coordinate, and k is an iteration counter;
calculating a first auxiliary variable s(k) from
x
(
k
)
-
τ
1
(
α
⁢
⁢
Φ
⁢
∑
n
⁢
L
n
*
⁢
y
n
(
k
)
+
Φ
⁢
⁢
R
*
(
R
⁢
⁢
Φ
-
1
⁢
x
(
k
)
-
b
)
)
,
wherein τ1,α are predetermined positive scalar constants, the sum is over all points n in x, and L* is an adjoint of operator L=(∇1, . . . , ∇I);
calculating a second auxiliary variable tn(k) from yn(k)+τ2LnΦ−1x(k), wherein τ2 is a predetermined positive scalar constant;
updating x(k+1) from sign(s(k))max{0,|s(k)|−τ1β}, wherein β is a predetermined positive scalar constant, to provide an improved approximation to the first expanded image x;
and
updating yn(k+1) from
min
⁢
{
1
τ
2
,

t
n
(
k
)

2
}
⁢
t
n
(
k
)

t
n
(
k
)

2
.

112 more elements

Dependencies are inferred from the claim text.

System and method for fixed point continuation for total variation based compressed sensing imaging

Life of this patent

System and method for fixed point continuation for total variation based compressed sensing imaging

Life of this patent

Abstract

Claims18