基于新最速下降法的目標跟蹤算法

王 帥, 向建軍, 彭 芳, 唐書娟

(空軍工程大學航空工程學院, 陜西 西安 710038)

0 引 言

跟蹤的主要任務是實現對運動目標狀態的連續估計。在軍用和民用領域目標跟蹤都有著重要的應用。常用的目標跟蹤方法有Kalman濾波、交互多模型(interacting multiple model, IMM)濾波、多項式擬合等。

Kalman跟蹤算法利用雷達來捕獲運動目標測量數據,利用這些數據來估計運動目標的位置、速度、加速度等參數,實現對動目標的自動跟蹤。但是Kalman算法仍然具有很多局限性,例如:受非線性誤差影響大、要求非線性函數必須可導、要求系統是平穩隨機過程等。同時模型具有單一性和不完整性。對此又研究出了許多改進模型,其中Blom等人提出了適用范圍廣的IMM跟蹤算法。

IMM濾波算法是一種自適應濾波算法,它在跟蹤中使用多種模型來描述不同的運動狀態,通過有效的系統加權進行融合,在運動狀態不固定的情況下也適用。多種模型中采用較多的是勻速直線運動(constant velocity, CV)模型、勻加速直線運動(constant acceleration, CA)模型、勻速圓周運動(constant turn, CT)模型、當前統計(current statistical, CS)模型等。IMM雖然具有應用范圍廣的優勢,但是其仍然存在運算量大、計算復雜、機動情況下模型切換延遲的缺點。

對此本文提出一種新最速下降法的目標跟蹤算法,該算法首先提出了一種運動模型,該模型屬于一種改進的多項式擬合模型,多項式擬合具有易實現、計算簡單和適用范圍廣的優點。接下來該算法采用一種新最速下降法來求解運動模型的最優參數,通過實時的最優運動模型對運動目標的航跡進行預測跟蹤。實質上是用一種新最速下降法來求解多項式的參數,利用多項式來擬合目標的運動軌跡,達到跟蹤預測的目的。經仿真驗證,該算法具有易于工程實現、計算量小、適用范圍廣、計算精度高等優點。

1 IMM

IMM是Blom在基于偽貝葉斯方法的基礎上提出的,具有里程碑式的意義。該模型是一種基于狀態估計的運動模型集合,集合中包含了多種運動模型,每個運動模型都具有其相應的濾波模型和概率,此概率稱為轉移概率,通過馬爾可夫矩陣的方式完成模型之間的相互轉換。

IMM主要包括4部分:輸入交互、Kalman濾波預測、更新模型概率、交互輸出。其算法流程如圖1所示。

圖1 IMM算法流程圖Fig.1 Flow chart of IMM algorithm

2 基于新最速下降法的跟蹤模型

本文提出基于一種新最速下降法的自適應目標跟蹤算法。首先是建立運動的描述模型,再建立運動模型與實際運動之間的誤差函數,通過新最速下降法求解運動模型的最優權系數,通過運動模型對目標進行跟蹤和預測。

2.1 建立運動模型

目標在空間中的運動可以分解到,,3個二維平面上,分別對3個平面進行跟蹤濾波,對3個平面進行處理之后,再將3個平面的運動聯合起來便構成了空間運動,實現了對空間中運動目標的跟蹤濾波。所以本文提出的運動模型將把平面作為示例進行解釋。

目標在平面的運動是一條曲線,該曲線可以用多項式進行擬合,目標運動狀態越復雜,曲線越多樣,擬合所需要的多項式的階次越高。例如:勻速運動只需要一階多項式就可以擬合,勻加速運動需要二階多項式才能擬合,以此類推復雜運動就需要高階多項式來擬合。所以根據實際中目標的運動狀態,提出一組狀態描述多項式,如下式所示:

(1)

需要注意的是,在實際中狀態描述方程組的方程個數需要根據實際的運動狀態測量信息確定,如果測量信息只有位置信息,那么只保留式(1)中第一個運動描述方程來描述運動,如果測量信息不止有位置、速度、加速度還有加加速度等,那么就需要增加方程來描述加加速度,其增加規則是逐級求導數。為了方便本文進行算法闡述,本文假設測量信息有3種,分別是位置、速度和加速度。

從式(1)中可以看出,描述運動狀態的權系數共有+1個。當=0時位置是常數,描述的是靜止的運動狀態;當=1時速度是常數,加速度為0,描述的是勻速的運動狀態;當=2時加速度是常數,描述的是勻變速的運動狀態。越大,狀態描述方程所能描述的運動狀態就越復雜,所能描述的運動狀態種類也越多。

實際中測量運動目標得到的都是點跡信息,所以假設時間間隔是,則式(1)離散抽樣簡化后可得

式中:代表時間被時間間隔離散化之后的第個時間點。上式用矩陣的形式表示為

()=

(2)

式中:

(·)表示矩陣的轉置。

2.2 構造誤差平方和函數

假設觀測到個連續的點跡信息為=[,,…,],其中,,…,為包含了目標位置、速度、加速度等信息的列向量。為了使第21節中提出的運動狀態描述方程可以最準確地描述目標的運動狀態,則要求觀測點和描述點之間的誤差達到最小,即和之間的誤差達到最小,可以求和之間的最小誤差平方和:

(3)

式中:()代表和之間的誤差平方和,min代表取最小。

將式(2)代入式(3)得

(4)

從式(4)中可以看出,當觀測信息給定時,誤差平方和函數是一個關于描述運動狀態權系數,,…,的函數,應該通過調整權系數使誤差平方和函數達到最小,此時權系數所對應的狀態描述方程所描述運動狀態與目標的實際運動狀態最貼近。

但是實際中運動目標的觀測信息并不是準確的目標運動狀態信息,因為會受到觀測噪聲的影響。即=+,其中=[,,…,]為目標的實際運動狀態,向量(=1,2,…)代表了目標運動的位置、速度、加速度等狀態信息。=(,,…,)代表了觀測噪聲。目標的運動狀態相對于噪聲是光滑的,由于受到噪聲的影響,曲線會出現上下波動的情況,如圖2所示。

圖2 觀測狀態與實際狀態對比圖Fig.2 Comparison diagram of observed and actual conditions

由圖2可以看出觀測運動狀態由于觀測噪聲的影響與實際運動狀態相比會變得不光滑,出現波動。如果用描述方程來描述觀測運動狀態,則相對于實際運動狀態會出現過擬合的現象,即描述出來的運動狀態也會出現上下波動,所以應該使描述出來的運動狀態盡量平滑,避免過擬合現象的出現,以此來過濾掉噪聲的影響,對此可以采用正則化的思想。

正則化的思想就是通過引入正則項,使曲線光滑化,防止過擬合現象的發生。引入正則項后的誤差平方和函數為

(5)

2.3 新最速下降法求最優權系數

新最速下降法是一種采用迭代的方式,逐步求解非線性函數最優值的算法,具有運算量小、實現簡單、精度高、魯棒性強等優點。

將新最速下降算法用于求第22節中所構建的最小誤差平方和函數,會得到最優權系數,,…,，由于新最速下降法具有精度高、收斂快、簡單等優點,會使對目標的跟蹤速度更快、精度也更高。

該方法主要把高維函數降到二維,用拋物線的性質求解極值,利用循環迭代的方式最終求解出使函數達到極值的最優解。

詳細推導如下:設有一個維非線性二次函數

(,,…,)=++…+

式中:

=(++…+1+)=(++…+2+) ?=(1+2+…++)

,,…,為函數的自變量;為自變量的個數;(=1,2,…,;=1,2,…,)為函數里的系數;代表約束方程的數量。

首先給自變量,,…,隨機設置一個初值,,…,,此時函數會變成一個以為自變量,(,,…,)為因變量的二維拋物線,根據拋物線的性質求拋物線的極值點,將此極值點作為。然后將,,…,代入函數,則函數變成一個以為自變量,(,,,…,)為因變量的二維拋物線,根據拋物線的性質求拋物線的極值點,將此極值點作為。如此一直迭代求解,直到求解出之后,重新返回,將,,…,代入函數,求解。如此一直迭代循環求解,(),(),…,()(=1,2,…)隨著循環次數的遞增將越來越逼近于維非線性二次函數的極值。

拋物線的性質為:拋物線的一般形式為=++,則其極值點位于=-2處。

由上述拋物線的性質知,極值點與拋物線的系數,有關,為了方便求出系數,，可以采用求導數的方式實現。=′(=0),′(=0)代表對求一階導數,然后令=0。2=″,″表示對求二階導數。那么極值點為=-′(=0)″。

所以可以推導出維非線性二次函數的求解極值:

(6)

為了使方程可以描述機動目標即運動狀態變化頻繁的目標,可以求取當前時刻到前-1時刻的個觀測點跡的最小誤差平方和,得到最佳的運動狀態描述方程,以此方程實現對下一時刻目標運動狀態的預測。

因為目標預測需要具有實時性,所以的取值應該避免取值過大,經仿真實驗得到取3、2甚至是1時都會取得不錯的效果。

根據上述所說建立點的誤差平方和函數：

()=

(7)

應用新最速下降法求解點的最小誤差平方和,即結合式(6)和式(7)得到描述方程的權系數迭代公式:

?

?

(8)

基于新最速下降法的目標跟蹤算法應用步驟可以概括如下:

根據觀察點跡信息設置描述方程的個數,設置訓練點跡數目,設置權系數的個數+1,設置正則化參數;

輸入新的觀測點,對式(7)和式(8)中的-和-進行更新;

重復循環步驟3～步驟5,將步驟4步中目標預測的結果輸出。

該目標跟蹤算法的基本過程如圖3所示。

圖3 算法過程圖Fig.3 Algorithm process diagram

3 仿真驗證

3.1 仿真背景

假設目標在二維平面上做平面運動,沿方向做速度為500 m/s的勻速運動,沿方向做機動過載分別為30和26的蛇形機動,表示重力加速度，=10 m/s。兩個方向的觀測噪聲是標準差均為10 m 的高斯白噪聲。對運動目標進行測量的采樣頻率為10 Hz,仿真的時長為10 s。方向的初始位置為80 m,方向初始位置為0 m。得到兩個方向的運動方程分別為

(9)

式中:()～N(0,100)。

IMM里包含兩個模型，分別是CV模型和CS模型,CV模型主要針對方向目標做勻速運動,CS模型主要針對方向目標做蛇形機動。初始化馬爾可夫轉移概率矩陣設為

新算法的模型階數分別設置為1、2,誤差平方和函數所用的點數設置為2。運動模型權系數的初始化賦值為0,以頻率10 Hz 即跟蹤時間間隔為01 s,對時長為10 s 的運動軌跡進行觀測,運動軌跡如式(10)所示,得到101組觀測數據。將觀測數據和初始化賦值后的運動模型權系數代入式(8)中進行迭代計算得到更新后的運動模型權系數,將計算所得運動模型權系數代入所提出的運動模型，即式(1)，計算出運動目標的預測軌跡,并計算預測值與實際值之間的誤差。

用Matlab軟件在相同的條件下對新算法和IMM算法進行500次Monte-Carlo仿真,求500次Monte-Carlo仿真的均方根誤差(root mean square error, RMSE)。計算公式如下:

(10)

式中:RMSE表示500次仿真的均方根誤差;和分別代表第次仿真的預測狀態和實際狀態。

3.2 預測軌跡

在第31節的仿真條件下,應用新算法和IMM算法分別對和兩個方向抽樣所得到的點跡信息進行濾波和預測。然后對得到的兩個方向的運動信息進行合成,得到運動目標在平面的預測軌跡。

將兩種算法所得到的預測軌跡與目標的實際運動軌跡進行對比,得到的仿真結果如圖4所示。

圖4 預測軌跡對比Fig.4 Predicted trajectory comparison

從圖4可直觀地看出,新算法預測得到的軌跡相對于IMM更加貼近目標實際軌跡,對目標的預測跟蹤能力更好。

3.3 預測狀態與實際狀態之間的RMSE

將兩種算法預測所得到方向的目標運動狀態與實際的運動狀態進行對比,計算兩種算法預測得到的位置、速度和加速度與運動目標實際的3種運動狀態之間的RMSE,得到的結果如圖5所示。

圖5 x方向RMSE對比Fig.5 Comparison of RMSE in x direction

從圖5中可以看到兩種算法一開始對于位置的預測誤差基本相同,新算法具有優勢。在第2 s和第6 s時,IMM算法對目標位置和速度的預測出現較大的誤差,可以從圖4中看出,在這兩個時間目標突然進行高機動運動,導致運動狀態發生很大的變化,因此誤差增大。由于IMM算法是多模型交互工作,所以運動狀態發生很大變化時,IMM算法需要進行不同運動模型的交互,經過一段過渡時間的調整之后RMSE趨于收斂。求位置RMSE的平均值對兩種算法進行對比,經平均計算后得到IMM算法的預測誤差的平均值為9.66 m,新算法的預測誤差的平均值為7.15 m,所以新算法對于位置的預測更準確。對于速度的預測誤差始終是新算法要小一些。綜上,新算法對于勻速運動的預測效果相對于IMM算法要更好一些。

將兩種算法預測所得到方向的目標的運動狀態與實際的運動狀態進行對比,計算兩種算法預測得到的位置、速度和加速度與運動目標實際的3種運動狀態之間的RMSE,得到的結果如圖6所示。

圖6 y方向均方根誤差對比Fig.6 Comparison of RMSE in y direction

從圖6中可以看出對于位置的預測,新算法的誤差始終較小,IMM算法在目標進行轉彎時預測誤差會變大。在第2 s和第6 s時,誤差突然增大,這也是由于在這兩個時間目標進行高機動運動,運動狀態的突然變化導致的。此時IMM算法進行模型交互,經過一段過渡時間的調整之后,RMSE重新收斂。對于位置的均方根誤差取平均值得IMM算法的位置RMSE預測平均值為20.46 m,新算法的位置RMSE的平均值為14.44 m,所以新算法對位置的預測誤差更小。對于速度的預測也是新算法的預測誤差更低。對于加速度的預測兩種算法各有優劣,新算法預測誤差的收斂速度較快,而IMM算法的初始預測誤差更低。綜上,新算法對于機動目標的位置預測要好于IMM算法,對于速度和加速度的預測則各有優劣。

3.4 運算時間

對兩種算法在相同的仿真背景下的運算時間進行計算。運算時間的計算采用Matlab函數對新算法和IMM算法兩個程序的運行時間分別進行計時得到。電腦的CPU型號為Intel Core i5-4288U,運行內存為ddr3 12GB,操作系統為Windows7,所安裝的Matlab軟件為MatlabR2017a。對兩種算法500次Monte-Carlo的運行時間進行計時得到:新算法500次Monte-Carlo仿真花費的運算時間是19.297 2 s,IMM算法500次Monte-Carlo花費的運算時間是72.972 0 s。所以新算法的計算量要小于IMM算法,因此新算法更適用于對實時性要求較高的雷達目標跟蹤系統。

3.5 新算法與最小均方誤差算法對比

圖7所示為新算法與最小均方誤差(least mean square error, LMSE)算法的性能對比。仿真環境設置為:目標函數是一個6維凸函數,LMS算法的迭代步長設置為0.000 1,經過多次選擇得到迭代步長0.000 1,是能使算法收斂的最大迭代步長,初始值均設置為10。從圖7中可以看出新算法相對于傳統的LMSE算法無論是收斂速度還是計算精度均有較大的優勢,新算法的性能要優于傳統最速下降法。

圖7 新算法與LMSE算法對比Fig.7 Comparison between new algorithm and LMSE algorithm

4 結 論

本文首先提出了一種基于改進多項式擬合模型的運動模型，然后使用一種新的最速下降算法來求解運動模型中的權系數，最后利用新最速下降法收斂速度快、精度高、運算簡單等優點提高了目標跟蹤算法的精度和速度。

經過仿真分析得到新算法主要具有如下優點:可以適用于多種不同的運動類型;對運動目標的跟蹤預測效果更好,尤其是對于高機動目標;運算量小、實時性較好;易于工程實現。

但是新算法也存在著一定的缺點,由于新算法主要應用數據擬合的方式來進行預測,而對于運動狀態急速變化的目標,應該采用高速的取樣速率來保持目標預測的精確性。