SOFTWARE FOR CARTOGRAPHIC RASTER-TO-VECTOR CONVERSION 
Laurence R. Moore 
U.S. Geological Survey 
1400 Independence Rd. 
Rolla, Missouri 65401 
ABSTRACT 
igi i i ter-to-vector 
ture digital cartographic data from maps usually require ras 
nat The e d of modern computers makes it possible to vectorize large data sets of 
conversion. Thinned cartographic linework 
run-length encoded cartographic linework in a reasonable time. 
can be vectorized in one pass through the raster data followed by one pass through the 
resultant vectors. 
that is fast and portable. : 
flexibility, which allows software tuning 
i i i -to- tor conversion 
Software written in the C language provides a raster to-vec 
Simple rule-based techniques in the design provide software 
for particular applications. 
Key Words: raster, vectorization, rule-based, sequential processing, C language 
INTRODUCTION 
Rotating-drum raster scanners provide an efficient 
means of capturing digital cartographic data from 
maps. Vector data formats allow digital 
cartographic data to be structured and stored 
efficiently. Converting digital data from raster 
to vector format is therefore required in most 
digital cartographic production systems. 
This conversion has historically been a problem. 
Because high-resolution cartographic data sets can 
be extremely large, the conversion of raster data 
to vector data requires large computers, long 
processing times, or both. 
Peuquet (1981) says that raster-to-vector 
conversion can be divided into three basic 
operations. First is skeletonization or line 
thinning. Second is line extraction or 
vectorization. Third is topology reconstruction. 
This paper deals with the second of these 
operations.  Vectorization is the process of 
identifying a particular series of data entities 
or coordinates that constitute an individual line 
segment as portrayed on the input document. 
Commercial systems that scan and vectorize 
linework are readily available today, but the 
algorithms used by these systems are usually 
proprietary. Commercial software also precludes 
fine tuning the vectorization for particular 
applications. For example, there are several 
reasonable ways to define the vectorization 
behavior at the intersection of lines with 
different attributes. 
This study implemented in software a flexible and 
reasonably fast vectorization algorithm. The 
software was designed specifically for 
cartographic data. High priorities were given to 
producing software that would (1) operate on large 
data sets and (2) be portable to different 
computers. 
METHODOLOGY 
This investigation focused on sequential 
processing solutions to the line extraction part 
of the raster-to-vector problem. Prototype 
software, written as part of the study, tested 
algorithms and data representations. A cycle of 
software development and testing was used to 
refine the algorithms and improve the 
implementation. 
Sequential processing 
Many useful functions in image processing perform 
a single operation on each point in the image. 
For example, the contrast of pictures can be 
smoothed or sharpened by altering the value of 
each pixel as some function of the values of the 
neighboring pixels. In such operations, only 
original values are used as input, and.the 
sequence in which the pixels are processed is 
therefore irrelevant. The operations are 
essentially performed in parallel. 
3l 
Parallel algorithms can be conceptually simple, 
but they can be inefficient on sequential 
processors. For small data sets this is not a 
problem. But most useful cartographic data sets 
are not small. 
For sequential operations the order of processing 
is important. Suppose that the points in a 
digital image are to be processed row by row 
beginning at the upper left. As soon as a 
particular point is processed, its new value, 
rather than the original value, is used in 
processing any succeeding points. 
Figure 1 illustrates the terminology of sequential 
processing. At any given time there is one 
current pixel (a; ;)- This pixel has eight 
neighbors, four of which have already been 
processed (prior pixels) and four of which have 
not yet been processed (successor pixels). 
  
  
  
  
P P P P = prior 
a i-Lj-1 a i-1j a i-1j+1| C= current 
S = successor 
P C S 
a ij-l a ij ij*l 
S S S 
i+1j-1 i+1j i*Lj*l 
  
  
  
  
  
  
  
  
Figure 1 Terminology of local sequential 
processing. 
Rosenfeld and Pfaltz (1966) show that "any picture 
transformation that can be accomplished by a 
series of parallel local operations can also be 
accomplished by a series of sequential local 
operations, and conversely." Further, they show 
that sequential processing on a sequential 
computer is always faster than parallel processing 
on a sequential computer. (Parallel processing on 
a parallel computer is faster yet.) 
A raster data set of cartographic single-pixel 
linework can be vectorized in one sequential pass 
through the raster data (Peuquet, 1981). That is, 
each pixel is a current pixel exactly once. A 
decision about the treatment of the current pixel 
can be made by looking at its state and the states 
of its eight neighbors. This decision may alter 
the state of the current pixel, and that altered 
state is used for any subsequent processing that 
involves the pixel.