【ch08】多目標(biāo)跟蹤算法

多目標(biāo)跟蹤算法工業(yè)和信息化部“十二五”規(guī)劃教材計(jì)算機(jī)視覺(jué)第八章01多目標(biāo)跟蹤概述目標(biāo)跟蹤過(guò)程可以定義為估計(jì)目標(biāo)在當(dāng)前時(shí)刻(濾波)和未來(lái)(外推)任意時(shí)刻狀態(tài)的過(guò)程。目標(biāo)的狀態(tài)包括各種運(yùn)動(dòng)參數(shù)或描述性的參數(shù)，一般地，運(yùn)動(dòng)參數(shù)具有重要的意義。目標(biāo)的狀態(tài)估計(jì)是在兩種不確定性下進(jìn)行的。多目標(biāo)跟蹤概述第一種是目標(biāo)運(yùn)動(dòng)模型的不確定性：由于大多數(shù)目標(biāo)在未來(lái)的時(shí)間段內(nèi)可能做已知或未知的機(jī)動(dòng)，因此目標(biāo)運(yùn)動(dòng)模型存在著不確定性。一般情況下，目標(biāo)的非機(jī)動(dòng)運(yùn)動(dòng)及機(jī)動(dòng)運(yùn)動(dòng)都可以通過(guò)不同的數(shù)學(xué)模型加以描述。在進(jìn)行目標(biāo)跟蹤的過(guò)程中，采用不正確的目標(biāo)運(yùn)動(dòng)模型會(huì)導(dǎo)致系統(tǒng)的跟蹤性能?chē)?yán)重下降。多目標(biāo)跟蹤概述第二種是測(cè)量的不確定性：測(cè)量的不確定性是指?jìng)鞲衅飨到y(tǒng)提供的測(cè)量可能是來(lái)自外部的數(shù)據(jù)干擾，它可能是由雜波、虛警或相鄰的目標(biāo)所引起的。測(cè)量作用點(diǎn)不能總是準(zhǔn)確地確定，并且測(cè)量含有噪聲，這兩個(gè)因素造成了測(cè)量的不確定性。這種不確定性在本質(zhì)上是離散的，給多目標(biāo)跟蹤提出了極大的挑戰(zhàn)，相應(yīng)的就產(chǎn)生了數(shù)據(jù)關(guān)聯(lián)的問(wèn)題。多目標(biāo)跟蹤概述目標(biāo)運(yùn)動(dòng)模型的研究是多目標(biāo)跟蹤技術(shù)研究的一個(gè)重要方面。20年來(lái),不少學(xué)者對(duì)此進(jìn)行了深入研究。根據(jù)目標(biāo)是否機(jī)動(dòng)。目標(biāo)運(yùn)動(dòng)模型多目標(biāo)跟蹤概述可以將其分為兩大類:一類是非機(jī)動(dòng)模型，主要有勻速（CV）模型和勻加速（CA）模型;另一類是機(jī)動(dòng)模型，主要有時(shí)間相關(guān)模型、當(dāng)前統(tǒng)計(jì)模型和轉(zhuǎn)彎（CT）模型。其他經(jīng)典的模型還包括微分多項(xiàng)式模型、半馬爾可夫模型和Noval統(tǒng)計(jì)模型等。多目標(biāo)跟蹤概述跟蹤波門(mén)技術(shù)跟蹤波門(mén)的形成是多目標(biāo)跟蹤首先面臨的問(wèn)題，跟蹤波門(mén)是以被跟蹤目標(biāo)的預(yù)測(cè)位置為中心，用來(lái)確定該目標(biāo)的觀測(cè)值可能出現(xiàn)的范圍。波門(mén)的大小由正確接收回波的概率確定，在確定波門(mén)形狀與大小時(shí)，應(yīng)使真實(shí)測(cè)量值以很高的概率落入波門(mén)中，同時(shí)又要使波門(mén)中的無(wú)關(guān)測(cè)量值的數(shù)量不是很多，落入跟蹤波門(mén)中的回波稱為有效(候選)回波。多目標(biāo)跟蹤概述跟蹤波門(mén)是將觀測(cè)值分配給已建立的目標(biāo)航跡或者確定新的目標(biāo)航跡的一種粗略的檢測(cè)方法，其作用有兩個(gè):(1)當(dāng)觀測(cè)值落入某個(gè)目標(biāo)的跟蹤波門(mén)內(nèi)時(shí)，該觀測(cè)值被考慮用于目標(biāo)航跡狀態(tài)的更新;(2)若觀測(cè)值沒(méi)有落入任何目標(biāo)的跟蹤波門(mén)內(nèi)，則認(rèn)為該觀測(cè)值可能來(lái)自新的目標(biāo)或者虛警。多目標(biāo)跟蹤概述濾波與預(yù)測(cè)是跟蹤系統(tǒng)最基本的要素，它是估計(jì)當(dāng)前時(shí)刻與未來(lái)時(shí)刻目標(biāo)的運(yùn)動(dòng)參數(shù)(如位置、速度和加速度)的必要手段。當(dāng)跟蹤非機(jī)動(dòng)或弱機(jī)動(dòng)目標(biāo)時(shí)，常用a-β濾波、α-β-γ濾波和卡爾曼濾波對(duì)線性運(yùn)動(dòng)進(jìn)行濾波和外推。濾波與預(yù)測(cè)多目標(biāo)跟蹤概述若目標(biāo)運(yùn)動(dòng)是非線性的，則需要采用擴(kuò)展卡爾曼濾波器(EKF)或不敏卡爾曼濾波器(和UKF)。當(dāng)跟蹤強(qiáng)機(jī)動(dòng)目標(biāo)時(shí)，一般采用交互式多模型算法和JerK模型算法等。多目標(biāo)跟蹤概述要實(shí)現(xiàn)對(duì)目標(biāo)的精確跟蹤，關(guān)鍵是有效地從測(cè)量數(shù)據(jù)中提取出有用的目標(biāo)狀態(tài)信息。一個(gè)好的目標(biāo)運(yùn)動(dòng)模型有助于信息的提取，因此大多數(shù)的跟蹤算法是基于模型的。目標(biāo)運(yùn)動(dòng)模型描述了目標(biāo)的運(yùn)動(dòng)狀態(tài)隨時(shí)間的變化過(guò)程，它用來(lái)表示目標(biāo)某個(gè)時(shí)刻的狀態(tài)變量與其前一時(shí)刻狀態(tài)變量之間的函數(shù)關(guān)系。多目標(biāo)跟蹤概述卡爾曼濾波基本模型若目標(biāo)做勻速直線運(yùn)動(dòng)，則其運(yùn)動(dòng)狀態(tài)可用CV模型表示。時(shí)間相關(guān)模型Singer提出了時(shí)間相關(guān)模型。轉(zhuǎn)彎模型在空中交通管制中，轉(zhuǎn)彎運(yùn)動(dòng)是一種比較常見(jiàn)的運(yùn)動(dòng)，通常也稱聯(lián)動(dòng)式轉(zhuǎn)彎運(yùn)動(dòng)(CT)。多目標(biāo)跟蹤概述當(dāng)目標(biāo)轉(zhuǎn)彎速率已知時(shí)，轉(zhuǎn)彎模型可以很好地模擬目標(biāo)的轉(zhuǎn)彎?rùn)C(jī)動(dòng)，從而實(shí)現(xiàn)對(duì)轉(zhuǎn)彎?rùn)C(jī)動(dòng)目標(biāo)的有效跟蹤。在CT模型中，ω<0表示目標(biāo)做順時(shí)針的轉(zhuǎn)彎運(yùn)動(dòng)，ω>0表示目標(biāo)做逆時(shí)針的轉(zhuǎn)彎運(yùn)動(dòng)。多目標(biāo)跟蹤概述02數(shù)據(jù)關(guān)聯(lián)算法數(shù)據(jù)關(guān)聯(lián)是多目標(biāo)跟蹤技術(shù)中最核心、最困難的部分，也是本章研究的重點(diǎn)。在雜波環(huán)境中，一個(gè)目標(biāo)的跟蹤波門(mén)中的測(cè)量數(shù)據(jù)可能不止一個(gè)，這些測(cè)量數(shù)據(jù)可能來(lái)自該目標(biāo)，也可能來(lái)自其他目標(biāo)，或者可能來(lái)自雜波。由于測(cè)量的不確定性，因此數(shù)據(jù)關(guān)聯(lián)可以描述為：將有效測(cè)量與已知航跡進(jìn)行比較，并確定可能的航跡與有效回波配對(duì)的過(guò)程。數(shù)據(jù)關(guān)聯(lián)算法最近鄰域法設(shè)置跟蹤波門(mén)，落入跟蹤波門(mén)中的測(cè)量值作為候選回波，即目標(biāo)的測(cè)量值z(mì)，(k)是否滿足其中，2(k|k-1)是跟蹤波門(mén)的中心。若波門(mén)中只有一個(gè)測(cè)量值，則該測(cè)量值直接用于航跡的更新;若有一個(gè)以上的候選回波，則選取統(tǒng)計(jì)距離最小的候選回波用于航跡的更新。數(shù)據(jù)關(guān)聯(lián)算法最近鄰域算法的優(yōu)點(diǎn)是計(jì)算量小、易于實(shí)現(xiàn)，且適用于低雜波環(huán)境的稀疏目標(biāo)跟蹤。但是在密集雜波環(huán)境下或當(dāng)目標(biāo)比較密集時(shí)，該算法往往容易誤跟或丟失目標(biāo)。數(shù)據(jù)關(guān)聯(lián)算法與最近鄰域法不同的是，概率數(shù)據(jù)關(guān)聯(lián)算法認(rèn)為落入跟蹤波門(mén)中的所有測(cè)量值都可能來(lái)自目標(biāo)，并且計(jì)算各個(gè)有效回波的概率，同時(shí)利用這些概率對(duì)各個(gè)回波進(jìn)行加權(quán)，利用有效回波的加權(quán)和來(lái)形成等效回波，這就是概率數(shù)據(jù)關(guān)聯(lián)算法的主要思想。概率數(shù)據(jù)關(guān)聯(lián)算法數(shù)據(jù)關(guān)聯(lián)算法假設(shè)目標(biāo)運(yùn)動(dòng)的狀態(tài)方程為x(k+1)=F(k)x(k)+G(k)w(k) 觀測(cè)方程為z(k)=H(k)x(k)+v(k)數(shù)據(jù)關(guān)聯(lián)算法在PDAF中，雜波密度是一個(gè)很重要的參數(shù)，直接關(guān)系到互聯(lián)概率的計(jì)算。然而，這個(gè)參數(shù)在實(shí)際情況中很難獲得。研究者提出了一種修正的概率數(shù)據(jù)互聯(lián)算法，能夠較為實(shí)用地解決雜波密度的實(shí)時(shí)估計(jì)問(wèn)題。由于PDAF的推導(dǎo)是基于關(guān)聯(lián)區(qū)域中僅有一個(gè)目標(biāo)的有效回波存在的假設(shè)，因此該算法僅適用于單目標(biāo)或稀疏多目標(biāo)的跟蹤，在密集目標(biāo)環(huán)境下，其跟蹤性能會(huì)大大降低。數(shù)據(jù)關(guān)聯(lián)算法聯(lián)合概率數(shù)據(jù)互聯(lián)(JPDA)算法是在PDA算法的基礎(chǔ)上提出來(lái)的，它綜合考慮了所有落入跟蹤波門(mén)內(nèi)的回波，認(rèn)為公共回波并非只源于一個(gè)目標(biāo)，也可能分屬于不同的目標(biāo)。因此JPDA算法適用于雜波環(huán)境下的多目標(biāo)跟蹤。聯(lián)合概率數(shù)據(jù)互聯(lián)算法數(shù)據(jù)關(guān)聯(lián)算法確認(rèn)矩陣的拆分需要依據(jù)以下兩個(gè)基本假設(shè):每個(gè)回波都有唯一的來(lái)源，即任意回波若不是來(lái)自某目標(biāo)，則就是來(lái)自雜波;對(duì)于某個(gè)確定的目標(biāo)，只有一個(gè)回波以其為源。若某個(gè)目標(biāo)與多個(gè)回波匹配，則將取其中一個(gè)為真，其余為假。數(shù)據(jù)關(guān)聯(lián)算法即確認(rèn)矩陣的拆分需遵循以下兩個(gè)原則::從確認(rèn)矩陣的每行中選出唯——個(gè)1，作為互聯(lián)矩陣在該行的非零元素;;在互聯(lián)矩陣中，除第一列外，每列最多有一個(gè)非零元素。數(shù)據(jù)關(guān)聯(lián)算法其他的經(jīng)典算法多假設(shè)跟蹤算法是1978年由Reid首先提出的，它以“全鄰”最優(yōu)濾波器和Bar-Shalom提出的聚矩陣為基礎(chǔ)，主要過(guò)程包括聚的構(gòu)成、“假設(shè)”的產(chǎn)生、每個(gè)假設(shè)的概率計(jì)算及假設(shè)約簡(jiǎn)。該算法綜合了JPDA算法和最近鄰域算法的優(yōu)點(diǎn)，適用于低檢測(cè)概率、高虛警率和密集雜波環(huán)境下的多目標(biāo)跟蹤;缺點(diǎn)是該算法過(guò)于依賴目標(biāo)與雜波的先驗(yàn)知識(shí)，并且該算法的計(jì)算量隨著目標(biāo)與雜波個(gè)數(shù)的增加而呈指數(shù)增長(zhǎng)。數(shù)據(jù)關(guān)聯(lián)算法航跡分裂法于20世紀(jì)60年代由Slitter首先提出，1975年由Smith和Buechler進(jìn)一步研究發(fā)展起來(lái)的一種以似然函數(shù)檢測(cè)為基礎(chǔ)的數(shù)據(jù)關(guān)聯(lián)算法。航跡分裂法數(shù)據(jù)關(guān)聯(lián)算法模糊數(shù)學(xué)及神經(jīng)網(wǎng)絡(luò)由于環(huán)境中噪聲的影響及傳感器分辨率的限制，因此得到的測(cè)量數(shù)據(jù)并不能完全準(zhǔn)確地反映日標(biāo)的真實(shí)情況，其帶有一定程度的模糊性及目標(biāo)運(yùn)動(dòng)模型的不確定性，不少學(xué)者將模糊數(shù)學(xué)理論引入多目標(biāo)跟蹤中。數(shù)據(jù)關(guān)聯(lián)算法由于數(shù)據(jù)關(guān)聯(lián)過(guò)程存在不確定性，并且傳統(tǒng)的基于單次掃描的數(shù)據(jù)關(guān)聯(lián)算法可能得不到正確的結(jié)果，因此使用多次掃描的結(jié)果進(jìn)行數(shù)據(jù)關(guān)聯(lián)可能會(huì)提高跟蹤性能?；诙鄴呙璧臄?shù)據(jù)關(guān)聯(lián)算法的核心是計(jì)算似然函數(shù)，該似然函數(shù)可用于航跡的起始，也可用于航跡的維持。多掃描分配算法數(shù)據(jù)關(guān)聯(lián)算法03基于圖模型的多目標(biāo)跟蹤算法在已有的多目標(biāo)跟蹤算法中，經(jīng)典的算法主要有JPDA算法、多假設(shè)(MHT)算法和最近鄰域算法。其中JPDA算法跟蹤精度比較高，且應(yīng)用比較廣泛。但是隨著目標(biāo)數(shù)量的增加，各目標(biāo)之間的狀態(tài)空間相互串聯(lián)，使得其計(jì)算量呈現(xiàn)“組合爆炸”式的增長(zhǎng)?；趫D模型的多目標(biāo)跟蹤算法圖模型是近年來(lái)很熱門(mén)的理論，很多具體模型都可以表示為圖模型，包括進(jìn)化樹(shù)、譜系圖、隱馬爾可夫模型、馬爾可夫隨機(jī)域和卡爾曼濾波，等等。由于圖模型結(jié)合了概率理論與圖理論的優(yōu)點(diǎn)，因此它能夠很好地解決類似多目標(biāo)跟蹤等復(fù)雜的不確定性問(wèn)題，圖模型已經(jīng)被廣泛地應(yīng)用在視覺(jué)跟蹤、數(shù)據(jù)挖掘和語(yǔ)音處理等領(lǐng)域。基于圖模型的多目標(biāo)跟蹤算法概率圖模型(簡(jiǎn)稱圖模型)是結(jié)合圖論和概率論來(lái)有效描述多元統(tǒng)計(jì)關(guān)系的模型。它可用G={V，ε}表示一個(gè)概率圖模型，其中圖上的節(jié)點(diǎn)集合用V={x1，x2，…，xN}表示邊集合，且ε∈V×V。概率圖模型分析基于圖模型的多目標(biāo)跟蹤算法圖8.1顯示了這兩種概率圖模型的基本形式。基于圖模型的多目標(biāo)跟蹤算法圖8.2顯示了一個(gè)2×2的成對(duì)馬爾可夫隨機(jī)場(chǎng)及其因子圖。基于圖模型的多目標(biāo)跟蹤算法從圖8.3可知，隱馬爾可夫過(guò)程類似一階馬爾可夫過(guò)程。基于圖模型的多目標(biāo)跟蹤算法圖8.4GMM的有向圖表示。基于圖模型的多目標(biāo)跟蹤算法具體EM算法如表8.1所示?；趫D模型的多目標(biāo)跟蹤算法圖8.5Stick-Breaking構(gòu)造的混合模型與CRP構(gòu)造的模型?；趫D模型的多目標(biāo)跟蹤算法概率圖模型推理方法概率圖模型推理問(wèn)題是具有良序結(jié)構(gòu)的組合優(yōu)化問(wèn)題，其中計(jì)算邊緣概率和計(jì)算最大概率狀態(tài)問(wèn)題是概率圖模型研究和應(yīng)用的核心問(wèn)題。因此，在大多數(shù)情況下，不能實(shí)現(xiàn)這些問(wèn)題的精確求解。目前，對(duì)精確推理的研究，主要是研究在特殊圖結(jié)構(gòu)和特殊參數(shù)條件下，能達(dá)到高階多項(xiàng)式復(fù)雜度的近似推理方法，而大致可分為變分法和采樣法兩類近似推理方法。基于圖模型的多目標(biāo)跟蹤算法變分法是基于最優(yōu)化方法，把推理問(wèn)題轉(zhuǎn)化為目標(biāo)函數(shù)的最小化問(wèn)題;采樣法是利用采集的樣本表征概率圖的聯(lián)合分布，并用采樣得到的樣本來(lái)近似最大概率或者邊緣概率?；趫D模型的多目標(biāo)跟蹤算法04本章小結(jié)目標(biāo)跟蹤算法屬于目前計(jì)算機(jī)視覺(jué)中的研究熱點(diǎn),各種不同的數(shù)據(jù)集層出不窮。公開(kāi)的數(shù)據(jù)集如OTB50,OTB100,VOT系列數(shù)據(jù)和UAV數(shù)據(jù),再加上近期深度學(xué)習(xí)在視覺(jué)領(lǐng)域的成功應(yīng)用,使得算法在數(shù)據(jù)集上的性能快速提升。本章小結(jié)但由于需要大量的標(biāo)注數(shù)據(jù),因此造成人工智能真正側(cè)重在“人工”上,而“智能”則體現(xiàn)得較少。深度學(xué)習(xí)在目標(biāo)檢測(cè)和跟蹤中的性能使自動(dòng)駕駛成為可能,但由于深度學(xué)習(xí)中的樣本覆蓋問(wèn)題仍導(dǎo)致事故不斷發(fā)生。本章小結(jié)現(xiàn)實(shí)世界的多樣性不太可能窮舉出所有的樣本集合,因