一種基于改進(jìn)型PN學(xué)習(xí)的在線長(zhǎng)時(shí)目標(biāo)跟蹤算法*

楊豐瑞，杜 奎，何 強(qiáng)

(1.重慶重郵信科集團(tuán)股份有限公司，重慶 400065；2.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065)

?

一種基于改進(jìn)型PN學(xué)習(xí)的在線長(zhǎng)時(shí)目標(biāo)跟蹤算法*

楊豐瑞1,2，杜 奎2，何 強(qiáng)2

(1.重慶重郵信科集團(tuán)股份有限公司，重慶 400065；2.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065)

文中主要討論針對(duì)未知目標(biāo)的長(zhǎng)時(shí)跟蹤問(wèn)題。在一幀圖像中，目標(biāo)是由其位置和外觀表征的；在連續(xù)的視頻幀中，需要確定出每一幀中目標(biāo)的位置和外觀特征或者在某一幀中標(biāo)識(shí)出目標(biāo)是不可見(jiàn)的。因此對(duì)PN半監(jiān)督機(jī)器學(xué)習(xí)算法進(jìn)行改進(jìn)，并在此基礎(chǔ)上整合模板匹配技術(shù)、背景抽離技術(shù)和主成分分析技術(shù)，提出一種基于檢測(cè)的在線長(zhǎng)時(shí)目標(biāo)跟蹤算法。針對(duì)該跟蹤算法詳細(xì)闡述了其跟蹤架構(gòu)和算法執(zhí)行流程，并精心篩選出5個(gè)測(cè)試視頻流。實(shí)驗(yàn)結(jié)果表明，該跟蹤算法具有較強(qiáng)的適應(yīng)能力和跟蹤能力。

長(zhǎng)時(shí)目標(biāo)跟蹤；改進(jìn)型PN學(xué)習(xí)；背景抽離；模板匹配；主成分分析

圖1 目標(biāo)跟蹤所面臨的挑戰(zhàn)

0 引言

人腦的視覺(jué)皮質(zhì)層通過(guò)分析視網(wǎng)膜成像從而定位并識(shí)別目標(biāo)[1]。類似地，目標(biāo)跟蹤通過(guò)評(píng)估連續(xù)視頻幀中目標(biāo)的狀態(tài)，從而獲取目標(biāo)的位置、輪廓以及軌跡等信息。

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

為了應(yīng)對(duì)這些挑戰(zhàn)，單單依靠傳統(tǒng)跟蹤算法或者檢測(cè)算法是遠(yuǎn)遠(yuǎn)不夠的。當(dāng)前，由跟蹤、學(xué)習(xí)和檢測(cè)整合而成的在線目標(biāo)跟蹤算法因其良好的適應(yīng)性和魯棒性已經(jīng)成為研究的主流。鑒于這種趨勢(shì)，本文對(duì)PN半監(jiān)督學(xué)習(xí)[2]進(jìn)行改進(jìn)，并在此基礎(chǔ)上整合模板匹配技術(shù)、背景抽離技術(shù)和主成分分析技術(shù)提出一種基于檢測(cè)的在線長(zhǎng)時(shí)目標(biāo)跟蹤算法。

圖4 模板匹配原理示意圖

1 相關(guān)技術(shù)

1.1 PN-Learning

圖5 背景抽離示意圖

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

圖2 TLD算法架構(gòu)圖

圖3 學(xué)習(xí)模塊邏輯圖

1.2 模板匹配

模板匹配是一種最原始、最基本的模式識(shí)別方法，模板匹配技術(shù)可以用于檢測(cè)和跟蹤目標(biāo)[4]。另外，模板匹配技術(shù)對(duì)目標(biāo)的外觀變化具有良好的適應(yīng)能力。圖4是模板匹配原理示意圖。

1.3 背景抽離

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

靜態(tài)場(chǎng)景中的正態(tài)分布模型也是絕大多數(shù)背景抽離技術(shù)的基礎(chǔ)模型。

1.4 PCA

PCA(Principal Component Analysis)，即主成分分析，它是一種最小均方意義上的最優(yōu)變換，目的是去除輸入隨機(jī)向量之間的相關(guān)性，突出原始數(shù)據(jù)中的隱含特性。對(duì)于原始數(shù)據(jù)，可以通過(guò)一些變換來(lái)提取數(shù)據(jù)間的內(nèi)在特征，這個(gè)過(guò)程可以為：

(1)

主成分分析經(jīng)常被用于人臉識(shí)別和圖像壓縮、目標(biāo)跟蹤等領(lǐng)域[8]。

2 基于改進(jìn)型PN學(xué)習(xí)的在線長(zhǎng)時(shí)目標(biāo)跟蹤算法

2.1 算法架構(gòu)和執(zhí)行流程

基于改進(jìn)型的PN學(xué)習(xí)的在線長(zhǎng)時(shí)目標(biāo)跟蹤算法是針對(duì)視頻流中任意未知目標(biāo)進(jìn)行長(zhǎng)時(shí)跟蹤而提出的。本算法不僅整合了當(dāng)前視覺(jué)跟蹤領(lǐng)域經(jīng)典的技術(shù)，如：模板匹配技術(shù)、背景抽離技術(shù)和主成分分析技術(shù)，還提出了以減少搜索區(qū)域的ROI和改進(jìn)的PN學(xué)習(xí)。算法架構(gòu)如圖6所示。

圖6 本文所提算法邏輯架構(gòu)圖

算法詳細(xì)執(zhí)行流程如下：

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

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

(3)用鼠標(biāo)框選跟蹤目標(biāo)，產(chǎn)生一個(gè)目標(biāo)限位框(包圍框)，此即手動(dòng)初始化；

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

(5)創(chuàng)建一個(gè)大小為50的圖像數(shù)組，用來(lái)存儲(chǔ)限位框所包含的目標(biāo)圖像；

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

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

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

(9)若在當(dāng)前幀中的矩形限位框內(nèi)匹配不到目標(biāo)，則加入改進(jìn)型PN學(xué)習(xí)以改善檢測(cè)精度；

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

2.2 改進(jìn)型PN學(xué)習(xí)

相比原始PN學(xué)習(xí)，本文所提改進(jìn)型PN學(xué)習(xí)主要體現(xiàn)在以下兩點(diǎn)：

(1)正負(fù)樣本的生成策略。對(duì)于470×310 大小的圖像，原始PN學(xué)習(xí)大概產(chǎn)生3 萬(wàn)個(gè)左右的正負(fù)樣本，實(shí)驗(yàn)分析發(fā)現(xiàn)其中絕大多數(shù)樣本是冗余的，因此造成了極大的計(jì)算資源浪費(fèi)。為此直接將當(dāng)前幀中包含目標(biāo)的矩形限位框置為正樣本，類似地，將當(dāng)前幀中除矩形限位框之外的背景區(qū)域等分為若干個(gè)負(fù)樣本。經(jīng)實(shí)驗(yàn)驗(yàn)證此舉可以在不犧牲跟蹤精度的前提下提高算法的實(shí)時(shí)性。

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)環(huán)境：Windows 10 64 bit家庭版平臺(tái)，Intel Core(TM) i5-6300HQ CPU，4 GB RAM，OpenCV 2.4.13視覺(jué)庫(kù)，Microsoft Visual Studio 2016。

本文使用以下參數(shù)進(jìn)行性能評(píng)估：

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

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

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

(2)

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

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

表1 測(cè)試用例

表2針對(duì)跟蹤成功幀數(shù)這一指標(biāo)，將4種經(jīng)典的跟蹤算法與本文所提目標(biāo)跟蹤算法進(jìn)行比較。Mean Shift和Camshift算法成功率最低，CT和TLD算法成功率相似，本文所提算法成功率最高。從Mean shift和Camshift算法跟蹤成功率來(lái)看，單單依靠跟蹤算法或者檢測(cè)算法是無(wú)法應(yīng)對(duì)“刁鉆”的測(cè)試用例的。

表2 跟蹤成功幀數(shù)

表3通過(guò)ROI、P-Type、N-Type、Matching Value、P、R和F來(lái)評(píng)估本文算法跟蹤性能。P-Type和N-Type分別表示跟蹤結(jié)束后正負(fù)樣本數(shù)組內(nèi)的樣本數(shù)量；第五列Matching Value均在0.95之上，這說(shuō)明模板匹配和背景抽離技術(shù)所提取的目標(biāo)的可靠性是很高的；最后一列F的值均大于0.70，證明本算法在面對(duì)極其復(fù)雜的跟蹤場(chǎng)景時(shí)依然具有一定的可靠性，其中視頻流②的F值大于0.90。

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

4 結(jié)論

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

[1] 梁娟, 項(xiàng)俊, 侯建華. 基于 Camshift 和 Kalman 濾波的自動(dòng)跟蹤算法[J]. 微型機(jī)與應(yīng)用, 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] 田娟, 鄭郁正. 模板匹配技術(shù)在圖像識(shí)別中的應(yīng)用[J]. 傳感器與微系統(tǒng), 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年重慶市研究生科研創(chuàng)新項(xiàng)目(CYS15166)

TP391.41

A

10.19358/j.issn.1674- 7720.2017.11.012

楊豐瑞，杜奎，何強(qiáng).一種基于改進(jìn)型PN學(xué)習(xí)的在線長(zhǎng)時(shí)目標(biāo)跟蹤算法[J].微型機(jī)與應(yīng)用，2017,36(11)：40-43，46.

2017-01-12)

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

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

何強(qiáng)(1991-)，男，碩士研究生，主要研究方向：人臉、車(chē)牌識(shí)別。