Week 1: Image Denoising

Goal

The main goal of Week 1 is to implement variational calculus techniques learned in M2 in a real image denoising problem. This will be achieved by applying the Rudin-Osher-Fatemi Denoising Model, with particular attention to the impact the variation of different parameters have on the final image.

Mandatory Tasks

Effect of Model and Numerical Parameters

The denoising is afforded minimizing an energy functional. We can vary some parameters in that functional in order to control how the minimization is done, and therefore the final result. In this section we study the influence of those parameters.

Lambda

The λ is a tradeoff term to control the importance of the regularity and the data fidelity terms in the minimization.

If varying λ we increase the regularity term, the result will be smoother. So we will delete better the noise, but we will smooth object edges.  If we increase the data fidelity term, the result will be more similar to the noisy image. So we will conserve the object edges, but won’t delete as much noise. Consequently, we should give more importance to the data fidelity term when we rely on the image to restore. If the image to restore has a lot of noise, we should give more importance to the regularity term in order to remove it (losing some object edges definition).

When we chose λ we also have to take into account how big is the regularity term chosen. For instance, in the L2-norm regularization method the regularity term is much bigger than in the TV regularization, so we will use λ to compensate that.

λ = 0.05

λ = 0.5

 * In the implementation 1/λ multiplies the fidelity term. So using a higher λ means giving more importance to the regularity term.

Discretization step

From time derivative of image u, used in regularization to determine time step of energy gradient.

Epsilon

The expression for total variation

is not differentiable at the origin or for discontinuous functions u.  To solve this problem, we approximate by a differentiable functional adding the ϵ so the term smooths the peak that the absolute value function has at its minimum in y.

If we choose a high ϵ value, the solution will be smoother. But if we choose an ϵ that is too small, the numerical resolution will fail. We don’t want an image that is too smooth (which is something we want to control with the λ parameter instead), but we don’t want the numerical resolution to fail.

Effect of using different seeds

In this section we study the relevance of the chosen seed. The seed we use for the denoising of the image is related with the data fidelity term. For each of the algorithm iterations, we compute the difference between the original image and the one we are looking for (at the beginning is the seed image). Then, the obtained result is used in the next iteration, and so on.

At first, the image we are looking for is given a known value (the seed image). Using this image as a starting point, in each of the iterations, we denoise it and compare it with the original image. Thus, the more iterations we make, the difference between the original and the used seed image is less. Therefore, the election of the seed image does not matter as long as we make enough iterations.

Results using 2500 iterations. As we can see in the following images, the chosen quantity of iterations gives us the same results even with different seeds, because they are enough for convergence.

Original	Lenna
Random	Zeros

When we do not run the algorithm enough iterations (200 for example), the obtained image is still similar to the seed image. Therefore, the final result changes for each of the seed images.

Original	Lenna
Random	Zeros

Energy Evolution

To solve the denoising problem we minimize the energy functional:

The lambda is a tradeoff term that should be changed to control the importance of the smoothness and the similarity term in the minimization.

At each iteration, the energy should decrease, which means that we are approaching to the ideal solution of the minimization problem.

L2-norm regularization with random seed and lambda = 15.

In the example above, E(u) decreases until nearly 0. Maybe the denoising problem has been solved correctly, but not necessarily; it’s possible that the chosen lambda is not correct. For instance, if the lambda is too big, maybe the resulting image is too smooth, without edges.

Effect of Boundary Conditions

Neumann boundary conditions specify the values that the gradients of the pixels need to take along the boundary, whereas Dirichlet boundary conditions specify the values that the pixels themselves need to take along the boundary.

Dirichlet boundary conditions imply that the borders are a fixed quantity (0, or black), whereas Neumann conditions imply that the gradient is constant, thus completing the image in a more continuous manner, as it bases the value of the next pixel on the previous.

Tikhonov (λ = 15)

The black border and its expansion due to the blurring can be seen by comparing the energies. With Neumann, the energy approaches zero as the iterations approach infinity. With Dirichlet, the asymptote is at Energy ≈ 45.

ROF (λ = 0.5)

We can see that with ROF, the black border when using Dirichlet boundary conditions is more defined and less intrusive in the image than it is with Tikhonov. Mathematically, Dirichlet boundary conditions give the border pixels a constant value. Since the Tikhonov denoising model blurs a lot due to the square value in the smoothness term (p = 2), the edges of the black boundary blur inwards. With ROF, since p = 1, the edges are more defined, so there is less blurring and the constant nature of the Dirichlet boundaries are more obvious.

Solution without Data Fidelity

Without the data fidelity term, the energy functional would be

The minimization would yield the minimum value needed for noise removal, which would blur the image without taking into consideration how similar it might be to the original.

With few iterations, it would simply blur the seed image. After a certain amount of iterations, this would eventually smooth out into a constant color.

Conclusion: Are the results a good solution of the real world problem? 

The results from this denoising method are a good solution of the real world problem. However, energy minimization doesn’t always yield the “best” solution. This is slightly subjective, so we have to look at the solutions ourselves to evaluate them visually, and thus see what parameters were used.