時(shí)顥，賴惠成，覃錫忠

新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊 830046

粒子群與K均值混合聚類的棉花圖像分割算法

時(shí)顥，賴惠成，覃錫忠

新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊 830046

1 引言

我國(guó)棉花種植地域廣闊，所需棉花采摘?jiǎng)趧?dòng)力極大，隨著機(jī)器人在農(nóng)業(yè)生產(chǎn)過程中的逐步應(yīng)用，研究基于圖像處理的采棉機(jī)器人技術(shù)具有相當(dāng)大的實(shí)用價(jià)值和現(xiàn)實(shí)意義。棉花分割是采棉機(jī)器人視覺系統(tǒng)的關(guān)鍵技術(shù)之一，是采棉機(jī)器人中棉花匹配、三維重構(gòu)技術(shù)的基礎(chǔ)。迄今關(guān)于棉花圖像分割的相關(guān)研究有：韋皆頂[1]等選取HSV模型中與亮度無關(guān)的S通道作為棉花圖像的特征，一定程度去除了圖像明暗變化對(duì)分割效果的影響，但由于分割模型過于簡(jiǎn)單，穩(wěn)定性不高；王勇等[2]根據(jù)棉花與背景的色差信息，提出利用（R-B）、（B-G）的差值進(jìn)行分割；王玲[3]研究了不同顏色空間下的棉花分割，發(fā)現(xiàn)在HIS和Lab顏色空間經(jīng)閾值分割后噪聲較低；董建明[4]提出了微粒群算法（PSO）優(yōu)化最小誤差分割算法，圖像分割的效果和速度都得到了一定的提高。前人的這些方法算法復(fù)雜度低，但受光照和陰影的影響較大，難以準(zhǔn)確分割各種復(fù)雜情況下的棉花。本文在上述研究的基礎(chǔ)上提出了在YCbCr顏色空間下，利用粒子群優(yōu)化（PSO）和K均值混合聚類算法進(jìn)行分割，得到了較好的分割效果。

2 顏色空間和方法的選取

2.1 顏色空間的選擇

在RGB顏色空間中，由于R、G、B分量之間有很高的相關(guān)性，對(duì)同一顏色屬性，在不同光照條件下，R、G、B值很分散，色彩表示不均勻，兩個(gè)顏色的差異不適合用該顏色空間中的兩點(diǎn)之間的距離表示。HSV顏色空間能將亮度分量，但從RGB顏色空間轉(zhuǎn)換到HSV顏色空間需要開方、反三角函數(shù)操作，復(fù)雜度高，所需計(jì)算量大，并且在亮度值和飽和度較低的情況下，采用HIS或者HSV顏色空間計(jì)算出來的H分量是不可靠的。YCbCr顏色空間由亮度分量Y，藍(lán)色色度分量Cb和紅色色度分量Cr組成。從RGB顏色空間到Y(jié)CbCr顏色空間的轉(zhuǎn)換公式如下：

基于YCbCr顏色空間中色度分量和亮度分量相互獨(dú)立、YCbCr顏色空間與RGB顏色空間存在一種線性變換關(guān)系，不同亮度下，在YCbCr空間內(nèi)亮度范圍的變化量很大，而色度范圍的變化量很小，有利于光照變化圖像的處理，因此選擇YCbCr顏色空間[5]。

2.2 粒子群算法介紹

粒子群算法（PSO）是基于群體智能理論的優(yōu)化算法，通過群體中粒子間的合作與競(jìng)爭(zhēng)產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索。與進(jìn)化算法類似[6]，PSO先將系統(tǒng)初始化為一組隨機(jī)解，然后通過迭代搜尋最優(yōu)值，但是其采用的速度-位移模型操作簡(jiǎn)單，避免了復(fù)雜的遺傳操作，它特有的記憶使其可以動(dòng)態(tài)跟蹤當(dāng)前的搜索情況調(diào)整其搜索策略。由于每代種群中的解具有“自我”學(xué)習(xí)提高和向“他人”學(xué)習(xí)的雙重優(yōu)點(diǎn)，從而能在較少的迭代次數(shù)內(nèi)找到最優(yōu)解。

在PSO算法中，先將系統(tǒng)初始化為一組隨機(jī)解，然后通過迭代搜尋最優(yōu)值。粒子群在一個(gè)n維空間中搜索，其中的每個(gè)粒子所處的位置都表示問題的一個(gè)解。粒子通過不斷調(diào)整自己的位置X來搜索新解。每個(gè)粒子都能記住自己搜索到的最好解，記做Pid，以及整個(gè)粒子群經(jīng)歷過的最好的位置，即目前搜索到的最優(yōu)解，記做Pgd。在迭代過程中，微粒第d維速度與位置的迭代式為：

式中，ω為慣性權(quán)值，η1，η2為飛向自身最好位置方向和全局最好位置的學(xué)習(xí)因子，rand()為隨機(jī)數(shù)生成函數(shù)。

從式（2）和式（3）可以看出，粒子的移動(dòng)方向由三部分決定，自己原有的速度Vid，與自己最佳經(jīng)歷的距離(Pid-Xid)和與群體最佳經(jīng)歷的距離(Pgd-Xid)，并分別由權(quán)重系數(shù)ω，η1和η2決定其相對(duì)重要性[7-9]。

2.3 K-means算法介紹

K均值聚類算法[10-11]是通過找到特征空間中像素值的空間聚類，并把每一個(gè)像素劃分到不同的聚類中來實(shí)現(xiàn)圖像的分割。假設(shè)一組數(shù)據(jù)包含K個(gè)聚類，其中每個(gè)聚類包含m個(gè)點(diǎn)，若聚類中心為Zk，則總的類間離散度和：

其中，Xi為d維模式向量，d(Xi，Zk)為樣本到對(duì)應(yīng)聚類中心距離，JC為各類樣本到對(duì)應(yīng)聚類中心距離的總和。這里d(Xi，Zk)為歐式空間的距離，即d(Xi，Zk)=‖Xi-Zk‖。而K均值聚類算法通過迭代，使總的類間離散度JC最小，即使每個(gè)類內(nèi)距離盡可能小，而類間距離盡可能大。

K均值聚類算法的具體步驟如下：

（1）隨機(jī)選取K個(gè)聚類中心。

（2）根據(jù)每個(gè)聚類對(duì)象的均值，計(jì)算每個(gè)像素到K個(gè)聚類中心的距離，找出最小距離，并且把該像素歸為該聚類中心的類別。

（3）計(jì)算每個(gè)有變化聚類的均值，重新調(diào)整K個(gè)聚類中心。

（4）判斷新的聚類中心是否和上次結(jié)果相同，若不同返回步驟（2），直到每個(gè)聚類不再發(fā)生改變?yōu)橹埂?/p>

3 粒子群與K均值混合聚類算法

K均值聚類算法因其算法簡(jiǎn)單、收斂速度快等優(yōu)點(diǎn)，在數(shù)據(jù)挖掘、圖像分割、模式識(shí)別、特征提取等諸多領(lǐng)域得到了廣泛應(yīng)用，然而傳統(tǒng)的K均值算法存在兩個(gè)固有的缺點(diǎn)：對(duì)初始值敏感，易陷入局部最優(yōu)，PSO優(yōu)化算法的出現(xiàn)為解決這一問題提供了新的思路。通過對(duì)以往文獻(xiàn)分析發(fā)現(xiàn)，如何能充分利用PSO的全局搜索能力以及K均值算法精確的局部解搜索能力，且在提高解精度的同時(shí)加快算法的收斂速度是提高PSO+K均值混合聚類算法的關(guān)鍵所在。

3.1 粒子群優(yōu)化算法

由文獻(xiàn)[12]知，如果ω隨算法迭代的進(jìn)行而線性減小，將顯著地改善算法的收斂性能[12-13]。初始化時(shí)設(shè)置最大加權(quán)系數(shù)ωmax，最小加權(quán)系數(shù)ωmin和算法最大迭代次數(shù)runMax，run為當(dāng)前迭代次數(shù)，則有：

3.2 確定K均值算法操作時(shí)機(jī)

群體適應(yīng)度方差反映的是粒子群中所有粒子的“收斂”程度[14]。σ2越小，則粒子群趨于收斂；反之，適應(yīng)度不同粒

為了將PSO算法和K均值聚類算法有機(jī)結(jié)合，首先要確定K均值算法的操作時(shí)機(jī)。事實(shí)上當(dāng)PSO算法在進(jìn)行全局隨機(jī)搜索階段時(shí)，不需進(jìn)行K均值算法，這樣可以最大程度地利用PSO算法向著全局解子空間逼近，加快算法的收斂速度。當(dāng)PSO算法進(jìn)入收斂狀態(tài)，此時(shí)引入K均值算法可以提高解的局部搜索能力，加快算法的收斂速度。于是真正實(shí)現(xiàn)PSO算法與K均值算法的有機(jī)結(jié)合的關(guān)鍵是確定PSO算法何時(shí)收斂。而PSO算法在收斂的情況下，粒子群中各粒子的位置一致即各粒子適應(yīng)度相同。因此，研究PSO中所有粒子適應(yīng)度的整體變化就可以跟蹤粒子群的狀態(tài)，判斷算法是否收斂。

設(shè)粒子群的粒子數(shù)目為n，fi為第i個(gè)粒子的適應(yīng)度，favg為粒子群目前的平均適應(yīng)度，粒子群的群體適應(yīng)度方差σ2的定義如下：子群則處于隨機(jī)搜索階段。因此，當(dāng)群體適應(yīng)度方差小于某一個(gè)閾值時(shí)，說明PSO算法進(jìn)入收斂階段這時(shí)開始執(zhí)行K均值進(jìn)行局部解精確搜索，這樣既提高了混合聚類算法全局解搜索性能，加快了收斂速度，同時(shí)解的精度也隨之增加。

3.3 算法結(jié)合具體操作流程

本文利用粒子群適應(yīng)度方差來確定K均值算法操作時(shí)機(jī)，實(shí)現(xiàn)PSO算法與K均值算法的有機(jī)結(jié)合，增強(qiáng)算法局部搜索能力的同時(shí)加快了算法的收斂速度。

下面是算法的具體步驟：

（1）種群的初始化。在初始化粒子時(shí)，先將每個(gè)樣本隨機(jī)指派為某一類，作為最初的聚類劃分，并計(jì)算各類的聚類中心、粒子的適應(yīng)度，初始化粒子的速度，設(shè)置最大加權(quán)系數(shù)ωmax，最小加權(quán)系數(shù)ωmin和最大迭代次數(shù)runMax。

（2）對(duì)每個(gè)粒子，比較它當(dāng)前位置的適應(yīng)度值和它經(jīng)歷過的最好位置的適應(yīng)度，如果更好，更新Pid。

（3）對(duì)每個(gè)粒子，比較它當(dāng)前位置的適應(yīng)度值和群體所經(jīng)歷的最好位置的適應(yīng)度值，如果更好，更新Pgd。

（4）根據(jù)式（2）和式（3）調(diào)整粒子的速度和位置。

（5）根據(jù)式（6）判斷當(dāng)前粒子群是否到達(dá)收斂狀態(tài)，若群體適應(yīng)度方差σ2小于閾值，則粒子進(jìn)入K均值優(yōu)化階段，否則轉(zhuǎn)步驟（2）。

（6）K均值優(yōu)化。

對(duì)于新一代粒子，按照以下的K均值算法進(jìn)行優(yōu)化：

①根據(jù)粒子的聚類中心編碼，按照最近鄰法則，來確定對(duì)應(yīng)該粒子的聚類劃分。

②按照聚類劃分，計(jì)算新的聚類中心，更新粒子的適應(yīng)度值，取代原來的編碼值。由于K均值具有較強(qiáng)的局部搜索能力，因此引入K均值優(yōu)化后的粒子群算法的收斂速度可以大大提高。

③如果達(dá)到結(jié)束條件（足夠好的位置或最大迭代次數(shù)），則結(jié)束，否則轉(zhuǎn)步驟②。

在使用粒子群算法的過程中，在第（6）步對(duì)新一代個(gè)體進(jìn)行重新劃分類別時(shí)，有可能會(huì)有空的聚類出現(xiàn)。如果出現(xiàn)空的聚類，則隨機(jī)地從其他某個(gè)非空的聚類中取出距離聚類中心最遠(yuǎn)的模式向量，將該向量放入空聚類，重復(fù)這個(gè)過程，直到劃分中沒有空聚類為止。

本算法采用粒子群算法有較強(qiáng)的全局搜索能力的優(yōu)勢(shì)確定棉花圖片的聚類中心，再根據(jù)K均值收斂速度快，局部搜索能力強(qiáng)的特點(diǎn)對(duì)圖像進(jìn)行分割，可以較好地解決粒子群算法收斂速度慢及K均值算法對(duì)初始聚類中心敏感的缺點(diǎn)。

3.4 連通域面積去噪

粒子群與K均值混合聚類后的圖像存在著將背景多余信息錯(cuò)誤分割出來的過分割區(qū)域，鑒于這部分誤差在二值圖中的面積相比于目標(biāo)區(qū)域要小得多且不連通，因此本文采用連通域去噪的方法[15]。首先獲取分割后圖像中每一塊白色連通區(qū)域的面積，通過統(tǒng)計(jì)確定一個(gè)閾值T，將面積小于閾值T的連通區(qū)域去除。為了去除棉花內(nèi)部的噪聲，將上述步驟得到的二值圖像進(jìn)行反色處理，再使用區(qū)域標(biāo)記法去除噪聲，最后再做一次反色處理得到分割圖像。

4 實(shí)驗(yàn)結(jié)果與分析

為了評(píng)價(jià)分割效果，本文分別進(jìn)行了兩組對(duì)比，第一組為在YCbCr空間下將PSO聚類算法與本文算法進(jìn)行比較，仿真后的分割圖如圖1所示。

圖1 YCbCr空間下不同算法對(duì)比圖

可以看出，PSO聚類算法在YCbCr顏色空間下雖然能完整地分割出棉花，但存在比較大的噪聲，尤其是細(xì)節(jié)部分無法準(zhǔn)確將棉莢、棉葉分割為背景，通過連通域面積去噪無法有效去除跟棉花相連處的噪聲。

第二組為本文提出的粒子群與K均值混合聚類算法分別在HSV顏色空間和YCbCr顏色空間下進(jìn)行分割對(duì)比，并選取棉花在陰影及強(qiáng)光照條件下的典型圖像，仿真后的分割圖如圖2、圖3所示。

圖2 棉花在陰影條件下的情況

圖3 棉花在強(qiáng)光照射下的情況

通過對(duì)比可知，自然條件下的棉花圖片轉(zhuǎn)換到HSV顏色空間下分割沒辦法很好地解決光照帶來的影響，尤其是強(qiáng)光照下分割誤差會(huì)更大，并且RGB顏色空間到HSV顏色空間的轉(zhuǎn)換較復(fù)雜，影響分割效率。

由此可知，粒子群與K均值混合聚類算法在YCbCr顏色空間下能有效地解決這些問題，將棉莢、棉葉成功分割為背景，在強(qiáng)光照和陰影情況下都能對(duì)棉花圖片準(zhǔn)確地分割并很好地保留了細(xì)節(jié)特點(diǎn)。

5 結(jié)論

YCbCr空間將亮度與色差分離并與RGB空間存在線性轉(zhuǎn)換關(guān)系，本文在YCbCr顏色空間下對(duì)棉花圖片進(jìn)行粒子群與K均值混合聚類分割，能夠有效克服光照、陰影帶來的影響，實(shí)現(xiàn)了全局解搜索能力與收斂速度的平衡，其分割穩(wěn)定性、分割精度優(yōu)于傳統(tǒng)PSO聚類的分割方法，可以將各種復(fù)雜環(huán)境下的棉花圖像準(zhǔn)確有效地分割，為采棉機(jī)器人自動(dòng)化采摘奠定基礎(chǔ)。

[1]韋皆頂，費(fèi)樹岷，汪木蘭，等.基于HSV顏色模型的自然場(chǎng)景下棉花圖像分割策略研究[J].棉花學(xué)報(bào)，2008，20（1）：34-38.

[2]王勇，沈明霞，姬長(zhǎng)英.采摘期成熟棉花不同部位顏色識(shí)別分析[J].農(nóng)業(yè)工程學(xué)報(bào)，2007，23（4）：183-185.

[3]王玲，王萍，陳兵林，等.基于顏色閾值的田間籽棉圖像分割技術(shù)[J].作物學(xué)報(bào)，2010，36（3）：503-507.

[4]董建明，胡覺亮.基于PSO算法的圖像分割方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006（18）.

[5]劉金帥，賴惠成，賈振紅.基于YCbCr顏色空間和Fisher判別分析的棉花圖像分割研究[J].作物學(xué)報(bào)，2011，37（7）.

[6]劉成洋，閻昌琪.粒子群遺傳算法及其應(yīng)用[J].核動(dòng)力工程，2012，33（4）.

[7]周馳，高海兵.粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2003（12）：7-12.

[8]高金雍，唐紅梅.一種基于改進(jìn)PSO和FCM的圖像分割算法[J].河北工業(yè)大學(xué)學(xué)報(bào)，2011，40（6）.

[9]張新娟，雷秀娟.改進(jìn)PSO算法在二維最佳閾值圖像分割中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（26）：207-209.

[10]王易循，趙勛杰.基于K均值聚類分割彩色圖像算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件，2010，27（8）：127-130.

[11]LiM J，Ng M K.Agglomerative fuzzy K-means clustering algorithm with selection of number of clusters[J].IEEE Τransactions on Knowledge and Data Engineering，2008，20（11）.

[12]呂振肅，侯志榮.自適應(yīng)變異的粒子群優(yōu)化算法[J].電子學(xué)報(bào)，2004，32（3）.

[13]程萬盛，臧希哲.面向Otsu閾值搜索的PSO慣性因子改進(jìn)方法[J].光學(xué)精密工程，2008，16（10）.

[14]陳茂源，吳國(guó)平.基于PSO改進(jìn)的OΤSU圖像分割方法[J].微計(jì)算機(jī)應(yīng)用，2009（12）.

[15]孫建成，曾培峰.二值圖像的區(qū)域標(biāo)識(shí)與噪聲去除[J].天津工業(yè)大學(xué)學(xué)報(bào)，2006，25（1）.

SHI Hao,LAI Huicheng,QIN Xizhong

School of Information Science and Engineering,Xinjiang University,Urumqi 830046,China

Image segmentation of cotton is the key step of the cotton picker robot vision system.In the complex environment of the cotton fields of the strong light,shadow,etc.accurately and effectively splitting cotton,helps to determine its position in threedimensional space.In accordance with the characteristics of cotton pictures,a method of Particle Swarm Optimization（PSO）and K-means hybrid clustering in YCbCr color space is proposed.Τhis approach reinforces the exploitation of global optimum of the PSO algorithm.In order to avoid the premature convergence and speed up the convergence,traditional K-means algorithm is used to explore the local search space more efficiently dynamically according to the variation of the particle swarm’s fitness variance.Τhe experiment results show that this method can segment cotton image with the complex background,and is more effective than the traditional PSO and K-means algorithm.

cotton segmentation;YCbCr color space;K-means algorithm;Particle Swarm Optimization（PSO）algorithm

棉花分割是采棉機(jī)器人視覺系統(tǒng)的關(guān)鍵步驟，在強(qiáng)光照、陰影等復(fù)雜的棉田環(huán)境下準(zhǔn)確有效地分割棉花，有助于確定其在三維空間的位置。針對(duì)棉花圖片的特點(diǎn)，提出在YCbCr顏色空間下，采用粒子群（PSO）和K均值混合聚類算法，提高了聚類算法的全局搜索能力，根據(jù)群體適應(yīng)度方差來確定K均值聚類算法操作時(shí)機(jī)，增強(qiáng)算法局部精確搜索能力的同時(shí)縮短了收斂時(shí)間。通過對(duì)棉田環(huán)境中拍攝圖像的分割實(shí)驗(yàn)表明：本方法對(duì)在陽(yáng)光直射及陰影等干擾條件下的棉花圖片也能準(zhǔn)確分割，效果優(yōu)于傳統(tǒng)PSO和K均值算法。

棉花分割；YCbCr顏色空間；K均值算法；粒子群算法

A

ΤP391

10.3778/j.issn.1002-8331.1303-0397

SHI Hao,LAI Huicheng,QIN Xizhong.Image segmentation algorithm of cotton based on PSO and K-means hybrid clustering. Computer Engineering and Applications,2013,49（21）：226-229.

新疆維吾爾自治區(qū)科學(xué)基金資助項(xiàng)目（No.2011211A010）。

時(shí)顥（1988—），女，碩士研究生，主要研究方向?yàn)閳D像處理；賴惠成（1963—），男，教授，主要研究方向?yàn)橥ㄐ排c信息系統(tǒng)，圖像處理等；覃錫忠（1964—），副教授，碩士生導(dǎo)師，主要研究方向?yàn)樾盘?hào)與信息處理。E-mail：13579410640@163.com

2013-03-26

2013-05-06

1002-8331（2013）21-0226-04

CNKI出版日期：2013-05-29http://www.cnki.net/kcms/detail/11.2127.ΤP.20130529.1519.010.html