= 
t 
of 
1€ 
ve 
S, 
1C 
representation of an image to a symbolic one [Lutofo et al., 
1989]. 
[Duba and Hart, 1972] introduced and modified the Hough 
Transform [Hough, 1962] for detection of straight lines. In this 
approach a line is described in the image space as: 
x*cos0+y*sin0 = p (1) 
where parameter 6 is the angle relative to the positive horizontal 
direction and p the normal distance from the origin (see figure 
1). The range of p is -2*D to 2 * D, where D is the 
size ( diagonal ) of the image space. The range of 0 is between 
0° and 180° degrees. 
Y À 
line 
  
  
O ! 
X 
Fig. 1: Normal representation of a line. 
Then a transformation from the image space (xy) to the 
parameter (p0) space is carried out. Image points are mapped 
into sinusoidal curves in the parameter space. If for a number 
of image points, the corresponding sinusoidal curves in the 
parameter space intersect in a common point (px , 0), then 
these points lie on the straight line : 
x*cos O+y*sin 0 = pi 
in the image. 
The computational attractiveness of the Hough Transform arises 
from subdividing the parameter space into accumulator cells 
A(p,0) (see figure 2). 
  
  
  
  
  
0 90 180 
A2*D — 9 
0 eoe o eee 
ÿZ*D : 
  
  
  
  
  
  
  
I 
Fig. 2: Quantization of the parameter space into cells. 
251 
Initially accumulator cells are set to zero: A(p,0) = 0. Then for 
every point (x,y) in the gradient image the quantized Mg values 
of 0 are incremented by 50 and for each value of © the 
corresponding p is calculated using equation (1). The 
calculated values of p are then quantized in My intervals of 
width óp and the correspondent accumulator cells are 
incremented by one : A(p,6) = A(p,6)+1. The accumulator cells 
with the greater number of votes correspond to lines in image 
space. 
As can be seen, the computational expense of the Hough 
Transform is Mg*n computations of p. where n is the number 
of points (pixels) in the image. Using the gradient instead of the 
of the original image, the number of points in the image is 
reduced dramatically and the Hough Transform becomes 
computationally much cheaper. 
In a noise-free image all points that belong to a line correspond 
to sinusoidal curves that intersect at a unique point (Px,0x) in the 
parameter space. But images are not noise-free, so the point of 
intersection is not unique anymore and a number of intersections 
are distributed around the actual one (py,Ok). It is clear now 
that local maxima in the parameter space describe the lines of the 
image. Working in this direction, [Harjoko, 1990] proposed the 
following procedure: 
After every pixel of the image has been considered and the 
accumulator cells of the parameter space have been prepared, a 
cluster algorithm is performed in order to detect clusters in the 
parameter space. Each cluster is bounded using a boundary 
value threshold. The boundary value is chosen to be a fixed 
fraction of the peak value of the cluster. The standard deviation 
of the cluster is selected as the peakyness (local maximum) 
measure. For everv bounded cluster:the standard deviations 
Op ; Op and the means mp , me are calculated. The value in each 
cell is treated as the weight of the cell: 
my- 1*zx i*fü,j) 
me= L+EZ H(i) 
oj- 1*ZX (i-m, *fü.j) 
o; - l*ZZ (m, Y*f(,j) 
where s=XX f(i,j; , f(ij) the value of the (i,j) cell, 
and ij=-atoa ,a isan integer part of the cluster size. 
The mean values for each cluster are the wanted local maxima in 
the accumulator array and correspond to straight lines in the 
image. The last step is the transformation of the local maxima 
back to the image in order to get the analytical equation of the 
detected lines. 
Hough transform cannot only detect straight lines, but it can also 
detect any predefined shape. But the order of computational 
expense increases with the complexity of the curve, and the 
Hough Transform tends to be computational expensive. A more 
efficient and computationally attractive Hough Transform for 
detecting analytical curves in images [Ballard, 1982] is making 
use of the edge pixel gradient directions as follows: 
If f(x,a)=0 is an analytical curve, where x represents image 
points, and a the parameter vector, then 
stepl: Form an accumulator array A(a). Initialize it to zero. 
step2: For each edge pixel x: