As figure 1 demonstrates, without human intervention or 
additional attribute information, non-closed contours can be 
irresolvable. Artificial intelligence techniques can be used to 
suggest 'likely' solutions, but in the absence of further 
information, (for example, by inspection of adjoining map 
sheets and expansion of the tree), solution may not be 
definitive. If the area of interest is morphologically simple, this 
may involve the inspection of many adjoining map sheets! 
IMPLEMENTATION 
The digital implementation is comprised of three main 
processes. They are: contour and inter-contour coding from a 
scanned relief plate; creating a contour tree from the coded 
image, and applying topological rules to order the contour tree. 
The input data is the relief plate of a topographic map. The 
other input data that is then required is height information 
available on a separate plate. For example, on a USGS 
1:24,000 7'.5 x 7.5 quadrangle, height information includes 
horizontal controls, vertical controls, boundary monuments, 
intermediate contours, index contours, supplementary 
contours, and depressions. Such information could be read 
using Optical Character Recognition (OCR) technology 
(Musavi et. al., 1988). 
A desktop scanner was used to scan the relief plate. The image 
of the contour lines is represented by 1s and Os for contour 
lines and inter-contour regions respectively. The depth-first 
search algorithm is applied to assign a unique identifier for 
pixels that belong to the same region. At this stage, the width 
of either contour lines or inter-contour regions is normally 
larger than one pixel size so they can all be treated as regions. 
The values assigned to contour lines are different from the 
values of the inter-contour regions. A search algorithm based 
on breadth-first graph traversal checks the connectivity of every 
pixel to a branch of the contour tree. 
Once the free tree has been formed, topological rules can be 
used to determine the furthest branches that need to be ‘seeded’ 
in order to complete most of the tree. 
Efficiency of matching contour line with its corresponding 
heights can be improved by setting search constraints. 
Matching the orientation and scale of both the contour and 
height information plate reduces the search time. 
For ease of data manipulation, the linked list data structure was 
adopted in this approach. The linked list is a record of three 
fields. The first field is a pointer for identifying the region. 
The second field contains attribute data describing the 
properties of this region, such as elevation, size, 
neighborhood, etc.. The third field is composed of all the 
pixels that fall in this region. The run-length code is an 
appropriate structure to chain the pixels. 
To derive the elevation order of two adjacent closed contours, it 
is essential to know their relationship. A simple intersection 
test will tell the relationship. Figure 5 explains the test that 
checks the number of intersections from any point within one 
contour line region. If the number of intersections is odd, the 
contour that the point belongs to is inside the other contour, and 
vice versa. In Figure 5, L1 has 4 intersections, and begins 
inside the contour; L2 has 3 intersections and lies outside the 
contour. In general, larger size contours will enclose smaller 
size contours. But this is not necessarily always true (Fig.5). 
There are three possible elevations for a contour when 
compared with its adjacent contour: one contour interval lower, 
one contour interval higher, or equal elevation. The topological 
rules will decide which one is correct. Figure 6 illustrates the 
unique and ambiguous solution in height ordering among a set 
of contours. In this instance, elevation of contour line L1 is 
known (14 meter). L2 has three possible elevations compared 
with L1, and so has L3 compared with L2. If L3 is unknown, 
then L2 is ambiguous; whilst if L3 is known (e.g., L3=16 
meter), then L2 can be uniquely defined. 
268 
  
  
  
  
Fig.5: Method to test the closure relation between 
two closed contours. 
  
13 
14 1 
p nn EPA -- AN e. - 
C 
13 14 15 14 1 
p 12 13 — 14 5 16 
5 
X 
L2 
  
  
then L2 is ambiguous; 
L3 if L3 is known (e.g., 16m), 
then L2 is unique, 
(L2 can only be 15m). 
c(B given L1 =14 m; 
D (Co if L3 is unknown, 
E 
  
  
  
Fig.6: An example illustrates the ambiguous and the 
unique solution. 
Merging the adjacent maps might result in a closed contour and 
may consequently create a unique solution. This is illustrated 
in Figure 7. 
  
     
I 
  
  
  
Fig.7: Merging the adjacent maps might 
result in closed contours and consequently 
creates unique solutions. 
As figure 1b and 1c demonstrate, without human intervention 
or additional attribute information, non-closed contours can be 
irresolvable. The process described above will eventually end 
up at a stage where some contours are labeled and some are 
not. Because the tree associates those pixels belonging to a 
particular node, it is relatively simple to graphically highlight 
the unsolved contour and provide suggestions as to which 
contour should be manually tagged to solve the whole tree.