目標跟蹤入門(mén)篇—相關(guān)濾波

前  言

目標跟蹤是計算機視覺(jué)領(lǐng)域的一個(gè)重要問(wèn)題，目前廣泛應用在體育賽事轉播、安防監控和無(wú)人機、無(wú)人車(chē)、機器人等領(lǐng)域。

簡(jiǎn)單來(lái)說(shuō)，目標跟蹤就是在連續的視頻序列中，建立所要跟蹤物體的位置關(guān)系，得到物體完整的運動(dòng)軌跡。給定圖像第一幀的目標坐標位置，計算在下一幀圖像中目標的確切位置。在運動(dòng)的過(guò)程中，目標可能會(huì )呈現一些圖像上的變化，比如姿態(tài)或形狀的變化、尺度的變化、背景遮擋或光線(xiàn)亮度的變化等。目標跟蹤算法的研究也圍繞著(zhù)解決這些變化和具體的應用展開(kāi)。

目前目標跟蹤的難點(diǎn)主要包含：

形態(tài)變化 - 姿態(tài)變化是目標跟蹤中常見(jiàn)的干擾問(wèn)題。運動(dòng)目標發(fā)生姿態(tài)變化時(shí), 會(huì )導致它的特征以及外觀(guān)模型發(fā)生改變, 容易導致跟蹤失敗。例如:體育比賽中的運動(dòng)員、馬路上的行人。

尺度變化 - 尺度的自適應也是目標跟蹤中的關(guān)鍵問(wèn)題。當目標尺度縮小時(shí), 由于跟蹤框不能自適應跟蹤, 會(huì )將很多背景信息包含在內, 導致目標模型的更新錯誤；當目標尺度增大時(shí), 由于跟蹤框不能將目標完全包括在內, 跟蹤框內目標信息不全, 也會(huì )導致目標模型的更新錯誤。因此, 實(shí)現尺度自適應跟蹤是十分必要的。

遮擋與消失 - 目標在運動(dòng)過(guò)程中可能出現被遮擋或者短暫的消失情況。當這種情況發(fā)生時(shí), 跟蹤框容易將遮擋物以及背景信息包含在跟蹤框內, 會(huì )導致后續幀中的跟蹤目標漂移到遮擋物上面。若目標被完全遮擋時(shí), 由于找不到目標的對應模型, 會(huì )導致跟蹤失敗。

圖像模糊 - 光照強度變化, 目標快速運動(dòng), 低分辨率等情況會(huì )導致圖像模型, 尤其是在運動(dòng)目標與背景相似的情況下更為明顯。因此, 選擇有效的特征對目標和背景進(jìn)行區分非常必要。

01

目標跟蹤算法發(fā)展

跟蹤算法主要從經(jīng)典算法到基于核相關(guān)濾波算法，再到基于深度學(xué)習的跟蹤算法。

早期經(jīng)典的跟蹤方法比如 Meanshift、Particle Filter 和 Kalman Filter。Meanshift 方法是一種基于概率密度分布的跟蹤方法，使目標的搜索一直沿著(zhù)概率梯度上升的方向，迭代收斂到概率密度分布的局部峰值上。首先 Meanshift 會(huì )對目標進(jìn)行建模，比如利用目標的顏色分布來(lái)描述目標，然后計算目標在下一幀圖像上的概率分布，從而迭代得到局部最密集的區域。Meanshift 適用于目標的色彩模型和背景差異比較大的情形，早期也用于人臉跟蹤。由于 Meanshift 方法的快速計算，它的很多改進(jìn)方法也一直適用至今。

粒子濾波（Particle Filter）方法是一種基于粒子分布統計的方法。以跟蹤為例，首先對跟蹤目標進(jìn)行建模，并定義一種相似度度量確定粒子與目標的匹配程度。在目標搜索的過(guò)程中，它會(huì )按照一定的分布（比如均勻分布或高斯分布）撒一些粒子，統計這些粒子的相似度，確定目標可能的位置。在這些位置上，下一幀加入更多新的粒子，確保在更大概率上跟蹤上目標。Kalman Filter 常被用于描述目標的運動(dòng)模型，它不對目標的特征建模，而是對目標的運動(dòng)模型進(jìn)行了建模，常用于估計目標在下一幀的位置。另外，經(jīng)典的跟蹤方法還有基于特征點(diǎn)的光流跟蹤，在目標上提取一些特征點(diǎn)，然后在下一幀計算這些特征點(diǎn)的光流匹配點(diǎn)，統計得到目標的位置。在跟蹤的過(guò)程中，需要不斷補充新的特征點(diǎn)，刪除置信度不佳的特征點(diǎn)，以此來(lái)適應目標在運動(dòng)中的形狀變化。本質(zhì)上可以認為光流跟蹤屬于用特征點(diǎn)的集合來(lái)表征目標模型的方法。

基于核相關(guān)濾波的跟蹤算法如MOSSE、CSK、KCF、BACF、SAMF將通信領(lǐng)域的相關(guān)濾波(衡量?jì)蓚€(gè)信號的相似程度)引入到了目標跟蹤中，相關(guān)濾波的跟蹤算法始于 2012 年 P.Martins 提出的 CSK 方法，作者提出了一種基于循環(huán)矩陣的核跟蹤方法，并且從數學(xué)上完美解決了密集采樣（Dense Sampling）的問(wèn)題，利用傅立葉變換快速實(shí)現了檢測的過(guò)程。在訓練分類(lèi)器時(shí)，一般認為離目標位置較近的是正樣本，而離目標較遠的認為是負樣本。利用快速傅立葉變換，CSK 方法的跟蹤幀率能達到 100～400fps，奠定了相關(guān)濾波系列方法在實(shí)時(shí)性應用中的基石。

利用深度學(xué)習訓練網(wǎng)絡(luò )模型，得到的卷積特征輸出表達能力更強，在目標跟蹤上，初期的應用方式是把網(wǎng)絡(luò )學(xué)習到的特征，直接應用到相關(guān)濾波或 Struck 的跟蹤框架里面，從而得到更好的跟蹤結果，網(wǎng)絡(luò )不同層的卷積輸出都可以作為跟蹤的特征。

總的來(lái)說(shuō)

相比于光流法、Kalman、Meanshift等傳統算法，相關(guān)濾波類(lèi)算法跟蹤速度更快，深度學(xué)習類(lèi)方法精度高。

具有多特征融合以及深度特征的追蹤器在跟蹤精度方面的效果更好。

使用強大的分類(lèi)器是實(shí)現良好跟蹤的基礎。

尺度的自適應以及模型的更新機制也影響著(zhù)跟蹤的精度。

02  相關(guān)濾波器思想

相關(guān)濾波跟蹤的基本思想就是，設計一個(gè)濾波模板，利用該模板與目標候選區域做相關(guān)運算，最大輸出響應的位置即為當前幀的目標位置。

其中 y 表示響應輸出， x 表示輸入圖像， w 表示濾波模板。利用相關(guān)定理，將相關(guān)轉換為計算量更小的點(diǎn)積。

 分別是y,x,w  的傅里葉變換。相關(guān)濾波的任務(wù)，就是尋找最優(yōu)的濾波模板w。

目前的難點(diǎn)：

一般的相關(guān)濾波都是固定學(xué)習率的線(xiàn)性加權更新模型，不需要顯式保存訓練樣本，每幀樣本訓練的模型與已有目標模型，以固定權值加權來(lái)更新目標模型，這樣以往的樣本信息都會(huì )逐漸失效，而最近幾幀的樣本信息占模型的比重很大。如果出現目標定位不準確、遮擋、背景擾動(dòng)等情況，固定學(xué)習率方式會(huì )平等對待這些“有問(wèn)題”的樣本，目標模型就會(huì )被污染導致跟蹤失敗。

另外相關(guān)濾波模板類(lèi)特征(HOG)對快速變形和快速運動(dòng)效果不好，但對運動(dòng)模糊光照變化等情況比較好。

03  相關(guān)濾波器發(fā)展

MOSSE

    相關(guān)濾波跟蹤的開(kāi)篇之作，利用目標的多個(gè)樣本作為訓練樣本，以生成更優(yōu)的濾波器。MOSSE 以最小化平方和誤差為目標函數，用m個(gè)樣本求最小二乘解。

CSK

    CSK針對MOSSE算法中采用稀疏采樣造成樣本冗余的問(wèn)題，擴展了嶺回歸、基于循環(huán)移位的近似密集采樣方法、以及核方法。MOSSE與CSK處理的都是單通道灰度圖像，引入了循環(huán)移位和快速傅里葉變換，極大地提高了算法的計算效率。但是離散傅里葉變換也帶來(lái)了一個(gè)副作用：邊界效應。

    針對邊界效應，有2個(gè)典型處理方法：在圖像上疊加余弦窗調制；增加搜索區域的面積。加余弦窗的方法，使搜索區域邊界的像素值接近0，消除邊界的不連續性。余弦窗的引入也帶來(lái)了缺陷: 減小了有效搜索區域。例如在檢測階段，如果目標不在搜索區域中心，部分目標像素會(huì )被過(guò)濾掉。如果目標的一部分已經(jīng)移出了這個(gè)區域，很可能就過(guò)濾掉僅存的目標像素。其作用表現為算法難以跟蹤快速運動(dòng)的目標。擴大搜索區域能緩解邊界效應，并提高跟蹤快速移動(dòng)目標的能力。但缺陷是會(huì )引入更多的背景信息，可能造成跟蹤漂移。

CN

    CN在CSK的基礎上擴展了多通道顏色。將RGB的3通道圖像投影到11個(gè)顏色通道，分別對應英語(yǔ)中常用的語(yǔ)言顏色分類(lèi)，分別是black, blue, brown, grey, green, orange, pink, purple, red, white, yellow，并歸一化得到10通道顏色特征。也可以利用PCA方法，將CN降維到2維。

DCF KCF

    從DCF到KCF多了Gaussian-kernel，performance上升0.21%，fps下降46.46%，kernel-trick雖然有用但影響較小，如果注重速度可以摒棄，如果追求極限性能可以用。KCF可以說(shuō)是對CSK的完善。論文中對嶺回歸、循環(huán)矩陣、核技巧、快速檢測等做了完整的數學(xué)推導。KCF在CSK的基礎上擴展了多通道特征。KCF采用的HoG特征，核函數有三種高斯核、線(xiàn)性核和多項式核，高斯核的精確度最高，線(xiàn)性核略低于高斯核，但速度上遠快于高斯核。

SAMF

    SAMF基于KCF，特征是HoG+CN。SAMF實(shí)現多尺度目標跟蹤的方法比較直接，類(lèi)似檢測算法里的多尺度檢測方法。由平移濾波器在多尺度縮放的圖像塊上進(jìn)行目標檢測，取響應最大的那個(gè)平移位置及所在尺度。因此這種方法可以同時(shí)檢測目標中心變化和尺度變化。

DSST fDSST

    從DSST到fDSST做了特征壓縮和scale filter加速即特征降維和插值，performance上升6.13%，fps上升83.37%。

    DSST將目標跟蹤看成目標中心平移和目標尺度變化兩個(gè)獨立問(wèn)題。首先用HoG特征的DCF訓練平移相關(guān)濾波，負責檢測目標中心平移。然后用HoG特征的MOSSE(這里與DCF的區別是不加padding)訓練另一個(gè)尺度相關(guān)濾波，負責檢測目標尺度變化。2017年發(fā)表的文章又提出了加速版本fDSST。

    尺度濾波器僅需要檢測出最佳匹配尺度而無(wú)須關(guān)心平移情況，其計算原理如圖。DSST將尺度檢測圖像塊全部縮小到同一個(gè)尺寸計算特征（CN+HoG），再將特征表示成一維(沒(méi)有循環(huán)移位)，尺度檢測的響應圖也是一維的高斯函數。

    DSST本來(lái)就是對尺度自適應問(wèn)題的快速解決方案(支持33個(gè)尺度還比SAMF快很多)，在fDSST中MD大神又對DSST進(jìn)行加速：

    平移濾波器：PCA方法將平移濾波器的HOG特征從31通道降維到18通道，這一步驟與上面的CN特征類(lèi)似，直接用PCA進(jìn)行降維，作者提到由于這里用了線(xiàn)性核，所以不需要CN中所用的平滑子空間約束，更加簡(jiǎn)單粗暴。由于HOG特征天然會(huì )降低響應分辨率(cell_size=4)，這里也采用簡(jiǎn)單粗暴的方法，將響應圖的分辨率上采樣到原始圖像分辨率，也就是響應圖插值以提高檢測精度，方法是三角插值，等價(jià)于頻譜添0，方法更加簡(jiǎn)單粗暴，但這一步會(huì )增加算法復雜度，而且方法太簡(jiǎn)單也必然效果較差。

尺度濾波器：QR方法將尺度濾波器的HOG特征(二特征，沒(méi)有循環(huán)移位)~1000*17降維到17*17，由于自相關(guān)矩陣維度較大影響速度，為了效率這里沒(méi)有用PCA而是QR分解。多尺度數量是17(DSST中的一半)，響應圖是1*17，這里也通過(guò)插值方法將尺度數量從17插值到33以獲得更精確的尺度定位。

 SRDCF

    SRDCF與CFLB的思路都是擴大搜索區域，同時(shí)約束濾波模板的有效作用域解決邊界效應。給濾波模板增加一個(gè)約束，對接近邊界的區域懲罰更大，或者說(shuō)讓邊界附近濾波模板系數接近0，速度比較慢。

CFLB/BACF

    使搜索區域內，目標區域以外的像素為0，CFLB僅使用單通道灰度特征，最新BACF將特征擴展為多通道HOG特征。CFLB和BACF采用Alternating Direction Method of Multipliers(ADMM)快速求解。

DAT

    不是一種相關(guān)濾波方法，而是一種基于顏色統計特征方法。DAT統計前景目標和背景區域的顏色直方圖，這就是前景和背景的顏色概率模型，檢測階段，利用貝葉斯方法判別每個(gè)像素屬于前景的概率，得到像素級顏色概率圖

STAPLE STAPLE+CA

    從Staple到STAPLE+CA加入Context-Aware約束項，performance上升3.28%，fps下降43.18%，說(shuō)明約束項有效，但犧牲了大量fps。STAPLE結合了模板特征方法DSST和顏色統計特征方法DAT。

    相關(guān)濾波模板類(lèi)特征(HOG)對快速變形和快速運動(dòng)效果不好，但對運動(dòng)模糊光照變化等情況比較好；而顏色統計特征(DAT)對變形不敏感，而且不屬于相關(guān)濾波框架沒(méi)有邊界效應，但對光照變化和背景相似顏色不好。因此，這兩類(lèi)方法可以互補。

C-COT

    圖像特征的表達能力在目標跟蹤中起著(zhù)至關(guān)重要的作用。以HoG+CN為代表的圖像特征，性能優(yōu)秀而且速度優(yōu)勢非常突出，但也成為性能進(jìn)一步提升的瓶頸。以卷積神經(jīng)網(wǎng)絡(luò )（CNN）為代表的深度特征，具有更強大特征表達能力、泛化能力和遷移能力。將深度特征引入相關(guān)濾波也就水到渠成。

LMCF

    LMCF提出了兩個(gè)方法，多峰目標檢測和高置信度更新。多峰目標檢測對平移檢測的響應圖做多峰檢測，如果其他峰峰值與主峰峰值的比例大于某個(gè)閾值，說(shuō)明響應圖是多峰模式，以這些多峰為中心重新檢測，并取這些響應圖的最大值作為最終目標位置。

    高置信度更新：只有在跟蹤置信度比較高的時(shí)候才更新跟蹤模型，避免目標模型被污染。一個(gè)置信度指標是最大響應。另一個(gè)置信度指標是平均峰值相關(guān)能量(average peak-to correlation energy, APCE)，反應響應圖的波動(dòng)程度和檢測目標的置信水平。

CSR-DCF

    提出了空域可靠性和通道可靠性方法?？沼蚩煽啃岳脠D像分割方法，通過(guò)前背景顏色直方圖概率和中心先驗計算空域二值約束掩膜。這里的二值掩膜就類(lèi)似于CFLB中的掩膜矩陣P。CSR-DCF利用圖像分割方法更準確地選擇有效的跟蹤目標區域。通道可靠性用于區分檢測時(shí)每個(gè)通道的權重。

ECO ECO-HC

    ECO是C-COT的加速版，從模型大小、樣本集大小和更新策略三個(gè)方便加速，速度比C-COT提升了20倍，加量還減價(jià)，在VOT2016數據庫上EAO提升了13.3%，當然最厲害的還是hand-crafted features版本的ECO-HC有60FPS，接下來(lái)分別看看這三步。

    第一減少模型參數，既然CN特征和HOG特征都能降維，那卷積特征是不是也可以試試？這就是ECO中的加速第一步，也是最關(guān)鍵的一步，Factorized Convolution Operator分解卷積操作，效果類(lèi)似PCA，但Conv. Feat.與前面的CN和HOG又不一樣：

CNN特征維度過(guò)于龐大，在C-COT中是96+512=608通道，需要降很多很多維才能保證速度，而無(wú)監督降維如果太多會(huì )直接影響效果(對比通用方法 - 取特征值的95%以上的維度，保留信息量)；

雖然CNN特征遷移能力比較強，但這并不是針對跟蹤問(wèn)題專(zhuān)門(mén)訓練的特征，對跟蹤問(wèn)題有用的信息隱藏在大量CNN激活值中，如果簡(jiǎn)單的無(wú)監督降維，可能會(huì )過(guò)濾掉那些雖然不顯著(zhù)，但對跟蹤問(wèn)題有效的特征信息。當然HOG和CN特征也有同樣的問(wèn)題。

    通過(guò)使用PCA, 有監督降維：

    P就是那個(gè)降維矩陣，放在目標函數中優(yōu)化得到，具體求解比較復雜看論文吧，用PCA作為P的初始值去迭代優(yōu)化，采用Gauss-Newton和Conjugate Gradient方法。但每幀都迭代優(yōu)化降維矩陣速度反而會(huì )更慢，大神告訴我們僅在第一幀優(yōu)化這個(gè)降維矩陣就可以了，第一幀優(yōu)化完成后這個(gè)降維矩陣就是固定的，后續幀都直接用。Factorized Convolution Operator減少了80%的卷積特征還能略微提升性能，HC版本從31+11降維到10+3速度提升非常明顯。至于為什么降維了還能提升效果，論文中說(shuō)參數太多容易過(guò)擬合，也可能是判別力較低或者無(wú)用的通道響應圖會(huì )成為噪聲，淹沒(méi)較高判別力的通道響應圖。

    第二減少樣本數量，這個(gè)是針對Adaptive decontamination of the training set的加速，C-COT中要保存400個(gè)樣本，但視頻相鄰幀之間的相似性非常高，存在大量相似的冗余樣本，而且每次更新都要用樣本集中所有樣本做優(yōu)化，速度非常慢。ECO中改為緊湊的生成樣本空間模型compact generative mode，采用Gaussian Mixture Model (GMM)合并相似樣本，建立更具代表性和多樣性的樣本集，需要保存和優(yōu)化的樣本集數量降到C-COT的1/8。用特征距離衡量?jì)蓚€(gè)樣本的相似程度，樣本合并方法是兩個(gè)樣本特征的權值相加，樣本特征按照權值加權合并。

    第三改變更新策略，以前CF方法都是每幀更新，這種過(guò)更新不僅慢，而且會(huì )導致模型對最近幾幀嚴重過(guò)擬合，對遮擋、變形和平面外旋轉等突然變化過(guò)度敏感，但對大多數方法都是無(wú)可奈何的，因為如KCF等方法不保存樣本，這一幀不更新就再也沒(méi)機會(huì )了。

    但ECO保存了所有樣本的代表性樣本集，所以完全沒(méi)有必要每幀都更新，這里采用了sparser updating scheme(稀疏更新策略)，即每隔5幀更新一次模型參數，這不但提高了算法速度，而且提高了對突變，遮擋等情況的穩定性，三步優(yōu)化中稀疏更新對效果提升最大。由于ECO的樣本集是每幀都更新的，稀疏更新并不會(huì )錯過(guò)間隔期的樣本變化信息，但這種方法可能不適合沒(méi)有樣本集的方法，如KCF，因為沒(méi)有保存樣本集。

本文僅做學(xué)術(shù)分享，如有侵權，請聯(lián)系刪文。