Stereo-Based Visual Odometry Method and System

• US 20080144925A1
• Filed: 08/03/2007
• Published: 06/19/2008
• Est. Priority Date: 08/15/2006
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Samarasekera, Supun, Kumar, Rakesh, Zhu, Zhiwei, Sawhney, Harpreet Singh, Naroditsky, Oleg, Oskiper, Taragay
• Granted Patent: US 7,925,049 B2
• Time in Patent Office: Days
• US Class Current: 382/154
• CPC Class Codes: G06T 2207/10021 Stereoscopic video; Stereoscopic image sequence
• CPC Class Codes: G06T 2207/20164 Salient point detection; Corner detection
• CPC Class Codes: G06T 2207/30212 Military
• CPC Class Codes: G06T 2207/30252 Vehicle exterior; Vicinity of vehicle
• CPC Class Codes: G06T 7/248 involving reference images or patches
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 2201/12 Acquisition of 3D measurements of objects

Abstract

A method for estimating pose from a sequence of images, which includes the steps of detecting at least three feature points in both the left image and right image of a first pair of stereo images at a first point in time; matching the at least three feature points in the left image to the at least three feature points in the right image to obtain at least three two-dimensional feature correspondences; calculating the three-dimensional coordinates of the at least three two-dimensional feature correspondences to obtain at least three three-dimensional reference feature points; tracking the at least three feature points in one of the left image and right image of a second pair of stereo images at a second point in time different from the first point in time to obtain at least three two-dimensional reference feature points; and calculating a pose based on the at least three three-dimensional reference feature points and its corresponding two-dimensional reference feature points in the stereo images. The pose is found by minimizing projection residuals of a set of three-dimensional reference feature points in an image plane.

Claims

1. A method for obtaining a pose of an object from a sequence of images, comprising the steps of:

(a) detecting at least three feature points in both the left image and right image of a first pair of stereo images at a first point in time;

(b) matching the at least three feature points in the left image to the at least three feature points in the right image to obtain at least three two-dimensional feature correspondences;

(c) calculating the three-dimensional coordinates of the at least three two-dimensional feature correspondences to obtain at least three three-dimensional reference feature points;

(d) tracking the at least three feature points in one of the left image and right image of a second pair of stereo images at a second point in time different from the first point in time to obtain at least three two-dimensional reference feature points; and

(e) calculating a pose based on the at least three three-dimensional reference feature points and its corresponding two-dimensional reference feature points in the stereo images.

2. The method of claim 1, wherein the step (e) further comprises the step of minimizing projection residuals of a set of three-dimensional reference feature points in an image plane.

3. The method of claim 2, wherein the step of minimizing projection residuals in an image plane farther comprises the step of finding

$\min $

∑

i = 1 n 

r i 2 



where 



r i = 

x i - x i ′







and 



x i ′

= Pr 



oj 

( RX i + T )

wherein Proj denotes the projection function,

wherein n>

=3,

wherein the reference features correspond to the at least three tracked features,

wherein R is a rotation matrix and T is the translation vector that maps the world coordinate system to the coordinate system of the stereo pair of images,

wherein x_i is the 2D coordinates of a feature point in the image, and

wherein x_i is its corresponding 3D coordinates in the world coordinate system.

4. The method of claim 1, wherein the step (a) further comprises the step of detecting at least three Harris corners.

5. The method of claim 1, wherein step (b) the step of finding the similarity of local image patches centered on the feature points, wherein a normalized correlation over an 11×

11-pixel window is used to measure the similarity, and wherein a feature that produces the highest similarity score is considered a match.

6. The method of claim 1, wherein (c) further comprises the step of triangulating the at least three two-dimensional feature correspondence from both the left image and the right image.

7. The method of claim 1, wherein (d) further comprises the steps of:

detecting at least three feature points in both the left image and right image of the second pair of stereo images at the second point of time and

matching the at least three feature points in one of the left image and right image of the first pair of stereo images to a corresponding one of the left image and the right image of the second stereo pair.

8. The method of claim 7, wherein the step of detecting the at least three feature points in both the left image and right image of the second pair of stereo images comprises the step of detecting at least three Harris corners.

9. The method of claim 1, wherein steps (d) and (e) are repeated for subsequent lime intervals.

10. The method of claim 9, wherein steps (a)-(e) are repeated at a later time period when the number of tracked features tracked in the subsequent time intervals relative to the first time interval falls below a predetermined number of features.

11. The method of claim 10, wherein the tracked features are landmarks with a distinctive intensity distribution.

12. The method of claim 11, wherein the predetermined number of features is determined based on a spatial distribution metric.

13. The method of claim 12, wherein the spatial distribution metric is calculated by performing the steps of:

dividing one of the left and right images at a subsequent time interval into 10×

10 grids of grid squares;

searching each grid square for the presence of at least one local landmark;

assigning an indicator indicating the presence of at least one local landmark to a grid square if at least one local landmark is present in the grid square; and

counting the number of grid squares containing at least one local landmark to determine a number to be assigned to the spatial distribution metric.

14. The method of claim 13, wherein the metric is set to about 50.

15. The method of claim 1, further comprising the step of applying one of an epipolar geometry constraint and a disparity constraint for reducing a search space during the performance of step (b).

16. The method of claim 1, wherein steps (d) and (e) are performed at a second point in time that is later than the first point in time during forward motion of images, and wherein steps (d) and (e) are performed at a second point in time that is earlier than the first point in time for reverse motion of images.

17. The method of claim 1, wherein a three-dimensional feature point and a corresponding two-dimensional reference point are discarded from a set of three-dimensional reference feature points and a corresponding set of two-dimensional reference points for obtaining a set of poses based on a Least Median of Squares approach.

18. A visual odometry system for estimating pose from a sequence of images, comprising:

means for obtaining a sequence of stereo images;

a processor and a memory for performing the steps of;

(a) detecting at least three feature points in both the left image and right image of a first pair of stereo images at a first point in time;

(b) matching the at least three feature points in the left image to the at least three feature points in the right image to obtain at least three two-dimensional feature correspondences;

(c) calculating the three-dimensional coordinates of the at least three two-dimensional feature correspondences to obtain at least three three-dimensional reference feature points;

(d) tracking the at least three feature points in one of the left image and right image of a second pair of stereo images at a second point in time different from the first point in time to obtain at least three two-dimensional reference feature points; and

(e) calculating a pose based on the at least three three-dimensional reference feature points and its corresponding two-dimensional reference feature points in the stereo images; and

a display for displaying the calculated pose.

19. The apparatus of claim 18, further comprising an TMU for sending measurements of orientation to said processor.

20. The apparatus of claim 19, further comprising a GPS receiver for sending a measurement of position to said processor.

21. The apparatus of claim 20, wherein said measurement of orientation and said measurement of position are integrated into a pose calculation by said processor using an extended Kalman filter framework.

22. The apparatus of claim 21, wherein filter dynamics for said extended Kalman filter framework is based on a constant velocity, constant angular velocity model.

23. A computer-readable medium carrying one or more sequences of instructions for estimating pose from a sequence of images, wherein execution of the one of more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

(a) detecting at least three feature points in both the left image and right image of a first pair of stereo images at a first point in time;

(b) matching the at least three feature points in the left image to the at least three feature points in the right image to obtain at least three two-dimensional feature correspondences;

(c) calculating the three-dimensional coordinates of the at least three two-dimensional feature correspondences to obtain at least three three-dimensional reference feature points;

(d) tracking the at least three feature points in one of the left image and right image of a second pair of stereo images at a second point in time different from the first point in time to obtain at least three two-dimensional reference feature points; and

(e) calculating a pose based on the at least three three-dimensional reference feature points and its corresponding two-dimensional reference feature points in the stereo images.

24. A method for obtaining a pose of an object from a sequence of images, comprising the steps of:

(a) detecting at least one feature point in both the left image and right image of a first pair of stereo images at a first point in time;

(b) matching the at least one feature point in the left image to the at least one feature point in the right image to obtain at least one two-dimensional feature correspondence;

(c) calculating the three-dimensional coordinates of the at least one two-dimensional feature correspondence to obtain at least one three-dimensional reference feature point;

(d) tracking the at least one feature point in one of the left image and right image of a second pair of stereo images at a second point in time different from the first point in time to obtain at least one two-dimensional reference feature point; and

(e) calculating a pose based on the at least one three-dimensional reference feature point and its corresponding two-dimensional reference feature point in the stereo images.

25. The method of claim 24, wherein the step (e) further comprises the step of minimizing projection residuals of a set of three-dimensional reference feature points in an image plane.

26. The method of claim 25, wherein the step of minimizing projection residuals in an image plane further comprises the step of finding

$\min $

∑

i = 1 n 

r i 2 



where 



r i = 

x i - x i ′







and 



x i ′

= Pr 



oj 

( RX i + T )

wherein Proj denotes the projection function,

wherein n>

=3,

wherein the reference features correspond to the at least three tracked features,

wherein R is a rotation matrix and T is the translation vector that maps the world coordinate system to the coordinate system of the stereo pair of images,

wherein x_i is the 2D coordinates of a feature point in the image, and wherein X_i is its corresponding 3D coordinates in the world coordinate system.