Projects:ProstateSegmentation

From NAMIC Wiki
Revision as of 18:55, 25 June 2008 by Melonakos (talk | contribs)
Jump to: navigation, search
Home < Projects:ProstateSegmentation
Back to Georgia Tech Algorithms

Prostate Segmentation

The objective is to extract the prostate from a 3D ultrasound data set.

Description

Two ways are employed to attack the problem. The first way is a combination of Cellular Automata(CA also called Grow Cut) with Geodesic Active Contour(GAC) methods. While the second is using a ellipsoid to match the prostate in 3D image. The details are given below.

Random Walks for prostate segmentation

Overview

The algorithm starts with a few initial seeds marking object and background. Then to decide the category of each of the other(non-seed) pixels, a random walker is released and it walks on the lattice of the image. The difficulty of walking from on pixel position to another is inversely related with the difference between the intensities of the two pixels. Given those settings, the probability of the random walker first hitting each kind of seeds are calculated. And the category of the pixel is assigned to the one with the greatest first hit probability.

Ideally, through this process the category of each pixel in the image could be decided.

Algorithm detail

The philosophy of random walk segmentation being stated above, it's practically impossible to implement that way. (Say, releasing many random walkers at each pixel and get the first hit probability using Monte-Carlo method.)

An analogy between first hit probability of random walks and the electrical potential distribution on a circuit network was given in the middle of last century. The resistance(conductance) in the circuit network is analogous to the crossing difficulty in the random walking scenario. Through the analogy the problem could be converted to a Dirichlet problem: [math] \triangle u = 0[/math] with boundary conditions: [math]u = 1 for object seeds[/math] [math]u = 0 for background seeds[/math]

In the above equation the [math]\triangle [/math] is a Laplace-Beltrami operator where the spatial variant resistance is considered to be metric of the space.

Cellular Automata and Geodesic Active Contour.

Cellular Automata incorporate the manual initialization to overcome the weak boundary and inhomogeneity in the object or the background. Its result is fed in for the Geodesic Active Contour method for fine tune.

Cellular Automata

Image segmentation using CA algorithm was proposed by V Vezhnevets and V Konouchine, in "Grow-Cut" - Interactive Multi-Label N-D Image Segmentation. Graphicon, 2005. The algorithm starts from an initialization where two patches in foreground and background, respectively, are picked by hand. Then algorithm iteratively determine the category of each pixel/voxel in the image.

Definition of Cellular Automaton for segmentation.

A Cellular Automaton is a pixel/voxel in image consisting three state variables: Label, Strength and Feature. Thus as in the scenario of segmentation, the Label is the category the pixel belongs to, the Strength describes how confident is this automaton belonging to current category while the Feature is its intensity. Graphically, we use a cartoon to depict one automaton as in the picture:

CA anAutomaton.png

Initialization of CA.

The algorithm needs some seed points in the object and background. The initialization doesn't have to be close to the boundary. Usually just two strokes in and outside of object is enough. We initialize the background region by drawing a square enclosing the whole object thus those outside are background. And we initialize the foreground by drawing a triangle inside the object. Thus, the Label of each cellular automaton in the manually drawn foreground and background is set to there corresponding value while the Strength of each automaton is set to 1 indicating we have 100% confidence of its category. However, there are regions belonging neither to the foreground and background. The Label and Strength of the automata in those regions are set to undecided and 0, respectively. And it is those we are going to decide in the subsequent steps. Before describing that process, we give an image illustrating the initialization step in below.

CA initialization.png

Attacking stage of CA and convergence.

Each automaton is "attacked" by its neighbors who has been assigned to a different Label. By "attack" we mean if the product of two factors is high enough, then the current automaton will take the Label of that neighbor. One of the two factors is the difference of features of the two automaton, the other is the attacker's current Strength.

Geodesic Active Contour

2 CA algorithm does not deal with smoothness directly. A GAC step is employed, for one purpose, to smooth the result given by CA and for the other to fine tune the contour.

3 Both algorithms are implemented in 3D. A ITK-Cellular Automata filter, handling N-D data, has already been completed and submitted into the NA-MIC SandBox.

Ellipsoid Matching

Prostate is usually modeled as an ellipsoid . Also, with no control of the global shape, the algorithm is highly influenced by noise and incomplete image information like weak boundary. A shape prior would be used to deal with such situations. However, firstly the prior is learned from a sufficient number of training data, which may not be available. Secondly the shapes need to be aligned in order to be learned or applied in segmentation. However for prostate which is mostly an ellipsoid in shape, there's not much prominent shape feature to drive the alignment and segmentation.

So we are trying to first model the prostate using an ellipsoid. With that global constrain of shape, extraction it from image would be more robust. Secondly, if the prostate is well captured by an ellipsoid, then starting from there more local method would be used to capture the detail feature of the organ.

This way of attacking is under developing and some result would be available before the Core 1 meeting in late May.

Key Investigators

  • Georgia Tech Algorithms: Yi Gao, Allen Tannenbaum

Publications