In this course, you will learn the science behind how digital images and video are made, altered, stored, and used. We will look at the vast world of digital imaging, from how computers and digital cameras form images to how digital special effects are used in Hollywood movies to how the Mars Rover was able to send photographs across millions of miles of space. The course starts by looking at how the human visual system works and then teaches you about the engineering, mathematics, and computer science that makes digital images work. You will learn the basic algorithms used for adjusting images, explore JPEG and MPEG standards for encoding and compressing video images, and go on to learn about image segmentation, noise removal and filtering. Finally, we will end with image processing techniques used in medicine. This course consists of 7 basic modules and 2 bonus (non-graded) modules. There are optional MATLAB exercises; learners will have access to MATLAB Online for the course duration. Each module is independent, so you can follow your interests.
2 - Introduction to Sparse Modeling - Part 2 - Duration 18:16
Loading...
来自 Duke University 的课程
Image and Video Processing: From Mars to Hollywood with a Stop at the Hospital
496 个评分
Duke University
496 个评分
从本节课中
Sparse modeling and compressed sensing
Here the goal is to present one of the most modern tools in image and video processing, and students will learn something that is today at the top of active research. This will also help to illustrate the use of linear algebra and optimization in image and video processing. This is the last formal unit of the course.
与讲师见面
Guillermo SapiroProfessor
Electrical and Computer Engineering
We're going to use a very simple diagram to demonstrate and to present the model.
Again we are on the search for a model for a signal X that has N dimensions.
What is N? For example if we consider 8x8 blocks.
As in jpeg we have that N is equal to 64 why 64?
We take an 8x8 block or image patch and we take one row after another.
We concatenate them and we get N = 64. This is the signal we are looking to
model. Now.
The next step and actually one of the main components of Sparse Modelling is
the Dictionary. The Dictionary is a matrix which is N by
K. N is the dimension of the signal we are
looking to model. K is the size of the dictionary.
We have K columns. Every column is called an atom.
It's kind of an image, kind of a patch. Because every column is 64-dimensional.
And we have K such columns. Very often, k.
Is larger than n. That's not necessary, but happens very
often. For example, when we are going to do
image renouncing as we are using as an example.
If case larger than n, then we say that the dictionary is over complete.
Now, if K is equal to N, then the dictionary's complete.
For example, Fourier or discrete cosine transform are complete dictionaries.
If K is less than N, we say that a dictionary is under-complete.
Now we have the dictionary. The second element of sparse modeling is.
This vector alpha. And what we have is a vector, alpha, that
has to have dimensions, K, and we multiply the matrix, D, the dictionary,
by the vector, alpha, and we produce the signal that we're trying to model.
What's particular of this vector alpha, is the number of non zero entries of the
vector is very small. We represent those by this red dot.
We have, at most, L non zero entries. And when we multiply this matrix, the
Dictionary D by alpha. What we are doing is having a linear
combination of the atoms. Corresponding to the non-zero entries.
So, we are combining, this is the second one.
It means it's picking the second atom. This is picking its corresponding atom.
And this is picking its corresponding atom.
And we basically have a linear combination according to the coefficients
here of those L atoms. And because these are only a few non-zero
coefficients, this vector is very sparse. And from that, the concept of sparse
modeling. So what we have is basically.
A signal. Represented as a product of the
dictionary, and a vector alpha. With only a few non zero entries.
A very sparse vector. Now, this model is, first of all, very,
very simple. Once we have the dictionary, d.
And alpha will obtain the signal just by a simple product.
This dictionary, we're going to discuss a lot about it in this video, in the future
videos. But for now, it's a fixed dictionary of
dimensions N by K, as we have seen in the previous slide.
Now, the model is extremely rich. Let's just do some numbers.
If we have a dictionary of size K, meaning K atoms, and we pick L.
We have L choose out of K possibilities. So if L is three we can pick any three
out of K. Once we pick them, each one of those
selections define a subspace, a very low dimensional subspace.
Once we pick, we do that selection, the signal, it's just a linear combination of
the corresponding atoms and that's a linear subspace.
But we have many of them. We have L out of K, a lot of them.
So the model is extremely, extremely rich and, hopefully, that will help us to
represent. Basically any signal of interest.
So, the model is simple, the model is very rich.
And also, the model is actually familiar to us.
This is not the first time that we see such a model of taking basically a signal
and representing it as a linear combination of a dictionary with only a
few atoms of that dictionary. Let's think for a minute, or for a few
seconds, when have we seen already this model?
We. Remember what we have learned in the last
few weeks. We have seen this model.
In JPEG. When, or how, in JPEG D.
Is basically the cosine basis. In JPEG we took and eight*8 block.
We did a transform into the cosine domain.
So d is the cosine basis. And alpha is basically the coefficient of
the cosine transform. And we saw that, for example, when we
quantize. A lot of the, these great cosine
transform coefficients became zero. So basically alpha was 64-dimensional.
But a lot of it was zero. So it was a very, very sparse vector.
And it achieved an extremely good representation of the eight by eight
patch. With just a few provisions, so JPEG is a
great example of the power of sparsity. Let me just give you another extreme
example of how we can represent signals in a very sparse fashion.
Consider that D includes all the signals of interest.
So if you're talking about images, this has huge matrix, K basically goes over
all the possible images. If that happens, then every time you want
to represent a signal x, an image. You only go and pick the corresponding
atom. The corresponding column in d.
And that means that our sparsity is one. So this extreme example is only to
illustrate that we can do sparse representations of signals.
Of course, it's not very practical; because imagine that you cannot put all
the patches or all the images in one dictionary.
That would be huge, and it won't be very useful.
The JPEG is, as we say, probably the most successful image processing algorithm,
and it's based on Sparse Representations. So, that's what we want.
We want to Sparse Representation of sigmas.
And the basic idea once again is that the signal is a linear combination of a few
atoms because alpha is sparse. How do we measure Sparsity, is the next
question? The way we are going to measure Sparsity
is with. This, which is called the LP norm for a
given P. Remember, alpha is nothing else than a K
dimensional vector. And what we are doing here with this formula is that we take
every entry of alpha, and we take the absolute value, and we elevate to the P
power, and we add all of them. And that's the LP norm of the vector.
Let's illustrate this for different values of P.
If p is equal to two, we don't really get what we want, because what we want is to
penalize. With an equal amount, every time one of
the entries of alpha is non-zero. And when it's zero, don't penalize at
all. So, that happens.
Zero, no penalization. But then the penalization increases
quadratically with actually demanding to lose the entry.
We don't want that. We want kind of an equal penalization.
As long as it's non-zero, it gets penalized.
What happen when P is equal to one. At least the penalization now is
proportional. Directly proportional and linearly
proportional to the magnitude of the entry, is not quadratic, that's better,
but doesn't look like it is good. We are going to see, later on that this
is actually a very good penalty function. This L1.
L for P = 1 It doesn't look like. But we are going to see that, under
certain conditions, this is exactly what we are looking for.
But before we get into that, let's keep looking for the ideal case.
If now, P becomes less than one, then we start to have what we really want.
A penalty of zero if the coefficient is zero.
And then the penalty starts to flatten out, meaning.
As long as the coefficient is non-zero, we get the same penalty.
If we further decrease p less than one, I'm getting close to zero, we get exactly
what we want. Zero penalty and equal penalty for
everybody that is non-zero. So the way we are going to measure
sparsity is with this function. For P equal zero.
And that's often written. As in this fashion with a zero here, and
a zero there. This is what's called a L0 pseudonorm.
It's not really a norm, and that's why it's called the pseudonorm, although very
often, it's called also the norm, with the understanding that it's not exactly a
norm, and this is how we are going to measure sparcity.
We are going to count the number of non-zero elements in the vector alpha.
[SOUND] So this is what we basically have here.
Signal represented as a linear combination of atoms from this, that
we're not allowed to pick more than l of those atoms.
So back to our problem of image denoising.
The Maximum-A-posteriori estimation of image denoising.
What we have, is that we want to represent our signal.
Very closely, this is the measurement and this is what we want to be.
We want to have a close representation, meaning very close.
X have to be as close as possible to Y as long as it belonged to the right model
and then we replace X by the alpha. Because we know that now we're going to
be representing the signal as. The dictionary multiplied by alpha that
not every alpha we basically must have the no more than L entries in alpha are
non zero. To give a.
Illustrative representation, and of course we get back.
The signal by the alpha, where alpha is the optimal.
So, in a, in a very simple pictorial representation, what we have is D alpha,
this is D, has dimensions N by K. This is alpha, that has dimensions K.
We'll subtract Y. That's aware approximation error.
But we are not allowed to pick any alpha. We're only allowed to pick alpha that has
at most L non-zeros, which means that we are going to be approximating Y by, at
most. L columns, the linear combination of at
most L columns of D. And from now on, the representation is
given by alpha. Instead of X we use alpha and we know if
we want to recover the signal we basically multiply by D.
Now what we have obtained is a very low dimensional representation of.
Our signal, and a low dimensional approximation of y.
And the idea is that, if we reduce the dimension of y.
Basically, we are getting rid of the noise.
Because we are not allowing to use all of the items.
We're only allowing to use very few, projecting the signal into a low
dimension. And therefore, reducing the noise.
It's the same as we saw with the points. We have points.
On the plane. That if we say that we are only allowed
to represent all these points with a straight line.
With feet of straight line and we're basically projecting the points onto the
straight line and by that we are denoising the points because we go into a
much lower dimension. In this case we just go from two to one,
but that illustrates the concept that we're going to a lower dimension of space
and by that we get rid of the noise. In order to represent the noise we will
need many additional atoms and that's why we are restricting alpha to be sparse.
Now. Are we done?
We are only at the very beginning of this week.
So for sure we are not done. Let me illustrate a few of the problems
that we need to still solve. Now.
We were talking about this, minimize the error under the constraint that you are
not allowed to pick more than L non zero entries in alpha.
Is this the problem we need to solve? Maybe we can solve it in this way.
Let us constrain here the error. You don't want more than the given error
and find the sparse's possible vector that achieves this error.
Or we can actually have a combination of the sparsity and error and try to
optimize for alpha such that it minimizes the sum of the two terms with a
coefficient lambda. So, we have three possibilities here.
Sometimes the three are equivalent. Sometimes they are not.
Which one shall we be using? Another problem.
In this case, a theoretical problem. Will we always find an alpha?
So, I give you a y. I give you a dictionary.
Will I be able to find, for example, an alpha that is sparse enough, and
represents this signal up to certain error.
Is that possible? And if I find it, will that be unique?
Will there be only one alpha? Will any alpha have the same support, the
same non-zero entries? When is that possible?
And of course what about a dictionary? Which dictionary should I use in order to
get alpha as sparse as possible? This is going to be something that we are
going to discuss quite a lot during this week.
And these are some of the questions these very nice sparse modelling and sparse
representations open. So what have we done?
We basically started with image denoising as an example and we say, we need to
model the signal, we need to understand what do we mean by image denoising, what
type of clean signal are we looking for. And that basically opened a question to
say, we need to define models. When we say we need to define models, we
basically. Describe a model, which is the sparse
model. The signal is a linear combination of a
few elements. A few atoms of a given dictionary.
Once we define that, are we done? Of course no.
We have all these questions that we just mentioned, theoretical, computational,
how do I compute that alpha and, of course, how do I compute a dictionary
that is appropriate for the type of signals that we are looking for?
So these are some of the questions that we are going to address during the next
few videos. And I'm looking forward to that.
This is, as I say, a very, very exciting topic.
And very, very active topic in image processing right now.
Thank you very much. Looking forward to seeing you in the next
video.
