Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1997-12-17
2001-03-13
Vo, Cliff N. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S423000
Reexamination Certificate
active
06201543
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer modeling and more particularly to an implementation of a three dimensional hybrid model to aid in initiating and fitting the hybrid model to two dimensional segmentations to form an improved three dimensional model fit.
2. Description of Related Art
Branching cylindrical structures appear in as diverse embodiments as plant roots, industrial pipelines and coral reefs. However, by far the most studied instances are those in the human body. Vascular or bronchial complexes may be imaged by volumetric techniques such as CT and magnetic resonance (MR). Recovery of these structures facilitates surgical path planning, quantification of prosthetic stent dimensions, and the detection of aneurysms, stenoses and tumors.
A proposed method segments objects from 3D images using a 3D deformable surface which was made up of a series of 2D planar curves. However, the model proposed was not cohesive in terms of being “global” or “parametric”. In addition, the 2D planar curves were not recovered via optimal active contours (“optimal” meaning that the energy function describing the contour had been globally minimized). Instead the proposed method employed snakes and relied on balloon forces to explore crevices. The problem with balloon forces is that the snake might leak where the image boundaries are not well defined. 2D deformable surfaces have also been applied to segmentation but the approaches have not been “optimal”. For 1D contours, optimality is a well understood concept. How this concept might be extended to 2D surfaces still presents difficulty.
Direct application of 3D hybrid models to 3D image volumes has also met with mixed success since the model's overall topology is constrained by the underlying parametric component. Again, describing deep crevices becomes a problem. Some proposed methods fit parallel sets of 2D contours to recover a 3D object. Once the fit is settled they repeat the process from an orthogonal direction using the results of the previous iteration as a starting point. However, they employ balloon forces to fit the 2D contours and their result is not a coherent parametric model. In addition, they demonstrate their method on relatively simple synthetic shapes. Region growing techniques may be used for segmentation. However, while they are often effective they suffer from bleeding in areas where the object boundary is not well defined. In addition, they do not result in a geometric description of the object, rather a collection of voxels.
Segmentation via the propagation of 2D active contours (i.e., using the result from a previous slice as the starting point for a segmentation of the current slice) may be problematic. A change in object's circumference in a slice might be due to a change in the radius of the object under recovery, or it might be a change in direction of the path taken by the object in space. Determining if a change in circumference or direction has occurred is essential for selecting an appropriate starting point for segmentation in the slices to follow. A change in circumference may indicate the initiation of a change in the topology of the object such as a bifurcation. For example, an aortic arch includes all three which occur simultaneously. Two dimensional active contours lack the global properties to account for these instances.
Active contours were first proposed under the name of snakes. Snakes are defined as contours that are pushed or pulled towards image features by constraining forces. A typical energy function for a snake is expressed as:
E=∫{&agr;|
u
s
(
s
)|
2
+&bgr;|u
s
s
(
s
)|
2
−&lgr;|∇I|
2
}ds
where the first two terms measure the smoothness of the contour (in terms of the first and second derivatives of the contour) and the third term measures the amount of edge strength in the image along the contour. It is desirable to minimize this energy function to find a contour which is both smooth and which coincides with high gradient magnitude points in the image. This energy is often minimized using Euler equations and gradient descent. The disadvantage of this technique and many of the subsequently proposed algorithms is that, since the minimization is based on gradient descent, it is not guaranteed to locate the global minimum of the energy function. As a result, neighboring edges can be very distracting to the process and depending on the initial configuration, different local minima of the energy function might be reached.
Graph search algorithms have been used in the past to look for the global minimum of the active contour's energy function. An image is represented as a graph by defining a node for each pixel and creating an arc between two nodes if the two corresponding pixels are connected. The energy function of the discrete contour is defined as:
E
=
∑
k
=
1
n
1
&LeftBracketingBar;
∇
I
&RightBracketingBar;
2
(
P
k
)
+
ϵ
+
μ
∑
k
=
1
n
-
1
&LeftBracketingBar;
∇
→
I
(
P
k
)
-
∇
→
I
(
P
k
+
1
)
&RightBracketingBar;
where the P
k
's are the points on the contour,
|∇I|
is the gradient magnitude and
{right arrow over (∇)}I
denotes the gradient direction. The energy function combines gradient magnitude and curvature information. The coefficient &mgr; balances the importance between the two components.
An important result of graph theory states that a dynamic programming approach for finding shortest paths in a graph can be replaced by Dijkstra's algorithm under the condition that all the edge costs are positive. To apply Dijkstra's algorithm to images, an image should be viewed as a graph where the nodes correspond to pixels and an edge is defined as a bridge between two neighboring pixels. At initialization, the cost for all nodes is set to be infinite and all the nodes are marked as unvisited. In addition, the cost at a finite set of source points is set to 0. A heap containing all the finite cost nodes which is ordered in terms of increasing cost is constructed and is maintained throughout the procedure. At each iteration, the node (i,j) with the best cost is retrieved from the heap. The cost at the neighboring pixels (k,l) is then updated by determining if there is now a shorter path from the source to (k,l) going through (i,j):
E(
k,l
)=min {E(
k,l
), E(
i,j
)+
e
(
i,j,k,l
)}
where
e
(
i
,
j
,
k
,
l
)
=
1
&LeftBracketingBar;
∇
I
&RightBracketingBar;
2
(
k
,
l
)
+
ϵ
+
μ
&LeftBracketingBar;
∇
→
I
(
i
,
j
)
-
∇
→
I
(
k
,
l
)
These steps are repeated until the heap is empty and all the nodes have been explored. In addition, at every node, the algorithm keeps track of the previous node on the shortest path. This way, the algorithm can simply backtrack down the list from the sink points to recover the optimal contour.
A physically-motivated recovery can be analogized to physical systems, independent coefficients for scaling data forces and material forces (e.g., smoothing) are used. Scaling data forces without regard to the material forces may cause instability in fitting, however. Tractable convergence requires an appropriate scaling of the forces, or alternatively an appropriate selection of time step or euler coefficient. Many methods do not address how to choose these values. An intuitive, practical implementation of quantities such as force coefficients which guarantee quick recovery with stability have been lacking in other proposed methods. This approach would advantageously lead to the assignment of unit values to time step and euler coefficients, thus increasing the generality of the physically-motivated scheme.
Hybrid models are powerful tools. They simultaneously provide a gross parametric as well as a detailed description of an object. It is difficult, however, to directly employ hybrid models in
Gupta Alok
Jolly Marie Pierre
O'Donnell Thomas
Paschburg Donald B.
Siemens Corporate Research Inc.
Vo Cliff N.
LandOfFree
Framework for segmentation of cylindrical structures using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Framework for segmentation of cylindrical structures using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Framework for segmentation of cylindrical structures using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2516850