歡迎光臨
每天分享高質量文章

標的跟蹤演算法分類

(點擊上方公眾號,可快速關註)

來源:張醬油

https://www.cnblogs.com/necp-zwl/p/6486326.html

運動標的跟蹤主流演算法大致分類

主要基於兩種思路:

  • a)不依賴於先驗知識,直接從圖像序列中檢測到運動標的,併進行標的識別,最終跟蹤感興趣的運動標的;

  • b)依賴於標的的先驗知識,首先為運動標的建模,然後在圖像序列中實時找到相匹配的運動標的。

 

一.運動標的檢測

對於不依賴先驗知識的標的跟蹤來講,運動檢測是實現跟蹤的第一步。運動檢測即為從序列圖像中將變化區域從背景圖像中提取出來。運動標的檢測的演算法依照標的與攝像機之間的關係可以分為靜態背景下運動檢測和動態背景下運動檢測。

(一)靜態背景

1.背景差

2.幀差

3.GMM

4.光流

背景減演算法可以對背景的光照變化、噪聲干擾以及周期性運動等進行建模,在各種不同情況下它都可以準確地檢測出運動標的。因此對於固定攝像頭的情形,目前大多數的跟蹤演算法中都採用背景減演算法來進行標的檢測。背景減演算法的局限性在於它需要一個靜態的固定攝像頭。

(二)運動場

通常情況下,攝像機的運動形式可以分為兩種:a)攝像機的支架固定,但攝像機可以偏轉、俯仰以及縮放; b)將攝像機裝在某個移動的載體上。由於以上兩種情況下的背景及前景圖像都在做全域性運動,要準確檢測運動標的的首要任務是進行圖像的全域性運動估計與補償。

考慮到圖像幀上各點的全域性運動矢量雖不盡相同 (攝像機做平移運動除外 ),但它們均是在同一攝像機模型下的運動,因而應遵循相同的運動模型,可以用同一模型引數來表示。

全域性運動的估計問題就被歸結為全域性運動模型引數的估計問題,通常使用塊匹配法或光流估計法來進行運動引數的估計。

塊匹配

基於塊的運動估算和補償可算是最通用的演算法。可以將圖像分割成不同的圖像塊,假定同一圖像小塊上的運動矢量是相同的,通過像素域搜索得到最佳的運動矢量估算。塊匹配法主要有如下三個關鍵技術:

  • a)匹配法則,如最大相關、最小誤差等

  • b)搜索方法,如三步搜索法、交叉搜索法等。

  • c) 塊大小的確定,如分級、自適應等。


    光流法

    光流估計的方法都是基於以下假設:圖像灰度分佈的變化完全是標的或者場景的運動引起的,也就是說,標的與場景的灰度不隨時間變化。這使得光流方法抗噪聲能力較差,其應用範圍一般局限於標的與場景的灰度保持不變這個假設條件下。另外,大多數的光流計算方法相當複雜,如果沒有特別的硬體裝置,其處理速度相當慢,達不到實時處理的要求。

    二.標的跟蹤

    運動標的的跟蹤,即通過標的的有效表達,在圖像序列中尋找與標的模板最相似候選標的區位置的過程。簡單說,就是在序列圖像中為標的定位。運動標的的有效表達除了對運動標的建模外,標的跟蹤中常用到的標的特性表達主要包括視覺特征 (圖像邊緣、輪廓、形狀、紋理、區域)、統計特征 (直方圖、各種矩特征)、變換繫數特征 (傅里葉描繪子、自回歸模型)、代數特征 (圖像矩陣的奇異值分解)等。除了使用單一特征外,也可通過融合多個特征來提高跟蹤的可靠性.

    相似性度量演算法 

    對運動標的進行特性提取之後,需要採用一定的相似性度量演算法與幀圖像進行匹配,從而實現標的跟蹤。圖像處理與分析理論中,常見的相似性度量方法有歐氏距離、街區距離、棋盤距離、加權距離、巴特查理亞繫數、Hausdorff距離等,其中應用最多和最簡單的是歐氏距離。

    搜索演算法 

    標的跟蹤過程中,直接對場景中的所有內容進行匹配計算,尋找最佳匹配位置,需要處理大量的冗餘信息,這樣運算量比較大,而且沒有必要。採用一定的搜索演算法對未來時刻標的的位置狀態進行估計假設,縮小標的搜索範圍便具有了非常重要的意義。其中一類比較常用的方法是預測運動體下一幀可能出現的位置,在其相關區域內尋找最優點。常見的預測演算法有Kalman濾波、擴展的Kalman濾波及粒子濾波方法等。

    Kalman濾波器是一個對動態系統的狀態序列進行線性最小方差估計的演算法。它通過狀態方程和觀測方程來描述一個動態系統,基於系統以前的狀態序列對下一個狀態作最優估計,預測時具有無偏、穩定和最優的特點,且具有計算量小、可實時計算的特點,可以準確地預測標的的位置和速度,但其只適合於線性且呈高斯分佈的系統。相對於卡爾曼濾波演算法,粒子濾波器特別適用於非線性、非高斯系統。粒子濾波演算法是一種基於蒙特卡洛和貝葉斯估計理論的最優演算法,它以遞迴的方式對測量資料進行序貫處理,因而無須對以前的測量資料進行儲存和再處理,節省了大量的儲存空間。在跟蹤多形式的標的以及在非線性運動和測量模型中,粒子濾波器具有極好的魯棒性。

    另一類減小搜索範圍的演算法是優化搜索方向。均值漂移演算法 (Meanshift演算法 )、連續自適應均值漂移演算法 (Camshift演算法 )和置信區域演算法都是利用無參估計的方法優化標的模板和候選標的距離的迭代收斂過程,以達到縮小搜索範圍的目的。Meanshift演算法是利用梯度優化方法實現快速標的定位,能夠對非剛性標的實時跟蹤,適合於非線性運動標的的跟蹤,對標的的變形、旋轉等運動有較好的適用性。但是 Meanshift演算法在標的跟蹤過程中沒有利用標的在空間中的運動方向和運動速度信息,當周圍環境存在干擾時 (如光線、遮擋 ),容易丟失標的。Camshift演算法是在Meanshift演算法的基礎上,進行了一定的擴展,結合標的色彩信息形成的一種改進的均值漂移演算法。由於標的圖像的直方圖記錄的是顏色出現的概率,這種方法不受標的形狀變化的影響,可以有效地解決標的變形和部分遮擋的問題,且運算效率較高,但該演算法在開始前需要由人工指定跟蹤標的。

    標的跟蹤分類 

    依據運動標的的表達和相似性度量,運動標的跟蹤演算法可以分為四類:基於主動輪廓的跟蹤、基於特征的跟蹤、基於區域的跟蹤和基於模型的跟蹤。跟蹤演算法的精度和魯棒性很大程度上取決於對運動標的的表達和相似性度量的定義,跟蹤演算法的實時性取決於匹配搜索策略和濾波預測演算法。

    1、基於主動輪廓的跟蹤

    Kass等人提出的主動輪廓模型,即Snake模型,是在圖像域內定義的可變形曲線,通過對其能量函式的最小化,動態輪廓逐步調整自身形狀與標的輪廓相一致,該可變形曲線又稱為Snake曲線。Snake技術可以處理任意形狀物體的任意形變,首先將分割得到的物體邊界作為跟蹤的初始模板然後確定表徵物體真實邊界的標的函式,並通過降低標的函式值,使初始輪廓逐漸向物體的真實邊界移動。
    基於主動輪廓跟蹤的優點是不但考慮來自圖像的灰度信息,而且考慮整體輪廓的幾何信息,增強了跟蹤的可靠性。由於跟蹤過程實際上是解的尋優過程,帶來的計算量比較大,而且由於 Snake模型的盲目性,對於快速運動的物體或者形變較大的情況,跟蹤效果不夠理想。

    2、基於特征的跟蹤

    基於特征匹配的跟蹤方法不考慮運動標的的整體特征,只通過標的圖像的一些顯著特征來進行跟蹤。假定運動標的可以由惟一的特征集合表達,搜索到該相應的特征集合就認為跟蹤上了運動標的。除了用單一的特征來實現跟蹤外,還可以採用多個特征信息融合在一起作為跟蹤特征。基於特征的跟蹤主要包括特征提取和特征匹配兩個方面。

    (1)特征提取

    特征提取是指從景物的原始圖像中提取圖像的描繪特征,理想的圖像特征應具備的特點是:

    • a)特征應具有直觀意義,符合人們的視覺特性;

    • b)特征應具備較好的分類能力,能夠區分不同的圖像內容;

    • c)特征計算應該相對簡單,以便於快速識別;

    • d)特征應具備圖像平移、旋轉、尺度變化等不變性。


      標的跟蹤中常用的運動標的的特征主要包括顏色、紋理、邊緣、塊特征、光流特征、周長、面積、質心、角點等。提取對尺度伸縮、形變和亮度變化不敏感的有效特征至今仍是圖像處理研究領域中一個比較活躍的方面。

      (2)特征匹配

      特征提取的目的是進行幀間標的特征的匹配,並以最優匹配來跟蹤標的。常見的基於特征匹配的跟蹤演算法有基於二值化標的圖像匹配的跟蹤、基於邊緣特征匹配或角點特征匹配的跟蹤、基於標的灰度特征匹配的跟蹤、基於標的顏色特征匹配的跟蹤等。

      基於特征的跟蹤演算法的優點在於對運動標的的尺度、形變和亮度等變化不敏感,即使標的的某一部分被遮擋,只要還有一部分特征可以被看到,就可以完成跟蹤任務;另外,這種方法與 Kalman濾波器聯合使用,也具有很好的跟蹤效果。但是其對於圖像模糊、噪聲等比較敏感,圖像特征的提取效果也依賴於各種提取算子及其引數的設置,此外,連續幀間的特征對應關係也較難確定,尤其是當每一幀圖像的特征數目不一致、存在漏檢、特征增加或減少等情況。

      3、基於區域的跟蹤

      基於區域的跟蹤演算法基本思想是:

      • a)得到包含標的的模板,該模板可通過圖像分割獲得或預先人為確定,模板通常為略大於標的的矩形,也可為不規則形狀;

      • b)在序列圖像中,運用相關演算法跟蹤標的。


        這種演算法的優點在於當標的未被遮擋時,跟蹤精度非常高、跟蹤非常穩定。但其缺點首先是費時,當搜索區域較大時情況尤其嚴重;其次,演算法要求標的變形不大,且不能有太大遮擋,否則相關精度下降會造成標的的丟失。近年來,對基於區域的跟蹤方法關註較多的是如何處理模板變化時的情況,這種變化是由運動標的姿態變化引起的,如果能正確預測標的的姿態變化,則可實現穩定跟蹤。

        4、基於模型的跟蹤

        基於模型的跟蹤是通過一定的先驗知識對所跟蹤標的建立模型,然後通過匹配跟蹤標的進行模型的實時更新。對於剛體標的來說,其運動狀態變換主要是平移、旋轉等,可以利用該方法實現標的跟蹤。但是實際應用中跟蹤的不僅僅是剛體,還有一大部分是非剛體,標的確切的幾何模型不容易得到。

        這種方法不易受觀測視角的影響,具有較強的魯棒性,模型匹配跟蹤精度高,適合於機動標的的各種運動變化,抗干擾能力強,但由於計算分析複雜、運算速度慢,模型的更新較為複雜,實時性較差。準確建立運動模型是模型匹配能否成功的關鍵

        1.區域與區域匹配

        這種演算法的優點在於當標的未被遮擋時,跟蹤精度非常高,跟蹤非常穩定。但其缺點首先是費時,當搜索區域較大時情況尤其嚴重;其次,演算法要求標的變形不大,且不能有太大遮擋,否則相關精度下降會造成標的的丟失。

        2.特征點(關鍵點)跟蹤

        KLT:Shi和Tomasi 在1994年提出的KLT 跟蹤演算法是一種被廣泛應用的基於特征點跟蹤演算法。由於特征點分佈在整個標的上,因此即使有一部分被遮擋,仍然可以跟蹤到另外一部分特征點,這也是基於特征點跟蹤演算法的優點。

        基於特征點的跟蹤演算法中,比較困難的問題是當標的發生旋轉或者被遮擋時,如何準確地完成特征點的提取、儲存、刪除等工作

        3.基於主動輪廓的跟蹤演算法

        主動輪廓模型也稱為Snake 模型,這種方法能較精確地跟蹤上標的的輪廓。Snake 模型非常適合可變形標的的跟蹤,如對運動細胞的跟蹤。這種模型與卡爾曼濾波相結合能夠更好地進行跟蹤。Snake模型比較適合單標的的跟蹤,對於多標的跟蹤更多地是採用基於水平集(Level Set)方法的主動輪廓模型

        4.光流

        Lucas-Kanade稀疏光流calcOpticalFlowPyrLK(利用金字塔)

        Horn-Schunck稠密光流calcOpticalFlowHS

        稠密光流需要很大的計算量,OpenCV中對此方法做了簡化,即對前後連續幀的一個像素的鄰域進行匹配,這種方法叫塊匹配。

        稀疏光流需要在跟蹤之前指定一組點,如果這些點具有某些明顯特征,那麼跟蹤就會相對穩定和可靠。可見,其運算量比稠密光流要小很多。

        首先利用goodFeaturesToTrack函式得到圖像中的強邊界作為跟蹤的特征點,接下來要呼叫calcOpticalFlowPyrLK函式,輸入兩幅連續的圖像,併在第一幅圖像里選擇一組特征點,輸出為這組點在下一幅圖像中的位置。再把得到的跟蹤結果過濾一下,去掉不好的特征點。再把特征點的跟蹤路徑標示出來。

        (實際效果一般)

        5.mean-shift和 camshift

        Mean-shift優缺點

        meanShift演算法用於視頻標的跟蹤時,採用標的的顏色直方圖作為搜索特征,通過不斷迭代meanShift向量使得演算法收斂於標的的真實位置,從而達到跟蹤的目的。

        傳統的meanShift演算法在跟蹤中有幾個優勢:

        • (1)演算法計算量不大,在標的區域已知的情況下完全可以做到實時跟蹤;

        • (2)採用核函式直方圖模型,對邊緣遮擋、標的旋轉、變形和背景運動不敏感。

        同時,meanShift演算法也存在著以下一些缺點:

        • (1)缺乏必要的模板更新;

        • (2)跟蹤過程中由於視窗寬度大小保持不變,當標的尺度有所變化時,跟蹤就會失敗;

        • (3)當標的速度較快時,跟蹤效果不好;

        • (4)直方圖特征在標的顏色特征描述方面略顯匱乏,缺少空間信息;


          由於其計算速度快,對標的變形和遮擋有一定的魯棒性,所以,在標的跟蹤領域,meanShift演算法目前依然受到大家的重視。但考慮到其缺點,在工程實際中也可以對其作出一些改進和調整;例如:

          • (1)引入一定的標的位置變化的預測機制,從而更進一步減少meanShift跟蹤的搜索時間,降低計算量;

          • (2)可以採用一定的方式來增加用於標的匹配的“特征”;

          • (3)將傳統meanShift演算法中的核函式固定帶寬改為動態變化的帶寬;

          • (4)採用一定的方式對整體模板進行學習和更新;


            CamShift演算法

            CamShift演算法的全稱是”ContinuouslyAdaptive Mean-SHIFT”,即:連續自適應的MeanShift演算法。其基本思想是對視頻序列的所有圖像幀都作MeanShift運算,並將上一幀的結果(即搜索視窗的中心位置和視窗大小)作為下一幀MeanShift演算法的搜索視窗的初始值,如此迭代下去。簡單點說,meanShift是針對單張圖片尋找最優迭代結果,而camShift則是針對視頻序列來處理,並對該序列中的每一幀圖片都呼叫meanShift來尋找最優迭代結果。正是由於camShift針對一個視頻序列進行處理,從而保證其可以不斷調整視窗的大小,如此一來,當標的的大小發生變化的時候,該演算法就可以自適應地調整標的區域繼續跟蹤。

            在OpenCV自帶的camShift的例子當中,是通過計算標的在HSV空間下的H分量直方圖,通過直方圖反向投影得到標的像素的概率分佈,然後通過呼叫OpenCV的CAMSHIFT演算法,自動跟蹤並調整標的視窗的中心位置與大小。該演算法對於簡單背景下的單標的跟蹤效果較好,但如果被跟蹤標的與背景顏色或周圍其它標的顏色比較接近,則跟蹤效果較差。另外,由於採用顏色特征,所以它對被跟蹤標的的形狀變化有一定的抵抗能力。

            OpenCV自帶例子中的camShift演算法,可以分為三個部分:

            A、計算色彩投影圖(反向投影):

            • (1)為了減少光照變化對標的跟蹤的影響,首先將圖像從RGB顏色空間轉換到HSV顏色空間;

            • (2)對H分量進行直方圖統計,直方圖代表了不同H分量取值出現的概率,或者說可以據此查找出H分量的大小為x時的概率或像素個數,即,得到顏色概率查找表;

            • (3)將圖像中每個像素的值用其顏色出現的概率進行替換,由此得到顏色概率分佈圖;


              以上三個步驟稱之為反向投影,需要提醒的是,顏色概率分佈圖是一個灰度圖像;

              B、meanShift尋優

              前面提到過meanShift演算法(http://blog.csdn.net/carson2005/article/details/7337432)是一種非引數概率密度估計方法,它通過不斷迭代計算得到最優搜索視窗的位置和大小。

              C、camShift跟蹤演算法

              前面提到,camShift其實就是在視頻序列的每一幀當中都運用meanShift,並將上一幀的meanShift結果作為下一幀的初始值,如此不斷迴圈迭代,就可以實現標的的跟蹤了。


              【關於投稿】


              如果大家有原創好文投稿,請直接給公號發送留言。


              ① 留言格式:
              【投稿】+《 文章標題》+ 文章鏈接

              ② 示例:
              【投稿】
              《不要自稱是程式員,我十多年的 IT 職場總結》:

              http://blog.jobbole.com/94148/


              ③ 最後請附上您的個人簡介哈~


              覺得本文有幫助?請分享給更多人

              關註「演算法愛好者」,修煉編程內功

赞(0)

分享創造快樂