Method and apparatus for finding feature correspondences between images captured in real-world environments

• US 7,356,164 B2
• Filed: 05/30/2003
• Issued: 04/08/2008
• Est. Priority Date: 05/30/2003
• Status: Expired due to Fees

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Aliaga, Daniel G., Carlbom, Ingrid Birgitta, Funkhouser, Thomas A., Yanovsky, Dimah V.
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): ALLISON, ANDRAE S
• Application Number:
  US10/452,019
• Publication Number:
  US 20040240707A1
• Time in Patent Office: 1,775 Days
• Field of Search: 382/103, 382/190, 382/154, 382/206, 382/284, 382/107, 345/419, 345/427, 345/423
• US Class Current: 382/103
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

Techniques for computing a globally consistent set of image feature correspondences across a wide range of viewpoints suitable for interactive walkthroughs and visualizations. The inventive approach takes advantage of the redundancy inherent in a dense set of images captured in a plane (or in higher dimensions, e.g., images captured in a volume, images captured over time, etc). The technique may detect features in a set of source images and track the features to neighboring images. When features track to the same position in the same image, they are flagged as potential correspondences. Among the potential correspondences, the technique selects the maximal set using a greedy graph-labeling algorithm (e.g., best-first order). Only correspondences that produce a globally consistent labeling are selected. After globalization is done, a set of features common to a group of images can be quickly found and used to warp and combine the images to produce an interpolated novel view of the environment.

Claims

1. A method of processing images captured from an environment, comprising the steps of:

detecting features in a set of two or more source images;

tracking the features to two or more destination images that surround the two or more source images;

identifying potential correspondences between features from different source images that track to the same image and that satisfy a feature similarity metric; and

selecting a maximal set of corresponding features from among the potential correspondences to form a set of image feature that is globally consistent across the set of two or more source images.

2. The method of claim 1, wherein the features may be tracked from each source image along a set of non-intersecting paths that spread radially outwards.

3. The method of claim 1, wherein the set of source images comprises a subset of the images captured from the environment.

4. The method of claim 1, wherein the feature similarity metric may be satisfied via any of multiple viewpoint paths between images.

5. The method of claim 4, wherein the feature similarity metric comprises one or more of the following thresholds:

(i) a maximum distance in pixels between tracked features in the same image;

(ii) a tracking quality threshold;

(iii) a feature quality threshold; and

(iv) a feature correlation threshold.

6. The method of claim 1, wherein the maximal set selection step utilizes a re-labeling process to select a globally consistent set of image features.

7. The method of claim 1, further comprising the step of utilizing the globally consistent set of image feature correspondences to reconstruct one or more images.

8. The method of claim 7, wherein image reconstruction comprises the steps of:

determining features common to a group of images based on the globally consistent set of image feature correspondences; and

warping and combining the images to generate an interpolated novel view of the environment.

9. The method of claim 1, wherein the feature tracking step and the potentially corresponding feature identification step may be interleaved with the maximal set selection step.

10. Apparatus for processing images captured from an environment, comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) detect features in a set of two or more source images;

(ii) track the features to destination images that surround the two or more source images;

(iii) identify potential correspondences between features from different source images that track to the same image and that satisfy a feature similarity metric; and

(iv) select a maximal set of corresponding features from among the potential correspondences to form a set of image feature that is globally consistent across the set of two or more source images.

11. The apparatus of claim 10, wherein the features may be tracked from each source image along a set of non-intersecting paths that spread radially outwards.

12. The apparatus of claim 10, wherein the set of source images comprises a subset of the images captured from the environment.

13. The apparatus of claim 10, wherein the feature similarity metric may be satisfied via any of multiple viewpoint paths between images.

14. The apparatus of claim 13, wherein the feature similarity metric comprises one or more of the following thresholds:

(i) a maximum distance in pixels between tracked features in the same image;

(ii) a tracking quality threshold;

(iii) a feature quality threshold; and

(iv) a feature correlation threshold.

15. The apparatus of claim 10, wherein the maximal set selection step utilizes a re-labeling process to select a globally consistent set of image features.

16. The apparatus of claim 10, wherein the at least one processor is further operative to utilize the globally consistent set of image feature correspondences to reconstruct one or more images.

17. The apparatus of claim 16, wherein image reconstruction comprises:

determining features common to a group of images based on the globally consistent set of image feature correspondences; and

warping and combining the images to generate an interpolated novel view of the environment.

18. The apparatus of claim 10, wherein the feature tracking operation and the potentially corresponding feature identification operation may be interleaved with the maximal set selection operation.

19. A computer program product for processing images captured from an environment, comprising a computer readable medium containing one or more computer programs which when executed by a computer processor implement the steps of:

detecting features in a set of two or more source images;

tracking the features to two or more destination images that surround the two or more source images;

identifying potential correspondences between features from different source images that track to the same image and that satisfy a feature similarity metric; and

selecting a maximal set of corresponding features from among the potential correspondences to form a set of image features that globally consistent across the set of two or more source images.