Estimation of 3-dimensional shape from image sequence

• US 6,628,819 B1
• Filed: 10/07/1999
• Issued: 09/30/2003
• Est. Priority Date: 10/09/1998
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Huang, Yingjieh, Nishida, Hirobumi
• Primary Examiner(s): Werner, Brian
• Application Number:
  US09/414,349
• Time in Patent Office: 1,454 Days
• Field of Search: 382/107, 382/154, 382/275, 382/285, 382/294, 382/309, 345/419, 348/43, 348/50
• US Class Current: 382/154
• CPC Class Codes: G06T 7/579 from motion

Abstract

A method of obtaining a 3-dimensional shape of an object from a sequence of image frames includes the steps of a) generating a tracking matrix which has matrix elements representing coordinates of feature points of the object tracked through the sequence, and has each row representing a corresponding image frame and each column representing a corresponding feature point, wherein some of the matrix elements are missing, b) generating an estimation matrix as a sub-matrix of the tracking matrix by selecting rows and by selecting a column of a given feature point and columns of a predetermined number of feature points closest to the given feature point, such that the estimation matrix has matrix elements thereof missing only for the given feature point in a single image frame, c) calculating estimates of the missing matrix elements of the estimation matrix, d) repeating the steps b) and c) to obtain estimates of remaining missing matrix elements of the tracking matrix, and e) obtaining a 3-dimensional shape of the object from the tracking matrix having the missing matrix elements thereof estimated.

Claims

1. A method of obtaining a 3-dimensional shape of an object from a sequence of image frames, comprising the steps of:

a) generating a tracking matrix which has matrix elements representing coordinates of feature points of the object tracked through the sequence, and has each row representing a corresponding image frame and each column representing a corresponding feature point, wherein some of the matrix elements are missing;

b) generating an estimation matrix as a sub-matrix of the tracking matrix by selecting rows and by selecting a column of a given feature point and columns of a predetermined number of feature points closest to the given feature point, such that the estimation matrix has matrix elements thereof missing only for the given feature point in a single image frame;

c) calculating estimates of the missing matrix elements of the estimation matrix;

d) repeating said steps b) and c) to obtain estimates of remaining missing matrix elements of the tracking matrix; and

e) obtaining a 3-dimensional shape of the object from the tracking matrix having the missing matrix elements thereof estimated.

2. The method as claimed in claim 1, wherein said step b) includes a step of comparing the coordinates of the given feature point with the coordinates of the feature points in an image frame immediately preceding said single image frame, so as to select said feature points closest to the given feature point.

3. The method as claimed in claim 1, wherein said step c) includes repeating estimation of the missing matrix elements of the estimation matrix until the estimation is successful while size of the estimation matrix is increased at each attempt of the estimation of the missing matrix elements of the estimation matrix.

4. The method as claimed in claim 1, wherein said step b) further includes a step of reshaping the tracking matrix by rearranging columns of the tracking matrix according to classification of the feature points into groups based on how the feature points are tracked through the sequence, said step of reshaping being performed prior to the generation of the estimation matrix.

5. The method as claimed in claim 4, wherein said step b) further includes a step of turning the tracking matrix upside down when the estimation matrix cannot be generated despite presence of still remaining missing matrix elements in the tracking matrix.

6. The method as claimed in claim 1, further comprising the steps of:

generating the sequence of image frames by taking pictures of the object while the object rotates relative to a camera view;

obtaining motion of the feature points from the tracking matrix having the missing matrix elements thereof estimated; and

reversing a convex surface to a concave surface or reversing a concave surface to a convex surface with regard to said 3-dimensional shape of the object if the motion of the feature points is in a direction opposite to a rotational direction of the object.

7. A device for obtaining a 3-dimensional shape of an object from a sequence of image frames, comprising:

a tracking-matrix-generation unit which generates a tracking matrix that has matrix elements representing coordinates of feature points of the object tracked through the sequence, and that has each row representing a corresponding image frame and each column representing a corresponding feature point, wherein some of the matrix elements are missing;

an estimation-matrix-generation unit which generates an estimation matrix as a sub-matrix of the tracking matrix by selecting rows and by selecting a column of a given feature point and columns of a predetermined number of feature points closest to the given feature point, such that the estimation matrix has matrix elements thereof missing only for the given feature point in a single image frame;

a missing-matrix-element-estimation unit which calculates estimates of the missing matrix elements of the estimation matrix, and further obtain estimates of remaining missing matrix elements of the tracking matrix based on estimation matrixes generated by said estimation-matrix-generation unit; and

a 3-dimensional-data operation unit which obtains a 3-dimensional shape of the object from the tracking matrix having the missing matrix elements thereof estimated.

8. The device as claimed in claim 7, wherein said estimation-matrix-generation unit compares the coordinates of the given feature point with the coordinates of the feature points in an image frame immediately preceding said single image frame, so as to select said feature points closest to the given feature point.

9. The device as claimed in claim 7, wherein repeats estimation of the missing matrix elements of the estimation matrix until the estimation is successful while said estimation-matrix-generation unit increases size of the estimation matrix at each attempt of the estimation of the missing matrix elements of the estimation matrix.

10. The device as claimed in claim 7, wherein said estimation-matrix-generation unit reshapes the tracking matrix by rearranging columns of the tracking matrix according to classification of the feature points into groups based on how the feature points are tracked through the sequence, and generates the estimation matrix as a sub-matrix of the reshaped tracking matrix.

11. The device as claimed in claim 10, wherein said estimation-matrix-generation unit turns the tracking matrix upside down when the estimation matrix cannot be generated despite presence of still remaining missing matrix elements in the tracking matrix.

12. The device as claimed in claim 7, further comprising a unit which generates the sequence of image frames by taking pictures of the object while the object rotates relative to a camera view, wherein said 3-dimensional-data operation unit obtains motion of the feature points from the tracking matrix having the missing matrix elements thereof estimated, and reverses a convex surface to a concave surface or reversing a concave surface to a convex surface with regard to said 3-dimensional shape of the object if the motion of the feature points is in a direction opposite to a rotational direction of the object.

13. A computer-readable medium having a program embodied therein for causing a computer to obtain a 3-dimensional shape of an object from a sequence of image frames, said program comprising:

a tracking-matrix-generation unit which generates a tracking matrix that has matrix elements representing coordinates of feature points of the object tracked through the sequence, and that has each row representing a corresponding image frame and each column representing a corresponding feature point, wherein some of the matrix elements are missing;

an estimation-matrix-generation unit which generates an estimation matrix as a sub-matrix of the tracking matrix by selecting rows and by selecting a column of a given feature point and columns of a predetermined number of feature points closest to the given feature point, such that the estimation matrix has matrix elements thereof missing only for the given feature point in a single image frame;

a missing-matrix-element-estimation unit which calculates estimates of the missing matrix elements of the estimation matrix, and further obtain estimates of remaining missing matrix elements of the tracking matrix based on estimation matrixes generated by said estimation-matrix-generation unit; and

a 3-dimensional-data operation unit which obtains a 3-dimensional shape of the object from the tracking matrix having the missing matrix elements thereof estimated.

14. The computer-readable medium as claimed in claim 13, wherein said estimation-matrix-generation unit compares the coordinates of the given feature point with the coordinates of the feature points in an image frame immediately preceding said single image frame, so as to select said feature points closest to the given feature point.

15. The computer-readable medium as claimed in claim 13, wherein said missing-matrix-element-estimation unit repeats estimation of the missing matrix elements of the estimation matrix until the estimation is successful while said estimation-matrix-generation unit increases size of the estimation matrix at each attempt of the estimation of the missing matrix elements of the estimation matrix.

16. The computer-readable medium as claimed in claim 13, wherein said estimation-matrix-generation unit reshapes the tracking matrix by rearranging columns of the tracking matrix according to classification of the feature points into groups based on how the feature points are tracked through the sequence, and generates the estimation matrix as a sub-matrix of the reshaped tracking matrix.

17. The computer-readable medium as claimed in claim 16, wherein said estimation-matrix-generation unit turns the tracking matrix upside down when the estimation matrix cannot be generated despite presence of still remaining missing matrix elements in the tracking matrix.

18. The computer-readable medium as claimed in claim 13, wherein said program further includes a unit which generates the sequence of image frames by taking pictures of the object while the object rotates relative to a camera view, and wherein said 3-dimensional-data operation unit obtains motion of the feature points from the tracking matrix having the missing matrix elements thereof estimated, and reverses a convex surface to a concave surface or reversing a concave surface to a convex surface with regard to said 3-dimensional shape of the object if the motion of the feature points is in a direction opposite to a rotational direction of the object.

19. A computer-readable medium having a program embodied therein for causing a computer to estimate missing matrix elements of a tracking matrix that has matrix elements representing coordinates of feature points of an object tracked through a sequence of image frames, and that has each row representing a corresponding image frame and each column representing a corresponding feature point, said program comprising

an estimation-matrix-generation unit which generates an estimation matrix as a sub-matrix of the tracking matrix by selecting rows and by selecting a column of a given feature point and columns of a predetermined number of feature points closest to the given feature point, such that the estimation matrix has matrix elements thereof missing only for the given feature point in a single image frame;

and

a missing-matrix-element-estimation unit which calculates estimates of the missing matrix elements of the estimation matrix, and further obtain estimates of remaining missing matrix elements of the tracking matrix based on estimation matrixes generated by said estimation-matrix-generation unit.

20. The computer-readable medium as claimed in claim 19, wherein said estimation-matrix-generation unit compares the coordinates of the given feature point with the coordinates of the feature points in an image frame immediately preceding said single image frame, so as to select said feature points closest to the given feature point.

21. A method of obtaining a 3-dimensional shape of an object, comprising the steps of:

generating a tracking matrix by tracking feature points through a sequence of images of the object, wherein the tracking matrix has some of matrix elements thereof missing;

extracting sub-matrixes from the tracking matrix to generate a plurality of tracking sub-matrixes having an overlapping portion with each other;

estimating the missing matrix elements in each of the tracking sub-matrixes to generate a plurality of measurement sub-matrixes substantially devoid of the missing matrix elements;

generating coordinate data of the feature points from each of the measurement sub-matrixes; and

integrating the coordinate data of the feature points over all the measurement sub-matrixes.

22. The method as claimed in claim 21, wherein said step of generating coordinate data of the feature points includes the steps of:

obtaining motion of the feature points and coordinates of the feature points from each of the measurement sub-matrixes; and

reversing a convex surface to a concave surface or reversing a concave surface to a convex surface with regard to a surface shape represented by said coordinates of the feature points if the motion of the feature points is in a direction opposite to a rotational direction of the object, so as to generate said coordinate data of the feature points.

23. The method as claimed in claim 21, further comprising the steps of:

obtaining data of camera positions from a given one of the measurement sub-matrixes;

selecting a texture-mapping image from one of the images that is selected based on the data of camera positions, the texture-mapping image being used for a surface represented by the coordinate data of the feature points obtained from the given one of the measurement sub-matrixes.

24. The method as claimed in claim 21, wherein said step of integrating the coordinate data of the feature points connects the coordinate data of the feature points between the measurement sub-matrixes by finding a match therebetween in said overlapping portion.

25. A computer-readable medium having a program embodied therein for causing a computer to obtain a 3-dimensional shape of an object, said program comprising:

a code unit configured to generate a tracking matrix by tracking feature points through a sequence of images of the object, wherein the tracking matrix has some of matrix elements thereof missing;

a code unit configured to extract sub-matrixes from the tracking matrix to generate a plurality of tracking sub-matrixes having an overlapping portion with each other;

a code unit configured to estimate the missing matrix elements in each of the tracking sub-matrixes to generate a plurality of measurement sub-matrixes substantially devoid of the missing matrix elements;

a code unit configured to generate coordinate data of the feature points from each of the measurement sub-matrixes; and

a code unit configured to integrate the coordinate data of the feature points over all the measurement sub-matrixes.

26. The computer-readable medium as claimed in claim 25, wherein said code unit configured to generate coordinate data of the feature points includes:

a code unit configured to obtain motion of the feature points and coordinates of the feature points from each of the measurement sub-matrixes; and

a code unit configured to reverse a convex surface to a concave surface or reverse a concave surface to a convex surface with regard to a surface shape represented by said coordinates of the feature points if the motion of the feature points is in a direction opposite to a rotational direction of the object, so as to generate said coordinate data of the feature points.

27. The computer-readable medium as claimed in claim 25, further comprising:

a code unit configured to obtain data of camera positions from a given one of the measurement sub-matrixes;

a code unit configured to select a texture-mapping image from one of the images that is selected based on the data of camera positions, the texture-mapping image being used for a surface represented by the coordinate data of the feature points obtained from the given one of the measurement sub-matrixes.

28. The computer-readable medium as claimed in claim 25, wherein said code unit configured to integrate the coordinate data of the feature points connects the coordinate data of the feature points between the measurement sub-matrixes by finding a match therebetween in said overlapping portion.

29. A device for obtaining a 3-dimensional shape of an object, comprising:

a tracking-matrix-generation unit which generates a tracking matrix by tracking feature points through a sequence of images of the object, wherein the tracking matrix has some of matrix elements thereof missing;

a tracking-matrix-division unit which extracts sub-matrixes from the tracking matrix to generate a plurality of tracking sub-matrixes having an overlapping portion with each other, and estimates the missing matrix elements in each of the tracking sub-matrixes to generate a plurality of measurement sub-matrixes substantially devoid of the missing matrix elements;

a 3-dimensional-fragmentary-data-generation unit which generates coordinate data of the feature points from each of the measurement sub-matrixes; and

a fragmentary-feature-point-data-integration unit which integrates the coordinate data of the feature points over all the measurement sub-matrixes.

30. The device as claimed in claim 29, wherein said 3-dimensional-fragmentary-data-generation unit obtains motion of the feature points and coordinates of the feature points from each of the measurement sub-matrixes, and reverses a convex surface to a concave surface or reverse a concave surface to a convex surface with regard to a surface shape represented by said coordinates of the feature points if the motion of the feature points is in a direction opposite to a rotational direction of the object, so as to generate said coordinate data of the feature points.

31. The device as claimed in claim 29, wherein said 3-dimensional-fragmentary-data-generation unit further obtains data of camera positions from a given one of the measurement sub-matrixes, and selects a texture-mapping image from one of the images that is selected based on the data of camera positions, the texture-mapping image being used for a surface represented by the coordinate data of the feature points obtained from the given one of the measurement sub-matrixes.

32. The device as claimed in claim 29, wherein said fragmentary-feature-point-data-integration unit connects the coordinate data of the feature points between the measurement sub-matrixes by finding a match therebetween in said overlapping portion.