image. Thus, the direction of gradient computed by 
gradient operator is not precise. Therefor, the extreme 
points are not distinct, and their detection is difficult. 
2.3. New modified algorithm 
step!: The sobel differences are calculated for each pixel: 
dx ={(gi+1,j-1+28ij+1+8i+1,j+1) - 
(8i-1,j-1+28i-1,j+8i-1,j+1) 4 
dy =[(8i-1,j+1+28i,j+1+8i+1,j+1) - 
(@i-1,j-1+28i j-1+8i+1,j-1)V4 
The direction of the gradient is 
=arcig(dy/dx) 
The feature points are extracted by edge detection 
operator, and the edge is thinned along the direction of 
the gradient by selecting the extreme maximun gradient. 
step 2: The parameter plane is quantized. 
step 3: For each feature point (xz,ÿx) with its gradient 
direction 6 
h(ij)-h(ij)1 
where i=ibk.ibk+1-ines Ibk=INT[(61-0p)}/d6], 
ipe INT] (01-69/d6], 65 is a experimental value between 5 
degree and 10 degree. 
step 4: The extreme maximum points of the parameter 
plane are detected, and the straight line paremeters are 
computed 
6=i-dé , pj do 
whereti,pis an extreme point of h plane. 
The new algorithm solves the contradiction between the 
running time and the accuracy, because the summation is 
porformed in a small area and the dé can be small. What 
is more, the gradient information is used more reasonably 
in the case of the noise. 
3.STRAIGHT SEGMENT RECOVERING 
The position of straight segment is still unknown after the 
parameters are acquired by Hough transformation, 
because there is no end-point, In order to determine the 
position of a straight segment, the pixels corresponding to 
certain parameters are recorded respectively. 
: The set of the 
parameters and corresponding set of pixels are 
L={(@p;) and S; | i=1,2,......,M} 
where Sj-((xk yk)lk-1.2........Ni) 
There is false information in L, due to the quantization 
errors on both of the image and parameter space. Those 
are: 
(1).The set includes some false pixels. 
(2). Two straight segment are in the same set. 
(3).The pixels in the intersection of two line are not in the 
set. 
634 
3.1. Delete false pixel 
If lpi-xkcosbi-yksinfjl<=dp then the pixel (xp.yk) is 
removed from the set S; 
3.2. Segmentation and merging 
After ordering the pixels of the set S; the break-points are 
searched, and interpolation is employed between two 
broken points(x;,y;) and (Xj+1.yi+1) If there is feature 
point in the window with size 1*3 pixels centering at the 
interpolated point, it is a supported point. 
The ratio of the number of the supported points and the 
interpolated points is 
K=m/M 
where m is the number of the supported points, and M is 
the interpolated points. If K>T(threshold), ponit(x;,y;) is 
the end point and (x;+1,ÿj+1) is the begin point of next 
segment. After that, the ovrerlapped segments are merged 
into one. 
3.3. Intersection 
The intersections of the staight lines may not be included 
in the set Sj due to the errors of the gradients at the 
corners or crosses. 
The intersection coordinates of two segments S; and Sj 
can be computed. If computed intersection is not in S; and 
Sj and the distances between it and nearer end-point are 
smaller than T,(threshold) it is received and the end- 
points are connected. If dj and d2 largre than To(another 
threshold), it will be rejected. Othewise, the method used 
in 3.2 is applied to deffmine whether the computed 
intersection is rejected . 
3.4.Extension of end-point 
Because of the strict criteria of straight line detection and 
noise, some real end-points are not included in the line set 
Si. The end-point, namely (x1, y1) should be extended. 
The extrapolated points are processed progressively, 
when there is not any feature point in the window 
centering at the extrapolated point with size 1*3 pixels, 
the extension is completed. 
From the straight segment recovering system, the straight 
line parameters, two end-points and all pixels of each 
straight segment are acquired. 
4. REGION SEGMENTATION USING GRAPH 
THEORY 
If there are only straight segments on the image, they 
divide the image plane into different regions. For the 
further application, the straight segments comprising the 
regions should be determined. The Graph Theory 
(Mayeda, 1972) can be used in the extraction of the 
regions on images. 
4.1 Background of Graph Theory(Mayeda, 1972)