r 
a 
QO ® 0 nn 
30 
ne OO: 
woo oS 0 
There are two methods for compacting raster data: 
quadtree and run-length encoding. But here the 
two-dimensional run-encoding is different from 
the conventional run-length encoding. It is a 
space-efficient form of linear quadtree, and 
uses the same address keys as linear quadtree. 
2.1 Linear Quadtree 
The linear quadtree is a data structure which is 
based on the regular decomposition of a square 
into quadrants and sub-quadrants (see Mark 1989). 
Such structure represents only leaf nodes, with 
nodes identified by numeric keys. The form of 
these keys permits topological and spatial 
relations to be determined from the key values. 
The data structure is conceptually then a list of 
the leaf nodes in sequence by key. In general, 
Morton keys are used as the numeric keys (Figure 
2). 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
7| 22143 | h6| 47 [58 | 59 | 62 | 63 
6| 40/41 | 54 | 45156 | 57 | 66/61 
5| 35|35| a8| 39|58| 51| 5| 55 
5| 32|33]| 36| 37 |n8 | n9 | 52] 53 
3| 18| 11] 15| 15|26 | 27 | 38| 31 
?| g|9]| 12] 13| 25] 25| 28| 29 
1| 2| 83 18| 19| 22| 23 
8| 8| 1 16 | 17] 28 21 | 
9 1.2 3 a 5 6 7 
Figure 2. Morton keys 
There are several ways to obtain Morton keys, 
while bit interleaving is the fast one (Gong 
1991). Bit interleaving consists of taking the 
bit representations of the row and the column 
number, and forming a key consisting of 
alternating bits from each number (Figure 3). 
   
A ais mt ta go FA j 
Pr / 
Morton key-[ — ^ Toe|rp [o[slo] ifo] 
  
Figure 3. Generation of Morton key 
A "bottom-up" quadtree construction may be the 
easier and faster than the "top-down" 
construction (Gong 1991). Appropriate sets of 
four mutually-adjacent cells can be examined and 
combined into a node of level 1 if they all have 
Linear quadtree 
  
  
  
  
  
  
  
  
M1 | Value 
; 2DHE 
0 0 | M1 |Valu 
4 D es 
[ally 
8 0 | 
a 10/4 
| 13| 0 
i | 14] 1 
14 | 1 | 
Fig. 4a 
15 1 Fig. 4c 
Fig. 4b 
Figure 4. Linear quadtree and 2DRE 
769 
the same value. Then, if four such level-1 nodes 
have the same value, they are combined into a 
level-2 node and so on (Figure 4b). This method 
will lead to the same set of quadtree nodes as 
the top-down approach. 
2.2 Two-dimensional Run-encoding 
Two-dimensional run-encoding (2DRE) is an 
approach for the compact representation and 
manipulation of linear quadtree (Lauzon 1983, 
Mark and Lauzon 1989). A 2DRE file can be 
constructed by run-encoding a linear quadtree, 
that is, by combining runs of consecutive leaves 
of the same value into a single data element. In 
figure 4b, the three values of the former leaf 
nodes are the same, and they are combined to form 
a record (Figure 4c). 
Two-dimensional run-encoding exhibits several 
desirable features for a data structure for use 
in geographical data processing; for example, 
multiple attribute encoding, random access and 
error recovery. This enhances the performance of 
GIS procedures such as search and overlay, and 
result in greater storage efficiency and 
flexibility for processing of geographical 
information than do other quadtree structures. 
3. MULTI-GRIDS TECHNIQUE 
The original cells of raster serve basic grids. 
To improve the representation precision of 
raster, some particular basic grids containing 
points and lines are divided into many fine 
grids, and to index the 2DRE file, basic grids 
are grouped into rough grids as indexing blocks. 
3.1 Fine-divided Grids for Improving 
Representation Precision of Raster 
A main disadvantage of raster structure is too 
low accuracy. In this section, an approach by 
using fine-dividing grids is presented. In figure 
5, each basic grid is encoded in Morton key(M1). 
In order to improve the geometric resolution of a 
raster, those basic grids that contain points and 
lines are redivided into 256*256 fine-grids, 
which are also encoded in Morton key(M2). Thus, a 
pair of coordinates x, y can be converted into 
two Morton keys M1 and M2, and replaced by them. 
In this way the represented precision of raster 
data for points and lines will be increased by 
about 256 times, however, the storage is 
increased only by 2 bytes for each sampling point 
and intersection point between a line and a basic 
grid side. 
  
Figure 5. Morton keys of basic grids 
and fine-divided grids