Segmentation of 3D medical structures using robust ray propagation

[0001] The present application claims priority to U.S. Provisional Patent Application Ser. No. 60/373,684, filed Apr. 18, 2002, which is hereby incorporated by reference.

[0002] 1. Field of the Invention

[0003] The present invention relates generally to computer vision and imaging systems, and more particularly, to a system and method for segmentation of 3D medical structures, e.g., organs, aneurysms and brain tumors, using robust ray propagation.

[0004] 2. Description of the Related Art

[0005] The segmentation of three-dimensional (3D) structures in CT (computerized tomography) and MR (magnetic resonance) images is an inherently difficult and time consuming problem. The accurate localization of object surfaces is influenced by the presence of significant noise levels, generated through partial-volume effects and by image acquisition devices. In addition, the processing in 3D space implies an increased computational complexity, which makes impractical the 3D extension of most two-dimensional (2D) segmentation algorithms.

[0006] Deformable models have been popular for segmentation of 3D medical images. These approaches can produce good segmentation results if the initialization is done properly. In general, deformable models work well if they are initialized close to object boundaries and if they are almost symmetrically away from boundaries. However, such initialization of deformable models is typically a difficult task because a 3D model must be created inside 3D data by using a 2D display device. In addition, the current deformable model approaches are computationally expensive. This is due to the additional dimension in the case of level set methods, or expensive reinitialization of parameters in the case of explicit surface evolution techniques.

[0007] A robust and efficient method for segmentation of 3D structures in CT and MR images is provided. The method is based on 3D ray propagation by mean-shift analysis with a smoothness constraint. Ray propagation is used to guide an evolving surface due to its computational efficiency. In addition, non-parametric analysis and shape priors are incorporated to the method for robust convergence.

[0008] According to one aspect of the present invention, a method for segmenting structures from three-dimensional (3D) images is provided. The method including the steps of receiving 3D image data; visualizing the 3D image data on a display device; selecting a structure in the 3D image data by placing a seed in the structure; initializing a plurality of rays from the seed to form a surface; determining a speed function of each of the plurality of rays; evolving the surface by propagating the plurality of rays based on the speed function of each of the plurality of rays; converging the plurality of rays on a boundary of the structure; and segmenting the structure when all of the plurality of rays have converged on the structure's boundary. The method further includes the step of determining a volume of the segmented structure.

[0009] According to another aspect of the invention, the evolving the surface step of the method includes performing a mean-shift analysis on each of the plurality of rays to identify image discontinuities, the image discontinuities defining the structure's boundary. Furthermore, the performing a mean-shift analysis includes the steps of determining a joint spatial-intensity domain for each of the plurality of rays, the joint spatial-intensity domain including for each pixel along each of the plurality of rays at least one location value and at least one intensity value; partitioning the domain to identify the discontinuities based on a probability density; and determining a displacement vector for each of the plurality of rays, the displacement vector being a spatial distance between a point on an individual ray and a discontinuity on the individual ray, wherein if the displacement vector of the individual ray is greater than a predetermined value, the speed of the individual ray is increased, and if the displacement vector of the individual ray is less than the predetermined value, the speed of the individual ray is decreased.

[0010] According to an additional aspect of the invention, the evolving the surface step of the method includes applying a smoothness constraint to the evolving surface. The applying a smoothness constraint includes filtering the speed function of an individual ray of the plurality of rays based on a neighboring ray and imposing a mean curvature on the evolving surface based on shape priors.

[0011] According to a further aspect of the present invention, a program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for segmenting structures from three-dimensional (3D) images includes the method steps of receiving 3D image data; visualizing the 3D image data on a display device; selecting a structure in the 3D image data by placing a seed in the structure; initializing a plurality of rays from the seed to form a surface; determining a speed function of each of the plurality of rays; evolving the surface by propagating the plurality of rays based on the speed function of each of the plurality of rays; converging the plurality of rays on a boundary of the structure; and segmenting the structure when all of the plurality of rays have converged on the structure's boundary.

[0012] According to still another aspect of the invention, a system for segmenting structures from three-dimensional (3D) images is provided. The system includes an input device for receiving 3D image data; a display device for visualizing the 3D image data; a cursor control device for selecting a structure in the 3D image data by placing a seed in the structure; and a processor for segmenting the structure from the 3D image data. The processor initializes a plurality of rays from the seed to form a surface, determines a speed function of each of the plurality of rays, evolves the surface by propagating the plurality of rays based on the speed function of each of the plurality of rays, converges the plurality of rays on a boundary of the structure, and segments the structure when all of the plurality of rays have converged on the structure's boundary. Furthermore, the cursor control device is a mouse and a user places the seed in the structure by clicking on the structure.

[0017] Preferred embodiments of the present invention will be described hereinbelow with reference to the accompanying drawings. In the following description, well-known functions or constructions are not described in detail to avoid obscuring the invention in unnecessary detail.

[0018] The present invention provides an efficient, robust, and user-friendly method for the interactive segmentation of 3D medical structures, e.g., aneurysms, from contrast enhanced CT or MR data. The primary innovation of the method is the boundary propagation by mean-shift analysis combined with a smoothness constraint. As a result, the method of the present invention is robust to both (1) outliers in the data and (2) missing data structures, e.g., surfaces that are not well defined or missing. The first property is guaranteed by a mean-shift procedure, while the second is obtained through the use of a priori information on boundary smoothness. Furthermore, due to the method's computationally efficient framework based on ray propagation, the entire process is fast, allowing real-time user interaction (under 10 seconds on a Penthium III 1 Ghz computer platform).

[0019] FIG. 1 summarizes a visualization of the method of the present invention. FIG. 1(a) illustrates an original Contrast Enhanced CTA (CE-CTA) image in multi-planar reformats (MPRs) and volume rendering. This data set contains an aneurysm which is indicated by an arrow. In addition, MPRs (orthogonal views) are centered on this pathology. A system embodying the method of the present invention allows a radiologist to quickly detect pathologies from different visualizations. The next step is the quantification of these pathologies. The goal of this method is to provide a mechanism such that a user can quickly measure the volume of blob-like structures by simply clicking on them. In this example, the user clicks on the area of interest, e.g., the aneurysm, and the 3D ray propagation algorithm detects the boundary of the structure and computes its volume. FIG. 1(b) illustrates the detected aneurysm (lumen boundary) blended with the original data and FIG. 1(c) illustrates the segmented aneurysm (lumen boundary).

[0020] The invention is particularly illustrated with reference to data generated by an X-ray computed tomography processes, but can likewise be applied to any other medical 3D image data, including data generated by magnetic resonance imaging (NRI), positron emission tomography, ultrasound imaging, etc.

[0021] It is to be understood that the present invention may be implemented in various forms of hardware, software, firmware, special purpose processors, or a combination thereof. In one embodiment, the present invention may be implemented in software as an application program tangibly embodied on a program storage device. The application program may be uploaded to, and executed by, a machine comprising any suitable architecture such as that shown in FIG. 2. Preferably, the machine 200 is implemented on a computer platform having hardware such as one or more central processing units (CPU) 202, a random access memory (RAM) 204, a read only memory (ROM) 206 and input/output (I/O) interface(s) such as keyboard 208, cursor control device (e.g., a mouse) 210 and display device 212. The computer platform also includes an operating system and micro instruction code. The various processes and functions described herein may either be part of the micro instruction code or part of the application program (or a combination thereof) which is executed via the operating system. In addition, various other peripheral devices may be connected to the computer platform such as an additional data storage device 214 and a printing device. Furthermore, a scanner device 216, for example an X-ray machine or MRI machine, may be coupled to the machine 200 for collecting image data.

[0022] It is to be further understood that, because some of the constituent system components and method steps depicted in the accompanying figures may be implemented in software, the actual connections between the system components (or the process steps) may differ depending upon the manner in which the present invention is programmed. Given the teachings of the present invention provided herein, one of ordinary skill in the related art will be able to contemplate these and similar implementations or configurations of the present invention.

[0023] Referring to FIG. 3, a method for segmenting 3D medical structures is presented. Initially, 3D image data is collected (Step 302) by the various means described above, e.g., X-rays, MRI, etc. Once the 3D image data has been received, the 3D image data is visualized via multi-planar reformats (MPRs) and volume rendering (Step 304), as illustrated in FIG. 1(a), on a display device such as a monitor. Within the segmentation method of the present invention, a user specifies a structure to be segmented by placing a single seed inside it, e.g., by clicking on the medical structure with a mouse or any other known cursor control device (Step 306). A boundary surface is then automatically generated via propagation of rays from the seed point (Step 308).

[0024] The propagation is guided by image forces defined through mean-shift analysis (Step 312) and smoothness constraints (Step 310). The gradient-ascent mean-shift localizes edges of the structure accurately in the presence of noise and provides good computational performance, being based on local operators, i.e., operators that use information only from its small neighborhood in computations, thus avoiding extensive computations if a quantity is computed several times for each voxel. Preferably, the method employs a mean curvature for the smoothness constraint, however, other geometric smoothing techniques, such as the mean-Gaussian curvature, as is known in the art, can be applied. The smoothness constraint process (Step 310) is influenced by a priori knowledge of medical structures (Step 314).

[0025] The boundary surface is evolved by updating the speed function of each of the rays (Step 316) as described above, i.e., by mean-shift analysis and applying smoothness constraints (Step 310). The surface is evolved until all the rays converge on the boundary surface of the structure to be segmented (Step 318). Otherwise, new rays are initialized and propagated to the boundary surface (Step 322). Once all the rays have converged, the structure is defined and can be segmented from the original 3D image data (Step 320). Additionally, once the structure has been segmented, physical dimensions of the structure and its volume can be determined.

[0026] The development of the method of the present invention will now be described below in detail.

• [0027] 1. Deformable Surfaces for 3D Volume Segmentation

[0028] Deformable model-based segmentation algorithms can be divided into explicit methods and implicit methods based on how the deformable surface is represented. In explicit methods, deformable surfaces are represented by triangular mashes, superquadrics, and other complex shapes. In implicit methods, the popular choice for deformable surface representation is the level set method. Level set methods have been popular because they are topologically flexible and can represent complex shapes without any computationally expensive reparametrization step. One of the main shortcomings of level set methods is the computational complexity due to the additional embedded surface requirement for simulations. To overcome the complexity, narrow band level set evolutions have been proposed. However, these methods are still not fast enough for real-time volume segmentation. Similarly, fast marching methods have been proposed for simulating the monotonically advancing front, e.g., a surface. This fast marching method does not require any additional surface, but it is limited to simulate one directional flows, i.e., no curvature smoothing, thus its use in segmentation is rather limited. Thus, the method of the present invention employs ray propagation for fast image segmentation.

• [0029] 1.1 Ray Propogation

[0030] Let the front be represented by a 3D surface ψ(ξ, η, t)=(x(ξ,η, t),y(ξ,η,t),z(ξ,η,t)) where x,y and z are the Cartesian coordinates, ξ, η parameterize the surface and t is time. The front evolution is governed by $\begin{array}{cc}\{\begin{array}{c}\frac{\partial \psi \left(s,t\right)}{\partial t}=S\left(x,y,z\right)N\\ \psi \left(\xi ,\eta ,0\right)={\psi }_0\left(\xi ,\eta \right)\end{array}& \left(1\right)\end{array}$
where ψ₀(ξ,η)=(x(ξ,η,0),y(ξ,η,0),z(ξ,η,0)) is the initial surface, and N is the unit normal vector and S(x,y,z) is the speed of a ray at point (x,y,z).

[0031] The method of the present invention is based on explicit front propagation via normal vectors. The contour is sampled and the evolution of each sample is followed in time by rewriting the Eikonal equation in vector form, namely, $\begin{array}{cc}\{\begin{array}{c}{x}_t=S\left(x,y,z\right)\frac{N_x}{N}\\ y_t=S\left(x,y,z\right)\frac{N_y}{N}\\ z_t=S\left(x,y,z\right)\frac{N_z}{N}\end{array}& \left(2\right)\end{array}$
This evolution is the Lagrangian solution since the physical coordinate system moves with the propagating wavefront.

[0032] In general, the applications of ray propagation for surface evolution have been limited. Since the normals to the wavefront may collide (formation of shocks), this approach exhibits numerical instabilities due to an accumulated density of sample points, thus requiring special care, such as reparametrization of the wavefront. Also, topological changes are not handled naturally, an external procedure being required.

[0033] The method of the present invention employs ray propagation from a single point source for the segmentation of blob-like structures found in medical images, such as aneurysm and brain tumors. In fact, ray propagation is well suited since it is very fast, no topological changes are necessary and no shocks form during the propagation, and rays from a single source point do not collide with each other.

[0034] Observe that the speed function S(x,y,z) plays an important role in the quality of the segmentation results. In the method of the present invention, the speed of rays, S(x,y,z), depends on image information and shape priors. Specifically, the method uses
S(x,y,z)=S₀(x,y,z)+S₁(x,y,z)   (3)
where S₀(x,y,z) measures image discontinuities, S₁(x,y,z) represents shape priors, and a constant, , balances these two terms where β ranges from 0 for no smoothing to 1 for a large amount of smoothing.

• [0035] 1.2 Robust Measure of Discontinuities: Mean-Shift Analysis

[0036] Traditionally, image gradients are used to guide deformable models to object boundaries. However, the image gradient is not robust to noise, and outliers in the data can significantly influence the result. A solution to this problem is to use robust measures of discontinuities.

[0037] The method of the present invention is based on a representation of image data which uses kernel density estimation as disclosed in D. Comaniciu, P. Meer: “Mean Shift: A Robust Approach toward Feature Space Analysis”, IEEE Trans. Pattern Analysis Machine Intell., Vol. 24, No. 5, 603–619, 2002, the contents of which are incorporated by reference. Consider a 1-dimensional intensity profile, e.g., a ray, obtained from a gray level image. Each pixel along the ray is characterized by a location x and an intensity value I. As a result, an input ray of N pixels is represented as a collection of 2-dimensional points {x_i, I_i}i=1, . . . ,N. The 2-dimensional space constructed is called the joint spatial-intensity domain. Note that this construction generalizes for standard gray-level image data (3-dimensional space with 2 dimensions for coordinates and one for intensity), color data (5-dimensional space with 2 dimensions for coordinates and three for color), multi-modal data, or image sequences.

[0038] The task of identifying image discontinuities reduces to the partitioning of the joint space according to the probability density estimated in this space. The number of segments, i.e., intervals in a density graph, is determined by the number of peaks (modes) of the underlying density. The iterative mean-shift procedure is used to find the modes in the joint space and assign each data point to a mode in its neighborhood. Denote by {x^*_i, I^*_i} the mode associated to {x_i, I_i} where i=1, . . . , N. Since the modes delineate regions with high concentration of similar data, the robustness to outliers is guaranteed.

[0039] Let {d_i=x^*_i−x_i}i=1, . . . , N be the oriented spatial distance from a point to its assigned mode. (Hereinafter, this quantity will be referred to as the displacement vector.) The displacement vectors always point away from discontinuities and play a dominant role in the propagation technique. The iterative, mean-shift-based algorithm for finding the displacement vectors is

[0040] For each i=1, . . . , N

• [0041] 1. Initialize k=1 and (x^k_i, I^k_i, d_i)=(x_i, I_i,0) where k is the discrete time, iteration number
• [0042] 2. Compute $\begin{array}{cc}\begin{array}{c}{X}_i^{k+1}=\frac{\sum _{j=1}^M{x}_j{e}^{\frac{-{\left(x_i^k-x_j\right)}^2}{2{\sigma }_x^2}e·\frac{-{\left(I_i^k-I_j\right)}^2}{2{\sigma }_I^2}}}{\sum _{j=1}^M{e}^{\frac{-{\left(x_i^k-x_j\right)}^2}{2{\sigma }_x^2}e\frac{-{\left(I_i^k-I_j\right)}^2}{2{\sigma }_I^2}}}\\ I_i^{k+1}=\frac{\sum _{j=1}^M{I}_j{e}^{\frac{-{\left(x_i^k-x_j\right)}^2}{2{\sigma }_x^2}e\frac{-{\left(I_i^k-I_j\right)}^2}{2{\sigma }_I^2}}}{\sum _{j=1}^M{e}^{\frac{-{\left(x_i^k-x_j\right)}^2}{2{\sigma }_x^2}e\frac{-{\left(I_i^k-I_j\right)}^2}{2{\sigma }_I^2}}}\end{array}& \left(4\right)\end{array}$
  until convergence.
• [0043] 3 Assign (x^*₁, I^*_i)=(x_i^k+1, I_i^k+1)
• [0044] 4. Assign d_i=(x^*_i, −x_i)
  wherein {circle around (9)}_x and {circle around (9)}_I are the bandwidths of Gaussian kernels in the spatial and intensity domain, respectively.

[0045] The first part of the speed term can be now defined by $\begin{array}{cc}{S}_o\left(x,y,z\right)=\frac{f\left(x,y,z\right)}{1.0+{\nabla d\left(x,y,z\right)}^2}.& \left(5\right)\end{array}$
The function d(x,y,z) is obtained by summarizing the information provided by the displacement vectors. For a given location along a ray, d(x,y,z) is positive when the corresponding displacement vector is pointing outbound and negative when the vector points towards the seed point. The term f(x,y,z) is given by $\begin{array}{cc}f\left(x,y,z\right)=\{\begin{array}{ccc}-\mathrm{sign}\left(d\left(x,y,z\right)\right)& \mathrm{if}& \nabla d\left(x,y,z\right)<\mathrm{threshold}\\ 1& & \mathrm{else}\end{array}& \left(6\right)\end{array}$
where the gradient of d(x,y,z), namely ∇d(x, y, z) is computed along the ray. If an absolute value of the gradient of the displacement vector of the individual ray is greater than a predetermined value and a sign of the displacement vector is negative, the individual ray is propagated from the seed to the boundary, and if the absolute value of the gradient of the displacement vector of the individual ray is greater than a predetermined value and the sign of the displacement vector is positive, the individual ray is propagated from outside the boundary toward the boundary. If an absolute value of a gradient of the displacement vector of the individual ray is less than a predetermined value, the individual ray is propagated from the seed to the boundary. In this formulation, rays propagate freely towards the object boundaries when they are away from them and slow down in the vicinity of boundaries. If a ray crosses over a boundary, it returns to the boundary. The parameter threshold is determined from statistical measures computed from the density function of displacement errors. It is assumed that locations of small gradients (less than threshold) in the displacement function are not part of any object.

• [0046] 1.3 Smoothness Constraints

[0047] Problems related to missing data, e.g., noise, data corruption, etc., are common in the segmentation of medical structures. A solution to missing data is to exploit a priori knowledge by imposing smoothness constraints on the evolving surface. We use two types of smoothness constrains in this method, one on the speed of neighboring rays, the other on the local curvature of the front.

[0048] Thus, the speed function S₀ (x,y,z) of a ray is filtered by employing the speed information in a neighborhood. In addition, the speed term, S₁ (x,y,z) imposes the smoothness of the front by employing the mean curvature given by $S_1\left(x,y,z\right)=\frac{K_1+K_2}{2}$
where K₁ and K₂ are the principal curvatures. However, other geometric smoothing techniques, such as the conventional Mean-Gaussian curvature can be used.

• [0049] 1.4 Implementation

[0050] For the initialization of rays, the method of the present invention uses an algorithm that provides an approximation to equidistant placement of points on a sphere by employing several subdivisions of an octahedron. The octahedron is initialized with the six points (1,0,0), (−1,0,0), (0,1,0), (0,−1,0) (0,0,1) and (0,0,−1) and connections between neighboring points give the first primitive triangulization of the unit sphere. In the subdivision process, each triangle is subdivided into four new ones by placing one new point on the middle of every edge, projecting it onto the unit sphere and connecting the neighboring points. Rays are then shot from the seed point along the direction given by this approximation of the unit sphere. Observe that in the initial propagations, a small number of rays are necessary. However, when the distance of rays from the seed point becomes large the distance between rays also becomes large, as well. This corresponds to each triangle occupying a larger region. In this implementation, when a triangle becomes greater than a predetermined size, i.e., the spatial distance between endpoints of two neighboring rays becomes greater than a predetermined size, it is again subdivided into four new ones by placing one new ray on the middle of every edge (i.e., initializing a new ray between the two neighboring rays), projecting it onto the unit sphere and connecting the neighboring points.

[0051] To estimate the surface curvature at the current position of a ray, the method uses the following algorithm: Compute the first matrix S $\begin{array}{cc}S=\left(\frac{1}{2N}\sum _{i=1}^N{n}_i{n}_i^t\right)+{\frac{1}{2}}^t& \left(7\right)\end{array}$
where N is the number of neighbors, n_i denotes the vector to the current position of the i-th neighbor and p is the vector to the current position of the ray in question. The positive definite matrix S is called structure tensor or scatter matrix. A principle component analysis provides the eigenvalues {circle around (9)}₁ μ {circle around (9)}₂ μ {circle around (9)}₃ and eigenvectors v₁, v₂, v₃ of S. The eigenvector v₁ corresponding to the largest eigenvalue {circle around (9)}₁ is in normal tangential direction. The other two eigenvectors point into the directions of the principal curvatures. Though the corresponding eigenvalues {circle around (9)}₂ and {circle around (9)}₃ already give an estimate of the degree of curvature in these directions, they do not give information of their orientation. Therefore, for every neighbor the method also calculates the dot product of the neighbor vector and the principal curvature vector. This coefficient is then multiplied with the difference of $\frac{\pi }{2}$
and the angle between the normal tangential vector v₁ and the vector connecting p and the neighbor. The sum over this weighted angle differences is positive for convex areas and negative for concave areas. Hence, the final formulas for principal curvatures are: $\begin{array}{cc}{K}_1=\sum _{i=1}^N\frac{v_2·n_i}{v_2n_i}\left(\arccos \left(\frac{v_i·\left(n_i-p\right)}{v_1n_i-p}\right)-\frac{\pi }{2}\right)& \left(8\right)\\ K_2=\sum _{i=1}^N\frac{v_3·n_i}{v_3n_i}\left(\arccos \left(\frac{v_i·\left(n_i-p\right)}{v_1n_i-p}\right)-\frac{\pi }{2}\right).& \left(9\right)\end{array}$
where K₁ is the minimum bending characteristic of the curvature and K₂ is the maximum bending characteristic of the curvature. K₁ and K₂ are then averaged to get the mean curvature.

[0052] The present invention provides a user-friendly 3D volume segmentation method. The segmentation method is very fast due to ray propagation. Second, the analysis based on mean-shift makes the method robust to outliers inherent in CT and MR images. Third, the use of shape priors, such as smoothness constraints, implies a reduced sensitivity of the method to missing data, i.e., surfaces that are not well defined or missing. Fourth, the method is user-friendly since one-click inside the 3D medical structure is often sufficient.

[0053] While the invention has been shown and described with reference to certain preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.