PREVIOUS EFFORTS 
Boyell and Ruston (1963) first introduced the graph 
representation of contour relationships in which contours and 
inter-contour regions are defined as edges and nodes, 
respectively. It provided a tool to visually perceive the 
relationship among contour lines. 
Later on, Pfaltz (1976) proposed a surface networks theory. In 
it, he attempted to select a limited set of disjoint points that 
conveyed the greatest amount of information about the surface. 
Those set of points were then used to reconstruct the 
interrelations of surface features such as peaks, passes, ridges 
and pits. In doing so, the topology of the surface can be 
formalized and terrain features can then be defined. Though 
not expanded on, contour labeling was mentioned as one of the 
possible applications of this theory. 
Mark (1977) concentrated on incorporating the contour tree 
concept in computer cartography, particular in contour labeling 
and surface generalization. He pointed out the potential of the 
graph structure in rebuilding the topology of contour lines. But 
it was Roubal and Poiker (1985) who first used the contour tree 
structures to automate the contour line labeling problem. The 
approach defined a graph structure using the topological 
adjacency of contour lines as nodes in the graph. In this 
approach, the inter-contour regions were not counted. Asa 
consequence, a non-closed contour resulted in the loss of its 
tree structure and the neighborhood relations were no longer 
retained (Figure 1a). 
  
  
  
  
  
  
  
  
  
  
LI 
I 
L2 
IS 
LS ——I3-——15-——I16 
| 
LA 
l 
I7 
Fig. la 
An 
"C — u—J 
G—D—E—F 
Fig. 1b 
An 
Nem Hm 
G— D-—E-—F 
Fig. lc 
  
Fig.1a: Non-closed contours in Roubal and Poikers' 
approach (1985) resulted in the loss of tree structure 
of the graph, and the neighborhood relations are no 
longer retained. 
Yagi et. al. (1991) reported a system that scans, digitizes and 
vectorizes the 1/25,000 topographic relief plate. The human 
operator was involved in the semi-automatic editing process to 
improve the quality of the scanned contour lines. An existing 
250m interval DTM was employed to assign the contour height 
in accordance with the height difference of a pair of known- 
height points. This approach improved image quality of 
cartographic documents by a photomechanical process and 
hence reduced the editing time. In general, it is an interactive 
method for contour labeling. 
266 
Sircar and Cebrian (1991) presented a raster-based approach to 
label contour lines digitized from topographic maps. The graph 
theory was also applied to reconstruct the topological 
adjacencies of elevation regions in rasterized contour maps. 
Both inter-contour regions and contour lines are treated as 
nodes in their representation in the resulting graph structure. A 
semi-automated batch-oriented approach was employed. It 
emphasized utilizing low cost desktop raster scanner for 
engineering applications of small or medium size organizations. 
Previous efforts have shown the merits of contour tree 
structures in preserving and representing the topology of the 
contour lines, and thus provided a basis for an automated 
contour labeling system. In an automated process involving 
human computer interaction, it is critical that the system follows 
the same logical sequence that a human operator does. This 
paper expands Sircar and Cebrians' (1991) approach with 
emphasis on the human-computer interaction. It begins by 
employing available height information to orientate the free tree. 
After applying topological rules to the graph structure in order 
to find the relative height order of the contours, unique 
solutions are derived and attached to the edges of the tree. The 
interactive mode will provide information so that ambiguous 
contours will be highlighted for the next iterative process to 
solve or for the operator to solve. For example, it is only by 
utilizing information from adjoining map sheets, that we can 
discriminate between Fig. lb and lc. Figure 2 is a block 
diagram of the proposed system and shows the general 
structure of the process. This paper now considers the 
methodology and reviews some of the problems encountered in 
implementation. 
relief plate 
   
  
image coding for contour lines 
and inter-contour regions 
| construct contour tree] 
topological rules 
\ 
| apply topological rules | 
height information 
/ 
| oriented contour tree | 
Fig.2: Block diagram of the automatic 
contour labeling system 
   
  
  
  
  
  
  
METHODOLOGY 
The project began by implementing the methodology proposed 
by Sircar and Cebrian (1991), but based on some topological 
rules that governed the relationship between contours. 
Construction of Contour Tree 
The tree structure is a graph with nodes and edges. Using 
edges to symbolize the contour lines and nodes to symbolize 
the inter-contour regions is an appropriate way of constructing 
the contour tree in light of rebuilding neighborhood 
relationships and for error detection. A tree without any 
directional information is called a free tree, whereas a tree with 
contour elevations attached to the edges (thus providing 
directional information) is called a directed tree. An adjacency 
matrix can also be used to represent the same structure.