An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation
November 1993 (vol. 15 no. 11)
pp. 1101-1113
DOI Bookmark:
http://doi.ieeecomputersociety.org/10.1109/34.244673
A novel graph theoretic approach for data clustering is presented and its application to the image segmentation problem is demonstrated. The data to be clustered are represented by an undirected adjacency graph G with arc capacities assigned to reflect the similarity between the linked vertices. Clustering is achieved by removing arcs of G to form mutually exclusive subgraphs such that the largest inter-subgraph maximum flow is minimized. For graphs of moderate size ( approximately 2000 vertices), the optimal solution is obtained through partitioning a flow and cut equivalent tree of G, which can be efficiently constructed using the Gomory-Hu algorithm (1961). However for larger graphs this approach is impractical. New theorems for subgraph condensation are derived and are then used to develop a fast algorithm which hierarchically constructs and partitions a partially equivalent tree of much reduced size. This algorithm results in an optimal solution equivalent to that obtained by partitioning the complete equivalent tree and is able to handle very large graphs with several hundred thousand vertices. The new clustering algorithm is applied to the image segmentation problem. The segmentation is achieved by effectively searching for closed contours of edge elements (equivalent to minimum cuts in G), which consist mostly of strong edges, while rejecting contours containing isolated strong edges. This method is able to accurately locate region boundaries and at the same time guarantees the formation of closed edge contours. [1] A. K. Jain and R. C. Dubes,Algorithms for Clustering Data. Englewood Cliffs, NJ: Prentice-Hall, 1988.[2] R. O. Duda and P. E. Hart,Pattern Classification and Scene Analysis. New York: Wiley, 1973.[3] L. J. Hubert, "Some applications of graph theory to clustering,"Psychometrika, vol. 38, pp. 435-475, 1974.[4] D. W. Matula, "Graph theoretic techniques for cluster analysis algorithms," inClassification and Clustering, J. Van Ryzin, Ed. New York: Academic Press, 1977, pp. 95-129.[5] C. T. Zahn, "Graph-theoretic methods for detecting and describing gestalt clusters,"IEEE Trans. Comput., vol. 20, pp. 68-86, 1971.[6] R. Urquhart, "Graph theoretical clustering based on limited neighborhood sets,"Pattern Recognit., vol. 15, pp. 173-187, 1982.[7] W. L. Koontz, P. M. Narendra, and K. Fukunaga, "A graph-theoretic approach to nonparametric cluster analysis,"IEEE Trans. Comput., vol. 24, pp. 936-944, Sept. 1976.[8] Z. Wu and R. Leahy, "Tissue classification in MR images using hierarchical segmentation," inProc. IEEE Int. Conf. Medical Imaging, Oct. 1990.[9] R. E. Jensen, "A dynamic programming algorithm for cluster analysis,"Oper. Res., vol. 17, pp. 1034-1057, 1969.[10] W. L. Koontz, P. M. Narendra, and K. Fukunaga, "A branch and bound clustering algorithm,"IEEE Trans. Comput.vol. 24, pp. 908-915, Sept. 1975.[11] L. P. Lefkovitch, "Conditional clustering,"Biometrics, vol. 36, pp. 43-58, 1980.[12] R. E. Gomory and T. C. Hu, "Multi-terminal network flows,"SIAM J. Appl. Math., vol. 9, pp. 551-570, 1961.[13] G. K. Coleman and H. C. Andrews, "Image segmentation bu clustering,"Proc. IEEE, vol. 5, pp. 773-785, May 1979.[14] R. L. Cannon, J. V. Dave, J. C. Bezdek, and M. M. Trivedi, "Segmentation of a thematic mapper image using the fuzzyc-means clustering algorithm,"IEEE Trans. Geoscience Remote Sensing, vol. 24, pp. 400-408, May 1986.[15] D. A. Ortendahl and J. W. Carlson, "Segmentation of magnetic resonance images using fuzzy clustering," inProc. 10th Conf. Inform. Processing in Medical Imaging, 1988, pp. 91-106.[16] P. K. Sahoo, S. Soltani, and A. K. C. Wong, "A survey of thresholding techniques,"Comput. Vision Graphics Image Processing, vol. 41, pp. 233-260, 1988.[17] D. Marr and E. Hildreth, "Theory of edge detection,"Proc. Roy. Soc. Lon., vol. 207, pp. 187-217, 1980.[18] L. R. Ford, Sr. and E. Fulkerson,Flows in Networks. Princeton NJ: Princeton Univ. Press, 1962.[19] N. Christofides,Graph Theory: An algorithmic Approach. New York: Academic Press, 1975.[20] L. Lovász and M. D. Plummer,Matching Theory. Amsterdam: Elsevier Science Pub. B.V., 1986.[21] R. K. Ahuja and J. B. Orlin, "A fast and simple algorithm for the maximum flow problem,"Oper. Res., vol. 37, pp. 748-759, 1989.[22] S. Geman and D. Geman, "Stochastic relaxation, Gibbs distribution, and the Bayesian restoration of images,"IEEE Trans. Pattern Anal. Machine Intell., vol. 6, pp. 721-741, Nov. 1984.[23] Z. Wu and R. Leahy, "A graph theoretic approach to image segmentation of MR images," inProc. SPIE/SPSE's Symp. on Elect. Image Sci.&tech., vol. SPIE-1450, Feb. 1991.[24] Z. Wu, "Hierarchical and graph theoretic approaches to image segmentation and pattern classification," Ph.D. dissertation, Signal and Image Processing Inst., Univ. of Southern California, 1991.[25] Z. Wu and R. Leahy, "Unsupervised hierarchical segmentation of textured images based on homogeneity testing," USC-Signal&Image Processing Inst., Tech. Rep. #157, June 1990.
Index Terms:
optimal graph theoretic approach; data clustering; image segmentation; undirected adjacency graph; arc capacities; mutually exclusive subgraphs; largest inter-subgraph maximum flow minimization; flow and cut equivalent tree partitioning; subgraph condensation; partially equivalent tree; region boundary location; closed edge contours; graph theory; image segmentation; minimax techniques; pattern recognition
Citation:
Z. Wu, R. Leahy, "An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, no. 11, pp. 1101-1113, Nov. 1993, doi:10.1109/34.244673
Usage of this product signifies your acceptance of the
Terms of Use.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb