immetria
^ marmo
di copie
cnico di
).
AN ALGORITHMIC METHOD FOR REAL-TIME 3-D MEASUREMENT
X. Wang. & T.A. Clarke. Centre for Digital Image Measurement and Analysis, Department of Electrical, Electronic,
& Information Engineering, City University, Northampton Square, LONDON. EC1V 0HB. UK.
Commission V, Working Group 2
KEY WORDS: K 014 Engineering K 046 Adjustment K 113 Bundle K 176 Close_Range K 199 Real-time, Iterative, Least squares
ABSTRACT
Photogrammetric methods will increasingly be used for real-time applications. A typical requirement is the continuous 3-D
measurement of target locations which arise from three or more cameras at 0.02 ms. per measurement. In this situation user
interaction with algorithms and hardware will be relatively unimportant and a range of new issues will assume greater significance.
For instance, if 100-1000 target locations must be measured, then the computational effort must be minimised and if possible
completely predictable. Furthermore, the external parameters of the cameras must be checked and, if necessary, adjusted at the same
time as the 3-D co-ordinates are measured, while the internal parameters may be adjusted more slowly. Hence, under these
conditions, the characteristics of the currently available algorithms and the way in which they are applied must be studied.
This paper describes a methodology for solving collinearity equations based on iterative least squares estimation. Unlike the
traditional bundle adjustment which solves for the unknown co-ordinates of object targets and camera parameters simultaneously, a
solution for least squares estimation is developed which separates the parameters into two different groups, one for camera
parameters, and the other for the co-ordinates of object points. Each group of parameters is adjusted individually with the other
group fixed. While conventionally this process may be carried out just once for a variety of purposes, by repeating this process both
sets of parameters are gradually refined. Because the same functional model is used in the two steps and the process is still a
conventional least squares optimisation, the final result is the same as that obtained using the usual bundle adjustment but with a
considerable time and storage saving. The full covariance matrix is not available, but it will not always be necessary in real-time
systems and it can always be computed if required.
1. INTRODUCTION
In close range photogrammetry multiple CCD cameras are used
to capture images of the targeted object from different
viewpoints. Based on the geometric perspective principle, a set
of so called collinearity equations can be derived to establish
the relationships between 2-D observations on the camera
image planes and 3-D co-ordinates of object targets. By solving
the collinearity equations the 3-D co-ordinates of these targets
can be estimated. Three major steps are normally needed for
this procedure: (i) 2-D image data acquisition and target
location; (ii) target matching between different cameras; and
(iii) least squares estimation of the unknown parameters of the
functional model. Using powerful processors or hardware real-
time target location can be realised. Various approaches to
target matching are possible such as using epipolar lines and
epipolar planes (2-D and 3-D matching). However, solving
collinearity equations is still a considerable time consuming
procedure. It is not appropriate within the confines of this paper
to give a full review of the historical development of least
squares optimisation methods so some references and highlights
are given which are pertinent to the contents of this paper. The
principles of simultaneous least squares adjustment are well
known (Mikhail, 1981; Cooper, 1987). It is clear that this
method provides the de facto standard for the output from an
adjustment. However, the requirement for large matrix
inversions places large demands on storage and computing
power. To avoid this a sequential adjustment may be used as a
means of providing fast updates for a few parameters while not
requiring a full matrix inversion (Shortis, 1980; Gruen, 1985).
For most true real-time applications the direct linear transform
(DLT) has been used but it does not provide the highest
accuracy due to its modelling deficiencies and the reliance on
accurately measured control points for camera parameter
587
estimation (Marzan, 1975; Karara, 1980). For situations where
interior and exterior camera parameters are known a direct
spatial intersection may be used (Granshaw, 1980; Shmutter,
1974). Because each of these methods have deficiencies
research is necessary to find an alternative fast, robust and
flexible solution.
This paper discusses a two step separated least squares
adjustment. It can be shown that this method gives the same
results as the simultaneous bundle adjustment but with a
significant decrease in storage requirements and computational
time. While this method may not be new, to the authors
knowledge this is the first time the method has been discussed
in the context of real-time 3-D measurement. For example:
Shmutter & Perlmuter (1974) discussed the use of iterations of
the process of resection followed by intersection to save
computer storage space. In this case the functional model was
not the same in the two steps hence the results could not be the
same as for a simultaneous bundle adjustment; Miles (1963)
discussed the solution of normal equations by an iterative
process where submatrices representing part of the unknown
parameters were solved separately. This was done to save
computing storage requirements; and Hill et al (1995) described
a two stage iterative solution for image interpretation based on a
point distribution model.
2. THEORETICAL BACKGROUND FOR ITERATIVE
LEAST SQUARES ESTIMATION
Least squares estimation is an efficient method dealing with
redundant measurement containing random errors of normal
distribution. It has being widely used in control surveying and
photogrammetry to evaluate unknown parameters when the
measured elements are more in number than the minimum
needed for a unique solution. In this section the normal least
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B5. Vienna 1996
