基于改進(jìn)K-means聚類算法的金魚陰影去除及圖像分割方法

王 帥，劉世晶，唐 榮，陳 軍，劉興國(guó)

(中國(guó)水產(chǎn)科學(xué)研究院漁業(yè)機(jī)械儀器研究所，上海 200092)

運(yùn)動(dòng)魚類檢測(cè)是魚類行為量化研究中的關(guān)鍵技術(shù)和難題[1]。受光照條件和自身運(yùn)動(dòng)影響，魚類運(yùn)動(dòng)會(huì)產(chǎn)生隨機(jī)陰影噪聲，增加了圖像分割難度。復(fù)雜背景的目標(biāo)對(duì)象提取是目前運(yùn)動(dòng)檢測(cè)研究的熱點(diǎn)，目前尚未看到有關(guān)魚類圖像運(yùn)動(dòng)陰影去除方面的研究報(bào)道，但在運(yùn)動(dòng)人群及運(yùn)動(dòng)車輛檢測(cè)方面已經(jīng)開展大量的工作，梳理近年來(lái)的研究成果，相關(guān)研究主要聚焦在基于顏色特征分割方法和基于紋理特征分割方法兩大類?；陬伾姆椒ㄖ饕峭ㄟ^陰影的色度不變性分割目標(biāo)對(duì)象。Cucchiara等[2]在HSV顏色空間中使用色度、飽和度及亮度信息建立背景模型，分離樣本圖像的亮度及色度分量，確定陰影范圍；徐少飛等[3]發(fā)現(xiàn)一種基于顏色屬性的運(yùn)動(dòng)陰影消除算法；Sun等[4]利用C1C2C3色彩空間的光照不變性和HIS色彩空間中圖像的色度和亮度比值，實(shí)現(xiàn)陰影分割，但由于沒有考慮前景和背景差異度，增加了背景識(shí)別誤差?；诩y理信息的方法是利用陰影的紋理相似性實(shí)現(xiàn)背景識(shí)別。Leone等[5]發(fā)現(xiàn)一種利用Gabor函數(shù)進(jìn)行樣本圖像的紋理特征提取，從而檢測(cè)出陰影區(qū)域并去除；郭春鳳等[6]提出一種融合D1D2D3模型和LBP紋理特征的LPTD算子，實(shí)現(xiàn)運(yùn)動(dòng)目標(biāo)背景檢測(cè)；曹健等[7]提出一種將區(qū)域顏色融合圖像LBP紋理進(jìn)行不同環(huán)境下的運(yùn)動(dòng)陰影區(qū)域檢測(cè)。以上基于紋理信息的方法，雖然可以獲得一些效果，然而當(dāng)樣本圖像存在平坦區(qū)域或者目標(biāo)與背景紋理特征接近時(shí)，會(huì)產(chǎn)生較多誤分割現(xiàn)象。

聚類算法是利用不同類型特征之間的特征距離分割目標(biāo)對(duì)象，可融合多種不同特征，是一種常用的數(shù)據(jù)分類方法。目前常用的圖像分割聚類算法有K-means算法及FCM(Fuzzy c-means)算法，Rocha等[8]在HSV色彩空間通過利用K-means算法提取圖像樣本的背景，進(jìn)而去除陰影；巨志勇等[9]將K-means算法與分水嶺算法相結(jié)合進(jìn)行果蔬圖像分割；龔劬等[10]提出一種基于圖論的FCM圖像分割算法。相比于基于顏色特征和紋理特征的分割算法，聚類算法在背景分割方面具有較好的分割效果。但是，由于典型聚類算法對(duì)聚類中心和噪聲點(diǎn)較為敏感，易于陷入局部極小解，導(dǎo)致算法適應(yīng)性較差，尚不能滿足水下對(duì)象的背景分割要求。本研究以金魚為目標(biāo)對(duì)象，提出一種改進(jìn)的K-means背景去除方法。該方法采用馬氏距離作為距離度量算子，可優(yōu)化聚類個(gè)數(shù)以及初始聚類中心點(diǎn)選擇方法。

1 材料與方法

1.1 金魚圖像

試驗(yàn)用魚為草金魚，購(gòu)于上海市曲陽(yáng)花鳥市場(chǎng)，金魚平均體長(zhǎng)約為10 cm。試驗(yàn)開展前，先將魚放于養(yǎng)殖魚缸暫養(yǎng)數(shù)月，使其充分適應(yīng)試驗(yàn)環(huán)境。試驗(yàn)設(shè)備主要有小蟻微單相機(jī)(CCD：Sony IMX269 M4/3，分辨率5 184 × 3 888 pixels，焦距12～ 40 mm)、玻璃魚缸(100 cm×75 cm×40 cm)和相機(jī)固定支架等(圖1)。

圖1 試驗(yàn)設(shè)備Fig.1 Experimental equipment

試驗(yàn)過程：1)相機(jī)放置于玻璃魚缸中心正上方位置，垂直距離110 cm；2)為保證成像質(zhì)量，相機(jī)鏡頭與玻璃魚缸的水平面近似于垂直；3)在室內(nèi)正常的光照強(qiáng)度條件下采集圖像，相機(jī)焦距和光圈設(shè)置到正好可以完全拍攝玻璃魚缸，設(shè)置自動(dòng)白平衡；4)采用等比例方法壓縮圖像，綜合考慮圖像大小和分辨率，采用10倍壓縮比例，壓縮后圖像分辨率為518×388(圖2)。從圖2中可以看出，光線照射到運(yùn)動(dòng)的金魚身上產(chǎn)生了明顯的陰影區(qū)域，且陰影區(qū)域映射了金魚的體色。在室內(nèi)開放條件下，由于拍攝的時(shí)間不同，會(huì)有不同方向的入射光，因此會(huì)造成金魚樣本圖像產(chǎn)生不同形狀及不同大小的陰影區(qū)域，增加陰影去除的難度。

圖2 金魚圖像Fig.2 Goldfish image

1.2 研究方法

1.2.1 顏色空間轉(zhuǎn)換

尋找恰當(dāng)?shù)念伾臻g是有效進(jìn)行圖像分割的第一步，而且對(duì)使用的方法及策略至關(guān)重要[11]。目前比較常用的是RGB 顏色空間，可以用R、G、B三基色的組合來(lái)表示全部的顏色，這3個(gè)分量擁有極強(qiáng)的相關(guān)性，所以并不適應(yīng)于直接用來(lái)基于三分量獨(dú)立運(yùn)算的圖像分割[12-13]，可以使用RGB 顏色空間通過各種不同的變換得到其他顏色空間。Lab顏色空間是一種顏色度量的國(guó)際標(biāo)準(zhǔn)[14-15]，是一種與設(shè)備無(wú)關(guān)的色彩模型[16-17]，可以運(yùn)行于全部的圖像相關(guān)設(shè)備上，能夠確保圖像相關(guān)設(shè)備輸出圖像轉(zhuǎn)換后的顏色擁有一致性[18]，因此Lab顏色空間可以克服RGB等其他顏色空間對(duì)圖像設(shè)備色彩特性的依賴性。Lab顏色空間分開保存一幅圖像的色彩及亮度信息，其由L、a和b三個(gè)分量(通道)組成，并分別作為L(zhǎng)ab顏色空間的三個(gè)坐標(biāo)軸[19]。其中，L描述亮度，從純黑到純白，其對(duì)應(yīng)值域?yàn)閇0,100]；a描述從綠色(-)到紅色(+)；b描述從藍(lán)色(-)到黃色(+)；a和b對(duì)應(yīng)的值域?yàn)閇-128,127]。Lab顏色空間可以由RGB 顏色空間通過創(chuàng)建一個(gè)由X、Y和Z三個(gè)原色組成的色彩空間非線性轉(zhuǎn)換得到[16]。

1.2.2 改進(jìn)K-means算法

目前K-means算法被廣泛用于模式識(shí)別、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等方面[20]。通常情況下K-means算法擁有簡(jiǎn)易、效率高、容易理解、高性能及可拓展性好等優(yōu)勢(shì)，然而對(duì)于一些數(shù)據(jù)，該算法又有無(wú)法準(zhǔn)確確定初始聚類中心數(shù)目及其初始數(shù)值對(duì)聚類結(jié)果影響極大、一般具有圓形或者球形簇的聚類結(jié)果及其僅在定義簇的均值時(shí)才可以被使用、對(duì)于孤立的數(shù)據(jù)點(diǎn)或噪點(diǎn)比較敏感、易于陷入局部極小解等劣勢(shì)。為了解決以上問題，本研究提出了一種改進(jìn)的K-means算法，分別從去除噪點(diǎn)及孤立數(shù)據(jù)點(diǎn)、使用馬氏距離作為距離度量方法、明確聚類個(gè)數(shù)以及初始聚類中心點(diǎn)選擇等領(lǐng)域進(jìn)行優(yōu)化。

(1)中值濾波。由于拍攝環(huán)境條件的變化、光照及其電磁波等外界因素的影響，會(huì)造成拍攝圖像產(chǎn)生噪點(diǎn)及孤立的數(shù)據(jù)點(diǎn)，對(duì)于后續(xù)圖像的分割處理會(huì)帶來(lái)很大的干擾[21]。為了獲得好的分割結(jié)果，同時(shí)解決傳統(tǒng)算法對(duì)噪聲點(diǎn)及孤立數(shù)據(jù)點(diǎn)比較敏感這一問題，本研究使用中值濾波[21]對(duì)樣本圖像進(jìn)行預(yù)處理，盡可能去除噪聲點(diǎn)及孤立點(diǎn)造成的影響。

(2)馬氏距離。K-means算法一般采用歐式距離作為其距離相似度度量方法，然而歐式距離不區(qū)分樣本不同屬性間的差異，同時(shí)未能包含樣本總體變化和差異對(duì)距離大小帶來(lái)的影響，這往往不能符合實(shí)際使用要求。因此，本研究提出使用馬氏距離來(lái)代替歐式距離衡量樣本之間的相關(guān)性。馬氏距離是一種使用樣本間的方差與協(xié)方差來(lái)描述樣本集合的分布情況，不會(huì)受到樣本量綱和測(cè)量尺度的干擾，同時(shí)還能去除樣本變量間的相關(guān)性影響[22-23]。馬氏距離的數(shù)學(xué)解釋為：令樣本集P={x1,x2,…,xn}，其中n為樣本的個(gè)數(shù)。此時(shí)樣本xi，xj之間的馬氏距離dij為：

(3)群G為素?cái)?shù)冪階循環(huán)群.設(shè)有限群G的階為,由(1)和(2)知G為循環(huán)群.若s≥2,則生成元個(gè)數(shù)1)···(ps-1)≥2,故可選取兩個(gè)不同生成元x,y,再取p1階元a,p2階元b以及單位元1構(gòu)成子集N={1,a,b,x,y},此時(shí)的誘導(dǎo)子圖P(N)如圖2所示,由引理1知P(G)不是某圖的線圖.

(1)

式中：dij是樣本i到樣本j的馬氏距離；xi是第i個(gè)樣本的屬性向量；xj是第j個(gè)樣本的屬性向量；T是矩陣轉(zhuǎn)置符號(hào)；m是待測(cè)樣本的協(xié)方差矩陣。dij對(duì)于所有的i，j及k值應(yīng)該符合4個(gè)條件：只有在i=j時(shí)，dij=0；dij>0；dij=dji；dij≤dik+dkj。

(3)確定聚類個(gè)數(shù)K。選取DBI指標(biāo)(Davies-Bouldin)[24]評(píng)價(jià)K值的選取是否最佳。DBI指數(shù)是一個(gè)使用類簇內(nèi)數(shù)據(jù)的緊密情況來(lái)評(píng)價(jià)聚類算法聚類效果好壞的度量指標(biāo)，是計(jì)算類內(nèi)的距離之和與類間的距離之和的比值，本質(zhì)上屬于內(nèi)部評(píng)估。DBI值的計(jì)算步驟為[24]：

第一步，假設(shè)待測(cè)樣本中描述第i類內(nèi)的數(shù)據(jù)集合分散程度的分散度值為S，且其可由公式(2)得到：

(2)

第二步，令第i類的質(zhì)心與第j類的質(zhì)心間的歐幾里得距離為D，其表達(dá)式為：

(3)

第三步，令i和j類間的相似度值為R，利用分散度和歐幾里得距離的相互關(guān)系可以得到：

(4)

最后一步，DBI的值即是全部分類(各個(gè)分類和其它分類之間)的最大相似度的平均值，可由下式得到：

(5)

(4)初始聚類中心點(diǎn)選擇。首先將樣本數(shù)據(jù)集合中密度最大的數(shù)據(jù)點(diǎn)選擇為首個(gè)初始聚類中心點(diǎn)，并且使用該基本準(zhǔn)則尋找距離第一個(gè)聚類中心最大的點(diǎn)作為第二個(gè)初始聚類中心點(diǎn)，然后將離的最近的數(shù)據(jù)點(diǎn)全部分配到同一類簇。這樣選取初始聚類中心點(diǎn)可以解決傳統(tǒng)K-means算法有可能存在選擇事實(shí)上是同一分類內(nèi)的點(diǎn)作為初始聚類中心點(diǎn)的問題，同時(shí)可解決該算法有可能存在某個(gè)類簇將樣本數(shù)據(jù)集合中密度過高的點(diǎn)錯(cuò)誤分配到自己類別的問題[25]。初始聚類中心點(diǎn)具體選擇步驟為：設(shè)定一個(gè)閾值計(jì)算出樣本集各個(gè)數(shù)據(jù)點(diǎn)的密度，找出其中密度最大的一個(gè)數(shù)據(jù)點(diǎn)并設(shè)為第一個(gè)初始聚類中心點(diǎn)k1，然后計(jì)算其他數(shù)據(jù)點(diǎn)到k1的馬氏距離，找到其中距離最大的點(diǎn)即第二個(gè)初始聚類中心點(diǎn)，如此循環(huán)，找到K個(gè)初始聚類中心點(diǎn)結(jié)束。

2 結(jié)果與分析

2.1 顏色空間轉(zhuǎn)換分析

使用合適的顏色空間對(duì)于分割彩色樣本圖像來(lái)說至關(guān)重要。因?yàn)楫?dāng)同一張彩色樣本圖像使用不同的顏色空間進(jìn)行預(yù)處理時(shí)，不同顏色分量的灰度圖像會(huì)相差很大，所以應(yīng)該選擇可以很容易區(qū)分金魚目標(biāo)和背景的顏色分量。將金魚樣本圖像從RGB 顏色空間轉(zhuǎn)換到Lab 顏色空間，L、a及b分量圖像及對(duì)應(yīng)的直方圖(圖3)。因?yàn)長(zhǎng)表示圖像的亮度，和人眼的感知相關(guān)，而且從圖3d的L分量直方圖能夠得到，L分量中金魚的亮度較大，然而相對(duì)于背景顏色來(lái)說沒有顯著的差別，因此可以不考慮L分量。從圖3e、圖3f的a和b分量的直方圖可以看出金魚和背景的顏色基本一致，金魚與背景呈現(xiàn)出顯著的雙峰，因此，提取Lab顏色空間的a、b分量分割金魚與背景。

圖3 金魚圖像Lab各分量及其直方圖Fig.3 Each component of goldfish Lab image and its histogram

2.2 不同聚類算法分析

首先使用中值濾波算法去除采集金魚圖像的噪點(diǎn)，結(jié)果如圖4a所示。再將去除噪點(diǎn)后的彩色圖像從RGB顏色空間轉(zhuǎn)化到Lab顏色空間，結(jié)果如圖4b所示，然后使用改進(jìn)的K-means算法對(duì)其進(jìn)行聚類，其中距離相似度度量參數(shù)選擇馬氏距離，聚類結(jié)果如圖4c所示。

圖4 金魚運(yùn)動(dòng)陰影去除及圖像分割實(shí)驗(yàn)流程圖Fig.4 Experimental flow chart of goldfish motion shadow removal and image segmentation

為了驗(yàn)證算法的有效性，選擇含有多條樣本的金魚圖像，分別使用傳統(tǒng)K-means算法和FCM算法進(jìn)行陰影去除及圖像分割實(shí)驗(yàn)，結(jié)果如圖5所示。

圖5 3種不同算法陰影去除及圖像分割結(jié)果圖Fig.5 Shadow removal and image segmentation results using three different algorithms

與上述兩種算法相比，本文算法在去除陰影方面取得了更好的效果，目標(biāo)對(duì)象分割丟失特征較少，4條金魚的輪廓完整，紋理清楚，但是尾部出現(xiàn)部分丟失；使用傳統(tǒng)K-means算法和FCM算法得到的金魚雖然輪廓完整，但受陰影干擾，有一部分陰影并未完全去除，總體的分割效果并不好。

為了驗(yàn)證本文算法的有效性，引入誤差概率來(lái)對(duì)比三種算法的優(yōu)劣。從圖像分割結(jié)果來(lái)看，分割率低將會(huì)造成像素的錯(cuò)分，因此，被錯(cuò)分的像素?cái)?shù)量可以作為一種評(píng)價(jià)圖像分割質(zhì)量的數(shù)據(jù)標(biāo)準(zhǔn)。此時(shí)，誤差概率能夠由公式(6)計(jì)算得到：

PE=P(O)×P(B|O)+P(B)×P(O|B)

(6)

式中：P(O)為待處理圖像中的目標(biāo)所占比例的先驗(yàn)概率；P(B)為待處理圖像中的背景所占比例的先驗(yàn)概率；P(B|O)為把檢測(cè)目標(biāo)誤判為背景的概率；P(O|B)為把背景誤判為檢測(cè)目標(biāo)的概率。

針對(duì)采集到的具有不同陰影區(qū)域的200張金魚樣本圖像，使用誤差概率和運(yùn)行時(shí)間分別對(duì)基于改進(jìn)K-means算法、傳統(tǒng)K-means算法及FCM算法進(jìn)行對(duì)比分析，3種算法的平均誤分類概率及運(yùn)行時(shí)間見表2。

表2 3種算法圖像分割效果比較Tab.2 Image segmentation effect comparison of three algorithms

從表2可以看出，改進(jìn)K-means算法的平均誤分類的像素比率和平均運(yùn)行時(shí)間分別為2.48%和0.875 s，均好于后兩種算法。其中，傳統(tǒng)K-means聚類算法因?yàn)闊o(wú)法準(zhǔn)確確定聚類種類的數(shù)目，以及其值的敏感性、對(duì)噪聲點(diǎn)及孤立數(shù)據(jù)比較敏感、隨機(jī)選取聚類中心等缺點(diǎn)，致使其陰影去除及分割的效果不是很理想；FCM算法僅簡(jiǎn)單地從圖像的像素灰度值考慮，只是依賴像素的分布強(qiáng)度，并未去除異常的數(shù)據(jù)，且忽略了可用的空間位置信息，導(dǎo)致FCM算法對(duì)噪聲點(diǎn)極其敏感，因此其分割效果并未達(dá)到理想范圍。

3 討論

針對(duì)魚類行為研究，有效對(duì)圖像進(jìn)行預(yù)處理，提取準(zhǔn)確的前景信息，是開展魚類行為分析的前提。采用視覺技術(shù)測(cè)量魚類三維運(yùn)動(dòng)，仍需對(duì)單個(gè)相機(jī)拍攝圖像進(jìn)行預(yù)處理。因此，本研究從單個(gè)相機(jī)圖像處理技術(shù)入手，采用單目相機(jī)拍攝魚類運(yùn)動(dòng)圖片，研究背景分割技術(shù)，適用于魚類較少發(fā)生上下重疊的平面二維運(yùn)動(dòng)跟蹤場(chǎng)景，可直接應(yīng)用到三維運(yùn)動(dòng)圖像預(yù)處理中。提出的陰影去除及目標(biāo)分割方法能夠較好地分割魚類和背景，但當(dāng)目標(biāo)存在水平粘連時(shí)，僅僅依靠聚類算法不能滿足個(gè)體分割或者運(yùn)動(dòng)跟蹤前處理的圖像分割要求，下一步研究將結(jié)合輪廓識(shí)別和運(yùn)動(dòng)方向預(yù)估輔助定位目標(biāo)魚類，以期提高圖像分割效果。

復(fù)雜工況魚類背景去除，不可避免地會(huì)受到相似背景干擾，針對(duì)魚類目標(biāo)個(gè)體，主要干擾因素包括相似背景、魚類體色環(huán)境適應(yīng)性以及光照條件。本試驗(yàn)采用聚類算法去除陰影，聚類目標(biāo)為顏色空間，可充分利用背景和體色之間的顏色差異，適用于目標(biāo)對(duì)象體色與陰影差異較大的試驗(yàn)場(chǎng)景。此外，由于Lab顏色空間中的L分量能夠反應(yīng)光照變化，聚類時(shí)采用a、b分量而忽略L分量可有效降低光照變化的影響，因此，基于Lab顏色空間的聚類分割算法對(duì)彩色圖像和光照條件魯棒性較好。針對(duì)體色較暗或者具備顏色適應(yīng)性的目標(biāo)對(duì)象，下一步工作將結(jié)合對(duì)比度增強(qiáng)及輪廓預(yù)識(shí)別功能初步定位目標(biāo)魚類，然后引入圖像形態(tài)學(xué)處理技術(shù)開展精準(zhǔn)分割研究。

算法運(yùn)行時(shí)間是影響魚類運(yùn)動(dòng)分析效能的關(guān)鍵因素，本文提出的基于聚類的背景去除方法，作為圖像預(yù)處理算法，主要應(yīng)用在行為分析的前處理過程，原則上要求具備較快的處理速度。本文通過壓縮圖像、降低圖像分辨率提高算法運(yùn)算速度，單幀圖像的處理時(shí)間接近1 s，能夠滿足離線魚類運(yùn)動(dòng)量化分析的需要，但圖像處理時(shí)間還是較長(zhǎng)。所以，本研究下一步將引入底層編碼機(jī)制優(yōu)化本文算法，進(jìn)一步提高算法運(yùn)行效率。

4 結(jié)論

以金魚作為研究對(duì)象，提出了一種基于改進(jìn)的K-means聚類算法的金魚圖像陰影去除及圖像分割方法，效果較好。1)使用該方法對(duì)采集的200張具有不同陰影區(qū)域的金魚樣本圖像進(jìn)行分割試驗(yàn)，平均誤分類的像素比率和平均運(yùn)行時(shí)間分別為2.48%和0.875 s，可以較好地去除金魚圖像的陰影部分，好于使用傳統(tǒng)K-means聚類算法和FCM聚類算法的分割結(jié)果。2)采用Lab顏色空間表述圖像，可有效降低光照條件對(duì)圖像的影響，有利于解決不同背景下的陰影去除及圖像分割，提高算法的普適性。3)受算法本身運(yùn)行邏輯的限制，算法運(yùn)行速度較慢，因此，如何提高算法的運(yùn)行速度將是下一步研究的重點(diǎn)方向。

□