& Faugeras, 
f Camera Lo- 
| Point Corre- 
8-37. 
nematic Mod- 
International 
Processing for 
ie, Italy. 
ned Trajectory 
n and Fusion. 
mage and Sig- 
. EOS, SPIE. 
ectification of 
rinity College 
ra Calibration 
[achine Vision 
Cameras and 
and Automa- 
cent Progress 
achine Vision. 
ssama, Craig, 
äs (eds), The 
>. 
ammetry. Sec- 
SPATIO-TEMPORAL INTERPOLATION OF CLASS VARIABLES 
BY INTEGRATING OBSERVATIONAL DATA AND A BEHAVIORAL MODEL 
WITH GENETIC ALGORITHM(GA) 
Shaobo HUANG* and Ryosuke SHIBASAKI** 
Center for Environmental Remote Sensing, Chiba University 
1-33 Yayoi-cho, Inage-ku, Chiba 263, Japan 
shaobo G rsirc.cr.chiba-u.ac.jp 
Institute of Industrial Science, University of Tokyo 
7-22-1 Roppongi, Minato-ku Tokyo 106, Japan 
shiba@ shunji.iis.u-tokyo.ac.jp 
KEY WORDS: Interpolation, Integration, Behavioral model, Genetic Algorithm(GA) 
ABSTRACT 
Spatio-temporal interpolation to generate voxel-field data in space-time domain from observational data is 
indispensable to many spatio-temporal analysis and visualization of dynamic spatial objects. However only very 
primitive interpolation methods such as nearest neighbor interpolation based on voronoi diagram are proposed for 
nominal or "class variable" data such as land use data. In interpolating nominal data with these primitive methods, 
we cannot make use of knowledge on spatial or temporal patterns or behaviors of the object. The authors proposed 
a spatio-temporal interpolation scheme for generating a voxel-field of nominal data under the framework of 
optimization of likelihood which is computed from the fitness to both observational data and expected patterns/ 
behaviors described by a behavioral model or rules specific to the object. Any model which provide likelihood or 
probability to a given spatio-temporal pattern can be used in this framework. For the optimization of likelihood, a 
genetic-algorithm (GA) was combined with Hill-climbing (HC) method to increase the efficiency and reliability of 
optimization. Through some experiments, it is demonstrated that GA/HC based interpolation method can generate 
voxel- fields which fits both to observational data and to knowledge on it's behavior and that the reliability of 
interpolation can be compared quantitatively in terms of the maximal likelihood. 
1. BACKGROUND & OBJECTIVE OF THE STUDY 
Temporal or dynamic analysis of spatial data are 
needed in various fields such as environmental systems 
analysis. One of the most fundamental problems which users 
are facing is the difficulties in generating spatio-temporal 
field(3D or 4D voxel field) of quality data for analysis 
through an interpolation or integration of observational data. 
It is because observational data from multi-sources 
sometimes have only sparse or biased distribution, different 
forms (point, edge, polygon and solid in a spatio-temporal 
space), different resolution and accuracy/reliability. 
In several fields, to improve reliability of spatio- 
temporal interpolation/ extrapolation in generating quality 
data, models and/or equations describing a mechanism and 
structure underlying a spatial or behavioral pattern is 
integrated with observational data. By integrating 
observational data and models describing underlying 
mechanisms and structures of object-phenomenon with a 
GIS, we can provide a GIS-based environment which allow 
dynamic update of spatio-temporal field of data whenever 
à new observational data and an improvement of models 
are given. 
Integration methods for data and models have been 
mainly developed for continuous variables such as 
temperature and precipitation in meteorology and 
oceanography. They are known as 4DDA (Four 
Dimensional Data Assimilation). For nominal or class 
variables such as land use types, there are only very primitive 
interpolation methods such as nearest neighbor interpolation 
and so forth. In this paper, the authors propose a integration 
methods of models and class data from multi-sources under 
the framework of optimization of likelihood of spatio- 
temporal events. For optimizing the likelihood, genetic 
algorithm (GA) is combined with classical “Hill climbing” 
method. Experimental results demonstrate that GA with HC 
can be successfully applied to the integration. 
2. GENETIC ALGORITHMS(GA) & NOMINAL 
VARIABLE INTERPOLATION 
2.1 Introduction of Genetic Algorithm (GA) 
Genetic algorithms are developed by John Holland 
and his colleagues as an approach to optimization which 
requires efficient and effective search in natural and artificial 
systems. They are search algorithms based on the 
mechanism of natural selection and evolution of natural 
803 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996