A structure and motion recovery is one of the fundamental problems in computer vision due to large spectrum of applications ranging from mobile robots navigation to multimedia and different tracking problems.

One of the most widely used approaches to structure and motion (SM) recovery is the factorization algorithm proposed by Tomasi and Kanade [8]. Image feature points are tracked over several frames and the SM parameters are computed using a singular value decomposition (SVD). This algorithm cannot be used for real time applications as this is a batch method and can only compute the parameters once all measurements have been made. The algorithm is also computationally very expensive (due to the use of the SVD). Morita and Kanade [5] developed a sequential version that has almost the same accuracy but has a much lower computational burden. The issues not addressed in these papers were how to prevent outliers incorrectly biasing the result, and how to handle a set of feature points that changes dynamically.

Held [1] partially extended the Morita and Kanade algorithm to include new features. The video sequence was divided into subsequences, and the features tracked over each subsequence. To track the features between the subsequences common tracked features between consecutive subsequences were needed. The algorithm was verified using synthetic measurements only, with added Gaussian noise. McLauchlan et al. [2,3] used the variable state-dimension filter (VSDF) to handle the problem of missing and new features. They posed the structure from motion problem as a parameter estimation problem and solved it by using the Extended Kalman Filter (EKF). They updated the structure and only the last motion estimate at each time step and therefore achieved a low computational cost O ( k ) compared to when the complete motion matrix has been updated. The authors mentioned outlier rejection, but they gave neither a method nor a reference to handle this problem. Another limitation of their algorithm is that features that have been obscured and reappear are treated as new feature points, and are not recognised as a previously tracked feature.

In this paper we present an algorithm that iteratively computes the structure and motion parameters at each time step. It has the same computational cost O ( n + k ) as McLauchlan et al , but it updates both the structure and the complete motion parameters, so it converges to the true solution. It is made possible by noting that structure should remain constant over time and hence we refine our estimate at each time step. Motivated by the work of Reid and Murray [7] we have extended their algorithm so that it can easily include new features and recover the complete structure and motion provided that in each set of three consecutive frames there are at least four successfully matched feature points. This is a reasonable condition in practice and is almost always fulfilled when using a good corner detector as the feature point detector. Further, we have detected outliers, which are feature points that are inconsistent with the recovered motion model, at each time step. We detect outliers as points that have a large influence on the estimated parameters and their standard variation. Finally we have developed a procedure that checks whether newly appeared features are genuinely new, or old features that have reappeared.

In this paper we assume an affine camera model which has the form:

where p _I ( j ) is the projection of i ^th point onto the j ^th image, and i and j vary from 1… n and 1… k respectively. To compute the SM parameters using all the measurement equations, one must minimise the objective function:

but for real time implementation the parameters must be computed following the acquisition of each frame. It may be shown that the translational component t ( j ) at each frame is given by the centroid of the feature locations and equation (2) can now be rewritten as where , or in matrix form:

Hence the structure and motion are given by the eigenvalue decompositions of and respectively.

Unlike Morita and Kanade who have computed motion and structure by iteratively updating equation (4) and McLauchlan who applied EKF to the measurement equation (2), we have employed direct minimisation of the cost function (3). For some initial number of frames (usually 3) we have initialised motion and structure matrices by solving equation (4). After a new frame has been acquired the cost function is iteratively minimised taking previously computed structure and motion parameters as initial values. Here we explain three methods, two of them we developed (1 and 2).

First, let us suppose that cost function C ( k ) has been minimised, i.e. that the values M , t and S ( k ) are known. Our goal is to minimise cost function at the next time step:

where is a binary weight which expresses presence ( = 1) or absence ( = 0) of i ^th feature in j ^th frame. Since it does not effect the rest of derivation it will be omitted for the clarity. Equation (5) may be rewritten in more concise form as:

It will be seen later that it is helpful to group motion parameters into a motion vector rather than using M and t separately and we define the motion vector as . To minimise the cost function we differentiate (6) to obtain

where

There are three different ways to solve this equation, and we will show them and give some comparison.

1. Linearizing (7) around previously estimated structure and motion and assuming that D _I and E ( j ) are constant. Since

equation (7) can be written as the linear system of n + k +1 equations

where

but the whole expression. Interestingly, we obtained a set of linear equations of the same form as (8), the only difference being that

can be written as:

and thus, equation (7) can be rewritten as

or,

We used the second method because it has quadratic converge, and usually found three to five iterations sufficient. For the initial estimates of the parameters at each stage of the algorithm we used the parameters determined in the previous stage.

where M _S and t _S can be found using equation (5), then we find the structure vector S _R for the remaining set of matched corner points C _R by solving the equation

where W _R is the measurement matrix corresponding to C _R . The position error from the model ( M _S , t _S ) is given by

The next step is outlier rejection. For each point we determine the initial weight w _i .

Then we compute the robust standard deviation estimate as

By matching feature points between three images we can make use of the rigidity constraint. For each set of three frames, the corners are matched between the consecutive frames and the outliers rejected. Then, given the position of a feature in any two images, and the motion parameters M and t, its position in the third image is uniquely determined. Hence, by using this procedure, we can detect those outliers which are "correctly" matched over each pair of consecutive images (satisfy the epipolar constraint) but do not satisfy the rigidity constraint over three frames.

New feature points will be included in the measurement matrix if they appear and are matched in three consecutive frames. Consider frames n -2, n -1, n and n +1, and let C ₁ denote a set of features which are matched over frames n -2 to n , while C ₂ denotes the set of features which have been matched only over frames n -1 to n +1. Let P be an arbitrary feature from C ₂ and let p ^{( n )} denote its image projection in the n ^th frame. Since the motion (and structure) parameters are estimated over the first n frames, the structure parameter S of this point is found by solving the set of equations,

Hence the initial parameters for the algorithm in Section 3.1 have been found.

Before we add the point from C ₂ to the measurement matrix, and perform an update, we first check whether this point is genuinely new or whether it is an old feature that has reappeared. Let P _i be a previous feature that had disappeared and P _l be an arbitrary feature from C ₂ . We can say that P _i and P _l represent the same feature if the world distance between them is small enough, i.e . if

Our algorithm has been verified by testing on several video sequences.

POV image sequence

This sequence consists of 90 frames of an object rotating around the fixed axes (see Fig. 1 a–c). The rotation is a constant four degrees per frame. Corners are detected and matched using an algorithm similar to [10]. This is a difficult sequence, because no single corner appears in all the frames, and because the number of points is small - it varies from 6 to 13 per frame. For this reason, both algorithms proposed by Tomasi and Kanade [9] and Morita and Kanade [6] are not applicable for this sequence as the number of features is not constant. The VSDF algorithm may be used, but in its original form (without the reappearance of features) this will have a growing number of features as old features reappear, this will lead to slower computation and greater errors in the calculated parameters.

Using our algorithm we obtained total of 22 features, and by disregarding all of them which appeared in less than 20 frames we were left with total of 17 features which is quite close to the 16 distinguished corners on the object. The corners that have been effectively tracked over all the frames are shown in Fig 1d. As we can see they are all close to the true locations, including those which are currently occluded or not detected. Some distortion is present due to imperfection of affine model, but the structure has been correctly recovered.

This sequence consists of 197 points tracked over 181 frames. Corners were detected in the first image and their positions in consequent images were determined using an optical flow technique [8] (see Fig. 2 a, b). The SM parameters were calculated using the SVD algorithm and our algorithm, which produced the same results, but the former took about an order of magnitude longer to compute. As in [4], we have found that updating motion parameters over all previous frames in each step is unnecessary, but unlike them,

we performed multiple iterations for accuracy. A very important step here is the outlier detection. Since we have matches over all frames, the rigidity constraint were checked not over last three frames only, but over the whole sequence. The comparison of mean squared error with, and without outlier removal is given in Fig. 2c.

This paper addresses a practical problem in structure and motion recovery for real image sequences. The first problem is speed to allow real time operation, and we presented a fast batch recursive algorithm for structure and motion parameter computation and have shown that it gives the same results as Tomasi and Kanade method. Furthermore, we have developed a technique for detecting feature points inconsistent with the motion model, and by disregarding these the performance of the algorithm is enhanced. This paper is the first one (to our knowledge) that deals the problem of feature dropout and reappearance. We developed a procedure that allows previously lost features to reappear in the sequence and have experimentally verified its operation.

The hotel image sequence (along with corners and displacements) was provided by the Modeling by Videotaping group in the Robotics Institute, Carnegie Mellon University. Financial support was provided by the Australian Research Council.