摘要:經典的Kalman濾波器認爲,目(狗)標(子)的運動模型已知,然而實際中這一假設難以保障,尤其是狗子經常改變運動模型時(機動目標跟蹤,Maneuvering Target Tracking)。將Kalman濾波器、數據關聯和交互多模型結合起來,便是目前最成熟的目標跟蹤算法之一(其實不想說之一,但怕得罪人),全稱:Interactive Multi-Model-Joint Probabilistic Data Association-Kalman Filter,別暈,有個簡寫IMM-JPDA-KF。

來源:“科學大院”公衆號(ID:kexuedayuan)

作者:望墨溢

你是否好奇過,人類的機器(飛船、導彈、魚雷)是怎麼“看”到目標的?是像喫雞中那樣用“眼睛”瞄目標麼?最初的機器是這樣看世界的,可從阿波羅飛船開始,藉助一些新奇的“眼睛”,人類開始看到了一個又一個不一樣的世界。機器的眼睛,就是目標跟蹤算法了。

算法是怎麼回事?爲了關愛沒學過算法的朋友,我們將用故事《追狗,從入門到精通》來說明~

追狗入門篇:

“瞄”哪打哪——尾追法

如果你要提着菜刀去收拾一條剛拆完家的二哈,你會採取什麼方法追上它呢?大概會是這樣的策略(算法,Algorithm):

(1)你用眼睛看它在什麼位置(量測,Measurement。對,搞科研的喜歡把AB叫BA,以顯得高大上,例如還有把“簡約”叫“約簡”,把“積累”叫“累積”),你就朝向它跑;

(2)如果它也在動,你每隔一段時間,根據它最新的位置,調整自己的方向(更新,Update);

(3)如果它跑步是有規律的(先驗信息,Priori Information,也就是已知的信息),例如勻速直線地朝狗窩跑,你還可以直接到它的必經之路去堵它(預測,Prediction)。

(4)如果你倆一直在靠近(收斂,Converge),當某項數值(追狗這件事是看距離)低於預先設定好的指標(門限,Threshold),直接撲過去或者扔菜刀(結束)。

你用來追殺兇狗的算法,曾經被人類用在了最初的導彈、魚雷上,這就是目標跟蹤中最簡單的“尾追法”。那時人類的機器跟蹤目標,就跟喫雞時我們用倍鏡鎖定對手一樣:瞄。

追狗提高篇:

已知狗的路線——Kalman濾波器

隨着技術的進步,對目標跟蹤精度的要求越來越高,尤其是在航空航天領域,例如在太空執行任務,幾釐米的差距就可能會造成嚴重的後果(你也想遠遠地鏢那條狗18刀,刀刀避開要害,但差1釐米可能就要了你的狗的命)。

這裏有個問題,看到了就是看到了,怎麼還有精度這一說法?實際上,任何量測都有誤差(量測噪聲,Measurement Noise),且誤差還是隨機數,我們只可能知道誤差的概率分佈,卻不知道誤差具體的值(否則用量測值減去誤差不就完了,還研究什麼算法?)。

例如,你突然想起平日裏買狗糧,包裝袋上寫着“10Kg±500g”,就是在講:一袋狗糧重10Kg,但由於各種因素,實際可能剛夠,也可能少了若干g,也可能多若干g,但多與少都不會大於500g。

同時,目標運動也是有噪聲的(狗以爲它逃跑路線是直線,但其實也有誤差的),通常把這個誤差叫過程噪聲(Process Noise)。若已知狗的潛逃路線(運動模型,Motion Model)以及過程噪聲和量測噪聲的概率分佈,那麼就可以改進追狗的算法:

(1)上一時刻:如果已知上一時刻狗跑到了狗窩處,但就像狗糧的“10Kg±500g”一樣,這一位置是有誤差的,比如說方差爲1cm2的誤差(具體值是多少不知道,但概率分佈知道);

(2)預測:按照運動模型(假設勻速直線運動),它當前時刻應該跑到冰箱處,但由於它腦子不好使,其實這一過程是有方差爲5cm2的誤差(依舊具體值是多少不知道,但概率分佈知道)。由於上一時刻狗窩的方差是1cm2,因此冰箱處實際方差應該是1+5=6 cm2;

(3)量測:若人眼看到它在電視處,但這個量測是有方差爲10cm2的誤差(同上);

(4)狀態更新:這兩個信息(預測和量測)都不完全可信,但可以知道,預測相對於量測更可信,因爲預測的誤差方差小(6cm2<10cm2),因此我們可以用預測位置乘以可信度10/16,用量測位置乘以可信度6/16,兩個結果相加,表示融合預測和量測信號後的估計(Estimate);

(5)誤差方差:這一估計的誤差方差是多少呢?如果認爲上述算法是用量測修正預測,那麼應該是預測誤差-量測的相對誤差,即6*(1-6/16)=3.75 cm2;如果認爲是用預測修正量測,那麼應該是量測誤差-預測的相對誤差,即10*(1-10/16),依舊等於3.75cm2。

不難看出,估計誤差的方差3.75 cm2既小於量測的10cm2,也小於預測的6cm2。如此一來,便實現了更準確地追狗(目標跟蹤),這便叫做Kalman濾波器[1]。當年的阿波羅飛船首次用它來進行目標跟蹤,實現了飛行器間的高精度對接,證實了其有效性。

“阿波羅”飛船總高110米,在登月艙和指揮艙進行對接時,需要對準上百個插針、插孔和連接管路。誤差必須保持在0.1米以內,按等比例縮放就相當於,一個人手穿針線,還是那種上下左右都得對齊的那種。而Kalman濾波器,做到了。

至於誤差的概率分佈,可能是均勻分佈(Uniform Distribution),也可能是其它分佈,但根據中心極限定理(Central Limit Theorem),管他什麼分佈,樣本多了都是正態分佈,也叫高斯分佈(Gaussian Distribution)。

追狗進階篇:

出現好多狗——數據關聯

道高一尺,狗高一丈,二哈邪魅一笑,叫來了自己的兄弟姐妹(雜波,Clutter,也就是會產生量測來干擾我們的事物),用來迷惑我們,該怎麼辦?(如果導彈跟蹤的敵機放出誘餌,魚雷打擊的敵艦處在多個漁船間,量測便不只一個)這裏就要涉及到數據關聯,Data Association。

可以這樣做,由於你知道“兇手”是做勻速直線運動,可以預測它下一時刻的位置,那麼可以認爲:距離這個預測的位置越近,兇手的可能性越大;反之越小。

最簡單的方法就是“找最近”[2],即將最近的量測作爲正確量測(Correct Measurement)。但不太可靠,因爲這種數據關聯算法把其餘嫌疑狗直接排除。

後來,學者用量測與位置預測間距(新息,Innovation)來量化源自目標的概率(關聯概率,Association Probabilities),利用關聯概率對量測求平均,計算結果作爲真兇[3]。這樣雖然犧牲了一定的精度,但保證了不誤殺(只要二哈的狗命)。

當然,實際中爲了更加準確地跟(殺)蹤(狗),算法不僅要估計位置,還估計座標、速度、加速度等,即估計目標狀態(State)。狀態間距的計算方式有很多,但把距離度量統稱爲範數(Norm)。當噪聲服從高斯分佈時,距離範數的計算和關聯概率的計算有特殊的方式。

追狗精通篇:

如果狗子太狡猾——交互多模型

經典的Kalman濾波器認爲,目(狗)標(子)的運動模型已知,然而實際中這一假設難以保障,尤其是狗子經常改變運動模型時(機動目標跟蹤,Maneuvering Target Tracking)。

若已知二哈在有限個運動模型中運動(左、右、勻速直線、勻速圓周),不難想象,量測與正確模型下的預測間距最短,因此可以用這一距離來量化各模型正確的概率(模型概率,Model Probabilities),再用模型概率對各模型下的Kalman濾波估計進行加權[4]。

值得注意的是,每次模型概率更新後,除了進行加權平均,還要把各模型估計結果進行某種轉移(Transition)。這就像買股票,不同股票的價格發生變化,需要相應地對投資金額進行調整(把前景不太好的股票賣掉一部分,用於購買前景喜人的股票)。

將Kalman濾波器、數據關聯和交互多模型結合起來,便是目前最成熟的目標跟蹤算法之一(其實不想說之一,但怕得罪人),全稱:Interactive Multi-Model-Joint Probabilistic Data Association-Kalman Filter,別暈,有個簡寫IMM-JPDA-KF。即在雜波環境下(真假量測共存),對多個機動目標(目標運動模型未知),進行持續且可靠地跟蹤(準確估計位置、速度、加速度等運動量)。

“追狗”這門學科的前沿

以數據關聯爲核心的經典跟蹤算法,也有其侷限性,包括計算量隨量測和目標數呈現指數型增長,需要已知目標的個數(對目標數量變化響應滯後)等。

目標跟蹤的研究歷史久遠,但又在不斷地湧現新的方法。例如用機器學習(Machine Learning, ML)、稀疏表示(Sparse Representation,SR)等。

然而上述跟蹤算法都是“自下而上“被設計出的,即符合人類的直觀邏輯(詳見《追狗,從入門到精通》)。目前人類最爲前沿的跟蹤理論,是基於隨機有限集(Random Finite Set, RFS)的各種濾波器[5]。

它是”自上而下“被設計的,從FISST理論出發(給大家翻譯一下:就是”沒基礎就別好奇,保證聽不懂“的意思)。需要的基礎呢,也不多,包括Bayes最優濾波、集合空間積分,高斯混合模型、序貫Monte-Carlo、粒子濾波……

在你還在用倍鏡瞄人頭的時候,人類機器早以藉助概率等數學工具,居高臨下地看到了更爲宏大、更爲完備的世界。

作者:望墨溢

文中圖片均爲作者製作

參考文獻:

[1] R. E. Kalman, R. S. Bucy. New results in linear filtering and prediction theory. Journal of Basic Engineering[J]. 1961(3): 95-108.

[2] Singer R. A., Sea R. G.. A New Filter for Optimal Tracking in Dense Multitarget Environment[C]. Proceedings of the 9th Allerton Conference Circuit and System Theory, 1971: 201-211.

[3] Fortmann T. E., Bar-Shalom Y., Scheffe M.. Sonar Tracking of Multiple Targets Using Joint Probabilistic Data Association[J]. IEEE Journal of Oceanic Engineering, 1983, 8(3): 173-184.

[4] Blom H. A. P.. An Efficient Filter for Abruptly Changing Systems[C]. IEEE 23th Conference on Decision & Control, 1984, 12: 1-4.

[5] R. Mahler. Statistical Multisource-Multitarget Information Fusion[M]. Norwood, MA: Artech House, 2007.

相關文章