Disclaimer: These papers are made available for personal use subject to author's and publisher's copyright.
We introduce a finite difference expansion for closely spaced cameras in projective vision, and use it to derive differential analogues of the finite-displacement matching tensors and constraints. The results are much simpler, more general and easier to use than Astrom & Heyden's time-derivative based `continuous time matching constraints'. We suggest how to use the formalism for `tensor tracking' -- propagation of matching relations against a fixed base image along an image sequence. We relate this to nonlinear tensor estimators and show how `unwrapping the optimization loop' along the sequence allows simple `linear n point' update estimates to converge rapidly to statistically near-optimal, near-consistent tensor estimates as the sequence proceeds. We also give guidelines as to when difference expansion is likely to be worthwhile as compared to a discrete approach.
Keywords: matching constraints, matching tensors, image sequences, tensor tracking, difference expansion.
We describe two direct quasilinear methods for camera pose (absolute orientation) and calibration from a single image of 4 or 5 known 3D points. They generalize the 6 point `Direct Linear Transform' method by incorporating some prior camera knowledge, while still allowing unknown calibration parameters to be recovered. Only linear algebra is required, the solution is unique in non-degenerate cases, and additional points can be included for improved stability. Both methods fail for coplanar points, but we give an experimental eigendecomposition based one that handles both planar and nonplanar cases. Our methods use recent polynomial solving technology, and we give a brief summary of this. One of our aims was to try to understand the numerical behaviour of modern polynomial solvers on some relatively simple test cases, with a view to other vision applications.
Keywords: Camera Pose and Calibration, Direct Linear Transform, Polynomial Solving, Multiresultants, Eigensystems.
This paper describes a theory and a practical algorithm for the autocalibration of a moving projective camera, from m>=5 views of a planar scene. The unknown camera calibration, and (up to scale) the unknown scene geometry and camera motion are recovered from the hypothesis that the camera's internal parameters remain constant during the motion. This work extends the various existing methods for non-planar autocalibration to a practically common situation in which it is not possible to bootstrap the calibration from an intermediate projective reconstruction. It also extends Hartley's method for the internal calibration of a rotating camera, to allow camera translation and to provide 3D as well as calibration information. The basic constraint is that the projections of orthogonal direction vectors (points at infinity) in the plane must be orthogonal in the calibrated camera frame of each image. Abstractly, since the two circular points of the 3D plane (representing its Euclidean structure) lie on the 3D absolute conic, their projections into each image must lie on the absolute conic's image (representing the camera calibration). The resulting numerical algorithm optimizes this constraint over all circular points and projective calibration parameters, using the inter-image homographies as a projective scene representation.
Keywords: Autocalibration, Euclidean structure, Absolute Conic and Quadric, Planar Scenes.
@inproceedings{Triggs:eccv98,
author="B. Triggs",
title="Autocalibration from Planar Scenes",
booktitle="European Conference on Computer Vision",
address="Freiburg",
month=jun, year=1998,
keywords="Autocalibration, Euclidean
structure, Absolute Conic and Quadric, Planar Scenes"}
Geometric fitting --- parameter estimation for data subject to implicit parametric constraints --- is a very common sub-problem in computer vision, used for curve, surface and 3D model fitting, matching constraint estimation and 3D reconstruction under constraints. Although many algorithms exist for specific cases, the general problem is by no means `solved' and has recently become a subject of considerable debate among researchers in statistical vision. This paper describes a new, more direct approach to geometric fitting, formulating it as the explicit recovery of a coherent, statistically optimal set of estimates of the ``underlying data points'' that gave rise to the observations, together with the estimated constraints which these points exactly verify. The method is implemented using an efficient constrained numerical optimization technique, and is capable of handling large problems with complex, constrained parametrizations. As examples of such problems, we consider the optimal estimation of the fundamental and essential matrices and the trifocal tensor, subject to their full sets of algebraic constraints. We also describe how our approach `reduces' to existing geometric fitting methods like gradient-weighted orthogonal least squares, and give a novel approach to robustness based on it.
Keywords: geometric fitting, orthogonal regression, statistical estimation, constrained optimization, matching tensors.
@unpublished{Triggs:iccv98,
author="B. Triggs",
title=" A New Approach to Geometric Fitting",
note="Submitted to 1998 International Conference on Computer Vision",
address="Bombay",
month=jan, year=1998,
keywords="geometric fitting, orthogonal regression,
statistical estimation, constrained optimization, matching tensors"}
We describe a new method for camera calibration and scaled Euclidean structure and motion, from three or more views taken by a moving camera with fixed but unknown intrinsic parameters. The motion constancy of these is used to rectify an initial projective reconstruction. Euclidean scene structure is formulated in terms of the {\bf absolute quadric} --- the singular dual 3D quadric ($4\times4$ rank 3 matrix) giving the Euclidean dot-product between plane normals. This is equivalent to the traditional absolute conic but simpler to use. It encodes both affine and Euclidean structure, and projects very simply to the dual absolute image conic which encodes camera calibration. Requiring the projection to be constant gives a bilinear constraint between the absolute quadric and image conic, from which both can be recovered nonlinearly from $m\ge3$ images, or quasi-linearly from $m\ge4$. Calibration and Euclidean structure follow easily. The nonlinear method is stabler, faster, more accurate and more general than the quasi-linear one. It is based on a general constrained optimization technique --- sequential quadratic programming --- that may well be useful in other vision problems.
Keywords: autocalibration, absolute quadric, multiple images, Euclidean reconstruction, constrained optimization.
@inproceedings{Triggs:cvpr97,
author="B. Triggs",
title="Autocalibration and the Absolute Quadric",
booktitle="Int. Conf. Computer Vision and Pattern Recognition",
address="Puerto Rico",
month=jun, year=1997,
keywords=" autocalibration, absolute quadric, multiple images,
Euclidean reconstruction, constrained optimization"}
This paper describes initial work on a family of projective reconstruction techniques that extract projection matrices directly and linearly from matching tensors estimated from image data. The simplest methods use fundamental matrices and epipoles, alternative ones use trilinear tensors. All of the data is treated uniformly, and there is no reliance on `privileged' images or tokens. The approach is based on `joint image closure relations' -- bilinear constraints between the projection matrices and their matching tensors, that express the fact that the latter derive from the former. The performance of the new techniques is quantified and compared with that of several existing methods.
Keywords: Multi-image Structure, Projective Reconstruction, Matching Tensors
@inproceedings{Triggs:bmvc96,
author="B. Triggs",
title="Linear Projective Reconstruction from Matching Tensors",
booktitle="British Machine Vision Conference",
address="Edinburgh",
month=sep, year=1996,
keywords="Multi-image Structure, Projective Reconstruction, Matching Tensors"}
A slightly revised version appears in the BMVC special issue of Image and Vision Computing:
@article{Triggs:ivc97,
author="B. Triggs",
title="Linear Projective Reconstruction from Matching Tensors",
journal=ivc,
pages="617--26",
volume=15,number=8,
month=aug, year=1997,
keywords="Multi-image Structure, Projective Reconstruction, Matching Tensors"}
Photogrammetry was developed in the last century in close connection with projective geometry, and the basic tools of projective geometry from Chasles, Sturm and Steiner where heavily used at this time. Since then, photogrammetry has moved towards highly technical issues and forgotten a little of its old bases. This tutorial provides an overview of the tools of projective geometry and some of their recent applications in computer vision. We will illustrate how they are particularly helpful when using uncalibrated cameras.
@unpublished{Mohr:Triggs:isprs96,
author="R. Mohr and B. Triggs",
title="Projective Geometry for Image Analysis",
booktitle="International Symposium of Photogrammetry and Remote Sensing",
address="Vienna",
month=jul, year=1996,
keywords="Projective Geometry, Visual Reconstruction, Invariants"}
This paper describes a family of factorization-based techniques for the recovery of 3D scene structure and camera motion from multiple uncalibrated perspective images of 3D points and lines, up to an overall projective transformation. The methods can be viewed as generalizations of the Tomasi-Kanade algorithm from affine cameras to fully perspective ones, and from points to lines. They make no restrictive assumptions about scene or camera geometry, and unlike most existing reconstruction techniques they do not rely on `privileged' points or images. All of the available image data is used, and each feature in each image is treated uniformly. The key to projective factorization is the recovery of a consistent set of {\bf projective depths} (projective scale factors) for the image points. We show how this can be done using fundamental matrices and epipoles estimated from image measurements, and present a detailed study of the performance of the new reconstruction techniques as compared to several existing methods. We also describe an approximate structure/motion factorization technique that gives similar results to Singular Value Decomposition based factorization, but runs much more quickly for large problems.
KEYWORDS: Projective Reconstruction, Multiple Images, Structure/Motion Decomposition, Matrix Factorization
@inproceedings{Triggs:cvpr96,
author="B. Triggs",
title="Factorization Methods for Projective Structure and Motion",
booktitle=cvpr, month=jun, year=1996,
address="San Francisco",
keywords="Projective Reconstruction, Multiple Images,
Structure/Motion Decomposition, Matrix Factorization",
comment="Tomasi-Kanade-like projective reconstruction method for
points and lines"}
We propose a method for the recovery of projective shape and motion from multiple images of a scene by the factorization of a matrix containing the images of all points in all views. This factorization is only possible when the image points are correctly scaled. The major technical contribution of this paper is a practical method for the recovery of these scalings, using only fundamental matrices and epipoles estimated from the image data. The resulting projective reconstruction algorithm runs quickly and provides accurate reconstructions. Results are presented for simulated and real images.
@inproceedings{Sturm:Triggs:eccv96,
author="P. Sturm and B. Triggs",
title="A Factorization Based Algorithm for Multi-Image
Projective Structure and Motion",
booktitle=eccv, pages="709--20", month=apr, year=1996,
address="Cambridge, England",
publisher="Springer-Verlag"}
This paper studies the geometry of multi-image perspective projection and the {\bf matching constraints} that this induces on image measurements. The combined image projections define a 3D {\bf joint image subspace} of the space of combined homogeneous image coordinates. This is a complete projective replica of the 3D world in image coordinates. Its location encodes the imaging geometry and is captured by the 4 index {\bf joint image Grassmannian} tensor. Projective reconstruction in the joint image is a canonical process requiring only a simple rescaling of image coordinates. Reconstruction in world coordinates amounts to a choice of basis in the joint image. The matching constraints are multilinear tensorial equations in image coordinates that tell whether tokens in different images could be the projections of a single world token. For 2D images of 3D points there are exactly three basic types: the epipolar constraint, Shashua's trilinear one, and a new quadrilinear 4 image one. For images of lines Hartley's trilinear constraint is the only type. The coefficients of the matching constraints are tensors built directly from the joint image Grassmannian. Their complex algebraic interdependency is captured by quadratic structural simplicity constraints on the Grassmannian.
@inproceedings{Triggs:iccv95,
author="B. Triggs",
title="Matching Constraints and the Joint Image",
booktitle=iccv,
address="Cambridge, {MA}",
editor="E. Grimson",
month=jun, year=1995,
keywords="multi-image stereo, projective reconstruction, matching
constraints, tensor calculus, geometric invariants"
comment="Compact summary of Triggs:ijcv95."}
This paper studies the geometry of perspective projection into multiple images and the matching constraints that this induces between the images. The combined projections produce a 3D subspace of the space of combined image coordinates called the {\bf joint image}. This is a complete projective replica of the 3D world defined entirely in terms of image coordinates, up to an arbitrary choice of certain scale factors. Projective reconstruction is a canonical process in the joint image requiring only the rescaling of image coordinates. The matching constraints tell whether a set of image points is the projection of a single world point. In 3D there are only three types of matching constraint: the fundamental matrix, Shashua's trilinear tensor, and a new quadrilinear 4 image tensor. All of these fit into a single geometric object, the {\bf joint image Grassmannian} tensor. This encodes exactly the information needed for reconstruction: the location of the joint image in the space of combined image coordinates.
@unpublished{Triggs:ijcv95,
author="B. Triggs",
title="The Geometry of Projective Reconstruction {I}:
Matching Constraints and the Joint Image",
note="Submitted to IJCV",
year=1995,
keywords="multi-image stereo, projective reconstruction,
matching constraints, tensor calculus, geometric
invariants"
comment="Nice theoretical study of the geometric structure
of multi-image projection and bi-/tri-/quad-linear
multi-image matching constraints. Uses tensors
and Grassmannian geometry. A summary appears in
Triggs:iccv95."}
Measurement uncertainty is a recurrent concern in visual reconstruction. Image formation and 3D structure recovery are essentially projective processes that do not quite fit into the classical framework of affine least squares, so intrinsically projective error models must be developed. This paper describes initial theoretical work on a fully projective generalization of affine least squares. The result is simple and projectively natural and works for a wide variety of projective objects (points, lines, hyperplanes, and so on). The affine theory is contained as a special case, and there is also a canonical probabilistic interpretation along the lines of the classical least-squares/Gaussian/approximate log-likelihood connection. Standard linear algebra often suffices for practical calculations.
@unpublished{Triggs:scene-rep95,
author="B. Triggs",
title="A Fully Projective Error Model for Visual Reconstruction",
note="Short version of work-in-progress on Projective Least Squares.
Originally submitted to {\em IEEE Workshop on Representations
of Visual Scenes}, Cambridge, MA, but rejected as too technical.
I really must get around to doing something with this...",
month=jun, year=1995,
keywords="least squares estimation, uncertainty models,
scene reconstruction, projective geometry"}
This paper describes an automated planner for visual inspection and monitoring tasks using a robot mounted CCD camera. It is capable of finding heuristically near-optimal viewing positions for a series of visual tasks, and of ordering them and planning robot paths between them to produce a near minimal cost overall task plan for the sequence. It has been optimized for intervention-style tasks with relatively large, cluttered workspaces, where it is difficult for a human operator to take account of all the constraints involved. The guiding principle of the work has been to aim for reliability by using quantitative, physically-based measures of quality wherever possible, and by using global search to ensure that possible solutions are not overlooked. We discuss a novel global function optimization technique based on decision theory and subjective models of function behaviour, that allows global viewpoint searches to run in the time usually required for local ones.
Keywords: Robot Task Planning, Machine Vision, Image Prediction, Global Optimization
@inproceedings{Triggs:Laugier:isrr95,
author="B. Triggs and C. Laugier",
title="Automatic Task Planning for Robot Vision",
booktitle="7$^th$ Int. Symposium on Robotics Research",
address="Munich", month=oct, year=1995,
comment="Global search to optimize heuristic view quality
metric for robot mounted camera. Takes accont of
kinematics, collisions, occlusion, focus... Task
scheduling and path planning for a sequence of
viewing tasks."}
Remote sensors such as CCD cameras can be used for a variety of robot sensing tasks, but given restrictions on camera location and imaging geometry, task constraints, and visual occlusion it can be difficult to find viewing positions from which the task can be completed. The complexity of these constraints suggests that automated, quantitative methods of sensor placement are likely to be useful, particularly when the workspace is cluttered and a mobile robot-mounted sensor is being used to increase the sensible region, circumvent occlusions, and so forth. We describe a camera placement planner designed to produce heuristically good static viewing positions for a robot-mounted CCD camera in an experimental workcell. It can be configured to produce viewpoints for a variety of tasks such as workpiece location, inspection and modelling; feedback control by visual servoing; and task progress monitoring. The planner uses a novel probability-based global search technique to optimize a viewpoint evaluation function that heuristically combines task, camera, robot and environmental constraints. The main advances over previous work are the incorporation of kinematic accessibility and collision constraints in the viewpoint evaluation and the introduction of a search technique powerful enough to handle the resulting strong nonlinearities.
@inproceedings{Triggs:Laugier:icra95,
author="B. Triggs and C. Laugier",
title="Automatic Camera Placement for Robot Vision Tasks",
booktitle="{IEEE} Int. Conf. Robotics {\&} Automation",
address="Nagoya, Japan",
year=1995,
comment="Global search to optimize heuristic view quality
metric for robot mounted camera. Takes accont of
kinematics, collisions, occlusion, focus..."}
This paper deals with the automation of dextrous grasping in a partly known environment using a stereo vision system and a multifingered hand mounted on a robot arm. Effective grasping requires a combination of sensing and planning capabilities: sensing to construct a well-adapted model of the situation and to guide the execution of the task, and planning to determine an appropriate grasping strategy and to generate safe, feasible manipulator motions. We propose an integrated approach that combines computer vision, path planning, and manipulator control in three complementary activities: the reconstruction of task-oriented models of the workspace, the determination of appropriate grasping configurations from computed `preshapes' of the hand, and the automatic generation and execution of hand/arm motions using a hybrid geometric path planner and a hybrid control system. This paper outlines the architecture of our system, discusses the new models and techniques we have developed, and finishes with a brief description of work-in-progress on the implementation and some preliminary experimental results.
@article{Bard:etal:ijrr95,
author="C. Bard and C. Bellier and J. Troccaz and C. Laugier and
B. Triggs and G. Vercelli",
title="Achieving Dextrous Grasping by Integrating Planning
and Vision Based Sensing",
journal=ijrr,
pages="445--64", volume=14, number=5, year=1995,
comment="Summary of grasping work on SECOND project. Mainly Christian Bard's
heuristic pre-shape based geometric grasp placement planner."}
The last few years have seen a burst of activity in motion planning for vehicles with rolling constraints such as cars and trucks with trailers. Our understanding of such {\bf nonholonomic} constraints has increased significantly and it is now possible to quickly plan complex parking and trailer-backing manoeuvres for these practically important systems. However the techniques used are highly mathematical and have not been easily accessible to a broad robotics-oriented audience. This paper presents an intuitive, geometrical introduction to the main mathematical definitions and theorems and summarizes some of the key practical approaches to nonholonomic vehicle planning.
@unpublished{Triggs:non-hol-planning:93,
author="B. Triggs",
title="Motion Planning for Nonholonomic Vehicles: An Introduction",
note="Survey paper presented at {\em Workshop on Computer
Vision and Robotics}, {Newton Institute of Mathematical
Sciences}, Cambridge, England in June 1993.",
institution="Oxford University Robotics Research Group",
address="Parks Rd, Oxford, England"}
We describe a sonar localisation system for autonomous mobile robot navigation in a known environment, which tries to extract as much information as possible from the sensors by building a detailed probabilistic model of each sonar event. It takes account of multiple hypotheses about the source of each signal and uses a probabilistic sensor fusion technique to merge the results into a single location update. The system is designed to run under our decentralised, highly parallel vehicle architecture, and we discuss some of the implementation techniques required to achieve this. The results of some initial simulations are presented.
@article{Triggs:ras94,
author="Bill Triggs",
title="Model-Based Sonar Localization for Mobile
Robots",
journal=ras, pages="173--86", volume=12, year=1994,
keywords="mobile robots, sonar sensing, Kalman
filtering, probabilistic data fusion",
note="Originally appeared in {\em Int. Workshop
Intelligent Robot Systems}, Zakopane,
Poland, 1993",
comment="Strongly geometric-model-bound
Kalman-filter-based sonar localization for mobiles (cf J. Leonard's work).
Tries to make the most of each sonar event, but ends up quite model
sensitive."}
After reviewing the advantages of supplying a robot with a geometric model of its surroundings, we discuss the design of a modular object-oriented database to support such a model, which is being implemented as part of the Oxford Autonomous Guided Vehicle project.
@inproceedings{Triggs:Cameron:asi90,
author="Bill Triggs and Stephen Cameron",
title="The {Oxford Robot World Model}",
booktitle="NATO ASI Expert Systems and Robotics",
volume="F-71", pages="275--284", year=1990,
address="Corfu",
publisher="Springer Verag",
comment="Initial version of Oxford AGV world model geometric
database. Not very conclusive."}