時顥，賴惠成，覃錫忠

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

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

時顥，賴惠成，覃錫忠

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

1 引言

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

2 顏色空間和方法的選取

2.1 顏色空間的選擇

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

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

2.2 粒子群算法介紹

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

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

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

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

2.3 K-means算法介紹

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

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

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

（1）隨機選取K個聚類中心。

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

（3）計算每個有變化聚類的均值，重新調整K個聚類中心。

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

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

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

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

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

3.2 確定K均值算法操作時機

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

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

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

3.3 算法結合具體操作流程

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

下面是算法的具體步驟：

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

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

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

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

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

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

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

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

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

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

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

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

3.4 連通域面積去噪

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

4 實驗結果與分析

為了評價分割效果，本文分別進行了兩組對比，第一組為在YCbCr空間下將PSO聚類算法與本文算法進行比較，仿真后的分割圖如圖1所示。

圖1 YCbCr空間下不同算法對比圖

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

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

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

圖3 棉花在強光照射下的情況

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

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

5 結論

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

[1]韋皆頂，費樹岷，汪木蘭，等.基于HSV顏色模型的自然場景下棉花圖像分割策略研究[J].棉花學報，2008，20（1）：34-38.

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

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

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

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

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

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

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

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

[10]王易循，趙勛杰.基于K均值聚類分割彩色圖像算法的改進[J].計算機應用與軟件，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ōu)化算法[J].電子學報，2004，32（3）.

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

[14]陳茂源，吳國平.基于PSO改進的OΤSU圖像分割方法[J].微計算機應用，2009（12）.

[15]孫建成，曾培峰.二值圖像的區(qū)域標識與噪聲去除[J].天津工業(yè)大學學報，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

棉花分割是采棉機器人視覺系統(tǒng)的關鍵步驟，在強光照、陰影等復雜的棉田環(huán)境下準確有效地分割棉花，有助于確定其在三維空間的位置。針對棉花圖片的特點，提出在YCbCr顏色空間下，采用粒子群（PSO）和K均值混合聚類算法，提高了聚類算法的全局搜索能力，根據(jù)群體適應度方差來確定K均值聚類算法操作時機，增強算法局部精確搜索能力的同時縮短了收斂時間。通過對棉田環(huá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ū)科學基金資助項目（No.2011211A010）。

時顥（1988—），女，碩士研究生，主要研究方向為圖像處理；賴惠成（1963—），男，教授，主要研究方向為通信與信息系統(tǒng)，圖像處理等；覃錫忠（1964—），副教授，碩士生導師，主要研究方向為信號與信息處理。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