運(yùn)動(dòng)目標(biāo)檢測(cè)和跟蹤算法綜述

王慧

摘要：運(yùn)動(dòng)目標(biāo)檢測(cè)和跟蹤在多媒體圖像、視頻監(jiān)控等方面有普遍應(yīng)用。多年來(lái)，人們?cè)谠擃I(lǐng)域進(jìn)行了大量的、深入的研究，發(fā)表了大量顯著性的成果。但目標(biāo)被遮擋、尺度變化以及光照變化仍然對(duì)跟蹤結(jié)果存在較大影響。為解決這些問(wèn)題，研究人員仍然在研究如何能構(gòu)造一個(gè)魯棒性好的跟蹤算法。該文主要對(duì)近年來(lái)常見的運(yùn)動(dòng)目標(biāo)檢測(cè)和跟蹤算法的發(fā)展做了簡(jiǎn)單敘述。簡(jiǎn)單分析了運(yùn)動(dòng)目標(biāo)檢測(cè)的幀間差分法、背景減法、光流法的原理；描述了運(yùn)動(dòng)目標(biāo)跟蹤所用的Meanshift算法、Kalman濾波器、粒子濾波方法；最后對(duì)壓縮感知理論進(jìn)行簡(jiǎn)介，并對(duì)基于該理論的兩種算法：稀疏表示的目標(biāo)跟蹤算法和實(shí)時(shí)壓縮感知目標(biāo)跟蹤算法做出系統(tǒng)的描述。

關(guān)鍵詞：運(yùn)動(dòng)目標(biāo)檢測(cè)；運(yùn)動(dòng)目標(biāo)跟蹤；壓縮感知；稀疏表示；特征提取

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）24-0194-04

Abstract：Moving target detection and tracking are widely used in multimedia images， video surveillance，etc. Over the years， people have done a lot of in-depth research in this field， and published a lot of significant results. However， target occlusion， scale change and illumination change still have a great impact on tracking results. To solve these problems， researchers are still studying how to construct a robust tracking algorithm. In this paper， we briefly describe the development of common algorithms for moving object detection and tracking in recent years. The principle of frame difference method， background subtraction and optical flow method for moving object detection is simply analyzed. The Meanshift algorithm， Kalman filter and particle filter method for moving target tracking are described. In the end， a brief introduction to the theory of compressed sensing is made. And two algorithms based on this theory are described： sparse representation tracking and compressive tracking.

Key words： moving target detection； moving target tracking； compressed sensing； sparse representation； feature extraction

1 引言

運(yùn)動(dòng)目標(biāo)檢測(cè)和跟蹤是計(jì)算機(jī)視覺學(xué)科主要的研究方向之一，涵蓋了自動(dòng)控制、圖像處理、智能識(shí)別等學(xué)科，目前在多個(gè)領(lǐng)域比如視頻監(jiān)控、人工智能、軍事等方面有非常廣泛的應(yīng)用。

運(yùn)動(dòng)目標(biāo)檢測(cè)與跟蹤是分目標(biāo)檢測(cè)和目標(biāo)跟蹤兩方面。目標(biāo)檢測(cè)指的是在監(jiān)視的場(chǎng)景中對(duì)運(yùn)動(dòng)的目標(biāo)做實(shí)時(shí)檢測(cè)，并提取該目標(biāo)。目標(biāo)跟蹤是在將目標(biāo)檢測(cè)出來(lái)后，根據(jù)該目標(biāo)的特征，利用合適的算法，在一系列圖像中尋找目標(biāo)的位置。運(yùn)動(dòng)目標(biāo)跟蹤可以提供目標(biāo)的運(yùn)動(dòng)軌跡，可以對(duì)目標(biāo)準(zhǔn)確定位，為下一步對(duì)目標(biāo)行為分析與理解提供可靠的數(shù)據(jù)來(lái)源，同時(shí)也可以為運(yùn)動(dòng)目標(biāo)檢測(cè)提供幫助，形成一個(gè)良性的循環(huán)。

2 運(yùn)動(dòng)目標(biāo)檢測(cè)算法

運(yùn)動(dòng)目標(biāo)檢測(cè)是指在視頻圖像序列中檢測(cè)出變化區(qū)域并將運(yùn)動(dòng)目標(biāo)從背景圖像中提取出來(lái)。由于目標(biāo)分類、跟蹤和行為分析等后續(xù)處理過(guò)程只是對(duì)運(yùn)動(dòng)的目標(biāo)像素區(qū)域做分析，因此如何能正確的將運(yùn)動(dòng)目標(biāo)檢測(cè)與分割出來(lái)非常重要。

通常檢測(cè)運(yùn)動(dòng)物體的有三種方法，第一種是用幀間差分法；第二種是背景減法；第三種是光流法。

2.1 幀差法

幀間差分法簡(jiǎn)單來(lái)說(shuō)就是將前后兩幀圖像對(duì)應(yīng)像素值相減。如果差值很小，認(rèn)為此處?kù)o止，如果差值很大，則認(rèn)為是由于物體運(yùn)動(dòng)引起的。把所有差值很大的像素標(biāo)記出來(lái)，就是運(yùn)動(dòng)目標(biāo)在圖像中的位置，當(dāng)然前提條件是前后兩幀圖像的環(huán)境亮度基本不變。如果背景亮度的差別很大，以及目標(biāo)在光照下的陰影處理，幀間差分法還需要考慮更多的內(nèi)容。

幀間差分法的主要優(yōu)點(diǎn)是：算法簡(jiǎn)單，程序設(shè)計(jì)復(fù)雜度低，實(shí)時(shí)性強(qiáng)。但在實(shí)際應(yīng)用中，這種最基本的幀間差分法精度不高，要求背景絕對(duì)靜止或很少有變化，對(duì)目標(biāo)很難精確標(biāo)記出來(lái)。

如果背景是動(dòng)態(tài)的，有很多改進(jìn)方法，常見的有雙差分法，區(qū)域差分方法等。雙差分方法是在第一次差分圖像的基礎(chǔ)上再將像素相乘，由于噪聲在時(shí)間域上很難重復(fù)，相乘后就可以除去孤立的噪點(diǎn)。區(qū)域差方法是在某一模板上做差分，利用空間信息將噪聲消除。

2.2 背景差法

背景差法[1]是用圖像序列中的視頻幀與背景圖像相減而檢測(cè)出目標(biāo)的方法，之后選擇一個(gè)合理閾值對(duì)差值圖像進(jìn)行二值化，從而獲取運(yùn)動(dòng)目標(biāo)。

簡(jiǎn)單常用的方式為：直接把視頻序列中某一幅圖像提取出來(lái)，或以多幅圖像的平均值作為背景。最簡(jiǎn)單的背景模型是時(shí)間平均圖像，提供的目標(biāo)特征數(shù)據(jù)也很完全。但這種背景對(duì)場(chǎng)景變化，比如光照等干擾敏感度較強(qiáng)。

背景差分法計(jì)算也很簡(jiǎn)單，得到的運(yùn)動(dòng)目標(biāo)也比較完整，并且對(duì)視頻中停止運(yùn)動(dòng)的物體也可以檢測(cè)出來(lái)。缺點(diǎn)是如果出現(xiàn)了較大的光照和場(chǎng)景變化，可能會(huì)出現(xiàn)較多的噪聲點(diǎn)，這就需要及時(shí)更新背景，因此算法的復(fù)雜性增加，實(shí)時(shí)性變差；而且閾值的選取對(duì)檢測(cè)效果影響較大，一個(gè)好的閾值可以大大提高檢測(cè)的精度。

2.3 光流法

在空間中，運(yùn)動(dòng)可以用運(yùn)動(dòng)場(chǎng)描述。在一個(gè)圖像平面上，物體的運(yùn)動(dòng)往往通過(guò)圖像序列中不同圖像灰度分布的變化體現(xiàn)?？臻g中的運(yùn)動(dòng)場(chǎng)轉(zhuǎn)移到圖像上就表示為光流場(chǎng)，光流場(chǎng)反映了圖像上每一點(diǎn)灰度在空間位置的變化趨勢(shì)。光流是研究圖像灰度在時(shí)間上的變化與景象中物體結(jié)果及其運(yùn)動(dòng)的關(guān)系。

光流法的優(yōu)點(diǎn)是不需要預(yù)先知道場(chǎng)景的任何信息，就能夠檢測(cè)出獨(dú)立運(yùn)動(dòng)的對(duì)象，可用于靜態(tài)、動(dòng)態(tài)背景。缺點(diǎn)是如果運(yùn)動(dòng)目標(biāo)的亮度變化較大，會(huì)影響結(jié)果準(zhǔn)確性；難以檢測(cè)暫時(shí)不動(dòng)的目標(biāo)；計(jì)算復(fù)雜，抗噪性能差，實(shí)時(shí)性差。

3 運(yùn)動(dòng)跟蹤

目標(biāo)跟蹤技術(shù)的基本思想是在序列視頻圖像中，已知需要跟蹤的目標(biāo)信息，通過(guò)提取出目標(biāo)的各種特征來(lái)建模得到目標(biāo)模板，再用候選模板與目標(biāo)模板進(jìn)行相似匹配，從而得到目標(biāo)的新位置。由于目標(biāo)可能因光照、遮擋、變形等各種影響導(dǎo)致目標(biāo)特征發(fā)生變化，所以跟蹤技術(shù)很重要的一點(diǎn)是要實(shí)時(shí)更新目標(biāo)模板，從而達(dá)到精準(zhǔn)跟蹤定位的目的。

運(yùn)動(dòng)目標(biāo)跟蹤算法中常用的數(shù)學(xué)工具有卡爾曼濾波（Kalman Filtering）及其改進(jìn)算法、動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)（Dynamic Bayesian Network）算法以及粒子濾波（Particle Filte ring）算法。

3.1 基于Mean Shift的跟蹤算法

Meanshift是1975年提出的，是先計(jì)算出當(dāng)前點(diǎn)的偏移均值，再移動(dòng)該點(diǎn)到其偏移均值，然后以此為一個(gè)新起點(diǎn)，持續(xù)移動(dòng)迭代，直到最后達(dá)到一定的條件要求結(jié)束。

Meanshift算法是一種非參估計(jì)方法，它根據(jù)運(yùn)動(dòng)目標(biāo)的顏色概率分布直方圖，在每一幀中，對(duì)目標(biāo)鄰近區(qū)域中做最大化尋找，完成目標(biāo)的跟蹤。 MeanShift算法對(duì)跟蹤目標(biāo)初始化時(shí)，需要人工選定目標(biāo)區(qū)域，首先在第一幀目標(biāo)區(qū)域，按像素點(diǎn)計(jì)算特征空間的每個(gè)特征值的概率，這樣將候選目標(biāo)模型描述出來(lái)；然后在后續(xù)每幀圖像描述出候選模型，即在可能存在目標(biāo)的候選區(qū)域中，對(duì)特征空間的每個(gè)特征值的概率進(jìn)行計(jì)算，使用相似性函數(shù)來(lái)判斷目標(biāo)模型與當(dāng)前候選模型的相似程度，相似性函數(shù)一般用 Bhattacharyya系數(shù)， 通過(guò)反復(fù)的迭代，最終在當(dāng)前候選幀中得到目標(biāo)最優(yōu)位置。該算法的優(yōu)點(diǎn)是對(duì)目標(biāo)邊緣遮擋、旋轉(zhuǎn)、變形不敏感， 計(jì)算量不大。

3.2 Kalman濾波器

Rudolph E.Kalman在1960年發(fā)表了一種最優(yōu)化的遞歸方法——卡爾曼濾波，可以用于解決離散數(shù)據(jù)的線性濾波問(wèn)題，是一種遞歸的估計(jì)方法。利用該方法，有了系統(tǒng)前一時(shí)刻狀態(tài)就能估計(jì)出系統(tǒng)下一時(shí)刻的狀態(tài)，同時(shí)還可利用當(dāng)前的觀測(cè)值修正系統(tǒng)狀態(tài)，估計(jì)的均方誤差最小。因?yàn)榭柭鼮V波器計(jì)算時(shí)具有無(wú)偏、穩(wěn)定和最優(yōu)的特點(diǎn)，因此在自動(dòng)控制系統(tǒng)中用的比較多。

3.3 粒子濾波

粒子濾波是一種通過(guò)非參數(shù)化的蒙特卡羅方法（Monte Carlo methods）來(lái)實(shí)現(xiàn)遞推的貝葉斯濾波。粒子濾波的基本原理是通過(guò)先驗(yàn)概率和當(dāng)前觀測(cè)值估計(jì)后驗(yàn)概率。

4 基于壓縮感知的目標(biāo)跟蹤方法

目標(biāo)跟蹤領(lǐng)域有很多算法魯棒性都很好，例如文獻(xiàn)[2][3]在處理目標(biāo)跟蹤時(shí)引入了Super Pixel 概念，處理目標(biāo)的遮擋、紋理變化方面效果很好；而文獻(xiàn)[4]中對(duì)非剛性目標(biāo)跟蹤有很好的魯棒性；而文獻(xiàn)[5]將Distribution Fields（DFS）引入到目標(biāo)跟蹤中，針對(duì)的是目標(biāo)遮擋和大幅度運(yùn)動(dòng)的情況；等等。但是這些魯棒性很好的算法的計(jì)算量都很大，因此實(shí)時(shí)性不高。

在2009 年，Xue Mei等人提出（Robust Visual Tracking using L1 Minimization）跟蹤算法[6]，首次將壓縮感知理論引入到目標(biāo)跟蹤領(lǐng)域中。

4.1 壓縮感知理論簡(jiǎn)介

傳統(tǒng)的采樣定理（香農(nóng)定理）指出：采樣頻率不能低于模擬信號(hào)頻譜中最高頻率的2倍。以香農(nóng)定理方式采集的數(shù)據(jù)能夠無(wú)失真的恢復(fù)原始信號(hào)，但是采樣頻率很高，導(dǎo)致采樣后的信號(hào)仍然存在著大量的冗余，這樣造成傳輸和存儲(chǔ)的成本的增加，同時(shí)也降低了采樣效率。

壓縮感知（Compressive Sensing，CS）是由D. Donoho、E. Candes及華裔科學(xué)家T. Tao （菲爾茲獎(jiǎng)獲得者）等人提出[7-9]，該理論可以描述為：可壓縮的或者在某個(gè)變換域是稀疏的信號(hào)，可以通過(guò)少量的采樣，把高維信號(hào)通過(guò)一個(gè)與變換域的基不相關(guān)的測(cè)量矩陣投影到低維的空間中，然后利用一種恢復(fù)算法把低維的信號(hào)還原或重構(gòu)出原始的高維信號(hào)，如果重構(gòu)出的信號(hào)包含了原始高維信號(hào)足夠的信息，則證明了投影的低維信號(hào)或者說(shuō)較少的采樣就能夠高精度表示原模擬信號(hào)。

壓縮感知理論打破了經(jīng)典的Nyquist采樣定理，依據(jù)這個(gè)理論，信號(hào)的采樣取決于信號(hào)本身所具有的稀疏性或可壓性，極大降低了信號(hào)的采樣頻率，減少了數(shù)據(jù)的傳輸和存儲(chǔ)代價(jià)，同時(shí)也提高了信號(hào)處理的運(yùn)算速度，為信號(hào)處理領(lǐng)域帶來(lái)而來(lái)革命性的影響，被評(píng)為美國(guó) 2007 年十大科技進(jìn)步獎(jiǎng)之一。

由上述內(nèi)容可知，通過(guò)壓縮感知采樣后的信息去除了原始信息的數(shù)量膨大的冗余信息，同時(shí)還包含了重建原始信號(hào)的所有信息，采樣信息和原始信息具有一對(duì)一的特性。而在目標(biāo)跟蹤時(shí)需要處理的大量的圖像信息正是一種典型的具有稀疏性的信息，因此，目標(biāo)跟蹤領(lǐng)域現(xiàn)在也已經(jīng)使用壓縮感知理論[10-11]。

2009年之后的前幾年，學(xué)者們提出的基于壓縮感知的算法在本質(zhì)上都沒(méi)有繞開粒子濾波，都是對(duì)粒子進(jìn)行稀疏表示的目標(biāo)跟蹤，信號(hào)重建部分計(jì)算量很大。在2012年12月 ICCV會(huì)議上， Kaihua Zhang， Lei Zhang提出了實(shí)時(shí)性壓縮感知目標(biāo)跟蹤算法，算法中直接將目標(biāo)的樣本特征采樣，然后把將采樣后的特征作為目標(biāo)的特征。

4.2 基于稀疏表示的目標(biāo)跟蹤算法

稀疏表示的目標(biāo)跟蹤算法，其核心思想是將目標(biāo)跟蹤問(wèn)題轉(zhuǎn)成解決目標(biāo)的稀疏逼近問(wèn)題。跟蹤目標(biāo)時(shí)，用目標(biāo)模板和正負(fù)小模板[12]組成字典，首先對(duì)每一個(gè)候選目標(biāo)（粒子濾波產(chǎn)生的粒子），用該字典進(jìn)行稀疏求解，求解方法是利用L1最小化來(lái)完成；然后選擇具有最大概率的候選目標(biāo)（粒子）作為當(dāng)前幀的跟蹤結(jié)果。下一幀繼續(xù)使用粒子濾波器產(chǎn)生候選目標(biāo)（粒子），重復(fù)上面的過(guò)程直至完成。

4.3 實(shí)時(shí)壓縮感知目標(biāo)跟蹤算法（Compressive Tracking）

2012年Kaihua Zhang第一次提出一種提取特征進(jìn)行跟蹤的算法——實(shí)時(shí)壓縮感知目標(biāo)跟蹤算法（Compressive Tracking）。 算法首先使用一個(gè)非常稀疏的測(cè)量矩陣，該矩陣滿足約束等距性 restricted isometry property（ RIP），將高維的圖像特征空間降維到一個(gè)低維的壓縮子空間，然后分別將目標(biāo)和背景的特征提取出，作為正樣本和負(fù)樣本，這兩個(gè)樣本用于在線更新分類器，分類器使用樸素貝葉斯分類器，最后利用分類器分類下一幀圖像的目標(biāo)。

實(shí)時(shí)壓縮感知目標(biāo)跟蹤算法簡(jiǎn)單，將壓縮感知和目標(biāo)特征提取聯(lián)系在一起，計(jì)算量小，具有很好的實(shí)時(shí)性，但是該算法采用的目標(biāo)特征比較單一，如果在目標(biāo)紋理或光照變化時(shí)，跟蹤效果不穩(wěn)定。

5 總結(jié)

運(yùn)動(dòng)目標(biāo)檢測(cè)與跟蹤是計(jì)算機(jī)視覺技術(shù)領(lǐng)域中一個(gè)重要組成部分，目前應(yīng)用在多個(gè)方面，與人們?nèi)粘Ｉ钕⑾⑾嚓P(guān)。在研究目標(biāo)檢測(cè)與跟蹤算法時(shí)，目標(biāo)被遮擋、形變等是需要解決的難題。經(jīng)過(guò)多年的研究，以壓縮感知為基礎(chǔ)的算法慢慢發(fā)展起來(lái)。目前，基于稀疏表示的跟蹤算法正在不斷發(fā)展，實(shí)驗(yàn)效果良好，具有很好的發(fā)展前景。

參考文獻(xiàn)：

[1] University， Technical Report： CMU-RI-TR-00-12， 2000.

[2] Wang S， Lu H， Yang F， et al. Superpixel tracking[C] 2011 IEEE International Conference on.IEEE，Computer Vision （ICCV）， 2011： 1323-1330.

[3] Oron S， Bar-Hillel A， Levi D， et al. Locally orderless tracking[C] 2012 IEEE Conference on. IEEE，Computer Vision and Pattern Recognition （CVPR），2012： 1940-1947.

[4] Kwon J， Lee K M. Tracking of a non-rigid object via patch-based dynamic appearance modeling and adaptive basin hopping monte carlo sampling[C] IEEE Conference on. IEEE，Computer Vision and Pattern Recognition， 2009. CVPR 2009. 2009： 1208-1215.

[5] Sevilla-Lara L， Learned-Miller E. Distribution fields for tracking[C] 2012 IEEE Conference on. IEEE，Computer Vision and Pattern Recognition （CVPR）， 2012： 1910-1917.

[6] X. Mei and H. Ling， "Robust visual tracking using1l minimization，" in Proc.IEEE Int. Conf. Comp. Vis.，Kyoto， Japan， 2009， 1436–1443.

[7] Donoho D L， Elad M， Temlyakov V N. Stable recovery of sparse overcomplete representations in the presence of noise[J]. IEEE Transactions on， Information Theory， 2006， 52（1）： 6-18.

[8] Donoho D L， Tsaig Y， Drori I， et al. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J]. IEEE Transactions on， Information Theory， 2012， 58（2）：1094-1121.

[9] Mallat S G， Zhang Z. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on， Signal Processing， 1993， 41（12）： 3397-3415.

[10] Li H， Shen C， Shi Q. Real-time visual tracking using compressive sensing[C] 2011 IEEE Conference on.IEEE， Computer Vision and Pattern Recognition （CVPR），2011： 1305-1312.

[11] Zhang K， Zhang L， Yang M H. Real-time compressive tracking[M] Computer Vision–ECCV 2012. Springer Berlin Heidelberg， 2012： 864-877.

[12] 張繼等.面向視頻的快速稀疏編碼算法.計(jì)算機(jī)與科學(xué).2012，6：1673-9418.

[13] Achlioptas D. Database-friendly random projections[C] Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems.ACM， 2001： 274-281.

[14] Zhang K， Zhang L， Yang M H. Real-time compressive tracking[M] Computer Vision–ECCV 2012. Springer Berlin Heidelb1erg， 2012： 864-877.

【通聯(lián)編輯：唐一東】