1、視頻目標檢測與跟蹤算法綜述1、引言 運動目標的檢測與跟蹤是機器視覺領域的核心課題之一，目前被廣泛應用在視頻編碼、智能交通、監控、圖像檢測等眾多領域中。本文針對視頻監控圖像的運動目標檢測與跟蹤方法，分析了近些年來國內外的研究工作及最新進展。2、視頻監控圖像的運動目標檢測方法運動目標檢測的目的是把運動目標從背景圖像中分割出來。運動目標的有效分割對于目標分類、跟蹤和行為理解等后期處理非常重要。目前運動目標檢測算法的難點主要體現在背景的復雜性和目標的復雜性兩方面。背景的復雜性主要體現在背景中一些噪聲對目標的干擾，目標的復雜性主要體現在目標的運動性、突變性以及所提取目標的非單一性等等。所有這些特點使得運

2、動目標的檢測成為一項相當困難的事情。目前常用的運動目標檢測算法主要有光流法、幀差法、背景相減法，其中背景減除法是目前最常用的方法。2.1 幀差法幀差法主要是利用視頻序列中連續兩幀間的變化來檢測靜態場景下的運動目標，假設和分別為圖像序列中的第k幀和第k+1幀中象素點(x，y)的象素值,則這兩幀圖像的差值圖像就如公式2-1 所示： (2-1)2-1式中差值不為0的圖像區域代表了由運動目標的運動所經過的區域（背景象素值不變），又因為相鄰視頻幀間時間間隔很小，目標位置變化也很小，所以運動目標的運動所經過的區域也就代表了當前幀中運動目標所在的區域。利用此原理便可以提取出目標。下圖給出了幀差法的基本流程：

3、1、首先利用2-1 式得到第k幀和第k+1幀的差值圖像；2、對所得到的差值圖像二值化（如式子2-2 示）得到Qk+1；3、為消除微小噪聲的干擾，使得到的運動目標更準確，對進行必要的濾波和去噪處理，后處理結果為。 （T為閾值） （2-2）幀差流程圖從結果看在簡單背景下幀差法基本可檢測到運動目標所在的位置，而且計算簡單，復雜度低。當圖像采樣間隔較小時，幀差法對圖像場景變化不敏感，這是幀差法的優點，但同時目標部分漏檢的可能性增大了，容易使檢測到的目標出現空洞。在實際應用中，由于幀差法的簡易性，幀差法經常作為某些改進算法的基礎。2.2 光流法光流的概念30,31是由Gibson 在1950 年首先提出

4、的，光流理論在計算機視覺，三維運動分析中有著非常廣泛的作用。外界物體由于運動在人的視網膜上產生一系列連續變化的信息，這些信息就如同是光的流一樣不斷從眼中流過，故此稱之為光流。1981 年Horn 和Schunck 創造性的將二維速度場和我們通常所說的圖像的灰度聯系在一起，提出了光流約束方程，從而使得光流的計算有了最基本的方法。隨后光流法不斷發展，按照理論基礎分為：微分法，快匹配法，基于能量的方法，基于相位的方法，其中尤以微分法最為常用，該方法主要是基于下面兩種假設：1、強度不變假設，即在一組連續的二維圖像序列中，某個目標的運動軌跡在各幀中對應的像素點具有相同的灰度值。2、全局平滑假設，即物體的

5、運動矢量是局部平滑的或只有緩慢變化。特別是剛體運動，各相鄰像素點具有相同的運動速度，即速度平滑。這時，光流矢量梯度的模值的平方應該最小，用x 和y分量的拉普拉斯算子的平方和來表征光流場的平滑程度。假如給定一個圖像上m點坐標為(x，y),且它在t時刻的象素值為在時刻該點運動到，象素值為：則在強度不變的假設下： （2-3）公式2-3即為光流約束方程，將式2-3泰勒展開，并令趨于0，我們可以得到： （2-4）其中，即為像素點在圖像平面運動產生的瞬時速度場也即光流場。光流法的主要任務就是通過求解光流約束方程求出u、v，但是由于只有一個方程，并不能唯一確定u和v，這就用到了第二個假設，在該假設下就是要使

6、得： （2-5）其中 是個權重系數，一般取0.5,這樣聯合(2-4)式和(2-5)式即可得到： （3-6）從推導的過程看，光流法的計算非常復雜，難于滿足實時性的要求，且在目標提取時對噪聲很敏感，所以此算法還難以直接在實際中推廣使用。2.3 背景減除法背景減除法是將視頻幀與背景模型進行比較，通過判定灰度等特征的變化，或用直方圖等統計信息的變化來判斷異常情況的發生和分割出運動目標。基于背景差的方法，概念非常清晰。該方法與幀差法相比，可以檢測出短時間靜止的目標，如短時間靜止的車輛(長時間靜止的車輛可以歸為背景)，且不受車速快慢的限制；與光流法相比，背景差法可以通過簡化算法，降低計算量，滿足視頻檢測的

7、實時性要求。但隨著研究的不斷深人，算法的復雜性也在不斷提高，特別是對較復雜場景下的前景（運動目標）檢測，如針對光照變化場景下的目標檢測(室外的環境光、室內的燈光等)，針對含有高噪聲場景區域的目標檢測(場景中含有樹木、水面、旗幟等物體的反復運動)，針對場景頻繁發生改變(車輛停止、背景中物體搬動等)情況下的目標檢測等問題，使得算法的復雜性大大提高。用背景減除法進行運動目標檢測的主要過程包括預處理、背景建模、前景檢測和運動區域后處理等。背景建模是背景減除法的核心環節，目前主要方法有：基于背景的時間差分法、中值濾波法、W4方法、線性預測法、非參數模型法(又稱內核密度估計法)、混合Gauss法、隱馬爾科

8、夫模型法(HMM)、本征法、基于均值替換的背景估計法、碼本方法等。目前用無參的核密度估計方法對復雜場景的背景建模正成為背景差方法研究的熱點，該方法特別針對具有微小重復運動的場合，如含有搖動的樹葉、晃動的灌木叢、旋轉的風扇、海面波濤、雨雪天氣、光線反射等運動的場合。由于基于無參的核密度估計的背景建模是對一段視頻的統計分析，在對視頻圖像中的背景進行建模時，計算量很大，這勢必會影響算法的實時性，因此需要在提高背景建模的速度與準確率上做大量的研究工作，同時改進模型的適應性。另外，背景更新策略方面，如何判斷是否需要更新背景模型，如何及時的更新背景模型都是現階段困擾研究人員的問題。基于無參方法的背景差法主

9、要分為四個步驟：1、利用無參法對背景進行建模，2、核函數帶寬選擇，3.對背景模型進行更新，4、運動目標的提取。對于以上三種運動目標的檢測方法，幀差法實現最為簡單，但目標提取效果較差，該方法通常可以作為某種改進算法的基礎。光流法相對準確，但計算復雜，實時性很差，且對多目標提取困難。背景差法可以較好的提取目標輪廓，但該方法涉及對背景的建模，建模過程比較復雜。這些早期提出的移動目標檢測方法大都單獨地處理各個像素的灰度值或顏色而沒有考慮較大尺度上的特征，故可稱它們為基于像素的方法。典型的方法包括均值-閾限方法、高斯混合模型、非參數模型等。由于這些方法沒有充分利用局部像素之間的關系信息，很多有效的圖像特

10、征無法得到表示，從而導致移動目標檢測精度及效度都受到影響。后期大量的檢測方法都不同程度地利用了局部區域層次的信息，稱為基于區域的方法。典型的基于區域的方法包括紋理方法直方圖方法等。針對移動目標檢測的各種像素級、區域級特征不斷被提出，它們各有各的優缺點。如何能夠設計一種特征將這些特征統一地結合在一起，從而充分利用各自的優勢顯得非常有意義。 一種簡單的思路是用幾種特征組成特征向量，并利用該向量作為各個像素的特征：3、視頻目標跟蹤算法運動目標跟蹤是在目標檢測的基礎上，對檢測到的目標進行有效跟蹤。目前，在視頻監控、人機交互及某些高級的視頻系統中，對感興趣目標的跟蹤是其中必不可少的重要環節，它為后面更高

11、級的視覺應用提供有價值的信息。通常影響跟蹤的因素主要有四個：目標模板的表示，候選目標的表示，相似度的衡量和搜索的策略。衡量跟蹤算法優劣的條件有兩個，即實時性和魯棒性，所以一個好的跟蹤算法應滿足：1. 實時性好：算法要費時少，至少要比視頻采集系統的采集速率快，否則將無法實現對目標的正常跟蹤。如果跟蹤系統還涉及到其他的圖像處理環節，那么就要預留較多的時間給圖像處理部分，所以實時性至關重要。2. 魯棒性強：實際的觀測環境，圖像的背景可能很復雜。光照、圖像噪音及隨時可能出現的目標遮擋，均使目標的跟蹤變得非常困難。因此算法的魯棒性對跟蹤效果的好壞起著重要的作用。以上提到的兩條很難在系統中同時得以滿足，往

12、往需要某種折中，以期得到較好的綜合性能。通常運動目標的跟蹤可以分為運動目標檢測、運動目標的特征選取和目標的后續跟蹤三個階段。由此可見跟蹤算法遠比單純的目標檢測算法復雜的多。根據被跟蹤目標信息使用情況的不同，可將視覺跟蹤算法分為：基于對比度分析的目標跟蹤、基于匹配的目標跟蹤和基于運動檢測的目標跟蹤。基于對比度分析的跟蹤算法主要利用目標和背景的對比度差異，實現目標的檢測和跟蹤。基于匹配的跟蹤主要通過前后幀之間的特征匹配實現目標的定位。基于運動檢測的跟蹤主要根據目標運動和背景運動之間的差異實現目標的檢測和跟蹤。前兩類方法都是對單幀圖像進行處理。基于匹配的跟蹤方法需要在幀與幀之間傳遞目標信息。對比度跟

13、蹤不需要在幀與幀之間傳遞目標信息。基于運動檢測的跟蹤需要對多幀圖像進行處理。除此之外，還有一些算法不易歸類到以上3類，如多目標跟蹤算法或其他一些綜合算法。3.1 基于對比度分析的目標跟蹤算法基于對比度分析的目標跟蹤算法利用目標與背景在對比度上的差異來提取、識別和跟蹤目標。這類算法按照跟蹤參考點的不同可以分為邊緣跟蹤、形心跟蹤和質心跟蹤等。這類算法不適合復雜背景中的目標跟蹤，但在空中背景下的目標跟蹤中非常有效。邊緣跟蹤的優點是脫靶量計算簡單、響應快，在某些場合(如要求跟蹤目標的左上角或右下角等)有其獨到之處。缺點是跟蹤點易受干擾，跟蹤隨機誤差大。重心跟蹤算法計算簡便，精度較高，但容易受到目標的劇

14、烈運動或目標被遮擋的影響。重心的計算不需要清楚的輪廓在均勻背景下可以對整個跟蹤窗口進行計算，不影響測量精度。重心跟蹤特別適合背景均勻、對比度小的弱小目標跟蹤等一些特殊場合。圖像二值化后，按重心公式計算出的是目標圖像的形心。一般來說形心與重心略有差別。3.2 基于匹配的目標跟蹤算法 特征匹配特征是目標可區別與其他事物的屬性，具有可區分性、可靠性、獨立性和稀疏性。基于匹配的目標跟蹤算法需要提取目標的特征，并在每一幀中尋找該特征。尋找的過程就是特征匹配過程。特征提取是一種變換或者編碼，將數據從高維的原始特征空間通過映射，變換到低維空間的表示 根據Marr的特征分析理論，有4種典型的特征計算理論：神經

15、還原論、結構分解理論、特征空間論和特征空間的近似。神經還原論直接源于神經學和解剖學的特征計算理論，它與生物視覺的特征提取過程最接近，其主要技術是Gabor濾波器、小波濾波器等。結構分解理論是到目前為止唯一能夠為新樣本進行增量學習提供原則的計算理論，目前從事該理論研究的有麻省理T學院實驗組的視覺機器項目組等。特征空間論主要采用主分量分析(PCA)、獨立分量分析(ICA)、稀疏分量分析(SCA)和非負矩陣分解(NMF)等技術抽取目標的子空間特征。特征空間的近似屬于非線性方法，適合于解決高維空間上復雜的分類問題，主要采用流形、李代數、微分幾何等技術。目標跟蹤中用到的特征主要有幾何形狀、子空間特征、外

16、形輪廓和特征點等。其中，特征點是匹配算法中常用的特征。特征點的提取算法很多，如Kanade LucasTomasi(KLT)算法、Harris算法、SIFT算法以及SURF算法等。特征點一般是稀疏的，攜帶的信息較少，可以通過集成前幾幀的信息進行補償。目標在運動過程中，其特征(如姿態、幾何形狀、灰度或顏色分布等)也隨之變化。目標特征的變化具有隨機性，這種隨機變化可以采用統計數學的方法來描述。直方圖是圖像處理中天然的統計量，因此彩色和邊緣方向直方圖在跟蹤算法中被廣泛采用。 貝葉斯跟蹤目標的運動往往是隨機的。這樣的運動過程可以采用隨機過程來描述。很多跟蹤算法往往建立在隨機過程的基礎之上，如隨機游走過

17、程、馬爾科夫過程、自回歸(AR)過程等。隨機過程的處理在信號分析領域較成熟，其理論和技術(如貝葉斯濾波)可以借鑒到目標跟蹤中。貝葉斯濾波中，最有名的是Kalman濾波(KF)。KF可以比較準確地預測平穩運動目標在下一時刻的位置，在彈道目標跟蹤中具有非常成功的應用。一般而言，KF可以用作跟蹤方法的框架，用于估計目標的位置，減少特征匹配中的區域搜索范圍，提高跟蹤算法的運行速度 KF只能處理線性高斯模型，KF算法的兩種變形EKF和UKF可以處理非線性高斯模型。兩種變形擴展了KF的應用范圍，但是不能處理非高斯非線性模型，這個時候就需要用粒子濾波(PF)。由于運動變化，目標的形變、非剛體、縮放等問題，定

18、義一個可靠的分布函數是非常困難的，所以在PF中存在例子退化問題，于是引進了重采樣技術。事實上，貝葉斯框架下視覺跟蹤的很多工作都是在PF框架下尋找更為有效的采樣方法和建議概率分布。這些工作得到了許多不同的算法。如馬爾可夫鏈蒙特卡洛(MCMC)方法、Unscented粒子濾波器(UPF)、RaoBlackwellised粒子濾波器(RBPF)等等文獻【5】引入了一種新的自適應采樣方法 序貫粒子生成方法在該方法中粒子通過重要性建議概率密度分布的動態調整順序產生。文獻【6】根據率失真理論推導了確定粒子分配最優數目的方法，該方法可以最小化視覺跟蹤中粒子濾波的整體失真。文獻【7】計算最優重要性采樣密度分布

19、和一些重要密度分布之間的KL距離，分析了這些重要密度分布的性能。文獻【8】在粒子濾波框架下，采用概率分類器對目標觀測量進行分類，確定觀測量的可靠性，通過加強相關觀測量和抑制不相關觀測量的方法提高跟蹤性能。除了KF和PF之外，隱馬爾科夫模型(HMMs)和動態貝葉斯模型(DBNs) 也是貝葉斯框架下重要的視覺跟蹤方法。HMMs和DBNs將運動目標的內部狀態和觀測量用狀態變量(向量)表示，DBNs使用狀態隨機變量(向量)集，并在它們之間建立概率關聯。HMMs將系統建模為馬爾科夫過程。這些算法的主要區別如表1所示。表1 貝葉斯跟蹤算法算法描述能力狀態表示方法拓撲結構KF線性、高斯一個隨機變量（向量）固

20、定PF非線性、任意分布一個隨機變量（向量）固定HMMs非線性、任意分布一個隨機變量（向量）固定DBNs非線性、任意分布隨機變量（向量）集可變表1中每個簡單的算法都可以看成是下一行復雜算法的特例。反之，每個復雜算法都可以看成是簡單算法的擴展。其中DBNs具有最佳的靈活性，可以處理不同的運動模型和不同的狀態變量組合。DBNs又可以看作概率圖模型(PGMs)的一個例子。PGMs的基本思想是用圖形的方式將多變量概率分布分解統計變量用圖的節點表示，變量間的條件關系用圖的連接或邊表示。PGMs可以分為有向圖(DAGs)和無向圖(Ugs)。前者能夠處理時間模式，適合目標跟蹤和場景理解等任務。后者能很好地描述

21、圖像像素之間的空間依賴性適合圖像分割和圖像分析等任務。通過組合圖理論和概率理論，PGMs可以用來處理問題描述中的不確定性。不確定性恰好符合人類視覺系統中天然的概率性和視覺模糊性(如遮擋從3D到2D投影的信息損失)。通過規定概率模型元素之間的關系，PGMs可以有效地表示、學習和計算復雜的概率模型。PGMs能夠有效地組合目標的動態信息和外觀信息，有效解決目標的運動估計問題，為目標跟蹤提供了很好的理論框架。表1中算法都可以看成是PGMs的特殊形式。 核方法核方法的基本思想是對相似度概率密度函數或者后驗概率密度函數采用直接的連續估計。這樣處理一方面可以簡化采樣，另一方面可以采用估計的函數梯度有效定位采

22、樣粒子。采用連續概率密度函數可以減少高維狀態空間引起的計算量問題，還可以保證例子接近分布模式，避免粒子退化問題。核方法一般都采用彩色直方圖作為匹配特征。Mean ShiftI 是核方法中最有代表性的算法，其含義正如其名。是“偏移的均值向量”。直觀上看，如果樣本點從一個概率密度函數中采樣得到，由于非零的概率密度梯度指向概率密度增加最大的方向，從平均上來說，采樣區域內的樣本點更多的落在沿著概率密度梯度增加的方向。因此，對應的Mean Shift向量應該指向概率密度梯度的負方向。Mean Shift跟蹤算法反復不斷地把數據點朝向MeanShift矢量方向進行移動，最終收斂到某個概率密度函數的極值點。

23、在Mean Shift跟蹤算法中。相似度函數用于刻畫目標模板和候選區域所對應的兩個核函數直方圖的相似性，采用的是Bhattacharyya系數。因此。這種方法將跟蹤問題轉化為Mean Shift模式匹配問題。核函數是Mean Shift 算法的核心，可以通過尺度空間差的局部最大化來選擇核尺度，若采用高斯差分計算尺度空間差，則得到高斯差分Mean Shift算法。Mean Shift算法假設特征直方圖足夠確定目標的位置，并且足夠穩健，對其他運動不敏感。該方法可以避免目標形狀、外觀或運動的復雜建模，建立相似度的統計測量和連續優化之間的聯系。但是，Mean Shift算法不能用于旋轉和尺度運動的估計

24、。為克服以上問題，人們提出了許多改進算法，如多核跟蹤算法、多核協作跟蹤算法和有效的最優核平移算法等。文獻11則針對可以獲得目標多視角信息的情況，提出了一種從目標不同視角獲得多個參考直方圖，增強Mean Shift跟蹤性能的算法。3.3 基于運動檢測的目標跟蹤算法基于運動檢測的目標跟蹤算法通過檢測序列圖像中目標和背景的不同運動來發現目標存在的區域。實現跟蹤。這類算法不需要幀之間的模式匹配，不需要在幀間傳遞目標的運動參數，只需要突出目標和非目標在時域或者空域的區別即可。這類算法具有檢測多個目標的能力，可用于多目標檢測和跟蹤。這類運動目標檢測方法主要有幀間圖像差分法、背景估計法、能量積累法、運動場估

25、計法等。光流算法是基于運動檢測的目標跟蹤的代表性算法。光流是空間運動物體在成像面上的像素運動的瞬時速度，光流矢量是圖像平面坐標點上的灰度瞬時變化率。光流的計算利用圖像序列中的像素灰度分布的時域變化和相關性來確定各自像素位置的運動，研究圖像灰度在時間上的變化與景象中物體結構及其運動的關系。將二維速度場與灰度相聯系，引入光流約束方程，得到光流計算的基本算法。根據計算方法的不同，可以將光流算法分為基于梯度的方法、基于匹配的方法、基于能量的方法、基于相位的方法和基于神經動力學的方法。文獻【12】提出了一種基于攝像機光流反向相關的無標記跟蹤算法，該算法利用反向攝像機消除光流中的相同成分，得到有效的跟蹤效果。文獻【13】將光流算法的亮度約束轉化為上下文約束把上下文信息集成到目標跟蹤的運動估計里，仿照光流算法，提出了上下文流算法。文獻【14】引入了幾何流的概念，用于同時描述目標在空間上和時間上的運