基于SVM 空對地目標跟蹤算法

郭星辰，張 葆，宋 策

(1.中國科學院 長春光學精密機械與物理研究所 中國科學院航空光學成像與測量重點實驗室，吉林 長春130033;2.中國科學院大學，北京100049)

目標跟蹤作為計算機視覺技術的分支，廣泛應用于視頻檢索、智能監控、人機交互、火控制導等領域。根據已知目標的先驗知識，對模板進行評估、分類、標識，獲取視頻序列中目標狀態(如位置、速度等)，實現目標跟蹤。雖然國內外學者對跟蹤技術進行多年研究，編寫出許多著名算法(如MIL［1］，Mean－shift［2］，TLD［3］等)，但是由于在空對地跟蹤過程中，目標尺度、旋轉、融合等問題引起跟蹤模板退化，導致跟蹤效果不理想，難以滿足實際工程的需要［4］。

SVM 是20 世紀90 年代Vapnik 和Cortes 提出的用于模式識別的方法［5］。它是建立在統計學習理論的VC 維理論和結構風險最小化原理基礎上的，通過對原問題二次規劃求取全局最優解，解決機器學習問題，可利用小樣本對目標學習，訓練分類器，屬半監督學習。隨著目標表示方法增多，采用多種表示方法可得到高精度跟蹤效果使得在跟蹤中數據維數增大，導致實時性下降，SVM 在處理高維數據中表現出獨特的優勢［6］。針對小樣本數據，SVM 分類器［7］對樣本的學習能力能夠解決跟蹤中目標丟失、融合等問題。基于上述分析，本文引入基于SVM 分類跟蹤算法，利用灰度直方圖和哈爾特征提取目標特征，采用線性、高斯等核函數對視頻評估，實現目標精準跟蹤。

1 支持向量機

n 維實數集X 表示輸入空間，m 維實數集Y 表示輸出空間，Z=X×Y 表示樣本空間，F 表示目標函數集合。機器學習的目的是在集合F 中找到一個函數f*(x，α*)逼近滿足樣本空間Z 中的位置概率分布F。則目標函數的實際風險式中，L(y，f(x，α))為一個給定模式x 的真實值和計算值f(x，α)之間的損失函數。

與用經驗風險Remp(f)逼近真實風險的經驗風險最小化原理不同，結構風險最小化(Structural Risk Minimization，SRM)原理引入置信風險ε(l，δ，h)

根據文獻［5］，ε(l，δ，h)可表示為

當VC 維h 增加時，系統對于目標細節掌握的先驗知識越多，其識別能力越強，能夠在從背景中精確的鎖定目標，因此經驗風險Remp(f)隨著h 的增加而減小;然而，從式(3)可見，算法的置信風險ε 與VC 維h 成正比，這是因為h 的增加會導致系統對背景噪聲過于敏感，背景中一個細小干擾都會對目標識別結果造成很大的影響。SRM 原理將真實風險在經驗風險與置信風險之間(分類模型復雜度與學習能力)尋求了一個折中，三者關系如圖1 所示，在滿足跟蹤精度的前提下，提高跟蹤過程實時性。

圖1 分類模型與學習能力關系

支持向量分類器［8］(Support Vector Classification，SVC)基本設計思想為，利用核函數對現實問題二次規劃為凸優化問題，將尺度空間中線性可分與線性不可分數據均映射為特征空間中線性可分數據，利用最大間隔分類器(即支持向量分類器)對數據學習、分類。

經二次優化后，求解決策函數的問題轉化為求解優化問題

式中:ω 為權重向量，b 為偏置，二者共同決定分類超平面;l為樣本總數。位于ω，b 所確定的分類超平面上或在超平面附近的輸入向量x*被稱為支持向量［9］，即為圖像中區分于背景的目標特征。

2 核函數選擇

選擇支持向量機的優勢在于它能夠將尺度空間中線性不可分數據通過非線性映射函數映射為高維特征空間中線性可分數據，繼而在特征空間中選取分類超平面。為了得到非線性映射，支持向量機引入核函數概念，根據Mercer 定理避免了在高維特征空間中進行內積運算問題，進一步提升運算速度。

Mercer 定理:如果函數K 是Rn×Rn→R 上的映射(即兩個n 維向量映射到實數域)。那么K 是一個有效函數(也成Mercer 核函數)，當且僅當對于訓練樣本{x1，x2，…，xl}，其相應的核函數是對稱半正定的［10］。

本次實驗采用的核函數下面分別介紹。

2.1 線性核函數(Linear Kernel)

線性核函數是各類核函數中形式最簡單的，僅僅為兩個向量的內積。采用線性核函數算法等價于不采用核函數，故該核函數針對于尺度空間中線性可分的數據。

2.2 高斯核函數(Gaussian Kernel)

高斯核函數也稱徑向基核函數(Randial Basis Function Kernel，RBF)，二者的主要差別是高斯函數每一個基函數中心對應一個支持變量，輸出權值由算法自主決定。函數中變量十分重要，選取過大會導致函數趨向于線性核函數，高維特征空間將失去其非線性特性;選取過小會導致函數對決策邊緣噪聲敏感，影響目標跟蹤準確度。

選取不同核函數將構成不同的支持向量機，并且對不同實驗數據效果亦不相同［11］。線性核函數和高斯核函數應用較為廣泛，針對線性可分數據，各類核函數分類效果大同小異，然而線性核函數計算量大大小于其他核函數，可減少算法運行時間，有利于提高算法實時性。高斯核函數適用范圍廣，不論低維、高維、大小樣本等情況，高斯核函數均適用。

3 目標表示

3.1 灰度直方圖［12］

直方圖是多種空間域處理技術的基礎。直方圖能有效用于圖像增強，其固有信息在其他圖像處理應用(如圖像壓縮與分割)中也非常有用。直方圖在軟件中易于計算，也適用于商業硬件設備，因此它是實時圖像處理的一個流行工具。

本實驗將灰度直方圖作為目標表示，主要是考慮到其計算簡易性，減小算法復雜度。灰度直方圖包含了目標的亮度信息，為了進一步突出其易于計算的特點，本算法并未直接對波門中目標像素進行直方圖提取，而是先對波門信息進行灰度降級，如此大大縮減了像素灰度數量與存儲空間，進而將目標進行一定數量的等分，將圖像分塊后再進行直方圖處理，在減少像素數量的同時，不會丟失目標特有的亮度信息。

3.2 哈爾特征

哈爾(Haar－like)特征是計算機視覺領域常用的一種特征算子。最初由Papageorigiou 等人用于人臉描述［13－14］，分為4 類共15 個算子，其中對角線特征1 個，中心特征(點特征)2個，邊緣特征4 個，線特征8 個。特征算子表示為黑白相間的矩形，其特征值定義為黑色區域的像素與白色區域像素的差值，在相減過程中，保證二者的像素數相同。矩形特征的位置、大小根據實驗需要進行調整。

矩形特征的靈活性(矩形大小、位置、像素權值)可為分類器提供大量目標特征，積分圖為哈爾特征提供快速算法，可在較短時間內完成對大量矩形特征計算，可滿足目標跟蹤準確性和實時性的要求［15］。故采用哈爾特征對目標進行表示，在提取目標固有特征同時，能夠在跟蹤過程中目標發生變化后提取并保存新特征，從而保證在跟蹤波門中長時間鎖定目標。本次實驗選取水平方向、垂直方向的邊緣特征和線特征，1 個對角線特征，1 個中心特征共6 個特征對目標進行表示，如圖2 所示。

圖2 目標表示的哈爾特征

4 實驗結果

本文主要針對機載環境對地面目標跟蹤的測試視頻，對基于SVC 跟蹤算法進行試驗驗證。測試視頻為卡內基梅隆大學數據庫中用于測試空對地目標跟蹤的視頻egtest02，幀頻25 f/s，幀圖大小為640 pixel×480 pixel。實驗設備為Intel CoreTM雙核CPU，主頻2.53 GHz，內存4.00 Gbyte。實驗軟件為Visual Studio 2010 和opencv2.4.8。跟蹤算法主要采用哈爾特征對目標表示，核函數選取σ=0.2 的高斯核函數。

SVC 中的樣本從視頻第一幀中選取，由于樣本數量較小，為了保證跟蹤精度，樣本中目標充滿整個波門，目標樣本在隨后跟蹤過程中不斷擴充。支持向量上限為75，減少計算量提高算法實時性。目標搜索區域為半徑30 pixel 圓形，算法對以上一幀中最佳匹配點為圓心的圓內區域進行步長為2 的遍歷，利用SVC 對樣本集分類，求得本幀中的支持向量，鎖定目標位置并將新的支持向量添加進學習器中，如圖3 所示。

圖3 基于SVC 空對地算法示意圖

其中，目標特征評價函數為

式中:x 為搜索區域模板;x*為目標模板;yout表示搜索區域與目標模板相似度，其值越大表示搜索區域是跟蹤目標的可能性越大。

跟蹤目標為機場背景下勻速行駛的汽車，如圖4 所示。綠色邊框為跟蹤波門，波門中為目標車輛，其余車輛為干擾車輛。在整個視頻中，第260 ～548 幀相機焦距增大，目標車輛減速、轉彎，車輛尺度、輪廓發生大幅度變化;車輛轉彎后在第549 ～716 幀與三輛車進行會車，第三輛車與目標車輛車型相同;會車完成后車輛轉彎，在952 ～1 231 幀航拍相機在x 方向劇烈晃動，x 方向最大速度為15 pixel/s，最大加速度為5.17 pixel/s2。

圖4 機場背景下的目標車輛

跟蹤過程中，航拍相機在第260 幀焦距縮短，目標車輛明顯減速，跟蹤波門中目標比例減小，如圖5b 所示。目標車輛在第402 ～531 幀完成約100°轉彎，角速度為1.45 rad/s，第400 ～424 幀遇到強光干擾，如圖5c 所示。第530 幀完成轉彎，學習器保存目標車輛轉彎過長中17 個姿態，支持向量增加到48 個。整個過程中目標車輛鎖在跟蹤波門內，并未發生任何波門抖動、假跟蹤現象。

圖5 目標車輛尺度、旋轉跟蹤結果

車輛完成第一次轉彎進行會車實驗，六輛車共三種車型，每種車型顏色不同。為減少算法復雜度，實驗處理對象均被轉化為灰度圖像，削弱算法對車輛顏色的分辨能力。在通過前兩輛不同車型的車輛時，波門可鎖定目標，未出現假跟蹤現象，其中相似車輛像素占波門最大達到12.7%，如圖6d 所示，但在第677 ～681 幀波門鎖定同款相向行駛車輛，如圖6f 所示。在完成回車后，目標與相似車輛分離，分類器根據學習器中在之前跟蹤過程中對目標積攢的先驗知識，重新鎖定目標車輛。

圖6 會車融合跟蹤結果

整個會車過程中，目標車輛分別于三輛相向車輛融合，干擾車輛部分進入跟蹤波門，但是沒有影響整體跟蹤效果，會車階段跟蹤精確度達到98.4%。

目標完成第二次轉彎，即第990 幀之后，航拍相機在x 方向產生劇烈抖動，并且焦距調小，目標所占波門比例減小，其像素比例為變換前的1/3，如圖7 所示，最大速度達到15 piexl/s。整個過程中目標被波門牢牢鎖住，跟蹤精度達到100%。

5 結束語

經仿真實驗驗證，算法在跟蹤過程中對目標學習后，可對尺度3 倍變換、角速度1.45 rad/s、融合12.7%波門的目標實現高度準確性和穩定性跟蹤，并且排除最大速度為15 piexl/s相機抖動的不穩定因素，魯棒性較強，因此，基于SVC 跟蹤算法精度滿足實際工程應用。

圖7 航拍相機劇烈抖動跟蹤結果

算法復雜度與目標模板和支持向量數量成正比，實驗中視頻后期隨學習器模板數量增多實時性略有下降，為降低目標尺度發生較大變換時學習器增加目標模板的數量，算法后期將修改對視頻波門尺寸，增大目標所占波門比例，減少學習器模板數量，減小算法復雜度，提高實時性。

［1］BABENKO B，YANG M H，BELONGIE S.Visual tracking with online multiple instance learning［C］//Proc. CVPR 2009. Anchorage，Alaska:IEEE Press，2009:983－990.

［2］王夢斐，王沛，馬燕，等. 基于卡爾曼和圖像信息量的MeanShift改進跟蹤算法［J］.電視技術，2015，39(5):41－44.

［3］KALAL Z，MATAS J，MIKOLAJCZYK K. Pn learning:Bootstrapping binary classifiers by structural constraints［C］//Proc. CVPR 2010.San Francisco:IEEE Press，2010:49－56.

［4］宋策，張葆，尹傳歷，等. 基于粒子濾波的空－地目標跟蹤算法［J］.光電子·激光，2013，24(10):2017－2023.

［5］VAPNIK V. The nature of statistical learning theory［M］. New York:Springer，1995.

［6］李俊，陳善學，馮銀波. 無人工樣本的SVM 遙感圖像分類方法［J］.電視技術，2013，37(23):27－30.

［7］文學志，方巍，鄭鈺輝. 一種基于類Haar 特征和改進AdaBoost分類器的車輛識別算法［J］. 電子學報，2011，39(5):1121－1126.

［8］侯明，張新新，范麗亞.四類基于支持向量機的多類分類器的性能比較［J］. 聊城大學學報:自然科學版，2014，27(3):54－60.

［9］王文劍，門昌騫.支持向量機建模及應用［M］. 北京:科學出版社，2014.

［10］CRISTIANINI N，SHAWE－TAYLOR J. 支持向量機導論［M］.李國正，王猛，曾華軍，譯.北京:電子工業出版社，2004.

［11］宋暉，薛云，張良均. 基于SVM 分類問題的核函數選擇仿真研究［J］.計算機與現代化，2014(8):133－136.

［12］魯凱翔，田鵬輝，隋立春.利用二維灰度直方圖跟蹤紅外運動目標［J］. 測繪通報，2014(3):29－31.

［13］陳勇飛，劉新明. 基于膚色和類Harr 特征的人臉圖像的人眼檢測［J］. 計算機工程與應用，2009，44(33):174－176.

［14］李盛文，鮑蘇蘇. 基于PCA+AdaBoost 算法的人臉識別技術［J］. 計算機工程與應用，2010，46(4):170－173.

［15］HARE S，SAFFARI A，TORR P H S. Struck:structured output tracking with kernels［C］//Proc. ICCV 2011. Barcelona，Spain:IEEE Press，2011:263－270.