KLT 算法 detection and tracking of point features1991.pdf

Shape and Motion from Image Streams: a Factorization Method—Part 3

Detection and Tracking of Point Features

Technical Report CMU-CS-91-132

Carlo Tomasi Takeo Kanade

April 1991

Abstract

The factorization method described in this series of reports requires an algorithm to track the motion of features in an

image stream. Given the small inter-frame displacement made possible by the factorization approach, the best tracking

method turns out to be the one proposed by Lucas and Kanade in 1981.

construction.

We show by experiment that the performance of both the selection and the tracking algorithm are adequate for our

factorization method, and we address the issue of how to detect occlusions. In the conclusion, we point out specific

open questions for future research.

Chapter 1

Introduction

The factorization method introduced in reports 1 and 2 of this series [12] [13] requires selecting and tracking of

features in an image stream. In this report we address the issues involved, and present our algorithm.

In general, two basic questions must be answered: how to select the features, and how to track them from frame

to frame. We base our solution to the tracking problem on a previous result by Lucas and Kanade [6], who proposed a

In practice, these approximations introduce errors, but a few iterations of the basic solution step suffice to converge.

The result is a simple, fast, and accurate registration method.

The first question posed above, however, was left unanswered in [6]: how to select the windows that are suitable

for accurate tracking. In the literature, several definitions of a ”good feature” have been proposed, based on an a priori

notion of what constitutes an ”interesting” window. For example, Moravec and Thorpe propose to use windows with

high standard deviations in the spatial intensity profile [8], [11], Marr, Poggio, and Ullman prefer zero crossings of

the Laplacian of the image intensity [7], and Kitchen, Rosenfeld, Dreschler, and Nagel define corner features based on

first and second derivatives of the image intensity function [5], [2].

In contrast with these selection criteria, which are defined independently of the registration algorithm, we show in

this report that a criterion can be derived that explicitly optimizes the tracking performance. In other words, we define

1

Chapter 2

Feature Tracking

As the camera moves, the patterns of image intensities change in a complex way. In general, any function of three

variables I(x, y, t), where the space variables x and y as well as the time variable t are discrete and suitably bounded,

can represent an image sequence. However, images taken at near time instants are usually strongly related to each

other, because they refer to the same scene taken from only slightly different viewpoints.

in plain English, a later image taken at time t + τ can be obtained by moving every point in the current image, taken

at time t, by a suitable amount. The amount of motion d = (ξ, η) is called the displacement of the point at x = (x, y)

between time instants t and t + τ , and is in general a function of x, y, t, and τ.

Even in a static environment under a constant lighting, the property described by equation (2.1) is violated in many

situations. For instance, at occluding boundaries, points do not just move within the image, but appear and disappear.

Furthermore, the photometric appearance of a region on a visible surface changes when reflectivity is a function of the

viewpoint.

However, the invariant (2.1) is by and large satisfied at surface markings, and away from occluding contours. At

An important problem in finding the displacement d of a point from one frame to the next is that a single pixel cannot

be tracked, unless it has a very distinctive brightness with respect to all of its neighbors. In fact, the value of the pixel

can both change due to noise, and be confused with adjacent pixels. As a consequence, it is often hard or impossible

to determine where the pixel went in the subsequent frame, based only on local information.

Because of these problems, we do not track single pixels, but windows of pixels, and we look for windows that

contain sufficient texture. In chapter 4, we give a definition of what sufficient texture is for reliable feature tracking.

Unfortunately, different points within a window may behave differently. The corresponding three-dimensional

surface may be very slanted, and the intensity pattern in it can become warped from one frame to the next. Or the

window may be along an occluding boundary, so that points move at different velocities, and may even disappear or

appear anew.

2

velocities can be associated to different points of the window.

This approach was proposed already in [6], and was recently explored in a more general setting in [10]. We feel,

however, that in cases where the world is known to be rigid the danger of over-parametrizing the system outweighs

the advantages of a richer model. More parameters to estimate require the use of larger windows to constrain the

parameters sufficiently. On the other hand, using small windows implies that only few parameters can be estimated

reliably, but also alleviates the problems mentioned above.

We therefore choose to estimate only two parameters (the displacement vector) for small windows. Any dis-

crepancy between successive windows that cannot be explained by a translation is considered to be error, and the

displacement vector is chosen so as to minimize this residue error.

Formally, if we redefine J (x) = I(x, y, t + τ), and I(x − d) = I(x − ξ, y − η, t), where the time variable has

In this expression, w is a weighting function. In the simplest case, w could be set to 1. Alternatively, w could be a

Gaussian-like function, to emphasize the central area of the window. The weighting function w could also depend on

the image intensity pattern: the relation (3.3) holds for planar patches, and w could be chosen, as suggested in [6], to

de-emphasize regions of high curvature.

Several ways have been proposed in the literature to minimize this residue (see [1] for a survey). When the

displacement d is much smaller than the window size, the linearization method presented in [6] is the most efficient

way to proceed.

3