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

《基于最小最大割算法的阈值分割算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第1期计算机科学Vo1．41No．12014年1月ComputerScienceJan2014基于最小最大割算法的阈值分割算法刘雅坤于双元罗四维(北京交通大学计算机与信息技术学院北京100044)摘要近年来，建立在图论基础上的谱聚类算法作为一种新型的工具被应用于图像分割。其本质是将图像分割转化为最优化问题，其中的最小最大割算法(Min-maxcut)能充分满足聚类算法的准则。算法实现过程中，把最优化准则转化为特征系统进行求解。该实现方法计算复杂，随着图像尺寸的增加，所需存储空间和计算时间复杂度都会增加。在实现最小最大割算法时，用基于灰度级的权值矩阵代替

2、通常所用的基于图像像素的权值矩阵来描述图像各像素的关系，确定分割的阈值。实验表明，此方法实现的最小最大割算法实现简单、实时性高，具有自动分割等优越的分割性能。关键词谱聚类，图论，最小最大割算法，图像阈值分割中图法分类号TP391文献标识码AThresholdImageSegmentationBasedonMin-maxCutAlgorithmLIUYa-kunYUShuang-yuanLUOSi~wei(DepartmentofComputerandInformationTechnology，BeijingJiaotongUniversity，Beijing1

3、00044，China)AbstractInrecentyears，thespectralclusteringalgorithmbased0ngraphtheoryisanewtooltobeappliedtoimagesegmentation．Essentially，imagesegmentadonistObeconvertedintotheoptimizationproblem，andtheminimumcutal—gorithrn(Min-maxcut)canfullymeetthecriteriaoftheclusteringalgorithm．Int

4、heprocessofimplementation，optimi—zationcriteriaintoeigensystemsolvestheproblem．Theimplementationiscomputationallycomplex，andtherequiredstoragespaceandcomputingtimecomplexityareincreasedastheimagesizeincreases．Inthepage，whenMin-maxcutalgorithmisachieved，theweightmatricesusedinevaluat

5、ingthegraphcutsarebasedonthegraylevelsofanimage，ratherthanthecommonlyusedimagepixelstodeterminethesegmentationthreshold．ExperimentalresultsshowthattheMin-maxcutsegmentationalgorithmthatthismethodachievesissimple，real-time，andhasautomaticsegmentationandothersuperiorsegmentationperfor

6、mance．KeywordsSpectralclustering，Graphtheory，M_in-maxcutalgorithm，Imagethresholdsegmentation图像分割是数字图像处理和计算机视觉中最重要的任务法l_6]、等周割集(Isoperimetricratio)[刀等。最小最大割算法之一，其目的是根据图像的区域内满足一定的灰度、纹理等特(Mcut)完全满足聚类算法的一般准则[8]：类内样本相似度最征的相似性准则，分割图像的各个特征区域并提取出感兴趣大，类间样本相似度最小。因此，Mcut比其他割集算法有更的目标[1]。很多重要应用都

7、需要依靠图像分割，例如图像编好的分割性能。码、基于内容的图像检索、模式识别等。正是这些重要的应用本文实现了基于特征系统的Mcut算法，同时提出了基技术的发展促使了大量高质量的图像分割技术的产生，特别于Mcut的阈值分割算法。Mcut阈值分割算法的基本思想：是基于图论的图像分割技术。它具有高度的灵活性，提供统采用基于灰度级的权值矩阵M(256*256)来代替通常所用一框架来处理图像的颜色、纹理、噪声和特征等。的基于图像像素的权值矩阵来描述图像各像素的关系。对每基于图论的图像谱分割技术是将图像映射为一个带权无一个门限t，利用灰度级矩阵M可以快速地求出Mcut的值，

8、向图，把图像中的单个像素或小区域作为无