龔楷椿,鄔春學(xué)

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

?

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

龔楷椿,鄔春學(xué)

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

2實驗結(jié)果與分析

2.1UCI測試集實驗

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

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

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

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

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

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

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

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

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

2.2圖像分割實驗

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

圖1　原始圖像

圖2　FCM算法分割后的圖像

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

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

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

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

圖5　攝像頭拍攝原始圖像

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

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

3結(jié)束語

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

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

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

參考文獻

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

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

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

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

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

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

基金項目:國家自然科學(xué)基金資助項目(61202376);上海市教育基金會晨光計劃基金資助項目(10CG49)

收稿日期:2015- 07- 06