Generalised Hough Transform - Lecture 6 - Week 3

Question 1

Why can the laplacian not be as good as the Laplacian-gaussian?

Answer 1

Finds lots of other things as well as edges

Question 2

What is the hough transform for?

Answer 2

Finding lines through points

Question 3

What is the formula rearranged for hough

Answer 3

y = mx+c -> c = -mx + y

Question 4

What is the hough parameter space?

Answer 4

c = -mx + y

Each possible line through a set of points can be represented as a single point in hough space

Question 5

Convert (-10,10) in cartesian space to a line in hough space

Answer 5

-10 = -m*-10 - 10
c = 10m - 10

Question 6

How is a point in Hough space picked to go through as many cartesian points as possible

Answer 6

The cartesian points are expressed as lines in Hough space, the point where the largest number of lines in Hough Space intersect is the line that goes through the most points in Cartesian space

Question 7

How is a point in Hough space picked to go through as many cartesian points as possible created programmatically?

Answer 7

By using a discrete table of values.
An accumulator array (big box) is made, with m and c values as columns and rows respectively, m is incremented over and the corresponding value of c has it’s row and column value incremented by 1.

There is a threshold for the number of intersections required to be considered a line through enough points.

Question 8

What is the problem with Hough Transform and cartesian coordinates?

Answer 8

If a line in the image is vertical m = infinity

So we use polar coordinates instead, by plugging our points into the equation of a line in polar coordinates and calling this our hough space (with theta and r) then sampling those lines in the same way as the previous cartesian hough space

Question 9

What is the equation of a line in polar coordinates?

Answer 9

r = xcos(theta) + ysin(theta)

Question 10

What are the parameters for the OpenCV HoughLines function and what do they mean

Answer 10

rho - resolution for r – how many rows are in the sampling matrix

theta - resolution for theta – how many columns are in the sampling matrix

threshold - Decides how many counts (votes) in our matrix we want to consider as a valid line might be hundreds or thousands depending on the resolution of the image

Question 11

How can we find circles through points instead of lines using Hough Transforms?

Answer 11

By using the equation of a circle (x-a)^2 + (a-b)^2 = r^2
In the “Hough” space the parameters become a and b, a constant value of r is used.

So for a point at (x,y) in image space, in parameter space a circle around the point of radius r exists

To find circles of different radii we need a 3D accumulator array with a, b and r as parameters

Question 12

What is the generalised Hough Transform?

Answer 12

Used to find arbitrary shapes in the image space, the algorithm mathematically calculates it

Question 13

How does the generalised Hough Transform model the template shape?

Answer 13

Choose an arbitrary point within the shape (xc, yc) this is the reference point, doesn’t matter where it is inside the shape.

For any point on the contour:
Xc = x + a
Yc = y + b

a = rcos(alpha)
b = rsin(alpha)

so:
xc = x + rcos(alpha)
yc = y + rsin(alpha)

Now phi, the normal to the template image edge at (x,y), is calculated

Later, a pixel with that gradient can be considered a candidate for that template point

An R-table is then constructed. This consists of a range of edge angles, phi (at some resolution, say 1 degree)

For every contour pixel in the shape, the edge gradient, phi, is found and the (r, alpha) for that pixel is calculated and appended to the R-table for that phi

Question 14

How does the generalised Hough Transform detect shapes?

Answer 14

An accumulator array is created (of some chosen resolution)

For each pixel in the target image (x,y), the edge gradient, phi, is calculated

Each (r, alpha) pair for this phi (from the r-table) is used to calculate a potential shape centre using:
xc = x + rcos(alpha)
yc = y + rsin(alpha)

The item in the accumulator for this (xc, yc) is incremented

• The highest values in the accumulator array show the likely centres of the template shapes
• This method can detect multiple instance of the template in an image
• Note that a separate R-table must be created for each template to be found in an image

Question 15

What dimension of accumulator array is required for a completely generalised Hough Transform?

Answer 15

4-dimensional
(x, y, s (scale), theta (angle))