WO2013057760A1

WO2013057760A1 - Digital elevation model generating system and method of generating a digital elevation model

Info

Publication number: WO2013057760A1
Application number: PCT/JP2011/005838
Authority: WO
Inventors: Tao Guo
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 2011-10-19
Filing date: 2011-10-19
Publication date: 2013-04-25
Anticipated expiration: 2014-04-19

Abstract

It is provided a digital elevation model generating system, comprising: a reception module for partitioning the input contour map into a triangulated irregular network; a marking module for marking each of triangle patches as flattened or non-flattened; a TIN calculating module for generating sub-contour lines by interpolation using the triangulated irregular network in the non-flattened region; a vector field generating module for calculating a vector field in which each vector represents a spatial effect of neighboring contour lines for the flattened region; a sub-contour line generating module for determining a curve on which vectors have the same magnitude; and a sub-contour line connecting module for generating a newly integrated sub-contour line by creating a buffer in a neighborhood of a boundary between a non-flattened region and the flattened region, and by smoothly linking the curve in the non-flattened region and the curve in the flattened region in the buffer.

Description

DIGITAL ELEVATION MODEL GENERATING SYSTEM AND METHOD OF GENERATING A DIGITAL ELEVATION MODEL

This invention relates to a technology for generating sub-contour lines from existing contour lines of a digital topographic map by means of interpolation.

A digital elevation model (DEM) is one of the most important fundamental data in a geographic information system (GIS) and is normally acquired from field survey, measurement on aerial photos, 3D matching from stereo pair of remote sensing images, and 3D point cloud of a set of points acquired from laser scanning. The DEM is available at a certain scale due to its data source and generation method. Moreover, the scale determines the interval between contour lines.

However, it is quite normal for many applications to demand a fine and detailed DEM. A triangulated irregular network (TIN) model is conventionally a dominant method adopted in the GIS and the related industries to generate and interpolate the DEM. However, the TIN model poses a problem that saddle regions, gentle slopes of ridges are marked as flattened, which results in a strange deformation in terrain representation.

The algorithm of the TIN model is to form the triangulated regions from three nodes on contour lines and interpolation is implemented in each triangle. Therefore, the interpolation employing the TIN model is fast and simple, and is thus widely used. The TIN model exhibits a high performance in representing a terrain with a sharp slope.

Moreover, various methods are being studied to solve the deformations of terrain in the DEM as disclosed in Patent Literatures 1, 2, and 3.

JP 2010-198544 A JP 2007-48185 A JP 2006-293105 A

According to the above-mentioned TIN model, if all three nodes are selected on the same contour line with the same elevation, the terrain in the triangle is treated as a horizontal surface. Particularly, the nodes of a triangle may be placed on a contour line with the same elevation on a terrain such as a saddle region and a gentle slope of a ridge, the interpolation using the TIN model often determines this region as flat, and the terrain of the triangle patch is thus considered as flat, resulting in strangely deforming the terrain, and affecting the generation of the DEM.

The weak points of the TIN model, such as influence of the above-mentioned flattening, have not been studied for a long time.

This invention has an object to propose a method of generating a highly-accurate DEM by gently interpolating the elevation particularly on a saddle region and a ridge, and generating new contour lines.

A representative example of the disclosed invention in this application calculates a vector field gradually changing from one boundary to another on a flattened region, smoothly interpolates the elevation, and generates sub-contour lines.

That is a digital elevation model generating system, comprising: a storage unit for storing a contour map; a processing unit for carrying out an interpolation process for generating sub-contour lines; a memory for storing a program to be executed by the processing unit; an input unit for receiving an input of the contour map; and an output unit for outputting a generated elevation map. The processing unit includes: a reception module for partitioning the input contour map into a triangulated irregular network; a marking module for marking each of triangle patches as flattened or non-flattened, and merging the triangle patches marked as flattened to form a flattened region; a TIN calculating module for generating curves serving as sub-contour lines by means of interpolation using the triangulated irregular network for the triangle patch marked as non-flattened; a vector field generating module for calculating a vector field in which each vector represents a spatial effect of neighboring contour lines for the flattened region; a sub-contour line generating module for determining a curve on which vectors have the same magnitude; and a sub-contour line connecting module for generating a newly integrated sub-contour line by creating a buffer in a neighborhood of a boundary between a non-flattened region constituted of the triangle patches marked as non-flattened and the flattened region, and by smoothly linking the curve in the non-flattened region and the curve in the flattened region in the buffer. The output unit outputs a digital elevation model containing the interpolated sub-contour lines.

According to the representative aspect of this invention, a highly-accurate DEM can be generated.

Fig. 1 is a block diagram illustrating a configuration of a matching system according to an embodiment of this invention. Fig. 2 is an overall flowchart of processing of generating a digital elevation model according to the embodiment of this invention. Fig. 3 is an explanatory diagram illustrating triangle patches generated in the embodiment of this invention. Fig. 4 is an explanatory diagram illustrating triangle patches generated in the embodiment of this invention. Fig. 5 is an explanatory diagram illustrating generation of effect vectors according to the embodiment of this invention. Fig. 6 is an explanatory diagram illustrating generation of sub-contour lines according to the embodiment of this invention. Fig. 7 is an explanatory diagram illustrating determination of the elevations of the sub-contour lines according to the embodiment of this invention. Fig. 8 is an explanatory diagram illustrating connecting of the sub-contour lines according to the embodiment of this invention. Fig. 9 is an explanatory diagram illustrating an effect vector field generated by the processing of generating the digital elevation model according to the embodiment of this invention. Fig. 10 is an explanatory diagram illustrating a generation of TIN according to the embodiment of this invention.

Fig. 1 is a block diagram illustrating a configuration of a digital elevation model (DEM) generating system according to an embodiment of this invention.

The DEM generating system of this embodiment is a computer including an input unit 110, a display unit 120, a data storage unit 130, a processing unit 140, an elevation map output unit 150, and a storage unit 160. The input unit 110, the display unit 120, the data storage unit 130, the elevation map output unit 150, and the storage unit 160 are connected with each other through the processing unit 140 (or mutually through a bus).

The input unit 110 includes a map input unit 111 and a parameter input unit 112. The map input unit 111 is an interface used for receiving an input of a digital contour map, and is constituted of an optical disc drive, a USB interface, and the like, for example. The parameter input unit 112 is a device used for receiving an input of parameters (such as the number and interval of sub-contour lines to be generated) used for processing of interpolating the sub-contour lines, and is constituted of a keyboard, a mouse, and the like, for example. It should be noted that the parameter input unit 112 may receive an input of individual parameters, or a set of parameters prepared in advance depending on the interval of the sub-contour lines to be generated.

The display unit 120 includes a map displaying unit 121 and a parameter displaying unit 122. The map displaying unit 121 is a display device for displaying a map to be processed by this system. The parameter displaying unit 122 is a display device for displaying parameters to be used for the processing of interpolating the sub-contour lines. It should be noted that the map displaying unit 121 and the parameter displaying unit 122 may be constituted of the same display device or independent display devices.

The data storage unit 130 is a non-volatile storage device for storing data for the digital contour map to be processed by the system, and is constituted of a magnetic disk device, a non-volatile memory, or the like, for example. The processing unit 140 includes a processor, and carries out processing to be carried out in this system by executing a program loaded on the memory.

The elevation map output unit 150 is a device for outputting a result processed by this system as a vector form or an image form, and is constituted of a printer, a plotter, or the like, for example.

The storage unit 160 is a storage device for storing the program to be executed by the processing unit 140, and is constituted of a hard disk drive, a non-volatile memory, or the like, for example. The storage unit 160 stores sub-programs 161-167 for installing each of a reception module, a marking module, a TIN calculating module, a vector field generating module, a sub-contour line generating module, a sub-contour line connecting module, and a terrain deviation determination module. DEM generating processing (Fig. 2) is installed by the processing unit 140 executing those programs.

The reception sub-program 161 acquires the contour map input to the map input unit 111, and partitions a region to be processed into a triangulated irregular network (TIN). The marking sub-program 162 marks each triangle patch as flattened or non-flattened, and merges the triangle patches marked as flattened to form a flattened region. The TIN calculating sub-program 163 interpolates sub-contour lines by using the TIN in the triangle patches marked as non-flattened (non-flattened region).

The vector field generating sub-program 164 generates a vector field constructed by vectors representing a spatial effect of surrounding contour lines for the flattened region. The sub-contour line generating sub-program 165 defines a curve on which a vector at every location has the same magnitude. The sub-contour line connecting sub-program 166 smoothly links the sub-contour lines in a buffer provided in a neighborhood of a boundary between the non-flattened region and the flattened region. The terrain deviation determination sub-program 167 determines whether the sub-contour line is higher or lower than the neighboring contour lines.

Fig. 2 is a flowchart of the DEM generating processing according to the embodiment of this invention.

First, the map input unit 111 receives an input of a contour map on which sub-contour lines are to be interpolated (S1). This contour map includes data on a plurality of contour lines. The input contour map is digitized data, and is to be stored in the data storage unit 130.

Moreover, the parameter input unit 112 receives a specification of a region 301 as illustrated in Fig. 3 in which sub-contour lines are to be generated in the input contour map.

The processing unit 140 provides points at a predetermined interval on contour lines in the specified region by executing the reception sub-program 161. The interval of the points provided on the contour lines is input to the parameter input unit 112, and a small value is set to the interval if the number of sub-contour lines to be generated is large.

The processing unit 140 then selects two neighboring points on a certain contour line, and selects a point on a neighboring contour line which has the shortest sum of the distances from the selected two points. It should be noted that the neighboring contour line includes both a contour line at a different elevation and a contour line at the same elevation. Then, the processing unit 140 generates a triangle patch using the selected three points. Fig. 3 illustrates a state in which triangle patches are generated in a specified region 301.

Then, the processing unit 140 marks the generated triangle patches to a flattened region or a non-flattened region by executing the marking sub-program 162 (S2). Specifically, this marking compares the elevations of the contour lines on which the points are set, and determines that the triangle patch is a flattened region when the elevations of the three vertices of the triangle patch are equal, and the triangle patch is a non-flattened region when at least one elevation is different.

For example, in the contour map of Fig. 3, triangle patches AFB, FBG, BGC, GCH, CHD, HDI, and DIE have vertices on contour lines at the same elevation, and are marked as flattened regions. Moreover, in Fig. 3, the other triangle patches have at least one vertex on a contour line at a different elevation, and are thus marked as non-flattened regions.

Moreover, in a region 401 in a contour map illustrated in Fig. 4, triangle patches BFE, BEC, and ECD are formed by points on a contour line at the same elevation as vertices, and are thus marked as flattened regions. Moreover, triangle patches AHB, BHF, and FHG are formed using at least one point on a contour line at a different elevation as a vertex, and are thus marked as non-flattened regions.

In other words, a saddle region between contour lines of 200 m illustrated in Fig. 3, a gentle slope of a ridge in a contour line of 100 m extending toward the left in Fig. 4 out of terrains contained in the contour maps are marked as flattened regions. According to the conventional TIN model, those flattened regions are marked as planes, and thus sub-contour lines cannot be generated.

The processing unit 140 merges neighboring triangle patches marked as non-flattened regions to form one wider non-flattened region, and merges neighboring triangle patches marked as flattened regions to form one wider flattened region by executing the marking sub-program 162. It should be noted that it is not necessary to merge triangle patches in a non-flattened region to which the conventional TIN is applied.

The processing unit 140 generates sub-contour lines using the TIN model in the merged non-flattened region by executing the TIN calculating sub-program 163 (S3), and generates sub-contour lines according to the method proposed by this specification in the merged flattened region (S4, S5). The method of generating sub-contour lines according to this invention requires a larger calculation amount than the method using the TIN model, but the overall calculation amount can be reduced while accurate sub-contour lines can be generated by applying the method according to this invention only to a flattened region.

According to the DEM generation method according to this embodiment marks regions in which sub-contour lines are to be generated as non-flattened regions and flattened regions, and applies the method according to this invention only to the flattened regions, but the method according to this invention may be applied to all the regions in which sub-contour lines are to be generated.

First, a description is given of the generation of sub-contour lines according to the TIN model applied to the non-flattened regions in Step S3.

The TIN model is represented by triangles continuously in contact with each other without overlapping, and a ground surface is represented by a plane in each of the triangles. The triangles can be selected at any location, and the accuracy of the surface model increases even for a location at which the surface shape drastically changes if nodes are properly selected.

To generate TIN from contour lines, Delaunay triangulation is a popular triangulation method, which is able to guarantee that a circle drawn through the three nodes of a triangle include no other node. In general all the vertices of the contour lines can be selected as nodes of the triangles to generate TIN. It is usually efficient to choose widely spaced nodes in regions where there is little variation in elevation whereas in areas of more intense variation in elevation the node density is increased.

As illustrated in Fig. 10, point set1 {a1, b1, c1} and point set2 {a2, b2, c2, d2} are randomly selected from contour L1 and contour L2 respectively. The Delaunay triangulation can be implemented in an incremental way, that is firstly to form a triangle, for example b1-a2-d2, then add the remains of points into this triangle to make a patch of triangles, then remove the triangles whose bounding circle includes other points. Repeat these steps until all points are included the triangles.

Once the TIN is formed, the height value at any location p within a triangle can be calculated through an interpolation of height values of the nodes of the triangle. As described above, sub-contour lines whose height values are between contour L1 and L2 can be easily generated.

The contour lines are a common data source for digital elevation data used for generating a TIN model. In general, an inflection point of a contour line is selected as a vertex of a triangle constituting the TIN model. Nodes which can partition a wide region in which the elevation hardly changes are usually efficient. On the other hand, density of nodes may be increased in a region in which the elevation changes drastically.

Next, a detailed description is given of the processing (S4, S5) of generating sub-contour lines according to the method proposed in this specification.

In Step S4, as illustrated in Fig. 5, the processing unit 140 provides a point A in a flattened region first by executing the vector field generating sub-program 164. Though Fig. 5 illustrates the one point A, as illustrated in the vector field of Fig. 9, the points A are provided in the form of a mesh at a predetermined interval in the flattened region.

Moreover, two contour lines C1 and C2 neighboring the point A are determined, a point Pi is provided on the contour line C1, and a point Qj is provided on the contour line C2.

Then, effect vectors Vpij and Vqij are defined at the point A. The directions of the vectors Vpij and Vqij are respectively directions from the point A to the point Pi and to the point Qj, and the magnitudes thereof are represented by the following equations.
|Vpij|=|AQj|/(|APi|+|AQj|)
|Vqij|=|APi|/(|APi|+|AQj|)
In the above-mentioned equations, |APi| is the distance between the point A and the point Pi, and |AQj| is the distance between the point A and the point Qi.

Then, the effect vectors Vpij and Vqij are calculated for all combinations of the point Pi and the point Qj in the flattened region, and the calculated effect vectors Vpij and Vqij are summed to calculate a resultant vector V. As a result, the vector V which is the accumulation of all effects from the neighboring two contour lines C1 and C2 is obtained. It should be noted that the resultant vector V is divided by the number of accumulated vectors. In this way, the magnitude of the vector V is 1 on each of the contour lines C1 and C2, and the magnitude of the vector V is 0 on a center line of the contour lines C1 and C2.

As illustrated in Fig. 9, a vector field of the effect vectors is generated by repeating the processing described above for all the points A. This vector field changes smoothly between the contour lines C1 and C2, and this vector field can be used to interpolate the elevation between existing contour lines.

Then, in Step S5, a sub-contour line is generated by connecting points at which the magnitudes of calculated effect vectors are the same.

Specifically, first, as illustrated in Fig. 6, the processing unit 140 obtains a center line S of the two contour lines C1 and C2 by executing the sub-contour line generating sub-program 165. The effects from the two contour lines C1 and C2 are the same at a point on this center line, and the magnitude of the effect vector is 0. Accordingly, points A at which the magnitude of the effect vector is 0 or equal to or less than a predetermined small threshold are retrieved in the region between the two contour lines C1 and C2, and a curve connecting the retrieved points A is generated. A cubic spline curve may be used for this curve (center line), for example.

Then, the magnitudes of the effect vectors to be selected are determined according to the number of sub-contour lines to be generated. Specifically, when two sub-contour lines are to be generated between the contour lines C1 and C2, two lines are drawn at an equal terrain deviation between the contour lines C1 and C2. In other words, as illustrated in Fig. 6, one sub-contour line is generated each between the contour line C1 and the center line S and between the contour line C2 and the center line S. As described above, the magnitude of the effect vector V is 1 on each of the contour lines C1 and C2, the magnitude of the effect vector V is 0 on the center line S, and the magnitude of the effect vector is thus proportional to the terrain deviation. Therefore, the difference in magnitude of the effect vectors on the sub-contour line is 2/3, which is a value obtained by dividing 2 by (number of sub-contour lines to be generated + 1).

In other words, by selecting vectors whose magnitude is different from the contour line C1 by 2/3 (vectors whose magnitude is 1/3), one sub-contour line can be generated between the contour line C1 and the center line S. Moreover, by selecting vectors whose magnitude is different from the contour line C2 by 2/3 (vectors whose magnitude is 1/3), one sub-contour line can be generated between the contour line C2 and the center line S.

It should be noted that the center line S is designated as a sub-contour line in the case where one sub-contour line is generated between the contour lines C1 and C2.

Then, the vectors having the determined magnitude (1/3) are selected in the region between the contour line C1 and the center line S, and points corresponding to the vectors are connected with each other. On this occasion, the selected vectors are the same in magnitude, but are different in direction. Then, the points corresponding to the selected vectors are connected with each other, thereby generating a sub-contour line R.

Similarly, the vectors having the determined magnitude (1/3) are selected in the region between the contour line C2 and the center line S, and points corresponding to the vectors are connected. On this occasion, the selected vectors are the same in magnitude, but are different in direction. Then, the points corresponding to the selected vectors are connected with each other, thereby generating a sub-contour line T. Cubic spline curves may be used for the sub-contour lines R and T, for example.

Then, the processing unit 140 determines terrain deviations of the sub-contour lines by executing the terrain deviation determination sub-program 167. An accumulated change in magnitude of the vectors on the contour line C1 to the vectors on the contour line C2 via the center line S is 2. In other words, the total difference in magnitude of the selected vectors is 2, and hence the terrain deviation between the sub-contour lines is a value obtained by dividing the terrain deviation between the contour lines C1 and C2 by 2 and multiplying the resultant quotient by the difference in magnitude of the vectors between the sub-contour lines.

For example, as illustrated in Fig. 6, when the contour line C1 represents the elevation of 200 m and the contour line C2 represents the elevation of 100 m, the terrain deviation (hR-hT) between the newly provided two sub-contour lines R and T is calculated as what is obtained by dividing a terrain deviation 100 m between the contour lines C1 and C2 by 2 and multiplying the resultant quotient by the difference in magnitude 2/3 between the vectors of the sub-contour lines, namely 33.3 (100/3) m. As a result, the sub-contour line R represents the elevation 166.7 m, and the sub-contour line T represents the elevation 133.3 m.

However, a slope of an actual terrain may not be monotonic, and it is necessary to determine whether the interpolated sub-contour line is higher or lower than the existing contour lines C1 and C2. As a result, the processing unit 140 calculates the terrain deviation at the boundary of the flattened region, and determines whether the elevation of the sub-contour line is higher or lower than the elevation of the neighboring contour lines according to the sign of the calculated terrain deviation by executing the terrain deviation determination sub-program 167.

Specifically, as illustrated in Fig. 7, a case of obtaining the elevation h of the sub-contour line S generated between the contour lines C1 and C2 is considered. If the elevation h1 of the contour line C1 is higher than the elevation h0 of the contour line C0, this case implies that the elevation increases from the contour line C0 toward the contour line C1, and the elevation h of the sub-contour line S is h1+0.5*d. On the other hand, if the elevation h1 of the contour line C1 is lower than the elevation h0 of the contour line C0, this case implies that the elevation decreases from the contour line C0 toward the contour line C1, and the elevation h of the sub-contour line S is h1-0.5*d. Further, if the elevation h1 of the contour line C1 is equal to the elevation h0 of the contour line C0, there is a ridge, a valley, or a plain between the contour lines C0 and C1. In this case, an operator determines whether the elevation h of the sub-contour line S is h1+0.5*d or h1-0.5*d based on other information.

Then, the processing unit 140 connects the generated sub-contour lines to each other by executing the sub-contour line connecting sub-program 166 (S6). Referring to Fig. 8, this processing of connecting the sub-contour lines is now described. According to this embodiment, the different methods are used for generating the sub-contour lines between the flattened region and the non-flattened region, and the generated sub-contour lines are not aligned at a boundary between the flattened region and the non-flattened region. It is therefore necessary to smoothly link the sub-contour line in the flattened region and the sub-contour line in the non-flattened region.

First, a rectangular buffer 802 is provided close to the boundary of the flattened region and the non-flattened region. The size d of one side of the buffer 802 in the direction of the extension of the sub-contour lines is preferably determined according to the magnitude of the displacement between the sub-contour line of the flattened region and the sub-contour line of the non-flattened region. In other words, if the displacement between the sub-contour line of the flattened region and the sub-contour line of the non-flattened region is large, the size d of the buffer 802 is preferably increased, and if the displacement between the sub-contour line of the flattened region and the sub-contour line of the non-flattened region is small, the size d of the buffer 802 may be decreased.

Then, an intersection point P1 between a sub-contour line S1 of the flattened region and the boundary of the buffer 802 is set, a center line 803 in the flattened region in the buffer 802 is set, and an intersection point A1 between the center line 803 and the sub-contour line S1 is set. Similarly, intersection points P2 and P3 and intersection points A2 and A3 are set on sub-contour lines S2 and S3.

Further, an intersection point Q1 between the sub-contour line T1 of the non-flattened region and the boundary of the buffer 802 is set, a center line 804 in the flattened region in the buffer 802 is set, and an intersection point B1 between the center line 804 and the sub-contour line T1 is set. Similarly, intersection points Q2 and Q3 and intersection points B2 and B3 are set on sub-contour lines T2 and T3.

Then, a curve U1 connecting the four points, P1, A1, B1, and Q1, with each other is generated. A cubic spline curve may be used for this curve, for example. Then, a newly integrated sub-contour line is generated by using the sub-contour line S1 up to the point P1 in the flattened region, the cubic curve U1 in the buffer 802 (between the point P1 and the point Q1), and the sub-contour line T1 up to the point Q1 in the non-flattened region.

Similarly, the sub-contour lines S2 and T2 are connected through a cubic curve U2, and the sub-contour lines S3 and T3 are connected through a cubic curve U3, thereby generating newly integrated sub-contour lines.

Finally, a DEM is output (S7). The DEM may be vector data or image data in the form of a map containing the generated sub-contour lines.

Next, a description is given of effects of this invention.

This embodiment can generate a highly-accurate DEM. Particularly, accurate sub-contour lines can be interpolated by eliminating a determination that a saddle region or a gentle slope of a ridge in a contour map is determined as flattened by the TIN model. The method according to this invention can thus be adapted to many applications for 3D terrain visualization.

Specifically, the effect vector field generated by the embodiment of this invention represents the effects of two contour lines as gentle changes between the two contour lines as illustrated in Fig. 9. As a result, smooth sub-contour lines can be accurately interpolated.

Moreover, the elevation of any point between two contour lines can be determined without loss of continuity in elevation of surrounding points. Then, sub-contour lines can be calculated in a triangle patch considered as flattened in place of the conventional method employing the TIN model. As a result, a highly-accurate DEM can be generated.

It should be noted that this invention can be applied to any region (non-flattened region) partitioned by existing contour lines in addition to the flattened region. This is because the effect vector field contains all effects from surrounding contour lines. Further, the elevation which is interpolated according to this invention provides smoother interpolation at every location than the conventional method employing the TIN model.

As a result, an optimal balance between efficiency and accuracy is achieved to generate an accurate DEM by simultaneously employing the conventional method employing the TIN model and the method according to this invention on a client terminal. Moreover, also on a server, by combining the conventional method employing the TIN model and the method according to this invention, limitation on computer resources can be relieved and a large and accurate DEM can be generated in a batch manner, thereby supplying high quality DEM data to the client terminal.

While the present invention has been described in detail and pictorially in the accompanying drawings, the present invention is not limited to such detail but covers various obvious modifications and equivalent arrangements, which fall within the purview of the appended claims.

Claims

A digital elevation model generating system, comprising:
a storage unit for storing a contour map;
a processing unit for carrying out an interpolation process for generating sub-contour lines;
a memory for storing a program to be executed by the processing unit;
an input unit for receiving an input of the contour map; and
an output unit for outputting a generated elevation map, wherein:
the processing unit includes:
a reception module for partitioning the input contour map into a triangulated irregular network;
a marking module for marking each of triangle patches as flattened or non-flattened, and merging the triangle patches marked as flattened to form a flattened region;
a TIN calculating module for generating curves serving as sub-contour lines by means of interpolation using the triangulated irregular network for the triangle patch marked as non-flattened;
a vector field generating module for calculating a vector field in which each vector represents a spatial effect of neighboring contour lines for the flattened region;
a sub-contour line generating module for determining a curve on which vectors have the same magnitude; and
a sub-contour line connecting module for generating a newly integrated sub-contour line by creating a buffer in a neighborhood of a boundary between a non-flattened region constituted of the triangle patches marked as non-flattened and the flattened region, and by smoothly linking the curve in the non-flattened region and the curve in the flattened region in the buffer; and
the output unit outputs a digital elevation model containing the interpolated sub-contour lines.
The digital elevation model generating system according to claim 1, wherein the marking module compares elevations of three nodes constituting vertices of each of the triangle patches, marks the triangle patch as flattened when the elevations of the three nodes are equal, and marks the triangle patch as non-flattened when the elevation of at least one of the three nodes is different.
The digital elevation model generating system according to claim 1, wherein the vector field generating module is configured to:
define, for a point A in the flattened region, an effect vector Vap whose magnitude decreases as a distance between the point A and a point P on a first contour line increases, and an effect vector Vaq whose magnitude decreases as a distance between the point A and a point Q on a second contour line next to the first contour line increases;
repeatedly calculate a plurality of effect vectors Vap and Vaq while the point P and the point Q are moved on the first contour line and the second contour line, respectively;
calculate a total effect vector for the point A by accumulating the plurality of calculated effect vectors Vap and Vaq; and
calculate the vector field of the flattened region by repeatedly calculating the total effect vectors while the point A is moved in the flattened region.
The digital elevation model generating system according to claim 1, wherein the sub-contour line generating module is configured to:
retrieve vectors having the same magnitude in a neighborhood of a certain point; and
determine the curve on which the vectors have the same magnitude by connecting locations of the retrieved vectors by the curve.
The digital elevation model generating system according to claim 1, further comprising a terrain deviation determination module for calculating a terrain deviation at boundaries of the flattened region, and determining whether an elevation of a sub-contour line is higher or lower than elevations of the neighboring contour lines based on a sign of the calculated terrain deviation.
The digital elevation model generating system according to claim 1, wherein the sub-contour line generating module is configured to:
form a substantially rectangular buffer of a predetermined size along a boundary between the flattened region and the non-flattened region;
define center lines between an outline of the buffer opposed to the boundary and the boundary;
define an intersection point between the outline of the buffer and a curve in the flattened region, an intersection point between a center line of the flattened region and the curve of the flattened region, an intersection point between a center line of the non-flattened region and the curve in the non-flattened region, and an intersection point between another outline of the buffer and the curve in the non-flattened region; and
connect the curve in the flattened region and the curve in the non-flattened region by fitting a cubic curve to the defined four intersection points.
A method of generating a digital elevation model by causing a computer to interpolate sub-contour lines at a certain elevation on a contour map,
the computer including a storage unit for storing the contour map, a processing unit for carrying out an interpolation process for generating sub-contour lines, a memory for storing a program to be executed by the processing unit, an input unit for receiving an input of the topographic map, and an output unit for outputting a generated elevation map,
the method including the steps of:
partitioning the contour map into a triangulated irregular network;
marking each of triangle patches as flattened or non-flattened;
merging the triangle patches marked as flattened to form a flattened region;
generating curves serving as sub-contour lines by means of interpolation using the triangulated irregular network for the triangle patch marked as non-flattened;
calculating a vector field in which each vector represents a spatial effect of neighboring contour lines for the flattened region;
determining curves on which vectors have the same magnitude;
creating a buffer in a neighborhood of a boundary between a non-flattened region constituted of the triangle patches marked as non-flattened and the flattened region;
generating a newly integrated sub-contour line by smoothly linking the curve in the non-flattened region and the curve in the flattened region in the buffer; and
outputting a digital elevation model containing the interpolated sub-contour lines.
The method of generating a digital elevation model according to claim 7, wherein the step of marking each of triangle patches includes the steps of comparing elevations of three nodes constituting vertices of each of the triangle patches, marking the triangle patch as flattened when the elevations of the three nodes are equal, and marking the triangle patch as non-flattened when the elevation of at least one of the three nodes is different.
The method of generating a digital elevation model according to claim 7, wherein the step of calculating a vector field includes the steps of:
defining, for a point A in the flattened region, an effect vector Vap whose magnitude decreases as a distance between the point A and a point P on a first contour line increases, and an effect vector Vaq whose magnitude decreases as a distance between the point A and a point Q on a second contour line next to the first contour line increases;
repeatedly calculating a plurality of effect vectors Vap and Vaq while the point P and the point Q are moved on the first contour line and the second contour line, respectively;
calculating a total effect vector for the point A by accumulating the plurality of calculated effect vectors Vap and Vaq; and
calculating the vector field of the flattened region by repeatedly calculating the total effect vectors while the point A is moved in the flattened region.
The method of generating a digital elevation model according to claim 7, wherein the step of determining curves includes the steps of:
retrieving vectors having the same magnitude in a neighborhood of a certain point; and
determining the curve on which the vectors have the same magnitude by connecting locations of the retrieved vectors by the curve.
The method of generating a digital elevation model according to claim 7, further including the step of calculating a terrain deviation at boundaries of the flattened region, and determining whether an elevation of a sub-contour line is higher or lower than elevations of the neighboring contour lines based on a sign of the calculated terrain deviation.
The method of generating a digital elevation model according to claim 7, wherein the step of generating a newly integrated sub-contour line includes the step of:
forming a substantially rectangular buffer of a predetermined size along a boundary between the flattened region and the non-flattened region;
defining center lines between an outline of the buffer opposed to the boundary and the boundary;
defining an intersection point between the outline of the buffer and a curve in the flattened region, an intersection point between a center line of the flattened region and the curve of the flattened region, an intersection point between a center line of the non-flattened region and the curve in the non-flattened region, and an intersection point between another outline of the buffer and the curve in the non-flattened region; and
connecting the curve in the flattened region and the curve in the non-flattened region by fitting a cubic curve to the defined four intersection points.