5 - Sparse Modeling Image Processing Examples - Duration 20:57 - Optional break at 09:25

Loading...

En provenance du cours de Duke University

Image and Video Processing: From Mars to Hollywood with a Stop at the Hospital

419 notes

Duke University

Image and Video Processing: From Mars to Hollywood with a Stop at the Hospital

419 notes

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.

À partir de la leçon

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.

1 - Introduction to Sparse Modeling - Part 1 - Duration 10:3910:39

2 - Introduction to Sparse Modeling - Part 2 - Duration 18:1618:16

3 - Sparse Modeling - Implementation - Duration 24:30 - Optional break at 11:5824:30

4 - Dictionary Learning - Duration 17:13 - Optional break at 06:0317:13

5 - Sparse Modeling Image Processing Examples - Duration 20:57 - Optional break at 09:2520:57

6 - A Note on Compressed Sensing - Duration 05:105:10

7 - GMM and Structured Sparsity - Duration 15:4015:40

8 - Bonus: Sparse Modeling and Classification - Activity Recognition - Duration 15:1015:10

Rencontrer les enseignants

Guillermo Sapiro
Professor
Electrical and Computer Engineering

Hello, and welcome back. It's time now to present examples of

sparse modeling in image processing. Before we do that, we have to do one more

thing. Now, remember what we have.

We have a dictionary of K elements, K atoms, and every atom has N dimensions.

Now, what are basically the, basically the signals that we are going to process?

And that's what we need to discuss just for one minute.

And the basic idea is very simple. We're going to be talking about images.

This is going to be our data, the noisy image.

The whole image. This is what we are looking for.

Now, we are not going to work on entire images,

we are going to work on patches. And this is the r.

The r is just a basic, a simple binary matrix that extracts the patch around ij.

So, if we have an image, for every pixel, we construct a patch around it.

Or, we could actually consider ij the upper left corner.

Anything that is good as a coordinate system, and we extract patches.

For example, eight by eight patches as we have been talking.

Now, it's very important that we do not take blocks as we did on JPEG, in JPEG.

We actually take all the patches that are fully overlapping.

So, we have an image, and we take a patch, and we take the

patch next to it and the patch next to it.

So, for every pixel, let's say the upper left corner,

we construct the eight by eight patch. So, this is a binary matrix that extracts

that patch. And it's the patch that we want to have a sparse code for it with a

learned dictionary. So here is the sparsity.

So, we're not working on the whole image at once, we're working on all the

overlapping patches of the image. And, what we have is as we discussed

before, the model is for the individual patches.

We're going to construct a dictionary that works, for example, on all the

overlapping patches of a given image at the same time.

And note here, we are doing basically the optimization over the signal, this is the

whole image. We are looking for the sparse code,

this is the second part. And as we're going to see in a second,

we're also going to learn the dictionary. We could learn the dictionary offline or

we could learn it and adopt it for the image as we're going to explain.

Once again, this is just nothing than a binary measure that extracts the patch.

So think like you have the image, you pick a patch,

you do sparse coding. You pick the next patch,

you do sparse coding. Now, what about then the dictionary?

The first option is to train on a large database.

So, you do that offline you train on a large database.

The second option, and these are not contradictory as we're going to see in a

second, is to use the image itself. You travel all around the patches of the

image, that gives you a lot of training data already.

And the basic idea is that normally we combine both of them.

That's one possibility. So, you learn a dictionary with a bunch

of images off the shelf offline, and that you use as your initialization of the

dictionary for K-SVD, and then you get the new image.

Even though it's noisy, you adapt the dictionary to the image.

So, you run a few iterations of this dictionary adaptation, K-SVD, sparse

coding, dictionary adaptation, sparse coding for the particular image.

That's one option. The other is to forget completely about

this and start with any visualization and only run it here.

So, there is many options and, depending on the application, which one you can

pick. Now, if you are in a rush and you don't

have computational time to do the de-noising, you don't have to update the

dictionary. Basically, you train it with a database.

Let's say, that you want to do faces, you train it with a database of faces and you

use that dictionary. If you have computational time to do

that, it's always better to basically adapt the dictionary to the particular

image. And we have tons of data for that because

we can use all the patches for doing that.

So, once again, this is our general formulation but now we have D either

because we are starting from scratch for the particular image or because we are

adopting the pre-learned dictionary to the current image.

We have to, this is our data. And we have to, basically reconstruct the

image, we have to compute the code, we have to compute the common dictionary,

one dictionary for all the patches in the image.

We are not allowed to use a dictionary per patch,

that would be basically ridiculous. So, we have three things to optimize for

and the basic idea is very simple. You fix two, you optimize for the third

one. For example, you fix,

you ignore x and basically you assume that x is fixed.

So you ignore this term, and you fix D, and you do sparse coding.

That counts the first part of K-SVD. Then, you fix the code,

and you update the dictionary. And this is basically an iteration that's

basically K-SVD. So, you have the image, you go over the

patches. Every patch becomes the columns of the

large x matrix that we saw in the previous video.

And then you do K-SVD for all of them, okay?

So you are encoding with sparse coding every patch.

When you're finished, you update the dictionary, you encode again, you update

the dictionary. When you are done with the dictionary,

all that's left is to compute x. So, you basically don't touch the code

anymore, don't touch the dictionary anymore.

And you have to basically solve for this problem when basically D and alpha are

already fixed. Of course, this is gone.

x only shows up here and shows up here, and is very easy to show that the result

is basically the weighted average of the patches.

So what happened is that every pixel is touched by multiple patches.

So let me just draw that here, for example.

We have an image, and we have a pixel.

Now, there are multiple patches that touch that pixel.

For example, this one that has the picture kind of the, pixel, kind of the,

on the bottom left corner. There is also this one.

basically there is also let me just use the different color, there is for

example, a patch here. There is how many?

If we have eight by eight, we have 64 patches that are touching that pixel,

unless the pixel is at the border of the image.

Let's ignore those for a second. And basically, for everyone of those

patches, we have sparse coding with the dictionary that we have learned from all

the patches in the image. So, that sparse coding, basically for

every single one of these patches is that we can reconstruct it as the alpha with

the optimal alpha that we have compute for every single of the patches ij.

Every single one has been reconstructed. How do we reconstruct the pixel?

We basically average all those patches. You can add weights to the average.

What's basically what the theory tells you.

If it's, the pixel is in the center of the patch, then that patch is more

important than if the pixel is in the corner of the patch, but that's just a

technicality. You can basically just do the

reconstruction of every patch with the sparse code and the dictionary that we

have learned and just average those 64 if you're using an eight by eight block.

So now, this is all what you do. Every patch sparse coding and K-SVD to

learn the dictionary. So, I think we are ready now to see

examples. Let's start from a image in gray values,

no color. This is the source image, and this is a

noisy image. We have add, we have added Gaussian noise

with these variants. Now, we can initialize the dictionary

with random patches from this image. We don't have this image anymore.

This is just for reference. This is all what we have.

We can initialize with patches from here. We can initialize with a dictionary that

we have learned offline, or we can initialize with something that

we know is good, Discrete Cosine Transform Dictionary.

That's the one used in JPEG. So we know it's reasonable a good

algorithm. So a, a good dictionary.

In this case, we have initialized with that.

And basically, we update using all the patches here all the possible patches.

We learn the dictionary, then we encode every part with the

learned dictionary using sparse coding. Then, we average all the patches that

touch a given pixel. And voila, this is the dictionary that we

have learned. Very interesting how it has changed from

the [UNKNOWN] dictionary. And here is the restored image where we

basically have reduced the noise by two things, one projecting every patch to the

space defined by these dictionary using sparse coding, and then averaging the

purges. And here you have a result.

This was the original, this is what's available to us, and this is the de-noise

data. Very important that the adaptation of the

dictionary is down with the noisy data and still the results are really, really

good. And I want you, once again, to observe

the type of dictionary that we have learned from the image.

For example, it has learned that texture that we have here, the different types of

texture, are learned in the dictionary. It was basically adapted to the image.

Now, how do we deal with color? There are numerous ways of dealing with

color, but basically one of the simplest ways is to, instead of doing eight by

eight patches, we do eight by eight by three.

We could have done every color independently, as we have done for

example, for in painting or even for compression.

But we can also take eight by eight by three patches.

You know, we concatinate all the colors and we do K-SVD sparse modeling in

exactly the same fashion. Let's see some results. So, again, we

always show the original just for reference because you never have it.

What you have is this image, this is noisy image.

A noisy version of this. And then, you run K-SVD on this eight by

eight by three or five by five by three, depending on the patch size that you

decide to use, and you get a very nice result of image

denoising. And here are just the, basically, the

standard measurements of, of p, K's and R in DB's to measure just the quality of

the result. Here is another example.

We start from again the reference. This is only for reference, the original

image. We have noises.

Look how bad it is. This is really bad.

We have added a lot of noise and we get a beautiful reconstruction from this sparse

modelling technique. Really, really nice reconstruction with a

lot of details and a relatively high quantitative measurement.

Although, what's most important is the qualitative quality of the

reconstruction. So, we went from here to here.

And once again, we learn the dictionary. In this case, we initialize a dictionary

with an off the shelf pre-learned dictionary, and then we adapt it to this

noisy image for a few iterations of K-SVD.

Now, we can also do inpainting with this.

Inpainting is a particular example of noise where the noise is kind of so

strong that it makes some pixels disappear. And, there's many ways of

defining the types of challenges of inpainting.

One of them is to take the image and to just drop 80% of the pixels.

This is related to compressed sensing, and we're going to talk about that at the

end of this week in just one video. we basically drop 80% of the pixels.

You say, you're gone. So that's basically represented here with

dark values zero. So it's like, the noise is so strong that

you, basically there's nothing there. And then you run basically sparse

modelling and K-SVD starting with this image, this is the missing part.

We start from this image and here is the reconstruction.

Once again, a very, very interesting result.

We only had 20% of the pixels and we managed to do a nice reconstruction.

Again, we go from here to here. This is just for reference, this image.

Let's just see that in color. Again, 80% missing and here is the

reconstruction. Once again, I think a very, very nice

result. Again, for this example, we started with

a dictionary that was learned from a database of natural images, then we adapt

it to this image for a few iterations. And then, we do this by reconstructing

every patch and then averaging for every pixel all the patches that touch it.

Again, I think a very impressive result showing the power of this technique.

This is another example, instead of dropping the pixels, we do the same that

we did when we were talking about inpainting in general.

We write on top of the image, and then we do the reconstruction.

Again, very good results with nothing else than doing sparse modeling, learning

a dictionary from this noise image and being able to reconstruct this image.

Now, we can also do video inpainting. We can drop 80% of the pixels.

And now, again, we have a number of options.

We can do every frame by itself, or we can do patches in kind of three

dimensions, X, Y and T.

We discussed about that when we were talking about video inpainting in the

previous week. Basically, we take patches, let's say, we

take three frames together, five frames together so the patches have also some

temporal information. After we have decided what type of

patches to use, we run sparse modeling with absolutely the same technique that

we have been describing. And I'm going to run a few of them.

The original is as always, only for reference.

It actually is not available. We always go from here to here doing the

dictionary learning. Let me run a few frames.

This is one frame, this is another frame. Look always at the quality of the result,

the reconstruction. Another one.

Another one. So once again, we basically walk through

the different frames going from this to this.

And you can always look at the reconstruction is very, very close to the

original that is not available to us. Just one more frame here.

Now, I want to do an, yet another frame. I want to finish with demosaicing.

This would be the last example. It's kind of a particular case of image

inpainting as we have seen before. Let me explain what's the problem here.

Most digital cameras do not collect full red, green, and blue.

They basically do a trick which is, one pixel, they collect ren, red.

The next, they collect green, the next, red, the next green, and so on.

For the next role, they collect green, blue, green, blue, green, blue, and then

they repeat that. So, at every pixel, they have only one

color. Red, or green,

or blue. And what you have to do is you have to

interpret. In order to show me the image, you have

to, at every pixel, create a red degree and a blue.

This is kind of an interpretation or an inpainting of the colors.

But, we can treat this as nothing esle than inpainting of the colors where

basically we have just, instead of dropping the entire pixel, we drop two of

the colors of the pixel per pixel. Sometimes we draw up the red and the

green. Sometimes we draw up the green and the

blue. Sometimes we draw up the red and the

blue. So imagine that you have a queue which is

n by n by three with sometimes is, you have it available and sometimes you

don't. Now, we have seen that sparse modeling is

extremely successfully even when the entire pixel is gone.

Even when 80% of the complete pixels are gone.

So, let's run it on this. And this is called demosaicing.

It has to be done basically in all consumer digital cameras.

Very expensive digital cameras actually collect the full red, the full green, and

the full blue. But, normal consumer cameras do this type of mosaic and then

the production of the full color image is called demosaicing. And here you see

examples of color images that have been reconstructed from patterns like this

using sparse modeling. It's a particular case of basically

inpainting in the color domain. It's even easier than that, because

instead of dropping entire 80% of the pixels, you just drop some of the colors

per pixel, and the results are really, really nice results.

We have, basically, some zooming, and you can see that the results are very, very

sharp. And these are really some of the best

results produced with, for demosaicing. They're obtained with sparse modeling

techniques. So, these are just some of the examples

of sparse modeling. Sparse modeling in image processing is

being used a lot these days, also for image classification and other image

processing challenges I have shown you for denoising, inpainting, demosaicing.

And I think that this basically illustrates the importance of the theory

that has a lot of mathematical components.

And basically also very, very cool applications.

We have a couple of additional things to learn this week about sparse modeling and

also about compressed sensing, and the connections between the two, and I am

going to do that in the forth coming videos.

Thank you very much, see you later.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play