Incremental motion estimation through local bundle adjustment

• US 20030044048A1
• Filed: 06/18/2001
• Published: 03/06/2003
• Est. Priority Date: 06/18/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Zhengyou, Shan, Ying
• Granted Patent: US 6,996,254 B2
• Time in Patent Office: Days
• US Class Current: 382/107
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 7/251 involving models
• CPC Class Codes: G06T 7/80 Analysis of captured images to determine intrinsic or extrinsic camera parameters, i.e. camera calibration

Abstract

An incremental motion estimation system and process for estimating the camera pose parameters associated with each image of a long image sequence. Unlike previous approaches, which rely on point matches across three or more views, the present system and process also includes those points shared only by two views. The problem is formulated as a series of localized bundle adjustments in such a way that the estimated camera motions in the whole sequence are consistent with each other. The result of the inclusion of two-view matching points and the localized bundle adjustment approach is more accurate estimates of the camera pose parameters for each image in the sequence than previous incremental techniques, and providing an accuracy approaching that of global bundle adjustment techniques except with processing times about 100 to 700 times faster than the global approaches.

Claims

1. A computer-implemented incremental motion estimation process for estimating the camera pose parameters associated with each of a sequence of images of a scene, comprising using a computer to perform the following process actions:

establishing a set of triple matching points that depict the same point in the scene across the three successive images of each triplet of images that can be formed from the sequence;

establishing a set of dual matching points that depict the same point in the scene across the latter two images of each triplet of images that can be formed from the sequence;

defining the camera coordinate system associated with the first image in the sequence as coinciding with a 3D world coordinate system for the scene depicted in the sequence of images;

estimating the camera pose parameters associated with the second image in the sequence; and

for each successive triplet of images formable from the sequence starting with the first three images, estimating the camera pose parameters associated with the third image of each triplet from previously-ascertained camera pose parameters associated with the first two images in the triplet, as well as the dual and triple matching points of the triplet.

2. The process of claim 1 wherein the process action for estimating the camera pose parameters associated with the third image of each triplet, comprises the action of computing the camera pose parameters associated with the third image in the triplet under consideration which will result in a minimum value for the sum of the squared differences between the image coordinates of each identified triple match point and its corresponding predicted image coordinates in each of the three images in the triplet, added to the sum of the squared differences between the image coordinates of each identified dual match point and its corresponding predicted image coordinates in each of the latter two images in the triplet.

3. The process of claim 2, wherein the predicted image coordinates of an either triple or dual matching point are characterized as a function of the 3D world coordinates associated with the matching point under consideration and the camera pose parameters of the image containing this matching point, and wherein the process action of estimating the camera pose parameters associated with the third image of each triplet further comprises the action of computing the 3D world coordinates associated with each triple and dual match point in the triplet, as well as the camera pose parameters associated with the third image in the triplet under consideration, which will result in a minimum value for the sum of the squared differences between the image coordinates of each identified triple match point and its corresponding predicted image coordinates in each of the three images in the triplet, added to the sum of the squared differences between the image coordinates of each identified dual match point and its corresponding predicted image coordinates in each of the latter two images in the triplet.

4. The process of claim 2, wherein the predicted image coordinates of an either a triple or dual matching point are characterized in terms of functions that define the relationship between them other than their common 3D world coordinates.

5. The process of claim 4, wherein the functions that define the relationship between a triple matching point comprise:

an epipolar relationship between pairs of the triple matching points in consecutive images of the triplet under consideration, said epipolar constraint requiring that the locations of each pair of triple matching points be related by the fundamental matrix associated with the images containing the points; and

a three-view relationship that defines the location of the triple matching point in the third image of the triplet under consideration in terms of the image coordinates of the triple matching points in the first two images of the triplet and the camera projection matrices associated with the triplet of images which include the camera pose parameters.

6. The process of claim 4, wherein the functions that define the relationship between a dual matching point comprise an epipolar relationship between dual matching points, said epipolar constraint requiring that the locations of each dual matching points be related by the fundamental matrix associated with the images containing the points.

7. The process of claim 1, wherein the process action of estimating the camera pose parameters associated with the second image in the sequence, comprises the action of using a two-view structure-from-motion technique.

8. The process of claim 1, wherein the process action of estimating the camera pose parameters associated with the second image in the sequence, comprises the action of applying a global bundle alignment technique to the first three images of the sequence of images.

9. A local bundling adjustment system for estimating the camera projection matrix associated with each of a sequence of images of a scene, comprising:

a general purpose computing device;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

input the sequence of images,

identify points in each image in the sequence of images;

determine which of the identified points depict the same point of the scene so as to be matching points,

define the camera coordinate system associated with the first image in the sequence as coinciding with a 3D world coordinate system for the scene depicted in the sequence of images;

compute the camera projection matrix associated with the second image in the sequence, and

for each successive triplet of images that can be formed from the sequence starting with the first three images, estimate the camera projection matrix of the third image of each triplet from previously-ascertained camera projection matrices associated with the first two images in the triplet as well as points determined to be matching points across all three images of the of the triplet and points determined to be matching points across at least one pair of images in the triplet.

10. The system of claim 9, wherein the program module for determining which of the identified points depict the same point of the scene so as to be matching points comprises sub-modules for:

establishing a set of triple matching points that depict the same point in the scene across the three successive images of each triplet of images that can be formed from the sequence; and

establishing a set of dual matching points that depict the same point in the scene across the latter two images of each triplet of images that can be formed from the sequence.

11. The system of claim 10, wherein the program module for estimating the camera projection matrix associated with the third image of each triplet comprises a sub-module for computing the camera projection matrix associated with the third image in the triplet under consideration which will result in a minimum value for the sum of the squared differences between the image coordinates of each identified triple match point and its corresponding predicted image coordinates in each of the three images in the triplet, added to the sum of the squared differences between the image coordinates of each identified dual match point and its corresponding predicted image coordinates in each of the latter two images in the triplet.

12. The system of claim 9, wherein the program module for determining which of the identified points depict the same point of the scene so as to be matching points comprises sub-modules for:

establishing a set of triple matching points that depict the same point in the scene across the three successive images of each triplet of images that can be formed from the sequence;

establishing a first set of dual matching points that depict the same point in the scene across the latter two images of each triplet of images that can be formed from the sequence; and

establishing a second set of dual matching points that depict the same point in the scene in the first and third images of each triplet of images that can be formed from the sequence.

13. The system of claim 12, wherein the program module for estimating the camera projection matrix associated with the third image of each triplet comprises a sub-module for computing the camera projection matrix associated with the third image in the triplet under consideration which will result in a minimum value for the sum of the squared differences between the image coordinates of each identified triple match point and its corresponding predicted image coordinates in each of the three images in the triplet, added to both the sum of the squared differences between the image coordinates of each dual match point in the first set of dual match points and its corresponding predicted image coordinates in each of the latter two images in the triplet and the sum of the squared differences between the image coordinates of each dual match point in the second set of dual match points and its corresponding predicted image coordinates in the first and third image in the triplet.

14. A computer-readable medium having computer-executable instructions for estimating the camera pose parameters associated with each of a sequence of images of a scene, said computer-executable instructions comprising:

identifying points in each image in the sequence of images;

determining which of the identified points depict the same point of the scene so as to be matching points;

defining the camera coordinate system associated with the first image in the sequence as coinciding with a 3D world coordinate system for the scene depicted in the sequence of images;

computing the camera pose parameters associated with the second image in the sequence, and

for each successive triplet of images that can be formed from the sequence starting with the first three images, estimate the camera pose parameters of the third image of each triplet from previously-ascertained camera pose parameters associated with the first two images in the triplet as well as points determined to be matching points across all three images of the of the triplet and points determined to be matching points across at least one pair of images in the triplet.

15. A local bundle adjustment process for estimating the camera pose parameters associated with each of a sequence of images of a scene, comprising the following process actions:

identifying points in each image in the sequence of images;

determining which of the identified points depict the same point of the scene so as to be matching points,

defining the camera coordinate system associated with the first image in the sequence as coinciding with a 3D world coordinate system for the scene depicted in the sequence of images;

computing the camera pose parameters associated with the second image in the sequence, and

for each successive triplet of images that can be formed from the sequence starting with the first three images, estimate the camera pose parameters of the third image of each triplet from previously-ascertained camera pose parameters associated with the first two images in the triplet as well as points determined to be matching points across all three images of the of the triplet and points determined to be matching points across at least one pair of images in the triplet.

16. The process of claim 15, wherein the instruction for determining which of the identified points depict the same point of the scene so as to be matching points comprises sub-modules for:

establishing a set of triple matching points {(p_0,j, p_1,j, p_2,j)| j=1, . . . , M} that depict the same point in the scene across the three successive images of each triplet of images that can be formed from the sequence, where j refers to a particular instance of a triple matching point and M refers to the total number of triple matching points in the set; and

establishing a set of dual matching points {(q_1,k, q_2,k)| k=1, . . . , N} that depict the same point in the scene across the latter two images of each triplet of images that can be formed from the sequence, where k refers to a particular instance of a dual matching point and N refers to the total number of dual matching points in the set.

17. The process of claim 16, wherein the process action of estimating the camera pose parameters associated with the third image of each triplet comprises the action of computing the 3D world coordinates associated with each triple and dual match point in the triplet, as well as the camera pose parameters associated with the third image in the triplet under consideration, which will result in a minimum value according to the equation,

18. The process of claim 17, wherein the predicted image coordinates φ

(M_i, P_j) of a triple matching point p_i,j are characterized by the equation {tilde over (p)}_i,j=P_i{tilde over (P)}_j/s, where {tilde over (p)}_i,j=[p_i,j^T,1]^T, P_i=A_iM_i, A_i is the camera internal parameters matrix, {tilde over (P)}_j=[[X_j,Y_j,Z_j],1]^T, and s is a non-zero scale factor, and wherein the predicted image coordinates φ

(M_i, Q_k) of a dual matching point q_i,k are characterized by the equation {tilde over (q)}_i,k=P_i{tilde over (Q)}_k/s, where {tilde over (q)}_i,k=[q_i,k^T,1]^T, and {tilde over (Q)}_k=[[X_k,Y_k,Z_k],1]^T.

19. The process of claim 15, wherein the instruction for determining 25 which of the identified points depict the same point of the scene so as to be matching points comprises sub-modules for:

establishing a set of triple matching points {(p_0,j, p_i,j, p_2,j)| j=1, . . . , M} that depict the same point in the scene across the three successive images of each triplet of images that can be formed from the sequence, where j refers to a particular instance of a triple matching point and M refers to the total number of triple matching points in the set;

establishing a first set of dual matching points {(q_1,k, q_2,k)| k=1, . . . , N} that depict the same point in the scene across the latter two images of each triplet of images that can be formed from the sequence, where k refers to a particular instance of a dual matching point in the first set and N refers to the total number of dual matching points in the first set; and

establishing a second set of dual matching points {(I_0,l, I_2,l)| l=1, . . . , O} that depict the same point in the scene in the first and third images of each triplet of images that can be formed from the sequence, where/refers to a particular instance of a dual matching point in the second set and O refers to the total number of dual matching points in the second set.

20. The process of claim 19, wherein the process action of estimating the camera pose parameters associated with the third image of each triplet comprises the action of computing the 3D world coordinates associated with each triple and dual match point in the triplet, as well as the camera pose parameters associated with the third image in the triplet under consideration, which will result in a minimum value according to the equation,

21. The process of claim 20, wherein the predicted image coordinates φ

(M_i, P_j) of a triple matching point p_i,j are characterized by the equation {tilde over (p)}_i,j=P_i{tilde over (P)}_j/s, where {tilde over (p)}_i,j=[p_i,j^T1]^T, P_i=A_iM_i, A_i is the camera internal parameters matrix, {tilde over (P)}_j=[[X_j, Y_j, Z_j],1]^T, and s is a non-zero scale factor, and wherein the predicted image coordinates φ

(M_i, Q_k) of a dual matching point q_i,k are characterized by the equation {tilde over (q)}_i,k=P_i{tilde over (Q)}_k/s where {tilde over (q)}_i,k=[q_i,k^T,1]^T, and {tilde over (Q)}_k=[[X_k,Y_k,Z_k],1]^T, and wherein the predicted image coordinates φ

(M_i, L_l) of a dual matching point I_i,l are characterized by the equation Ĩ

_i,l=P_i{tilde over (L)}_l/s, where Ĩ

_i,l=[I_i,l,1]^T, and {tilde over (L)}_l=[[X_l,Y_l,Z_l],1]^T.