Linear Algebra in Deblurring and Blurring an Image

2k Views Asked by At

I have been trying to research the various mathematical techniques involved in the image processing application of deblurring. Many of the resources that I have found have been demonstrated using high-level mathematics with a large amount of assumed knowledge, or have been equation-heavy with very little explanations of why the equations are used and what they are looking to accomplish. It seems a strong understanding Singular Value Decomposition is a good starting place, but I find most explanations of it's application in deblurring very confusing.

I am ideally looking for a general explanation of how linear algebra applies to deblurring and what mathematical techniques are essential to the process. It would be helpful if any included equations had an explanation of why they are used and what they aim to accomplish. I have been desperate to find some sort of introduction into this topic so any information is greatly appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

Here's a very simplistic SVD model.

Let $b$ be the blurred image and $x$ be the deblurred image. We assume these are the vector forms of the image, created by "reshaping" the standard image matrix into a single column vector.

Then, let's assume that the blurring is caused by a linear operation $A$ so that: $$ b = Ax $$ Suppose we know $A$. Often, we can estimate it e.g. by some calibration images. You might think that we could just obviously take $\tilde{x}=A^{-1}b$. But this will fail (e.g. see here or here). It will emphasize the noise in the image.

Let's see why. The SVD is written $A = U \Sigma V^T$. So, $A^{-1}=V\Sigma^{-1}U^T$ because $U,V$ are orthogonal. Then we can write the matrix multiplication: $$ \tilde{x} = \sum_i \frac{1}{\sigma_i}u_i^Tbv_i $$ The next fact you likely know, but is key in general: for any matrix, the components corresponding to the smaller singular values (SVs) are the "noise-like" components. This is why one way to denoise an image is to treat it as a matrix and zero the smaller SVs.

Since we are inverting the singular values, we are now emphasizing the noise components, because the later (smaller) SVs are now the larger ones!

We fix this by truncation. If $b\in\mathbb{R}^N$, let $k<< N$ and define $$ {x} = \sum_{i=1}^k \frac{1}{\sigma_i}u_i^Tbv_i $$ so this removes those offending small SVs. Notice the tradeoff: removing some of the noise components also removes some of the real data. This works a bit better.

See e.g. Fundamentals of Algorithms - Deblurring Images: Matrices, Spectra, and Filtering by Hansen et al for more.