自適應(yīng)K-means圖像分割方法

王嘉棟，李寒松

(北京華航無(wú)線(xiàn)電測(cè)量研究所，北京 100013)

自適應(yīng)K-means圖像分割方法

王嘉棟，李寒松

(北京華航無(wú)線(xiàn)電測(cè)量研究所，北京 100013)

本文提出了一種自適應(yīng)K-means圖像分割方法，該方法通過(guò)用Otsu方法來(lái)初步選取閾值作為初始K-means聚類(lèi)中心，然后經(jīng)過(guò)K-means聚類(lèi)方法對(duì)圖像進(jìn)行分割，最后根據(jù)K-means獲得的聚類(lèi)中心與Otsu所確定的閾值進(jìn)行平均計(jì)算，作為圖像分割的閾值。實(shí)驗(yàn)結(jié)果表明：該方法自動(dòng)快速形成的分割閾值較為合理，對(duì)圖像能達(dá)到更好的分割效果，可以進(jìn)一步提高后續(xù)圖像匹配與定位的準(zhǔn)確性。

自適應(yīng)K-means；圖像分割；聚類(lèi)中心；Otsu

0 引言

圖像處理是圖像匹配定位的重要組成部分，因此要想使圖像匹配定位更加精確，首先要將圖像處理的工作做好，K均值方法是其一種新的方法。圖像分割是從圖像處理到圖像分析的關(guān)鍵步驟，所謂圖像分割就是將圖像中有意義的邊緣、區(qū)域等有意義的部分與背景圖像進(jìn)行分離，并且進(jìn)行標(biāo)記和定位，一個(gè)完整的目標(biāo)邊緣對(duì)后續(xù)圖像與定位的準(zhǔn)確性至關(guān)重要。因此，圖像分割的效果直接影響對(duì)圖像的理解以及后續(xù)對(duì)目標(biāo)的匹配定位，本文的算法可以將目標(biāo)區(qū)域的邊緣信息更加清晰完整地檢測(cè)出來(lái)，進(jìn)一步提高了后續(xù)圖像匹配與定位的準(zhǔn)確性。

目前，圖像分割的方法很多，根據(jù)不同評(píng)價(jià)標(biāo)準(zhǔn)，圖像分割可以劃分為不同種類(lèi)，本文圖像分割的方法可以粗略地分為三類(lèi)：1)基于直方圖的分割技術(shù)，包括閾值分割[1]和聚類(lèi)[2-3]等；2)基于鄰域的分割技術(shù)，包括邊緣檢測(cè)和區(qū)域增長(zhǎng)；3)基于物理性質(zhì)的分割技術(shù)，包括利用光照特性和物體表面特征等。

在大多數(shù)文章中，依靠K-means聚類(lèi)方法對(duì)圖像進(jìn)行分割的方法中，K-means聚類(lèi)的初始中心是靠隨機(jī)選擇的，但這樣帶來(lái)的結(jié)果是當(dāng)初始聚類(lèi)中心選取不當(dāng)時(shí)，會(huì)導(dǎo)致最終聚類(lèi)結(jié)果陷入局部最優(yōu)值，從而影響后續(xù)的圖像處理。因此，初始聚類(lèi)中心位置的選擇直接影響到聚類(lèi)劃分結(jié)果的好壞。

本文巧妙地將Otsu方法與K-means方法進(jìn)行結(jié)合，發(fā)揮了每種算法的優(yōu)勢(shì)，并創(chuàng)造出了一種新的圖像分割方法：通過(guò)用Otsu方法[4-6]來(lái)初步選取閾值作為初始K-means聚類(lèi)中心，然后經(jīng)過(guò)K-means聚類(lèi)方法對(duì)圖像進(jìn)行分割，最后根據(jù)K-means獲得的聚類(lèi)中心與Otsu所確定的閾值進(jìn)行平均計(jì)算，作為圖像分割的閾值。實(shí)驗(yàn)結(jié)果表明：該方法自動(dòng)快速形成的分割閾值較為合理，對(duì)圖像能達(dá)到更好的分割效果，使得目標(biāo)更加清晰，可以進(jìn)一步提高后續(xù)圖像匹配的準(zhǔn)確性。

1 K-means聚類(lèi)算法

MacQueen在1967年提出了K-means算法，其算法原理是使得聚類(lèi)域中所有點(diǎn)到聚類(lèi)中心距離的平方和達(dá)到最小值，從而對(duì)樣本進(jìn)行聚類(lèi)分割，該方法簡(jiǎn)單高效，在圖像分割領(lǐng)域中是一種經(jīng)典算法，在目標(biāo)定位中，該方法得到了有效的應(yīng)用。

K-means算法的大致過(guò)程如下：

1)首先隨機(jī)選擇K個(gè)初始聚類(lèi)中心；

2)分別計(jì)算每個(gè)點(diǎn)xi(i=1,2,…，n)到各個(gè)聚類(lèi)中心mi(i=1,2,…,p,…,k)的歐式距離大小，若D(xi,mp)≤D(xj,mi)，則分配xi點(diǎn)到第p類(lèi)；

4)進(jìn)行收斂判斷，通過(guò)步驟2)和3)的循環(huán)計(jì)算，直到聚類(lèi)中心mi不再發(fā)生變化，則聚類(lèi)劃分結(jié)束。

從K-means算法的基本步驟可以看出：1)初始聚類(lèi)中心的選擇不同會(huì)導(dǎo)致最后聚類(lèi)的結(jié)果不同；2)該算法極有可能導(dǎo)致最后的聚類(lèi)結(jié)果陷入局部最優(yōu)值。因此，本文提出了一種基于Otsu閾值分割的自適應(yīng)獲取初始聚類(lèi)中心的方法。

2 自適應(yīng)K-means圖像分割方法

2.1Otsu多閾值分割劃分聚類(lèi)中心的方法

選取最佳閾值使得用該閾值分割圖像得到的兩類(lèi)具有最好的分離性，即計(jì)算得到的兩類(lèi)的類(lèi)間方差達(dá)到最大值或者類(lèi)內(nèi)方差達(dá)到最小值。

Otsu算法得到的灰度值T就是將圖像中目標(biāo)與背景劃分的最佳劃分界限，當(dāng)圖像比較簡(jiǎn)單時(shí)，可以將圖像劃分為兩類(lèi)，其中每類(lèi)的聚類(lèi)中心從灰度值T左右兩端分別自動(dòng)選取，這樣可以避免陷入局部最優(yōu)值。

當(dāng)圖像比較復(fù)雜，存在較多目標(biāo)信息時(shí)，可以首先將直方圖用Otsu算法進(jìn)行直方圖多閾值分割，將圖像分成多個(gè)類(lèi)，使得多個(gè)類(lèi)的類(lèi)間方差達(dá)到最大，每個(gè)類(lèi)的類(lèi)內(nèi)方差達(dá)到最小，由此得到的分割閾值就是最佳分割閾值。

假設(shè)圖像有背景及目標(biāo)共計(jì)M個(gè)待區(qū)分的類(lèi)C0,C1,…,CM-1，其中C0與C1之間的閾值為T(mén)1，C1與C2之間的閾值為T(mén)2，則根據(jù)Otsu算法將獲得M-1個(gè)分割閾值，分別是T1,T2,…,TM-1。

則C0到CM-1對(duì)應(yīng)的概率和均值分別如下：

則類(lèi)間方差為：

pCM-1[μCM-1-μ]2

2.2 自適應(yīng)K-means圖像分割方法

本文算法流程：

1)將K個(gè)Otsu的分割閾值T1,T2,…,TK作為K-means的初始聚類(lèi)中心；

2)分別計(jì)算每個(gè)點(diǎn)xi(i=1,2,…，n)到各個(gè)聚類(lèi)中心Ti(i=1,2,…,p,…,K)的歐式距離大小，若D(xi,Tp)≤D(xj,Ti)，則分配xi點(diǎn)到第p類(lèi)；

4)進(jìn)行收斂判斷，通過(guò)步驟2)和3)的循環(huán)計(jì)算，直到聚類(lèi)中心ti不再發(fā)生變化，則聚類(lèi)劃分結(jié)束；

5)將聚類(lèi)中心ti與對(duì)應(yīng)的Otsu的分割閾值Ti相加除二得到最后的圖像分割閾值Mi；

6)用新的圖像分割閾值M1,M2,…,MK對(duì)圖像進(jìn)行分割。

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

為了驗(yàn)證本文自適應(yīng)K-means算法，本文進(jìn)行了大量的仿真對(duì)比測(cè)試，由于篇幅的限制，在這一節(jié)中將部分結(jié)果內(nèi)容進(jìn)行展示以驗(yàn)證本文算法的效果，將本文算法與傳統(tǒng)K-means算法進(jìn)行比較分析，實(shí)驗(yàn)結(jié)果如圖1～圖3所示(適應(yīng)典型場(chǎng)景)。

(a)原圖

(b)K-means算法分兩類(lèi)

(c)本文算法分兩類(lèi)圖1 分兩類(lèi)時(shí)，本文算法與K-means算法效果對(duì)比圖Fig.1 The contast of the method of the paper and the K-means when divided into two categories

(a)原圖

(b)K-means分三類(lèi)

(c)本文算法分三類(lèi)圖2 分三類(lèi)時(shí)，本文算法與K-means算法效果對(duì)比圖 Fig.2 The contast of the method of the paper and the K-means when divided into three categories

(a)原圖

(b)K-means分四類(lèi)

(c)本文算法分四類(lèi)圖3 分四類(lèi)時(shí)，本文算法與K-means算法效果對(duì)比圖 Fig.3 The contast of the method of the paper and the K-means when divided into four categories

從圖1～圖3的對(duì)比中可以看出，隨著聚類(lèi)中心數(shù)的增加，分類(lèi)的效果逐漸明顯，目標(biāo)邊緣更加清晰，可以更好地定位目標(biāo)，并且本文算法比傳統(tǒng)的K-means算法更清晰地將背景與目標(biāo)分割出來(lái)。

表1是兩種算法針對(duì)人圖像的性能對(duì)比，表2是兩種算法針對(duì)rice圖像的性能對(duì)比。其中閾值是根據(jù)本文算法計(jì)算得到的分割閾值，準(zhǔn)確率是根據(jù)檢測(cè)到的圖像邊緣像素?cái)?shù)與原圖像邊緣像素?cái)?shù)的比值來(lái)計(jì)算的，并且根據(jù)最后分割的準(zhǔn)確率進(jìn)行對(duì)比，準(zhǔn)確率越高，說(shuō)明圖像邊緣檢測(cè)的越完整，為后續(xù)圖像匹配提供了完整的待檢測(cè)目標(biāo)，提高了后續(xù)圖像定位的精確度。

表1 兩種算法的性能對(duì)比(人)

表2 兩種算法的性能對(duì)比(rice)

由此可知，用傳統(tǒng)的K-means算法雖然能顯示部分圖像細(xì)節(jié)，但是還有很多部分的細(xì)節(jié)信息沒(méi)有顯示出來(lái)，目標(biāo)定位不清晰，并且一些不太清晰的邊緣會(huì)漏檢。尤其是圖3，用普通K-means算法分類(lèi)會(huì)將一些較亮背景劃分為目標(biāo)信息，而用本文算法能根據(jù)Otsu獲取的閾值進(jìn)行聚類(lèi)的調(diào)整，從而減少背景較亮信息的干擾，使得最后的分類(lèi)結(jié)果更加清楚。這對(duì)于以后檢測(cè)目標(biāo)具有很大的現(xiàn)實(shí)意義，能更精確地把目標(biāo)從背景中分割出來(lái)，從而為后續(xù)目標(biāo)檢測(cè)、目標(biāo)跟蹤、目標(biāo)識(shí)別打下堅(jiān)實(shí)的基礎(chǔ)。

4 結(jié)論

本文通過(guò)用Otsu方法來(lái)初步選取閾值作為初始聚類(lèi)中心，然后經(jīng)過(guò)K-means聚類(lèi)方法對(duì)圖像進(jìn)行分割，最后根據(jù)Otsu方法所確定的閾值對(duì)聚類(lèi)結(jié)果進(jìn)行適當(dāng)調(diào)整。實(shí)驗(yàn)結(jié)果表明：該方法自動(dòng)快速形成的K-means聚類(lèi)中心較為合理，對(duì)圖像能達(dá)到更好的分割效果，使得目標(biāo)邊緣信息更加準(zhǔn)確，可以進(jìn)一步提高后續(xù)圖像匹配與定位的準(zhǔn)確性。下一步，將針對(duì)更加復(fù)雜的背景與目標(biāo)進(jìn)行研究，使得目標(biāo)的定位更加準(zhǔn)確，目標(biāo)的邊緣更加清晰，為以后的圖像匹配與定位奠定基礎(chǔ)。

[1] 陳崢，石勇鵬，吉書(shū)鵬.一種改進(jìn)的Otsu圖像閾值分割算法[J]. 激光與紅外，2012，42(5)：584-588.

[2] 謝娟英，蔣帥，王春霞，等.一種改進(jìn)的全局K均值聚類(lèi)算法[J]. 陜西師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2010，38(2)：18-22.

[3] 江健生，朱會(huì)萍.基于直方圖的K-means聚類(lèi)中心自動(dòng)檢測(cè)方法[J]. 廊坊師范學(xué)院學(xué)報(bào)(自然科學(xué)版)，2013，13(2)：49-52.

[4] 何志勇，孫立寧，陳立國(guó).Otsu準(zhǔn)則下分割閾值的快速計(jì)算[J]. 電子學(xué)報(bào)，2013，41(2)：267-272.

[5] 李惠光，姚磊，石磊.改進(jìn)的Otsu理論在圖像閾值選取中的應(yīng)用[J]. 計(jì)算機(jī)仿真，2007，24(4)：216-220.

[6] 尹奎英，劉宏偉，金林.快速的Otsu雙閾值SAR圖像分割法[J]. 吉林大學(xué)學(xué)報(bào)(工學(xué)版)，2011，41(6)：1760-1765.

Self-AdaptiveK-means on the Method of Image Segmentation

WANG Jia-dong, LI Han-song

(Beijing Huahang Radio Measurement Research Institute，Beijing 100013,China)

This paper proposes an adaptiveK-means about image segmentation method,the method uses Otsu to preliminarily select threshold as the initialK-meansclustering centers,and then the image is segmentated through theK-means clustering method, finally, according to the obtained cluster centers and threshold by Otsu, the average is determined as the threshold of the image segmentation.The experimental results show that:the segmentation threshold is reasonable and the image can achieve better segmentation results.

AdaptiveK-means;Image segmentation;Clustering centers;Otsu

10.19306/j.cnki.2095-8110.2016.05.013

2014-10-11；

2015-04-10。

王嘉棟(1990 - )，男，碩士，主要從事目標(biāo)檢測(cè)、識(shí)別方面的處理。E-mail:1324564709@qq.com

U666.12

A

2095-8110(2016)05-0066-04