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.
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
422 classificações
Duke University
422 classificações
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.
Conheça os instrutores
Guillermo SapiroProfessor
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.
© 2018 Coursera Inc. Todos os direitos reservados.
