Hough Transform
It is one of the most efficient technique for feature extraction in Computer Vision. This algorithms helps in detecting imperfect instances of a particular object, broken lines, distorted lines etc. After successful detection of such lines it helps in representing it in a mathematical form.
While doing Edge detection there are many challenges -
1. Extraneous Data
2. Incomplete Data
3. Noise
Hough tranform solves all such challenges and provide efficient way to apply edge detection. Initially Hough transform was concerned for line detection only but later it is extended to identify arbitrary shapes also.
Line space can be expressed with two variables:
a. Cartesian coordinate — y = mx+c
b. Polar coordinate — xcosθ + ysinθ = r
Description of Hough Transform using Cartesian coordiantes:
Consider a point (xi, yi)
equation 1: yi = mxi + c
therefore, equation 2: c = yi — mxi
This allows us to look problem into two spaces:
a. Image Space
b. Parameter Space
If you plug (xi,yi) in equation 2 than you will get a straight line in parameter space i.e all the lines that will pass through point (xi,yi) . In the same manner we will keep putting all the points that lie on line in image space to get corresponding line on a parameter space.
Once you get the point of intersection (m,c) its the straight line all of them have in common.
If you take a point which does not lie on the line in image space than it will too create a line but that line will not pass through intersection point (m,c) since that point does not lie on the straight line in image space.
A point in an image space maps to a line in parameter space and a line in parameter space maps to a point in an image space and vice versa. Based on this assumption we can create a line detection algorithm.
Line Detection Algorithm
- Quantize parameter space (m,c).
- Create an accumulator array A(m,c) to define parameter space and it will be quantized to some resolution thats appropriate for the problem.
- Set A(m,c) = 0 for all (m,c)
- For each edge point (xi,yi) we will plug it into equation 2
c = yi — mxi
and for every value of (m,c) which lies on the straight line we will increment accumulator value by 1. Incrementing all the points this straight line will pass.
A(m,c) = A(m,c) + 1
Intersection point is selected on the basis of voting scheme i.e local maxima.
Multiple Line Detection
In this scenario all the line will give an intersection point in parameter space.
Joining all the intersection points in the parameter space will correspond to the lines in the image space.
Better Parameterization
Problem in using Cartesian coordinate system is that value of m ranges from -∞≤m≤∞ since the value of m is infinite than we have to take a very large accumulator space in order to represent every point in parameter space. To overcome this problem use of polar coordinate system is preferred.
xsinθ -ycosθ + ρ = 0
In polar coordinate system the range of orientation θ is finite: 0≤θ<π and distance ρ is also finite.
If we take a point on a line in an image space than it will create a sinusoid in the parameter space. Same steps will be followed and it will keep creating sinusoids until we get an intersection point in the parameter space which will correspond to the line in image space. In this case an accumulator will be created using θ and ρ and voting is done along sinusoids in that space.
Code for applying Hough Transform
import numpy as npimport cv2
img = cv2.imread('images/soduku.jpg')gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)canny = cv2.Canny(gray,100,170,apertureSize=3)cv2.imshow("canny",canny)cv2.waitKey(0)hough_lines = cv2.HoughLines(canny,1,np.pi/180,200)for line in hough_lines:rho, theta = line[0]a = np.cos(theta)b = np.sin(theta)x0 = a*rhoy0 = b*rhox1 = int(x0 + 1000*(-b))y1 = int(y0 + 1000*(a))x2 = int(x0 - 1000*(-b))y2 = int(y0 - 1000*(a))cv2.line(img,(x1,y1),(x2,y2),(0,255,0),3)cv2.imshow("Hough line",img)cv2.waitKey(0)cv2.destroyAllWindows()
Hough Mechanics
Q1. How big should the accumulator cells be?
A1. There are two cases for selecting the accumulator size:
a. Too big cell size may result in overlapping of lines i.e lines may be merged.
b. Too small cell size may result in not capturing the noise causes lines.
Q2. How many lines are there in an image?
A2. Count the peak values in an accumulator array this will give the number of lines present in an image.
Q3. How to handle inaccurate edge locations?
A3. Increment the patch in accumulator rather than incrementing a single point.
Line Detection Results
Hough Transform: Circle Detection
Equation of circle: (xi-a)^2 + (yi-b)^2 = r^2
If radius r is know than
Image Space equation 1
(xi-a)² + (yi-b)² = r^2
Parameter Space equation 2
(a-xi)² + (b-yi)² = r²
Accumulator = A(a,b)
For every point (xi,yi) that lies on a circle in an image space will map to a circle in a parameter space. Finally after plotting all the values we will get an intersection point (a,b) that corresponds to the circle in image space that passes through all the points.
Using Gradient Information
If Edge Direction Φi is given along with Edge Location (xi,yi) and radius r. In such case after plotting circle in parameter space rather than voting from entire circle you just need to vote in direction of r and the opposite of the point in parameter space. Since you don’t know in which direction the centre lies so you need to take two votes one in direction of radius r and other one in opposite direction. Eventually you just need to increment by 2 in parameter space for every point of image space. The point which receives the maximum number of votes will be the centre of the circle.
Special Case
If radius r is not know for a circle. In such case the dimensionality of the Hough Space will be three (a,b,r). For every point in the image space if we put it in the equation of parameter space than it will give you cone and once the plotting is done for entire set of points in the image space than the voting will be done along the cone. Finally maxima will be calculated in the accumulator array.
