Adjusting camera parameters associated with a plurality of images

• US 9,036,044 B1
• Filed: 07/22/2013
• Issued: 05/19/2015
• Est. Priority Date: 07/22/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bae, Soohyun, Rucklidge, William James
• Primary Examiner(s): Vu, Ngoc-Yen
• Application Number:
  US13/947,159
• Time in Patent Office: 666 Days
• Field of Search: 348/207.99, 348/222.1
• US Class Current: 348/222.1
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/20072 Graph-based image processing
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06T 7/73 using feature-based methods

Abstract

Systems and methods for adjusting a camera parameter associated with a plurality of two-dimensional images are provided. Matched features can be selected as constraints for bundle adjustment using a graph model constructed based on the matched features. The graph model can have a plurality of nodes including a source node, a sink node, a point node for every matched feature, and a pose pair node associated with each pose pair viewing a matched feature. The graph model can include a plurality of edges interconnecting the plurality of nodes in the graph model. Each of these edges can be assigned a capacity and a cost based on various parameters. A flow can be computed through each of the edges of the graph model using, for instance, a minimum-cost maximum-flow algorithm. Matched features can be selected for bundle adjustment based on the flows of the edges in the graph model.

Claims

1. A computer-implemented method for adjusting one or more camera parameters associated with a plurality of images, the method comprising:

identifying, by one or more computing devices, a matched feature in the plurality of images, the matched feature associated with at least one pose pair, the at least one pose pair comprising two images of the plurality of images that depict the matched feature;

constructing, by the one or more computing devices, a graph model based at least in part on the matched feature, the graph model comprising a plurality of nodes including a source node and a sink node, the graph model comprising a plurality of edges;

computing, by the one or more computing devices, a flow through the plurality of edges in the graph model; and

selecting, by the one or more computing devices, the matched feature as a constraint for adjusting the camera parameter based at least in part on the flow computed through the plurality of edges in the graph model;

wherein selecting the matched feature as a constraint for adjusting the camera parameter based on the flow computed through the plurality of edges in the graph model comprises;

comparing, by the one or more computing devices, the flow of a source edge in the graph model to a threshold; and

selecting, by the one or more computing devices, the matched feature as a constraint when the flow exceeds the threshold.

2. The computer-implemented method of claim 1, wherein the graph model is constructed based at least in part on the number of pose pairs viewing the matched feature and the number of images viewing the matched feature.

3. The computer-implemented method of claim 1, wherein the flow is computed through the plurality of edges in the graph model using a minimum-cost maximum-flow algorithm.

4. The computer-implemented method of claim 1, wherein the graph model comprises:

a point node representing the matched feature; and

a pose pair node representing the at least one pose pair.

5. The computer-implemented method of claim 4, wherein the plurality of edges comprises:

a source edge between the source node and the point node;

a point edge between the point node and the pose pair node; and

a sink edge between the pose pair node and the sink node.

6. The computer-implemented method of claim 5, wherein the source edge has a capacity determined based on the number of pose pairs that view the matched feature associated with the point node.

7. The compute implemented method of claim 5, wherein the point edge has a capacity of 1.

8. The computer-implemented method of claim 5, wherein the sink edge has a capacity determined based at least in part on a maximum number of matched features viewed by the pose pair to be selected as a constraint for adjusting the camera parameter.

9. The computer-implemented method of claim 5, wherein the source edge has a cost determined based at least in part on the number of images viewing the matched feature associated with the point node.

10. The computer-implemented method of claim 5, wherein the point edge has a cost determined based at least in part on the number of cameras associated with the pose pair.

11. The computer-implemented method of claim 5, wherein the sink edge has a cost of zero.

12. The computer-implemented method of claim 1, Wherein the method comprises adjusting, by the one or more computing devices, the camera parameter based on the constraint.

13. The computer-implemented method of claim 1, wherein adjusting, by the one or more computing devices, the camera parameter comprises a non-linear optimization.

14. The computer-implemented method of claim 1, wherein the camera parameter comprises a pose of at least one of the plurality of images.

15. A computing system for adjusting a camera parameter associated with a plurality of images, the computing system comprising:

one or more processors;

one or more computer-readable media;

a feature matching module implemented by the one or more processors, the feature detection module configured to identify a matched feature in the plurality of images, the matched feature associated with at least one pose pair, the at least one pose pair comprising two images of the plurality of images that depict the matched feature;

a graph construction module implemented by the one or more processors, the graph construction module configured to construct a graph model based at least in part on the number of pose pairs viewing the matched feature and the number of images viewing the matched feature;

a graph analysis module implemented by the one or more processors, the graph analysis module configured to compute a flow through the plurality of edges in the graph model using a minimum-cost maximum-flow algorithm; and

a feature selection module implemented by the one or more processors, the feature selection module configured to select the matched feature as a constraint based at least in part on the flow computed through the plurality of edges in the graph model;

wherein the feature selection module is configured to compare the flow of a source edge in the graph model to a threshold; and

to select the matched feature as a constraint when the flow exceeds the threshold.

16. The computing system of claim 15, wherein the system further comprises a parameter optimization module implemented by the one or more processors, the parameter optimization module configured to adjust the camera parameter based on the constraint using non-linear optimization.

17. One or more tangible, non-transitory computer-readable media, the one or more tangible, non-transitory computer-readable media storing instructions that when executed by one or more processors cause the one or more processors to perform operations, the operations comprising;

identifying a matched feature in the plurality of images, the matched feature associated with at least one pose pair, the at least one pose pair comprising two images of the plurality of images that depict the matched feature;

constructing a graph model based at least in part on the matched feature, the graph model comprising a plurality of nodes including a source node and a sink node, the graph model comprising a plurality of edges;

computing a flow through the plurality of edges in the graph model; and

selecting the matched feature as a constraint for adjusting the camera parameter based at least in part on the flow computed through the plurality of edges in the graph model,

wherein the graph model comprises a point node representing the matched feature and a pose pair node representing at least one pose pair, wherein the plurality of edges comprises a source edge between the source node and the point node, a point edge between the point node and the pose pair node, and a sink edge between the pose pair node and the sink node;

wherein the source edge has a capacity determined based on the number of pose pairs that view the matched feature associated with the point node.