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.