System and methods for world-scale camera pose estimation

• US 9,324,151 B2
• Filed: 12/08/2012
• Issued: 04/26/2016
• Est. Priority Date: 12/08/2011
• Status: Active Grant

• Current Assignee: Cornell University
• Original Assignee: Cornell University
• Inventors: Huttenlocher, Daniel, Snavely, Noah, Li, Yungpeng
• Primary Examiner(s): Dunphy, David F
• Application Number:
  US14/361,547
• Publication Number:
  US 20140314322A1
• Time in Patent Office: 1,235 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06T 2200/04 involving 3D image data
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06T 7/75 involving models
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59

Abstract

System and methods for determining where a digital photograph was taken by estimating the camera pose with respect to a global scale three-dimensional database. Accurate location and orientation of the digital photograph is established through feature correspondence and geometry estimated from photograph collections.

Claims

1. A method for determining the location or the orientation of a digital photograph, comprising the steps of:

constructing a database of database images, points and feature descriptors;

receiving an input query image;

extracting features from the input query image to obtain image features;

matching image features to the database, wherein a match is a point in the input query image and a point in the database;

selecting one or more of a first subset of matches according to a randomized selection process, wherein each first subset of matches includes matches that co-occur more frequently in the database;

calculating one or more preliminary camera poses;

obtaining a second subset of matches;

determining the number of matches of the second subset of matches that agree with each of the one or more preliminary camera poses to obtain a number of agreeing matches for each of the one or more preliminary camera poses;

providing a best camera pose from the one or more preliminary camera poses, wherein the best camera pose is the preliminary camera pose with the largest number of agreeing matches;

deciding if the best camera pose exceeds a threshold of the number of agreeing matches; and

returning a final camera pose when the best camera pose exceeds the threshold of the number of agreeing matches.

2. The method for determining the location or the orientation of a digital photograph according to claim 1 wherein a match further includes a match distance that is a ratio of distances to the top two nearest neighbors of points or feature descriptors in the database, the match being kept if the match distance is smaller than a threshold.

3. The method for determining the location or the orientation of a digital photograph according to claim 1 wherein said constructing step further comprises the steps of:

creating a model of one or more scenes, wherein each scene includes one or more database images and one or more points;

generating the database of one or more feature descriptors for each point; and

indexing the one or more feature descriptors using a data structure.

4. The method for determining the location or the orientation of a digital photograph according to claim 3 wherein the model is a 3D model.

5. The method for determining the location or the orientation of a digital photograph according to claim 3 further comprising one or more of the steps of:

performing geo-registration on the model; and

defining an affinity score for each point.

6. The method for determining the location or the orientation of a digital photograph according to claim 5 wherein said performing step further comprises the steps of:

aligning each scene to a surface of Earth using geotags;

estimating a gravity vector by analyzing the orientations of one or more cameras in each scene; and

computing a similarity transformation between a location of the one or more cameras and the geotags.

7. The method for determining the location or the orientation of a digital photograph according to claim 6 wherein said estimating step further comprises one or more of the step of:

assessing vanishing points detected in each database image; and

analyzing the orientations of one or more cameras in each scene.

8. The method for determining the location or the orientation of a digital photograph according to claim 3 wherein said creating step further comprises the steps of:

extracting features from each database image;

matching features on pairs of database images; and

deriving information for each scene.

9. The method for determining the location or the orientation of a digital photograph according to claim 8 wherein the information for each scene includes one or more camera poses, one or more points, a visibility relation describing which points are visible in each database image, and one or more feature descriptors for each point.

10. The method for determining the location or the orientation of a digital photograph according to claim 3 wherein said generating step further comprises one or more selected from the steps of:

averaging all of the feature descriptors for each point;

clustering all of the feature descriptors for each point; and

using all of the feature descriptors for each point unchanged.

11. The method for determining the location or the orientation of a digital photograph according to claim 3 wherein the data structure is a k-dimensional tree.

12. The method for determining the location or the orientation of a digital photograph according to claim 1 wherein said selecting step further comprises the step of choosing three matches when a focal length of the input query image is known.

13. The method for determining the location or the orientation of a digital photograph according to claim 12 wherein said selecting step further comprises the step of choosing the subset of matches limited to a certain radial distance measured from an estimate of the camera'"'"'s position.

14. The method for determining the location or the orientation of a digital photograph according to claim 1 wherein said selecting step further comprises the step of choosing four matches when a focal length of the input query image is unknown.

15. The method for determining the location or the orientation of a digital photograph according to claim 14 wherein said selecting step further comprises the step of choosing the subset of matches limited to a certain radial distance measured from an estimate of the camera'"'"'s position.

16. The method for determining the location or the orientation of a digital photograph according to claim 1 wherein said deciding step further comprises the steps of:

concluding the one or more preliminary camera poses do not exceed the threshold of the number of agreeing matches;

designating zero or more primary seed matches and zero or more secondary seed matches;

producing a data structure built from the features descriptors in the input query image;

assigning a priority score to each point;

processing each point;

selecting the one or more first subset of matches to re-calculate the one or more preliminary camera poses; and

returning to said obtaining step.

17. The method for determining the location or the orientation of a digital photograph according to claim 16 wherein said assigning step further comprises the steps of:

summing, over each primary seed match, a number of database images that possess the point belonging to the primary seed match and the point in question;

allocating a large priority score when the points correspond to the zero or more primary seed matches and a small priority score when the points correspond to the zero or more secondary seed matches.

18. The method for determining the location or the orientation of a digital photograph according to claim 16 wherein said processing step further comprises the steps of:

reviewing each point in decreasing order of priority;

retaining one or more nearest neighboring feature descriptors in the input query image using the data structure built from the features descriptors in the input query image to obtain retained nearest neighboring feature descriptors;

keeping a match comprised of the point and the nearest neighbor point in the input query image when a distance computed from the feature descriptor of the point and the retained nearest neighboring feature descriptors is smaller than a certain threshold; and

updating the priority of each point based on the matches kept.