Description
MTH 410/510 Inverse Problems & Data Assimilation
The goal of this project is to apply regularization techniques for reconstructing an image from an
incomplete (gappy) blurred version of it. The setup is as follows.
Consider an image represented as a matrix X ∈ R
n×m and a columnwise (1-dimensional) blurring/transmission process represented by the nonsingular matrix A ∈ R
n×n
such that the true image
is the solution to the matrix equation
AX = D, AX(:, j) = D(:, j) , for j = 1 : m (1)
In practice, it is often the case that we only have available an incomplete data set corrupted by
noise (measurement and/or representation errors),
M ◦ Db = M ◦ (D + ξ) (2)
In equation (2), ξ ∈ R
n×m denotes a matrix of random noise, ◦ denotes the elementwise (Hadamard)
matrix product and M ∈ R
n×m is a ”mask” matrix whose entries are 0 or 1 and are used to indicate
data availability:
Mi,j = 1 if data Db i,j is available; Mi,j = 0 if data Db i,j is not available.
Essentially, if J ∈ R
nj
, nj ≤ n, denotes the vector of indices of all nonzero entries in the column
j of the mask matrix,
J = f ind(M(:, j))
then the column j of the reconstructed image Xb is obtained as a regularized solution to the underdetermined linear system of nj equations for n unknowns
A(J, :)Xb (:, j) = Db (J, j) (3)
Columnwise Reconstruction Algorithm
for j = 1 : m
J = f ind(M(:, j))
Xb (:, j) = rgmethod
A(J, :), Db (J, j)
end
where rgmethod represents the regularization method used to solve (3).
Figure 1: The mask matrix M (left figure) and the masked noisy data M◦Db (right figure). Roughly,
50% of data is masked (missing).
Project requirements
In this project n = 220, m = 520, and X is a 220 × 520 matrix representing the image of a
dollar bill. The blurring operation is represented as follows: Consider a n×n symmetric tridiagonal
matrix B with entries 1
B(i, i) = 1 − 2s, i = 1, 2, . . . n
B(i, i + 1) = s, i = 1, 2, . . . n − 1; B(i + 1, i) = s, i = 1, 2, . . . n − 1
where s = 0.45. Then the blurring operator is
A = B
10
The file ”mask.m” contains the 220 × 520 mask matrix M and the file ”prdata.m” contains the
220 × 520 masked noisy data matrix M ◦ Db in (2). In MATLAB you may execute:
load mask.m; imagesc(mask); colormap(gray);
load prdata.m; D = prdata; imagesc(D); colormap(gray)
to visualize M and M ◦ Db as shown in Fig. 1.
Your job: Implement a regularization procedure of your choice to provide an approximation
Xb of the unknown image X such that the serial number on the dollar bill can be identified.
Provide the serial number, an image of the reconstructed bill and a listing of the code you
used to obtain the solution Xb , clearly indicating the regularization procedure implemented and the
specification of the regularization parameters (e.g., TSVD, standard/generalized Tikhonov, TV).
1
such matrix results from discretization of the 1-D heat equation ut − kuxx = 0 with s = k∆t/(∆x)
2
.