一種基于MeanShift改進(jìn)的移動(dòng)目標(biāo)跟蹤算法*

鄒梓秀

(福州理工學(xué)院 福州福建 350202)

關(guān)鍵字： MeanShift算法，移動(dòng)目標(biāo)跟蹤，車聯(lián)網(wǎng)

移動(dòng)目標(biāo)的跟蹤是當(dāng)前車聯(lián)網(wǎng)研究熱點(diǎn)，MeanShift算法是業(yè)界非常著名的跟蹤算法，是Fukunage學(xué)者在1975年提出的[1]。謝達(dá)奇等學(xué)者把MeanShift算法應(yīng)用到焊點(diǎn)檢測(cè)中，利用最小二擬合與MeanShift算法相結(jié)合完成若干圓心點(diǎn)的收集，通過(guò)實(shí)驗(yàn)對(duì)比驗(yàn)證了該方法的有效性[2]；周正欽等學(xué)者擴(kuò)展了均值漂移聚類，引入了鄰域權(quán)重因子，實(shí)現(xiàn)了紅外圖像中熱故障區(qū)域的有效提取，取得了很好的效果[3]；李旺靈等學(xué)者對(duì)Meanshift算法提出了錐套跟蹤的自適應(yīng)核窗口思想，提高了算法的適應(yīng)能[4]；孟一飛等學(xué)者利用MeanShift算法來(lái)識(shí)別西夏文字筆形，這是一個(gè)很新穎的思路，利用核估計(jì)直方圖統(tǒng)計(jì)方法，提取西夏文字的特征值，實(shí)現(xiàn)智能識(shí)別[5]；朱聞亞等學(xué)者對(duì)Meanshift算法進(jìn)行了改進(jìn)，引入了穩(wěn)健估計(jì)，部分實(shí)現(xiàn)了跟蹤丟失問(wèn)題，但當(dāng)跟蹤目標(biāo)快速通過(guò)時(shí)仍然可能導(dǎo)致跟蹤目標(biāo)丟失[6]；成怡等學(xué)者利用Meanshift算法與攝像機(jī)標(biāo)定相結(jié)合，實(shí)現(xiàn)了無(wú)人機(jī)定位問(wèn)題[7]。很多學(xué)者對(duì)Meanshift算法進(jìn)行了深入研究，在諸多領(lǐng)域都有很多應(yīng)用；也有很多學(xué)者對(duì)該算法進(jìn)行了多個(gè)角度的改進(jìn)，但跟蹤目標(biāo)在快速行進(jìn)時(shí)容易丟失、跟蹤目標(biāo)中途改變形狀等問(wèn)題仍然不夠理想，文章把MeanShift算法應(yīng)用到車聯(lián)網(wǎng)中，并針對(duì)其缺陷進(jìn)行改進(jìn)。

1 MeanShift算法

Meanshift算法的主要目標(biāo)是計(jì)算當(dāng)前坐標(biāo)點(diǎn)與移動(dòng)目標(biāo)的偏移向量的均值，然后移動(dòng)到該點(diǎn)，并以此為新的起點(diǎn)，不斷迭代該過(guò)程，直到滿足條件為止，如圖1所示(圖來(lái)自https：//my.oschina.net/u/3702502/blog/1815341)。

圖1 向量均值

圖1中C1_O表示目標(biāo)的起始點(diǎn)，C1、C2為監(jiān)視框，當(dāng)目標(biāo)移動(dòng)到C1_r時(shí)，計(jì)算兩點(diǎn)之間的偏移向量的均值，并向做移動(dòng)，然后不斷迭代直到C1與C2重合為止，具體實(shí)現(xiàn)步驟如下：

(1)偏移向量均值計(jì)算。某高維度區(qū)域，設(shè)其半徑為r，該區(qū)域有n個(gè)目標(biāo)對(duì)象，計(jì)算某D點(diǎn)與其它點(diǎn)Di偏移向量均值，其公式為：

(1)

(2)核函數(shù)的引入，為了更快地移動(dòng)到目標(biāo)位置，絕大部分的目標(biāo)跟蹤都會(huì)引入核函數(shù)，把MeanShift算法轉(zhuǎn)化為基于密度的聚類算法。高斯核函數(shù)是最常用的密度函數(shù)，設(shè)高維空間中任意兩點(diǎn)x1、x2的距離記作k(|x1-x2|)，高斯核函數(shù)的計(jì)算公式為：

(2)

通過(guò)高斯核函數(shù)的轉(zhuǎn)換，MeanShift算法的偏移向量均值的計(jì)算公式變?yōu)椋?/p>

(3)

通過(guò)高斯核函數(shù)的變換，從式(3)可以看出目標(biāo)將向概率密度上升的區(qū)域移動(dòng)，從而實(shí)現(xiàn)目標(biāo)的跟蹤。

2 MeanShift算法改進(jìn)

MeanShift算法是一種很成熟的跟蹤算法，在實(shí)踐中得到了廣泛應(yīng)用，但適應(yīng)能力有待提高，例如移動(dòng)目標(biāo)大小發(fā)生變化時(shí)，由于MeanShift算法的跟蹤框是固定的，容易導(dǎo)致丟失跟蹤目標(biāo)。此外，由于車聯(lián)網(wǎng)中，車輛運(yùn)行一般比較快，這需要算法反應(yīng)比較靈敏，但MeanShift算法由于緯度高、計(jì)算量大，也可能導(dǎo)致丟失跟蹤目標(biāo)。針對(duì)這兩個(gè)缺陷，可從以下幾個(gè)方面進(jìn)行改進(jìn)：

(1)跟蹤框的改進(jìn)。如圖1的C1框是固定的，如果跟蹤過(guò)程中正好下雨，某移動(dòng)目標(biāo)撐起了雨傘，那么跟蹤目標(biāo)的大小發(fā)生了很大的變化，為了不會(huì)丟失移動(dòng)目標(biāo)，文章增加一個(gè)實(shí)時(shí)形態(tài)監(jiān)測(cè)函數(shù)，用于在計(jì)算偏移量均值時(shí)同時(shí)計(jì)算移動(dòng)目標(biāo)的大小，實(shí)現(xiàn)過(guò)程：首先獲得移動(dòng)目標(biāo)的坐標(biāo)(x，y)和寬高w、h，然后根據(jù)坐標(biāo)和寬高構(gòu)造矩形框，返回矩形框Rec(x，y，w，h)。

(2)核函數(shù)改進(jìn)。文章使用的是高斯核函數(shù)，該函數(shù)有一個(gè)參數(shù)半徑r，該參數(shù)是固定的，單位頻率采集時(shí)間內(nèi)，目標(biāo)移動(dòng)速度越大，根據(jù)式(2)可知得到的結(jié)果越小，因此文章通過(guò)增設(shè)一個(gè)權(quán)重來(lái)調(diào)整半徑的值，以弱化該趨勢(shì)，從而避免由于速度較快導(dǎo)致跟蹤目標(biāo)丟失問(wèn)題，把式(2)進(jìn)行改造，得：

(4)

從式(4)可以看出，改進(jìn)后的公式在指數(shù)的分母增加了x2/x1的比例權(quán)重來(lái)削弱移動(dòng)趨勢(shì)，即移動(dòng)速度越快，x2/x1的比例越大，則式(4)得到的值比式(2)的值更小，因此式(3)需要迭代的次數(shù)也就減少了，從而減少了計(jì)算量，增強(qiáng)了整個(gè)算法反映速度，即反映會(huì)更靈敏，改進(jìn)后的算法命名為E-MeanShift。

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

在福州大學(xué)城某高校的校園主干道中安排了一場(chǎng)實(shí)驗(yàn)，主干道長(zhǎng)度3.3km，雙向兩車道，實(shí)驗(yàn)安排在某星期六完成。第一組實(shí)驗(yàn)，安排10人步行(正常速度)，3人騎電動(dòng)車(大約20km/h)，行進(jìn)中途，隨機(jī)安排步行中的3人打開(kāi)雨傘，并繼續(xù)前行。

圖2 跟蹤能力對(duì)比圖

圖2的實(shí)驗(yàn)結(jié)果表明，MeanShift算法跟蹤成功率為100×10/13=76.9%，目標(biāo)丟失率為100×3/13=23.1%；E-MeanShift算法的成功率為100%。通過(guò)后臺(tái)的監(jiān)控知道MeanShift算法丟失了三個(gè)中途打雨傘的目標(biāo)，說(shuō)明該算法對(duì)中途目標(biāo)大小的變化無(wú)法適應(yīng)，而E-MeanShift算法增加了實(shí)時(shí)監(jiān)測(cè)函數(shù)，不受此影響。

第二組實(shí)驗(yàn)，安排3輛電動(dòng)車(大約40km/h)，3輛汽車(大約60km/h)參與實(shí)驗(yàn)，當(dāng)電動(dòng)車和汽車陸續(xù)通過(guò)時(shí)，發(fā)現(xiàn)MeanShift算法和E-MeanShift算法都能全部跟蹤到，原因在于電動(dòng)車和汽車行進(jìn)中都不會(huì)改變尺寸大小，并且速度較慢。

第三組實(shí)驗(yàn)，為了檢驗(yàn)跟蹤效果，實(shí)驗(yàn)場(chǎng)地安排在某練車場(chǎng)，經(jīng)與私營(yíng)業(yè)主的許可，獲得了4.5km兩車道場(chǎng)地1h的使用時(shí)間，3輛汽車以100km/h的速度通過(guò)，實(shí)驗(yàn)結(jié)果：MeanShift算法2輛汽車跟蹤成功，其中1輛跟蹤目標(biāo)丟失，并且系統(tǒng)感受到明顯的“卡頓”，即跟蹤不夠流暢；E-MeanShift算法3輛全部跟蹤成功，實(shí)驗(yàn)證明在高速通過(guò)時(shí)E-MeanShift算法的跟蹤能力較出色。由于實(shí)驗(yàn)場(chǎng)地有限，科研經(jīng)費(fèi)有限等原因，文章未檢驗(yàn)超過(guò)100km/h的速度，也未檢測(cè)更多車輛同時(shí)通過(guò)的情況，但從該實(shí)驗(yàn)可以預(yù)計(jì)更高速和更多車輛的情況下，E-MeanShift算法的優(yōu)勢(shì)會(huì)更明顯。

4 結(jié)語(yǔ)

文章為了解決車聯(lián)網(wǎng)中移動(dòng)目標(biāo)跟蹤問(wèn)題，利用MeanShift算法和高斯核函數(shù)來(lái)跟蹤移動(dòng)目標(biāo)。由于MeanShift算法存在諸多缺陷，文章提出了兩個(gè)方面的改進(jìn)，通過(guò)3組實(shí)驗(yàn)證明改進(jìn)后的算法在適應(yīng)能力方面和移動(dòng)目標(biāo)高速通過(guò)時(shí)具有一定的優(yōu)勢(shì)。