K均值聚類-粒子群優(yōu)化多目標(biāo)定位算法

廖延娜，李夢君，張婧琪

（1.西安郵電大學(xué)理學(xué)院，陜西西安710121；2.西安郵電大學(xué)電子工程學(xué)院，陜西西安710121；3.中國兵器工業(yè)第二0三研究所陜西西安710065）

隨著海洋開發(fā)、國防建設(shè)和智能交通等應(yīng)用領(lǐng)域的快速發(fā)展，多目標(biāo)識別技術(shù)[1]受到越來越多的重視，同時(shí)對多目標(biāo)的識別能力和分辨精度的要求日益提高[2]。目標(biāo)的準(zhǔn)確定位對于目標(biāo)識別以及圖像的理解與分析都起著重要的作用[3]。目標(biāo)定位多應(yīng)用于無人飛行器定位[4]、遙感及醫(yī)學(xué)圖像分析[5]、零部件識別與定位、產(chǎn)品檢驗(yàn)、攝影測量和車輛識別[6]等應(yīng)用中。常見的單目標(biāo)定位方法，如灰度特性法[7]、hough變換法[8]、數(shù)學(xué)形態(tài)學(xué)法[9]、紋理特征分析法[10]、彩色分割法[11]等，已經(jīng)被充分的研究和討論。而對多個(gè)目標(biāo)進(jìn)行定位研究的內(nèi)容卻不多見。

針對目前多目標(biāo)定位和識別的實(shí)際需要，文中提出一種K均值聚類-粒子群優(yōu)化的多目標(biāo)定位算法。算法以粒子群優(yōu)化為核心，結(jié)合K均值聚類保持種群的多樣性[12]，從而實(shí)現(xiàn)圖片中多個(gè)目標(biāo)的準(zhǔn)確、自動定位。

1 粒子群優(yōu)化算法原理

粒子群算法（ParticleSwarm Optimization，PSO）[13-14]是一種群體智能優(yōu)化算法[15]：在一個(gè)D維搜索空間內(nèi)，n個(gè)粒子組成的種群（粒子群）不斷調(diào)整速度和位置；通過若干次迭代搜索，到達(dá)最優(yōu)位置，即得到算法最優(yōu)解。在迭代搜索的過程中，每個(gè)粒子跟蹤比較兩個(gè)極值：個(gè)體極值P_best，即單個(gè)粒子自身找到的最優(yōu)解；全局極值G_best，即整個(gè)粒子群體找到的最優(yōu)解；從而實(shí)現(xiàn)粒子個(gè)體位置與速度的更新。

粒子群算法位置與速度更新公式如下：

其中，wmin為最小權(quán)重；wmax為最大權(quán)重；runMax為算法的最大迭代次數(shù)；run為當(dāng)前迭代次數(shù)。

2 排擠機(jī)制K均值聚類

為了保持目標(biāo)粒子種群[16]的多樣性，引入K均值聚類算法[17]。K均值聚類是一種以距離為判定條件的聚類算法，根據(jù)目標(biāo)粒子的編碼設(shè)計(jì)，定義目標(biāo)粒子i與j之間的距離dij的度量函數(shù)。

為避免算法收斂緩慢或陷入局部最優(yōu)解，初始質(zhì)心的位置對K均值聚類算法來說十分重要。本文根據(jù)目標(biāo)粒子的適應(yīng)度Fitness[18]，采用基于排擠機(jī)制的初始聚類質(zhì)心產(chǎn)生法，其思想如下：

根據(jù)粒子編碼生成表示目標(biāo)的粒子種群后，將種群中的n個(gè)元素按照適應(yīng)度Fitness_S的大小由高到低進(jìn)行排序，記為{p1,p2,…,pn}，令初始聚類質(zhì)心C1=p1。

計(jì)算距離矩陣Dn×n={dij}，預(yù)設(shè)距離門限D(zhuǎn)isT，若d12＞DisT，則認(rèn)為p1和p2距離甚遠(yuǎn)，可作為兩個(gè)不同的初始聚類質(zhì)心，即令C2=p2；反之，則認(rèn)為p1和p2距離過近，舍去p2，繼續(xù)比較d1i和DisT，直至選出C2=pi。

根據(jù)選出的C1=p1和C2=pi，繼續(xù)考察粒子pj(j＞i)：若d1j＞DisT且dij＞DisT，則令初始聚類質(zhì)心C3=pj。

以此類推，直至選出全部M個(gè)初始聚類質(zhì)心。

3 K均值聚類-粒子群優(yōu)化聯(lián)合算法

K均值聚類-粒子群優(yōu)化聯(lián)合算法的思想設(shè)計(jì)為：利用K均值聚類將目標(biāo)粒子種群劃分為若干個(gè)子群，在每個(gè)子群中，用粒子群算法進(jìn)行優(yōu)化；然后再重復(fù)進(jìn)行聚類、優(yōu)化，直到各個(gè)目標(biāo)子群得到最優(yōu)解。K均值聚類-粒子群優(yōu)化交錯(cuò)算法實(shí)現(xiàn)多目標(biāo)定位的具體步驟如下：

Step 1：隨機(jī)初始化目標(biāo)種群粒子速度與位置；

Step 2：計(jì)算每個(gè)目標(biāo)粒子的適應(yīng)度Fitness；

Step 3：采用基于排擠機(jī)制的K均值聚類算法確定聚類質(zhì)心并對種群進(jìn)行分類，得到M個(gè)子群；

Step 4：根據(jù)目標(biāo)粒子的適應(yīng)度，確定每個(gè)子群的全局極值和個(gè)體極值，并根據(jù)粒子速度和位置更新公式對子群中的粒子進(jìn)行更新；

Step 5：重新計(jì)算每個(gè)子群的質(zhì)心，根據(jù)排擠機(jī)制的預(yù)設(shè)距離門限，判斷是否需要重新聚類，若需要則返回Step 3，否則算法繼續(xù)向下運(yùn)行；

Step 6：判斷是否達(dá)到粒子群算法預(yù)設(shè)的迭代次數(shù)，若達(dá)到則結(jié)束算法輸出結(jié)果，若沒達(dá)到則返回步驟2重新執(zhí)行。

算法流程圖如圖1所示。

4 仿真實(shí)驗(yàn)

4.1 目標(biāo)粒子編碼設(shè)計(jì)

文中以多車牌定位為例，對多目標(biāo)定位算法進(jìn)行仿真了實(shí)驗(yàn)。粒子編碼是粒子群算法重要部分。本文設(shè)計(jì)車牌目標(biāo)粒子編碼為4維粒子pi={Xi,Yi,Li,Wi}；該目標(biāo)粒子中的各維分量分別代表車牌左上角坐標(biāo)X，左上角坐標(biāo)Y，車牌長L和車牌寬W。

圖1 算法流程圖

目標(biāo)粒子編碼時(shí)若不加任何限制，可能出現(xiàn)粒子初始位置離最優(yōu)解較遠(yuǎn)，極大的影響粒子尋優(yōu)的速度，并可能導(dǎo)致算法無法收斂。在實(shí)際應(yīng)用中，監(jiān)控?cái)z像機(jī)位置相對固定，所攝圖像中車牌的大小只在一定范圍內(nèi)變化。因此文中根據(jù)圖像的大小對車牌目標(biāo)粒子編碼進(jìn)行如下限制：

其中xmax和ymax分別代表圖片的最大長和寬；l和w為實(shí)際車牌長寬參考值；a和b為相應(yīng)的調(diào)整量。

4.2 目標(biāo)粒子特征提取

在灰度二值化后的圖像中，車牌區(qū)域在水平方向呈現(xiàn)有一定疏密度的黑白間隔的紋理分布，這是車牌目標(biāo)粒子的一大特征。本利用多尺度濾波技術(shù)，采用一組反映不同疏密度的高斯差分濾波器L1、L2、L3對圖像進(jìn)行濾波，即將車牌目標(biāo)粒子區(qū)域T(x,y)與濾波模板卷積：

根據(jù)車牌紋理特征空間分布的均勻性，使用Di(x,y)的標(biāo)準(zhǔn)差來表示車牌目標(biāo)粒子紋理特征值σi和特征描述向量T：

其中m、n為車牌目標(biāo)粒子區(qū)域的大小。

由于車牌由各種字符組成，與其他位置相比紋理變化較劇烈，可以認(rèn)為車牌目標(biāo)粒子特征向量T的模越大，則越有可能是車牌目標(biāo)區(qū)域。故設(shè)計(jì)適應(yīng)度函數(shù)如下：

鑒于σi＞0，也可以簡化設(shè)計(jì)適應(yīng)度函數(shù)Fitness_S=σ1+σ2+σ3。

4.3 仿真結(jié)果

算法仿真環(huán)境為matlab2012a，仿真測試圖片樣本來源于在某單位停車場一個(gè)月時(shí)間范圍內(nèi)隨機(jī)拍攝的近三百副圖片，圖片大小為640×300。圖片拍攝時(shí)模擬固定攝像頭位置，根據(jù)實(shí)際圖片，設(shè)置則車牌長、寬度調(diào)整量a=32，b=8。粒子大小為50，粒子最大速度限制為vmax=[vXmaxvYmaxvLmaxvWmax]=[20 10 4 2]，wmin=0.1，wmax=0.9，學(xué)習(xí)因子c1=c2=1；粒子群算法最大迭代次數(shù)設(shè)為50。

以包含兩輛車和三輛車的圖片為例，圖2為初始粒子種群經(jīng)過聚類過后的車牌目標(biāo)分布狀態(tài)。

圖2 聚類后車牌目標(biāo)分布圖

圖2中不同的虛、實(shí)型線分別代表不同類的車牌目標(biāo)。由圖可見，通過排擠機(jī)制的K均值聚類算法能夠有效將待定目標(biāo)區(qū)域分類，且分布在實(shí)際目標(biāo)的周圍。

圖3為粒子群算法中，每個(gè)子群最優(yōu)全局極值，即最優(yōu)目標(biāo)粒子的適應(yīng)度變化趨勢圖。

圖3 車牌目標(biāo)粒子適應(yīng)度變化趨勢

由圖3可見，粒子群進(jìn)化過程中，最優(yōu)車牌目標(biāo)粒子的適應(yīng)度隨進(jìn)化代數(shù)增加而增大，并漸趨穩(wěn)定，50代以內(nèi)粒子群算法基本收斂。

圖4為最終的車牌目標(biāo)定位結(jié)果?？梢娽槍Π瑑奢v車和三輛車的圖片，最終的車牌目標(biāo)定位結(jié)果準(zhǔn)確。

圖4 車牌目標(biāo)定位最終結(jié)果

分別以包含兩輛車的100幅兩車圖片和包含3輛車100幅三車圖片作為測試樣本，重復(fù)運(yùn)行50次進(jìn)行測試，目標(biāo)定位成功率統(tǒng)計(jì)結(jié)果如表1所示。

表1 多車牌定位結(jié)果統(tǒng)計(jì)

仿真實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果表明：兩車圖片的車牌目標(biāo)定位的平均成功率在96.8%；隨著圖片復(fù)雜性的增加，三車圖片的車牌目標(biāo)定位成功率略低于兩車圖片。粒子群算法最快6代內(nèi)即達(dá)到收斂，最慢46代達(dá)到收斂。為了更好的說明算法的收斂代數(shù)分布，圖5對粒子群算法收斂代數(shù)進(jìn)行了分段統(tǒng)計(jì)。

圖5 粒子群算法收斂代數(shù)統(tǒng)計(jì)

由圖5可見，對于兩車圖片和三車圖片，粒子群算法的收斂代數(shù)分布基本一致，主要集中在11～20代內(nèi)收斂，圖5的統(tǒng)計(jì)結(jié)果表明：對于不同類型的圖片，算法的收斂性能是穩(wěn)定的。

但是，K均值聚類算法需要預(yù)先指定聚類數(shù)目，實(shí)際應(yīng)用中很難確定圖片中車牌目標(biāo)數(shù)，針對這一局限性，文中進(jìn)行了如下測試：在兩車圖片中，將聚類數(shù)目指定為3，此時(shí)可以成功定位出2個(gè)車牌的正確位置，第3個(gè)子群的進(jìn)化較為隨機(jī)，一般收斂在圖片中紋理變化較明顯的非車牌區(qū)域，本文稱之為誤判區(qū)。在三車圖片中，將聚類數(shù)目指定為2，可以成功定位出其中隨機(jī)2個(gè)車牌的正確位置，會遺漏一個(gè)車牌目標(biāo)區(qū)域。因此在實(shí)際應(yīng)用中，可以適當(dāng)放大聚類數(shù)目，以免遺漏；對于誤判區(qū)，可通過后續(xù)的車牌字符識別進(jìn)行剔除。

5 結(jié) 論

通過針對實(shí)際拍攝圖片進(jìn)行的仿真實(shí)驗(yàn)可見，結(jié)合K均值聚類和粒子群優(yōu)化，可實(shí)現(xiàn)多目標(biāo)優(yōu)化。算法不需要對圖片中目標(biāo)的大致位置有先驗(yàn)經(jīng)驗(yàn)，通過粒子群迭代可自動搜索定位到準(zhǔn)確的多個(gè)目標(biāo)區(qū)域，算法性能穩(wěn)定、收斂，其定位的準(zhǔn)確率能夠滿足實(shí)際的應(yīng)用需求。

值得說明的是，K均值聚類方法需要人為設(shè)置所需的聚類個(gè)數(shù)，這在一定程度上限制了算法的應(yīng)用范圍。在下一步的研究中，可以考慮優(yōu)化聚類算法，根據(jù)粒子特征自動設(shè)置、調(diào)整聚類個(gè)數(shù)，以提高算法的靈活性。

[1]范梅梅，廖東平.基于WLS-TIR的多目標(biāo)識別認(rèn)知雷達(dá)波形自適應(yīng)方法[J].電子學(xué)報(bào)，2012（1）:73-77.

[2]秦洪峰.水下多目標(biāo)定位關(guān)健技術(shù)研究[D].西安：西北工業(yè)大學(xué)，2002.

[3]高希報(bào).圖像中幾種實(shí)用的目標(biāo)定位方法研究與應(yīng)用[D].南京：南京理工大學(xué)，2005.

[4]Y Qu，J Zhang.Cooperative localization based on the azimuth angles among multiple VAVs[C]//2013 International Conference on Unmanned Aircraft Systems（ICUAS），2013:818-823.

[5]曾雪，胡春華.帕金森病腦深部刺激療法中STN靶點(diǎn)定位方法綜述[J].北京:生命科學(xué)儀器，2014（3）:12-16.

[6]Ashtari A H，Nordin M J，F(xiàn)athy M.An Iranian license plate recognition system based on color features[J].IEEE Transactions on Intelligent Transportation Systems，2014，15（4）：1690-1750.

[7]馬永杰，云文霞.遺傳算法研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究，2012，29（4）:1201-1206.

[8]林俊，楊峰，林凱.Hough變換與先驗(yàn)知識在車牌定位中的新應(yīng)用[J].計(jì)算機(jī)與數(shù)字工程，2009，37（8）:138-140.

[9]趙軍偉.基于數(shù)學(xué)形態(tài)學(xué)和HSI顏色空間的人頭檢測[J].山東大學(xué)學(xué)報(bào)，2013（4）:6-10.

[10]周鐵平，王慶.一種新的汽車牌照快速定位方法[J].網(wǎng)絡(luò)新媒體技術(shù)，2007，28（4）:343-348.

[11]曾慶渝.視頻分割算法研究及實(shí)踐[D].杭州：浙江大學(xué)，2005.

[12]邢小紅，羅軍剛等.基于改進(jìn)多目標(biāo)粒子群算法的水庫防洪調(diào)度[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（30）:33-39.

[13]馮琳，毛志忠等.一種改進(jìn)的多目標(biāo)粒子群優(yōu)化算法及其應(yīng)用[J].控制與決策，2012，27（9）:1313-1319.

[14]張嶺軍.基于多目標(biāo)免疫算法的動態(tài)網(wǎng)絡(luò)社區(qū)檢測[D].西安：西安電子科技大，2012.

[15]Wickramasinghe U K，Li Xiaodong.Integrating User Preferences with Particle Swarms for Multiobjective Optimization[C]//Proc.Of the 10th Annual Conference on Genetic and Evolutionary Computation.Atlanta，USA:ACM Press，2008.

[16]陳東輝，劉志鏡，王縱虎.一種基于粒子群優(yōu)化的可能性C均值聚類改進(jìn)方法[J].計(jì)算機(jī)科學(xué)，2012（11）:122-126.

[17]M.Baydoun，M.Dawi and H.Ghaziri，"Enhanced parallel implementation of the K-Means clustering algorithm，"2016 3rd International Conference on Advances in Computational Tools for Engineering Applications（ACTEA），Beirut，2016：7-11.

[18]李丹煜，楊慶山，田玉基.基于K-means聚類的風(fēng)壓系數(shù)快速分區(qū)方法[J].工程力學(xué)，2014（12）:164-172.