System and method for three-dimensional shape generation from partial and incomplete views, and interactive design system using same

• US 20060262112A1
• Filed: 05/23/2005
• Published: 11/23/2006
• Est. Priority Date: 05/23/2005
• Status: Abandoned Application

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Shimada, Kenji
• Application Number:
  US11/135,528
• Publication Number:
  US 20060262112A1
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2200/24 involving graphical user interfaces [GUIs]
• CPC Class Codes: G06T 2207/10081 Computed x-ray tomography [CT]
• CPC Class Codes: G06T 2207/10116 X-ray image
• CPC Class Codes: G06T 2207/20116 Active contour; Active surface; Snakes
• CPC Class Codes: G06T 2207/30004 Biomedical image processing
• CPC Class Codes: G06T 2210/44 Morphing
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/149 involving deformable models, e.g. active contour models
• CPC Class Codes: G06T 7/55 from multiple images
• CPC Class Codes: G06T 7/564 from contours

Abstract

Systems and methods for automatically generating a three-dimensional model of an object based on an input set of images of the object that may only have partial or incomplete information about the object'"'"'s shape are disclosed. The technique may assumes a template geometry, which represents a similar shape to the target object, and applies free-form deformation iteratively until the deformed shape matches a given set of partial views of the object. A non-linear numerical optimization technique is used to find the optimal deformation of the template geometry to achieve a good match. Also disclosed is an interactive design system that may be used to design an object whereby design modifications are applied interactively by a user to an existing design geometry to generate a new design geometry. The new design geometry is generated using extended free form deformation and optimization to deform the existing design of the object to match the new design.

Claims

1. A system for generating a three-dimensional model of an object comprising:

a deformation module for applying an extended free form deformation on an input set of CT scans of the object using a template geometry for the geometry of the object; and

an optimization module for determining a combination of free-form deformation parameters corresponding to a deformed three-dimensional shape that optimally matches the input set of CT scans of the object.

2. The system of claim 1, wherein the template geometry includes non-rectangular grids.

3. The system of claim 2, wherein the template geometry includes triangular grids.

4. The system of claim 2, wherein the template geometry includes hexagonal grids.

5. The system of claim 1, wherein the deformation module uses a polynomial interpolation function.

6. The system of claim 5, wherein the deformation module uses a linear polynomial interpolation function.

7. The system of claim 5, wherein the deformation module uses a higher-order polynomial interpolation function.

8. The system of claim 7, wherein the higher-order polynomial interpolation function includes a cubic Bezier curve.

9. The system of claim 7, wherein the deformation module uses a non-polynomial interpolation function.

10. The system of claim 1, wherein the optimization module uses a non-linear optimization algorithm.

11. The system of claim 1, wherein the optimization module is for determining the combination of free-form deformation parameters corresponding to the deformed three-dimensional shape that optimally matches the input set of CT scans of the object by:

matching a center of a contour of the template geometry with a center of a contour in the input set of CT scans; and

determining control lattice parameters that minimize the area between the contours of the input set of CT scans and planar cross contours of the template geometry.

12. A system for generating a three-dimensional model of an object comprising:

a deformation module for applying an extended free form deformation to a template geometry for the object based on an input set of images of the object, wherein a deformation lattice of the template geometry includes non-rectangular grids; and

an optimization module for determining a combination of free-form deformation parameters corresponding to a deformed three-dimensional shape that optimally matches the input set of CT scans of the object.

13. A system for designing an object, comprising:

a graphical user interface including a user input device for inputting a design modification to an existing design of the object displayed for the user on the graphical user interface;

a three-dimensional shape reconstruction system in communication with the graphical user interface for generating a three-dimensional model of the object based on the design modification input by the user.

14. The system of claim 13, wherein the design modification includes an input to indicate a desired geometry for a portion of the existing design.

15. The system of claim 14, wherein the three-dimensional shape reconstruction system includes:

a deformation module for applying an extended free form deformation on a template geometry for the existing design; and

an optimization module for determining a combination of free-form deformation parameters corresponding to a deformed three-dimensional shape that optimally matches the design modification.

16. The system of claim 15, wherein the template geometry includes non-rectangular grids.

17. The system of claim 16, wherein the template geometry includes triangular grids.

18. The system of claim 16, wherein the template geometry includes hexagonal grids.

19. The system of claim 15, wherein the deformation module uses a polynomial interpolation function.

20. The system of claim 15, wherein the deformation module uses a linear polynomial interpolation function.

21. The system of claim 15, wherein the deformation module uses a cubic polynomial interpolation function.

22. The system of claim 21, wherein the deformation module uses a non-polynomial as the interpolation function.

23. The system of claim 15, wherein the optimization module uses a non-linear optimization algorithm.

24. The system of claim 15, wherein the optimization module uses a linear optimization algorithm.

25. The system of claim 15, wherein the optimization module is for determining the combination of free-form deformation parameters corresponding to the deformed three-dimensional shape that optimally matches the design modification by:

matching a center of a contour of the template geometry with a center of a contour in the design modification; and

determining control lattice parameters that minimize the area between the contours of the design modification and planar cross contours of the template geometry of the existing design.

26. A method for generating a three-dimensional model of an object comprising:

applying an extended free form deformation on an input set of CT scans of the object using a template geometry for the geometry of the object; and

determining a combination of free-form deformation parameters corresponding to a deformed three-dimensional shape that optimally matches the input set of CT scans of the object.

27. A method for generating a three-dimensional model of an object comprising:

applying an extended free form deformation to a template geometry for the object based on an input set of images of the object, wherein the template geometry includes non-rectangular grids; and

determining a combination of free-form deformation parameters corresponding to a deformed three-dimensional shape that optimally matches the input set of CT scans of the object.

28. A method for designing an object, comprising:

displaying an existing three-dimensional design of the object on a graphical user interface;

receiving, from a user of the graphical user interface, a design modification to the existing design;

generating a three-dimensional model of the object based on the design modification by;

applying an extended free form deformation on a template geometry for the existing design; and

determining a combination of free-form deformation parameters corresponding to a deformed three-dimensional shape that optimally matches the design modification.