Feature reduction based on local densities for bundle adjustment of images

• US 9,465,976 B1
• Filed: 09/14/2015
• Issued: 10/11/2016
• 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:
  US14/852,831
• Time in Patent Office: 393 Days
• US Class Current: 1/1
• 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 computer-implemented method for determining three-dimensional positions of features, comprising:

receiving, by one or more computing devices, data associated with a plurality of images, wherein each of the plurality of images covers at least a portion of a geographic area;

detecting, by the one or more computing devices, features contained within the plurality of images;

determining, by the one or more computing devices, a plurality of matched features based on a comparison of the detected features contained within the plurality of images;

selecting, by the one or more computing devices, a subset of the plurality of matched features, wherein each respective matched feature of the subset is selected based at least in part on a quantity of other matched features in proximity to the respective matched feature; and

determining, by the one or more computing device, three-dimensional positions associated with one or more of the matched features included within the selected subset.

2. The computer-implemented method of claim 1, wherein selecting the subset comprises filtering, by the one or more computing devices, 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 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 computer-implemented method of claim 1, wherein selecting the subset comprises:

adjusting, by the one or more computing devices, a sensitivity level for detecting the features contained within the plurality of images 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, by the one or more computing devices, one or more of the plurality of matched features from each of the one or more subareas of the geographic area such that a count of the plurality of matched features in 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 computer-implemented method of claim 3, wherein filtering the one or more of the plurality of matched features comprises:

determining, by the one or more computing devices, 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 determination is based at least in part upon providing a substantially equal distribution of the subset over the plurality of subareas; and

removing, by the one or more computing devices, the determined number of the matched features from each of the subareas in which the count exceeds the threshold.

5. The computer-implemented method of claim 1, wherein selecting the subset comprises:

determining, by the one or more computing devices, a priority for respective ones of the plurality of matched features based at least in part 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, by the one or more computing devices, the subset based at least in part upon the determined priority.

6. The computer-implemented method of claim 5, wherein determining the priority comprises determining, by the one or more computing devices, the priority of a particular matched feature of the plurality of matched features based at least in part upon a number of the images in which the particular matched feature is present.

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

grouping, by the one or more computing devices, the plurality of matched features according to their respective locations in the geographic area; and

determining, by the one or more computing devices, the priority of a particular matched feature of the plurality of matched features based at least in part 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 computer-implemented method of claim 5, wherein determining the priority comprises determining, by the one or more computing devices, the priority of a particular matched feature based at least in part upon a detection confidence associated with the particular matched feature.

9. The computer-implemented method of claim 8, wherein the detection confidence is determined based upon at least one of a detection sensitivity level of a feature detector at which the particular matched feature is found to be present or 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.

10. The computer-implemented method of claim 5, further comprising:

projecting, by the one or more computing devices, the plurality of matched features onto a common plane, wherein the common plane encompasses the geographic area; and

partitioning, by the one or more computing devices, the common plane into a plurality of partitions.

11. The computer-implemented method of claim 10, wherein selecting the subset comprises selecting one or more of the plurality of matched features from respective ones of the partitions based upon the determined priority.

12. A system for determining three-dimensional positions of features, the system comprising:

one or more computing devices including one or more processors and associated memory, the memory storing instructions that, when implemented by the one or more processors, configure the one or more computing devices to;

receive data associated with a plurality of images, wherein each of the plurality of images covers at least a portion of a geographic area;

detect features contained within the plurality of images;

determine a plurality of matched features based on a comparison of the detected features contained within the plurality of images;

select a subset of the plurality of matched features, wherein each respective matched feature of the subset is selected depending on a quantity of other matched features in proximity to the respective matched feature; and

determine three-dimensional positions associated with one or more of the matched features included within the selected subset.

13. The system of claim 12, wherein the one or more computing devices are configured to select the subset of the plurality of matched features by 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 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.

14. The system of claim 12, wherein the one or more computing devices are further configured to determine a priority for respective ones of the plurality of matched features, wherein the subset is selected based at least in part on the determined priority.

15. The system of claim 14, wherein the one or more computing devices are further configured to:

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

partition the common plan into 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.

16. The system of claim 14, wherein the one or more computing devices are further configured to determine the priority of a particular matched feature of the plurality of matched features based at least in part upon at least one of a number of the images in which the particular matched feature is present, a number of other matched features of the plurality of matched features that are in a common group as the particular matched feature or a detection confidence associated with the particular matched feature.

17. The system of claim 15, wherein the detection confidence is determined based upon at least one of a detection sensitivity level of a feature detector at which the particular matched feature is found to be present or 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.

18. A tangible, non-transitory computer readable medium storing computer-executable instructions that, when executed by one or more processors, cause the one or more processors to perform operations, comprising:

receiving data associated with a plurality of images, wherein each of the plurality of images covers at least a portion of a geographic area;

detecting features contained within the plurality of images;

determining a plurality of matched features based on a comparison of the detected features contained within the plurality of images;

selecting a subset of the plurality of matched features, wherein each respective matched feature of the subset is selected based at least in part on a quantity of other matched features in proximity to the respective matched feature; and

determining three-dimensional positions associated with one or more of the matched features included within the selected subset.

19. The tangible, non-transitory computer readable medium of claim 18, further comprising determining a priority for respective ones of the plurality of matched features, wherein the subset is selected based at least in part on the determined priority.

20. The tangible, non-transitory computer readable medium of claim 19, further comprising:

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

partitioning the common plane into a plurality of partitions; and

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