Abstract
A novel method is proposed for performing multi-label, semi-automated image segmentation. Given a small number of pixels with user-defined labels, one can analytically (and quickly) determine the probability that a random walker starting at each unlabeled pixel will first reach one of the pre-labeled pixels. By assigning each pixel to the label for which the greatest probability is calculated, a high-quality image segmentation may be obtained. Theoretical properties of this algorithm are developed along with the corresponding connections to discrete potential theory and electrical circuits. This algorithm is formulated in discrete space (i.e., on a graph) using combinatorial analogues of standard operators and principles from continuous potential theory, allowing it to be applied in arbitrary dimension.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Wallace, R., Ong, P.W., Schwartz, E.: Space variant image processing. International Journal of Computer Vision 13, 71–90 (1994)
Grady, L.: Space-Variant Computer Vision: A Graph-Theoretic Approach. PhD thesis, Boston University, Boston, MA (2004)
Kakutani, S.: Markov processes and the Dirichlet problem. Proc. Jap. Acad. 21, 227–233 (1945)
Doyle, P., Snell, L.: Random walks and electric networks, 22 in Carus mathematical monographs. Mathematical Association of America, Washington, D.C. (1984)
Courant, R., Hilbert, D.: Methods of Mathematical Physics, vol. 2. John Wiley and Sons, Chichester (1989)
Biggs, N.: Algebraic Graph Theory in Cambridge Tracts in Mathematics, vol. 67. Cambridge University Press, Cambridge (1974)
Simon, H.D., Teng, S.H.: How good is recursive bisection? SIAM Journal of Scientific Computing 18, 1436–1445 (1997)
Chan, P.K., Schlag, M.D.F., Zien, J.Y.: Spectral k-way ratio-cut partitioning and clustering. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems 13, 1088–1096 (1994)
Alpert, C.J., Yao, S.Z.: Spectral partitioning: the more eigenvectors, the better. In: Proceedings of the 32nd ACM/IEEE conference on Design automation conference, ACM/IEEE, pp. 195–200. ACM Press, New York (1995)
Zhu, S.C., Yuille, A.: Region competition: Unifying snakes, region growing, and Bayes/MDL for multiband image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 18, 884–900 (1996)
Yu, S.X., Shi, J.: Multiclass spectral clustering. In: Ninth IEEE International Conference on Computer Vision, International Conference on Computer Vision, vol. 1, pp. 313–319. IEEE Computer Society, Los Alamitos (2003)
Bar-Hillel, A., Weinshall, D.: Learning with equivalence constraints and the relation to multiclass learning. In: 16th Conference on Learning Theory, Washington DC, pp. 640–654 (2003)
Boykov, Y., Jolly, M.P.: Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images. In: International Conference on Computer Vision, vol. I, pp. 105–112 (2001)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence 23, 1222–1239 (2001)
Zhu, X., Lafferty, J., Ghahramani, Z.: Combining active learning and semisupervised learning using gaussian fields and harmonic functions. In: Proceedings of the ICML 2003 workshop on The Continuum from Labeled to Unlabel Data in Machine Learning and Data Mining, pp. 58–65 (2003)
Meilă, M., Shi, J.: Learning segmentation by random walks. In: Advances in Neural Information Processing Systems. 13, 873–879 (2000)
Boykov, Y., Veksler, O., Zabih, R.: A new algorithm for energy minimization with discontinuities. In: Pelillo-M., H.E.R. (ed.) Energy Minimization Methods in Computer Vision and Pattern Recognition. Second International Workshop, EMMCVPR 1999, York, UK, July 26-29, pp. 205–220 (1999)
Harary, F.: Graph Theory. Addison-Wesley, Reading (1994)
Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 888–905 (2000)
Biggs, N.: Algebraic potential theory on graphs. Bulletin of London Mathematics Society 29, 641–682 (1997)
Grady, L., Schwartz, E.: Anisotropic interpolation on graphs: The combinatorial Dirichlet problem. Technical Report CAS/CNS-TR-03-014, Department of Cognitive and Neural Systems, Boston University, Boston, MA (2003)
Merris, R.: Laplacian matrices of graphs: A survey. Linear Algebra and its Applications 197,198, 143–176 (1994)
Fiedler, M.: Special matrices and their applications in numerical mathematics. Martinus Nijhoff Publishers (1986)
Feller, W.: An Introduction to Probability Theory and its Applications, 2nd edn., vol. II. John Wiley and Sons, Inc., Chichester (1971)
Kirchhoff, G.: Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer ströme geführt wird. Poggendorf’s Annalen der Physik Chemie 72, 497–508 (1847)
Chen, W.K.: Applied Graph Theory: Graphs and Electrical Networks. Applied Mathematics and Mechanics, 2nd edn. North-Holland Publishing Company, Amsterdam (1976)
Golub, G., Van Loan, C.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, MD (1996)
Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes in C: The Art of Scientific Computing, 2nd edn. Cambridge University Press, Cambridge (2002)
Hackbusch, W.: Iterative Solution of Large Sparse Systems of Equations. Springer, Heidelberg (1994)
Dongarra, J.J., Duff, I.S., Sorenson, D.C., van der Vorst, H.A.: Solving Linear Systems on Vector and Shared Memory Computers. Society for Industrial and Applied Mathematics, Philadelphia (1991)
Gremban, K.: Combinatorial preconditioners for sparse, symmetric diagonally dominant linear systems. PhD thesis, Carnegie Mellon University, Pittsburgh, PA (1996)
Shapira, Y.: Matrix-Based Multigrid: Theory and Applications. Numerical Methods and Algorithms, vol. 2. Kluwer Academic Publishers, Dordrecht (2003)
Dendy, J.E.: Black box multigrid. Journal of Computational Physics 48, 366–386 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Grady, L., Funka-Lea, G. (2004). Multi-label Image Segmentation for Medical Applications Based on Graph-Theoretic Electrical Potentials. In: Sonka, M., Kakadiaris, I.A., Kybic, J. (eds) Computer Vision and Mathematical Methods in Medical and Biomedical Image Analysis. MMBIA CVAMIA 2004 2004. Lecture Notes in Computer Science, vol 3117. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27816-0_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-27816-0_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22675-8
Online ISBN: 978-3-540-27816-0
eBook Packages: Springer Book Archive