基于改進(jìn)型K均值算法的尿沉渣圖像分割研究

重慶郵電大學(xué)生物醫(yī)學(xué)工程研究中心　程　星　李章勇　姜小明　夏　爽

1　引言

尿成渣圖像的分析檢查是尿常規(guī)檢查中非常重要的部分，對于臨床診斷泌尿系統(tǒng)疾病有很大幫助[1]。傳統(tǒng)的尿沉渣檢查需要在顯微鏡下，對尿沉渣樣本圖片進(jìn)行人工檢查，其目的是檢查尿液里面各種有形成分，這些有形成分包括有顆粒管型、紅細(xì)胞、白細(xì)胞、上皮組織以及從尿液中沉析出來的各種晶體[2]。由于醫(yī)院每天需要分析大量的尿液，給檢驗(yàn)人員帶來極大地勞動量，容易影響其對于結(jié)果的判斷，且易受主觀性等因素的影響。更加重要的是，人工檢查無法對所查圖像進(jìn)行快速、準(zhǔn)確的定量處理，延緩了臨床醫(yī)生對疾病進(jìn)行進(jìn)一步的分析[3]。將數(shù)字圖像處理技術(shù)應(yīng)用在尿沉渣圖像上不僅能有效降低檢驗(yàn)人員的勞動強(qiáng)度，提高圖像處理效率，減小主觀因素帶來的誤差，而且能夠?qū)崿F(xiàn)對尿沉渣圖像的精準(zhǔn)的定量分析，從而提高診斷的準(zhǔn)確性。

在尿沉渣圖像中，由于病變、光照或其他原因，某些成分邊緣模糊難以識別[4]。導(dǎo)致一些傳統(tǒng)分割方法如閾值分割、邊緣檢測、分水嶺等、在此類圖像分割上無法獲得快速精準(zhǔn)的效果[5,6]。

本文采用Prewitt算子對預(yù)處理后的尿沉渣圖像進(jìn)行邊緣提取。為了得到更好的效果還需要對圖像進(jìn)行二值化。利用尿沉渣有形成分形態(tài)和面積的不同提出一種應(yīng)用于尿沉渣圖像分割的改進(jìn)型K均值聚類算法。

2　K均值聚類算法

2.1　傳統(tǒng)的K均值聚類算法

K均值算法是目前最經(jīng)典也是應(yīng)用最為廣泛的聚類算法[7]。該算法的基本思想為：在空間中K個點(diǎn)為中心進(jìn)行聚類，以歐式距離作為相似度測度，對最靠對象歸類。并通過迭代的方法，依次更新各聚類中心的值，直到得到最好的近他們的聚類結(jié)果，從而是的生成的每一個聚類類內(nèi)緊湊，類間獨(dú)立。

K均值算法首先需要指定一個固定的K值，該K值表示為希望從對象數(shù)據(jù)庫中獲得的簇的個數(shù)，然后隨機(jī)選取任意K個對象作為初始簇的中心，初始地代表一個簇[8]。該算法在每次迭代中對數(shù)據(jù)集中余下的每一個對象，根據(jù)其到各個簇中心的距離將每個對象重新分配給距離其最近的簇。當(dāng)考察完所有數(shù)據(jù)對象之后，該次迭代運(yùn)算完成，根據(jù)結(jié)果，新的聚類中心被計(jì)算出來[9]。在一次迭代前后，如果E的值沒有發(fā)生變化，說明算法已經(jīng)收斂。E是聚類誤差平方和函數(shù)作為聚類準(zhǔn)則函數(shù)：

②將數(shù)據(jù)樣本集合中的每一個樣本按照最小距離原則分配到最鄰近聚類。一般使用歐幾里德距離來衡量每一個樣本到不同聚類中心的距離，并將其歸屬到距離其最近的聚類中心；

③根據(jù)聚類的結(jié)果，重新計(jì)算K個聚類的中心：

K均值聚類算法是一種簡單、快速的用來解決聚類問題的經(jīng)典算法。在處理比較 大的數(shù)據(jù)集合的時(shí)候，該算法是相對可伸縮和高效率的。因?yàn)樗膹?fù)雜度是0（nkt），其中，n是所有數(shù)據(jù)對象的數(shù)目，k是聚類的數(shù)目，t是迭代的次數(shù)。通常來說k ≤ n且t ≤ n。K均值算法比較適合結(jié)果簇較為密集的集合，在類與類間區(qū)別較為明顯的時(shí)候，算法效果較好。

K均值缺點(diǎn)也較為直觀，一般需要事先給出要生成的聚類的個數(shù)K，這個K值的選擇非常難以預(yù)估，而且對于初始聚類點(diǎn)的選擇很敏感，最終的聚類結(jié)果較為依賴與初始點(diǎn)的選擇[10]。若選擇不適合的數(shù)據(jù)作為聚類中心點(diǎn)，就很有可能導(dǎo)致最后結(jié)果產(chǎn)生誤差。此外，它對于“噪聲”數(shù)據(jù)和遠(yuǎn)離群點(diǎn)的數(shù)據(jù)較為敏感，只需少數(shù)的諸如此類的數(shù)據(jù)就可以對平均值產(chǎn)生很大的影響。

2.2　改進(jìn)的K均值聚類算法

由于初始簇中心的的選取對于K均值聚類算法的結(jié)果影響很大，不同點(diǎn)作為初始簇中心可能獲得不同的聚類結(jié)果，一旦選取錯誤的話極易導(dǎo)致算法生成很差的聚類結(jié)果，因此初始簇中心的選取至關(guān)重要。本文針對此問題提出一種基于傳統(tǒng)K均值算法的改進(jìn)算法，并且定義了新的函數(shù)，計(jì)算出每一個數(shù)據(jù)樣本對應(yīng)到此函數(shù)的值，選擇讓函數(shù)取得最大值的數(shù)據(jù)樣本作為算法的下一個聚類中心，進(jìn)而得到一種新的簇中心方法。該方法不僅可以考慮的到距離數(shù)據(jù)樣本分布密集區(qū)域較為遠(yuǎn)的數(shù)據(jù)樣本，也可以消除噪音點(diǎn)對于下一個簇中心選擇的影響，從而避免了傳統(tǒng)K均值算法的缺點(diǎn)。

算法描述：

Step1：初始化，所有數(shù)據(jù)樣本點(diǎn)xi，計(jì)算Di：

選擇使得取得最小值的點(diǎn)當(dāng)作最佳初始簇中心，并設(shè)置q=1。

Step3：通過計(jì)算尋找到下一個的簇中心，這里我們引入Ti：

運(yùn)算是的Ti取得最小值時(shí)的 數(shù)據(jù)樣本xi作為下一個簇的初始聚類中心點(diǎn)。

Step4：判斷程序終止條件，q=q+1，若q ≤ K，算法轉(zhuǎn)到step2，若q＞K，則算法終止。

該算法提出了一種通過對Ti的計(jì)算來獲得下一簇的最佳初始中心的方法，改進(jìn)了傳統(tǒng)K均值算法對聚類中心的選擇方式，并可以準(zhǔn)確快速的在所有數(shù)據(jù)樣本中挑選出一個周圍樣本分布較為密集的樣本作為下一簇的最佳聚類中心，并且這個中心點(diǎn)距離現(xiàn)有已存在的聚類中心都有相隔比較遠(yuǎn)的距離，這樣不僅可以避免了遠(yuǎn)離數(shù)據(jù)群點(diǎn)的樣本和噪音點(diǎn)對聚類結(jié)果的影響，也能夠規(guī)避傳統(tǒng)K均值算法采用隨機(jī)選取簇中心的方法所帶來的隨機(jī)性，大大的提高了算法的準(zhǔn)確性和可靠性。同時(shí)，本算法中引入的的計(jì)算可以讓后面計(jì)算過程中避免對數(shù)據(jù)樣本間距離的重復(fù)計(jì)算，極大的節(jié)省了計(jì)算機(jī)的運(yùn)算時(shí)間。本算法通過對尿沉渣圖像數(shù)據(jù)的實(shí)驗(yàn)測試表明該算法相較于傳統(tǒng)K均值算法在處理效果和運(yùn)算時(shí)間上均有所提升。

3　實(shí)驗(yàn)結(jié)果和分析

本文試驗(yàn)環(huán)境：Intel CPU，8G內(nèi)存，1T硬盤，Win7操作系統(tǒng)，Matlab 2013平臺。

實(shí)驗(yàn)數(shù)據(jù)來源與重慶市天海公司提供的尿沉渣圖像，在實(shí)驗(yàn)測試中分別使用傳統(tǒng)K均值算法與本文所提出的改進(jìn)K均值算法對圖像進(jìn)行處理，并進(jìn)行對比。在用K均值算法前，首先對圖像進(jìn)行預(yù)處理，經(jīng)邊緣檢測后，利用形態(tài)學(xué)運(yùn)算對圖像進(jìn)行孔洞填充，最后確定尿沉渣圖像有形成分坐標(biāo)。圖2（a）、（b）分別是一些通過分割得到的紅細(xì)胞和結(jié)晶。

圖2　分割后的有形成分

通過對算法運(yùn)算時(shí)間T和聚類誤差平方和E值進(jìn)行對比，證明本文所提出的改進(jìn)算法相比傳統(tǒng)的K均值算法在性能上得到較好的提升。在此選取了幾幅尿沉渣圖像分別用這兩種方法進(jìn)行處理，實(shí)驗(yàn)結(jié)果比較見表1所示。

表1　不同聚類分割算法的實(shí)驗(yàn)結(jié)果比較

由圖表1可以發(fā)現(xiàn)在相同圖片上分別運(yùn)行K均值聚類和改進(jìn)型的K均值聚類算法，通過其聚類的時(shí)間T和聚類誤差平方和E的比較，可以發(fā)現(xiàn)本文提出的改進(jìn)的算法相較于傳統(tǒng)的K均值算法不僅在準(zhǔn)確性方面有所提升，同時(shí)也縮短了算法的運(yùn)行時(shí)間。

4　結(jié)論

本文在傳統(tǒng)K均值算法的基礎(chǔ)上提出了一種改進(jìn)型的K均值算法，針對傳統(tǒng)算法聚類中心選取的隨機(jī)不確定性和噪音點(diǎn)對聚類結(jié)果造成的不良影響，本文所提改進(jìn)型K均值算法定義了一種新的目標(biāo)函數(shù)來挑選一個距離現(xiàn)有已存在簇中心較遠(yuǎn)且周圍樣本分布較為密集的數(shù)據(jù)樣本作為下一個簇的聚類中心，并選擇距離所有數(shù)據(jù)樣本均值最近的點(diǎn)作為第一個聚類的初始中心，從而解決了傳統(tǒng)K均值算法中選取聚類中心所帶來的不確定性因素和噪音點(diǎn)所導(dǎo)致的分割結(jié)果不準(zhǔn)確的問題，進(jìn)而得到了一種高效的改進(jìn)型K均值算法。通過實(shí)驗(yàn)證明 ，改進(jìn)型算法相比傳統(tǒng)K均值算法不僅可以得到更為準(zhǔn)確的聚類分割結(jié)果，而且在聚類時(shí)間上也要優(yōu)于傳統(tǒng)K均值算法。

[1]Aswani K C,Srinivas S.Concept lattice reduction using fuzzy K-means clustering[J].Expert System with Application,2010,37(3):2696-2704.

[2]Hassanzadeh T,Meybodi,M R.A new hybrid approach for data clustering using firefly algorithm and K-means[C].IEEE Intelligent Systems,2012:7-11.

[3]Yong-Ming L I,Zhou D, Zeng X P,et al.Research of Feature Selection of Red Cell and White Cell of Urinary Sediment Images Based on Genetic Algorithm Embedded with Multi-criteria[J].Journal of System Simulation,2008,20(14):253-282.

[4]Nath R,Jain R.Insulin Chart Prediction for Diabetic Patients Using Hidden Markov Model(HMM)and Simulated Annealing Method[C].Proceedings of the Second International Conference on Soft Computing for Problem Solving(SocProS 2012),December 28-30,2012.Springer India,2014:3-11.

[5]Erisoglu M,Calis N,Sakallioglu S.A new algorithm for initial cluster centers in K-means algorithm.Pattern Recognition Letters,2011(32):1701-1705.

[6]Saeedizadeh Z,Mehri Dehnavi A,Talebi A,et al.Automatic recognition of myeloma cells in microscopic images using bottleneck algorithm, modified watershed and SVM classifier[J].Journal of Microscopy,2016,261(1):46-56.

[7]Likas A,Vlassis M,Verbeek J.T he global K-means cluste ring algo rithm[J].P attern Recog nitio n,2003,36(2):451-461.

[8]Grigorios Tzortzis,Aristidis Likas.The min max K-means clustering algorithm[J].Pattern Recognition,2014:47(2):2505-2516.

[9]Kong Dexi,Kong Rui.A fast and effective kernel based K-Means clustering Algorithm[C].IEEE Intelligent Systems,2013:58-61.

[10]Hassanzadeh T,Meybodi,M R.A new hybrid approach for data clustering using firefly algorithm and K-means[C].IEEE Intelligent Systems,2012:7-11.

[11]Thakur P D,Patil M E.Traffic symbol recognition by means of image segmentation[J].World Journal of Science and Technology,2012,2(3):137-139．