GISdevelopment.net ---> AARS ---> ACRS 1995 ---> Poster Session 4 A Development of DEM Generation System Jaeyeon Lee, Kiyonari Fukue, Haruhisa Shimoda and Toshibumi Sakata Tokai University Research and Information Center 2-28-4 Tomigaya, Shibuya-ku, Tokyo 151, Japan Tel+81-3-3481-0611 FAX+81-3-3481-0610 Abstract A DEM generation system which generates DEM from topographic map is reported. In the developed system m a new restoration algorithm which uses adjoining relationship between contour lines is adopted By using the new algorithm, throughput of the system is improved quite largely (5 to 24 times compared to surveyed methods). Also by using contour/grid conversion algorithm which utilizes Euclidean distance transformation, DEM of good quality can be generated. 1. Introduction DEM (Digital Elevation Model) is seriously needed from various fields of science, practical applications, environmental researches and/or natural disaster analysis. However, the available DEM is so scarce compared to the necessity. Generally, DEM is generated from the topographic map by recognizing the contour on the map and convert it to grid data using contour/grid conversion algorithm however, the process is very costly, and there are many cases where the quality of acquired DEM is not satisfactory. This paper is to report the newly developed DEM generation system which provides an integrated functionality for the process of generating DEM from the topographic map. In the developed system restoration of extracted contour image which had been the most time-consuming task in the flow, is automated. Also, the system provides new contour/grid conversion functionality which can generate DEM of quite good quality. Further, the system is implemented on Microsoft Windows NT Operating System which supports wide variety of computing environments including personal computers and workstations. In this paper, the configuration of the system and the algorithms for restoration and contour/grid conversion is described. Also, the evaluation results will be presented. 2. System Configuration The configuration of the developed system is very simple and no special hardware is included as shown in fig.1. The system operates on the personal computer and uses color scanner for scanning topographic map. Figure 1 Haedware Configuration of the System Fig.2 is the processing flow of the system. A scanned topographic map is imported via input module and mosaiced if necessary. In mosaic module, multiple pages of the topographic map is merged so as not to make gap between pages by converting the coordinate system of the topographic map to latitude-longitude coordinate system. Figure 2 Processing Flow of the System In the next step, contour is extracted from the map by using the color and line width parameter. Actually, a neural network whose input is R,G,B components of each pixel is used for color extraction and kasvand filter is applied to the result of neural network for thin line extraction. Even though the contour extraction module showed good performance, there still exist quite large number of cut lines in the extracted contour image. To restore them, the contour image is processed by restoration module (the detail of the restoration algorithm will be described later). After restoration labeling module assigns respective elevation for each contour lines by interactive operation with human. Up to labeling, the resolution of the image is quite high (approximately 300dpi). However, the original data, topographic/Grid conversion process. shrinking module shrinks the image conserving the connectivity of the contours. By applying contour/ Grid conversion algorithm (the detail of the algorithm will be described later),DEM is generated and finally the data is converted to coordination system of user specification. 3. Restoration of contour Image Beside of contour lines, topographic map includes many symbols, characters and various kinds of lines, which make the image very complex. Generally, it is inevitable that extracted contour image contains a large number of cut lines (hence, ending points). This is why restoration process is required. However, because of the complexity of the contour image, it is very difficult to restore the cut lines. Even though there has been reported many algorithms for this problem, those algorithms had achieved only limited success and seldom used in the field. In the previously reported algorithms. only local relationships between ending points are used for the restoration. In the developed system, a new restoration algorithm utilizing relation has global characteristics and is able to recognize the structure of the contour image. Fig.3 shows the basic idea of the adopted restoration algorithm. That is, if both of the contour C1 and C2 is adjoined with L1 and L2 then C1 and C2 should be the contours of same height and need to be connected. Figure 3 Basic Idea for the Restoration Algorithm With consideration of the above idea. the proposed restoration algorithm restores the contour image in two stage operations. In the first stage, the traditional restoration method which uses local relationships between ending points is applied. By this processing, a short and simple cut lines can be restored. And in the second stage, the adjoining relationship is applied to the contour image for more efficient restoration. The experimental result is shown in Table 1. At the time of extraction, these had been 130 ending points in the image. After the first stages processing, It is lessened to 62, about half of the ending point is eliminated, In traditional restoration algorithms, the processing is terminated at this point and the remaining ending points should be restored by human operator. Table 1 Experimental Result   Contour Image After 1st Stage Finale Result Number of Endings 1 3 0 (100%) 62 (48%) 8 (65) On the contrary in the proposed method. a second stage processing is applied and the number of ending points is lessened to 8, that is only 6% of the original ending points remains. 4. Contour/Grid Conversion Contour/Grid conversion is a so extensively researched topic and there has been reported a lot of algorithms for this problem. However, the available algorithms often generates peculiar grid data which contains unnatural linear incontinuities as shown in Fig.4. Figure 4 Quality Problem of the Previously Proposed Algorithms In general contour/grid conversion process consists of the two sub-operations. This is, searching for the standard points for the interpolation and interpolation itself. Among the two sub-operation the later is straight-forward and not so much problem. Mainly the former is thought to be the cause of the peculiar results . for example, Fig.5 shows a well-known contour/grid conversion algorithm, in which a contour map is scanned, and the detected contours are interpolated by a spline curve. As shown in the figure, the standard points for interpolation abruptly changed at the scan point indexed by an arrow mark, which results in the incontinuity of the grid data as shown in (b) of the figure. Figure 5 Cause of Incontinuity In the developed system, a new contour/grid conversion algorithm which do not require the searching for the standard points for interpolation is adopted, In the proposed algorithm, instead of searching process, contour itself is propagated to the region by Euclidean distance transformation. As a result of the transformation, the distance to the contour to the contour from every to-be-interpolated points is automatically obtained2). Fig.6 (a) is the experimental contour image, and Fig.6(b) is the result generated by adopted algorithm. The incontinuities scattered in Fig.4 is not shown in the result and the quality of the DEM is quite satisfactory. Figure 6 Experimental Result 5.Evaluation To evaluate the performance of the developed system, a throughput which is defined as a time to generate DEM from a topographic map is measured (a.1:25,000 topographic map published by Japanese geographical survey institute is used). also, throughput of the methods which are adopted by the organizations who generates DEM from topographic map is surveyed for the comparison. Table 2 is the result. Because the flows of the surveyed methods vary, each operation steps are grouped into contour recognition(includes contour extraction and restoration), labeling and contour/grid conversion. As shown in the table, totally 40 to 207 hours for 1 page of topographic map. On the contrary, in the developed system, only 8.5 hours were necessary. Table 2 Comparison on the Throughout   Surveyed Methods Developed   A B C System Contour Recognition 32.0 92.0 200.0 3.5 Labeling 4.0 8.0 5.0 3.0 Contour/Grid Conversion 4.0 0.5 2.0 2.0 Sum 40.0 100.5 207.0 8.5 6.Conclusion Even though there exist wide need for DEM, it has been very difficult to satisfy them because of lack of efficient DEM generation technology. In this paper, a new DEM generation system is reported . In the developed system a new restoration algorithm is adopted, which resulted in 5 to 24 times improvement of throughput. Also, by using a contour/grid conversion algorithm which uses Euclidean distance transformation, DEM of satisfactory quality could be generated. References Lee, Fukue, Shimoda,Sakata,"Restoration of contour image by using adjoining property", journal of the Japan society of photogrammetry and Remote sensing, Vol.34.No. 2,pp45-53. 1995. Lee. Fukue, shimoda, sakata, "A contour/grid conversion method by using euclidean distance transformation," journal of the Japan society of photogrammetry and remote sensing, Vol.33.No.6,pp26-34, 1994.