3 - Hough Transform with Matlab Demo - Duration 20:59

Loading...

Do curso por Duke University

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

480 classificações

Duke University

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

480 classificações

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.

Na lição

Image segmentation

Not all parts of the image are the same, and students will learn the basic techniques to partition an image, from simple threshold to more advanced graph cuts and active contours. This is the first unit where student will learn about image analysis and image interpretation, and will learn why this is important, e.g., in medical imaging and object recognition.

1 - Introduction to Segmentation - Duration 04:174:17

2 - On Edges and Regions - Duration 05:175:17

3 - Hough Transform with Matlab Demo - Duration 20:5920:59

4 - Line Segment Detector with Demo - Duration 03:203:20

5 - Otsu's Segmentation with Demo - Duration 14:2514:25

6 - Congratulations - Duration 00:170:17

7 - Interactive Image Segmentation - Duration 21:1321:13

8 - Graph Cuts and Ms Office - Duration 09:349:34

9 - Mumford-Shah - Duration 05:505:50

10 - Active Contours - Introduction with ipol.im and Photoshop Demos - Duration 05:585:58

11 - Behind the Scenes of Adobe's Roto Brush - Duration 31:29 - Optional breaks at 20:30 and 27:2631:29

12 - End of the Week - Duration 00:210:21

Conheça os instrutores

Guillermo Sapiro
Professor
Electrical and Computer Engineering

Hello and welcome back, I want to talk now about a half transform.

The half transform is a really nice technique to detect objects, to segment

out objects, for which you know their shape.

Maybe a straight line, maybe a circle, as we have seen in the previous example.

For example we want to detect the ball. We know it's circular.

So can we include that information in our detection, in our segmentation technique,

to detect that it's actually circular? Can we use the information that we're

expecting here as a straight line, and basically get a straight line.

So the half transform allows to do that, and in a very simple and really, really

nice fashion. Let's illustrate that.

The basic idea is quite simple, and we're going to start with ideas on how to

detect straight lines, and then we're going to move to circles.

But starting with straight lines makes it much, much easier to understand.

In school I mean, probably in elementary or middle school you have learned how to

represent a straight line that is on a plane.

And I'm going to write down the equations and explain them to you again.

So here we have the plane. This is a image plane, the x y.

This is the image plane and we have points on a straight line on the plane.

For example this straight line might be this one or this one.

Now a straight line on a plane is represented, can be written down in the

following form. We have rho, and I'm going to explain

each one of these symbols in a second, is X cosine theta plus Y sine theta.

So rho is the distance from the coordinate system's center to the

straight line, and this should be perpendicular, of course.

It's a distance. Might be a bit tilted in the video, but

it should be, basically, a 90 degrees angle.

So rho is the distance to the straight line, and theta is this angle here that

basically is the angle with one of the axes. Let's pick this one in this case

with the line connecting test center with the straight line that we are

considering. So basically, every point that is on the

line holds this equation. Every single point, this one and this one

and every point in the line will hold this equation.

Using that, here is the idea of the half transform.

We take a point on the image and that comes from the edge detection.

So basically every point that the edge detector said, there is an edge going

through. For every point, we basically have an

infinite number of lines going through it.

This is one of them, with a particular rho and a particular theta.

Now, let's draw a different one. This line has its own rho and its own

theta. This will be rho, this will be theta.

We can go and draw a different line, all the lines going through the point.

See, here is another one. It has its own rho, here, and its own

theta. And we can keep doing that, we can pick

yet another one. For example, let us pick this one.

And, he had rope. And it has theta.

So, every point has an infinite number of lines.

And basically, every point will go and say, any of those lines is okay with me.

The point will go and vote for. Ro.

And theta for a series of them. It should be voting for an infinite

number but we're going to discrotize we're going to do this on the computer so

we won't be able to vote for an infinite number.

We're going to vote for discreet space of row and feta.

Now that's only one point and basically every possible line that goes through

that point will get one vote. Okay.

Now what happens with this other point? This other point has it's own lines that

go through it. So it's going to go and vote for it's own

lines. It's going to vote for this one of

course. But it's also going to vote, for example,

for this one. That has its own rho and its own theta.

And it's going to vote, and I don't want to draw too many, because it will make

the picture very unclear. But it's going to vote for another line

here and another line here and so on. So it's basically going to vote also for

a series of rho and theta. And all the votes will get one vote.

But look what happened. This line is common to both of them.

And we know that in Euclidean space through two points, there is a single

line. So there is only one line.

The one that we are looking for, that's going to get two votes.

Basically, and that will help us to understand what's the row and the theta

for this line. But of course not only two vaults,

because there's going to be another point here, that's also going to vote for a

series of rho and theta, but is going to vote for this one.

So this one is now getting three votes, one for each point that the edge detector

found, that is on that line.

now of course the edge detector might find points that are outside of that

line, and those will also make their own votes, but hopefully the only line that

gets a large number of votes is the line of interest.

So that's the basic idea of the Hough transform, and we're going to provide

more details in a second but every point that the edge detector find votes for the

possibilities, in this case, lines. If we have multiple points on the same

line, then we're going to have multiple votes.

So how do we do that in reality. So, in reality, we are going to go from

the XY coordinate system, which means the image coordinate system, to a new

coordinate system, which is theta and rho.

That coordinate the system, the same way that our image is discretized,

is going to be discretized. So theta can be anything around the

circle, and we basically discrotize as fine as we want or as fine as our memory

or our, our computational time allow us. Let's say we can discretize every one

degree. We do the same for rho, we discrotize it.

We know that row can not go further than the size of the image, so we know it's

bounded, and then we basically discretize it.

And then what we're going to do, let me write the equation again, with half the

equation, rho x, cosine theta plus y sine theta.

So what we are going to do is the following.

We go through every point, let's say this one.

So every point gives us x, y, the coordinates of that point.

Then we run through theta, and we say, let's say, one degree.

So we have the coordinate x and y. We put cosine of one, sine of one.

That gives us a rho. We go and vote for that one.

We, let's say, add one vote. This is sometimes called the accumulator.

And then we go ascertain, theta now equal two.

We have x, y. We define theta 2.

We have cosine of two plus sine of two. We get a new rho.

We go and vote for that one as well. And we keep voting for every single

point. Now it's not very hard to see that once

you fix x and y, if you vary theta as here, or as here, rho changes in a

sinusoidal fashion. So, that's very easy and it counts on the

cosine and sine. So your votes will look like a sinusoidal

function for every single point. Remember now when I go to a second point,

I will got, I will get more votes, a different sinusoidal.

So I will get different votes, and there will be a place, the place for responding

to this straight line, that is starting to accumulate votes.

Everything, for every point, we are going to have

that sinusoidal. We vote basically, on that sinusoidal,

and we start to accumulate. And now, the next step is to go into the

accumulator, and find the maxima. It may be multiple, if there are multiple

straight lines, but we go and find, and say, oh,

this is the rho and theta that many points like,

and that's how we detect these lines. So, let me just run you through the

pipeline again. You start from the image, and you do an

edge detection. Every point.

Some of them in the lines that you care about.

Some of them outside. Every point defines an equation like

this. Every point gives you the x, y

coordinates. So you go into the accumulator space, and

you vote sinusoidal votes. Or you just run through the thetas in the

discretized space and you vote for every rho that you get from this equation.

Every point a vote, then you finish, you basically say, lets go and look which

areas, which basically entries in my accumulator have enough bolts that means

that there is a straight line going through them.

Now this concept of voting goes very far, and you can actually do many, many things

beyond detecting straight lines. Let us show one example.

The basic, so here, we have four, five points, and then they accumulators so its

just going and you will see there is a straight line so there will be three

votes for that, and there is another straight line that will should be three

votes. Two votes, two votes, and so on.

For this very, very particular example, I just want to use it to show how we

basically get this sinusoidal type of votes for every point.

Now, let's see that on a real image. So what we see here is an aerial image

here. we clearly see that there is some

straight lines. This is the result of edge detection.

In particular, it's a canny edge detector.

Now, it's a bit confusing. From it, we want to get the parametrized

straight line. We want to go the rho, we want to get the

rho and theta for this one. This is the picture of this accumulator

that went through all these points. Now, you don't need to use all of them.

You can just sample some of them. There's plenty of points on this straight

line so you will get very high accumulator just by using a subset of

them. But, this is the result of the

accumulator. And then you go here and you look for the

maximum values. And from then you get the rho and the

theta that correspond to those maximum values.

Remember this is your theta, rho accumulator.

So wherever is the maximum, it gives you a value for theta and a value for rho,

and those corresponds to what we see here, and then you can put it back on the

picture and say, this is my most basically extreme line, my most prominent

line. Then there might be other maximal.

There would certainly be for this line, and this line, and this, and you can go

and pick all of them. In this case, we are only marking the

most prominent one, a very simple and extremely powerful technique.

I want to show you also how we do this for circuits but before that I want to

run this example in mat lab. Let's see that.

We're now as we said inside the mat lab environment.

And let's see the type of operations that we are going to do to illustrate the

Hough transform to the text trade lines. So there is a bunch of commands here but

I'm going to describe them to you. Most of them are just to make nice plot.

I'm going to describe to you those that are important, to understand what

basically the Hough transform is doing here.

So first, as we have seen many times in the past, we read the image.

This is the first operation. Then we're going to rotate that image.

This is just for the fun of it. I don't want you to believe that we can

only detect horizontal or vertical lines, so we're going to rotate that image.

Here, we do edges. Remember, the first thing we need to do

is detect the edges in the image. That's the input to the Hough transform.

And then here it is the Hough transform in MATLAB.

That would basically create this accumulator in the theta rho space.

And these are a bunch of operations, just to illustrate, to visualize.

We're going to run it in a second, I'm just describing the operations for now.

Then, the next, we need to detect the peaks.

We need to detect the maximal in the accumulator.

And that's this operation, and we're going to plot it.

Now we have the maximal, which means that we have the rho, and the theta and, we

need to detect the lines. We actually need to draw those lines.

And that's what this operation does, is basically finds the lines and then the

rest is going to draw them, and actually it's going to draw them as segments and,

with the images, I'm going to illustrate you how we do that.

So let's just run all these operations. and then just see the results.

So, here are the two images. As you see it's pretty fast, and we see

the original image. This is the accumulator, and here, the

squares, the wide squares are basically the peaks the, basically, the most

important maximal in the accumulator. And those are these green lines that we

see here. Once again in the accumulator, we have

rho and theta. Once we have that we can go back into the

image plain and draw the lines. Now you may wonder, but wait a second,

rho and theta would give us straight lines, but all across the image how do we

get to segments if we need to get to segments.

And the basic idea is that there are many ways of doing that.

But one way of doing that is you go and put the line back in the image as we have

here. And then you can go around that line and

see if there actual points in the image which were detected by the age detector

that voted for that line. And you basically can get what actually

was the real segment and not the whole line in the image.

That's just one way of doing that. And as we see here, we got this straight

lines. Very fast, and very simple operation to

get straight lines. There are others.

Just, their votes are weaker, and we need to decide to put a threshold in the

cumulator. We might put a threshold that says don't

give me any line that has less than certain amount of votes,

or we can say give me the ten top lines, give me the, the, the five top lines or

anything that is application dependent. So with this image and with this example

we see the whole pipeline. From the image, detect the edges, create

the accumulator, find the maximal,

draw up those lines back to the image. And if you need,

basically find the segments by looking in the image, where do you have actual

points that voted for that, if you need just the segment.

So now we're going to go back and I'm going to describe what we do for circles.

What about circles then? So here we have an image of circles and

we are going to know if we can basically find the circle using the half transform.

The idea is exactly the same. Now a circle can be written down in the

following form. X minus X zero, that's a X coordinate of

the circle. Square plus Y minus Y zero squared equal

to the radius squared so, every point in the circle holds this equation where the

center of the circle. Is given by this and this.

These are the coordinates of the center, what we need to find.

And the radius of the center, which is also an unknown.

It's given here. If you don't remember this formula, just

pick any of the elementary geometry books, or just believe me that this

formula is the right formula for a circle on the plane.

Now in the same way that we need rho and theta for straight lines, we need to find

the center and the radius for a circle. So we need one.

To three parameters. So now accumu, our accumulator won't be

on the plane. It will be a 3-dimensional accumulator,

but we're going to do exactly the same. We're going to have an edge detector.

Every point is not a vote for a circus every point is going to give us.

Its coordinates. And then we are going to run through the

accumulator on the X coordinate of the center, the Y coordinate of the center,

and get the radius. So we are going to run through that,

through the Xs, run through the Ys. And then, get the radius.

We accumulate, we pick the maximum one, and we basically are done.

We got our center and radius. So, let us see this straight one example.

Here we have the edges and I want to repeat that once again.

Every point here will vote for multiple centers, multiple radius.

We can of course limit the centers, because we know the dimensions.

We can also limit the votes for the radius, because we also know how large

the objects can be in the image. We are going to vote for that.

There are going to be multiple votes for the real circles in the images and then

we basically detect them and here they are.

We basically went through that cummulator, and find the top votes.

And we get out results. Basically the Hough transform can be used

for any parametric curve. Anything that we need to vote for some

parameters of that curve. As rho and theta, the centers we can find

parabolas, we can find any, any curve that we can write with parameters.

The more parameters you have, the more expensive the Hough transform is.

So normally, the Hough transform is used for finding straights line, circles,

ellipses, relatively simple objects that have a

controllable number of parameters. Otherwise, your accumulator space is

huge, takes a lot of memory, and takes a lot of computational time, both to

compute it and to find the maximal. But for those simple shapes, there's,

one of the best techniques out there is the Hough transform.

So I hope you enjoy this video and I'll see you in the next video.

Thank you very much.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play