Set-Theoretic Restoration Approaches

Loading...

From the course by Northwestern University

Fundamentals of Digital Image and Video Processing

657 оценки

Northwestern University

Fundamentals of Digital Image and Video Processing

657 оценки

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.

From the lesson

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.

Examples of Image and Video Recovery 26:28

Image Restoration 15:43

Matrix-Vector Notation for Images 24:32

Inverse Filtering 13:14

Constrained Least Squares 25:32

Set-Theoretic Restoration Approaches 9:28

Iterative Restoration Algorithms 13:06

Iterative Least-Squares and Constrained Least-Squares 19:07

Spatially Adaptive Algorithms20:37

Meet the Instructors

Aggelos K. Katsaggelos
Joseph Cummings Professor
Department of Electrical Engineering and Computer Science

We present in this segment a general framework for solving estimation problems.

Like the recovery problems we're addressing during this and next week.

The framework is rather intuitive and quite powerful.

And it has been applied towards

the solution of various signal estimation problems.

Of course, we apply it here specifically to the image restoration problem.

According to it, we are interested in estimating a

signal that belongs to a number of sets of signals.

Each set represents the collection of signals that possess a certain property.

For example, can define the set of all smooth images or

the set of all images that only accept non-negative intensity values.

Which is a very reasonable request given the nature of light.

If the sets are convex, then the problem we are asked to solve is simple.

One way to obtain a solution in later section of the sets, assuming

it is not empty, is to alternate or [UNKNOWN] projections onto these sets.

It's a rather intuitive and smart framework, as we will see.

I would like to briefly discuss another approach

towards solving recovery problems or estimating a signal.

Under the name of Set Theoretic Approach.

And you'll see that, if we apply to

the specific problem at hand, the image restoration problem.

We can come up with another version of the constrained least squares filter.

This approach is rather intuitive.

According to it, we are looking for a

signal, an image, but has a set of properties.

So, each property defines a set, such as the one shown here.

So, all the signals, all the images that

belong to this set, have a specific property.

The set of signals have the second property we're

interested in define another set, such as this one.

And there could be a third, a fourth property and so on.

So for the problem at hand, the image restoration problem, the example of

the first set is a set of signals that satisfy this inequality here.

So this is the set of the images that have high

frequencies, that have energy at the high frequencies, less than absolute squared.

Says again, a high-pass filter and therefore

this is the energy of high frequencies.

And this is the smoothness constrained, as we explained earlier.

So all these signals that belong to this set are smooth.

By the way, this set is shown as an ellipse here in

the n dimensional space is an ellipsoid, the generalization of an ellipse.

And is therefore a convex set, an important property of such set.

The second set you can define based on our restoration problem is, is shown here.

So, it's the set of images that have this difference y minus Hf being

less than E squared and this is the fidelity to the data constraint.

So, we are looking for an image that has both of

these properties, it's smooth and satisfies the fidelity to the data.

Therefore, we are looking for an image that

belongs to the intersection of these two convex sets.

And this intersection is going to be convex as well since the sets are convex.

So this is the general setup of a set theoretic approach.

And the question now is, how can one obtain

a solution in the intersection of these two sets.

By the way, these two sets, may have a non-empty intersection, or may not.

So typically, after we find the solution, we do a posterior test.

And we test if, indeed, the solution satisfies both constraints.

Belongs to both sets, as we would be interested in.

So, one approach to find the solution is to

bound the intersection by another ellipsoid, as shown here.

And choose the center of this ellipsoid,

of this bounding ellipsoid as the solution.

We'll see that this approach can result in a constrained least squares filter.

So I have again two sets, a set C 1 and C

2, each of them represents a set of images with desirable properties.

They intersect, C 0 is the intersection of the two sets.

And I'm interested in finding a solution in the intersection of the two sets.

An intuitively, very clear approach is to

utilize projections onto convex sets, Approach algorithm.

So according to it, I start from an arbitrary initial condition

f 0 and I project image of 0 into the first set.

So there's the projection P1 on set C 1 of f 0.

Then I take this point and project it onto the second set.

So this is now the projection two, one to set two,

on the set C 2 of the point P1 of f 0.

And they call this f 1.

And I keep repeating this process.

I now take this point, project it to C1.

And then, I'll take it and project it back to C 2 and so on.

So, the theory tells us that, in general, if I have m, such convex sets.

If I repeat this projection onto

convex sets or alternating projection algorithm, right.

I start with an f 0 arbitrary and project onto the first, the second, the m set.

This gives me the new update, f of k minus 1 becomes f of k.

And they keep repeating this way.

Then, in the limit, after so many iterations.

The solution of star here is going to be in

the intersection, C 0, of this m, in general, convex sets.

So this should be a very, again, intuitively clear algorithm.

Of course, these projections, depending on the description of these

sets, might be a rather straightforward way to find these projections.

Or it might be terribly com, complicated.

So the theory of, set theoretic estimation following

then any of the two solution approaches I mentioned.

Has been applied to a number of problems successfully.

And if I apply it now to the restoration

problem at hand, I will see what expressions we obtain.

[SOUND]

So for the image restoration problem, we're looking for

an image that belongs to both of these sets.

This is the set that represents the [UNKNOWN] to the data.

And this is the set that represents the smoothness constraint.

So according to the first approach we discussed, we'll

find a ellipsoid bounding the intersection of these two sets.

And then it can be shown that the center of

this ellipsoid, the bounding ellipsoid, is given by this expression.

So this is the expression for the

constrained least squares filter that we derived earlier.

The difference being that now the

equalization parameter alpha is given to us.

Because we assumed that we know this two bounds E and epsilon.

It should be clear that by picking E and

epsilon a certain way, these two sets may not intersect.

If they both are, for example, chosen to be very small.

And therefore, I need to check if indeed this solution I

find, it belongs to both of these sets that it should belong.

The second approach we discussed is the projection onto convex sets.

So if I follow this, I have two sets.

The first one is set one.

So, this is C 1.

This is C 2.

And

this is the projection of f of an f of an

image onto the first set P 1 is given by this expression.

And lambda here needs to be chosen appropriately.

Soo that P1f belongs to set C 1.

Or another words, P1f satisfies this first expression.

It is the projection of the second set, the set of smooth images.

And similarly lambda 2 needs to be chosen

appropriately so that p2f belongs to the second set.

So it keep alternating the projection so to this two

set I'm going to converge to a point in the intersection.

So again this is a specific application of

this set's theoretical approach to the image restoration problem.

However now that hopefully you do, have a grasp of the basic idea.

You can search and see that this approach, estimation approach,

has been applied to the solution of additional problems of interest.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play