基于改進(jìn)粒子群優(yōu)化的快速目標(biāo)定位*

敖 佳，陳 蔓

（中國電子科技網(wǎng)絡(luò)信息安全有限公司，四川 成都 610000）

0 引言

隨著信息技術(shù)的不斷發(fā)展，計算機(jī)視覺在制造業(yè)領(lǐng)域發(fā)揮著重要作用[1]。圖像目標(biāo)定位作為其中的一個分支，是該領(lǐng)域的研究熱點。制造業(yè)領(lǐng)域產(chǎn)品的圖像采集具備連續(xù)性、重復(fù)性等特點，若對采集的圖像進(jìn)行分割則需使用模板圖像進(jìn)行定位。此過程也可抽象地看作目標(biāo)跟蹤。由于工業(yè)制造過程具有實時性要求，因此目標(biāo)跟蹤過程的目標(biāo)定位需快速且準(zhǔn)確。

目標(biāo)定位可以看作是目標(biāo)搜索過程的優(yōu)化，以達(dá)到快速搜索的目的，從而滿足實時性要求。搜索過程的優(yōu)化可以采用確定性方法或隨機(jī)方法。在確定性方法中，具有代表性的是均值漂移[2-3]和Snakes 模型[4]。隨機(jī)方法中具有代表性的是卡爾曼濾波法[5]和粒子濾波法[6-7]。隨機(jī)方法通常速度很快，但是容易陷入局部最優(yōu)，因為它們依賴迭代搜索來尋找模板圖像和當(dāng)前圖像之間代價函數(shù)的局部最優(yōu)值。

粒子群優(yōu)化算法[8]是一種隨機(jī)優(yōu)化技術(shù)。由于它的實現(xiàn)簡單且已成功應(yīng)用于各個領(lǐng)域[9-11]，因此受到了人們的廣泛關(guān)注。過去十年內(nèi)，較多學(xué)者在其基礎(chǔ)上進(jìn)行了相關(guān)改進(jìn)，或針對靜態(tài)或針對動態(tài)的優(yōu)化問題，均取得了較好的結(jié)果。粒子群算法也成功應(yīng)用于目標(biāo)定位[12-15]，如Borra[13]等提出的模糊均值分類粒子群算法（Particle Swarm Optimization Fuzzy Means Clustering，PSO-FMC）。PSO-FMC 使用混合圖像分割方法和模式匹配，其中圖像分割采用模糊C 均值聚類分離目標(biāo)，然后進(jìn)行模式匹配。該方法較耗時，且其精度極大地依賴于圖像分割的精度。

本文提出一種基于改進(jìn)粒子群優(yōu)化的快速目標(biāo)定位算法，對粒子群算法做出了兩方面點改進(jìn)。一方面，對粒子的初始化范圍進(jìn)行區(qū)域劃分，使粒子初始化位置分布相對均勻，一定程度上加快了收斂速度。另一方面，引入采用“獵物-捕食者”機(jī)制的粒子群優(yōu)化算法[16]，通過刪除或轉(zhuǎn)換“懶惰”粒子進(jìn)一步加速算法收斂，提高計算效率。實驗結(jié)果表明，本文提出的算法在收斂速度和穩(wěn)定性方面均有一定提升。

1 粒子群算法

Kennedy[8]等提出的粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）受到了鳥群覓食行為的啟發(fā)，即模擬鳥群尋找食物源。如果對鳥群的覓食行為進(jìn)行建模，那么種群中的粒子則被認(rèn)為是給定問題的解，而問題的解空間是粒子為了尋找問題最優(yōu)解可活動的范圍。粒子活動時存在兩個關(guān)鍵點，一是全局最佳粒子，二是該粒子的歷史記憶，即該粒子活動過程中的當(dāng)前最佳解。每個粒子具備位置和速度兩個基本屬性。位置和速度在粒子活動的整個生命周期中不斷迭代更新，更新公式為：

2 本文算法

本文提出一種基于改進(jìn)粒子群優(yōu)化的快速目標(biāo)定位算法，主要包括5 個步驟。

2.1 粒子初始化

粒子的初始化包括位置和速度的初始化。由于本文針對的是圖像目標(biāo)的定位，因此速度初始化為[-1，1]之間的隨機(jī)數(shù)。位置為二維，相對于所有粒子位置均隨機(jī)初始化而言做出了如下改進(jìn)：將搜索目標(biāo)范圍等分為4 個子區(qū)域，同時將粒子也等分為4 份（若無法等分，最后一個區(qū)域可多或少部分粒子），隨機(jī)初始化到對應(yīng)的4 個子區(qū)域范圍內(nèi)；搜索范圍的正中心初始化一個粒子，若初始化粒子數(shù)n=17，則圖1 為其可能的初始分布之一。

圖1 粒子位置初始化（n=17）

每個區(qū)域初始化粒子數(shù)可公式化為：

式中，ns(s=1,2,3,4)為區(qū)域s內(nèi)的粒子數(shù)。

2.2 種群評估

種群評估共包含3 個部分。

第1 部分：計算每個粒子的適應(yīng)度。本文針對的是圖像目標(biāo)的定位，因此粒子的適應(yīng)度為目標(biāo)與圖像部分位置的相似度。相似度越高，匹配程度也越高。相似度公式表示為：

式中，fitness(i)為粒子i的適應(yīng)度，pi_x,pi_y分別為粒子i在x方向、y方向的位置，f為相似度計算函數(shù)。本文使用以該點為中心的鄰域矩陣相關(guān)性表示，相關(guān)性計算公式如下：

式中，corr(X,Y)為X、Y的相似度，X、Y為二維矩陣，Cov(X,Y)為X、Y的協(xié)方差，Var(X)、Var(Y)分別為X、Y的方差。

第2 部分：計算每個粒子當(dāng)前時刻的最佳位置。比較粒子當(dāng)前時刻位置與歷史最佳位置的適應(yīng)度，如果當(dāng)前時刻位置的適應(yīng)度更大，則更新該粒子的最佳位置為當(dāng)前位置，并同步更新最佳適應(yīng)度。

第3 部分：計算全局最佳粒子。將粒子當(dāng)前時刻位置的適應(yīng)度與全局最佳粒子適應(yīng)度進(jìn)行比較，若大于它，則更新全局最佳粒子的位置和適應(yīng)度。

2.3 信息更新

信息的更新包括各粒子速度和位置的更新，本文針對的是二維情況，因此速度和位置的更新公式為：

2.4 獵物和捕食者關(guān)系

“懶惰”粒子是指速度很低、對尋找最佳位置貢獻(xiàn)度不大的粒子，因此需設(shè)置一個速度閾值E，判定哪些粒子為“懶惰”粒子，具體處理流程如圖2 所示。

圖2 獵物-捕食者關(guān)系流程

步驟1：如果粒子i不是全局最佳粒子，且粒子的速度小于速度閾值E，則判定為“懶惰”粒子，并轉(zhuǎn)步驟2。

步驟2：產(chǎn)生一個[0，1]之間的隨機(jī)數(shù)t1，并設(shè)置一個閾值K1，K1表示獵物（當(dāng)前粒子i）遇到捕食者的概率，若隨機(jī)數(shù)t1＜K1，粒子i的行為將轉(zhuǎn)到步驟3。

步驟3：產(chǎn)生另一個[0，1]之間的隨機(jī)數(shù)t2，并設(shè)置一個閾值K2，K2表示獵物被捕食者抓住的概率，如果t2＜K2，將轉(zhuǎn)到步驟4（表示被抓住），否則轉(zhuǎn)到步驟5（表示獵物成功逃脫）。

步驟4：如果當(dāng)前種群大小S大于上一次迭代時的種群大小，直接刪除當(dāng)前粒子i。

步驟5：當(dāng)前粒子i的位置將隨機(jī)更改為其歷史最優(yōu)位置，粒子i的速度則重新隨機(jī)初始化。

文獻(xiàn)[16]對K1、K2進(jìn)行了相關(guān)實驗，并給出了其最佳變化范圍。K1變化范圍為[0.3，0.5]，K2變化范圍為[0.1，0.2]，本文取K1=0.4，K2=0.1。

2.5 種群繁殖

種群數(shù)量的波動需要控制在一定的范圍之內(nèi)，可使用比例積分（Proportional-Integral，PI）控制方法。PI 控制可以穩(wěn)定有效地將參數(shù)控制在某個指定范圍內(nèi)，或控制其根據(jù)某個指定的規(guī)則變動。種群數(shù)量的變化公式如下：

3 實驗結(jié)果分析

3.1 實驗數(shù)據(jù)和參數(shù)設(shè)置

為驗證算法的有效性，本文隨機(jī)選取了4 組實驗數(shù)據(jù)[17]（來自Pascal VOC 2007），見圖3，并與標(biāo)準(zhǔn)粒子群算法[8]（Standard Particle Swarm Optimizer，SPSO）、幾何粒子群算法[18]（Geometric Particle Swarm Optimizer，GPSO）、自適應(yīng)合作粒子群算法[19]（Adaptive Cooperative Particle Swarm Optimizer，ACPSO）以及基于基因?qū)W習(xí)的粒子群算法[20]（Genetic Learning Particle Swarm Optimizer，GLPSO）等基于粒子群的算法進(jìn)行對比分析。

圖3 中左邊圖為目標(biāo)搜索源圖像，右下角為待搜索目標(biāo)圖像（對應(yīng)源圖像的方框位置），右邊圖像為搜索目標(biāo)與搜索源圖像的相關(guān)性圖像。顯然，相關(guān)性為1 的地方，即為最終目標(biāo)解。

初始粒子個數(shù)的設(shè)置會影響計算時間和迭代次數(shù)，粒子個數(shù)越多，迭代次數(shù)越少，易收斂，但會增加計算時間；反之，粒子個數(shù)越少，計算時間短，但迭代次數(shù)會增加，不利于收斂。因此，為達(dá)到計算時間和收斂穩(wěn)定性之間的平衡，本文對初始粒子數(shù)做了以下實驗（見圖4），最終取一個相對合理的值。為實驗方便，初始粒子個數(shù)取值范圍在[10,100]，取值間隔為10，實驗圖像大小為372×372（實線）和800×800（虛線）。

圖4 中帶圓圈的曲線為算法運行1000 次（下同）的平均計算時間，帶三角形的曲線為找到最優(yōu)解的平均迭代次數(shù)，帶正方形的曲線為找到最優(yōu)解時迭代次數(shù)標(biāo)準(zhǔn)差（所有數(shù)據(jù)除以最大值進(jìn)行歸一化）。從圖4 可以看出，隨初始粒子數(shù)不斷增加，計算時間、迭代次數(shù)均值和標(biāo)準(zhǔn)差基本在n=20 的時候出現(xiàn)拐點，因此本文粒子數(shù)初始化為20（若需要提高穩(wěn)定性，可增加初始化粒子數(shù)量）。

圖3 實驗數(shù)據(jù)

圖4 計算時間與迭代次數(shù)關(guān)系

3.2 實驗環(huán)境

本文實驗采用的系統(tǒng)為Windows 7，處理器為Intel（R） Core（TM） i7-6700 CPU@3.40 GHz，內(nèi)存大小為16 GB，編程環(huán)境為Matlab 2016a。

3.3 實驗結(jié)果

實驗結(jié)果分成兩個部分：一是驗證改進(jìn)的粒子位置初始化方式對收斂速度的提升；二是驗證算法整體在計算時間和收斂速度方面的提升。本文用到的評價指標(biāo)有迭代次數(shù)均值（Mean）、迭代次數(shù)標(biāo)準(zhǔn)差（Std）、成功率（Sr）和計算時間（Time）共4 類。

3.3.1 驗證改進(jìn)的粒子位置初始化對收斂速度的影響

對4 組實驗數(shù)據(jù)分別采用不同的初始化方式，運行傳統(tǒng)PSO 算法1000 次，統(tǒng)計迭代次數(shù)的平均值和標(biāo)準(zhǔn)差。迭代次數(shù)平均值越小，說明收斂越快；迭代次數(shù)標(biāo)準(zhǔn)差越小，說明算法越穩(wěn)定，實驗結(jié)果分別見圖5 和圖6。

圖5 迭代次數(shù)均值

圖6 迭代次數(shù)標(biāo)準(zhǔn)差

從圖5 中可以看出，采用本文提出的位置初始化方式使迭代次數(shù)有了一定程度的降低，且每組實驗數(shù)據(jù)均呈現(xiàn)出一致的趨勢，說明本文提出的初始化方式能夠一定程度地提升收斂速度。此外，從圖6 可以看出，迭代次數(shù)標(biāo)準(zhǔn)差也相應(yīng)地有所降低，說明在提升收斂速度的同時，還提升了一定的穩(wěn)定性。

3.3.2 驗證整體算法

對4 組實驗數(shù)據(jù)分別采用3.1 節(jié)的4 類對比算法和本文提出算法，并從平均迭代次數(shù)均值、標(biāo)準(zhǔn)差、成功率和計算時間4 個方面進(jìn)行分析。每類算法在每組實驗數(shù)據(jù)上運行1000 次，最大迭代次數(shù)為200（若算法迭代次數(shù)超過最大迭代次數(shù)，則認(rèn)為失敗），實驗結(jié)果見表1（加粗部分表示最優(yōu)結(jié)果）。

表1 實驗結(jié)果

從表1 可以看出，SPSO、GPSO、ACPSO 可能出現(xiàn)不收斂的情況（成功率小于1.00），而GLPSO和本文算法則表現(xiàn)較好，在每組數(shù)據(jù)上運行1000次的情況下未出現(xiàn)不收斂的情況。此外，本文算法迭代次數(shù)的均值和標(biāo)準(zhǔn)差除了G2 的標(biāo)準(zhǔn)差未取得最佳結(jié)果外，其他均具有優(yōu)勢。此外，相對標(biāo)準(zhǔn)粒子群優(yōu)化算法而言，本文算法取得了相對明顯的提升，進(jìn)一步說明“獵物-捕食者”機(jī)制的引入對整體算法的效果從收斂速度和穩(wěn)定性方面有明顯提升。

4 結(jié)語

本文提出一種基于改進(jìn)粒子群優(yōu)化的快速目標(biāo)定位算法，分別從粒子位置的初始化方式和整體算法結(jié)構(gòu)兩方面進(jìn)行改進(jìn)，尤其是引入“獵物-捕食者”機(jī)制，使算法的收斂速度和穩(wěn)定性有了明顯提升。該算法除了可應(yīng)用到工業(yè)領(lǐng)域，也能應(yīng)用到其他具有高實時性要求的領(lǐng)域。