一種基于改進型PN學習的在線長時目標跟蹤算法*

楊豐瑞，杜 奎，何 強

(1.重慶重郵信科集團股份有限公司，重慶 400065；2.重慶郵電大學 通信新技術應用研究中心，重慶 400065)

?

一種基于改進型PN學習的在線長時目標跟蹤算法*

楊豐瑞1,2，杜 奎2，何 強2

(1.重慶重郵信科集團股份有限公司，重慶 400065；2.重慶郵電大學 通信新技術應用研究中心，重慶 400065)

文中主要討論針對未知目標的長時跟蹤問題。在一幀圖像中，目標是由其位置和外觀表征的；在連續的視頻幀中，需要確定出每一幀中目標的位置和外觀特征或者在某一幀中標識出目標是不可見的。因此對PN半監督機器學習算法進行改進，并在此基礎上整合模板匹配技術、背景抽離技術和主成分分析技術，提出一種基于檢測的在線長時目標跟蹤算法。針對該跟蹤算法詳細闡述了其跟蹤架構和算法執行流程，并精心篩選出5個測試視頻流。實驗結果表明，該跟蹤算法具有較強的適應能力和跟蹤能力。

長時目標跟蹤；改進型PN學習；背景抽離；模板匹配；主成分分析

圖1 目標跟蹤所面臨的挑戰

0 引言

人腦的視覺皮質層通過分析視網膜成像從而定位并識別目標[1]。類似地，目標跟蹤通過評估連續視頻幀中目標的狀態，從而獲取目標的位置、輪廓以及軌跡等信息。

目前，目標跟蹤已經廣泛應用于自動視頻監控、軍事打擊、人機交互、智能交通、行為分析、虛擬現實等領域[1]。隨著目標跟蹤在應用廣度和深度上的不斷拓展，其面臨的挑戰也與日俱增，比如：外觀變化、快速移動、相似外觀、目標遮擋、光照變化、尺度變化、運動模糊和3D投影等。圖1列出了三種常見的跟蹤痛點：圖1(a)中目標與其左邊人物極其相似；圖1(b)中高速飛行的洲際導彈；圖1(c)中被遮擋的人臉目標。

為了應對這些挑戰，單單依靠傳統跟蹤算法或者檢測算法是遠遠不夠的。當前，由跟蹤、學習和檢測整合而成的在線目標跟蹤算法因其良好的適應性和魯棒性已經成為研究的主流。鑒于這種趨勢，本文對PN半監督學習[2]進行改進，并在此基礎上整合模板匹配技術、背景抽離技術和主成分分析技術提出一種基于檢測的在線長時目標跟蹤算法。

圖4 模板匹配原理示意圖

1 相關技術

1.1 PN-Learning

圖5 背景抽離示意圖

2012年，英國薩里大學捷克籍博士研究生Zdenek Kalal提出了TLD(Tracking-Learning-Detection)[3]目標跟蹤算法，它是一種基于檢測的長時在線目標跟蹤算法，具有良好的跟蹤能力和適應能力。TLD算法架構圖如圖2所示。TLD算法由4個模塊構成：跟蹤模塊、學習模塊、檢測模塊和整合模塊。其中PN-Learning是學習模塊的核心，它是一種半監督的機器學習算法，PN學習邏輯圖見圖3。它針對檢測模塊對樣本分類時產生的誤差提供了P專家和N專家。P專家的作用是尋找數據在時間上的結構性，利用追蹤器的結果預測物體在t+1幀的位置。如果這個位置(包圍框)被檢測器分類為負，P專家就把這個位置改為正，P專家增加了訓練集中的正標記樣本的數量，增強了分類器泛化能力(Generality)。N專家的作用是尋找數據在空間上的結構性，它把檢測器產生的和P專家產生的所有正樣本進行比較，選擇出一個最可信的位置，保證物體最多只出現在一個位置上，把這個位置作為TLD算法的追蹤結果。同時這個位置也用來重新初始化追蹤器，N專家增加了訓練集中負標記樣本的數量，增強了分類器的檢錯能力(Discriminability)。

圖2 TLD算法架構圖

圖3 學習模塊邏輯圖

1.2 模板匹配

模板匹配是一種最原始、最基本的模式識別方法，模板匹配技術可以用于檢測和跟蹤目標[4]。另外，模板匹配技術對目標的外觀變化具有良好的適應能力。圖4是模板匹配原理示意圖。

1.3 背景抽離

背景抽離是一種常用的分割運動區域的技術手段[5]，它參照背景圖像(在初始化時段通過平均圖像生成)，然后以像素為單位抽離當前圖像來檢測運動區域, 其中差值高于閾值的像素被分類為前景像素, 這樣就可以形成一個由前景像素組成的前景像素Map，接下來利用一些形態學中的侵蝕(erosion)、擴張(dilation)和關閉(closing)來減少噪聲的影響并增強檢測到的目標位置，最后，不斷更新參考背景圖像就可以適應動態場景變化了。圖5是背景抽離示意圖。

靜態場景中的正態分布模型也是絕大多數背景抽離技術的基礎模型。

1.4 PCA

PCA(Principal Component Analysis)，即主成分分析，它是一種最小均方意義上的最優變換，目的是去除輸入隨機向量之間的相關性，突出原始數據中的隱含特性。對于原始數據，可以通過一些變換來提取數據間的內在特征，這個過程可以為：

(1)

主成分分析經常被用于人臉識別和圖像壓縮、目標跟蹤等領域[8]。

2 基于改進型PN學習的在線長時目標跟蹤算法

2.1 算法架構和執行流程

基于改進型的PN學習的在線長時目標跟蹤算法是針對視頻流中任意未知目標進行長時跟蹤而提出的。本算法不僅整合了當前視覺跟蹤領域經典的技術，如：模板匹配技術、背景抽離技術和主成分分析技術，還提出了以減少搜索區域的ROI和改進的PN學習。算法架構如圖6所示。

圖6 本文所提算法邏輯架構圖

算法詳細執行流程如下：

(1)輸入視頻流(支持開啟攝像頭獲取實時視頻流)；

(2)獲取第一幀圖像，即初始化幀；

(3)用鼠標框選跟蹤目標，產生一個目標限位框(包圍框)，此即手動初始化；

(4)在目標限位框基礎上，長與寬各增加20 pixel生成ROI圖像，如果ROI圖像生成失敗則使用背景抽離技術；

(5)創建一個大小為50的圖像數組，用來存儲限位框所包含的目標圖像；

(6)將步驟(3)獲取的由一個矩形限位框標識的目標圖像保存在數組中，索引值(index)為0；

(7)對于圖像數組中索引值(index)為0的由一個矩形限位框標識的目標圖像，使用模板匹配算法將其與ROI進行匹配，如果匹配則計算出目標位置，同時計算匹配率，如果匹配率低于L，那么數組將駁回保存該幀輸入圖像(拒絕圖像)的請求；

(8)若在當前幀中的矩形限位框內匹配到了目標，那么接下來運用主成分分析(PCA)來檢測目標，同時再次計算匹配率，如果匹配率低于M而大于L，那么將當前矩形限位框中的目標圖像保存在數組index=0的位置，數組內其余圖像元素依次向后移動一位；

(9)若在當前幀中的矩形限位框內匹配不到目標，則加入改進型PN學習以改善檢測精度；

(10)返回到步驟(6)。

2.2 改進型PN學習

相比原始PN學習，本文所提改進型PN學習主要體現在以下兩點：

(1)正負樣本的生成策略。對于470×310 大小的圖像，原始PN學習大概產生3 萬個左右的正負樣本，實驗分析發現其中絕大多數樣本是冗余的，因此造成了極大的計算資源浪費。為此直接將當前幀中包含目標的矩形限位框置為正樣本，類似地，將當前幀中除矩形限位框之外的背景區域等分為若干個負樣本。經實驗驗證此舉可以在不犧牲跟蹤精度的前提下提高算法的實時性。

3 實驗結果

實驗環境：Windows 10 64 bit家庭版平臺，Intel Core(TM) i5-6300HQ CPU，4 GB RAM，OpenCV 2.4.13視覺庫，Microsoft Visual Studio 2016。

本文使用以下參數進行性能評估：

(2)M(百分制)，M即More，它是一個關于匹配率的上限閾值，本文定義匹配率等于95%的匹配值為M，如果匹配率大于M則認為是一次成功的跟蹤。

(3)L(百分制)，L即Less，它是一個關于匹配率的下限閾值，本文定義匹配率等于85%的匹配值為L，如果匹配率小于L那么就認為是一次失敗的跟蹤。

(4)Matching Value(百分制)，即匹配率，表征兩個圖像塊的相似程度，其公式如下：

(2)

式中，μ和σ是圖像塊P的均值與方差。

為了驗證本文所提算法的有效性，精挑細選了5個“刁鉆”的測試視頻流，保證每個測試用例至少包含光照變化、相似外觀、尺度變化、目標遮擋和外觀變化這5種目標跟蹤痛點中的3種情景，每個測試用例詳情見表1。

表1 測試用例

表2針對跟蹤成功幀數這一指標，將4種經典的跟蹤算法與本文所提目標跟蹤算法進行比較。Mean Shift和Camshift算法成功率最低，CT和TLD算法成功率相似，本文所提算法成功率最高。從Mean shift和Camshift算法跟蹤成功率來看，單單依靠跟蹤算法或者檢測算法是無法應對“刁鉆”的測試用例的。

表2 跟蹤成功幀數

表3通過ROI、P-Type、N-Type、Matching Value、P、R和F來評估本文算法跟蹤性能。P-Type和N-Type分別表示跟蹤結束后正負樣本數組內的樣本數量；第五列Matching Value均在0.95之上，這說明模板匹配和背景抽離技術所提取的目標的可靠性是很高的；最后一列F的值均大于0.70，證明本算法在面對極其復雜的跟蹤場景時依然具有一定的可靠性，其中視頻流②的F值大于0.90。

表3 本文所提算法跟蹤性能

4 結論

目前，基于檢測和半監督學習的目標跟蹤算法已經成為研究的主流[1]。本文所提目標跟蹤算法作為一種基于檢測和半監督學習的目標跟蹤算法，通過實驗驗證，其具有良好的適應性和魯棒性，在運動檢測、自動監控、視頻檢索、人機交互和交通監控的各領域有一定的應用前景，但是其依然有許多不足之處，比如：需要手動初始化、不支持多目標擴展、目標在持續旋轉或者持續尺度變化時限位框會發生飄移現象、背景抽離技術平均耗時100 ms而且會隨著ROI區域的增大而增大等，還需要進一步的改進。

[1] 梁娟, 項俊, 侯建華. 基于 Camshift 和 Kalman 濾波的自動跟蹤算法[J]. 微型機與應用, 2011, 30(24): 28-31.

[2] KALAL Z, MATAS J, MIKOLAJCZYK K. PN learning: bootstrapping binary classifiers by structural constraints[C].Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010: 49-56.

[3] KALAL Z, MIKOLAJCZYK K, MATAS J. Tracking-learning-detection[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2012, 34(7): 1409-1422.

[4] 田娟, 鄭郁正. 模板匹配技術在圖像識別中的應用[J]. 傳感器與微系統, 2008, 27(1): 112-114.

[5] ELGAMMAL A, HARWOOD D, DAVIS L. Non-parametric model for background subtraction[C].European Conference on Computer Vision. Springer Berlin Heidelberg, 2000: 751-767.

[6] COMANICIU D, MEER P. Mean shift: a robust approach toward feature space analysis[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2002, 24(5): 603-619.

An online and long-term object tracking algorithm based on modified PN-Learning

Yang Fengrui1,2, Du Kui2, He Qiang2

(1. Chongqing Information Technology (Group) Co., Ltd, Chongqing 400065, China;2. Application of New Technologies of Communication Research Center, Chongqing University of Post and Telecommunications, Chongqing 400065, China)

This paper mainly investigates long-term tracking of unknown objects in a video stream. The object is defined by its location and extent in a single frame. In every frame that follows, the task is to determine the object’s location and extent or indicate that the object is not present. So we improve the PN semi-supervised machine learning algorithm, on the basic of modified PN-learning algorithm, an online long-term object tracking algorithm based on detection is proposed. In this paper, we detailedly describe the tracking architecture and algorithm execution flow of the object tracking algorithm proposed in this paper. In addition, five concise video streams are selected elaborately. Experimental results show that the tracking algorithm has stronger adaptability and tracking ability.

long-term tracking; modified PN-Learning; background subtraction; template matching; PCA

2015年重慶市研究生科研創新項目(CYS15166)

TP391.41

A

10.19358/j.issn.1674- 7720.2017.11.012

楊豐瑞，杜奎，何強.一種基于改進型PN學習的在線長時目標跟蹤算法[J].微型機與應用，2017,36(11)：40-43，46.

2017-01-12)

楊豐瑞(1963-)，男，博士，教授，主要研究方向：通信新技術應用與電信增值業務。

杜奎(1990-)，男，碩士研究生，主要研究方向：視覺目標跟蹤和大型分布式系統。

何強(1991-)，男，碩士研究生，主要研究方向：人臉、車牌識別。