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
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.