Feature reduction based on local densities for bundle adjustment of images

• US 8,965,107 B1
• Filed: 05/18/2012
• Issued: 02/24/2015
• Est. Priority Date: 05/18/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Schpok, Joshua Sam, Lin, Michael Hongmai, Reinhardt, Tilman
• Primary Examiner(s): Johns, Andrew W
• Application Number:
  US13/475,710
• Time in Patent Office: 1,012 Days
• Field of Search: 382/100, 382/103, 382/154, 382/284, 382/291, 345/419, 345/427, 345/629, 345/634
• US Class Current: 382/154
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 5/10 using non-spatial domain filtering
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

Methods, systems, and computer program products are provided for determining camera parameters and three dimensional locations of features from a plurality of images of a geographic area. These include, detecting features in the plurality of images where each of the images cover at least a portion of the geographic area, comparing the detected features between respective ones of the images to determine a plurality of matched features, selecting a subset of the plurality of matched features, and determining the camera parameters and the three dimensional positions of one or more of the detected features using the selected subset. The respective matched features are selected depending on a quantity of other matched features in proximity to the respective matched features.

Claims

1. A method of determining camera parameters and three dimensional locations of features from a plurality of images of a geographic area, comprising:

detecting features in the plurality of images, wherein each of the images cover at least a portion of the geographic area;

comparing the detected features between respective ones of the images to determine a plurality of matched features;

selecting a subset of the plurality of matched features, respective matched features selected depending on a quantity of other matched features in proximity to the respective matched features; and

determining the camera parameters and the three dimensional positions of one or more of the matched features using the selected subset.

2. The method of claim 1, wherein the selecting a subset comprises:

filtering one or more of the plurality of matched features from each of one or more subareas of the geographic area such that a count of the plurality of matched features in said each of the one or more subareas exceeds a threshold, wherein the subset includes ones of the plurality of matched features remaining after the filtering.

3. The method of claim 1, wherein the selecting a subset comprises:

adjusting a sensitivity level of the detecting in order to increase the plurality of matched features present in one or more subareas of a plurality of subareas in the geographic area; and

filtering one or more of the plurality of matched features from each of one or more subareas of the geographic area such that a count of the plurality of matched features in said each of the one or more subareas exceeds a threshold, wherein the subset includes ones of the plurality of matched features remaining after the filtering.

4. The method of claim 3, wherein the filtering includes:

determining, for each of the plurality of subareas in which the count exceeds the threshold, a number of the matched features in the subarea to be removed, wherein the determining is based upon a substantially equal distribution of the subset over the plurality of subareas; and

removing the determined number of the matched features from each of the subareas in which the count exceeds the threshold.

5. The method of claim 1, wherein the selecting a subset comprises:

determining a priority for respective ones of the plurality of matched features based at least upon a count of others of the plurality of matched features in proximity to the respective ones of the plurality of matched features; and

selecting the subset based at least upon the determined priority.

6. The method of claim 5, wherein the determining a priority comprises:

determining the priority of a particular matched feature of the plurality of matched features at least in part based upon a number of the images in which the particular matched feature is present.

7. The method of claim 5, wherein determining the priority comprises:

grouping the plurality of matched features according to their respective locations in the geographic area; and

determining the priority of a particular matched feature of the plurality of matched features at least in part based upon a number of other matched features of the plurality of matched features that are in the same group as the particular matched feature.

8. The method of claim 5, wherein determining the priority further comprises:

determining the priority of a particular matched feature at least in part based upon a detection confidence associated with the particular matched feature.

9. The method of claim 8, wherein the detection confidence is determined based upon a detection sensitivity level of a feature detector at which the particular matched feature is found to be present.

10. The method of claim 8, wherein the detection confidence is determined based upon a ratio of a number of images in which the particular matched feature is detected to a number of images which overlap an area including the particular matched feature.

11. The method of claim 5, further comprising:

projecting the plurality of matched features onto a common plane, wherein the common plane encompasses the geographic area; and

partitioning the common plane to a plurality of partitions.

12. The method of claim 11, wherein the selecting a subset comprises:

selecting one or more of the plurality of matched features from respective ones of the partitions based upon the determined priority.

13. The method of claim 12, wherein the selecting one or more of the plurality of matched features from respective ones of the partitions is further based upon substantially equally distributing the selected matched features among the partitions.

14. The method of claim 13, wherein the selected matched features are distributed substantially uniformly in locations in the geographic area having overlapping ones of the images.

15. The method of claim 11, wherein the common plane is partitioned to a plurality of equal sized tiles.

16. The method of claim 1, wherein the plurality of images are oblique images captured from one or more airborne cameras.

17. A system for determining camera parameters and three dimensional locations of features from a plurality of images of an area, comprising:

at least one processor;

a feature detector configured to be executed on the at least one processor and further configured to detect features in the plurality of images, wherein each of the images cover at least a portion of the area;

a feature matcher configured to be executed on the at least one processor and further configured to compare the detected features between respective images to determine a plurality of matched features;

a feature selector configured to be executed on the at least one processor and further configured to select a subset of the plurality of matched features, respective matched features selected depending on a quantity of other matched features in proximity to the respective matched features; and

a bundle adjuster configured to be executed on the at least one processor and further configured to determine camera parameters and three dimensional positions of one or more of the matched features for the images using the selected subset.

18. The system of claim 17, further comprising:

a feature prioritizer configured to be executed on the at least one processor and further configured to determine a priority for respective ones of the plurality of matched features.

19. The system of claim 17, wherein the feature selector is further configured to:

project the plurality of matched features onto a common plane, wherein the common plane encompasses the geographic area;

partition the common plane to a plurality of partitions; and

select one or more of the projected plurality of matched features from respective ones of the partitions based upon the determined priority.

20. A non-transitory computer readable storage medium having instructions stored thereon that, when executed by a processor, cause the processor to perform a method of determining camera parameters and three dimensional locations of features from a plurality of images of an area, wherein the method comprises:

detecting features in the plurality of images, wherein each of the images cover at least a portion of the geographic area;

comparing the detected features between respective ones of the images to determine a plurality of matched features;

selecting a subset of the plurality of matched features, respective matched features selected depending on a quantity of other matched features in proximity to the respective matched features; and

determining the camera parameters and the three dimensional positions of one or more of the matched features using the selected subset.