Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (9): 178-183.DOI: 10.3778/j.issn.1002-8331.1801-0447

Previous Articles     Next Articles

Image Segmentation Algorithm of Minimum Spanning Tree Combined with Ostu Threshold Method

SONG Sensen1, JIA Zhenhong1, YANG Jie2, Nikola KASABOV3   

  1. 1.College of Information Science and Engineering, Xinjiang University, Urumqi 830046, China
    2.Institute of Image Processing and Pattern Recognition, Shanghai Jiao Tong University, Shanghai 200240, China
    3.Knowledge Engineering and Discovery Research Institute, Auckland University of Technology, Auckland 1020, New Zealand
  • Online:2019-05-01 Published:2019-04-28


宋森森1,贾振红1,杨  杰2,Nikola KASABOV3   

  1. 1.新疆大学 信息科学与工程学院,乌鲁木齐 830046
    2.上海交通大学 图像处理与模式识别研究所,上海 200240
    3.奥克兰理工大学 知识工程与发现研究所,新西兰 奥克兰 1020

Abstract: Image segmentation algorithm based on Minimum Spanning Tree(MST) is a global optimal algorithm. However, there will be poor performance in the processing of image details, that is, the segmentation results will appear different degree of over segmentation and under segmentation. To address this problem, according to the property of the largest class variance among local regions and global image, the MST segmentation algorithm combined with the method of the largest class variance threshold(Ostu) is proposed, which is an optimal method for MST. The Ostu threshold will be used two times, one is a merger between the components, and another is to merge small regions to the target area or the background area. It is proved by experiments that the ratio of over segmentation and under segmentation can be effectively reduced, as well as the error rate of segmentation, by the proposed algorithm.

Key words: minimum spanning tree, Ostu threshold, error rate of segmentation

摘要: 基于最小生成树的图像分割算法是一种全局最优的算法,然而会出现图像细节的处理不甚理想的问题,即分割结果出现不同程度的过分割和欠分割的现象。针对这一现象,根据图像全局和区域间的最大类间方差(Ostu),将Ostu阈值法与最小生成树(MST)算法相结合,提出了一种基于MST的Ostu阈值法图像分割准则。该图像分割算法是一种MST的优化方法,将区域合并判决条件取决于相互合并的两个区域的Ostu阈值,又考虑到较小的区域包含在较大的目标区域中或者背景区域中,再次使用Ostu阈值进行区域合并。该方法通过实验证明,可以有效地减弱图像的过分割与欠分割比例,减少了误分割率。

关键词: 最小生成树, Ostu阈值, 误分割率