Surface model generation for visualizing three-dimensional objects using multiple elastic surface nets

• US 6,362,821 B1
• Filed: 01/06/1999
• Issued: 03/26/2002
• Est. Priority Date: 01/06/1999
• Status: Expired due to Term

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Leventon, Michael E., Gibson, Sarah F. F.
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Padmanabhan, Mano
• Application Number:
  US09/225,454
• Time in Patent Office: 1,175 Days
• Field of Search: 345/424, 345/427, 345/428, 345/432, 345/433, 345/435, 345/441, 345/425, 345/589, 345/619, 345/629, 382/131, 382/154, 382/173, 382/294, 382/285
• US Class Current: 345/424
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method generates a surface model for a three-dimensional object. The object is scanned from a plurality of directions to produce a volume data for each scanning direction. Each volume data is segmented to extract data associated with the object. The volume data are then registered to a common coordinate frame. After registration, a surface net is initialized for each volume data. The multiple surface nets are relaxed and merge according to the common coordinate frame to generate a renderable surface model.

Claims

1. A method for generating a surface model of a three-dimensional object, comprising the steps of:

scanning the object from a plurality of directions to produce volume data for each scanning direction;

segmenting each volume data to identify data associated with the object;

registering each volume data to a common coordinate frame;

initializing a surface net for each volume data; and

relaxing the surface nets interdependently according to the common coordinate frame to generate a renderable surface model.

2. The method of claim 1 wherein the object is scanned in two orthogonal directions.

3. The method of claim 1 wherein the scans are low-resolution scans.

4. The method of claim 1 wherein the segmentation identifies voxels of the volume data, the identified voxels corresponding to the scanned object.

5. The method of claim 1 wherein the segmenting is performed by intensity thresholding.

6. The method of claim 1 wherein the registering is performed by a stochastic gradient descent on the sum of squared differences of the smoothed segmented volume data.

7. The method of claim 1 wherein the surface nets are initialized by locating surface cells that contain surface nodes, a surface cell being defined by neighboring voxels straddling the surface of the object.

8. The method of claim 1 wherein the interdependent relaxing comprises the steps of:

relaxing a first surface net with respect to a second surface net;

relaxing the second surface net with respect to the first surface net;

relaxing the first surface net;

relaxing the second surface net; and

repeating the relaxing steps until a predetermined threshold is reached.

9. The method of claim 7 wherein the surface cells are dilated to increase convergence of the surface nets.

10. A system for generating a surface model of a three-dimensional object, comprising:

means for scanning the object from a plurality of directions to produce a volume data for each scanning direction;

means for segmenting each volume data to identify data associated with the object;

means for registering each volume data to a common coordinate frame;

means for initializing a surface net for each volume data; and

means for relaxing the surface nets interdependently according to the common coordinate frame to generate a renderable surface model.

11. A method for generating a surface model of a three-dimensional object, comprising:

identifying a first surface net based upon a first volume image scan of the object from a first direction, the first volume image scan having a first resolution;

identifying a second surface net based upon a second volume image scan of the object from a second direction different than the first direction, the second volume image scan having a second resolution; and

relaxing the first and the second surface nets interdependently to generate at least one surface model having a third resolution higher than the first resolution and higher than the second resolution.

12. The method of claim 11, wherein the first direction is orthogonal to the second direction.

13. The method of claim 11, wherein the first resolution and the second resolution are the same.

14. The method of claim 11, wherein the first and the second surface nets each include a plurality of nodes, each node in one surface net corresponding to a respective node in the other surface net, further comprising:

mapping the first surface net and the second surface net to a common coordinate frame;

wherein the interdependent relaxing of the first and the second surface nets includes determining an average weighted distance between two corresponding nodes on the common coordinate frame, and moving the node belonging to the first surface net based upon the determined average weighted distance.

15. The method of claim 14, wherein the generated surface model is a smoothed surface model.

16. The method of claim 14, wherein:

each node is disposed within one of a plurality of cells, each cell having a boundary; and

the interdependent relaxing of the first and the second surface nets includes moving the node no further than the cell boundary of the cell in which the moving node is disposed.

17. The method of claim 14, wherein:

each node is disposed within one of a plurality of cells, each cell having a boundary; and

the interdependent relaxing of the first and the second surface nets includes dilating the cell in which the moving node is disposed in correspondence with the movement of that node based upon the determined average weighted distance.

18. A system for generating a surface model of a three-dimensional object, comprising:

a volume image scanning device configured to scan the object in a first resolution from a first direction and to scan the object in a second resolution from a second direction different than the first direction;

a processor configured to (1) receive from the volume image scanning device first volume image data associated with the scan in the first direction and second volume image data associated with the scan in the second direction, (2) identify a first surface net based upon the first volume image data and a second surface net based upon the second volume image data, and (3) relax the first and second surface nets interdependently to generate at least one surface model having a third resolution higher than the first resolution and higher than the second resolution.

19. The system of claim 18, wherein the first resolution and the second resolution are the same.

20. The system of claim 18, wherein the first direction is orthogonal to the second direction.

21. The system of claim 18, wherein:

the first and second surface nets each include a plurality of nodes, each node in one surface net corresponding to a respective node in the other surface net; and

the processor is further configured to map the first surface net and the second surface net to a common coordinate system, and to, in interdependently relaxing the first and the second surface nets, determine an average weighted distance between two corresponding nodes on the common coordinate frame and move the node belonging to the first surface net based upon the determined average weighted distance.

22. The system of claim 21, wherein the generated surface model is a smoothed surface model.

23. The system of claim 21, wherein:

each node is disposed within one of a plurality of cells, each cell having a boundary; and

the processor, in interdependently relaxing the first and the second surface nets, is further configured to move the node no further than the cell boundary of the cell in which the moving node is disposed.

24. The system of claim 21, wherein:

each node is disposed within one of a plurality of cells, each cell having a boundary; and

the processor, in interdependently relaxing the first and the second surface nets, is further configured to dilate the cell in which the moving node is disposed in correspondence with the movement of that node based upon the determined average weighted distance.