Interactive Segmentation with Graph-Cuts
Resistor-Network is equivalent to a weighted Graph.
© dkfz.de
The image is interpreted as a graph G=(V,E), V are the image voxels and E is a set of edges connecting neighboring voxels. The identification of certain vertices as labels is used to partition the graph and hence the image into different regions corresponding to an optimal graph-cut. These regions correspond to the final segmentation of the image. For the partition of the The Random-Walk algorithm [1,2] is a graph-cut approach to interactive image segmentation. With the help of user defined labels several structures in medical images can be segmented at the same time. The segmentation is equivalent to the solution of a system of linear equations. The remaining (non-label) vertices are grouped according to the Random-Walker theory. A vertex belongs to a certain label if the probability of a random walk is highest to arrive at one of those vertices belonging to this label. This problem can be solved analytically. The resulting system of linear equations is equivalent to the inversion problem of a symmetric, sparse matrix.
In graph theory these edges can have weights attached to them. For this algorithm the weight wij connecting the Voxel i and j with i, j in V is calculated with a Gaussian weighting function, i. e.:
wij = exp (-ß(gj - gi)2)
where gi, gj are the gray values of the voxels i and j. The parameterbregularizes the influence of the image data on the weighting factor.
Picture with three different Labels (left). Segmentation result (right).
© dkfz.de
Model-based Segmentation with Active Contour Models
Another interactive segmentation tool is based on the T-snakes approach [3,4]. Snakes can be compared to balloon blown up inside a mould. In image processing the mould corresponds to the edges and the elastic properties of the balloon to contour/surface properties of an expanding closed contour/surface. A segmentation is realized when image forces and surface forces are balanced.
Segmentation with snakes is interpreted as an optimization of an energy functional including terms for image features and contour properties. The Segmentation starts with an initial two or three dimensional contour template which allows for locally defined segmentation parameters. Segmentation is an iterative optimization using gradient descent. The T-snakes approach was extended by calculating the image features separately for the x- and y-direction leading to a better point distribution on the contour. This results in more accurate segmentation results and better preservation of the topology of the points during segmentation. A reparameterization of the contour during segmentation ensures the topological adaption of the contour to the image data and a uniform distribution of the points on the surface. The final segmentation result can be influenced by user-defined weighting of smoothness of the contour and its alignment to edges in the image data.
The method was tested on CT scans of the prostate region with special emphasis on the segmentation of the bladder. The segmentation tool was evaluated with respect to its accuracy and efficiency. The results show that the algorithm is capable of separating the bladder from the prostate and that it can cope with moderate image artifacts. The efficiency of the algorithm can be described by the time it takes to segment an organ at risk. With the implemented approch a bladder can be segmented within three seconds on a standard PC (3 GHz) and a 3D cylindric template as initial contour.
Initial Contours for the 3D segmentation (left). Intermediate segmentation step. Final segmentation result (right)
© dkfz.de
Shape-based Segmentation
An extension to the segmentation with Active Contour Models are Active Shape Models [5]. First a template model is generated from a training data set. The template model is the surface of a segmentation. It is then divided into a certain number of patches. The division is performed according to the curvature of the contour. Points with similar curvature are grouped together. During the segmetation process the patches are adapted to the image data independently. After all patches are adapted, the final contour is generated by interpolation. The resulting algorithm is a template based approach for the segmention of organs at risk. This way the robustness of the underlying ACM approach is improved and the difficult training of a Point Distribution Model PDM is avoided.
Intermediate segmentation step (left). Final segmentation result (right).
© dkfz.de
References
[1] Grady L, Gareth Funka-Lea. Multi-Label Image Segmentation for Medical Applications Based on Graph-Theoretic Electrical Potentials. In: Proceedings of the 8th ECCV04, Workshop on Computer Vision Approaches to Medical Image Analysis and Mathematical Methods in Biomedical Image Analysis, p. 230-245, May 15th, 2004, Prague, Czech Republic, Springer-Verlag.
[2] Grady L, Schwartz EL. Isoperimetric graph partitioning for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 2006;28(3):469–475.
[3] Kass M, Witkin A, Terzopoulos D: Snakes: Active Contour Models. Int J Comput Vis 1(4):321–331, 1988.
[4] McInerney T, Terzopoulos D: T-snakes: Topology adaptive snakes. Med Image Anal 4(2):73–91, 2000.
[5] Cootes TF, Taylor CJ: Statistical models of appearance for medical image analysis and computer vision. Proc SPIE Med Img: 236–248, 2001.