of
'sal
rsity,
stic
veys
; Four
Hf
Jour.
IMAGE SEGMENTATION BASED ON HOUGH TRANSFORMATION *
Prof. Zhang ZhuXun, Mr. Min Y
iren, Prof. Zhang Jianqing
Wuhan Technical Universty of surve ying and mapping
P.R.China
Commission ITI of ISPRS
ABSTRACT
In this paper the standard algorithm of the straight-line Hough
F.O.Gorman and M.B.Clowes are analysed. The author prese
which solves the contradiction between the running time and a
Transformation and the modified algorithm presented by
nis a new modified algorithm of Hough Transformation,
ccuracy. In order to get the position of the straight-line , a
straight-line recovering system is defined. On this base, region segmentation using Graph Theory is presented. The
satisficatory experiment results with aerial photographs are shown finnaly.
key words: Image segmentation, Hough Transformation, straight-line recovering, Graph theory, region segmentation
{INTRODUCTION
For the large scale image of a city area, existent methods
of image matching may be not suitalbe. The edge
extraction and image segmentation based on the
description of image structure seem to be the first step of
the new strategy, not only in matching of city images, But
also in image analysis and interpretation. One of image
segmentation methods, which divides the image into
some regions with even grey level(colour, or texture), is
the edge detection, and Hough transformation is the
importent techniqne of edge detection. It is used in many
fields to extract various curves successfully. but, there is
a contradiction between the running time and the accuracy
in the transformation procedure, and the description of
the regions is necessary for image processing in the
higher level, after edges are extracted.
Based on the analyses of the traditional algorithm of
straight line Hough transformation and the modified
algorithm proposed by Gorman and Clowes(1976), a
new algorithm is proposed, in which the information of
gradient direction is used more reasonably.
A straight line recovering system is designed in order to
locate the straight line. then, image segmentaion can be
carried out through the regions are described by the
edges using Graph Theory. The experiment results with
real images will be shown finally.
2. ALGORITHM OF STRAIGHT LINE HOUGH
TRANSFORMATION AND ITS MODIFICATION
The straight line equation used by Hough is
y=kx+b
Because k may be unlimited, the normal line equation was
proposed by Duda and Hart(1972)
p=xcosf+ysinf
where g and g are the direction angle and length of the
normal line of the straight line.
2.1. Traditional Algorithm
step 1: extracting feature points with edge detection
operator.
step 2: quantizing the parameter plane as h(m,n) with
initial value Zero, where m-INT(z/dg)-1,
n=INT(2R/dp)+1, de and dp are the intervals of
quantization, R=sqri(L2+W2)/2, L and W are the length
and width of the image.
step 3: for each feature point(xg, yy),
h(ij)-h(1j)-1
where i=0,1,..,m, 0j=i-d0> p;=xkcos0j+yksin0;,
j=INT(p;/dp).
step 4: detecting the extreme maximum points of the
parameter plane h. The extreme maximum point (ij)
conresponds to the straight line parameters 6;=i-d6 and
p= i-dp.
In this algorithm, the calculation is carried out from 6; to
6m: If the high accuracy is expected, then, the dé should
be small and m will be large. — The running time must be
much. Beside, determination of the threshold of extreme
point detection is difficult, and there are some false
straight lines.
2.2. Modified algorithm of Gorman and Clowes
Other steps are the same as in traditional algorithm except
step 5: for each feature point(xy,yx). calculating the
direction 6j. of its gradient with Roberts operator or Sobel
operator and poy-XycosOytyysin(y , — i-INT(6,/d6),
j-INT(pw/do), h(.j)-h(.j)*1.
In this way, (xy. yx; corresponds to only one point (6,9)
on parameter plane. The summation is only performed in
one cell of parameter plane h. However, there is noise on
* The investigation is supported by National Nature funds and National Bureau of Surveying and Mapping of P.R. China
633
