than in original image ICi,j), it is still difficult to 
automatically recognize and extract residential sec- 
tions directly form Q(Ci,j). The graphics in QCG,j) 
are thick ones which are not easily manipulated. In 
this case, thinning transform should be performed 
to reduce the graphics to minimal sets of pixels 
representing invariants of the graphics geometrical 
shapes. There are many algorithms for binary im- 
age thinning process. The algorithms used in our 
system can be briefly described as follows. Every 
time the pixel meeting the following conditions are 
deleted (i. e. turning their image values to 1s) 
from image Q(,)). 
aJIG.D-1; 
b)IG,j—1)=0 || IG,j;+1)=0 ||IG—1,j)=0 [TG 
+1,j)=0; 
c)CG,j)=1. 
where I(1,j) refers to the image value of pixel (1,3) 
and CG,j) to the 0—1 modes of its neighbour pix- 
els in clockwise direction of pixel (i,j). After per- 
forming a few times of this process, all of the 
graphics in Q (i,j) is thinned. Suppose n repre- 
sents the times of thinning process, we sign the 
thinning transforms as T,(i,j). The result of T, (i5 
j) is shown in Figure 10. 
pou 
Te GR 
NS ? 
x anb. e 
SS Frit 
ld bn. 
s o LE 009 
m 
bot. 
= o 
Fig. 10 The result of T, GG, (n—3) for QG,p 
We know that the residential areas are closed poly- 
gons on maps. But there are many open graphics in 
image T.(i,j) and they should be deleted. In order 
to delete the open graphics, the pixels which meet 
the following conditions are need to be changed in- 
to white pixels. 
a)lG,)=0; 
b)CG,)=1. 
Thus a new image R (i,j) is obtained by deleting 
open graphics from Tn(i,j). The result of R(i,j) 
is shown in Figure 11. ; 
6. TRACING POLYGONS 
2 
? 43 pa 
9$ 
as . 
A 
ê 
Fig. 11 The result of RG,j) 
As shown in Figure 11. image RG,j) consists of 
closed polygons exclusively. Since all of the resin- 
dential sections are included in these polygons, it is 
a key step to trace these polygons automatiocally. 
The procedures of polygon tracing is briefly de- 
scribed as follows. 
a)Searching a black pixel row by row and column 
by column as the first border pixel of a polygon. 
b)Successively tracing other border pixels of the 
polygon anticlockwisely until coming back to the 
first border pixel. 
Thus we can obtain all of the border pixels of the 
traced polygon and their image coordinates are sup- 
posed to be (xi, y) (i—1,-*,n). After completing 
the tracing process of a polygon, the pixels on its 
border and in its interior area should be deleted 
from image R(i,j) to avoid retracing this polygon. 
The border pixels can be easily deleted by changing 
them to white pixels. However, the deletion of its 
interior black pixels needs a much complicate pro- 
cess, which mainly includes following steps. 
a)Determining the minimum row Ym and the maxi- 
mum row ya 0f the traced polygon. 
Yin = minCyisi € [1,n D; 
Ymaz # MAX CH; si € [1,n D. 
b)For an arbitrary row y (Ymin CYXYmax) » search- 
ing the border pixels with vertical image coordinate 
y from the polygon border pixes set (xi,y:) (= € 
[1,n]) and thus obtaining a pixel set (xi,y), GE 
[1,k]). 
c) Reordering the pixel set (xi,y),1€ [1,k],ac- 
cording to the horizontal image coordinate. If i<j, 
(i,j€[1,k]), then x;<x,. 
d)Determining the start pixel and the end pixel of a 
horizontal segment in the polygon. There may be 
several horizontal segments in a row. 
e) Turning the pixels on the segments into white 
ones. 
In this way, the pixels in the polygon can be delet- 
340 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996 
  
ed f 
poly 
link 
and 
dant 
hatc 
link 
step 
a)R 
gon: 
are 
ther 
mon 
sam 
mov 
can. 
whe 
b)R: 
pend 
7, 
Amc 
some 
and 
hatc] 
hatc] 
do n: 
the 
can ( 
a)TE 
ing, 
stanc 
pixel 
the r 
poly 
poly 
thres 
class 
then 
the 1: 
as ha 
b)TI 
imag 
black 
trary 
point 
any l 
the n