一种基于改进型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-)，男，硕士研究生，主要研究方向：人脸、车牌识别。