龔楷椿,鄔春學(xué)

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上?！?00093)

?

基于鄰接矩陣的自適應(yīng)圖像分割算法研究

龔楷椿,鄔春學(xué)

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海200093)

摘要基于聚類的圖像分割算法是其中常見的一種,傳統(tǒng)聚類算法需人為確定初始聚類中心和類別數(shù),針對(duì)如何確定最優(yōu)聚類類別數(shù)的問題,基于鄰接矩陣提出一種自適應(yīng)圖像分割算法,該算法克服了傳統(tǒng)聚類算法人為確定初始聚類中心和聚類類別數(shù)而導(dǎo)致局部最優(yōu)的缺陷。利用實(shí)驗(yàn)數(shù)據(jù)將算法和傳統(tǒng)聚類算法比較,并應(yīng)用于圖像分割。實(shí)驗(yàn)結(jié)果顯示,算法穩(wěn)定性較好,能自適應(yīng)的得到準(zhǔn)確地聚類類別數(shù),且魯棒性較強(qiáng),在應(yīng)用于圖像分割時(shí)的聚類結(jié)果相對(duì)與傳統(tǒng)聚類算法更加準(zhǔn)確。

關(guān)鍵詞圖像處理;圖像分割;聚類算法;鄰接矩陣;自適應(yīng);迭代

隨著智能技術(shù)的飛速發(fā)展,其在生活中也得到了廣泛應(yīng)用,智能家居技術(shù)便是其重要產(chǎn)物之一。智能家居的設(shè)備多樣,其中攝像頭可展示最為立體化的場(chǎng)景。通過攝像頭可及時(shí)而有效地監(jiān)控所關(guān)心區(qū)域的動(dòng)態(tài),一旦發(fā)現(xiàn)意外情況可及時(shí)處理,這對(duì)于做好重要區(qū)域的安防工作有較大幫助。攝像頭可采集某時(shí)間點(diǎn)目標(biāo)區(qū)域的圖像,而圖像分割[1]作為圖像處理和圖像識(shí)別的重要步驟,也逐漸成為該領(lǐng)域研究者研究的熱點(diǎn)。

文獻(xiàn)[2]介紹了多種圖像分割的算法,如閾值分割法,邊緣檢測(cè)法,直線提取法,區(qū)域生長(zhǎng)和分裂合并法等,這些算法根據(jù)不同的應(yīng)用場(chǎng)景可有多種變形,而基于聚類的圖像分割算法是其中較為常見的一種。文獻(xiàn)[3]對(duì)聚類分析定義如下:根據(jù)數(shù)據(jù)集中發(fā)現(xiàn)的數(shù)據(jù)對(duì)象及數(shù)據(jù)對(duì)象之間的關(guān)系,將數(shù)據(jù)對(duì)象進(jìn)行分組。文獻(xiàn)[4]中提出聚類分析的目標(biāo)是,同一組內(nèi)的對(duì)象是相似的,而不同組中的對(duì)象是不同的。同一組內(nèi)的相似性越大,不同組間差別越大,則聚類效果越好,即達(dá)到高內(nèi)聚低耦合的效果。文獻(xiàn)[5]根據(jù)數(shù)據(jù)特性可將聚類算法分為基于劃分的聚類分析算法、基于層次的聚類分析算法、基于密度的聚類分析算法、基于網(wǎng)格的聚類分析算法和基于模型的聚類分析算法。

文獻(xiàn)[6]提出的模糊C均值算法(FCM)是模糊集合論與傳統(tǒng)聚類算法的經(jīng)典結(jié)合,并對(duì)其進(jìn)行了相應(yīng)的介紹,該算法是聚類分析中較為有效的算法。文獻(xiàn)[7～8]介紹FCM算法的優(yōu)勢(shì),FCM算法提出了隸屬度的概念,隸屬度表示每個(gè)數(shù)據(jù)點(diǎn)隸屬于該聚類簇的程度,該特性能更好地反映出數(shù)據(jù)點(diǎn)和質(zhì)心之間的關(guān)系。

研究者后將模糊理論引入到圖像處理中,并取得較好的效果。文獻(xiàn)[8～9]中Nas和Wang等人采用應(yīng)用最為廣泛的模糊C-均值算法(Fuzzy C-Means)進(jìn)行圖像分割,采用該算法進(jìn)行圖像分割的優(yōu)點(diǎn)是避免了設(shè)定閾值的問題,并能解決閾值化分割難以解決的多個(gè)分支的分割問題;聚類過程中不需要任何人工干預(yù),很適合于自適應(yīng)圖像分割的應(yīng)用領(lǐng)域。但是基于FCM的圖像分割算法仍存在一些問題:(1)聚類類別數(shù)的確定,不同的值會(huì)導(dǎo)致結(jié)果差異較大;(2)初始類中心和初始隸屬度矩陣的確定,會(huì)導(dǎo)致聚類結(jié)果局部最優(yōu)。

1基于鄰接矩陣的自適應(yīng)圖像分割算法

文獻(xiàn)[10～11]介紹了提取圖像特征的方法,如顏色、像素灰度、鄰域均值灰度等,該步驟是圖像分割中的關(guān)鍵步驟,特征選取的優(yōu)劣將直接影響分割的效果。本文提出基于鄰接矩陣的自適應(yīng)的圖像分割算法,該算法屬于基于顏色特征的圖像分割算法,此類方法根據(jù)圖像的顏色的RGB特征值,對(duì)圖像進(jìn)行分割處理,將聚類分析算法有效地與圖像分割進(jìn)行結(jié)合。與基于模糊聚類的圖像分割算法相比,該算法的優(yōu)勢(shì)在于:(1)能與經(jīng)典的聚類算法如K-means,FCM等有效結(jié)合,利用經(jīng)典聚類算法對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理;(2)克服了K-means、FCM算法人為確定初始聚類中心和聚類類別數(shù)而導(dǎo)致的聚類結(jié)果局部最優(yōu),通過多次迭代的方式自適應(yīng)地得到精確的聚類類別數(shù)和穩(wěn)定的聚類結(jié)果。

算法的具體實(shí)現(xiàn)過程如下:

步驟1圖像特征的數(shù)據(jù)集采集:根據(jù)給定圖像的像素點(diǎn)的值將圖像均勻分成若干等份,并計(jì)算出每一等份中所有像素點(diǎn)平均的RGB值作為該等份的代表值,將得到的平均RGB值作為算法的初始數(shù)據(jù)集。

(1)

由上述參數(shù)可得到如下C×N的U矩陣

步驟3矩陣運(yùn)算:定義一維向量L=[l1,l2,…,lN],其中l(wèi)j為U矩陣j列uij最大下標(biāo)i的值,每個(gè)lj表示對(duì)應(yīng)的xj所屬的類別。

定義觀察矩陣O,該矩陣完全由一維向量L的值所決定

根據(jù)O矩陣的特征不難發(fā)現(xiàn),O矩陣實(shí)際表示數(shù)據(jù)點(diǎn)之間的關(guān)系,若Oij=1,說明xi和xj在同一類別中,反之若Oij=0,則說明兩個(gè)點(diǎn)在不同的類別中。因此,經(jīng)過以上矩陣變換,O矩陣即為在給定類別數(shù)后產(chǎn)生的聚類結(jié)果矩陣;

步驟5圖像分割:通過上述過程可以得到最優(yōu)聚類類別數(shù),即為圖像分割的類別數(shù)以及每個(gè)像素點(diǎn)所屬類別,將相同類別的像素點(diǎn)聚成一類,利用圖像處理的方法將圖像還原,最終得到圖像分割的效果圖。

2實(shí)驗(yàn)結(jié)果與分析

2.1UCI測(cè)試集實(shí)驗(yàn)

本文采用的數(shù)據(jù)集為加州大學(xué)歐文分校(UniversityofCaliforniaIrvine)提出的用于機(jī)器學(xué)習(xí)UCI數(shù)據(jù)庫(kù)中的Iris、Hayes和Wine這3個(gè)數(shù)據(jù)集,詳細(xì)描述如表1所示。

表1　UCI的3個(gè)數(shù)據(jù)集

實(shí)驗(yàn)1將3組UCI的測(cè)試集作為實(shí)驗(yàn)的初始數(shù)據(jù)集,通過本文所提算法,改變迭代次數(shù)k,驗(yàn)證最終得到的聚類類別數(shù)與預(yù)期是否相同,實(shí)驗(yàn)結(jié)果如表2所示。

表2　UCI數(shù)據(jù)集聚類結(jié)果

實(shí)驗(yàn)結(jié)果分析:通過上述實(shí)驗(yàn)結(jié)果發(fā)現(xiàn),當(dāng)k=10、k=30和k=40時(shí),3個(gè)測(cè)試集實(shí)驗(yàn)的結(jié)果均存在與預(yù)期結(jié)果不一致的結(jié)果。原因是當(dāng)?shù)螖?shù)不同時(shí),兩種類別之間的數(shù)據(jù)點(diǎn)差異不大,甚至可能只相差幾個(gè)數(shù)據(jù)點(diǎn),則會(huì)造成聚類數(shù)量增加,導(dǎo)致與實(shí)際結(jié)果不一致。為使聚類效果最優(yōu),需多次迭代才可獲取穩(wěn)定的聚類類別數(shù),實(shí)驗(yàn)結(jié)果表明通過本文所提算法,當(dāng)增加迭代次數(shù)后,聚類個(gè)數(shù)會(huì)穩(wěn)定在一個(gè)固定的值,該值即為最優(yōu)聚類類別數(shù)。

實(shí)驗(yàn)2將3組UCI的測(cè)試集作為實(shí)驗(yàn)的初始數(shù)據(jù)集,比較K-means和本文所提算法在聚類質(zhì)量、聚類準(zhǔn)確率以及聚類時(shí)間這3個(gè)參數(shù)的實(shí)驗(yàn)結(jié)果,驗(yàn)證本文所提算法在多次聚類時(shí)的穩(wěn)定性,實(shí)驗(yàn)迭代次數(shù)設(shè)定為40次,實(shí)驗(yàn)結(jié)果如表3和表4所示。

表3　K-means算法聚類結(jié)果

表4　本文所提算法聚類結(jié)果

實(shí)驗(yàn)結(jié)果分析:對(duì)于聚類質(zhì)量和聚類準(zhǔn)確率,除Hayes測(cè)試集外,本文提出的聚類算法均高于K-means算法,通過分析表明,本文所提算法在多次聚類情況下的穩(wěn)定性優(yōu)于K-means算法,魯棒性較強(qiáng)。但對(duì)于聚類時(shí)間,本文所提算法與K-means算法相比耗費(fèi)時(shí)間更長(zhǎng),原因在于本文提出的聚類算法需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,且需要多次迭代取最優(yōu)解,導(dǎo)致算法時(shí)間耗費(fèi)較長(zhǎng)。

2.2圖像分割實(shí)驗(yàn)

實(shí)驗(yàn)1人工選取像素為300×200的3幅圖像,通過K-means算法和本文所提算法對(duì)3幅圖像進(jìn)行了圖像分割的實(shí)驗(yàn),并得到如下圖所示結(jié)果。其中圖1為原始圖像,圖2為使用FCM算法分割后的圖像(聚類類別數(shù)默認(rèn)取3),圖3為使用K-means算法分割后的圖像(聚類類別數(shù)默認(rèn)取2),圖4為使用本文所提算法分割后的圖像。

圖1　原始圖像

圖2　FCM算法分割后的圖像

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

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

實(shí)驗(yàn)結(jié)果分析:對(duì)于相同的3幅圖像進(jìn)行圖像分割,K-means算法和FCM算法都需要提前設(shè)定聚類類別數(shù)和相應(yīng)的初始參數(shù),而不同的初始值所對(duì)應(yīng)實(shí)驗(yàn)結(jié)果也有所差異,通過本文所提算法可以自適應(yīng)地獲得最優(yōu)聚類類別數(shù),從而避免人工干預(yù)導(dǎo)致結(jié)果的局部最優(yōu)。因此通過比較可發(fā)現(xiàn)本文所提算法在聚類的精確性方面優(yōu)于單獨(dú)使用K-means算法和FCM算法。

實(shí)驗(yàn)2通過攝像頭連續(xù)拍攝得到同一場(chǎng)景下連續(xù)的4幅圖像,再經(jīng)由本文所提算法進(jìn)行圖像分割實(shí)驗(yàn),得到如下圖所示結(jié)果。其中圖5為攝像頭拍攝的原始圖像,圖6為使用本文所提算法分割后的圖像。

圖5　攝像頭拍攝原始圖像

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

實(shí)驗(yàn)結(jié)果分析:通過本文提出的分割算法對(duì)攝像頭連續(xù)拍攝的4幅圖像進(jìn)行圖像分割處理,可直觀地分辨出圖像中物體的輪廓和所處位置,當(dāng)圖像中的物體個(gè)數(shù)不斷增加時(shí),也可清楚分辨出圖中物體的個(gè)數(shù)。該實(shí)驗(yàn)表明本文所提算法可具體應(yīng)用于現(xiàn)實(shí)場(chǎng)景,有效減小圖像識(shí)別和處理的難度。

3結(jié)束語

傳統(tǒng)基于聚類的圖像分割算法存在一定的缺陷,聚類效果的差異會(huì)導(dǎo)致圖像分割結(jié)果魯棒性較差。針對(duì)此問題,提出基于鄰接矩陣的自適應(yīng)圖像分割算法,文中主要介紹該算法的原理和具體實(shí)現(xiàn),并通過實(shí)驗(yàn)驗(yàn)證了算法的正確性以及在實(shí)際應(yīng)用于圖像分割中的準(zhǔn)確性,比較了算法與K-means聚類算法的差異,實(shí)驗(yàn)結(jié)果表明,本文提出的算法不僅能得到最優(yōu)聚類類

別數(shù),聚類穩(wěn)定性優(yōu)于K-means聚類算法,且圖像分割效果以及準(zhǔn)確性也較好,具有一定的實(shí)際應(yīng)用價(jià)值。

在未來的研究工作中,還需對(duì)算法做進(jìn)一步的研究,算法仍存在一定的問題:(1)本文僅針對(duì)圖像的顏色特征進(jìn)行了分割,并未涉及到其他圖像的特征;(2)在預(yù)處理階段的時(shí)間效率略低,針對(duì)像素過大圖片的處理效果并不理想,后期需改進(jìn)算法效率;(3)聚類時(shí)間耗費(fèi)比K-means聚類算法長(zhǎng)。

參考文獻(xiàn)

[1]楊懷義.圖像分割中算法的應(yīng)用研究[J].計(jì)算機(jī)仿真,2012,29(2):229-232.

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

[3]金建國(guó).聚類方法綜述[J].計(jì)算機(jī)科學(xué),2014,41(S2):288-293.

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

[5]孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學(xué)報(bào),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

中圖分類號(hào)TP391.41

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1007-7820(2016)02-066-04

doi:10.16180/j.cnki.issn1007-7820.2016.02.017

作者簡(jiǎn)介:鄔春學(xué)(1987—),男,博士,教授。研究方向:計(jì)算機(jī)監(jiān)測(cè)與控制等。龔楷椿(1991—),男,碩士研究生。研究方向:圖像識(shí)別等。

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61202376);上海市教育基金會(huì)晨光計(jì)劃基金資助項(xiàng)目(10CG49)

收稿日期:2015- 07- 06