stigation of the 
in the maria of the 
1996 
Multi-spectral Quadtree based Image Segmentation 
Ben G.H. Gorte 
International Institute for Aerospace Survey and Earth Sciences (ITC), 
Enschede, the Netherlands. 
e-mail: ben@itc.nl 
KEYWORDS: Remote sensing, algorithms, multi-spectral, image segmentation, quadtrees 
ABSTRACT 
The paper gives a description of an image segmentation method, which is based on multi-spectral image data. It is 
embedded in a quadtree based GIS and Image Processing system. Generally, the system gives the possibility to integrate 
remotely sensed data, map data and attribute data. It offers raster processing capabilities, combined with high resolutions, 
with modest storage and processing time requirements. By subdividing an image into segments, assuming that these 
correspond to objects in the terrain, the integration of R.S. and GIS can be strengthened. 
1 Introduction 
For the purpose of widening for post-graduate and M.Sc. 
students in our institute the opportunities to study and in- 
vestigate spatial data structures, a modest quadtree soft- 
ware system was gradually developed during the last few 
years. In the course of this activity, a stage was reached 
were quadtree based image segmentation could be imple- 
mented without too much additional effort. Although this 
subject has received attention in literature since the sev- 
enties [3], it did not become widely accepted in the field 
of analysis of remotely sensed imagery. For example, in 
very respected textbooks in this field, such as [4] and [7], 
image segmentation is not mentioned. Also the major com- 
mercial digital image processing software packages do not 
include image segmentation modules. Nevertheless, im- 
age segmentation is intuitively appealing. Human image 
vision generally tends to divide the image into homogen- 
eous areas first, and characterize those areas more care- 
fully later. Applying this approach to digital image ana- 
lysis software leads to a segmentation step, which divides 
the image into segments that correspond — in the ideal 
case — to meaningful objects in the terrain, followed by 
a supervised classification step, in which each segment is 
compared with class characteristics that are derived from 
training data. In contrast to usual classification methods, 
the comparison does not have to be limited spectral prop- 
erties, but can also take spatial characteristics of segments 
(size, shape and adjacency to other segments) into account. 
The remainder of this paper focuses on quadtree based 
segmentation. The success of segmentation depends on the 
availability of: 
e High resolution imagery, such that the relevant objects 
are represented by a significant number of pixels; oth- 
erwise there is no point in segmentation. 
e Powerful hardware: fast and with a lot of memory 
e An efficient implementation, regarding the sizes of re- 
mote sensing images. 
A special case, which is typical for earth observation 
applications, is multi-band imagery. Grey-scale segment- 
ations ([5], [1]) of the individual bands give different sets 
of segments. In this paper a method is presented that seg- 
ments a multi-spectral image into one unique set of objects. 
2. Quadtrees 
Quadtrees serve as a spatial data model, in the sense that 
they allow the storage of data about various types of spa- 
tial objects and phenomena, as well as the operations on 
such data. In this study, area based quadtrees are used [6], 
which are conceptually equivalent to raster maps. There- 
fore, raster based GIS analysis operations are also defined 
in the quadtree domain and a large number of them can be 
implemented efficiently [2]. The advantage is that the spe- 
cifications and implementations of many GIS operations, 
such as mapcalculations and other kinds of overlay, are 
straightforward in the raster (and quadtree) domain. 
On the other hand, the raster data structure tends to 
lead to large data volumes, which need a lot of space and 
processing time. In case of (however advanced) “ordin- 
ary” compression techniques, the space requirements are 
relieved, but the processing times increase, because the 
actual processing will still take place pixel by pixel, and 
expansion / compression steps must be added. 
The quadtree data structure and software help to de- 
crease the storage and processing time requirements at the 
same time, especially at high resolutions. Roughly, stor- 
age requirements increase linearly with resolution when us- 
ing quadtrees, and quadratically using rasters. The chal- 
lenge of quadtrees is to create algorithms that work in the 
quadtree domain, which means that they do not expand 
251 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996