Hough transform is used to detect the presence of certain models in an image, for example lines, circles etc… Fitting was used before Hough transform and it has some limitations, for example if the edge of the object i am trying to detect is noisy or is missing some points.
Hough Space
Hough space is characterized by the parameters of the object we want to detect, let’s say we want to detect a line, straight line’s equation is $y=mx+b$$, then Hough space has two axis for m and b. This is generalized for all models.
Line fitting
If we have a line in image space it represents point in hough space. What about a point in image space, it is represented by line in image space.
in\space hough\space space$$
![[Pasted image 20241124170240.png]]
### How can we detect a line
Let's say we have multiple points in image space and we want to fit a line that passes through them. Each point in image space represents a line, and the line that passes through these points has the parameters at the intersection of the all the line that represents the points in hough space.
But what if the they don't intersect at a single definite point, maybe there is a really small deviation between the points and the closest fitting line, what should we do ?
## Voting
Hough transform after all is a just a voting technique for features, the best way to think about it is as following, a point in image space **votes** for the line parameters that pass through it. The line that this point represented in Hough space are the votes for the parameters of the line that my pass through this point, like to get more specific that point votes that $b_{0}\space \&\space m_{0}$, $b_{1}\space \&\space m_{1}$, $b_{2}\space \&\space m_{2}$, and so on pass through this point. When multiple points accumulate points in a certain position that means the the line that passes through all of them have the parameters at the intersection point.
## Bin voting
When the line don't really intersect at a single point we divide the space into small bins - characterized by some parameters - and the bins that have most number of votes, mean that the the closes fitting line that passes through the point in image space has the parameters of the bin.
Choosing an appropriate bin size is a little bit tricky, since increasing the bin size will lead to decreased accuracy and increased error margin, but is also less prune to noise. The opposite happens when we choose a smaller bin.
## Polar representation of lines
I can represent a line with with its distance from the origin and the angle of the line that connects to it. We do this representation because vertical line can not be identified due to infinity y intersection.
![[Pasted image 20241124171934.png]]
Now we have Hough space with the parameters $\theta, d$
>**NOTE:** If we interchanged our axis then the line equation will be $xcos(\theta)+ysin(\theta) = d$
Example:
![[Pasted image 20241124172123.png]]
There is also polar representation for circle modelling ant it goes by:
$$a=x+rcos(\theta),\space b =y+rsin(\theta)$$
Where $x$ and $y$ are the points that the circle passes by, and $\theta$ is the angle between the perpendicular to the tangent of the circle at $(x, y)$ and the x-axis.
>**NOTE**: In the problem if you were given the gradient at the point without any information, most likely you will use the polar form.
## Algorithm for Hough
![[Pasted image 20241124172300.png]]
I don't what is the time complexity thing.
An extension for Hough algorithm. In this extension we don't really use all the possible $\theta$ points, we only the gradient, since most likely the line that we are trying to model is an edge and its normal is the gradient direction, because again it's an edge.
![[Pasted image 20241124172428.png]]
## Hough transform for other shapes
We can also use hough transform for other objects, for example circles:
$$ (x - a)^2 + (y-b)^2 = r^2$$
If we are a fitting circle with a constant radius then the Hough space will have only a and b axis and a point in image space will represent a circle in its transform. If we are looking for circles with variable radius then Hough space will be three dimensional and a point will represent a cone.
## Hough transform for general object
If we want do detect a general model in image space, we get every point in the model and get its gradient direction and then choose an arbitrary reference point in the middle of the model, we then connect every point to this reference point and save in a look up table the gradient of the point and magnitude and the direction of the vector that we connected from the point to the reference point.
![[Pasted image 20241124173201.png]]
During detection we get the gradient of every point an draw the same vector again, and the point the vector stops at is considered a vote, the more votes at this point means we may have detected the object.
## A question that was in the section
In 2, the current algorithm does not, but by modifying it that it takes into consideration different rotation in the gradient and and the vector r, either by mapping it then yes. The same in 3, our current implementation no, but by modifying that we take into consideration different scales for the vector r.
## Pros and cons
![[Pasted image 20241124173341.png]]
And that algorithm can be implemented as a parallel algorithm which is good.
If we have a line in image space it represents point in hough space. What about a point in image space, it is represented by line in image space.