System and method for fixed point continuation for total variation based compressed sensing imaging
View Patent ↗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 i th 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 t n (k) from y n (k) +τ 2 L n Φ −1 x (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 y n (k+1) from min { 1 τ 2 , t n ( k ) 2 } t n ( k ) t n ( k ) 2 .
1. 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 i th 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 t n (k) from y n (k) +τ 2 L n Φ −1 x (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 y n (k+1) from
min
{
1
τ
2
,
t
n
(
k
)
2
}
t
n
(
k
)
t
n
(
k
)
2
.
2. The method of claim 1 , wherein said steps of calculating a first auxiliary variable s (k) , calculating a second auxiliary variable t n (k) , updating x (k+1) , and updating y n k+1) are repeated until convergence.
3. The method of claim 1 , wherein said wavelet transform matrix Φ is a Haar wavelet transform matrix.
4. The method of claim 1 , wherein said Fourier transform matrix R is a non-invertible matrix of size m×n, wherein m is a number of points in image b, n is a number of points in first expanded image x , and m<<n.
5. The method of claim 4 , wherein the m rows of R are selected by sampling more points in Fourier space near bottom corners in said Fourier space, and fewer points approaching a center of said Fourier space, wherein upper half space is masked.
6. The method of claim 2 , further comprising constructing a second expanded digitized image ū from ū=Φ −1 x .
7. The method of claim 2 , further comprising updating said positive, scalar constants α,β from α k+1 =α k η α and β k+1 =β k η β , wherein η α and η β are predetermined positive, scalar constants, and repeating said steps of calculating a first auxiliary variable s (k) , calculating a second auxiliary variable t n (k) , updating x (k+1) , and updating y n (k+1) until convergence.
8. The method of claim 7 , further comprising updating said positive, scalar constants α,β until α,β reach predetermined minimum values.
9. 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Φ −1 x, and m<<n;
jointly minimizing an l 1 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 Φ −1 x, 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 i th coordinate; and
constructing a second expanded digitized image u from u=Φ −1 x, to provide an improved approximation to the first expanded image x.
10. The method of claim 9 , wherein said operator-splitting fixed point iterations comprise the steps of:
initializing points (x (k) , y (k) , wherein x (k) is an initial approximation of the first expanded image x, y (k) is a point in the set of subgradients
∂
(
∑
i
=
1
l
(
∇
i
Φ
-
1
x
(
k
)
)
2
)
1
/
2
,
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 t n (k) from y n (k) +τ 2 L n Φ −1 x (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 y n (k+1) from
min
{
1
τ
2
,
t
n
(
k
)
2
}
t
n
(
k
)
t
n
(
k
)
2
.
11. 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 i th 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 t n (k) from y n (k) +τ 2 L n Φ −1 x (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 y n (k+1) from
min
{
1
τ
2
,
t
n
(
k
)
2
}
t
n
(
k
)
t
n
(
k
)
2
.
12. The computer readable program storage device of claim 11 , wherein said steps of calculating a first auxiliary variable s (k) , calculating a second auxiliary variable t n (k) , updating x (k+1) , updating y n (k+1) are repeated until convergence.
13. The computer readable program storage device of claim 11 , wherein said wavelet transform matrix Φ is a Haar wavelet transform matrix.
14. The computer readable program storage device of claim 11 , wherein said Fourier transform matrix R is a non-invertible matrix of size m×n wherein m is a number of points in image b, n is a number of points in first expanded image x , and m<<n.
15. The computer readable program storage device of claim 14 , wherein the m rows of R are selected by sampling more points in Fourier space near bottom corners in said Fourier space, and fewer points approaching a center of said Fourier space, wherein an upper half space is masked.
16. The computer readable program storage device of claim 12 , the method further comprising constructing a second expanded digitized image ū from ū=Φ −1 x .
17. The computer readable program storage device of claim 12 , the method further comprising updating said positive, scalar constants α,β from α k+1 =α k η α and β k+1 =β k η β , wherein η α and η β are predetermined positive, scalar constants, and repeating said steps of calculating a first auxiliary variable s (k) , calculating a second auxiliary variable t n (k) , updating x (k+1) , and updating y n (k+1) until convergence.
18. The computer readable program storage device of claim 17 , the method further comprising updating said positive, scalar constants α,β until α,β reach predetermined minimum values.