Nội dung

CHAPTER 9 Multi-Scale Representations of Digital Terrain Models The previous two chapters addressed the issues on the quality of DTMs. The representations of DTM data will be discussed in the next three chapters. This chapter will look at some issues on multi-scale representation. 9.1 MULTI-SCALE REPRESENTATIONS OF DTM: AN OVERVIEW Before multi-scale representations of DTM data can be discussed, it is essential to clarify some concepts related to scale, to understand what is to be addressed in this chapter. 9.1.1 Scale as an Important Issue in Digital Terrain Modeling “Scale is a confusing concept, often misunderstood, and meaning different things depending on the context and disciplinary perspective” (Quattrochi and Goodchild 1997, p. 395). Scale is an old issue in geosciences such as cartography and geography. In cartography, maps are produced at different scales, for example, 1:10,000 and 1:100,000. A ground area with a fixed size will be mapped into a bigger map space at a larger scale. For example, a ground area of 10 km × 10 km will be a map area of 1 m × 1 m at a scale of 1:10,000. However, at 1:100,000, it is an area of only 0.1 m × 0.1 m on map. Due to the reduction in size (from 1 m × 1 m to 0.1 m × 0.1 m), the same level of detail (LOD) as represented on the larger-scale map cannot be represented on the smaller-scale map. This means that the representations of the same feature in the same area will be different when the maps are at different scales. Therefore, there is a multi-scale issue in cartography, that is, how to derive small-scale maps from large-scale maps through operations such as simplification and aggregation. This issue is called generalization. 191 © 2005 by CRC Press DITM: “tf1732_c009” — 2004/10/25 — 12:39 — page 191 — #1 192 DIGITAL TERRAIN MODELING: PRINCIPLES AND METHODOLOGY In geography, there is a similar issue. Normally, geographical data are sampled from enumeration units. The size of the enumeration unit is a scale indicator. In some geographical applications, a larger unit is needed as the basis for analysis. The sampled data need to be aggregated into a larger enumeration unit from the original unit. However, the statistical results may be different when the analysis is carried out based on different sizes (i.e., different scales) of the enumeration unit. Therefore, the issue is how to aggregate data from small enumeration units to larger units for processing. This issue is called the “modifiable areal unit” issue (Openshaw 1994). Indeed, there are similar issues in all geosciences, such as geomorphology, oceanography, soil science, biology, biophysics, social sciences, hydrology, environmental sciences, and so on. In digital terrain modeling, there is also a similar issue. Currently, DTM data at a national level are produced at various scales, for example, 1:10,000, 1:50,000, and 1:100,000, for different applications. They are mainly derived from contour maps at the corresponding scales. It would be desirable to maintain and update the DTM data at the largest scale only and to derive DTM data at any smaller scale by a generalization process, that is, DTM generalization. In computer graphics and games, landscape is often used as a background in various situations such as driving and flight simulations. In such cases, the LOD of the terrain surface may appear to be different if viewed from different distances. Therefore, in a scene, some parts may be represented in more detail and other parts in less detail. This is also a multi-scale issue and is simply termed LOD, which is also an important issue in DTM visualization. As will be discussed later, LOD is an issue quite different from generalization. In this chapter, the emphasis is on generalization although the basic ideas on LOD will also be outlined. 9.1.2 Transformation in Scale: An Irreversible Process in Geographical Space Here, the term geographical space means the real world. However, the term real world is still confusing because different disciplines study different aspects of it. Nuclear physics studies particles at the sub-molecular level in units of nanometers. This is an extreme at a micro-scale. At the other extreme, astro-physics studies the planets at an intergalactic level in units of light-years (the distance travelled by light in the period of a year). Such studies are at a macro-scale. Between these two extremes, many scientific disciplines study the planet earth, such as geology, geography, geomatics, geomorphology, geophysics, which are collectively called geosciences. Here, real world refers to the world studied by the geosciences. Such studies are at a scale called geo-scale. By an analogy to electromagnetic (EM) spectrum, the scale range, from micro-scale to geo-scale to macro-scale, is termed the scale spectrum (Figure 9.1). Like the visible light band in the EM spectrum, geo-scale is also a small band in the scale spectrum (Li 2003). Digital terrain modeling is a branch of geoscience. The transformation in the scale of geographical space is much more complicated than that in Euclidean space. In Euclidean space, any object has an integer dimension, that is, 0 dimension for a point, 1 for a line, 2 for a plane, and 3 for a volume. © 2005 by CRC Press DITM: “tf1732_c009” — 2004/10/25 — 12:39 — page 192 — #2 MULTI-SCALE REPRESENTATIONS OF DIGITAL TERRAIN MODELS Macro-scale 193 Astro-physics Space science Meteorology Geo-scale Geosciences Biology Micro-scale Nuclear physics Figure 9.1 Geo-scale in the scale spectrum. Scale 1 Scale 2 Scale 3 Scale 1 Scale 2 Scale 3 Figure 9.2 Scale change in 2-D Euclidean space: a reversible process. An increase (or decrease) in scale will cause an increase or (or decrease) in length in a 2-D space and in volume in a 3-D space. However, the shape of the object remains unchanged. Figure 9.2 illustrates the scale reduction in a 2-D Euclidean space. Scale 2 is a two-time reduction of scale 1 and scale 3 is a four-time reduction of scale 1. In such a transformation process, the length of the perimeter is reduced by two and four times, respectively, and the area of the object is reduced by 22 and 42 times, respectively. When the object at scale 3 is increased four times, the shape of the object is identical to the original one shown at scale 1. That is, the transformations are reversible. However, in geographical space, the dimensions are not integers. The concept of fractal dimensions was introduced by Mandelbrot (1967). In such a space, a value between 1.0 and 2.0 is the dimension of a line and a value between 2.0 and 3.0 is the dimension of a surface. In fractal geographical space, it was discovered long ago that different lengths will be obtained for a coastline represented on maps at different scales. The length measured from smaller-scale maps will be shorter if the same unit size (at map scale) is used for measurement. This is because different levels of reality (i.e., the Earth’s surface with different degrees of abstraction) have been measured. Indeed, on maps at a smaller scale, the level of complexity of an object is reduced to suit the representation at that scale. But when the representation at a smaller scale is enlarged back to the original size, the level of complexity cannot be recovered. © 2005 by CRC Press DITM: “tf1732_c009” — 2004/10/25 — 12:39 — page 193 — #3 194 DIGITAL TERRAIN MODELING: PRINCIPLES AND METHODOLOGY Scale 1 Scale 2 Scale 1 Scale 2 Scale 3 Scale 3 Figure 9.3 Scale change in 2-D geographical space: an irreversible process. Figure 9.3 illustrates that such a transformation is not reversible. Li (1996, 1999) regarded such kind of transformation as “transformation in scale dimension.” This means that the generalization of a DTM from a large-scale to a smaller-scale representation is an irreversible process. It will be shown in Section 9.3 that this process follows a natural principle (Li and Openshaw 1993). 9.1.3 Scale, Resolution and Simplification of Representations The size of the basic unit for measurement or representation is referred to as resolution. If the data are in raster format, the size of the raster of pixels is referred to as the resolution. The larger the pixel size, the lower the resolution. In the case of grid DTM, the grid interval is usually regarded as the resolution. Normally, the scale and resolution of spatial data are tightly packed. With the resolution of one’s eyes fixed, when one views an object more closely, the images formed in one’s eyes are larger, thus the images have a higher resolution or are at a larger scale. That is, in normal cases, the resolution is also good indicator of scale for DTM data. This is because resolution means the level of detail and scale means the level of abstraction. However, scale is not equal to resolution. Scale could refer to the ratio of distances as well as the relative size of interest. Figure 9.4 shows four images at the same scale but with four different resolutions. Similarly, digital maps can be plotted at any scale one wishes, but the resolution is fixed. With the introduction of resolution, it is easier to explain the difference between scale reduction in Euclidean and geographical spaces. In Euclidean space, reduction in the size of an object does not cause a change in its complexity. This can be understood with the following line of thought. When the scale is reduced, the size of the object is also reduced, but at the same time, the basic resolution of the observation instrument is also refined by the same magnification. This is implied in Euclidean geometry. For example, if the scale is reduced by two times, the size is reduced by two times and the resolution is two times finer (i.e., higher). On the other hand, in geographical space, when the scale is reduced, the size of an object is also reduced, but the basic resolution of the observation instrument remains unchanged. That is, this change of complexity is achieved by changing the relationship between the size of the object and the resolution of observation. © 2005 by CRC Press DITM: “tf1732_c009” — 2004/10/25 — 12:39 — page 194 — #4 MULTI-SCALE REPRESENTATIONS OF DIGITAL TERRAIN MODELS (a) (b) (c) (d) 195 Figure 9.4 Four images of Hong Kong with the same scale but different resolutions. The color plate can be viewed at http://www.crcpress.com/e_products/downloads/ download.asp?cat_no=TF1732. Table 9.1 The Cause and Effect of Scale Reduction in Euclidean and Geographical Space Effect Cause Space Relative Complexity Absolute Complexity Instrumentation Resolution Observer’s Resolution Euclidean space Geographical space Increased Unchanged Unchanged Decreased Reduced Unchanged Unchanged Unchanged There are ways in which to achieve this result (Table 9.1). The first is to change the size of the object but, at the same time, to retain the basic resolution of the observational instrument. The second is (a) to retain the size of the object but change the basic resolution of the observation instrument and then (b) to change the size of the observed objects by simple reduction in Euclidean space. 9.1.4 Approaches for Multi-Scale Representations It becomes clear that there are two different types of multi-scale representations. The first one is map-like, emphasizing the metric quality, and is thus useful for measurement. The multi-scale issue on the DTM is related to how to automatically © 2005 by CRC Press DITM: “tf1732_c009” — 2004/10/25 — 12:39 — page 195 — #5 196 DIGITAL TERRAIN MODELING: PRINCIPLES AND METHODOLOGY (b) (a) Figure 9.5 Steps and linear slope compared to discrete and continuous transformations: (a) discrete (steps) and (b) continuous (linear slope). derive DTM data suitable for any smaller-scale representation from the DTM at the largest scale, which is updated continuously. Such a process is called generalization and it is applied uniformly across the whole area covered by the DTM data so that all data points within the area will have a uniform accuracy. This is referred to as metric multi-scale representation here. The other type, for visual impression only (e.g., for computer graphics and games), is called visual multi-scale representation. On the same image, the scale of the image pixels produced from DTM data is not the same over the whole image and is a function of viewing distance. In other words, the LOD represented on an image varies from place to place. This kind of approach is simply called LOD in computer graphics. In some literature, it is also called view-dependent LOD and, in contrast, metric multi-scale representation is called view-independent LOD. There are also two types of transformations in scale, discrete and continuous transformations. “Discrete” means that there are only a few scales available, for example, 1:10,000, 1:100,000, and 1:1,000,000. The transformation jumps from 1:10,000 to 1:100,000, then to 1:1,000,000. Discrete transformation is like fixed steps in a staircase (Figure 9.5a). “Continuous” means that transformation can be to any scale, for example, 1:50,000 or 1:56,999, although in practice some scales are not used (e.g., 1:56,999). Continuous transformation is like a linear slope (Figure 9.5b). From the above discussions, the approaches for multi-scale representation of DTM data can be summarized as in Figure 9.6. 9.2 HIERARCHICAL REPRESENTATION OF DTM AT DISCRETE SCALES The hierarchical representation seems to be popular for the representation of DTM data at discrete scales, particularly in computer graphics and games and terrain visualization, in order to speed up the data processing. Both grid and triangular networks could be represented in hierarchy (de Berg and Dobrindt 1998; de Floriani 1989). 9.2.1 Pyramidal Structure for Hierarchical Representation The pyramid is the most commonly used hierarchical representation of DTM data. Figure 9.7 shows three-level pyramid structures of square grid and triangular grids. That is, four squares (or triangles) at the third level form a larger square quadrilateral © 2005 by CRC Press DITM: “tf1732_c009” — 2004/10/25 — 12:39 — page 196 — #6 MULTI-SCALE REPRESENTATIONS OF DIGITAL TERRAIN MODELS Discrete Continuous Isotropic View-dependent Metric multi-scale representation (Generalization, or isotropic LOD or view-independent LOD) 197 Visual multi-scale representation (View-dependent LOD) Figure 9.6 Alternative approaches for multi-scale representation of DTM data. Figure 9.7 Pyramid representations of grid and triangular networks. (or triangle) at the second level. Similarly, four squares (or triangles) at the second level form the largest square (or triangle) at the first level. The number of squares (triangles) at the nth level is 4n−1 . The sizes of the squares at the same level of the pyramid structure are identical. Figure 9.8 is an example of the grid pyramid representation of DTM data, where the original DTM is represented in three hierarchical levels. In the four-to-one aggregation process, simple averaging is adopted to compute the height value of the new grids. For example, if the heights of the four grid nodes at the fourth level are 5, 6, 4.5, and 5.5 m, then the average height value of these, that is, (5+6+4.5+5.5) m/4 = 5.25 m, is used as the height for the new grid node at the third level. The hierarchical concept of a simple pyramid emphasizes the level of grid sizes, that is, different resolutions, to represent the terrain surface at different scales. This is also the simplest LOD for visualization of DTM data. However, it does not take into consideration certain terrain features and thus usually produces relatively obvious visual distortions due to the loss of important surface characteristics and discontinuity at the boundaries between grid cells. © 2005 by CRC Press DITM: “tf1732_c009” — 2004/10/25 — 12:39 — page 197 — #7 198 DIGITAL TERRAIN MODELING: PRINCIPLES AND METHODOLOGY (a) (b) (c) (d) Figure 9.8 Pyramid representation of grid DEM: (a) original DEM at 1:20,000; (b) the second level; (c) the third level; and (d) the fourth level. 9.2.2 Quadtree Structure for Hierarchical Representation A major shortcoming of the simple pyramid structure is that the grid intervals among the grid cells are identical at any hierarchical level irrespective of whether the terrain surface is complicated or simple. This may cause problems if some parts of an area are complicated while other parts are simple. In this case, a hierarchical structure with varying grid sizes would be more desirable. The complicated parts could be represented with grid cells with finer resolution (i.e., smaller grid interval) and the simpler parts could be represented by grid cells with coarser resolution that is, (larger grid interval). Area quadtree, or simply quadtree, is such a kind of grid in common use. Figure 9.9 is an illustration of quadtree structure. Similarly, triangular cells also can be represented by quadtree. Figure 9.10 is an example of triangular quadtree. The aggregation of four cells into one is similar to the simple pyramid. The only difference is that in a quadtree, some criteria must be set so as to determine whether aggregation should take place for the four given cells. For example, if the height differences are larger than the threshold, then no aggregation should take place, otherwise they are aggregated into one. Figure 9.11 is an example of a hierarchical representation by a quadtree. In visualization with such a representation, when a more detailed level is desired, the next level with smaller grid intervals will be displayed, only in those parts with complicated terrain variations. To speed up the visualization process, one would like to generate an LOD for in as many levels as possible. However, in normal practice, only three to five LODs are produced and stored. Further levels are generated in real time by algorithms. © 2005 by CRC Press DITM: “tf1732_c009” — 2004/10/25 — 12:39 — page 198 — #8 MULTI-SCALE REPRESENTATIONS OF DIGITAL TERRAIN MODELS Figure 9.9 Hierarchical representation of grid by quadtree structure. Figure 9.10 Hierarchical description of terrain triangular network by use of quadtree. Figure 9.11 Quadtree representation of DTM (Cheng 2000). © 2005 by CRC Press DITM: “tf1732_c009” — 2004/10/25 — 12:39 — page 199 — #9 199 200 DIGITAL TERRAIN MODELING: PRINCIPLES AND METHODOLOGY 9.3 9.3.1 METRIC MULTI-SCALE REPRESENTATION OF DTM AT CONTINUOUS SCALES: GENERALIZATION Requirements for Metric Multi-Scale Representation of DTM Since the later 1970s, metric multi-scale representation of DTM data has been a research topic. A list of six criteria were proposed by Weibel (1987) for the evaluation of the methodology used: 1. 2. 3. 4. 5. 6. to run as automatically as possible to perform a broad range of scale changes to be adaptable to the given relief characters to work directly on the basis of the DTM to enable an analysis of the results to provide the opportunity for feature displacement based on the recognition of the major topographic features and individual landforms (major scale reduction). Three approaches have been proposed for metric multi-scale representation of DTM data. 1. filtering methods (e.g., Loon 1978) 2. generalization of structure lines (e.g., Wu 1997) 3. a hybrid (Weibel 1987) of the above two. However, these methods do not directly relate to the filtering process to scales and, therefore, are not true generalization methods. If the set of criteria proposed by Weibel (1987) are used to evaluate these pyramidal representations, the results are not too good. The most serious shortcoming is that only a fixed number of scales are produced, at least for hierarchical grid networks, that is, 2-time, 4-time, 8-time, 16-time, . . . scale reduction. Therefore, this approach is only convenient for data structures with which visualization of DTMs could be speeded up, but it cannot be used to produce smaller-scale DTMs from larger-scale ones. In this section, an approach based on a natural principle will be introduced. 9.3.2 A Natural Principle for DTM Generalization The natural principle formalized by Li and Openshaw (1993) mimics the generalization process of the Nature. The example they used is the Earth’s surface viewed from different heights. If one views the Earth from the Moon, all terrain variations disappear and the Earth appears like a blue ball. If one views it from a satellite, then the terrain surface becomes very smooth. These phenomena can easily be checked by forming a stereo model from a pair of satellite images such as SPOT images with 10-m resolution or Spacelab Metric Camera photography. Such a stereo model is at a very small scale. When one views the terrain surface from an airplane, small details are still not visible but the main characteristics of the terrain variations become clear. It is a commonplace to photogrammetrists that stereo models formed from © 2005 by CRC Press DITM: “tf1732_c009” — 2004/10/25 — 12:39 — page 200 — #10