Image analysis – Applications – Biomedical applications
Reexamination Certificate
2001-03-27
2003-10-07
Ahmed, Samir (Department: 2623)
Image analysis
Applications
Biomedical applications
Reexamination Certificate
active
06631202
ABSTRACT:
BACKGROUND
1. Field of the Invention
This invention relates to the analysis of digital images, specifically to the construction of computational meshes from such images.
2. Description of the Prior Art
Digital images are often analyzed to obtain meshes for further computation. For example, seismic images are analyzed to obtain geologic meshes used to simulate oil flowing in subsurface reservoirs. Similarly, medical images of the human brain are analyzed to obtain meshes used to simulate blood flow in arteries. A somewhat different example is image morphing, in which meshes derived from one image may be used to encode efficiently differences in subsequent images. In all of these applications, an image is analyzed to construct a mesh.
Images and Meshing Today
Specifically, such applications often consist of the following sequence of steps:
(1) Process an image to enhance features of interest.
(2) Find curves or surfaces in the image that bound regions of interest.
(3) Fill the space defined by those regions with a computational mesh.
(4) Simulate some process on the space-filling mesh.
For an application in medical imaging, see, Cebral, J. R., and Löhner, R., From Medical Images to CFD Meshes, Proceedings of the 8th International Meshing Roundtable, p. 321-331, Sandia, 1999. For an application in seismic imaging, see, Garrett, S., Griesbach, S., Johnson, D., Jones, D., Lo, M., Orr, W., and Sword, C., Earth Model Synthesis, First Break, v. 15, no. 1, p. 13-20, 1997.
For various reasons, each step in this sequence is today often taken independently, with little regard for the requirements of subsequent steps. For example, it is common in step (2) to produce a bounding curve or surface with more detail than can be represented in the space-filling mesh used in step (4). Seismic reflections representing geologic interfaces are routinely mapped with higher resolution than can practically be used in meshes for petroleum reservoir simulation. This leads to the “scale up” or “upscaling” problem cited by Garrett et al. (1997).
This discrepancy in resolution is often accompanied by a discrepancy in data structure. For example, a two-dimensional (2-D) curve represented by a simple linked list of line segments in step (2) may become a relatively complex mesh of triangles in step (3). Such discrepancies today disrupt the analysis sequence, and may yield inconsistencies between the image processed in step (1) and the mesh used in step (4) that are difficult to quantify.
The disruptions are costly. In the example of seismic image analysis, one iteration of this sequence today may require months of work. This high cost makes it difficult to perform multiple iterations in an attempt to estimate uncertainties in analysis results.
One reason for discrepancies in resolution and data structure lies in the implementation of the analysis sequence. Historically, the four steps listed above may have been performed by separate computer programs, developed independently, and used by different specialists. Today, a single person or small group may perform all four steps in this sequence, and there exists demand for the steps to be more integrated.
Another reason for discrepancies is a lack of methodology. The simulation step (4) often requires the numerical solution of partial differential equations (PDEs). In the past, these solutions were feasible for only structured meshes, in which mesh elements can be indexed as simple arrays. The conversion of an unstructured mesh produced in step (3) to a structured mesh yields additional inconsistencies between the processed image and the mesh used in simulation. However, recent advances in numerical methods for solving PDEs on unstructured meshes suggest that this conversion and resulting inconsistencies can be avoided.
Meshing with Lattices
The accuracy of most computations performed on meshes depends on the regularity of mesh elements. Simulations performed on highly regular triangular meshes, those with nearly equilateral triangles, are more accurate than those performed on irregular meshes with long thin triangles.
This is one reason that the Delaunay triangulation is popular. Given a set of points representing the locations of nodes for a 2-D mesh, the Delaunay triangulation of those points, when compared with all other possible triangulations, yields triangles most nearly equilateral. However, Delaunay triangulation alone does not guarantee a regular mesh. For that, one must choose carefully the locations of the mesh nodes.
(For a survey of 2-D and 3-D Delaunay triangulation applied to the problem of meshing, see Bern, M., and Eppstein, D., Mesh Generation and Optimal Triangulation, in Computing in Euclidean Geometry, Du, D. -Z. and Hwang., F. K. eds., World Scientific, 1995.)
Outside the domain of image analysis, the problem of choosing optimal mesh node locations has been well studied. One solution to this problem is based on the observation that the triangulation of a set of points defined by a simple crystal lattice yields a highly regular mesh. (See Mello, U. T., and Cavalcanti, P. R., A Point Creation Strategy for Mesh Generation Using Crystal Lattices as Templates, Proceedings of the 9th International Meshing Roundtable, p. 253-261, Sandia, 2000.) However, a uniform lattice of points can seldom be aligned exactly with the boundaries of objects to be meshed. Therefore, some solutions begin with an approximately uniform lattice, and then use numerical models of physical forces between atoms or bubbles to automatically move mesh nodes (atoms or bubbles) to more optimal locations. (See Shimada, K., Physically-Based Mesh Generation: Automated Triangulation of Surfaces and Volumes via Bubble Packing, Ph.D. thesis, Massachusetts Institute of Technology, 1993, and Shimada, K., and Gossard, D. C., Bubble Mesh: Automated Triangular Meshing of Non-Manifold Geometry by Sphere Packing, in Proceedings of the Third Symposium on Solid Modeling and Applications, p. 409-419, 1995. U.S. Pat. No. 6,124,857, to Itoh, T., Inoue, K., Yamada, A., and Shimada, K., Meshing Method and Apparatus, 2000, extends this work to quadrilateral meshing. See also Bossen, F. J., and Heckbert, P. S., A Pliant Method for Anisotropic Mesh Generation, Proceedings of the 5th International Meshing Roundtable, p. 63-74, Sandia, 1996.)
In all of these examples, lattice-based meshing begins with a geometric model that defines precisely the internal and external boundaries of objects to be meshed. Thus, there exists a need for a meshing system and methodology capable of addressing problems where such boundaries may not be known a-priori.
U.S. Patents Cited in this Specification
U.S. Pat. No. 4,908,781, to Levinthal, C., and Fine, R., Computing Device for Calculating Energy and Pairwise Central Forces of Particle Interactions, 1990.
U.S. Pat. No. 5,596,511, to Toyoda, S., Ikeda, H, Hashimoto, E., and Miyakawa, N., Computing Method and Apparatus for a Many-Body Problem, 1997.
U.S. Pat. No. 6,124,857, to Itoh, T., Inoue, K., Yamada, A., and Shimada, K., Meshing Method and Apparatus, 2000.
Other References Cited in this Specification
Bentley, J. L., and Friedman, J. H., Data Structures for Range Searching, Computing Surveys, vol. 11, no. 4, 1979.
Bern, M., and Eppstein, D., Mesh Generation and Optimal Triangulation, in Computing in Euclidean Geometry, Du, D. -Z. and Hwang., F. K. eds., World Scientific, 1995.
Bossen, F. J., and Heckbert, P. S., A Pliant Method for Anisotropic Mesh Generation, Proceedings of the 5th International Meshing Roundtable, p. 63-74, Sandia, 1996.
Byrd, R. H., Nocedal, J., and Schnabel, R. B., Representations of Quasi-Newton Matrices and Their Use in Limited Memory Methods, Technical Report NAM-03, Northwestern University, Department of Electrical Engineering and Computer Science, 1996.
Cebral, J. R., and Löhner, R., From Medical Images to CFD Meshes, Proceedings of the 8th International Meshing Roundtable, p. 321-331, Sandia, 1999.
Garrett, S., Griesbach, S., Johnson, D., Jones, D., Lo, M., Orr, W., and Sword, C., Earth Model Synthesis, First Break, v. 15, no. 1, p. 13-20, 199
Ahmed Samir
Bali Vikkram
Hood Jeffrey C.
Landmark Graphics Corporation
Meyertons Hood Kivlin Kowert & Goetzel P.C.
LandOfFree
Method for aligning a lattice of points in response to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for aligning a lattice of points in response to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for aligning a lattice of points in response to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3171575