Week 3 - Hough Transforms Flashcards
How do we rearrange a line equation for hough lines
To c = -mx + y
We can then plug in (x,y) values to find where all the possible lines that cross through these x,y values
can find a (x,y) where they all cross and get the line equation from it y = mx + c
How do we find hough line intercepts programmatically
With the same c = -mx + y equations
Create an accumulator array of m going across, c going down
1) all values initially 0
2) plot each equation into the array using 1s to show it is a point on a line
3) when two lines are plot at the same point, increment (says 2 instead)
4) choose the entry with the highest value - we can decide on threshold value; minimum no. of points that we will consider a valid line
Put coordinates back into y = mx +c
What happens in the array if the line is vertical
m = ∞, line has an infinite gradient and the array cannot manage this
What is the polar equation for r
r = x cos(θ) + y sin(θ)
How do we set up an array using polar coordinates
theta along the top, r going down
Use the same method of incrementing interceptions
What happens to theta after reading it from the array
θ = 45* corresponds to the line θ = -45* because our array actually gives the angle from the normal (+ve x axis) clockwise through to our line which is actuall -ve
How do polar coordinates handle vertical lines
They wont read the gradient as infinity, just an angle θ=90*
Why are hough lines useful
Edge points are identified using techniques such as gradient-based methods (e.g., Sobel operator) or thresholding
We then create hough lines from these points and add them to an array
Peaks in the accumulator array correspond to potential lines in the image space
Why are hough circles useful
Help us detect circular images: car wheels or biscuits in an image
What is the equation of a circle
r² = (x - a)² + (y - b)²
From the equation of a circle, what is the centre coordinates
(a, b)
How do we rearrange the equation of a circle for a hough circle
(a - x)² + (b - y)² = r²
How do we find hough circle intercepts programmatically (fixed radius)
Use an accumulator array for a and b (a is horizontal)
Draw each circle into an array
Eg for point (2,3) a circle with fixed radius is drawn with centre at (2,3)
Increment each intercept
Highest value represents the circle centre (a,b)
What happens if the hough circles do not have fixed radii
Need a 3D accumulator array for a,b,r
What do bright points represent in detection images
a circle centre is correctly detected
play around with different r to find more bright points (more circle centres)
What is the generalised hough transform
Used to find other shapes (not just line and circle)
Like hough lines and circles, the generalised transform uses edge pixels to find contours in an image, but then uses edge directions as well (derived from the grey levels at each point)
What is meant by generalised hough transform has ‘no shape’
We describe the image we are looking for in the image, and it can be any sort of shape
How do we model a template shape with fixed orientation and size
1) Choose the centre point within the shape (xc, yc) and a point on the contour of the shape(x,y)
2) xc = x + r cos(α)
yc = y + r sin(α)
3) We find the normal φ to the tangent at (x,y)
And compare it to α
4) If the gradients are the same, x,y is a candidate point for the shape contour
How do we model a template shape using an R-table (fixed orientation and size)
1) For every contour pixel in the shape, the edge gradient φ is found and (r,α) calculated and appended to the table
2) Using these (r, α) pairs, a potential shape centre (xc, yc) can be calculated:
1. xc = x + r cos(α)
2. yc = y + r sin(α)
3) create an accumulator array with xc and yc axes
4) For each edge pixel and its calculated xc and yc, (from φ and (r, α)) the, the entry is added to the array
5) As before, a threshold can be set to how many increments before the point is considered correct
What is an R table
Essentially a lookup table
Consists of a range of edge angles φ at some resolution (resolution 1 means at each degree 1, 2, 3, …180)
Each entry in the R-table holds an edge angle φ and its corresponding (r,α)
How do we find a template shape at any scale s and orientation θ
Use an R-table again
A 4D Accumulator Array is required A(xc,yc,s,θ)
Using these equations:
xc = x − (a cos(θ) − b sin(θ))s
yc = y − (a sin(θ) + b cos(θ))s
s and θ are varying scale and orientation
