| Sonstiges: |
- Nachgewiesen in: USPTO Patent Applications
- Sprachen: English
- Document Number: 20080205720
- Publication Date: August 28, 2008
- Appl. No: 11/960867
- Application Filed: December 20, 2007
- Assignees: Siemens Corporate Research, Inc. (Princeton, NJ, US)
- Claim: 1. A method for determining whether a point is contained in a sub-volume of a digitized medical image, comprising the steps of: providing a digitized image volume, said image volume comprising a plurality of intensities associated with a 3-dimensional grid of voxels; representing a sub-volume of said image with a tetrahedron volume mesh (TVM); providing a point M in said image; finding a vertex P of said TVM that is closest to point M; and determining whether there exists a tetrahedron T in said TVM that defines a solid angle around point P where point M is located, wherein if no such tetrahedron T exists, then point M is outside said TVM, and wherein if T exists and M is inside T, then M is inside said TVM.
- Claim: 2. The method of claim 1, wherein if tetrahedron T exists and M is not inside T, further comprising the steps of: finding a facet F of tetrahedron T through which a line PM connecting points M and P exits T; determining whether a next tetrahedron Ti+1 of said TVM exists along line PM, wherein if no such tetrahedron Ti+1 exists, then point M is outside said TVM, and wherein if Ti+1 exists, determining whether point M is inside tetrahedron Ti+1.
- Claim: 3. The method of claim 2, wherein if point M is inside tetrahedron Ti+1, then point M is inside said TVM, and if point M is not inside tetrahedron Ti+1, repeating said steps of finding a facet F of tetrahedron Ti+1 through which a line PM exits Ti+1 and determining whether another tetrahedron of said TVM exists along line PM.
- Claim: 4. The method of claim 2, wherein determining whether point M is inside tetrahedron Ti+1, wherein tetrahedron Ti+1 has vertices A, B, C, D, comprises testing whether the inequalities ( BM· NAABCD)·( BA· NAABCD)≧0, ( CM· NBABCD)·( CB· NBABCD)≧0, ( DM· NCABCD)·( DC· NCABCD)≧0, ( AM· NDABCD)·( AD· NDABCD)≧0, hold true, wherein NAABCD, NBABCD, NCABCD, and NDABCD are the normal vectors to the four facets of ABCD, and the subscript corresponds to the opposite vertex of the facet.
- Claim: 5. The method of claim 2, wherein finding a facet F of tetrahedron T wherein tetrahedron T has vertices A, B, C, P, through which line PM exits T comprises, for a first tetrahedron along line PM, finding facet ABC and the point H0 in ABC through which line PM exits, and for a subsequent tetrahedron Ti along line PM, finding the points of intersection of line PM with the planes containing each of the other facets of tetrahedron T and determining which intersection point is contained within the triangle of a facet of tetrahedron T.
- Claim: 6. The method of claim 5, wherein finding the points of intersection of line PM with the planes containing each of the other facets of tetrahedron T comprises calculating [mathematical expression included] wherein point O is the origin of the coordinate system, NAABCD, NBABCD, NCABCD, and NDABCD are the normal vectors to the four facets of ABCD and the subscript corresponds to the opposite vertex of the facet, and HiBiCiDi, HiAiBiCi, HiAiBiDi, are the points of intersection with the planes of facets BiCiDi, AiBiCi, and AiBiDi of tetrahedron Ti.
- Claim: 7. The method of claim 6, wherein if Hi−1HiBiCiDi· NBiAiBiCiDi≧0 and Hi−1HiBiCiDi· NCiAiBiCiDi≧0 then Hi=HiBiCiDi, if Hi−1HiAiCiDi· NAiAiBiCiDi≧0 and Hi−1HiBiCiDi· NCiAiBiCiDi≧0 then Hi=HiAiCiDi, or if Hi−1HiAiBiDi· NAiAiBiCiDi≧0 and Hi−1HiBiCiDi· NBiAiBiCiDi≧0 then Hi=HiAiBiDi, wherein Hi−1 is the intersection point of a previous tetrahedron along line PM.
- Claim: 8. The method of claim 1, further comprising computing an octree to represent said digital image volume, wherein said vertex P of said TVM that is closest to point M is found by using a nearest point algorithm on said octree.
- Claim: 9. The method of claim 2, further comprising: computing a list LP of all tetrahedra of said TVM; computing and storing normal vectors of each of the four facets of each tetrahedron in said list; and computing a table of facets TF corresponding to each normal vector; searching said list LP to find said tetrahedron Tin said TVM that defines a solid angle around point P in which point M is located; and searching said facet table TF to find said next tetrahedron Ti+1 of said TVM along line PM.
- Claim: 10. The method of claim 9, further comprising, for a TVM that is not convex, searching said facet table TF to find facets TB with no other corresponding facets, computing a convex envelope of the facets TB and adding facets {tilde over (T)}B corresponding to said envelope to said facets TB, computing connected components C({tilde over (T)}B) in {tilde over (T)}B, and filling each connected component of C({tilde over (T)}B) with a tetrahedron labeled as an outside tetrahedron, wherein tetrahedra of said non-convex TVM are labeled as inside tetrahedra, wherein said TVM is converted to a convex sub-volume.
- Claim: 11. The method of claim 10, wherein point M is inside said TVM if said tetrahedron T is an inside tetrahedron.
- Claim: 12. A method for determining whether a point is contained in a sub-volume of a digitized medical image, comprising the steps of: providing a tetrahedron volume mesh (TVM) representing a sub-volume of a digital image volume, and a point M; finding a vertex P of said TVM that is closest to point M; finding a tetrahedron Ti in said TVM that defines a solid angle around point P where point M is located, wherein if M is inside Ti, then M is inside said TVM; if M is not inside Ti, finding a facet F of tetrahedron Ti through which a line PM connecting points M and P exits Ti; and determining whether a next tetrahedron Ti+1 of said TVM exists along line PM, wherein if no such tetrahedron Ti+1 exists, then point M is outside said TVM, and wherein if Ti+1 exists, determining whether point M is inside tetrahedron Ti+1.
- Claim: 13. The method of claim 12, wherein if no such tetrahedron Ti in said TVM exists that defines a solid angle around point P where point M is located, then point M is outside said TVM.
- Claim: 14. The method of claim 12, wherein if point M is inside tetrahedron Ti+1, then point M is inside said TVM, and if point M is not inside tetrahedron Ti+1, repeating said steps of finding a facet F of tetrahedron Ti+1 through which a line PM exits Ti+1 and determining whether another tetrahedron of said TVM exists along line PM.
- Claim: 15. The method of claim 12, wherein determining whether point M is inside tetrahedron Ti+1, wherein tetrahedron Ti+1 has vertices A, B, C, D, comprises testing whether the inequalities ( BM· NAABCD)·( BA· NAABCD)≧0, ( CM· NBABCD)·( CB· NBABCD)≧0, ( DM· NCABCD)·( DC· NCABCD)≧0, ( AM· NDABCD)·( AD· NDABCD)≧0, hold true, wherein NAABCD, NBABCD, NCABCD, and NDABCD are the normal vectors to the four facets of ABCD, and the subscript corresponds to the opposite vertex of the facet.
- Claim: 16. The method of claim 12, wherein finding a facet F of tetrahedron T wherein tetrahedron T has vertices A, B, C, P, through which line PM exits T comprises, for a first tetrahedron along line PM, finding facet ABC and the point H0 in ABC through which line PM exits, and for a subsequent tetrahedron Ti along line PM, finding the points of intersection of line PM with the planes containing each of the other facets of tetrahedron T and determining which intersection point is contained within the triangle of a facet of tetrahedron T.
- Claim: 17. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for determining whether a point is contained in a sub-volume of a digitized medical image, said method comprising the steps of: providing a digitized image volume, said image volume comprising a plurality of intensities associated with a 3-dimensional grid of voxels; representing a sub-volume of said image with a tetrahedron volume mesh (TVM); providing a point M in said image; finding a vertex P of said TVM that is closest to point M; and determining whether there exists a tetrahedron T in said TVM that defines a solid angle around point P where point M is located, wherein if no such tetrahedron T exists, then point M is outside said TVM, and wherein if T exists and M is inside T, then M is inside said TVM.
- Claim: 18. The computer readable program storage device of claim 17, wherein if tetrahedron T exists and M is not inside T, the method further comprises the steps of: finding a facet F of tetrahedron T through which a line PM connecting points M and P exits T; determining whether a next tetrahedron Ti+1 of said TVM exists along line PM, wherein if no such tetrahedron Ti+1 exists, then point M is outside said TVM, and wherein if Ti+1 exists, determining whether point M is inside tetrahedron Ti+1.
- Claim: 19. The computer readable program storage device of claim 18, wherein if point M is inside tetrahedron Ti+1, then point M is inside said TVM, and if point M is not inside tetrahedron Ti+1, repeating said steps of finding a facet F of tetrahedron Ti+1 through which a line PM exits Ti+1 and determining whether another tetrahedron of said TVM exists along line PM.
- Claim: 20. The computer readable program storage device of claim 18, wherein determining whether point M is inside tetrahedron Ti+1, wherein tetrahedron Ti+1 has vertices A, B, C, D, comprises testing whether the inequalities ( BM· NAABCD)·( BA· NAABCD)≧0, ( CM· NBABCD)·( CB· NBABCD)≧0, ( DM· NCABCD)·( DC· NCABCD)≧0, ( AM· NDABCD)·( AD· NDABCD)≧0, hold true, wherein NAABCD, NBABCD, NCABCD, and NDABCD are the normal vectors to the four facets of ABCD, and the subscript corresponds to the opposite vertex of the facet.
- Claim: 21. The computer readable program storage device of claim 18, wherein finding a facet F of tetrahedron T wherein tetrahedron T has vertices A, B, C, P, through which line PM exits T comprises, for a first tetrahedron along line PM, finding facet ABC and the point H0 in ABC through which line PM exits, and for a subsequent tetrahedron Ti along line PM, finding the points of intersection of line PM with the planes containing each of the other facets of tetrahedron T and determining which intersection point is contained within the triangle of a facet of tetrahedron T.
- Claim: 22. The computer readable program storage device of claim 21, wherein finding the points of intersection of line PM with the planes containing each of the other facets of tetrahedron T comprises calculating [mathematical expression included] wherein point O is the origin of the coordinate system, NAABCD, NBABCD, NCABCD, and NDABCD are the normal vectors to the four facets of ABCD and the subscript corresponds to the opposite vertex of the facet, and HiBiCiDi, HiAiBiCi, HiAiBiDi are the points of intersection with the planes of facets BiCiDi, AiBiCi, and AiBiDi of tetrahedron Ti.
- Claim: 23. The computer readable program storage device of claim 22, wherein if Hi−1HiBiCiDi· NBiAiBiCiDi≧0 and Hi−1HiBiCiDi· NCiAiBiCiDi≧0 then Hi=HiBiCiDi, if Hi−1HiAiCiDi· NAiAiBiCiDi≧0 and Hi−1HiBiCiDi· NCiAiBiCiDi≧0 then Hi=HiAiCiDi, or if Hi−1HiAiBiDi· NAiAiBiCiDi≧0 and Hi−1HiBiCiDi· NBiAiBiCiDi≧0 then Hi=HiAiBiDi, wherein Hi−1 is the intersection point of a previous tetrahedron along line PM.
- Claim: 24. The computer readable program storage device of claim 17, the method further comprising computing an octree to represent said digital image volume, wherein said vertex P of said TVM that is closest to point M is found by using a nearest point algorithm on said octree.
- Claim: 25. The computer readable program storage device of claim 18, the method further comprising: computing a list LP of all tetrahedra of said TVM; computing and storing normal vectors of each of the four facets of each tetrahedron in said list; and computing a table of facets TF corresponding to each normal vector; searching said list LP to find said tetrahedron Tin said TVM that defines a solid angle around point P in which point M is located; and searching said facet table TF to find said next tetrahedron Ti+1 of said TVM along line PM.
- Claim: 26. The computer readable program storage device of claim 25, the method further comprising, for a TVM that is not convex, searching said facet table TF to find facets TB with no other corresponding facets, computing a convex envelope of the facets TB and adding facets {tilde over (T)}B corresponding to said envelope to said facets TB, computing connected components C({tilde over (T)}B) in {tilde over (T)}B, and filling each connected component of C({tilde over (T)}B) with a tetrahedron labeled as an outside tetrahedron, wherein tetrahedra of said non-convex TVM are labeled as inside tetrahedra, wherein said TVM is converted to a convex sub-volume.
- Claim: 27. The computer readable program storage device of claim 26, wherein point M is inside said TVM if said tetrahedron T is an inside tetrahedron.
- Current U.S. Class: 382/128
- Current International Class: 06
|
