May 
for 
ica 
and 
ust 
88. 
hgt 
res 
ca. 
on 
DIGITAL TOPOLOGICAL AND MATRIX STRUCTURED IMAGE PROCESSING * 
Shao. Juliang 
Li Deren 
Department of Photogrammetry and Remote Sensing 
Wuhan Technical University of Surverying and Mapping, 
39 Loyu Road, Wuhan 430070,P. R. China 
17th ISPRS Congress, Comm. I , Washington D. C. 
ABSTRACT 
Digital topology deals with the topological properties of digital image and provides a sound mathematical basis for 
image processing operations such as image thinning, border following and connected component labelling. Matrix 
structure is also a consistent mathematical framework for image processing. This paper reviews the concepts of 
these two fields and suggests some image processing operations such as image thinning, border following, region 
growing and discrete Fourier transform by integrating these two methods. In this integration the digital topology 
of imagery is considered as constraint condition and the matrix structure of imagery is used as the parallel 
representation method. This investigation would be valuable for image matching and image understanding. 
KEY WORDS; Digital Topology; Matrix Structure; Image Processing; Algorithm; 
]. INTRODUCTION 
1. 1 Digital topology 
Digital topology is to study the topological properties 
of digital image arrays. Its results provide a sound 
mathematical basis for image processing operations 
such as image thinning, border following, and region 
growing. Most people (Kong &. Rosenfeld 1989, 
Arcelli 1979 ,and Tsao & Fu 1982] paid attention to 
the properties of the digital topology with two — and 
three—dimensional binary image arrays ,but not with 
gray —scale image arrays. However ,some tasks such 
as region growing, image understanding and pattern 
recognition, etc. relate to the digital topology with 
the gray — scale image arrays. We review therefore 
some basic concepts about the digital topology, and 
extend the connectivity of the binary image to that of 
gray value image . 
Let (i,j) be a point of an given image. It then has 
x This paper is the early research to interpret the 
man — made objects from the aerial photograghs. 
four horizontal and vertical neighbors described as the 
following: 
(1.0, Uy F196,j—1) 63-154) 
Such points are called to be 4 — ADJACENT. 
Moreover, (i,j) has four diagonal neighbors, i. e. 
—15j— 15,661, 11-15, 
G+1,1—1)50+1,4+1) 
These points together with four 4 — adjacent points 
are called to be 8— ADJAECNT. 
A PATH is a sequence (p; |] 0<i<n) , and pi is 
adjacent to pi+1. A set of pixels is said to be 
CONNECTED if there is a path between any two 
pixels. 
Here, we set up a theorem related to the gray —scale 
image. 
Theorem 1; A set of pixels posses connectivity, and 
is called region, when a pixel is extended to be such a 
set of pixels according to the following steps. 
A. Select a starting point as region 0(Ry) ,and give a