Theoretical Background
Algorithms are developed based on certain principles and theories. To facilitate the presentation of algorithms, a discussion of these principles and theories is provided in this chapter.
Scale is a term not well defined yet. "Of all words that have some degree of specialised scientific meaning, 'scale' is one of the most ambiguous and overloaded" (Goodchild and Quattrochi, 1997). In different contexts, it may mean different things. To discuss the scale issues in spatial representation, it is necessary to conduct a discussion on the theory of scale.
3.1.1  Geo-Scale in the Scale Spectrum
Scale may mean different things in different contexts. That is, different types of scale may be differentiated with different criteria. Table 3.1 is an attempt to classify scale based on different criteria.
Digital scale is the scale used in the expression of digital number. For example, we may express the same distance in a number of ways, such as 1.68 x 102 for 168.0 and 1.68 x lO"2 for 0.0168.
Temporal scale is related to the time interval. It may range from a few nanoseconds to hours, days, seasons, years, and even billions of years.
Radiometric scale is related to the detail level of the brightness of image pixels. A binary scale representation produces a black and white image. An image with 256 gray levels smoothly represents detailed variations in brightness.
Spectral scale is related to frequency, concerning the interval of frequency spectrum. For example, in remote sensing, the electromagnetic spectrum is a fundamentally important concept. That is, electromagnetic radiation (EMR) has a range of waves with different length, from gamma rays to radio waves. Visible light is only a small band in this electromagnetic (EM) spectrum. Different spectral bands (ranges) from this EM spectrum have been selected for remote sensing. The width of a band can be regarded as the spectral scale used.
Spatial scale is related to space and is the main concern of this text. In space-related science, different disciplines study different natural phenomena. Nuclear physics studies particles at the submolecular level in units of nanometers. This is an extreme at a microscale. In the other extreme, astrophysics studies the planets at an intergalactic level in units of light-years (the distance traveled by light in the period of a year). Such studies are at a macroscale. In the middle, many scientific disciplines study the
3.1   SCALE IN GEOGRAPHICAL SPACE
57
© 2007 by Taylor & Francis Group, LLC
58
Algorithmic Foundation of Multi-Scale Spatial Representation
TABLE 3.1
Classification of Scale Based on Different Criteria
Criteria
Type of Scales
Domain of interest
Digital, spatial, temporal, spectral, radiometric Micro, geo-scale, macro
Reality, data source, sampling, processing, model, representation Nominal, ordinal, interval, ratio
Scope of interest Stage of processing Level of measurement
planet earth, such as geology, geography, geomatics (surveying and mapping), geo-morphology, geophysics, and so on. These sciences relevant to the studies of the earth are called geosciences. Such studies are at a scale called geoscale in this book.
By analogy to the EM spectrum, the scale range in science, from microscale to geoscale to macroscale, is termed the scale spectrum and is shown in Figure 3.1. Like the visible light band in the EM spectrum, geoscale is a small band in the scale spectrum.
Recently, the word geospatial has become popular. This is directly related to the geoscale concept. The word geospatial was perhaps first used by the U.S. Geologic Survey in a program called "geospatial data infrastructure." It is normally used to refer to spatial information at geoscale.
In spatial data handling, at different stages (from reality, to data, and to final representation), different scales may be used. The concept scale may be expressed in different ways, such as in nominal scale (e.g., temporal, spatial), order scale (e.g., global, continental, national, provincial, local, etc.), or ratio and interval scale (e.g., 1:10,000).
3.1.2 Measures (Indicators) of Scale
The term scale may mean different things in different disciplines. In cartography, scale is the ratio of distance on a map to that on the ground, and this ratio is applicable to all other engineering drawings. The important question to be answered is, "Is there any other meaning implied in the scale of a map?" The answer to this question is directly related to the answer to the following question: "Do maps
Macro scale    i i Astrophysics
O  Light-year as unit
Space science Meteorology
Geo-scale
— Geo-sciences
•   Commonly used units
Biology
Micro scale
Nuclear physics
•  Nano-meter as unit
FIGURE 3.1 The scale spectrum and the geoscale. © 2007 by Taylor & Francis Group, LLC
Theoretical Background
59
of the same area at different scales represent the same reality?" The answer to the latter is "no." In other words, maps of the same area but at different scales represent different levels of abstraction. Therefore, scale also implies degree of abstraction or level of detail (LoD), in addition to ratio of distance. If a map is represented in raster, then the size of raster pixels (i.e., resolution) is also an indicator of LoD. A map at a given scale also implies a certain level of accuracy, according to map specifications. For a given map area, the size of the ground area varies with scale. The same map area will cover a larger ground area if the map scale is smaller. That is why in geography the size of the study area is used to indicate scale or LoD.
In summary, a set of parameters should be used as the measures (or indicators) of scale:
• Cartographic ratio
• Size of study area (i.e., geographical context)
• Resolution
• Accuracy
It should be emphasized here that scale is meaningful only when these parameters are consistent. Figure 3.2 (See color insert following page 116) shows four images with same image size and ground coverage. Thus, the cartographic ratio of these four images is identical, but they represent LoD because the resolutions are different. Therefore, it can be said that the scale of these four images is different.
Maps in digital form can be plotted at any scale one wishes, but the resolution and accuracy of the digital data is fixed. Therefore, there is no point to plotting a map at a very large scale if the accuracy requirement cannot be met.
The concept of resolution should be more precisely called spatial resolution, because there are other resolutions for spatial data (i.e., temporal, spectral, and radiometric resolutions).
3.1.3 Transformations of Spatial Representation in Scale in Geographical Space
In Euclidean space, an increase (or decrease) in scale will cause an increase (or decrease) in length, area, and volume in a three-dimensional (3-D) space. However, the shape and complexity of a feature remain unchanged. Figure 3.3 is an example of scale reduction in a 2-D Euclidean space. The graphic representation of the feature at scale 2 is a 2 times reduction of that at scale 1, and the graphic representation at scale 3 is a 4 times reduction of that at scale 1. In such a transformation process, the (area) size of the graphic representation is reduced by 22 and 42 times, respectively. When the graphic representation at scale 3 is increased by 4 times, the enlarged graphic is identical to original one shown at scale 1. That is, the transformations are reversible.
However, in the fractal geographical space, as discussed in Chapter 2, it was discovered long ago that different length values will be obtained for a coastline represented on maps at different scales. The length measured from a smaller scale
© 2007 by Taylor & Francis Group, LLC
60
Algorithmic Foundation of Multi-Scale Spatial Representation
FIGURE 3.2 (See color insert following page 116) Four images with the same cartographic ratio but different resolutions.
map will be shorter if the same unit size (at map scale) is used for measurement. This is because a different level of reality (e.g., the Earth's surface with different degrees of abstraction) has been measured. At a smaller scale, the size of the graphical representation is reduced. At the reduced graphics, the complexity of the graphics is still retained at the same level. As a result, if the graphic is enlarged back to the size at the larger scale, the level of complexity of the representation will appear to be much reduced. In other words, in geographical space, the level of complexity cannot be recovered by an increase in scale. Figure 3.4 illustrates the effect of an increase and decrease in scale on spatial representation in geographical space. It shows that the transformations in scale in such geographical space are not reversible.
In this example, in Euclidean space the reduction of graphic representation in size does not cause a change in its complexity in an absolute sense. This can be understood with the following line of thought: When the size of the graphic is changed, the basic resolution of the observational instrument is also changed by
© 2007 by Taylor & Francis Group, LLC
Theoretical Background
61
€2£ At Scale 1	>=>	At Scale 2	■=>	At Scale 3
				
At Scale 1		At Scale 2		es At Scale 3
FIGURE 3.3 Scale change in Euclidean space: a reversible process.
At Scale 1	^>	At Scale 2	1=>	CP At Scale 3
				
At Scale 1	<=>	CP At Scale 2	<=>	CP At Scale 3
FIGURE 3.4 Scale change in 2-D geographical space: lost complexity is not recovered.
the same magnification. However, the reduction of a graphic in size does cause a change in complexity in a relative sense. It is clear from Figure 3.3 that the graphic at scale 3 appears more complex than other two. This is because these three graphics are observed by the same observer, that is, with an identical resolution (Table 3.2).
TABLE 3.2
Causes and Effects of Scale Reduction in Euclidean and Geographical Space
Effect Cause
Relative       Absolute Instrumentation Observer's
Space Complexity Complexity       Resolution Resolution
Euclidean space Increased Unchanged Reduced Unchanged
Geographical space    Unchanged Decreased Unchanged Unchanged
© 2007 by Taylor & Francis Group, LLC
62
Algorithmic Foundation of Multi-Scale Spatial Representation
However, in geographical space, the change of complexity is achieved by changing the relationship between the size of the feature and the basic resolution of the observation instrument. There are two ways to achieve this result. The first is to change the size of the feature but to retain the basic resolution of the observational instrument (Table 3.2). The second way is (a) to retain the size of the feature unchanged but to change the basic resolution of the observation instrument, and then (b) to change the size of observed features by a simple reduction in Euclidean space.
3.2  RELATIVITY IN SCALE: THE NATURAL PRINCIPLE
It is a common sense that when taking a picture, you see more detail if you zoom in, and you see less detail if you zoom out. This is a principle underlining this natural phenomenon and it is a basis for multi-scale spatial representation.
3.2.1   The Idea of a Natural Principle
Reality at different scales means different things, as discussed in Chapter 1. A simple example is the Earth's surface viewed from different heights, which was used by Li and Openshaw (1993). If one views the terrain surface from a satellite, it becomes very smooth. When one views the terrain surface from an airplane, small details do not appear and the main characteristics of the terrain variations are very clear. These are just some of the many practical examples illustrating the transformation in scale dimension. In such a transformation the (absolute) complexity of spatial features has been altered with a change in scale (Li, 1996).
This is also due to the limitation of the human eye's resolution. When the viewpoint is higher, the ground area corresponding to the human eye's resolution becomes larger, and thus the ground surface appears to be more abstract. In the case of stereo models formed from images, it is due to the resolution of images. That is, all information within the image resolution (e.g., 10 m per pixel in the case of SPOT images) disappears.
These examples underline a universal principle, a natural principle as it is called by Li and Openshaw (1993), which states:
For a given scale of interest, all details about the spatial variations of geographical objects (features) beyond a certain limitation cannot be presented and can thus be neglected.
It follows, therefore, that a simple corollary to this process can be used as a basis for the transformations in scale dimension. The corollary can be stated as follows:
By using a criterion similar to the limitation of the human eye's resolution and, neglecting all the information about the spatial variation of spatial objects (features) beyond this limitation, zooming (or generalization) effects can be achieved.
Li and Openshaw (1992) call such a limitation the smallest visible object (SVO), called smallest visible size (SVS) in other literature. Figure 3.5 illustrates
© 2007 by Taylor & Francis Group, LLC
Theoretical Background
63
4} £
□ a
(a) An area represented by a pixel (b) A volume represented by a voxel
FIGURE 3.5 The natural principle. Spatial variations in an SVS can be neglected.
the natural principle to generate a zooming effect for a 2-D (left) and a 3-D representation (right).
Figure 3.6 illustrates the working example of applying this natural principle to 2-D representations. In the upper-left of this diagram is a river depicted by its two banks. On the upper right is a template full of overlapping SVSs. The SVS represents the size for representation at a smaller scale but has been enlarged to match the map scale of the river. On the lower left is the overlay of this river feature onto the template. The lower right shows the result at the smaller scale where every SVS becomes a point (i.e., represented by a dot in this diagram). This principle mimics
FIGURE 3.6 The natural principle applied to a 2-D representation (Reprinted from Li and Openshaw, 1993).
© 2007 by Taylor & Francis Group, LLC
64
Algorithmic Foundation of Multi-Scale Spatial Representation
(a) The process of zooming at two view distances (scales)
(b) Result viewed at LA
(c) Result viewed at LB
FIGURE 3.7 The natural principle applied to a 3-D representation (Reprinted from Li and Openshaw, 1993).
the effect of zooming when a photograph is taken. Li (1996) refers to this zooming effect as the transformation in scale dimension.
Figure 3.7 illustrates the working example of applying this natural principle to 3-D representations. Figure 3.7a shows the view of a 3-D surface at two different heights, resulting in representations at two different scales. Figure 3.7b shows the result viewed at level LA, and Figure 3.7c shows the result viewed at level LB. In these latter two figures, the zooming effects are very clear.
3.2.2  Estimation of Parameters for the Natural Principle
To apply this natural principle, the critical element to be considered is the value of this "certain limitation," that is, the value of the SVS, beyond which all spatial variations (no matter how complicated) can be neglected. This is related to the thresholds of perception in visual science and to map scales. That is, the minimum separation and minimum size of symbols on maps may be used as a reference.
© 2007 by Taylor & Francis Group, LLC
Theoretical Background
65
TABLE 3.3
Minimum Size Required for Various Types of Map Symbols
Map Symbols      Type of Symbols Thresholds
■/□
•/O
A/A i/A
■ /[=
Point Line Square Circle Equalateral triangle Isosceles triangle Rectangle
0.2 mm Thickness: 0.1 mm Side: 0.4 mm/0.6 mm Diameter: 0.4 mm/0.5 mm Width: 0.6 mm/0.7 mm Width: 0.4/0.5 mm, Height: 1.0 mm Width: 0.4 mm/0.5 mm
It is generally understood that the minimum separation between two map symbols is 2 mm at map scale. The minimum sizes of map symbols are listed in Table 3.3, which is extracted from Spiess (1988). From this table it is can be seen that the thresholds of point symbols range from 0.2 mm to 1.0 mm. Therefore, the value of the SVS for any spatial representations might be between 0.2 mm and 1.0 mm.
Theoretically speaking, the absolute value of the SVS on the ground (K) must be a function of the SVS value (k) on the map (or other spatial representation) and the scale (l:Sr) of the target map (or other spatial representations). A natural thought is
K = kxST (3.1)
However, there is a problem associated with this formula. That is, the K value is the same no matter what the scale of the source map. To solve this problem, Li and Openshaw (1992, 1993) modified Equation 3.1 as follows:
K- kxSTx
S A c
V        °T J
(3.2)
where ST and Ss are the scale factors of the target map and source maps, respectively, and k is the SVS value in terms of map distance on the target map. Through intensive experimental testing, Li and Openshaw (1992) found that a value between 0.5 mm and 0.7 mm enabled them to produce line generalization results similar to manual generalization. Therefore, it is recommend that
k — {0.5mm, 0.7mm} (3.3)
Equation 3.2 seems more reasonable. When the difference between Ss and ST is small, the K value is small. This means that not much is to be changed in the transformations. In an extreme, when ST— Ss, K — 0. This means nothing should be changed in the transformations.
© 2007 by Taylor & Francis Group, LLC
66
Algorithmic Foundation of Multi-Scale Spatial Representation
3.3 THE RADICAL LAWS: PRINCIPLES OF SELECTION
In the cartographic community, some interesting studies have been conducted on the relationship between the numbers of symbols at different scales of representation. An empirical law has been formed from these studies, called the principle of selection. This principle has been used to determine how many symbols to retain on a representation at a smaller scale.
3.3.1   Number of Symbols at Different Scales: A Theoretical Analysis
It is clear that for the same ground area, if a map (at a smaller scale) is being derived from maps at a larger scale, the map space is reduced. As a result, not all the symbols on the maps at a larger scale can be represented on the map at a smaller scale. That is, the absolute number of total symbols must be reduced on the small-scale map. However, the relative number of symbols in terms of per unit of map area should be approximately retained. In other words, the density of symbols on map should be retained somehow. Mathematically,
N, NT As Aj.
where Ns and NT are the numbers of symbols on the source and target maps, respectively, and As and AT are the areas of the maps at source and target scales, respectively.
Suppose that a ground area is L2 x L2. The corresponding areas on source map As and on target map AT are as follows:
s     s (3.5) Aj, = — x —
where Ss and ST are the same as in Equation 3.2. By substituting Equation 3.5 into Equation 3.4, the following equation can be obtained:
S2
r s
VJr J
(3.6)
This is called the equal map density function. This is the case when the minimum size of cartographic symbols is not considered. When considering the need to exaggerate some cartographic symbols on a map at a smaller scale, Equation 3.6 needs to be modified. That is, one or more adjustment factors need to be introduced into Equation 3.6.
© 2007 by Taylor & Francis Group, LLC
Theoretical Background
67
3.3.2  Principle of Selection: Empirical Formula or Radical Law
Töpfer was one of the first to study the transformations of spatial representation in map form. He formulated the principle of selection, or radical law (Töpfer and Pillewizer, 1966), to express the relationship between map scale and the number of features represented on maps. Töpfer and Pillewizer found that many cartographic processes have a direct relationship between the square root of map scale (Jg). Thus, the number (AO of cartographic features represented on a map is a function of      , that is,
N = kxjs
(3.7)
Töpfer referred this formula to as the radical law. Substituting Equation 3.7 into Equation 3.6, the following equation can be obtained:
NT=Nsx.
(3.8)
Töpfer also called this formula the law of natural dimension. Variations can be made to Equation 3.8 by considering a number of factors such as the purpose of the map and the form of symbols, as follows:
NT = CpxCFxNsx,
(3.9)
where CF and CP are the factors for map purpose and symbol form, respectively. CF and CP are also related to Ss and ST. In the end, a more general formula is obtained as follows:
NT=Nsx,
ös
V   T J
(3.10)
where x takes a value of 0, 1, 2, 3, 4, or 5. This is called the general selection law. The interpretation of these values is as follows:
0 ==> no selection
1-3 => a densification of map image
4 ==> equal map density
5 => a loosening-up of map image
(3.11)
© 2007 by Taylor & Francis Group, LLC
68
Algorithmic Foundation of Multi-Scale Spatial Representation
The principle of selection is able "to provide some measure of the amount of information which the cartographer can reasonably expect to put on a derived map," as emphasized by Maling in his introduction of Töpfer's paper (Töpfer and Pillewizer, 1966).
3.3.3  Fractal Extension of the Principle of Selection
Equation 3.11 can also be written as
NT = Nsx
rs V
ySTj
(3.12)
where p = x/2 takes a value of 0, 0.5, 1, 1.5, 2, or 2.5. Yu (1993) found that the highest p-value belongs to areal symbols, then point symbols, then line symbols, and the least value was lettering. This means that the space occupied by areal symbols will decrease very quickly with a reduction in the map scale. In other words, the density of areal symbols will decrease quickly. Equation 3.12 can be written as
£=log(W
2 log(Ss/Sr)
Yu (1993) tried to connect the principle of selection with fractal dimension. In a similar use as the radical laws, if one knows the fractal dimension (D) of a line and its length (Ls) on the source map at scale l:Ss, then it is possible to predict the length (LT) of this line on the target map at scalel:Sr. To do so, Equation 2.8 can be rewritten as
D -
\og(LT/Ls) log(Ss/ST)
(3.14)
Then the following equation can be obtained for prediction of the line length at the target scale:
■■Lsx
ySTj
(3.15)
Yu (1993) claims that this formula is a correlative form to Equation 3.12 and that Equation 3.14 is a correlative form of Equation 3.13. Yu further emphasizes that "This connection between Topfer's 'Law' and fractal geometry is not simply a conversion. The theoretical and practical meaning goes beyond the simple mathematical expression and opens potential for future generalization formulation."
© 2007 by Taylor & Francis Group, LLC
Theoretical Background
69
3.4 STRATEGIES FORTRANSFORMATIONS OF SPATIAL REPRESENTATIONS IN SCALE
3.4.1   Separation of Scale-Driven from Graphics-Driven Transformations
Map data is an important type of spatial representation. Paper maps have been used as a medium for both data storage and data display. As a result, in traditional manual map generalization, the transformations are carried out simultaneously for both the change of map complexity and the consideration of graphic legibility. In addition, the "characteristics and importance" of features are also considered in this process, as pointed out by Keates (1989). That is, one may want to keep certain characteristics on a map or to retain certain small features although they are too small for the map scale. All these together make the generalization process appear to be very subjective.
In a digital environment, graphic display and data storage are separated. Therefore, these two issues can be tackled separately. The legibility issue may be considered only when there is a need of graphic display because data resolution could be very high in a database. For example, two lines with spacing much less than 0.01 mm are still separable in a digital database. If the spatial data are only for analytical analysis, no legibility issue needs to be considered. Only when a graphic presentation is considered do we have the issues of graphic legibility, resulting in exaggeration, displacement, and other complex operations.
Miiller et al. (1995) emphasized that a generalization can be separated into two stages: model generalization and cartographic generalization. A similar view has also been expressed by Li and Su (1995), as shown in Figure 3.8. In this figure the two stages are called digital-to-digital transformation (or data generalization) and digital-to-graphic transformation (or graphic presentation). There is a slight difference between these two views. In the one by Li and Su (1995), digital-to-graphics transformation is simply a graphic presentation but not a generalization process. Peng et al. (1996) employ a slightly different terminology, database generalization and visualization generalization, to express exactly the same view as Miiller et al. (1995). All in all, there are two processes — one for data (or model) and the other for graphics.
FIGURE 3.8 A strategy for digital map generalization (Reprinted from Li and Su, 1995. With permission.).
© 2007 by Taylor & Francis Group, LLC
70
Algorithmic Foundation of Multi-Scale Spatial Representation
It can be noted here that the digital-to-digital transformation is the only step required if no graphic presentation is concerned. The digital-to-digital transformation is driven by scale. Such a process will simplify the shape, form, and structure of spatial representations and should be very objective, so that a unique solution can be achieved, given the same conditions. Such a transformation can be considered a transformation in scale dimension (Li, 1996) and it follows a natural principle. However, if graphics are considered, one needs to take into account the geographical, multipurpose, and cartographic requirements. It is now clear that cartographic requirements should be considered in the digital-to-graphic transformation after the scale-driven digital-to-digital transformation. Of course, one can also use some of the cartographic requirements as constraints for the digital-to-digital transformation. Some of the multipurpose and geographical requirements may also be used as constraints for this scale-driven transformation and for selecting data layers for generalization.
In the context of this book, emphasis is given to the scale-driven objective transformations. Indeed, only Chapter 10 is devoted to the transformations of graphic representation or, more precisely, displacement.
3.4.2 Separation of Geometric Transformation from high-level constraints
A map contains the following types of information about map features (Li and Huang, 2002):
• (Geo)metric information related to position, size and shape.
• Thematic information related to the types and importance of features.
• Relational information about spatial relations between neighboring features implied by distribution.
The transformations of spatial representation in the context of this book are about the geometric information, which is at the bottom level. Geometric transformations are achieved by some operations, each of which is implemented by one or more algorithms and operators. These operators and algorithms, such as afflne and conformal transformations, are the basic functions in the transformation and can be utilized whenever needed.
The question of "when needed" should be answered by rules that are formalized by using thematic information and other knowledge. It has been recognized that such thematic information and knowledge can be acquired from (a) cartographic experts through interview, (b) existing maps through analysis, or (c) map specifications. A lot of work on this topic has been undertaken (e.g., Buttenfield and McMaster, 1991). However, this is a topic beyond the scope of this book.
After the geometric transformations are applied, the relations (order, topologie, and directional) between map features may be altered. The adequacy and allowable changes can be monitored by models for spatial relations. When human cartographers carry out generalization processing, they have an overview of a larger area and try
© 2007 by Taylor & Francis Group, LLC
Theoretical Background
71
to consider the interrelationship between features and thus consider a number of generalization operations simultaneously. However, computers do not have such an overview and execute operations one by one. Therefore, the relations between features need to be modeled so that reasoning changes before and after generalization can be made.
The thematic transformation is also directly related to topological relations between features, which vary greatly with scale. For example, on a map at 1:1,000 scale (i.e., a high degree of detail), almost every building and street is represented, and therefore, topological relationships between buildings and streets are important at this scale. However, on a map at 1:100,000 scale (a higher degree of abstraction), buildings need to be grouped together into blocks, and individual streets may disappear. In this case, the classes of features such as streets and buildings disappear and are replaced by new classes such as blocks. Therefore, topological relationships between blocks are important at this scale, and topological relationships between buildings and streets can and should be neglected. If the map scale is even smaller (a higher level of abstraction), then a town may become a point symbol, and thus all topological relations between features in the town disappear.
3.4.3  Distinguishing Three Levels of Transformations for Spatial Representation
The transformations of spatial representations can be carried out at three different levels:
• Individual features (i.e., feature level)
• A class of features (i.e., class level)
• The whole representation (i.e., map level)
At the feature level, one is concerned with the transformation of a specific map feature from source maps at a larger scale than the target maps at a smaller scale. A typical example is line generalization algorithms used to simplify a line to suit the representation at a smaller scale.
At the class level, one is concerned with the transformation of a specific class (or subclass) of features from the source maps at a larger scale to the target maps at a smaller scale. Many operators have been designed for transformations at this level, such as aggregation, merging, and typification.
At the map level, one considers the transformation of all classes of features from source maps at a larger scale to the target maps at a smaller scale as a whole. Map information is dealt with at this level. That is, one is concerned with the transformation of map information from larger scale source maps to smaller scale target maps (Knopfli, 1983; Li and Huang, 2001). However, a discussion of transformations at this level lies outside the scope of this book.
In this book emphasis is given to transformations at feature and class levels. The discussions of transformations at the feature level are in Chapters 5-7, 9 and part of Chapter 11, while the discussions on the transformations at class level are in Chapter 8 and 10, and part of Chapter 11.
© 2007 by Taylor & Francis Group, LLC
72
Algorithmic Foundation of Multi-Scale Spatial Representation
3.4.4 Integration of Raster-Based Manipulation into Vector-Based Data Structure
Map generalization is due to the reduction in map space on smaller-scale maps. Therefore, the raster data model is the most appropriate one, as raster is a space-primary data structure. However, vector data is more intelligent. As a result, a hybrid data structure of vector and raster should be used as part of a strategy for multi-scale spatial representation. The vector structure could be used to hold spatial data in a database since a vector is a feature-primary data structure and is good for organizing data efficiently. The raster structure could be used as a working environment. This has been suggested by many researchers (e.g., Su et al., 1998; Peter and Weibel, 1999).
In this way, one needs to rasterize different types of vector features into various layers only when they need to be considered. This means it is not necessary to rasterize features if they are not relevant to a particular operation or if the original data are already in raster format. The raster size will be determined in such a way that rasterization will not affect the quality of the representation at the target scale. This can be achieved by following the natural principle, as presented in the previous subsection. After generalization is completed, the result can be vectorized back.
With such an integration in mind, a mix of vector-based and raster-based algorithms are presented in this book without special notifications.
REFERENCES
Buttenfield B. P. and McMaster, R. B., Eds., Map Generalization: Making Rules for Knowledge Representation, Longman Scientific & Technical, Essex, UK, 1991.
Gold, C. M. and Snoeyink, J., A one-step crust and skeleton extraction algorithms, Algorith-mica, 30, 144-163.
Goodchild, M. and Quattrochi, D., Introduction: scale, multiscaling, remote sensing and GIS, in Scale in Remote Sensing and GIS, Quattrochi, D. and Goodchild, M., Eds., CRC Press, Boca Raton, FL, 1997, pp. f-f 2.
Keates, J., Cartographic Design and Production, 2nd ed., Longman Scientific & Technical, Essex, UK, 1989.
Knöpfli, R., Communication theory and generalization, in Graphic Communication and Design in Contemporary Cartography, Taylor, D. R. F., Ed., John Wiley & Sons, 1983, pp. 177-218.
Li, Z. L., Transformation of spatial representation in scale dimension: a new paradigm for
digital generalisation of spatial data, International Archives for Photogrammetry and
Remote Sensing, XXI(B3), 453^58, 1996. Li, Z. L. and Huang, P. Z., Transformations of spatial information in multi-scale representation,
Proceedings of the 20th International Cartographic Conference, August 26-28, 2001,
Beijing (CD-Rom).
Li, Z. L. and Huang P., Quantitative measures for spatial information of maps. International Journal of Geographical Information Science, 16(7), 699-709, 2002.
Li, Z. L. and Openshaw, S., Algorithms for automated line generalisation based on a natural principle of objective generalisation, International Journal of Geographic Information Systems, 6(5), 373-389, 1992.
© 2007 by Taylor & Francis Group, LLC
Theoretical Background
73
Li, Z. L. and Openshaw, S., A natural principle for objective generalisation of digital map data, Cartography and Geographic Information Systems, 20(1), 19-29, 1993.
Li, Z. L. and Su, B., From phenomena to essence: envisioning the nature of digital map generalisation, Cartographic Journal, 32(1), 45-47, 1995.
Müller, J.-C, Weibel, R., Lagrange, J. P., and Salge, F, Generalization: state of the art and issues, in GIS and Generalization, Müller, J.-C, Lagrange J. P., and Weibel R., Eds., Taylor and Francis, London, 1995, pp. 3-17.
Peng, W., Tempfli, K., and Molennar, M., Automated generalization in a GIS context, in Proceedings of Geoinformatics '96 (International Symposium on GIS/RS, Research, Development and Application), Florida, 1996, pp. 135-144.
Peter, B. and Weibel, R., Using vector and raster-based techniques in categorical map generalization, in Third Workshop on Progress in Automated Map Generalization, Ottawa, August 12-14, 1999.
Spiess, E., Map compilation, in Basic Cartography, Vol. 2, Anson, R. W., Ed., Elsevier,
London, 1988, pp. 23-70. Su, B., Li, Z. L., and Lodwick, G., Morphological models for the collapse of area features
in digital map generalisation, Geolnformatica, 2(4), 359-382, 1998. Töpfer, F. and Pillewizer, W, The principles of selection, Cartographic Journal, 3(1), 10-16,1966. Yu, Z., The Effects of Scale Change on Map Structure, PhD thesis, Department of Geography,
Clark University, Worcester, MA, 1993.
© 2007 by Taylor & Francis Group, LLC