Recursive Spatio-Temporal Function Estimation
William S. Kerwin and J.L. Prince
Overview
|
Interpolating
or smoothing scattered data is an often encountered problem
in science and engineering. When data depend on time and space,
existing interpolation methods can rapidly become overwhelmed
with data. In this work, we have developed a new, computationally
efficient method for estimating smooth spatial functions from
observations distributed over time and space. The method estimates
the current spatial distribution of a function that has been
observed at regular intervals in time. Potential uses include
estimating the temporal changes in geophysical/ecological
data, tracking the movement of a surface over time, and determining
time-varying flow fields.
The method itself
combines features of two well-known estimation tools: 1) kriging
(a spatial interpolator) and 2) Kalman filtering (a computationally
efficient recursive estimator). The stochastic models used
in each of these methods are combined into a state equation
representation we call the "kriging update model" that permits
a recursive solution, akin to Kalman filtering, for estimating
a function. The state equation representation preserves the
principle assumption of kriging, that the mean is deterministic
but unknown. We derive the estimate using best linear unbiased
estimation, and state the result in a concise algorithm for
general use in arbitrary spatial dimensions.
|
|
Problem
Statement
|
The
method is best described with reference to the figure above.
The far left Column (a) represents some function of both time
and space z(x,t). The plot shows the function at each of ten
time frames; that is z(x,t1) through z(x,t10).
The
second Column (b) shows observations of the function at each
of the ten time frames. Random noise has been added to the
samples to simulate an imperfect observation process. Our
goal is to estimate the sequence of functions in Column a
given the observations in Column b. This goal poses two challenges:
to reject observation noise and to interpolate between observation
locations.
|
Past
Work
|
One possible solution
is to individually apply a spatial interpolator such as kriging
to the observations made at each time. Kriging models a function
as z(x) = u(x) + m(x), where u(x) is a zero-mean random component
and m(x) is an unknown, deterministic mean function. The function
estimate is determined using best linear unbiased estimation
(BLUE). Column c above shows the results of applying kriging
to the data in Column b.
This approach
does not prove satisfactory. One of the principle drawbacks
is that it does not take advantage of the slow temporal variation
of the function. At the second time frame, we also have data
from the first time frame; at the third time frame, we also
have data from the first two time frames and so on. The method
should use this past data and the temporal smoothness to produce
a better estimate. While there exist extensions of kriging
that do this (space-time kriging and cokriging), they run
into a new challenge. As the number of time frames grows,
the number of past observations becomes too large to handle
practically.
|
Our
Method
|
To overcome this
growing data problem we have proposed a new update model for
the data in which z(x,tn) = z(x,tn-1) + u(x,tn) + m(x,tn).
The update components u(x,tn) and m(x,tn) are a zero-mean,
stochastic portion and an unknown, deterministic mean, respectively,
as in kriging. Hence, we call this model the kriging update
model.
Based on this
data model we have derived a method for computing the best
linear unbiased estimate of the function. The method is recursive
so that the current estimate is simply an update of the previous
estimate. Computing the estimate at each time frame involves
no more computation than individually kriging the functions.
However, the estimates include information from all past time
frames in addition to the present one. The resulting improvement
is shown in Column d above, showing the results of our algorithm
applied to the data in Column b.
|
Discussion
|
This example is
a simple one-dimensional one. The algorithm actually works
in spaces of any dimension. Details of the method, the model
and a statement of the algorithm may be found in the publications
listed below. The paper also discusses an application in medical
imaging.
|
Publications |
- W.S. Kerwin
and J.L. Prince, "The Kriging Update Model and Recursive
Time-Space Function Estimation," IEEE Transactions
on Signal Processing, 47(11):2942-2952, November 1999.
- W.S. Kerwin
and J.L. Prince, "The Kriging Update Model and Recursive
Time-Space Function Estimation," JHU Tech Rep ECE 98-11,
28 pages, October, 1998.
- W.S. Kerwin
and J.L. Prince, ``Recursive Filtering and Interpolation
Algorithm for Function Sequences of Any Dimension,'' Proc.
Image and Multidimensional Digital Signal Processing (IMDSP)
Workshop, Alpbach, Austria. July, 1998, pp. 239-242.
|