1.1 Background and approach

Background

What are the causes of the image distortion? Well using the given model for our blurry observation there are two causes: K and omega.

K is a blurring kernel. It is a matrix convolved with our original image u that performs a linear operation to represent the effects of a particular kind of blur . Omega is a term used to represent the additive forms of noise introduced by our camera and the environment into our imperfect observation.

To model and recover our image, we applied an algorithm know as the Fast Total Variation Deconvolution.

Fast Total Variation Deconvolution takes advantage of our problem structure and assumes several facts about the information in our image. Because of the additive noise in all of our observations, we cannot directly recover our desired image from the blurry observation by performing the inverse of operation, deconvolve our original image with the blurring kernel. Instead, we first try to minimize the noise to approximate an ideal blurring. Then we can invert the problem to find u .

To do this we model our problem using the following equation:

$\underset{u}{\text{min}}\sum _{i=1}^{n^2}\parallel D_{i}u\parallel +\frac{m}{2}{\parallel K\ast u-f\parallel }_2^2$ [5]

In the equation above, we have two terms: the first is our total variation norm, which is a discretized gradient measured across our entire image, the second is the data fidelity term. The data fidelity term attempts to make the difference between our blurry observation and an ideally blurred image very small. If the difference were zero, we could very easily perform the deconvolution to recover u . So, the minimization step will take us as close as possible to a problem with a closed form solution. This model supposes a few facts about our problem. Primarily, it assumes that the majority of scenes in the real world will have flat, uniform surfaces. This means that our image should have very few nonzero gradients and the additive noise will introduce many random peaks and thus non-zero gradients to be minimized.

The full form of the Total Variation Regularization transforms our first model into the following:

$\underset{w,u}{\text{min}}\sum _i{\parallel w_i\parallel }_2+\frac{\beta }{2}\sum _i{\parallel w_i-D_{i}u\parallel }_2^2+\frac{m}{2}{\parallel K\ast u-f\parallel }_2^2$ [5]

This equation adds another term to our model. Here we try to minimize the difference between the non-zero gradients and some term w , while simultaneously trying to make w as small as possible. The beta parameter in the second term helps to establish convergence, when beta is very large. For our purposes, we have used the parameters for convergence given by the FTVd reference, which has chosen optimal value for beta. We can group these terms together as the regularizing term, which constrains our model so that we have a well conditioned noisy observation.

$\underset{u}{\text{min}}J(u)=F_{\text{reg}}(u)+\frac{m}{2}{\parallel K\ast u-f\parallel }^2$ [5]

There are many other possible forms for constrained minimization. Different constraints will result in different ability for our model to converge. The FTVd algorithm performs this minimization using 2FFT’s and one inverse FFT, giving a complexity of N log (N). In particular, we note that the FTVd will converge quickly with relatively little iteration, but it is also important to note that our problem sacrifices some clarity on textured surfaces. This algorithm is ideal for quick noise removal.