Method for recovering 3D scene structure and camera motion from points, lines and/or directly from the image intensities

• US 6,859,549 B1
• Filed: 09/01/2000
• Issued: 02/22/2005
• Est. Priority Date: 06/07/2000
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Oliensis, John
• Primary Examiner(s): Dastouri, Mehrdad
• Assistant Examiner(s): KIBLER, VIRGINIA M
• Application Number:
  US09/653,023
• Time in Patent Office: 1,635 Days
• Field of Search: 382/103, 382/154, 382/284, 382/289, 382/294, 382/296, 348/36, 348/42, 348/51
• US Class Current: 382/154
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/579 from motion
• CPC Class Codes: G06V 10/147 Details of sensors, e.g. sensor lenses fingerprint or palmprint sensors G06V40/13; vascular sensors G06V40/145; eye sensors G06V40/19
• CPC Class Codes: G06V 2201/12 Acquisition of 3D measurements of objects

Abstract

An algorithm for recovering structure and motion from points, lines and/or image intensities. The algorithm combines feature based reconstruction and direct methods. The present invention is directed to a method for recovering 3D scene structure and camera motion from image data obtained from a multi-image sequence, wherein a reference image of the sequence is taken by a camera at a reference perspective and one or more successive images of the sequence are taken at one or more successive different perspectives by translating and/or rotating the camera. The method comprising the steps of (a) determining image data shifts for each successive image with respect to the reference image; the shifts being derived from the camera translation and/or rotation from the reference perspective to the successive different perspectives; (b) constructing a shift data matrix that incorporates the image data shifts for each image; (c) calculating two rank-3 factor matrices from the shift data matrix using SVD, one rank-3 factor matrix corresponding the 3D structure and the other rank-3 factor matrix corresponding the camera motion; (d) recovering the 3D structure from the 3D structure matrix using SVD by solving a linear equation; and (e) recovering the camera motion from the camera motion matrix using the recovered 3D structure.

Claims

1. An image processing method for recovery of a scene structure from successive image data, the method comprising the steps of:

(a) computing rotational motion in the successive image data using a combination of first rotational flow vectors derived from a set of tracked points collected from the successive image data second rotational flow vectors derived from a sat of tracked lines collected from the successive image data, where the first rotational flow vectors are represented by ${\mathrm{\Psi <br><br>}}_x\equiv <br><br>\left[\begin{array}{c}\left\{r_x^{\left(1\right)}<br><br>\left(q\right)\right\}\\ \left\{r_y^{\left(1\right)}<br><br>\left(q\right)\right\}\end{array}\right],{\mathrm{\Psi <br><br>}}_y\equiv <br><br>\left[\begin{array}{c}\left\{r_x^{\left(2\right)}<br><br>\left(q\right)\right\}\\ \left\{r_y^{\left(2\right)}<br><br>\left(q\right)\right\}\end{array}\right],{\mathrm{\Psi <br><br>}}_z\equiv <br><br>\left[\begin{array}{c}\left\{r_x^{\left(3\right)}<br><br>\left(q\right)\right\}\\ \left\{r_y^{\left(3\right)}<br><br>\left(q\right)\right\}\end{array}\right]$

where r⁽¹⁾, r⁽²⁾, r⁽³⁾ are three point rotational flows with respect to an image position q of one of the tracked points and where the second rotational flow vectors derived from the set of tracked lines are represented by projections in two directions that take into account differences in noise of a measured line in different directions and where the second rotational flow vectors are represented by ${\mathrm{\Psi <br><br>}}_{\mathrm{Lx}}\equiv <br><br>\left[\begin{array}{c}\left\{P_U·<br><br>\left(\hat{x}\times <br><br>A\right)\right\}\\ \left\{P_L·<br><br>\left(\hat{x}\times <br><br>A\right)\right\}\end{array}\right],{\mathrm{\Psi <br><br>}}_{\mathrm{Ly}}\equiv <br><br>\left[\begin{array}{c}\left\{P_U·<br><br>\left(\hat{y}\times <br><br>A\right)\right\}\\ \left\{P_L·<br><br>\left(\hat{y}\times <br><br>A\right)\right\}\end{array}\right],{\mathrm{\Psi <br><br>}}_{\mathrm{Lz}}\equiv <br><br>\left[\begin{array}{c}\left\{P_U·<br><br>\left(\hat{z}\times <br><br>A\right)\right\}\\ \left\{P_L·<br><br>\left(\hat{z}\times <br><br>A\right)\right\}\end{array}\right]$

where A represents one of the tracked lines and P_U and P_L represent unit vectors projecting on the two directions;

(b) constructing a shift data matrix for the tracked lines and the tracked points that compensates for the rotational motion in the successive image data; and

(c) decomposing the shi data matrix into a translational motion matrix and a structure matrix and recovering the scene structure by solving for the structure matrix.

2. The image processing method of claim 1 wherein ith rotational motion is compensated through linear elimination of rotational dependence in the shift data matrix.

3. The image processing method of claim 1 wherein the shift data matrix is decomposed using singular value docomposition.

4. The image processing method of claim 1 wherein components of the shift data matrix ae weighted to account for greater accuracy of measurement of the components.

5. The image processing method of claim 1 wherein the method is iterated until it converges to a reconstruction of the scene structure.

6. An image processing method for recovery of a scene structure from successive image data, the method comprising the steps of:

(a) parameterizing a set of tracked lines collected from the successive image data;

(b) computing rotational motion in the successive image data using rotational flow vectors derived from the tracked lines where the rotational flow vectors am represented by projections in two directions that take into account differences in noise of a measured line in different directions and where the rotational flow vectors are represented by ${\mathrm{\Psi <br><br>}}_{\mathrm{Lx}}\equiv <br><br>\left[\begin{array}{c}\left\{P_U·<br><br>\left(\hat{x}\times <br><br>A\right)\right\}\\ \left\{P_L·<br><br>\left(\hat{x}\times <br><br>A\right)\right\}\end{array}\right],{\mathrm{\Psi <br><br>}}_{\mathrm{Ly}}\equiv <br><br>\left[\begin{array}{c}\left\{P_U·<br><br>\left(\hat{y}\times <br><br>A\right)\right\}\\ \left\{P_L·<br><br>\left(\hat{y}\times <br><br>A\right)\right\}\end{array}\right],{\mathrm{\Psi <br><br>}}_{\mathrm{Lz}}\equiv <br><br>\left[\begin{array}{c}\left\{P_U·<br><br>\left(\hat{z}\times <br><br>A\right)\right\}\\ \left\{P_L·<br><br>\left(\hat{z}\times <br><br>A\right)\right\}\end{array}\right]$

where A represents one of the tracked lines and P_U and P_L represent unit vectors projecting on the two directions;

(c) constructing a shift data matrix for the tracked lines that compensates for the rotational motion in the successive image data; and

(d) decomposing the shift data matrix into a translational motion matrix and a structure matrix and recovering the scene structure by solving for the structure matrix.

7. The image processing method of claim 6 wherein the rotational motion is compensated through linear elimination of rotational dependence in the shift data matrix.

8. The image method of claim 6 wherein the shift data matrix is decomposed using singular value decomposition.

9. The image method of claim 6 wherein components of the shift data matrix are weighted to account for greater accuracy of measurement of the components.

10. The image processing method of claim 6 wherein the method is iterated until it converges to a reconstruction of the scene structure.