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

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

1　引言

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

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

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

2　K均值聚類算法

2.1　傳統的K均值聚類算法

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

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

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

③根據聚類的結果，重新計算K個聚類的中心：

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

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

2.2　改進的K均值聚類算法

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

算法描述：

Step1：初始化，所有數據樣本點xi，計算Di：

選擇使得取得最小值的點當作最佳初始簇中心，并設置q=1。

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

運算是的Ti取得最小值時的 數據樣本xi作為下一個簇的初始聚類中心點。

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

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

3　實驗結果和分析

本文試驗環境：Intel CPU，8G內存，1T硬盤，Win7操作系統，Matlab 2013平臺。

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

圖2　分割后的有形成分

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

表1　不同聚類分割算法的實驗結果比較

由圖表1可以發現在相同圖片上分別運行K均值聚類和改進型的K均值聚類算法，通過其聚類的時間T和聚類誤差平方和E的比較，可以發現本文提出的改進的算法相較于傳統的K均值算法不僅在準確性方面有所提升，同時也縮短了算法的運行時間。

4　結論

本文在傳統K均值算法的基礎上提出了一種改進型的K均值算法，針對傳統算法聚類中心選取的隨機不確定性和噪音點對聚類結果造成的不良影響，本文所提改進型K均值算法定義了一種新的目標函數來挑選一個距離現有已存在簇中心較遠且周圍樣本分布較為密集的數據樣本作為下一個簇的聚類中心，并選擇距離所有數據樣本均值最近的點作為第一個聚類的初始中心，從而解決了傳統K均值算法中選取聚類中心所帶來的不確定性因素和噪音點所導致的分割結果不準確的問題，進而得到了一種高效的改進型K均值算法。通過實驗證明 ，改進型算法相比傳統K均值算法不僅可以得到更為準確的聚類分割結果，而且在聚類時間上也要優于傳統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．