基于图论Gomory-Hu算法的快速图像分割  

Fast image segmentation based on Gomory-Hu algorithm

作　　者：刘丙涛[1] 田铮[1,2] 周强锋[1] 李小斌[1] 

机构地区：[1]西北工业大学应用数学系,西安710072 [2]中国科学院遥感应用研究所,遥感科学国家重点实验室,北京100101

出　　处：《计算机应用研究》2008年第9期2865-2867,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(60375003);国家航空基础科学基金资助项目(03I53059)

摘　　要：Gomory-Hu算法是图论中的经典算法,用于寻找图的最小流割等价树,具有最优解,但是该算法很难处理较大的图像,而且倾向于分割出孤立点集。为此,给出了孤立点的判定方法,并提出一种基于Gomory-Hu算法的图像分割方法。该算法首先通过快速聚类减少图中顶点数目,然后构造新的赋权图,并应用Gomory-Hu算法对图进行最优划分,得到分割结果。提出的算法对多幅自然图像进行了分割实验,平均分割时间在3 s内。实验结果证明了算法的有效性和快速性。Gomory-Hu algorithm is a classical algorithm for finding the minimum flow and cut equivalent tree of the graph in graph theory, it had the optimal solution. But it was very difficult to deal with large images, and it was biased toward finding small components. In order to solve this problem, this paper presented a novel definition of isolated node, and proposed a novel algorithm based on improved Gomory-Hu algorithm. This algorithm first used the fast clustering algorithm to reduce the number of vertices ,then used the improved Gomory-Hu algorithm in the new graph and achieve the optimal solution. Then applied the new algorithm to a number of natural images. The experimental results demonstrate that the algorithm is effective and efficient.

关 键 词：图像分割 Gomory-Hu算法 聚类 图论 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]