Method and system for efficient extraction of a silhouette of a 3D mesh

Patent metadata

Field	Value
Publication number	US-9582934-B2
Application number	US-201113235802-A
Country	US
Kind code	B2
Filing date	Sep 19, 2011
Priority date	Sep 20, 2010
Publication date	Feb 28, 2017
Grant date	Feb 28, 2017

Abstract

A method and system for extracting a silhouette of a 3D mesh representing an anatomical structure is disclosed. The 3D mesh is projected to two dimensions. Silhouette candidate edges are generated in the projected mesh by pruning edges and mesh points based on topology analysis of the projected mesh. Each silhouette candidate edge that intersects with another edge in the projected mesh is split into two silhouette candidate edges. The silhouette is extracted using an edge following process on the silhouette candidate edges.

First claim

The invention claimed is:

1. A method for extracting a silhouette of a 3D mesh representing an anatomical structure, comprising:
projecting the 3D mesh onto a 2D image;
generating silhouette candidate edges in the projected mesh by pruning mesh points and edges of the projected mesh that lie completely inside a region enclosed by the projected mesh;
splitting each silhouette candidate edge that intersects with another edge in the projected mesh into two silhouette candidate edges; and
extracting the silhouette using an edge following process on the silhouette candidate edges.

2. The method of claim 1 , wherein the 3D mesh is an open mesh, further comprising:
converting the 3D mesh from an open mesh to a closed mesh prior to the step of projecting the 3D mesh to two dimensions.

3. The method of claim 2 , wherein the step of converting the 3D mesh from an open mesh to a closed mesh prior to the step of projecting the 3D mesh to two dimensions comprises:
adding a mesh point to the 3D mesh at a center of a hole in the 3D mesh; and
adding edges to connect mesh points on a rim of the hole in the 3D mesh to the added mesh point at the center of the hole.

4. The method of claim 1 , wherein the step of projecting the 3D mesh onto a 2D image comprises:
projecting mesh points of the 3D mesh onto the 2D image while preserving connectivity between the mesh points.

5. The method of claim 1 , wherein each edge of the projected mesh is shared by two triangle faces, the normal of an imaging place is N 1 , the and normals of the two faces shared by and edge are N 1 and N 2 , respectively, and the step of generating silhouette candidate edges in the projected mesh comprises:
calculating N 1 ·N 1 and N 1 ·N 2 for each edge; and
determining that an edge is a silhouette candidate edge when N 1 ·N 1 and N 1 ·N 2 have different signs for that edge.

6. The method of claim 1 , wherein each edge of the projected mesh has two endpoints A and B which are shared by two triangle faces, and a third point in each of the two faces is C 1 and C 2 , respectively, and the step of generating silhouette candidate edges in the projected mesh comprises:
for each edge, determining that the edge is an edge candidate when C 1 and C 2 lie on the same side of the edge.

7. The method of claim 1 , wherein the step of generating silhouette candidate edges in the projected mesh comprises:
dividing a plurality of mesh points of the projected mesh into a set of inner points and a set of boundary points;
pruning the set of inner points; and
determining the silhouette candidate edges to be a set of edges connecting the boundary points.

8. The method of claim 7 , wherein the step of dividing a plurality of mesh points of the projected mesh into a set of inner points and a set of boundary points comprises:
for each mesh point, calculating a summation of internal angles of a closed contour defined by neighboring mesh points to the mesh point;
determining each mesh point with a summation equal to zero to be a boundary point; and
determining each mesh point with a summation equal to 2π or −2π to be an internal point.

9. The method of claim 1 , wherein the step of splitting each silhouette candidate edge that intersects with another edge in the projected mesh into two silhouette candidate edges comprises:
detecting an intersection point between a silhouette candidate edge and another edge in the projected mesh; and
adding a mesh point at the detected intersection point to divide the silhouette candidate edge into two silhouette candidate edges.

10. The method of claim 1 , wherein the step of extracting the silhouette using an edge following process on the silhouette candidate edges comprises:
starting in a downward direction from a left most mesh point of the set of silhouette candidate edges, following a series of right most neighbor silhouette candidate edges to return to the starting point.

11. The method of claim 1 , further comprising:
generating a silhouette mask in a 2D image from the extracted silhouette.

12. An apparatus for extracting a silhouette of a 3D mesh representing an anatomical structure, comprising:
means for projecting the 3D mesh onto a 2D image;
means for generating silhouette candidate edges in the projected mesh by pruning mesh points and edges of the projected mesh that lie completely inside a region enclosed by the projected mesh;
means for splitting each silhouette candidate edge that intersects with another edge in the projected mesh into two silhouette candidate edges; and
means for extracting the silhouette using an edge following process on the silhouette candidate edges.

13. The apparatus of claim 12 , further comprising:
means for converting the an 3D mesh from an open mesh to a closed mesh prior to projecting the 3D mesh to two dimensions.

14. The apparatus of claim 12 , wherein the means for projecting the 3D mesh onto a 2D image comprises:
means for projecting mesh points of the 3D mesh onto the 2D image while preserving connectivity between the mesh points.

15. The apparatus of claim 12 , wherein each edge of the projected mesh is shared by two triangle faces, the normal of an imaging place is N 1 , the and normals of the two faces shared by and edge are N 1 and N 2 , respectively, and the means for generating silhouette candidate edges in the projected mesh comprises:
means for calculating N 1 ·N 1 and N 1 ·N 2 for each edge; and
means for determining that an edge is a silhouette candidate edge when N 1 ·N 1 and N 1 ·N 2 have different signs for that edge.

16. The apparatus of claim 12 , wherein each edge of the projected mesh has two endpoints A and B which are shared by two triangle faces, and a third point in each of the two faces is C 1 and C 2 , respectively, and the means for generating silhouette candidate edges in the projected mesh comprises:
means for determining that an edge is an edge candidate when C 1 and C 2 lie on the same side of the edge.

17. The apparatus of claim 12 , wherein the means for generating silhouette candidate edges in the projected mesh comprises:
means for dividing a plurality of mesh points of the projected mesh into a set of inner points and a set of boundary points;
means for pruning the set of inner points; and
means for determining the silhouette candidate edges to be a set of edges connecting the boundary points.

18. The apparatus of claim 12 , wherein the means for splitting each silhouette candidate edge that intersects with another edge in the projected mesh into two silhouette candidate edges comprises:
means for detecting an intersection point between a silhouette candidate edge and another edge in the projected mesh; and
means for adding a mesh point at the detected intersection point to divide the silhouette candidate edge into two silhouette candidate edges.

19. The apparatus of claim 12 , further comprising:
means for generating a silhouette mask in a 2D image from the extracted silhouette.

20. A non-transitory computer readable medium encoded with computer executable instructions for extracting a silhouette of a 3D mesh representing an anatomical structure, the computer executable instructions defining steps comprising:
projecting the 3D mesh onto a 2D image;
generating silhouette candidate edges in the projected mesh by pruning mesh points and edges of the projected mesh that lie completely inside a region enclosed by the projected mesh;
splitting each silhouette candidate edge that intersects with another

Assignees

• Zheng Yefeng
• Pang Yu
• Liao Rui
• John Matthias
• Boese Jan
• Zhou Shaohua Kevin
• Comaniciu Dorin
• Siemens Healthcare Gmbh

Inventors

• Zheng Yefeng
• Pang Yu
• Liao Rui
• John Matthias
• Boese Jan
• Zhou Shaohua Kevin
• Comaniciu Dorin

Classifications

• G06T2207/20136

  Physics · mapped topic

• G06T17/20 Primary

  Finite element generation, e.g. wire-frame surface description, {tesselation} · CPC title

• G06T7/0083

  Physics · mapped topic

• G06T7/12

  Edge-based segmentation · CPC title

• G06T7/181

  involving edge growing; involving edge linking · CPC title