Method of centerline generation in virtual objects

• US 7,324,104 B1
• Filed: 09/16/2002
• Issued: 01/29/2008
• Est. Priority Date: 09/14/2001
• Status: Expired due to Fees

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Wax, Mark R., Bitter, Ingmar, Kaufman, Arie E., Wan, Ming, Liang, Jerome
• Primary Examiner(s): Chauhan; Ulka
• Assistant Examiner(s): WOODS, ERIC V
• Application Number:
  US10/246,015
• Time in Patent Office: 1,961 Days
• Field of Search: 382/154, 382/128, 382/259, 345619-641, 345418-428
• US Class Current: 345/420
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images
• CPC Class Codes: G06T 2207/10081 Computed x-ray tomography [CT]
• CPC Class Codes: G06T 2207/20044 Skeletonization; Medial axis transform
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 2207/30028 Colon; Small intestine
• CPC Class Codes: G06T 2207/30172 Centreline of tubular or elongated structure
• CPC Class Codes: G06T 2210/41 Medical
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/155 involving morphological operators
• CPC Class Codes: G06T 7/162 involving graph-based methods
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes

Abstract

Methods for generating a centerline or skeleton structure within a 3D virtual object are provided. A first method defines a centerline based on distance from boundary values along points of the defined centerline. A second method uses a distance from boundary field to assign costs to voxels in the virtual object and defines a minimum cost spanning tree based on assigned costs. The centerline is defined along the minimum cost spanning tree. Branches along the centerline are identified and added to the centerline to define a skeleton.

Claims

1. A computer-readable medium which includes thereon a set of instructions for generating a centerline in a virtual object represented as a plurality of voxels, wherein the set of instructions are configured to program a processing arrangement to perform the steps of:

computing the distance from boundary (DFB) for each voxel in the virtual object;

selecting a seed point in the virtual object as the current voxel;

selecting a next point from a set of points having a distance from the current voxel determined by the distance from boundary value of the current voxel;

connecting the current voxel to the next point and assigning the next point as the new current voxel; and

repeating the steps of selecting a next point and connecting until the centerline for the object is complete, thereby generating a centerline for at least one of display and navigation within the virtual object;

wherein the set of points is the set of voxels on the surface of at least a portion of a sphere centered at the current voxel and having a radius equal to the DFB value of the current voxel, and wherein the next point has a DFB value that is higher than the DFB value of its neighbors.

2. The computer readable medium containing instructions for generating a centerline as set forth in claim 1, wherein the next point is the voxel on the surface of the sphere having the maximum DFB value.

4. The computer readable medium containing instructions for generating a centerline as set forth in claim 1, wherein the connection of current voxels and next points is defined by straight line segments.

5. The computer readable medium containing instructions for generating a centerline as set forth in claim 1, wherein the connection of current voxels and next points is defined by a ridge in the DFB field between each two connected voxels.

6. The computer readable medium containing instructions for generating a centerline as set forth in claim 1, wherein the connection of current voxels and next points is defined by a smooth curve.

3. A computer-readable medium which includes thereon a set of instructions for generating a centerline in a virtual object represented as a plurality of voxels, wherein the set of instructions are configured to program a processing arrangement to perform the steps of:

computing the distance from boundary (DFB) for each voxel in the virtual object;

selecting a seed point in the virtual object as the current voxel;

selecting a next point from a set of points having a distance from the current voxel determined by the distance from boundary value of the current voxel;

connecting the current voxel to the next point and assigning the next point as the new current voxel; and

repeating the steps of selecting a next point and connecting until the centerline for the object is complete, thereby generating a centerline for at least one of display and navigation within the virtual object,

wherein the set of points is defined by the surface of a cube inscribed within the sphere.

7. A system for generating a centerline of a virtual object represented as a plurality of voxels, comprising:

a computer-readable medium which includes thereon a set of instructions, wherein the set of instructions are configured to program a processing arrangement to;

compute the distance from boundary (DFB) for each voxel in the region;

select a seed point in the region;

compute a minimum cost spanning tree (MCST) rooted at the seed point for all voxels in the region;

determine the furthest voxel with the longest piecewise accumulated distance along the edges of the MCST; and

define the centerline as the path within the MCST between the seed voxel and the furthest voxel, thereby generating a centerline for at least one of display and navigation within the virtual object;

wherein computing a minimum cost spanning tree includes assigning a cost value to voxels which is inversely proportional to the voxel'"'"'s DFB value; and

wherein the centerline is determined from back-trace in an accumulated cost field using the local gradient descent.

8. Computer readable media programmed with instructions to direct a computer to generate a centerline of a virtual object comprising the steps:

computing the distance from boundary (DFB) for each voxel in the region;

selecting a seed point in the region;

computing a minimum cost spanning tree (MCST) rooted at the seed point for all voxels in the region;

determining the furthest voxel with the longest piecewise accumulated distance along the edges of the MCST; and

defining the centerline as the path within the MCST between the seed voxel and the furthest voxel, thereby generating a centerline for at least one of display and navigation within the virtual object;

wherein the step of computing a minimum cost spanning tree includes assigning a cost value to voxels which is inversely proportional to the voxel'"'"'s DFB value; and

wherein the centerline path is determined from back-trace in an accumulated cost field using the local gradient descent.