DDA 3005 — Numerical Methods

2024-12-12 Admin 写评论

Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

DDA 3005 — Numerical Methods

Course Project
Image Deblurring and QR Factorizations
Problem 1 (Course Project): (approx. 100 pts)

The goal of this course project is to investigate and implement different algorithms (including QR factorizations, least squares models, etc.) to reconstruct blurry images.

Project Description and Tasks. General deblurring problems can be modeled in the following way. Given a blurry image B ∈ R n×n and two blurring kernels  ∈ R n×n and  ∈ R n×n , we consider linear systems of the form:


We seek to recover the original image X ∈ R n×n , i.e., we can set X =   if the matrices   and  are invertible.
The problem (1) can be used to model the deblurring problem presented in one of our introductory
lectures. A typical format for the blurring kernels  and  is

∈ R n×n , ai ∈ R,
∀ i.

For instance, if A is symmetric with ai ≥ 0 and a1 + · · · + an = 1, then the corresponding blurring kernel computes weighted averages of pixels in the matrix X which results in the blurry image B.

Furthermore, in order to generate motion-type blurring, we can consider the specific choice:

h an+j an+j−1 . . . an+j−k+1i = k(k 2 + 1) h k k − 1 . . . 1 i and ai = 0
(2)
for all i > n + j and i < n + j − k + 1 and suitable j, k ∈ N. Let us consider two examples:
• We consider A with n = 5, j = 0, k = 2 and B with n = 5, j = 1, k = 3. Then, for A, we have n + j = 5, n + j − k + 1 = 5 − 2 + 1 = 4, and [a5, a4] = 1 3 [2, 1]. This implies that the matrix A is diagonal with an additional superdiagonal (corresponding to a4). For B, we obtain n + j = 6, n + j − k + 1 = 4, and [b6, b5, b4] = 1 6 [3, 2, 1]. Overall, this yields

∈ R 5×5 .
Several illustrating examples of the blurring operation (1) are presented below in Figure 1.

Figure 1: Left: Original image X. Middle and Right: Blurred images.

a) The blurry images shown in Figure 1 are created using kernels following the format (2):
for  :
j = 0, k = 12
( is an upper triangular matrix)
for :
j = 1, k ∈ {24, 36}
(Ar is upper triangular with an extra subdiagonal)

On BB, we have provided a test set of original images X with different sizes n. The images are saved using the format

n_name_original.png to indicate n. Download the test image package from BB. Select several images and construct suitable blurring kernels Aℓ and Ar as well as the corresponding blurry images B. Select at least two different images and create two different blurry versions of the images. You can follow the outlined construction of Aℓ and Ar (other blurring kernels are also possible).

Hint: The test image package also contains two test files that showcase how to load, read, and write image files in MATLAB and Python.

b) Design and implement an algorithm in MATLAB and Python that can solve problem (1) and recover the original image X from a given blurry image B and known blurring kernels Aℓ and Ar. Specifically, develop two suitable codes for solving (1) that are based on

– LU factorizations of  and
– QR factorizations of and  and test the methods on the generated problems from part a). For each tested image reportyour result (i.e., plot your reconstructed image), the required cpu-time, and the relativeforward error (using the Frobenius norm). What are your observations? Which versionreturns better results? Can you explain your observations?

You are allowed to use MATLAB or Python inbuilt operations to compute the LU factorizations, the QR factorizations, etc.

c) Let A ∈ R m×n be a given matrix with m ≥ n. Implement the (your own) Householder QR factorization A = QR in MATLAB or Python (with our without column permutations).

You can follow the steps and derivations discussed in lectures L-12 and L-13. It is not necessary to return the full orthonormal matrix Q, but your code should be (potentially) adjustable so that it can be used for the application in part b).

d) Repeat the task in part b) using your own implementation of the QR factorization. What are your observations? Does your code return the same or similar results?

Hint: You do not need to beat the inbuilt QR factorizations provided by MATLAB or Python.

e) The reconstructions obtained in part b) and d) can still be affected by numerical errors and might not be perfect. Based on your results in part b), discuss potential improvements or more robust versions of your algorithm. In particular, consider the least-squares formulation of (1),

min ∥AℓXAr − B∥ 2 F ,
X
as a potential direction and check whether the blurring kernels Aℓ and/or Ar are (approxi-mately) singular. Explain your adjustments and discuss the modified results.

General Hints and Guidelines:

• You can use the peak-signal-to-noise ratio


to measure the quality of your reconstructions Xrec. (If you have rescaled the images to [0, 1], then you do not need the factor “2552 ” in PSNR).
• You can resize/rescale the images to test your implementation first on simpler and low-dimensional examples.

• It is possible to pad the images, i.e., to extend the image borders with additional white pixels (or other suitable colors). This can result in a smoother/more natural blurred image.

Project Report. This is an individual course project.

A report should be written to summarize the project and to collect and present your differentresults. The report itself should take no more than 10–15 typed pages plus a possible additional appendix. It should cover the following topics and items:

  • What is the project about?
  • What have you done in the project? Which algorithmic components have you implemented?
  • Summarize your main results and observations.
  • Describe your conclusions about the different problems and methods that you have studied.

You can organize your report following the outlined structure in this project description.

Try to be brief, precise and fact-based. Main results should be presented by highly condensed and organized data and not just piles of raw data. To support your summary and conclusions, you can put more selected and organized data into an appendix which is not counted in the page limit.

The deadline for the report submission is December, 9th, 11:59pm (night). Please submit your report (as pdf-document) and all supporting materials and code online using Blackboard.

发表评论

电子邮件地址不会被公开。 必填项已用*标注