基于邻接矩阵的自适应图像分割算法研究

龚楷椿,邬春学

(上海理工大学 光电信息与计算机工程学院,上海　200093)



基于邻接矩阵的自适应图像分割算法研究

龚楷椿,邬春学

(上海理工大学 光电信息与计算机工程学院,上海200093)

摘要基于聚类的图像分割算法是其中常见的一种,传统聚类算法需人为确定初始聚类中心和类别数,针对如何确定最优聚类类别数的问题,基于邻接矩阵提出一种自适应图像分割算法,该算法克服了传统聚类算法人为确定初始聚类中心和聚类类别数而导致局部最优的缺陷。利用实验数据将算法和传统聚类算法比较,并应用于图像分割。实验结果显示,算法稳定性较好,能自适应的得到准确地聚类类别数,且鲁棒性较强,在应用于图像分割时的聚类结果相对与传统聚类算法更加准确。

关键词图像处理;图像分割;聚类算法;邻接矩阵;自适应;迭代

随着智能技术的飞速发展,其在生活中也得到了广泛应用,智能家居技术便是其重要产物之一。智能家居的设备多样,其中摄像头可展示最为立体化的场景。通过摄像头可及时而有效地监控所关心区域的动态,一旦发现意外情况可及时处理,这对于做好重要区域的安防工作有较大帮助。摄像头可采集某时间点目标区域的图像,而图像分割[1]作为图像处理和图像识别的重要步骤,也逐渐成为该领域研究者研究的热点。

文献[2]介绍了多种图像分割的算法,如阈值分割法,边缘检测法,直线提取法,区域生长和分裂合并法等,这些算法根据不同的应用场景可有多种变形,而基于聚类的图像分割算法是其中较为常见的一种。文献[3]对聚类分析定义如下:根据数据集中发现的数据对象及数据对象之间的关系,将数据对象进行分组。文献[4]中提出聚类分析的目标是,同一组内的对象是相似的,而不同组中的对象是不同的。同一组内的相似性越大,不同组间差别越大,则聚类效果越好,即达到高内聚低耦合的效果。文献[5]根据数据特性可将聚类算法分为基于划分的聚类分析算法、基于层次的聚类分析算法、基于密度的聚类分析算法、基于网格的聚类分析算法和基于模型的聚类分析算法。

文献[6]提出的模糊C均值算法(FCM)是模糊集合论与传统聚类算法的经典结合,并对其进行了相应的介绍,该算法是聚类分析中较为有效的算法。文献[7～8]介绍FCM算法的优势,FCM算法提出了隶属度的概念,隶属度表示每个数据点隶属于该聚类簇的程度,该特性能更好地反映出数据点和质心之间的关系。

研究者后将模糊理论引入到图像处理中,并取得较好的效果。文献[8～9]中Nas和Wang等人采用应用最为广泛的模糊C-均值算法(Fuzzy C-Means)进行图像分割,采用该算法进行图像分割的优点是避免了设定阈值的问题,并能解决阈值化分割难以解决的多个分支的分割问题;聚类过程中不需要任何人工干预,很适合于自适应图像分割的应用领域。但是基于FCM的图像分割算法仍存在一些问题:(1)聚类类别数的确定,不同的值会导致结果差异较大;(2)初始类中心和初始隶属度矩阵的确定,会导致聚类结果局部最优。

1基于邻接矩阵的自适应图像分割算法

文献[10～11]介绍了提取图像特征的方法,如颜色、像素灰度、邻域均值灰度等,该步骤是图像分割中的关键步骤,特征选取的优劣将直接影响分割的效果。本文提出基于邻接矩阵的自适应的图像分割算法,该算法属于基于颜色特征的图像分割算法,此类方法根据图像的颜色的RGB特征值,对图像进行分割处理,将聚类分析算法有效地与图像分割进行结合。与基于模糊聚类的图像分割算法相比,该算法的优势在于:(1)能与经典的聚类算法如K-means,FCM等有效结合,利用经典聚类算法对数据集进行预处理;(2)克服了K-means、FCM算法人为确定初始聚类中心和聚类类别数而导致的聚类结果局部最优,通过多次迭代的方式自适应地得到精确的聚类类别数和稳定的聚类结果。

算法的具体实现过程如下:

步骤1图像特征的数据集采集:根据给定图像的像素点的值将图像均匀分成若干等份,并计算出每一等份中所有像素点平均的RGB值作为该等份的代表值,将得到的平均RGB值作为算法的初始数据集。

(1)

由上述参数可得到如下C×N的U矩阵

步骤3矩阵运算:定义一维向量L=[l1,l2,…,lN],其中lj为U矩阵j列uij最大下标i的值,每个lj表示对应的xj所属的类别。

定义观察矩阵O,该矩阵完全由一维向量L的值所决定

根据O矩阵的特征不难发现,O矩阵实际表示数据点之间的关系,若Oij=1,说明xi和xj在同一类别中,反之若Oij=0,则说明两个点在不同的类别中。因此,经过以上矩阵变换,O矩阵即为在给定类别数后产生的聚类结果矩阵;

步骤5图像分割:通过上述过程可以得到最优聚类类别数,即为图像分割的类别数以及每个像素点所属类别,将相同类别的像素点聚成一类,利用图像处理的方法将图像还原,最终得到图像分割的效果图。

2实验结果与分析

2.1UCI测试集实验

本文采用的数据集为加州大学欧文分校(UniversityofCaliforniaIrvine)提出的用于机器学习UCI数据库中的Iris、Hayes和Wine这3个数据集,详细描述如表1所示。

表1　UCI的3个数据集

实验1将3组UCI的测试集作为实验的初始数据集,通过本文所提算法,改变迭代次数k,验证最终得到的聚类类别数与预期是否相同,实验结果如表2所示。

表2　UCI数据集聚类结果

实验结果分析:通过上述实验结果发现,当k=10、k=30和k=40时,3个测试集实验的结果均存在与预期结果不一致的结果。原因是当迭代次数不同时,两种类别之间的数据点差异不大,甚至可能只相差几个数据点,则会造成聚类数量增加,导致与实际结果不一致。为使聚类效果最优,需多次迭代才可获取稳定的聚类类别数,实验结果表明通过本文所提算法,当增加迭代次数后,聚类个数会稳定在一个固定的值,该值即为最优聚类类别数。

实验2将3组UCI的测试集作为实验的初始数据集,比较K-means和本文所提算法在聚类质量、聚类准确率以及聚类时间这3个参数的实验结果,验证本文所提算法在多次聚类时的稳定性,实验迭代次数设定为40次,实验结果如表3和表4所示。

表3　K-means算法聚类结果

表4　本文所提算法聚类结果

实验结果分析:对于聚类质量和聚类准确率,除Hayes测试集外,本文提出的聚类算法均高于K-means算法,通过分析表明,本文所提算法在多次聚类情况下的稳定性优于K-means算法,鲁棒性较强。但对于聚类时间,本文所提算法与K-means算法相比耗费时间更长,原因在于本文提出的聚类算法需要对数据进行预处理,且需要多次迭代取最优解,导致算法时间耗费较长。

2.2图像分割实验

实验1人工选取像素为300×200的3幅图像,通过K-means算法和本文所提算法对3幅图像进行了图像分割的实验,并得到如下图所示结果。其中图1为原始图像,图2为使用FCM算法分割后的图像(聚类类别数默认取3),图3为使用K-means算法分割后的图像(聚类类别数默认取2),图4为使用本文所提算法分割后的图像。

图1　原始图像

图2　FCM算法分割后的图像

图3　K-means算法分割后的图像

图4　本文所提算法分割后的图像

实验结果分析:对于相同的3幅图像进行图像分割,K-means算法和FCM算法都需要提前设定聚类类别数和相应的初始参数,而不同的初始值所对应实验结果也有所差异,通过本文所提算法可以自适应地获得最优聚类类别数,从而避免人工干预导致结果的局部最优。因此通过比较可发现本文所提算法在聚类的精确性方面优于单独使用K-means算法和FCM算法。

实验2通过摄像头连续拍摄得到同一场景下连续的4幅图像,再经由本文所提算法进行图像分割实验,得到如下图所示结果。其中图5为摄像头拍摄的原始图像,图6为使用本文所提算法分割后的图像。

图5　摄像头拍摄原始图像

图6　本文所提算法分割后的图像

实验结果分析:通过本文提出的分割算法对摄像头连续拍摄的4幅图像进行图像分割处理,可直观地分辨出图像中物体的轮廓和所处位置,当图像中的物体个数不断增加时,也可清楚分辨出图中物体的个数。该实验表明本文所提算法可具体应用于现实场景,有效减小图像识别和处理的难度。

3结束语

传统基于聚类的图像分割算法存在一定的缺陷,聚类效果的差异会导致图像分割结果鲁棒性较差。针对此问题,提出基于邻接矩阵的自适应图像分割算法,文中主要介绍该算法的原理和具体实现,并通过实验验证了算法的正确性以及在实际应用于图像分割中的准确性,比较了算法与K-means聚类算法的差异,实验结果表明,本文提出的算法不仅能得到最优聚类类

别数,聚类稳定性优于K-means聚类算法,且图像分割效果以及准确性也较好,具有一定的实际应用价值。

在未来的研究工作中,还需对算法做进一步的研究,算法仍存在一定的问题:(1)本文仅针对图像的颜色特征进行了分割,并未涉及到其他图像的特征;(2)在预处理阶段的时间效率略低,针对像素过大图片的处理效果并不理想,后期需改进算法效率;(3)聚类时间耗费比K-means聚类算法长。

参考文献

[1]杨怀义.图像分割中算法的应用研究[J].计算机仿真,2012,29(2):229-232.

[2]HeJ,GeH,WangY.Surveyonthemethodsofimagesegmentationresearch[J].ComputerEngineering&Science,2009(12):018-025.

[3]金建国.聚类方法综述[J].计算机科学,2014,41(S2):288-293.

[4]XuR,WunschD.Surveyofclusteringalgorithms[J].IEEETransactionsonNeuralNetworks,2005,16(3):645-678.

[5]孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.

[6]IzakianH,AbrahamA.FuzzyC-meansandfuzzyswarmforfuzzyclusteringproblem[J].ExpertSystemswithApplications,2011,38(3):1835-1838.

[7]CaiW,ChenS,ZhangD.Fastandrobustfuzzyc-meansclusteringalgorithmsincorporatinglocalinformationforimagesegmentation[J].PatternRecognition,2007,40(3):825-838.

[8]NazS,MajeedH,IrshadH.Imagesegmentationusingfuzzyclustering:Asurvey[C].Harbin:6thIEEEInternationalConferenceonEmergingTechnologies,2010.

[9]WangXY,BuJ.AfastandrobustimagesegmentationusingFCMwithspatialinformation[J].DigitalSignalProcessing,2010,20(4):1173-1182.

[10]AquinoA,Gegúndez-AriasME,MarínD.Detectingtheopticdiscboundaryindigitalfundusimagesusingmorphological,edgedetection,andfeatureextractiontechniques[J].IEEETransactionsonMedicalImaging,2010,29(11):1860-1869.

[11]SonkaM,HlavacV,BoyleR.Imageprocessing,analysis,andmachinevision[M].MAUSA:CengageLearning,2014.

[12]LiZ,WuXM,ChangSF.Segmentationusingsuperpixels:Abipartitegraphpartitioningapproach[C].Sydney:2012IEEEConferenceonComputerVisionandPatternRecognition,2012.

[13]KhandekarR,RaoS,VaziraniU.Graphpartitioningusingsinglecommodityflows[J].JournaloftheACM,2009,56(4):19-26.

Adaptive Image Segmentation Algorithm Based on the Adjacency Matrix

GONG Kaichun,WU Chunxue

(School of Optical-Electrical and Computer Engineering,University of Shanghai for

Science and Technology,Shanghai 200093,China)

AbstractThe image segmentation algorithm based on clustering is a common one.Traditional clustering algorithm requires the determination of the initial cluster centers and cluster number of categories,and how to determine the optimal cluster number of categories is a major challenge.An adaptive image segmentation algorithm based on the adjacency matrix is proposed to overcome the local optimization caused by artificial determination of the initial cluster centers and cluster number of categories by traditional clustering algorithms.The proposed algorithm is compared with the traditional algorithm by experiment and applied to segmentation.Experimental results demonstrate good robustness and stability of the algorithm with more accurate result of clustering for segmentation than those by the traditional algorithm.

Keywordsimage processing;image segmentation;clustering algorithm;adjacency matrix;adaptive;iteration

中图分类号TP391.41

文献标识码A

文章编号1007-7820(2016)02-066-04

doi:10.16180/j.cnki.issn1007-7820.2016.02.017

作者简介:邬春学(1987—),男,博士,教授。研究方向:计算机监测与控制等。龚楷椿(1991—),男,硕士研究生。研究方向:图像识别等。

基金项目:国家自然科学基金资助项目(61202376);上海市教育基金会晨光计划基金资助项目(10CG49)

收稿日期:2015- 07- 06