基于图论Gomory-Hu算法的SAR图像多尺度分割  

Multiscale SAR Image Segmentation Based on Gomory-Hu Algorithm

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

机构地区：[1]西北工业大学应用数学系,西安710072

出　　处：《宇航学报》2008年第3期1002-1007,共6页Journal of Astronautics

基　　金：国家自然科学基金(60375003);航空基础科学基金(03I53059);西北工业大学创新基金

摘　　要：由于SAR图像含有斑点噪声,很难有效的分割出精确的结果,为此提出一种新的基于图论的SAR图像分割方法,证明了算法具有最优解,分析了算法的复杂度,验证了算法具有实时性。该算法通过构造多尺度结构快速找到收缩图以及初始图的子图集合,然后对其分别应用Gomory-Hu算法得到对应的等价树,最后根据规则得到初始图的等价树,按照割值由小到大依次去边后,可得到对原图的最优划分,映射回图像则可得分割结果。实验结果说明了算法的有效性和实时性。The multiplicative nature of the speckle in SAR images is a difficult problem. A novel method for SAR image segmentation based on Gomory-Hu algorithm is proposed in this paper. We have proved that it has the optimal solution, and also analyzed it＇ s complexity. The algorithm construct the multiscale structure to find the condense graph and the sub graphs of the initial graph first, then construct the equivalent tree separately using the Gomory-Hu algorithm, and construct the equivalent tree of the initial graph under the rule, remove the arcs in order, the optimal solution will be found. Finally, mapping back to the original image and achieve the result. Segmentation results on real SAR images demonstrate the effectiveness of the proposed algorithm.

关 键 词：图像分割 Gomory-Hu算法 多尺度 图论 

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