GISdevelopment.net ---> AARS ---> ACRS 1992 ---> Digital Image Processing A Surface Interpolation for Large-scale Representation of Terrain Surface in An Urban Area Huag Shaobo,R.Shibasaki Institute of Industrial Science, University of Tokyo 7-22, Roppongi Minatoku, Tokyo, Japan Abstract: The 3D representation of the urban space is essential in managing and utilizing urban information in geographic information systems. The 2.5-d surface based boundary representation (SR) model seems to be an suitable 3D representation model of the urban space. In order to efficiently implement SR model, an improved surface interpolation method is proposed in the paper. Through an example of the representation of terrain surface, which have large volume of data and complex shape, it is demonstrated that the proposed surface interpolation method can be successfully and efficiently applied. Introduction: Nowadays, with the considerable growth in geographic information systems to meet two dimensional mapping needs, more and more demands are turning to the design and development of three dimensional mapping and modeling systems in a range of application areas. These demands are much stronger for those applications related to urban planning, infrastructure construction and facility management due to the complicated and dense utilization of urban space from the underground to the air. The conventional maps and map-drove data such as digital models (DTMs) can not represent 3D geographic objects. To handle 3D geographic data, solid modeling methods have been developed for computer aided design(CAD)/computer graphics(CG) systems. In geological information management, solid modeling methods and related surface interpolation techniques such as NURBS [Fisher and Wales, 1991) are applied for the 3D representation of geological objects [Raper et.al, 1988], [Jones, 1989], [Raper and Kelk, 1991]. However, these solid modeling methods could not be directly applied to the 3D representation of urban space because urban space contains & a much wider variety and larger amount of geographical objects. The basic requirement for 3D representation model of urban space can be summarized as follows (Shibasaki et.al. 1990) : (1) ease of representation of a variety of geographic objects in urban space; (2) Efficiency in building and updating 3D spatial database; (3) Ease of spatial query and analysis; (4) Compatibility with existing map data and CAD/CG systems. The surface based boundary representation(SR) model proposed by [Shibasaki & Huang 1992] can satisfy the requirement of 3D representation in urban space. The BR model fulfills both the compatibility with 2D map data and the ease of the representation of urban space, but the input and update of 3D spatial data with the BR model is severely labour-demanding. Although an algorithm was proposed for uncovered both planar polygons(faces) in edges and solids in polygons, the identification of non-planar polygons(faces) in edges still remains difficult. The polygon identification in the 2.5D surface(which is represented by a single-valued and continuous function), whether planar or non-planar, can be easily done by applying conventional algorithm to its projected plane. Surface interpolation algorithms for 3D data can be directly applied to the interpolation of their surface. By combining 2.5D surfaces into the BR model 3D spatial database can be easily developed. The 2.5D surface such as the terrain surface serves as a basis of SR model. The suitable surface interpolation for the 2.5 surface will be important in automatically and efficiently generating a 2.5D surface, especially the terrain surface. The existing Surface interpolation methods: A large amount of elevation points are necessary to represent 3D spatial object with a SR model. Especially the representation of terrain surfaces requires many reliable elevation points. This is not only because terrain surfaces have complicated shaped but also because the elevation of other spatial objects such as underground structures have to be determined based on the elevations of terrain surfaces. However it is not easy task to assign elevation data to so many points manually. For example, it is very labor-demanding to obtain elevation data from conventional maps in urban areas because contour lines are usually cut in pieces due to buildings and other man-made features. With aerial surveying techniques, it is not so easy to obtain enough number of elevation points due to occasions. Only roads and the roofs of buildings are exceptionally easy places for 3D measurement. A method of surface interpolation in urban areas is indispensable to meet the requirement of elevation data and to give a sound basis of elevation to a SR model. The conversional surface interpolation methods were developed for digital terrain models (DTMs). Since the conventional surface interpolation methods are mostly used for the small scale representation of rural terrain area, they can not be directly applied into the large scale representation of urban terrain surface because the discontinuities of slopes and elevation are often the cases in an urban area. It is necessary to improve existing surface interpolation method to represent the characteristic of urban terrain surface. The outline of a surface interpolation method: Existing terrain surface interpolation methods usually assume that terrain surfaces are smooth although the discontinuities of slopes and elevations are often the cases in urban areas. To make larger-scale representations of terrain surfaces and related spatial objects in urban areas, the following geometric conditions(Figure 1) must be considered, which characterize terrain surfaces in urban areas. Figure 1 Examples of geometric constraint conditions in surface interpolation Break lines : The steepness of slopes shows discontinuities on a break line. Break lines are often to be seen in the boundaries of man-made objects such as roads and levees. Step lines : Elevation shows a abrupt change (like steps) on a step lines. Retaining walls and the side walls of buildings are generated by step lines. Sometimes, step also can seen in the boundaries of the buildings, especially when the building is constructed in a steep slope. It should be noted that a step line must be derived into two lines in triangulation. Horizontal planes : Every points in a horizontal plane has the same elevation value. Floors of buildings are the examples. Under these geometric conditions, surface are represented by TIN to easily integrate the interpolated surface with the SR model. At places where these geometric conditions do not hold, elevations are interpolated under the assumption that a terrain surface is smooth. Smooth terrain surfaces are obtained to maximize the sum of the square of inner-products of unit normal vectors of neighbouring triangular planes. Moreover, some lines such as road boundaries sometimes have to be interpolated smoothly. The "smoothness" of lines is evaluated in terms of the sum of the squares of vertical changes of unit vectors along the lines. Thus elevations are interpolated so as to maximize to smoothness of terrain surface and lines under the above geometric constraint conditions. The basic process of the surface interpolation is shown in figure 2. The surface interpolation process consists of four parts as following: (1) 3D coordinates (x, y, z) of selected elevation points(known points) and 2D coordinates (x, y) of the rest(unknown pints) are given. The geometric conditions or structural features such as break lines and step lines are also specified. Figure 2. The basic process of the surface interpolation (2) TIN networking is generated based on Delaunay triangulation so as to include both break lines and step lines as edges in the TIN network. (3) Elevations of a road network are estimated through the surface interpolation. The elevation of roads can be a sound basis in determining the elevation of other spatial objects such as buildings, because they can be more easily and reliably acquired with conventional surveying techniques and because most of spatial objects are easily related to road networks. (4) Elevations of spatial objects are estimated within each block respectively. By estimating elevations in each block bounded by roads, computational loads in the surface interpolation can be decreased. 4. Estimation of elevation through surface interpolation: 1> "Smooth Plane" condition: Although there are many man-made discontinuities in an urban terrain surface, we can assume that the surface is smooth except these discontinuities. We call this assumption as "smooth plane" condition. Let ej be an edge of triangle, nej and nejr and nej1 be the normal vectors of neighboring triangles which share the edge ej, and ¡ej be the angle between ne and nej1 (see Fig. 3.). The "smooth plane" condition can be expressed by 2) "Break Line" condition: For edge ej which belongs to a break line, cos2 (¡ej), the smoothness index of ej is omitted in equation <1>. 3) "Step Line" condition: For an edge ej in a cut line, cos2 (¡ej) is omitted. In addition, on cut lines, each point except both start and end point has two (unknown) elevation values, while each point on break lines has only one z value. Start and end points on a step lien have one or two (unknown) elevation values. 4) "Horizontal Plane" condition: The z values of points in a horizontal plane must be the same. That is, where i1 denotes 1i th point in horizontal plane I and n3 is the number of horizontal planes. 5) "Smooth line" condition: Let zj, zj1 and zj2 be elevations of three neighboring points Pj, Pj1 respectively, and Sj1 and Sj1 be the horizontal distances of | P0P1 | and | P1P2 | (see Fig. 4.). The smooth line condition will be given by 6) Estimation of elevations by optimization: Unknown elevations are estimated by minimizing the weighted sum of equation <1> and equation <3> under the horizontal plane conditions given by equation <2>. The weights for equation <1> and equation <3> are to be determined by a user. A optimal solution i.e. estimated elevations can be obtained by using least squares method through the linearization of equation <1> and <3>. 5. The case study in SHIBUYA area and its discussion: A example of the surface interpolation has been made in SHIBUYA area around the SHIBUYA station(figure 5). The range of studied area is about 1.5km by 1.5km. There are about 250 blocks in the area. And more than 1500 buildings and other man-made objects are located in its terrain surface. In its 2D mapping data, more than twenty thousand points and edges are existing. After triangulation, the number of points and edges will be doubled. It is efficient to automatically assign such enormaous number of points and edges and their topological relations into the 2.5-D terrain surface. The final result of surface interpolation in SHIBUYA is shown in figure 6. The geometric conditions have different effects on the result of surface interpolation. The "smooth plane" conditions serve as basic conditions in surface interpolation. The "smooth line" conditions let the result of road surface interpolation like naturally. The break lines and step lines reserve the structural feature in the terrain surface. The "horizontal plane" conditions ensure that planes like ground floors will be flat. Non of them can be ignored. Fig 5. The air photograph in studied SHIBUYA area FIG 6. example of surface interpolation in SHIBUYA area Conclusion: The terrain surfaces in urban areas have geometric characteristics such as discontinuities in terms of elevation and the steepness of slopes. Under these geometric conditions, the proposed surface interpolation enables us to estimate the Z values of spatial objects from some observed elevation data. The example suggests that the surface interpolation method can save much labor and time in modeling 3D spatial objects in an urban space, and can provide a sound basic to implement SR (Surface based representation) model for the development of 3D spatial database in urban space. References: P.A. Burrough, Principles of Geographical Information Systems for Land Resources Assessment, Clarendon Press, Oxford, 1986. J.Raper, Three Dimensional Application in Geographic Information Systems, 1989, Dept. of Geography, Taylor and Francis Ltd. 1989. E.M. Mikhail, Observations and Least Squares, Thomas Y. Crowell Company, Inc. 1976. R.Shibasaki and H.Nakamura, A Digital Urban Space Model for Urban Planning and Management, Proc. Of the International Conference of the Application of Geodesy to Engineering, forthcoming, Springer Verlag. R.Shibasaki and Huang Shaobo, A Digital Space Model ---- A Three Dimensional modeling technique of Urban Space in a GIS Environment, Institute of Industrial Science, University of Tokyo, Proc. Of ISPRS, Washington, USA. Huang Shaobo, T.Kadowaki and R.Shibasaki, The Representation of Terrain Surface and Its Interpolation Method for Large Scale Digital Maps in An Urban Area, Proc. of annu. symposium of the Japan Society of Photogrammetric and Remote Sensing, Tokyo, May, 1992, pp. 77-pp88.