ON-LINE TRIANGULATION FOR AUTONOMOUS VEHICLE NAVIGATION
Kenneth Edmundson, Dr. Kurt Novak
Department of Geodetic Science and Surveying
The Ohio State University
1958 Neil Ave.
Columbus, Ohio 43210
PURPOSE:
At the Center for Mapping of The Ohio State University, a mobile mapping workstation has
been built which integrates a GPS receiver, an inertial system, and a stereo-vision system
for the automatic capture of highway data.
with vehicle positions at regular increments.
applying bundle triangulation.
Digital stereo-images are captured together
They can be connected into a strip by
This paper focuses on the development of an algorithm to
utilize the stereo-vision system in sequential triangulation mode.
This approach can be
directly applied to intelligent vehicle highway systems(IVHS) to automatically navigate
a vehicle along a road.
Recursive problems, such as on-line triangulation require algorithms providing real-time
responses. Givens Transformations offer an ideal solution to such problems as they yield
a direct solution to linear least-squares problems without forming the normal equations
and permit continuous monitoring of the solution vector and necessary statistical measures.
Givens Transformations without square roots require significantly less operations than
conventional Givens.
In this paper the mathematical formulation is given, followed by a
description of the triangulation program developed for this study. Various implementation
problems are addressed and results of a practical example are presented.
KEY WORDS: Givens, GPS, Triangulation, IVHS. Navigation.
INTRODUCTION
Various sensors have been utilized independently for
the collection of data for Geographic Information
Systems(GIS) and for the production of digital maps.
The Global Positioning System(GPS) can produce three
dimensional ground coordinates by triangulation using
measurements to a minimum of four satellites.
Overlapping stereo-images are commonly used to map
surface details and for the extraction of elevations.
Inertial systems, when carried in a vehicle,
continuously record velocity and acceleration changes
and thus can be applied to the surveying of linear
features such as roads. During the past two years,
research conducted by the Center for Mapping at The
Ohio State University, focused on the integration of
a GPS receiver, an inertial system, and a stereo-
vision system into a van for the automatic recording
of data from the highway environment[Novak,
1990;Bossler,et.al., 1991]. The prototype of this
vehicle appears in Plate 1.
An important problem associated with GPS occurs when
the satellite signals are unable to reach the
receiver antenna. This problem, called "loss-of-
lock", occurs when obstructions such as buildings,
trees, and bridges come between the satellite and the
antenna. The inertial system can be used to overcome
this problem. It can provide position information
during loss-of-lock periods, knowing the GPS
coordinates of the vehicle before and after the
satellite signal was interrupted.
The stereo-vision system offers another solution to
the same problem. Stereo-pairs captured during loss-
of-lock can be tied together and controlled by the
GPS coordinates of the van before and after signal
loss. Utilizing on-line triangulation techniques, a
strip of stereo-pairs can be formed in a sequential
manner. This is advantageous because of the
sequential nature of the data collection. Thus, the
vehicle can literally be "navigated" from one stereo-
pair to the next. In this article, we investigate
the feasibility of using visual navigation to bridge
over areas without satellite lock.
Before a photogrammetric solution of this navigation
problem can be derived, it is necessary to
differentiate between sequential and simultaneous
adjustment solutions. The appropriate simultaneous
solution for strip triangulation is the well known
bundle adjustment. This method requires all data
collection to be completed before the adjustment.
The sequential solution allows the strip to be built
model by model, and, additionally, permits the
editing of data at any stage of the process.
The very definition of "on-line triangulation"
requires that results be available at any time during
processing. Due to the sequential nature of the
measurement process, the use of sequential algorithms
follows naturally. As on-line triangulation is an
interactive process between the operator and the
computer, real-time or near real-time responses are
necessary. Thus, there has been a continuing search
for fast and efficient algorithms for sequential
adjustment.
The most prominent approaches are the "Kalman-form",
which updates the inverse of the normal equations
[Mikhail,Helmering,1973], the "Triangular Factor
Update" (TFU), that updates the factorized normals
directly [Gruen,1982], and Givens Transformations
which updates the factorized normal equation matrix
[Blais, 1983]. Our algorithm is based upon Givens
Transformations.
The Givens method is an orthogonal transformation
technique based on the use of plane rotations to
annihilate matrix elements. This approach provides
a direct way for solving linear least-squares
problems without forming the normal equations. Since
all updating is done in the factorized normals,
numerical instabilities associated with forming and
solving the normal matrix are avoided. Large, sparse
design matrices are readily exploited by Givens
Transformations.
Pertinent to the on-line triangulation problem,
Givens Transformations process one row of the design
matrix at a time, and thus can be used for the
sequential addition or deletion of observations in an
interactive environment. Additionally, the solution
vector is available at any stage by simply performing
a back substitution in an upper triangular equation
system. Givens Transformations can also be used to
update the cofactor matrix simultaneously with the
solution, thus providing the necessary statistical
measures for analysis. This method adapts easily to
handle weighted observations [Gentleman, 1973;
Blais, 1983] in addition to weighted parameters.
Plane rotations are usually designed to annihilate
only one element at a time. The inherent weakness is
that for each annihilated element, one square root
is required, and additionally, for each pair of
elements, four multiplications are needed. For this
reason, Givens Tranformations were not considered as
a viable solution when results are required in real-
time. However, this changed when Gentleman[1973]
proposed a modification which eliminates the square
roots, reduces the number of multiplications by one-
fourth, and facilitates weighted least squares at no
extra cost.
In this study, Givens Transformations without square
roots are used for the on-line triangulation of
strips of sequential stereo-pairs obtained by the
mapping van. The program developed to solve this
problem allows for a variable size parameter vector,
the update of the solution vector, and the ability to
perform a simultaneous solution at the operators
convenience.
