the data to raster format at any stage. In that case, pro-
cessing times depend on the quadtree data set sizes, which
leads to a significant gain at high resolutions.
Another advantage of the raster data structure is the
ease of integration of map and image data. This advant-
age is equally valid for the area based quadtree approach.
Unfortunately, not much is gained in terms of space and
time, when processing images as quadtrees. However,
quadtrees allow to combine data layers with different res-
olutions without having to re-sample one to the other.
2.1 Data Structure
Linear, sequential quadtrees (no indexing)
Z-scanning
order
Raster Quadtree
5151.
Data File
structure structure
level |value .qtl file
: s 3 (max level == level of entire map)
1 5 8 (actual number of lines) 4 x 4 bytes
1 8 8 (actual number of columns)
2 5 1 (type of pixel value: 1 = byte, 2 = integer)
2 5 131122 p! 1 (sequence of level’, 2 values per byte)
0 7 ! À l (one 0 instead of four)
0 5 (bytes)
0 5
0 5
1 | 5 .qtv file
1 5
1 5 5558557555555 (1 or 4 bytes per value)
Figure 1: Quadtree data structure
2.2 Operations
The package in its current state is useful to demonstrate
quadtrees in education or to explore them during research
in the field of spatial data structures and operations. The
programs have in common that they read input and write
output sequentially and simultaneously, without excess-
ive buffering in internal memory. Therefore, there are no
(practical) limitations to the sizes (resolutions) of the data
sets to be processed. The entire data set does not have to
reside in internal memory at any time.
The following modules are present:
General: raster to quadtree and quadtree to raster con-
versions, image calculations, statistical analysis (his-
tograms, multi-band statistics), simple map and im-
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
age generalization, which allows to create levels of de-
tail (LOD) at different representation scales.
Image Analysis: Training data analysis and maximum
likelihood classification, principal component trans-
formation, RGB to IHS transforms.
GIS: Map overlay and map calculation, aggregation func-
tions, determination of topology (region adjacency),
connected component labeling.
The segmentation algorithm is based on the one for con-
nected component labeling — in fact, the latter will appear
to be a special case of the former. Also, the map calcula-
tion module will be involved in the segmentation process,
as well as the connected component labeling. Therefore, we
describe these three modules with somewhat more detail.
Connected component labeling: a program that as-
signs to each homogeneous region a unique value. The
output quadtree values have the type “integer”, which
allows over 2,000,000,000 regions - more than there
will ever be pixels in the input. It's interesting to no-
tice that the structure of the quadtree does not change
with this operation.
'The program assumes 4-adjacency: a pixel has only
four neighbors (above, below, left and right), which
are taken into account when connectivity is estab-
lished, instead of 8 neighbors (the diagonal ones don t
count) In the “very high resolution quadtree filo-
sophy”, region pairs that are 8-adjacent without being
also 4-adjacent are very unlikely to occur,
Image and map calculations are carried out by à pro-
gram which allows overlaying data layers by perform-
ing arithmetical, mathematical, logical and relational
operations on corresponding pixels in different layers.
This program also provides the link between spatial
and attribute data. If pixel values have the meaning of
object number, attribute values can be found at any
pixel by indexing the attribute table with the pixel
value. See the result of segmentation in Figure 2.
Region Adjacency software can be used to establish ad-
jacency between pixel values in a quadtree. The result
is a relational table with two columns; if somewhere in
the quadtree a pixel with value p is neighboring a pixel
with value q, then (p, q) will be a record in the table.
The table is sorted in ascending order of (primarily)
the first column and (secondarily) the second column.
The value in the second columns is always larger than
the one in the first; if p is less then q, you will find a re-
cord (q, p) in the table. Therefore, every combination
is listed only once.
The operation makes most sense if the quadtree is
filled with regions that have unique numbers, such as
the result of an image segmentation process. In that
case it generates region adjacency information, which
can be incorporated in subsequent classification.
Figure
of multi
9.0
The imr
age as in
of objec
(mean v
topologi
as well e
The p
ively co
gions. |
input b:
quadtre
simple:
distance
be not |.
ariances
mention
only on:
Like
is scant
through
the proc
ing to «
and lool
