EGIS (1994), copyright EGIS Foundation.
In the spatial databases domain, data models currently used are often outmoded by always increasing user's needs. For instance, the very discrete aspect of Object-Oriented (OO) models (spatio-temporal attributes only specified for source points and objects), does not supply a sufficient realistic idea of nature. In a query, two points that are close together in space can have very different attribute values only because they belong to two different objects (even if the features of these objects are the same). Solving this problem leads to interpolate and extrapolate between values of object attributes, so that information could be spread upon the entire zones. Applications range from meteorological data to geological layer estimation or digital terrain modelling and phenomenon propagation estimation. In the estimating process, precise morphological and statistical constraints must be taken into account, so that the interpolation preserves the salient features of the environment. Classic approximating methods do not meet all these requirements. Based on the Field-Oriented approach a new method of interpolation and extrapolation by means of artificial neural networks is specified, in order to approximate spatio-temporal attributes, and satisfying our constraints. It is an extensional method which is able to take into account any spatial information. The neural net is based on the Hopfield model which minimizes a state function. This state function follows the principles of a classic interpolation method, the finite differences method. This neural interpolation technique is integrated to existing OO geographic models.
neural network, Hopfield model, interpolation, extrapolation, spatio-temporal information, object-orientation field-orientation.
Attribute values, in nature, are continuous: temperatures, altitudes, are spread all other the space. This is not the case in Object-Oriented (OO) models, where attributes are discrete (only specified for source points). GIS deals with static and discrete data but environmental models are concerned with dynamic and continuous phenomena (Kemp 93). In other words, the problem is to manage efficiently continuous data in spatio-temporal information systems. In this paper, we expose the definition, the main advantages and the drawbacks of the OO approach when applied to Geographic Information System (GIS) (Pornon 92)(Laurini, Thompson 92)(Laurini, Milleret-Raffort 93). To palliate the OO drawbacks, a theoretical solution is presented: the Field-Oriented (FO) approach. The FO provides a different view of nature, precisely a
[End Page 684]
raster view of the environment. This approach leads to interpolate and extrapolate between and beyond sample points (sample points corresponding to the locations of geographic attributes). But these approximations must be processed according to precise statistical and morphological constraints, in order to respect environmental salient features.
Classic interpolation methods are criticized depending on these constraints. A new neural solution is defined, meeting all our exigencies: an extensional interpolation and extrapolation technique is specified, respecting the features of most observed phenomena described by vector fields. Finally, this neural approach of the problem of continuous data management is integrated into the existing OO models.
In this paragraph, the main advantages and drawbacks of the OO approach are presented, from a GIS point of view.
Object-oriented (OO) concepts were introduced about ten years ago, because of the limitations of relational data models. These limitations concern the management and the manipulation of complex data (as geographic data) (Boursier & al. 93). OO systems are based on the functions of databases, and OO languages: persistence, query language, structured objects definition, object identity, reusability, inheritance, overloading, extensibility, types constructed recursively using atomic types and applying to them constructors like set, tuple, and list (Delobel & al. 91). The main advantage is a better management of complex data modelling. For example, when defining a class, it is possible to describe both the structure (attributes types) and the behaviour (methods) of a set of objects.
In the OO approach the world is divided into concepts or objects. At first, it still exists a difficulty for users and developers to be OO-minded. Indeed, it is not always practical, and evident to describe nature by means of bounded objects. Another limit is that attribute values generally correspond to the privileged points of the objects. All the other points belonging to the object do not own a particular value. As shown in Figure 1, points l1 and l2 belong, respectively to zones z4 and z5, and no attribute value is specified for them. A simple determination of their attribute values (for example their elevation) is a4=72 for l1, and a5=40 for l2 (privileged attribute values). The continuity always observed in nature is not respected.
[End Page 685]
Field-Oriented (FO) concept (Couclelis 92) tries to address to these limitations by means of a new approach: the geographic world is seen as a range of discrete values, supplied by characteristic measures. Our method of interpolation and extrapolation described in this paper is based on the FO approach, which is an extensional view of the geographic space. Until now, the FO approach does not supply any practical solution. It just provides a different way of thinking: instead of partitioning the real world into discrete objects and attribute values, it is represented by means of a wide range of values, each value corresponding to the attribute value of a piece of space. The principles of FO are the following: - every spatial object can be considered as a spatial extension including an infinite number of points: the space of values is continuous,
Figure 2 shows an example of an extensional view of the space (from Figure 1). The space is seen as a grid of cells (six different digital terrain models are available: grid of cells, polygons, triangular irregular networks, contours, point grids, and irregular points) (Laurini, Milleret-Raffort 93). Discrete values are supplied some cells, because these cells contain a sample point. Other cells need an interpolation or an extrapolation (or both). Our goal is to represent nature by means of a continuous and differentiable model, respecting morphological and statistical constraints.
A GIS must be able to model reality, which is in fact the observed reality. This model must satisfy user's needs: approximating attribute values respecting morphological and mathematical requirements, statistical knowledge of the environment (from which, if necessary, unexpected information may appear). All these constraints must be taken into account. A few methods attempt to respond to a subset of these requirements. In this paragraph, our constraints will be exposed. The goal is to interpolate and extrapolate a studied phenomenon considered as a scalar or vector field from a given set of data (source points with fixed attribute values).
[End Page 686]
etc. These objects depend on the category of the phenomenon, and describe the relationships between geographic objects. If it is concerned with social and economic data political frontiers can be specified. A factor of permeability (of the boundary, according to the phenomenon) can be defined.
Continuity and differentiability. If a mathematical function modelling the environment exists, it is continuous and differentiable between boundaries, because the phenomenon is considered as differentiable and continuous (a way to avoid crisp fractures in the values). Values at sites that are close together in space are more likely to be similar than others, they depend on one another from a statistical point of view (spatial autocorrelation).We cannot imagine that two neighbouring points could have "very" different attribute values, unless it is a general trend of the studied space (see Figure 3).
Preserving realism. The information system must return the exact value of source points. In other words, when we query for the attribute value of a point specified in the set of source points, the method must not provide an estimated value, but the true one. So exact interpolation methods are preferred to approximate ones: approximation must not be applied to fixed sample points. Even if this constraint appears as obvious, certain mathematical methods do not meet it, and the preference is given to differentiability instead of exactness (see Figure 4) It is also important to preserve the original values of sample points because of possible problems of databases integrity.
Point attribute or zone attribute. Source can be either the mean value of a zone (a), or they can concern one particular point (b). The case (a) is useful to include statistical constraints into the estimating process. It can be useful to include a method allowing to specify precise statistical constraints like variance, regression parameters (or gradients) (see Figure 5). By this way, errors of measure can be taken into account.[End Page 687]
Estimating unspecified peak. The goal to estimate, by means of morphological and statistical data, peak points not belonging to the convex hull of source points. So that the space morphology is imagined beyond and below known source points. In other words, interpolated values do not only belong to the interval between the highest and the lowest sample values, but take into account statistics about the studied space, such as not forecast peaks might appear. In Figure 6, the zone having one source point attribute of 27, and a mean value of zone of 31 (hatched zone), will have a peak higher than the peak measured at 27: a new peak is estimated. Extrapolation must be clearly defined, according to statistical data at the edges of the studied space.
Here, the main (and not exhaustive) constraints for a good interpolation method have been presented, obviously from a GIS point of view. Classic interpolation methods usually try to meet these requirements. But not all of them simultaneously. Our goal is to satisfy the greater number of constraints. In the next paragraph, existing interpolation methods are briefly presented.
In this paragraph, the limitations of a few methods commonly used in GIS are briefly exposed. Note that spatio-temporal knowledge is either an information or a way to find this information (by using basic parameters, like measures) (Laurini, Thompson 92). Interpolation and extrapolation methods can be classified as structural or statistical, linear or non-linear, global or local, extensional or intensional (see (Jeansoulin 91) and (Lam 83)). A wide range of interpolation methods has been tested, as spline functions, polynomial functions, nearest point interpolation, gravitational and distance-weighted functions (Laurini, Thompson 92), fuzzy interpolation (van Gaans & al. 93), Bayesian methods, Kriging (Matheron 67), triangulation, Voronoi diagrams, feedforward neural nets (Sontag 92). The finite differences method is more deeply studied; it satisfies some of our constraints with accuracy. A partial table of comparison follows (details of these methods in (Pariente, Laurini 93a)).
[End Page 688]
Concerning neural interpolation (by feedforward nets), a limitation is that the learning systems using training by backpropagation are often time-consuming and sometimes impossible to be performed (Fisher 93). It is commonly accepted that feedforward nets do not give the best estimates (for more explanations about backpropagation, its applications and limits see (Kouam & al. 92), (Rajagopalan & al. 92)).
The Finite Differences Method can satisfy a great part of the constraints exposed beyond. A limitation is that this method is time-consuming, and memory space problems occur. Iterative method can be used to solve it, such as "Relaxation" techniques (used in (Servigne 93)). But limitations are a number of iterations often too much important, and cases in which relaxation is not possible, imposing arbitrary stopping rule.
Interpolation and extrapolation can be considered as a problem of optimization. We propose to compute estimated values by using a neural network specialized in optimization (based on Hopfield model). Neural networks are able to find near-optimal solutions to problems with a large set of simultaneous constraints. Hopfield model permits to define a neural network, in such a way that an energy function of the system is minimized. This energy function is defined according to the results of the FDM.
The continuous Hopfield neural net, introduced by Hopfield (Hopfield 84), is a layered network, autoassociative nearest-neighbour encoder in continuous time (for more details on the Hopfield model, see (Bourret & al. 91)(Hopfield 84)(Lippman 87)).
The new neural solution must preserve the characteristics of the Finite Differences method as it is based on the same fundamental principles.
[End Page 689]
Extrapolation is considered as an extension of the same principles. Each neuron concerned by extrapolation will have its activation equal to the average of neighbours activations. The Finite Differences Method is known to be poor in information at the edges of the studied space. More information is provided by considering that all our space is surrounded by boundaries, so that crisp decreasing values at edges is avoided. Another direction is to include statistical information concerning not sampled pieces of space, allowing a good extrapolation. However, it is obvious that extrapolation will only concern very nearby zones of source points. By propagation of the neighbourhood, at the end of the process of updating, we can be sure that (except source neurons and boundary neurons) each current neuron has an activation value which is the average of its adjacent neighbours.
Comparison with a Cell Automata (CA): a CA corresponds to the simplest case of the interpolation: when no specific morphological and statistical constraints have to be satisfied and where interpolation is only concerned with the neighbourhood. Special conditions will oblige to take into account local nodes, but also certain remote nodes, and particular neurons (statistics). Few supplementary neurons will be connected to all (or a part of) the others to satisfy constraints. This leads to use a neural net with which it is possible to specify a total interconnected network.
Interpolation with statistical constraints satisfaction: by introducing supplementary neurons, it is possible to specify constraints upon zones. By this technique, during the interpolation process, certain statistical constraints are taken into account (details in (Pariente, Laurini 93b)). Note that this kind of constraints can be applied to data like gradients: it is imposed that for a certain zone, the mean value of gradients magnitudes is constrained to be fixed to a certain value.
Pyramidal Approach for Time-Consuming and Memory Space Optimization: a pyramidal architecture of neural network is included to the system, improving convergence speed. The first step of the pyramid includes few neurons, to accelerate the convergence. The next steps, the nets contain more neurons inheriting of their
[End Page 690]
parent neurons (see (Pariente, Laurini 93a)). The result of the pyramidal approach is very satisfying: the convergence speed is increased of about 120 (comparing with no pyramidal architecture).
Direction of Research (discussed in (Pariente, Laurini 93a)):
Our goal is to integrate a neural approach to existing OO models. The neural approach, as exposed beyond integrates both the geometrical and geographical data and a method of interpolation and extrapolation satisfying our constraints. By this way, a hierarchy of classes (geometrical. geographical, and neural) is specified which is able to solve the problem of continuous data in OO databases. Here is, very briefly presented, the suggested data model (see Figure 9). During a query (about the attribute value of a particular point), if the user needs an interpolation, a method will ask the neural net for the coordinates of the point, and this neural net will return the estimated value (in fact, the activation of the neuron corresponding to the coordinates). The class Neural net inherits of all information necessary to the interpolation and the extrapolation. Presently, our work focuses on the integration of our neural solution to existing OO-DBMS.
[End Page 691]
This paper has presented a new method of interpolation and extrapolation, based on neural nets, solving the problem of continuous spatio-temporal data in OO databases. Our approach has been the following: the studied space is seen as a grid of cells (Field-Orientation), each cell corresponding to a neuron. Each neural activation will be the average of activations of the neighbourhood. The solution uses the Hopfield neural model, respecting the finite differences method results. This new solution permits to define boundaries, and supplies a more realistic model of nature than classic interpolation and extrapolation methods. Very precise statistical constraints can be included, giving the opportunity of estimating unspecified extrema of the system. A pyramidal approach optimizes time-consuming and memory space, better than any other extensional interpolation method.
The estimates come from a surdetermined system (due to statistical and morphological constraints) which increases spatial information, and permits to take into account requirements during the approximation process. Current tests confirm the excellent quality of the estimates, and the entire satisfaction of our constraints. The neural method is much more precise than other interpolation methods, in particular when boundaries must be taken into account in the propagation of a phenomenon.
(Bourret & al. 91): Bourret P., Reggia J., Samuelides M. - RŽseaux Neuronaux, Une approche connexionniste de l'intelligence artificielle. Toulouse: Teknea, 1991. 269 pages. (Boursier & al. 93): Boursier P., Mullon C. - GIS Evolution: Object-Orientation, Multimedia, and Other Trends Stemming from Research in Computer Science. Proceedings of UDMS' 93. ADV Ed. Vienna Austria, 1993. pp 11-18.
(Couclelis 92): Couclelis H. - People Manipulate Objects (But Cultivate Fields). Proceedings of International Conference on GIS. Pisa - Italy. Lecture Note 639. Springer-Verlag, September 1992. pp 65 - 77.
[End Page 692]
(Delobel & al. 91): Delobel C., LŽcluse C., Richard P. - Bases de DonnŽes: des Systmes Relationnels aux Systmes ˆ Objets. Paris: InterEditions, 1991. 461 pages.
(Fisher 93): Fischer M. - From Conventional to Knowledge Based Geographical Information Systems. Proceedings of UDMS' 93. Vienna Austria, 1993. pp 17-25. (Hopfield 84): Hopfield J.J. - Neurons with Graded Response Have Collective Properties like Those of Two-State Neurons - PNAS - Washington - USA 1984. pp 3088 - 3092. (Jeansoulin 91): Jeansoulin R. - Extension, Intension et Interpolation Spatiales. Proceedings of RFIA 1991. Vol 1. Lyon 1991. pp 429-432.
(Kemp 93): Kemp K. - Environmental Modelling and GIS: Dealing with Spatial Continuity. Proceedings of HydroGIS'93, Vienna. IAHS Publ. N¡211, 1993. pp 107-115. (Kouam & al. 92): Kouam A., Badran F., Thiria S. - Approche MŽthodologique pour l'Etude de la PrŽvision ˆ l'aide des RŽseaux de Neurones. Proceedings of NeuroN”mes'92. EC2 Ed., Nanterre. pp 117-127.
(Lam 83): Lam N. S.-N. - Spatial Interpolation Methods: A Review. The American Cartographer, Vol. 10, No 2. New-York 1983. pp 129-149.
(Laurini, Milleret-Raffort 93): Laurini R., Milleret-Raffort F. - Les bases de donnŽes en gŽomatique. Herms, Paris, 1993. 340 pages.
(Laurini, Thompson 92): Laurini R., Thompson D. - Fundamentals of Spatial Information System. The APIC series no37, San Diego: Academic Press, 1992. 680 pages.
(Lippman 87): Lippmann R. P. - An Introduction to Computing with Neural Nets. IEEE ASP Magazine. Avril 1987. pp4-22.
(Matheron 67): Matheron G. - Kriging, or Polynomial Interpolation Procedures? Canadian Mining and Metallurgy Bulletin 60, No 665. pp 1246-1266.
(McClelland & al. 86): McClelland J., Rumelhart D. - The PDP Research Group. Parallel Distributed Processing. Academic Press, New-York, 1986. 351 pages.
(Pariente, Laurini 93a): Pariente D., Laurini R. - Spatio-Temporal Interpolation by means of Hopfield Neural Net. Reasearch Report INSA LISI. Octobre 1993. 21 pages.
(Pariente, Laurini 93b): Pariente D., Laurini R. - Interpolation and Extrapolation of Statistical Spatio-Temporal Data Based on Neural Networks. Proceedings of Workshop on New Tools for Spatial Analysis. Lisbon Portugal, EUROSTAT ed., November 1993. 10 pages.
(Pornon 92): Pornon H. - Les SIG: Mise en oeuvre et applications. Herms 1992. 158 pages.
(Rajagopalan & al. 92): Rajagopalan J., Jongepier A. G., van der Sluis L. - Short Term Load Forecasting Using Functional Link Networks: Results of a Feasibility Study - Proceedings of NeuroN”mes'92. EC2 Ed., Nanterre. pp 151-162.
(Servigne 93): Servigne S. - Base de DonnŽes GŽographiques et Photos AŽriennes: de l'Appariement ˆ la Mise ˆ Jour. Thse de Doctorat. INSA de Lyon, 1993. 152 pages. (Sontag 92): Sontag E. D. - Feedforward Nets for Interpolation and Classification. Journal of Computer and System Sciences. No 45. New-York, 1992. pp 20-48.
(van Gaas & al 93): van Gaans P. F. M., Burrough P. A. - The Use of Fuzzy Logic and Continuous Classification in GIS Applications: A Review Proceedings of EGIS'93. Vienna Austria 1993. pp 1025-1034.
[End Page 693]