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

GomoryHu算法是图论中的经典算法，用于寻找图的最小流割等价树，具有最优解，但是该算法很难处理较大的图像，而且倾向于分割出孤立点集。为此，给出了孤立点的判定方法，并提出一种基于GomoryHu算法的图像分割方法。该算法首先通过快速聚类减少图中顶点数目，然后构造新的赋权图，并应用GomoryHu算法对图进行最优划分，得到分割结果。提出的算法对多幅自然图像进行了分割实验，平均分割时间在3 s内。实验结果证明了算法的有效性和快速性。

Fast image segmentation based on Gomory Hu algorithm

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.