In this class you will learn the basic principles and tools used to process images and videos, and how to apply them in solving practical problems of commercial and scientific interests. Digital images and videos are everywhere these days – in thousands of scientific (e.g., astronomical, bio-medical), consumer, industrial, and artistic applications. Moreover they come in a wide range of the electromagnetic spectrum - from visible light and infrared to gamma rays and beyond. The ability to process image and video signals is therefore an incredibly important skill to master for engineering/science students, software developers, and practicing scientists. Digital image and video processing continues to enable the multimedia technology revolution we are experiencing today. Some important examples of image and video processing include the removal of degradations images suffer during acquisition (e.g., removing blur from a picture of a fast moving car), and the compression and transmission of images and videos (if you watch videos online, or share photos via a social media website, you use this everyday!), for economical storage and efficient transmission. This course will cover the fundamentals of image and video processing. We will provide a mathematical framework to describe and analyze images and videos as two- and three-dimensional signals in the spatial, spatio-temporal, and frequency domains. In this class not only will you learn the theory behind fundamental processing tasks including image/video enhancement, recovery, and compression - but you will also learn how to perform these key processing tasks in practice using state-of-the-art techniques and tools. We will introduce and use a wide variety of such tools – from optimization toolboxes to statistical techniques. Emphasis on the special role sparsity plays in modern image and video processing will also be given. In all cases, example images and videos pertaining to specific application domains will be utilized.
Iterative Least-Squares and Constrained Least-Squares
Loading...
Del curso dictado por Northwestern University
Fundamentals of Digital Image and Video Processing
723 calificaciones
De la lección
Image Recovery: Part 1
In this module we study the problem of image and video recovery. Topics include: introduction to image and video recovery, image restoration, matrix-vector notation for images, inverse filtering, constrained least squares (CLS), set-theoretic restoration approaches, iterative restoration algorithms, and spatially adaptive algorithms.
Conoce a los instructores
Aggelos K. KatsaggelosJoseph Cummings Professor
Department of Electrical Engineering and Computer Science
Hello.
In this segment, we utilize the success of approximations iterative approach
towards the solution of the least squares and the constrained least squares filter.
It's a gradient descent method in essence, since
we are utilizing the gradient of the objective function.
Although we're utilizing a fixed step size.
We derive sufficient conditions for convergence of the two
iterations using the same approach as in the previous segment.
As demonstrated experimentally, an important
benefit of the iterative restoration algorithm.
Of a, a direct implementation of this restoration feat when this is an option.
Is, that, the number of iterations can be used as a means of regularization.
That is, to control the tradeoff between
sharpness of the solution, and noise amplification.
Due to this, the choice of regularization parameter also becomes secondary.
That is the value of the regularization parameter
can be chosen based on some general guidelines.
And then, the most desirable solution can
be chosen after an appropriate number of iterations.
If we choose as phi of f one half the gradient of
respect to f of this error norm, then the iteration takes this form.
This is the, gradient of the norm here.
And this is really the, iterative, iterative implementation
of the least squared filter that we started earlier.
So if H is block circulant, then I can take this
to the frequency domain and the iteration takes exactly this form.
Let's look now at the convergence properties of this algorithm.
Following exactly the same steps, we, we took
in the previous case it's straightforward to show.
That the restoration filter now with the kth iteration step
in the frequency domain, u, v discrete frequencies, has this form.
And the summation is equal to this.
So, for convergence of this series when k goes to infinity.
The condition is that the magnitude of this term here
is strictly less than 1.
But since, now, I have the magnitude of H inside the magnitude, this
is a real number and it's non-negative.
So with the exception of the frequencies for which H
is equal to 0 this condition can be always satisfied.
Actually, the 0 frequencies don't cause a
problem if we look at the restoration filter.
At those frequencies for which H is 0, is going to be 0.
Therefore, the restored image is going to be 0 at those frequencies.
So from here, then, it's easy to find this.
And since H u, v is normalized with the maximum value to 1.
Then this condition really becomes that beta should be
between 0 and 2 to guarantee convergence of the algorithm.
Actually the closer to two the faster the algorithm converges.
So if I look at the limiting condition there of the restoration
filter, as k goes to infinity is equal to the inverse filter.
For those frequencies that H is different than 0,
and it's exactly 0 for the 0 frequency of H.
And this is exactly the solution we obtained with the
least squares filter or the generalized inverse of the matrix H.
Although the one pass least squares filter and the iterative least
squares filter in the limit will give us the same answer.
There are certain advantages that data figure offers that they mentioned
earlier on and therefore it's worth looking in to it's behavior.
So here, for the same experiment that
we have been working throughout this presentation.
We have a blurred image.
Motion blurred over eight pixels, horizontally.
But there's no noise in this experiment.
So here we show the residual error, which is the f of k plus 1
minus f of k, norm squared, divided by f of k.
This is the standard convergence criterion is used when either
of the algorithms are deployed and we set the threshold.
And when this error becomes smaller
than the threshold, then we declare convergence.
So, the threshold here for this experiment was at 10 minus 8.
So the algorithm converged at this point and it's exactly 465 iterations.
So we do want to look at this point of convergence, but also want to look at
these two earlier points after 20 and after 50 iterations.
So let's see how the restoration looks after 20, 50 and 465 iterations.
We see here the familiar motion blurred image
over eight pixels horizontally, no noise has been added.
This is a slice of the magnitude
of the frequency response of the degradation system.
It's a sync function rectified.
And this slice depends only on one
frequency, it's independent of the other one.
We show here the restoration by
the iteratively squares filter after 20 iterations.
And this is the improvement in signal to noise ratio.
I call your attention to the maximum value here of the spectrum, it's three.
And by looking at the, the general comment would
be that the low frequencies of the restoration filter.
Since they converge faster they're closer to the shape of the least squares filter.
While the high frequencies of the restoration
filter since they converge slower, are far away
from the values of the the squares filter.
We show, here, the restored images by
the iteratively least squares filter, after 50 iterations.
And after 465 iterations at convergence, based on this threshold that we utilized.
So the image on the left has ISNR 622 dB the image on the right ISNR 11.58 dB.
So the general statement base for the ISNR values, but also in the visual qualities
that the more iterations the sharper the restored image.
And this agrees with the description we've been making that the
low frequencies are restored faster than the high frequencies the edges.
So as the iteration progresses you see
shaper and sharper edges in the restored image.
I should also call your attention to the fact that the scale here changes.
It's 5 here, it's 14 here, pointing to the fact
that again, this restoration filter approaches the least squares filter.
At different rates for low and high frequencies.
So you see more activity at high frequencies as the iteration increases.
We show here and compare the historic images obtained by
the iteratively least squares filter, after 465 iterations at convergence.
And by the direct inversion of the, degradation.
The image on the left has improvement in signal to noise ratio, 11.58 dB.
While the image on the right has 15.5 dB.
So, based on this metric, this image is closer to the original one than this one.
By looking at the images however, it can be
argued, I would argue that the so called ringing artifacts.
And we'll talk about them a bit later, are
more pronounced on this image than on this one.
And therefore, I would argue that this has a worse quality than this image over here.
So this also points to the fact that error based objective metrics of
quality do not really always represent the visual quality of images.
This difference can be attributed to the shape
of the frequency response of the restoration filter.
The one shown here, the one shown here.
Again calling your attention to the fact that the maximum
value here is 14, while the maximum value here is 100.
Actually, the exact 0s of the frequency response of the
degradation system do not cause any problems with this generalized inversion.
The restoration filter will be 0 as well at those frequencies.
But it's really the small values of
the frequency response degradation system that cause problems.
And these small values give rise in the restoration filter to values like 80 here.
While this same frequency in the iteratively restored image
in the iteratively restoration filter there is only 14.
So it is this tapering off at the high frequencies of this,
again, iteratively implemented restoration filter that result in this visual quality.
And actually, this is the property that really provides
advantages to the iterative restoration filter when noise is present.
So here is a situation in the presence of noise.
One the motion blur over eight pixels plus 20 dB BMSR.
We show three restorations by the iterative
least squares filter, after 20 iterations here.
50 iterations.
And the convergence after 1,376 iterations here.
And the last one is the direct inversion.
So as it was argued earlier, the iterative implementation of the filter
is just doing a better job when it comes to noise amplification.
Although one might argue that both these images are unacceptable.
However if one were to pick, you would
pick, I guess, the lesser of the two evils.
This one here is, again a better quality relatively speaking than this one.
However, the real advantage comes from the fact that
in getting to this restoration after 1376 iterations of convergence.
We can pick any of these two restorations.
And most probably after 50 iterations, we have a,
an acceptable, decent restoration that might serve our purposes.
So this noise amplification restoration and noise
amplification they, they, they go hand in hand.
I restore high frequencies of the image, but
at the same time the noise is amplified.
It takes place gradually, iteration by iteration.
And therefore, as it was argued earlier on,
the number of iterations provides a means of rigorization.
The noise can be controlled this way.
And if a human is in the loop then any intermediate
result before conversion can be used as they restore the image.
The ISNL's shown here and some of them
are negative even at 50 durations is negative 0.3.
Which means that the denominator in that expression is larger than the numerator.
And it's considerably large for the last two restorations.
Although in this particular case based on ISNR [UNKNOWN]
minus 90dB is a better quality, versus minus 12dB.
We show data implementation of the constrained least
squares filter least squares filter here for completeness.
Once we have gone through the structure
and the analysis of these iterative algorithms.
Then, it should be crystal clear here, what happens with the CLS filters.
So, the function, we try to find a root of is shown here, fi of f.
And then, here is the resulting iteration.
The successful approximation based iteration.
So in addition to the fidelity term, we have
the smoothness constraint, and alpha here is the regularization parameter.
When both H and C are block circulant, this iteration can be
taken to the discrete frequency domain, and this is the resulting form.
When alpha equals 0 then this iteration becomes
the iteration of the least squares filter we had.
As we know the CLS becomes the LS filter.
Here is the resulting convergence analysis and the discrete frequency domain.
So the sufficient condition for convergent is shown here.
Now, I have the frequency response to the degradation system
plus alpha, the magnitude of the frequency response of the constraint.
So, even when H is 0 at certain frequencies.
As long as C is not 0,
those same frequencies these unquality can be satisfied.
This is mother of five this can be a guiding principle in choosing a C.
We want the C that will be non 0.
Where H is zero and have some values.
And also take the small values of H away from 0.
As k goes to infinity this is the resulting form of the restoration
filter, the iterative restoration filter and as expected is the CLS filter.
When the denominator is different than 0 and is 0 otherwise.
So, it's a kind of generalized again inversion.
We show here, results obtained by
the iterative constrained least squares filter.
The degraded image is the same one we will be using through out this presentation.
Due to 1D motion blur over eight pixels with BSNR equal to 20dB.
For the CLS filter, a 2D Laplacian is used
and here is the value of the rigorization parameter.
So on the left, we see the restored image after 20 iterations.
And on the right restored image after 50 durations.
Below it,we show the magnitude of the frequencies response
of the restoration filter, which is a function of iteration.
So again, 20 over here 50 over here.
Now this frequency response is the slice we
show here is the one going through the origin.
Because it's not independent of the second, variable,
as was the case without the, the sequence strain.
This filter converges toward the CLS filter.
But the rate of convergence it's faster for those frequencies for
which, the frequency response of the degradation system has larger values.
Than for those frequencies that it has smaller values.
So in the low frequencies will converge faster and the frequencies close to 0.
The 0 itself is not a problem, because this is generalized inversion.
So H is 0, the restoration filter is 0 the same frequencies.
But around it there are nonzero values, very small but nonzero
values which will converge slower towards the constraint least squares filter.
Again, the scale is different here, it's maximum is three.
Maximum is five.
Another, interesting observation is that the
ISNR decreases with the number of iterations.
So this image is closer to the original one than this one.
However, by looking at the images.
I would argue that these probably is a better restoration than this one.
Of course, the characteristic is that as the
number of iteration increases, the edges become sharper.
However, along with that, noise magnification takes place.
But still the amplification of the noise is kind of acceptable here.
And this again, could be an acceptable restoration for
the, for our purposes, to serve our purposes well.
[BLANK_AUDIO]
Here is finally the comparison between the
iterative CLS filter and the direct CLS filter.
So the result of the left was obtained after 330 durations at convergence.
In terms of bias and now the image on the left is
better than the image on the right slightly, close to the original one.
By looking at the images maybe there's more noise in this one then this one.
And below, we see the magnitude of
the frequencies response of the restorative filter.
It's very similar for most values.
It's over here, the maximum here is 12, here is 30.
It's around this frequencies that we have this
larger values for the
direct implementation [UNKNOWN] related implementation.
And this because again there are some very small
values in the frequency response from the gradation system.
And those are the frequencies that are very slow to converge.
The convergence criterion utilize all the pixels in the image.
I could potentially devise a convergence criterion per frequency.
Can see, and kind of, do not stop iterating for
specific frequencies, until a, a, a threshold is met.
So I could potentially run a different number of iterations per frequency.
[BLANK_AUDIO]
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
