Point Selection in Bundle Adjustment

• US 20130121558A1
• Filed: 11/25/2008
• Published: 05/16/2013
• Est. Priority Date: 08/15/2008
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Jin, Hailin, Ni, Kai
• Granted Patent: US 8,548,225 B2
• Time in Patent Office: Days
• US Class Current: 382/154
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20164 Salient point detection; Corner detection
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06T 7/73 using feature-based methods

Abstract

In an embodiment, a method comprises receiving a set of three dimensional (3D) points estimated from a plurality of images; selecting a subset of the 3D points that, as a group, provide at least a desired amount of constraint on each of a plurality of camera parameters; and performing non-linear optimization over the selected subset of 3D points to recover the plurality of camera parameters and the 3D points. The selected subset excludes one or more 3D points in the set.

Claims

1. A method comprising:

receiving a set of three dimensional (3D) points estimated from a plurality of images;

selecting a subset of the 3D points that, as a group, provide at least a desired amount of constraint on each of a plurality of camera parameters, wherein the subset excludes one or more 3D points in the set; and

performing non-linear optimization over the selected subset of 3D points to recover the plurality of camera parameters and the 3D points.

2. The method as recited in claim 1 wherein the selecting comprises:

determining an indication of contribution of each of the 3D points in the set to constraining each of the plurality of camera parameters;

selecting one or more 3D points for the subset based on overall contributions of each 3D point to each of the plurality of camera parameters;

updating the overall contributions of the remaining points; and

selecting one or more additional 3D points for the subset based on the updated overall contributions.

3. The method as recited in claim 2 wherein determining the indication of contribution comprises forming a Jacobian matrix that relates the set of 3D points to the plurality of camera parameters.

4. The method as recited in claim 3 wherein the indication of contribution of a given 3D point in the set to a given camera parameter of the plurality of camera parameters is derived from an entry in the Jacobian matrix that relates the given point and the given camera parameter.

5. The method as recited in claim 4 wherein the indication is the absolute value of the entry.

6. The method as recited in claim 2 wherein determining the indication of contribution comprises determining a contribution of a given 3D point of the set to each of the plurality of camera parameters and summing the contributions to generate the overall contribution of the given 3D point.

7. The method as recited in claim 6 wherein updating the overall contributions comprises eliminating contributions from the sum that correspond to one or more camera parameters of the plurality of camera parameters that are sufficiently constrained according to the selected points in the subset.

8. The method as recited in claim 7 further comprising:

determining that each of the plurality of camera parameters are sufficiently constrained according to a first threshold;

subsequent to determining that each of the plurality of camera parameters are sufficiently constrained according to a first threshold, determining that not enough 3D points have been selected to perform the non-linear optimization;

establishing a second threshold different from the first threshold; and

repeating the selecting to sufficiently constrain each of the plurality of camera parameters to the second threshold.

9. A computer accessible storage medium storing a plurality of instructions which, when executed:

receive a set of three dimensional (3D) points estimated from a plurality of images;

select a subset of the 3D points that, as a group, provide at least a desired amount of constraint on each of a plurality of camera parameters, wherein the subset excludes one or more 3D points in the set; and

perform non-linear optimization over the selected subset of 3D points to recover the plurality of camera parameters and the 3D points.

10. The computer accessible storage medium as recited in claim 9 wherein the plurality of instructions which, when executed, select the subset comprise instructions which, when executed:

determine an indication of contribution of each of the 3D points in the set to constraining each of the plurality of camera parameters;

select one or more 3D points for the subset based on overall contributions of each 3D point to each of the plurality of camera parameters;

update the overall contributions of the remaining points; and

select one or more additional 3D points for the subset based on the updated overall contributions.

11. The computer accessible storage medium as recited in claim 10 wherein the instructions which, when executed, determine the indication of contribution comprise instructions which, when executed, form a Jacobian matrix that relates the set of 3D points to the plurality of camera parameters.

12. The computer accessible storage medium as recited in claim 11 wherein the indication of contribution of a given 3D point in the set to a given camera parameter of the plurality of camera parameters is derived from an entry in the Jacobian matrix that relates the given point and the given camera parameter.

13. The computer accessible storage medium as recited in claim 12 wherein the indication is the absolute value of the entry.

14. The computer accessible storage medium as recited in claim 10 wherein the instructions which, when executed, determine the indication of contribution comprise instructions which, when executed, determine a contribution of a given 3D point in the set to each of the plurality of camera parameters and sum the contributions to generate the overall contribution of the given 3D point.

15. The computer accessible storage medium as recited in claim 14 wherein the instructions which, when executed, update the overall contributions comprise instructions which, when executed, eliminate contributions from the sum that correspond to one or more camera parameters of the plurality of camera parameters that are sufficiently constrained according to the selected points in the subset.

16. The computer accessible storage medium as recited in claim 15 wherein the plurality of instructions, when executed:

determine that each of the plurality of camera parameters are sufficiently constrained according to a first threshold;

subsequent to determining that each of the plurality of camera parameters are sufficiently constrained according to a first threshold, determine that not enough 3D points have been selected to perform the non-linear optimization;

establish a second threshold different from the first threshold; and

repeat the selecting to sufficiently constrain each of the plurality of camera parameters to the second threshold.

17. A computer system comprising:

a processor configured to execute instructions; and

a memory coupled to the processor, wherein the memory is configured to store a source video sequence comprising a plurality of images and a bundle adjustment module comprising instructions executable by the processor, wherein the instructions, when executed;

receive a set of three dimensional (3D) points estimated from the plurality of images by one or more other modules based on feature correspondences between two or more images of the plurality of images;

select a subset of the 3D points that, as a group, provide at least a desired amount of constraint on each of a plurality of camera parameters, wherein the subset excludes one or more 3D points in the set; and

perform non-linear optimization over the selected subset of 3D points to recover the plurality of camera parameters and the 3D points.

18. The computer system as recited in claim 17 wherein the instructions of the bundle adjustment module, when executed:

determine an indication of contribution of each of the 3D points in the set to constraining each of the plurality of camera parameters;

select one or more 3D points for the subset based on overall contributions of each 3D point to each of the plurality of camera parameters;

update the overall contributions of the remaining points; and

select one or more additional 3D points for the subset based on the updated overall contributions.

19. The computer system as recited in claim 18 wherein the instructions which, when executed, determine the indication of contribution comprise instructions which, when executed, determine a contribution of a given 3D point of the set to each of the plurality of camera parameters and sum the contributions to generate the overall contribution of the given 3D point.

20. The computer system as recited in claim 19 wherein the instructions which, when executed, update the overall contributions comprise instructions which, when executed, eliminate contributions from the sum that correspond to one or more camera parameters of the plurality of camera parameters that are sufficiently constrained according to the selected points in the subset.

21. The computer system as recited in claim 21 wherein the instructions of the bundle adjustment module, when executed:

determine that each of the plurality of camera parameters are sufficiently constrained according to a first threshold;

subsequent to determining that each of the plurality of camera parameters are sufficiently constrained according to a first threshold, determine that not enough 3D points have been selected to perform the non-linear optimization;

establish a second threshold different from the first threshold; and

repeat the selecting to sufficiently constrain each of the plurality of camera parameters to the second threshold.

22. A computer-implemented method comprising:

executing instructions on a specific apparatus so that binary digital electronic signals representing a subset of a set of three dimensional (3D) points estimated from a plurality of images are selected, wherein the subset, as a group, provide at least a desired amount of constraint on each of a plurality of camera parameters, wherein the subset excludes one or more 3D points in the set;

executing instructions on a specific apparatus so that binary digital electronic signals representing the selected subset have non-linear optimization performed over the selected subset to recover the plurality of camera parameters and the 3D points; and

storing the plurality of camera parameters and the 3D points in a memory location of the specific apparatus.