Line and Curves Detection
Given an edge image, nd line or curve segments present in the image.
1
Issues with Curve Detection Grouping (e.g., the Canny hysteresis thresholding procedure) Model tting They can be performed sequentially or simultaneously.
2
The Hough Transform The Hough Transform (HT) is a popular technique for detecting straight lines and curves on gray-scale images. It maps image data from image space to a parameter space, where curve detection becomes peak detection problem.
3
The HT for Line detection
1. Parameterize the line
y = ax + b In the parameter spaces determined by a and b, each parameter pair (a b) represents a line. For example (0,4) represents a horizontal line. This line representation can not represent a vertical line.
4
Alternatively, we can also parameterize a line in polar coordinates as
x cos + y sin ; = 0
5
X
θ ρ
y=ax+b xcos θ + ysinθ = ρ
Y
6
ρ
(θ, ρ)
θ
In parameter space determined by and , each pair of ( ) represents a line. For example, a vertical line my be represented as (0 4). 7
An image point (x0 y0 ) represents the intersection of all lines that satisfy x0 cos + y0 sin ; = 0, each of which can be represent by a pair of ( ). In the parameter space, the image point is represented by a sinusoid curve 15
10
rho
5
0
−5
−10
−15
0
50
100
150
200 theta
8
250
300
350
400
The intersection of two sinusoid curves representing the line going through two image points (e.g., (10,10) and (20,20)) uniquely determines a line. X 30 x1=(10,10) x2=(20,20) 25
(10,10)
20
15
10 rho
(20, 20)
5
0
−5
−10
−15
Y
−20
0
20
40
60
80
100
120
140
160
180
theta
If lines are parameterized using a and b, then an image point is represented by as a line in the parameter space (g. 5.1). 9
2. Quantize parameters and To keep the parameter space nite, it is often necessary to quantize the parameter space. By quantization, the parameter space is divided into nite grid of cells, the dimensions of each cell are determined by the quantization intervals. Each cell is indexed by a pair of quantized ( ).
10
3. Build an accumulator array A( ) The accumulator array is used to accrue the contribution of each image point to a quantized ( ). The standard HT scheme for updating the accumulator array A( ) is
A( ) = #f(x y) 2 X Y jx cos + y sin + = 0g where X Y are the image domain. For example, if we have N image points lying on a line with parameter pair (0 0 ), then we have A(0 0 ) = N and the accumulator array values for
all other parameter pairs are 1. For each quantized , we use the line equation to 11
compute the corresponding . The computed is then quantized. The accumulator corresponding to the quantized and are then incremented by 1.
12
4. Search A( ) for peaks The image lines are therefore detected by the peaks of A( ). To detect multiple lines, look for all local maxima of A( ).
13
HT Algorithm Outline
For an input gray scale image I of M N . 1. Locate the HT coordinate system 2. Identify the ranges for and . Let the range for for be between l and h , and the range for between l and h . 3. Choose quantization intervals and for and respectively. 4. Discrete the parameter space of and using sampling steps and . Let d and d be 1D arrays containing the discretized and . 14
5. Let A(T, R) be an array of integer counter initialize all elements of A to zero, where R = h; l and T = h;l . 6. Let L(T,R) be an array of a list of 2D coordinates. 7. For each image pixel (c r), if its gradient magnitude g(c r) > , where is a gradient magnitude threshold. for i=1 to T
= c cos(d(i)) + r sin(d (i)) nd the index k, for the element of d closest to
increment A(i,k) by one. 15
Add point (c,r) to L(i,k) 8. Find all local A(ip kp) such that A(ip kp) > t, where t is a threshold. 9. The output is a set of pairs (d (ip) d (kp)) and lists of points in L(ip kp), describing the lines detected in the image, along with points located on these lines
16
HT Coordinate Systems The HT coordinate system coincides with the row-column coordinate system. Ranges of and p 0 < < M2 + N2 ;90 < < 180 or p -M < < M 2 + N 2 0 < < 180 The HT coordinate system locates at the center of the image 17
or
Ranges of and p 2 2 0 < < M 2+N 0 < < 360 ;
p
M 2 +N 2 2
