Week 3 - Hough Transforms

Question 1

How do we rearrange a line equation for hough lines

Answer 1

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

Question 2

How do we find hough line intercepts programmatically

Answer 2

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

Question 3

What happens in the array if the line is vertical

Answer 3

m = ∞, line has an infinite gradient and the array cannot manage this

Question 4

What is the polar equation for r

Answer 4

r = x cos(θ) + y sin(θ)

Question 5

How do we set up an array using polar coordinates

Answer 5

theta along the top, r going down
Use the same method of incrementing interceptions

Question 6

What happens to theta after reading it from the array

Answer 6

θ = 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

Question 7

How do polar coordinates handle vertical lines

Answer 7

They wont read the gradient as infinity, just an angle θ=90*

Question 8

Why are hough lines useful

Answer 8

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

Question 9

Why are hough circles useful

Answer 9

Help us detect circular images: car wheels or biscuits in an image

Question 10

What is the equation of a circle

Answer 10

r² = (x - a)² + (y - b)²

Question 11

From the equation of a circle, what is the centre coordinates

Answer 11

(a, b)

Question 12

How do we rearrange the equation of a circle for a hough circle

Answer 12

(a - x)² + (b - y)² = r²

Question 13

How do we find hough circle intercepts programmatically (fixed radius)

Answer 13

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)

Question 14

What happens if the hough circles do not have fixed radii

Answer 14

Need a 3D accumulator array for a,b,r

Question 15

What do bright points represent in detection images

Answer 15

a circle centre is correctly detected
play around with different r to find more bright points (more circle centres)

Question 16

What is the generalised hough transform

Answer 16

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)

Question 17

What is meant by generalised hough transform has ‘no shape’

Answer 17

We describe the image we are looking for in the image, and it can be any sort of shape

Question 18

How do we model a template shape with fixed orientation and size

Answer 18

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

Question 19

How do we model a template shape using an R-table (fixed orientation and size)

Answer 19

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

Question 20

What is an R table

Answer 20

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,α)

Question 21

How do we find a template shape at any scale s and orientation θ

Answer 21

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