GISdevelopment.net ---> AARS ---> ACRS 1989 ---> Digital Image Processing 1 Efficient preprocessing of generating DEM from digitized contour map Koji Kajiwara, Ryutaro Tateishi Remote Sensing and Image Research center, Chiba university 1-33, yayoi-cho, Chiba City, Chiba, Japan Abstract In order to reduce the processing time and human power in reprocessing of generating DEM from digitized contour map (raster image), an efficient method is proposed as follows: High speed and simple algorithm for automatic processing in some parts of editing digitized contour image. Interactive editing procedure utilizing information obtained by automatic editing processing in the other parts. A automatic recognition of numerals on principal contour lines for efficient assignment of altitude to contour lines. Introduction For the generation of Digital Elevation Model (DEM) from digital raster image which digitized from topographic maps, it is necessary to identify the contour lines and assign altitude to them. At present, this preprocessing requires much time and enormous accumulated topographic maps to be digitized, it is important to develop efficient method. However, it is difficult to develop the full automatic system including editing process. If such a system developed, it will be high cost system which needs powerful computer for the complex algorithm. So we propose to combine the automatic processing with interactive processing effectively. This approach enables the automatic processing algorithm can be realized by utilizing the information which obtained in automatic processing. Methodology Fig. 1 shows the outline of processing. First, multi level contour image is produced by digitizing a topographic map using the drum scanner. Binary contour image which is the object of editing process is built by binrizing multi level contour image. Multi level contour image and binary contours image are source of preprocessing. After first step of editing process, all contour liens on both multi level image and binary level image are traced., In this process, various information is obtained. We call this information contour attribute (described in detail in the section 4). The contour attributes stored in attribute file. This file and edited binary contour image will be final output of preprocessing after modification of editing, recognizing principal lines, recognizing numerals represented altitude and assignment of altitude to contour lines. As shown in Fig. 1, basic processing form is analysis of the information read from attribute file and modification of the attributes by results of processing. In this study, we propose the method of altitude assignment which is composed of two steps. In the first step, altitude is assigned to principal contour lines using recognitions of numerals which represent height value. The intermediate contour lines are assigned in the second step utilizing the height value of principal contour lines. To realize this method, identification of principal contour lines and recognition of numerals are required. Fig. 1 Flow of processing Topographic map for digitization In this study, we use the 1:25, 000 scale contour map made by Geographical Survey Institute of Japan. Principal contour lines and intermediate contour lines are drawn on 1:25,000 scale contour map. The height interval of principal contour lines is 50 m and that the intermediate contour lines is 10 m. Therefore, there are four intermediate contour lines between neighboring principal contour lines. This contour maps has some map symbols such as cliff, rocks, depression in addition to the contour lines and numerals indicating the altitude. To make a multi level contour image, this contour amp was scanned by drum scanner with 50 um pitch. Binary this contour map was scanned by drum scanner with 50 um pitch. Binary contour image is made from multi level contour image by binarizing and thinning. Attributes of contour After removing the isolated point noise and unnecessary branches, all lines one the binary and multi level contour image is traced to collect the contour attributes as follows. Location Coordinates of start point and end point of a contour line. Length Total number of pixels which compose an traced line. Continutity of contour Contour lines before connecting process can be classified into four types from their continuity as shown in Fig. 2. Attribute of numerals This is a flag indicating the possibility of certain traced line whether it is a numeral or not. In the line tracing process, lines on contour image are not identified whether they are contours or numerals. But it can be said that broken or closed short lines have a possibility to be numerals. Sum of digital count Total sum of digital count in a line is obtained by tracing the multi level contour image. After connecting process, the average count of each line is calculated from its length and the sum for identification of the principal line. Fig. 2 Four types of continuity of contour line. A. CONTINUE B. BREAK 1 C. BREAK 2 D. CLOSE Editing digital contour image Editing branch off points First, branch off points are found by raster scan with 3 x 3 pixels window and analyzed their structure by line tracing. Most branch off points caused by binarizing and thinning process have simple structure. It is easy to edit them automatically. Fig. 3. shows the branch off points which have simple structure and short branches. All branches are traced from branch off point, and the number of branches and their length and direction are examined. It is easy to find unnecessary branches and remove them automatically in the case of Fig. 3. Map symbols such as cliff, however, make complex branches. In this case, editing to remove unnecessary lines in themselves. Therefore, the interactive processing was proposed to edit appropriately. Connecting broken lines Very simple algorithm was used to connect broken contour lines. That is "When searching inside of the circle with radius r, centered on a certain break point , if another break point is found, connect these points by the straight line". Using this method with fixed radios r, however, many disconnected lines will remain. If r is small, it will be seldom to success the searching. In the opposite case, there will be high probability that more than two break points are found in the circle. Then iteration method with growing r is proposed in order to decrease the above effect. Fig. 3 Simple structured branches which are edited automatically. Recognition of principal contour lines The output digital count of contour lines from drum scanner is influenced by their width. The averages of digital count of principal contour lines is relatively higher than intermediate lines. It is possible to categorize the distribution of average value into two categories by the threshold which maximized the separability of principal contour lines and intermediate contour lines. Principal contour lines are identified by this method. Recognition of Numerals Since numerals are drawn with contour line in the digital contour image, it is necessary to identify the numerals at first. The numerals on the 1:25,000 scale contour map have some characteristics which are 1) the lowest figure is always '0' 2) numerals always on the principal contour Lines, 3) direction vector' (which is the direction from highest figure to lowest figure) is not always horizontal, but no numerals is displayed up side down. Using the characteristics, numerals on the principal contour lines are identified. It is necessary to analyze the shape of each digit to obtain the value represented by numerals. Fig 4. shows the 'direction vector' (SE) and the tangential vector of digit (a1,a2,... b1, b2, ...) 'direction vector' is the direction of sequence of digit. Fig. 5 shows variation of cosine of the angle between 'direction vector' and the tangential vector along the curve on each digit. Each digit can be recognized by the characteristics of fluctuated curves. And that means it is possible to obtain height value of the principal contour lines which has numerals on themselves. Fig. 4 Tangential vector of digit and direction vector. Fig. 5 Fluctuation of cosine of the angle between direction vector and tangential vector. Table 1:Result of auto editing   Before auto editing Afterauto editing Isolated points Branch of points 161 504 0 92 'CONTINUE' type contours 'BREAK 1' type contours' 'Break 2' type contours 'CLOSE' type contours Total amount of contours 138 239 484 72 933 243 29 49 96 417 Altitude assignment to contour lines Recognition of numerals gives the height values to principal contour lines. However, principal contour lines do not always have numerals on themselves. It is necessary to assign altitude using the interactive methods. For intermediate contour lines. altitude assignment is performed using the height value of principal lines. In General, there are four intermediate contourlines between neighboring principal contour lines. If altitude of both principal lines are already known, it is easy to obtain height value of each intermediate contour lines. Experimental results Except altitude assignment, above mentioned algorithms are verified using the micro computer system. The size of contour image for processing is 3072 x 3072. Table 1. Shows the result of auto editing. Both branch off points and broken contour lines are fairly reduced. Fig. 6. shows the fact that most of remaining branch off points are parts of the map symbols like cliff. The result of connecting process of the broken contour lines is shown in Fig. 7. Note that digit '5' is not connected to contour lines. In connecting process, attribute of numerals' was referenced in order to prevent the connection of numerals and contour lines. The result of recognizing principal contour line and numerals is shown in Fig. 8. White lines are principal contour lines and green lines are intermediate contour lines. Numerals are indicated by yellow color. Conclusion The proposed method of preprocessing to generate DEM includes following characteristics. Combining the automatic processing and interactive processing efficiently. Numerals on contour image are recognized automatically Experimental result indicate the possibility to actualize the efficient processing system. Output of the processing resented in the paper are applicable to both of vector type processing and raster type processing as the subsequent processing to generate DEM. We are continuing this research work and, we will verify we will verify all algorithms of our method and develop the optimized system. Acknowledgements The authors would like to express their sincere thanks to Map Information Office of Map Management Department, Geographical Survey Institute of Japan for their permission to utilize contour maps for this research. Fig. 6 The interactive edition (a) Distribution of branch off points after auto editing. (b)Editing of cliff mark which is delimited white rectangle in (a). Fig. 7 The result of auto connecting process. (a) Before processing . (b) After processing Connected parts are colored as red. Fig. 8 The result of auto recognizing process of principal contour lines and numerals. White lines : Principal Contour lines Green lines : Intermediate contour lines Yellow lines : Numerals.