基于最小最大割算法的阈值分割算法

Threshold Image Segmentation Based on Min-max Cut Algorithm

近年来,建立在图论基础上的谱聚类算法作为一种新型的工具被应用于图像分割。其本质是将图像分割转化为最优化问题,其中的最小最大割算法(Min-max cut)能充分满足聚类算法的准则。算法实现过程中,把最优化准则转化为特征系统进行求解。该实现方法计算复杂,随着图像尺寸的增加,所需存储空间和计算时间复杂度都会增加。在实现最小最大割算法时,用基于灰度级的权值矩阵代替通常所用的基于图像像素的权值矩阵来描述图像各像素的关系,确定分割的阈值。实验表明,此方法实现的最小最大割算法实现简单、实时性高,具有自动分割等优越的分割性能。

In recent years,the spectral clustering algorithm based on graph theory is a new tool to be apphed to image segmentation. Essentially, image segmentation is to be converted into the optimization problem, and the minimum cut al- gorithm （Min-max cut） can fully meet the criteria of the clustering algorithm. In the process of implementation,optimi- zation criteria into eigen system solves the problem. The implementation is computafionally complex, and the required storage space and computing time complexity are increased as the image size increases. In the page, when Min-max cut algorithm is achieved, the weight matrices used in evahmting the graph cuts are based on the gray levels of an image, rather than the commonly used image pixels to determine the segmentation threshold. Experimental results show that the Min-max cut segmentation algorithm that this method achieves is simple, real-time, and has automatic segmentation and other superior segmentation performance.