Raster representation and processing 
Raster cartographic linework is often stored using 
run-length encoding to compress the data. 
Run-length encoding is a good storage format, but 
a poor processing format. Sequential processing 
software must use internal data representations 
that simulate an uncompressed raster format. 
Each pixel in the current neighborhood has a color 
(or attribute). This color either is the same as 
the current pixel or is not the same as the 
current pixel. These two possibilities can be 
designated "1" and "O." The state of the 
neighborhood can, therefore, be represented in a 
single byte. Each bit shows the state of one of 
the pixels in the eight-member neighborhood. This 
one-byte coding of the neighborhood can be called 
the neighborhood state. This is a meaningful 
concept only if the current pixel is linework. 
Figure 2 shows the decimal and binary values of 
each neighboring pixel. The neighborhood state is 
calculated by summing the values of all linework 
pixels. This coding scheme is taken from Greenlee 
(1987), who credits the idea to Golay (1969). 
Greenlee uses this neighborhood coding to reduce 
storage space. The current study uses it to 
reduce search times. 
  
  
64 128 1 
01000000 | 10000000 | 00000001 
  
32 current 2 
00100000 | pixel 00000010 
  
16 8 4 
00010000 | 00001000 | 00000100 
  
  
  
  
  
  
  
  
Figure 2 Coding the neighborhood state. 
There are 256 possible neighborhood states (29). 
This number is small enough to treat each one 
individually. In the worst case, no more than 256 
rules are needed to define the vectorization of 
all nine-pixel squares. 
The raster data set is examined left to right and 
top to bottom. Each pixel is the current pixel 
only once. When the current pixel is part of the 
map background, no action is taken and the scan 
continues to the next pixel. 
When the current pixel is not background, the 
pixel must be assigned to a line. There are three 
factors that affect this decision: 
1. The neighborhood state. 
2. A rule set that dictates how specific 
neighborhood states are handled. 
3. Information about the line membership 
of the four predecessor pixels. 
These factors are applied in the order listed. 
The first factor is the neighborhood state. This 
is evaluated, and the result causes an appropriate 
rule to fire. 
The second factor is a vectorization rule set. 
Sixteen rules are adequate for all 256 
neighborhood states. Table 1 summarizes these 
rules: 
32 
  
  
  
  
  
  
  
  
  
  
  
  
A B cC D 
I 1 O | Do nothing 
II 2 2 | Make a node 
III 3 1 | Make a node 
Close line of NE pixel 
& 32 | Make a node 
Close line of W pixel 
5 64 | Make a node 
Close line of NW pixel 
6 128 | Make a node 
Close line of N pixel 
IV 7 5 | Extend line of NE pixel 
8 34 | Extend line of W pixel 
9 66 | Extend line of NW pixel 
10 130 | Extend line of N pixel 
V 11 33 | Connect line of W pixel 
with line of NE pixel 
  
12 65 | Connect line of NW pixel 
with line of NE pixel 
  
13 160 | Connect line of W pixel 
with line of N pixel 
  
VI 14 37 | Make a node 
Close line of W pixel 
Close line of NE pixel 
  
15 69 | Make a node 
Close line of NW pixel 
Close line of NE pixel 
  
16 162 | Make a node 
Close line of W pixel 
  
  
  
Close line of N pixel 
(= 
Table 1. Rule set for sequential vectorization. 
  
  
  
Column A: The 16 rules fall into six 
categories. These categories are not 
present in the software implementation of 
the rules, but are useful to understanding 
the system. For example, the four rules in 
category IV can be generalized to "if there 
is exactly one predecessor pixel, extend the 
line containing that pixel to include the 
current pixel." 
Column B: Rule numbers. 
Column C: The one-byte decimal code of the 
first (lowest-numbered) neighborhood state 
to which the rule applies. Most rules apply 
to more than one neighborhood state. 
Table 2 relates all neighborhood codings to 
the 16 rules. 
Column D: A brief statement of the rule. 
The beginning and end of each line is flagged with 
a node. The term node in this context does not 
imply topologic structure. The raster processing 
pass creates a node when two different vectors 
meet or when a vector ends. Because the 
processing is sequential, and because the 
processor views only nine pixels at a time, large 
numbers of temporary nodes are created. For 
example, a node will be created wherever there is 
a local maximum or minimum in a line (Figure 3). 
These temporary nodes must be removed during 
subsequent processing. A node-line list and a 
line-node list are constructed during the pass 
through the raster data to aid vector processing. 
The third factor to the vectorization decision for 
the neighborhood is knowledge about the states of 
other pixels in the neighborhood. The most 
important piece of information is whether or not 
any of these pixels are nodes. The words "close," 
"extend" and "connect" in table 1 mean different 
things for nodes than for pixels. 
  
  
The 
vec 
tyr 
fra 
nod 
unn 
the 
The 
sea 
set 
to 
The 
tre 
suc