3-D reconstruction and registration

• US 8,401,276 B1
• Filed: 05/20/2009
• Issued: 03/19/2013
• Est. Priority Date: 05/20/2008
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Medioni, Gerard, Choe, Tae Eun
• Primary Examiner(s): DULANEY, KATHLEEN YUAN
• Application Number:
  US12/469,638
• Time in Patent Office: 1,399 Days
• Field of Search: 382/154, 382/203, 382/266, 382/285, 382/294, 345/419, 356/12
• US Class Current: 382/154
• CPC Class Codes: G01C 11/06 by comparison of two or more pictures of the same area
• CPC Class Codes: G06T 2200/08 involving all processing steps from image acquisition to 3D model generation
• CPC Class Codes: G06T 2207/30041 Eye; Retina; Ophthalmic
• CPC Class Codes: G06T 2207/30244 Camera pose
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/55 from multiple images
• CPC Class Codes: G06T 7/73 using feature-based methods

Abstract

Generating three-dimensional information can include accessing multiple different images of an object taken by one or more cameras; selecting one of the accessed images as a reference image; identifying corresponding features between the reference image and one or more different ones of the accessed images; determining first camera pose information for each accessed image based on one or more of the corresponding features, each first camera pose information indicative of a relationship between an imaging device and the object; determining a first three-dimensional structure of the object based on first camera pose information of two of the accessed images; and generating a second three-dimensional structure and a second camera pose information for each accessed image based on the first three-dimensional structure and the first camera pose information for each accessed image.

Claims

1. A computer-implemented method for image processing, comprising:

accessing multiple different images of an object taken by one or more cameras;

selecting one of the accessed images as a reference image;

identifying corresponding features between the reference image and one or more different ones of the accessed images;

determining first camera pose information for each accessed image based on one or more of the corresponding features, each first camera pose information indicative of a relationship between an imaging device and the object;

determining a first three-dimensional structure of the object based on first camera pose information of two of the accessed images;

generating a second three-dimensional structure and a second camera pose information for each accessed image based on the first three-dimensional structure and the first camera pose information for each accessed image;

projecting points of the reference image to the second three-dimensional structure based on the second camera pose information associated with the reference image;

re-projecting the projected points onto a second one of the accessed images based on the second camera pose information associated with the second one of the accessed images; and

using the re-projected points to register the second one of the accessed images in three dimensions.

2. The method of claim 1, wherein determining the first three-dimensional structure comprises determining points on a three-dimensional structure that correspond to points on the two of the accessed images.

3. The method of claim 1,

wherein generating the second three-dimensional structure and second camera pose information for each accessed image comprises adjusting the first three-dimensional structure and the first camera pose information for each accessed image to back-project a three-dimensional structure based on a respective camera pose information onto a respective one of the accessed images.

4. The method of claim 1, wherein selecting one of the accessed images as the reference image comprises:

identifying features of each accessed image;

using the identified features of each accessed image and an iterative nearest neighbor matching algorithm to determine and refine homographies and feature matches between pairs of the accessed images; and

using an image with a least total shortest path cost to the other accessed images as the reference image, wherein a determination of the least total shortest path cost is based on the refined homographies.

5. The method of claim 1, further comprising:

selecting one of the accessed images as a widest baseline image, the widest baseline image corresponding to a camera position with a widest baseline with respect to the reference image;

determining a third three-dimensional structure of the object based on a mapping of points between the reference image and the widest baseline image; and

refining the second camera pose information for each accessed image different from the widest baseline image based on the widest baseline image.

6. The method of claim 5, further comprising:

projecting second points of the reference image to the third three-dimensional structure based on the refined second camera pose information associated with the reference image; and

re-projecting the second projected points onto a second one of the accessed images based on the refined second camera pose information associated with the second one of the accessed images; and

using the second re-projected points to register the second one of the accessed images in three dimensions.

7. The method of claim 1, wherein each accessed image has a near-planar surface depiction of the object.

8. The method of claim 1, wherein each camera pose information comprises a rotation matrix, a translation vector, and a focal length value.

9. The method of claim 1, further comprising:

registering the accessed images in two-dimensions, the registering comprising identifying one or more features of each accessed image and generating a two-dimensional representation of each feature of each accessed image,

wherein identifying corresponding features comprises using two or more of the two-dimensional representations.

10. A non-transitory computer readable medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

accessing multiple different images of an object taken by one or more cameras;

selecting one of the accessed images as a reference image;

identifying corresponding features between the reference image and one or more different ones of the accessed images;

determining first camera pose information for each accessed image based on one or more of the corresponding features, each first camera pose information indicative of a relationship between an imaging device and the object;

determining a first three-dimensional structure of the object based on first camera pose information of two of the accessed images;

generating a second three-dimensional structure and a second camera pose information for each accessed image based on the first three-dimensional structure and the first camera pose information for each accessed image;

projecting points of the reference image to the second three-dimensional structure based on the second camera pose information associated with the reference image;

re-projecting the projected points onto a second one of the accessed images based on the second camera pose information associated with the second one of the accessed images; and

using the re-projected points to register the second one of the accessed images in three dimensions.

11. The computer readable medium of claim 10, wherein determining the first three-dimensional structure comprises determining points on a three-dimensional structure that correspond to points on the two of the accessed images.

12. The computer readable medium of claim 10, wherein generating the second three-dimensional structure and second camera pose information for each accessed image comprises adjusting the first three-dimensional structure and/or the first camera pose information for each accessed image to back-project a three-dimensional structure based on a respective camera pose information onto a respective one of the accessed images.

13. The computer readable medium of claim 10, wherein selecting one of the accessed images as the reference image comprises:

identifying features of each accessed image;

using the identified features of each accessed image and an iterative nearest neighbor matching algorithm to determine and refine homographies and feature matches between pairs of the accessed images; and

using an image with a least total shortest path cost to the other accessed images as the reference image, wherein a determination of the least total shortest path cost is based on the refined homographies.

14. The computer readable medium of claim 10, the operations further comprising:

selecting one of the accessed images as a widest baseline image, the widest baseline image corresponding to a camera position with a widest baseline with respect to the reference image;

determining a third three-dimensional structure of the object based on a mapping of points between the reference image and the widest baseline image; and

refining the second camera pose information for each accessed image different from the widest baseline image based on the widest baseline image.

15. The computer readable medium of claim 14, the operations further comprising:

projecting second points of the reference image to the third three-dimensional structure based on the refined second camera pose information associated with the reference image; and

re-projecting the second projected points onto a second one of the accessed images based on the refined second camera pose information associated with the second one of the accessed images; and

using the second re-projected points to register the second one of the accessed images in three dimensions.

16. The computer readable medium of claim 10, wherein each accessed image has a near-planar surface depiction of the object.

17. The computer readable medium of claim 10, wherein each camera pose information comprises a rotation matrix, a translation vector, and a focal length value.

18. The computer readable medium of claim 10, the operations further comprising:

registering the accessed images in two-dimensions, the registering comprising identifying one or more features of each accessed image and generating a two-dimensional representation of each feature of each accessed image,

wherein identifying corresponding features comprises using two or more of the two-dimensional representations.

19. An image processing system comprising:

a memory configured to store multiple images of an object taken by one or more cameras; and

processor electronics in communication with the memory, configured to perform operations comprising;

accessing multiple different images of the object;

selecting one of the accessed images as a reference image;

identifying corresponding features between the reference image and one or more different ones of the accessed images;

determining first camera pose information for each accessed image based on one or more of the corresponding features, each first camera pose information indicative of a relationship between an imaging device and the object;

determining a first three-dimensional structure of the object based on first camera pose information of two of the accessed images;

generating a second three-dimensional structure and a second camera pose information for each accessed image based on the first three-dimensional structure and the first camera pose information for each accessed image;

projecting points of the reference image to the second three-dimensional structure based on the second camera pose information associated with the reference image;

re-projecting the projected points onto a second one of the accessed images based on the second camera pose information associated with the second one of the accessed images; and

using the re-projected points to register the second one of the accessed images in three dimensions.

20. The system of claim 19, wherein determining the first three-dimensional structure comprises determining points on a three-dimensional structure that correspond to points on the two of the accessed images.

21. The system of claim 19, wherein generating the second three-dimensional structure and second camera pose information for each accessed image comprises adjusting the first three-dimensional structure and/or the first camera pose information for each accessed image to back-project a three-dimensional structure based on a respective camera pose information onto a respective one of the accessed images.

22. The system of claim 19, wherein selecting one of the accessed images as the reference image comprises:

identifying features of each accessed image;

using the identified features of each accessed image and an iterative nearest neighbor matching algorithm to determine and refine homographies and feature matches between pairs of the accessed images; and

using an image with a least total shortest path cost to the other accessed images as the reference image, wherein a determination of the least total shortest path cost is based on the refined homographies.

23. The system of claim 19, the operations further comprising:

selecting one of the accessed images as a widest baseline image, the widest baseline image corresponding to a camera position with a widest baseline with respect to the reference image;

determining a third three-dimensional structure of the object based on a mapping of points between the reference image and the widest baseline image; and

refining the second camera pose information for each accessed image different from the widest baseline image based on the widest baseline image.

24. The system of claim 23, the operations further comprising:

projecting second points of the reference image to the third three-dimensional structure based on the refined second camera pose information associated with the reference image; and

re-projecting the second projected points onto a second one of the accessed images based on the refined second camera pose information associated with the second one of the accessed images; and

using the second re-projected points to register the second one of the accessed images in three dimensions.

25. The system of claim 19, wherein each accessed image has a near-planar surface depiction of the object.

26. The system of claim 19, wherein each camera pose information comprises a rotation matrix, a translation vector, and a focal length value.

27. The system of claim 19, the operations further comprising:

registering the accessed images in two-dimensions, the registering comprising identifying one or more features of each accessed image and generating a two-dimensional representation of each feature of each accessed image,

wherein identifying corresponding features comprises using two or more of the two-dimensional representations.