AN OPTIMAL GRAPH-THEORETIC APPROACH TO DATA CLUSTERING - THEORY AND ITS APPLICATION TO IMAGE SEGMENTATION

被引:644
作者
WU, Z [1 ]
LEAHY, R [1 ]
机构
[1] UNIV SO CALIF,INST SIGNAL & IMAGE PROC,DEPT ELECT ENGN SYST,LOS ANGELES,CA 90089
关键词
CLUSTERING; EDGE CONTOURS; FLOW AND CUT EQUIVALENT TREE; GRAPH THEORY; IMAGE SEGMENTATION; SUBGRAPH CONDENSATION;
D O I
10.1109/34.244673
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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 How 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. 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.
引用
收藏
页码:1101 / 1113
页数:13
相关论文
共 25 条
[1]   A FAST AND SIMPLE ALGORITHM FOR THE MAXIMUM FLOW PROBLEM [J].
AHUJA, RK ;
ORLIN, JB .
OPERATIONS RESEARCH, 1989, 37 (05) :748-759
[2]  
[Anonymous], 1988, ALGORITHMS CLUSTERIN
[3]   SEGMENTATION OF A THEMATIC MAPPER IMAGE USING THE FUZZY C-MEANS CLUSTERING-ALGORITHM [J].
CANNON, RL ;
DAVE, JV ;
BEZDEK, JC ;
TRIVEDI, MM .
IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING, 1986, 24 (03) :400-408
[4]  
Christofides N., 1975, GRAPH THEORY ALGORIT
[5]  
COLEMAN GB, 1979, P IEEE, V5, P773
[6]  
Duda R. O., 1973, PATTERN CLASSIFICATI, V3
[7]  
Ford L., 1962, FLOWS NETWORKS, V71, P1059, DOI 10.2307/2311955
[8]   STOCHASTIC RELAXATION, GIBBS DISTRIBUTIONS, AND THE BAYESIAN RESTORATION OF IMAGES [J].
GEMAN, S ;
GEMAN, D .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1984, 6 (06) :721-741
[9]   MULTI-TERMINAL NETWORK FLOWS [J].
GOMORY, RE ;
HU, TC .
JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1961, 9 (04) :551-570
[10]  
HUBERT LJ, 1974, PSYCHOMETRIKA, V38, P435