计算机应用   2016, Vol. 36 Issue (9): 2566-2569  DOI: 10.11772/j.issn.1001-9081.2016.09.2566 0

### 引用本文

GOU Chengfu, CHEN Bin, ZHAO Xuezhuan, CHEN Gang. Object tracking algorithm based on random sampling consensus estimation[J]. Journal of Computer Applications, 2016, 36(9): 2566-2569. DOI: 10.11772/j.issn.1001-9081.2016.09.2566.

### 文章历史

1. 中国科学院 成都计算机应用研究所, 成都 610041; ;
2. 中国科学院大学, 北京 100049

Object tracking algorithm based on random sampling consensus estimation
GOU Chengfu1,2, CHEN Bin1,2, ZHAO Xuezhuan1,2, CHEN Gang1,2
1. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu Sichuan 610041, China; ;
2. University of Chinese Academy Sciences, Beijing 100049, China
Background: This work is partially supported by the Science and Technology Achievement Transformation Foundation of Sichuan Province (2014CC0043)
GOU Chengfu, born in 1989, M.S. candidate. His research interests include image processing, computer vision
CHEN Bin, born in 1970, Ph. D., professor, His research interests include image analysis, machine vision
ZHAO Xuezhuan, born in 1986, Ph.D. candidate. His research interests include image analysis, machine vision
CHEN Gang, born in 1984, Ph.D. candidate. His research interests include image analysis, machine learning
Abstract: In order to solve tracking failure problem caused by target occlusion, appearance variation and long time tracking in practical monitoring, an object tracking algorithm based on RANdom SAmpling Consensus (RANSAC) estimation was proposed. Firstly, the local invariant feature set in the searching area was extracted. Then the object features were separated from the feature set by using the transfer property of feature matching and non-parametric learning algorithm. At last, the RANSAC estimation of object features was used to track the object location. The algorithm was tested on video data sets with different scenarios and analyzed by using three analysis indicators including accuracy, recall and comprehensive evaluation (F1-Measure). The experimental results show that the proposed method improves target tracking accuracy and overcomes track-drift caused by long time tracking.
Key words: local feature invariance    transitive matching property    non-parametric learning    RANdom SAmpling Consistency (RANSAC) estimation    object tracking
0 引言

1 随机一致性采样估计目标跟踪算法

 图 1 算法流程
1.1 算法概述

S(x, y, r)表示以(x, y)为中心，r为半径的目标搜索区域，然后采用两个不同的无参最近邻分类器分别判别跟踪目标和背景。目标模板Tt表示t时刻目标的形状和外观：

 ${T_t} = \left\{ {\left( {{\boldsymbol{p}_i},{\boldsymbol{d}_i}} \right)} \right\}_{i = 1}^{{N_t}}$ (1)

 ${C_t} = \left\{ {{\boldsymbol{d}_i}} \right\}_{i = 1}^{{N_c}}$ (2)

 $\boldsymbol{M}\left( {\boldsymbol{p},{\boldsymbol{X}_t}} \right) \Leftrightarrow {\boldsymbol{X}_t} = \left( {{x_t},{y_t},{s_t}} \right)$ (3)

pR2是关键点的坐标，M : R2｜ → R2是将图像中检测到目标的位置映射到目标模板的坐标系统，Xt=(xt, yt, st)是需要预测的目标状态变量。

 $P\left( {{{\boldsymbol{\hat X}}_t}\left| {{{\boldsymbol{\hat X}}_{t - 1}}} \right.} \right) = \left\{ \begin{array}{l} \begin{array}{*{20}{c}} {1,}&{{{\left\| {{{\boldsymbol{\hat X}}_t} - {{\boldsymbol{\hat X}}_{t - 1}}} \right\|}_\infty }M < r} \end{array}\\ \begin{array}{*{20}{c}} {0,}&{其他} \end{array} \end{array} \right.$ (4)

 ${S_t} = \left\{ {\left( {{p_i},{d_i}} \right)} \right\}_{i = 1}^{{N_s}}$ (5)

 ${C_t} = \bigcup\limits_{\tau = t - l}^t {\left\{ {\left( {\boldsymbol{p,d}} \right)\left| {p \in {A_\tau }} \right.} \right\}}$ (6)

1.2 目标特征选择

 $\left( {{T_t} \sim {S_t}} \right) \cap \left( {{C_t} \sim {S_t}} \right) \Rightarrow {T_t} \sim {C_t}$ (7)

 ${F_t} = T_t^*/C_t^*$ (8)

 图 2 搜索区域SIFT特征点和分离出的目标特征点
1.3 目标状态估计

w=目标特征的数目/特征集中特征的数目

 $1 - P = {\left( {1 - {w^n}} \right)^k}$ (9)

 $k = \frac{{\log \left( {1 - P} \right)}}{{\log \left( {1 - {w^n}} \right)}}$ (10)

 $SD\left( k \right) = \sqrt {1 - {w^n}} /{w^n}$ (11)

 $\left( {{x_t},{y_t}} \right) = \boldsymbol{M}\left( {{x_o},{y_o}} \right)$ (12)

 $P\left( {y = 1\left| {{S_t}} \right.} \right) = \left\{ \begin{array}{l} \begin{array}{*{20}{c}} {1,}&{{{\left\| {{{\hat s}_t} - {{\hat s}_{t - 1}}} \right\|}_\infty } < {k_s}} \end{array}\\ \begin{array}{*{20}{c}} {0,}&{其他} \end{array} \end{array} \right.$ (13)

ks是预定义的常量，控制尺度变化的最大速度，这可以避免在相似变换过程中由坐标和非中心对称建模引起的误报。因为跟踪是在尺度空间上执行的，从检测的目标上提取的特征要好于目标模板上的特征，因此，使分类器学习正确目标的外观和形状更容易。

1.4 遮挡检测

 ${O_t} = \left\{ {\left( {\boldsymbol{p,d}} \right) \in \left| {p \in OBB\left( {{{\boldsymbol{\hat X}}_t}} \right)} \right.} \right\}$ (14)

 图 3 遮挡跟踪效果
1.5 目标和背景模板更新

 $\boldsymbol{p'} = \boldsymbol{M}\left( {\boldsymbol{p};{{\boldsymbol{\hat X}}_t}} \right)$ (15)

 ${{\varepsilon '}_t} = \left\{ {\left( {\boldsymbol{p',d}} \right)\left| {\left( {\boldsymbol{p,d}} \right) \in {\varepsilon _t},\boldsymbol{p'} = M\left( {\boldsymbol{p};{{\boldsymbol{\hat X}}_t}} \right)} \right.} \right\}$ (16)
 ${T_t} = {\varepsilon _t} \cup {T_{t - 1}}$ (17)

 ${D_t} = {D_{t - 1}} \cup {O_t}$ (18)

 ${C_t} = \bigcup\limits_{\tau - 1}^t {\left( {{S_\tau }/{\varepsilon _\tau }} \right) \cup {D_t}}$ (19)
2 实验结果分析 2.1 实验环境设置

 图 4 部分实验视频序列
2.2 实验评价指标

3个评价指标分别是：准确率、召回率和综合评价指标(F1-Measure)：

 $F1 = \left( {2 \times P \times R} \right)/\left( {P + R} \right)$ (20)

F1综合评价指标是准确率和召回率的调和平均数。

2.3 实验结果分析

 图 5 Pedestrian跟踪效果
 图 6 Jumping跟踪效果
 图 7 Motocross跟踪效果
3 结语

 [1] 董慧芬, 董保磊, 丁小芬, 等. 基于相关区域分层的改进Meanshift目标跟踪算法[J]. 计算机应用, 2014, 34 (S2) : 286-290. ( DONG H F, DONG B L, DING X F, et al. Improved Meanshift tracking algorithm based on relevant regional stratification[J]. Journal of Computer Applications, 2014, 34 (S2) : 286-290. ) (0) [2] 习文星, 汤心溢. 基于随机森林和支持向量机的快速行人检测算法[J]. 计算机应用, 2014, 34 (S2) : 283-285. ( XI W X, TANG X Y. Pedestrian detection based on random forest and support vector machine[J]. Journal of Computer Applications, 2014, 34 (S2) : 283-285. ) (0) [3] 付忠良, 赵向辉, 苗青, 等. 基于属性组合的集成学习算法[J]. 计算机应用, 2010, 30 (2) : 465-468. ( FU Z L, ZHAO X H, MIAO Q, et al. Ensemble learning algorithm on attribute combination[J]. Journal of Computer Applications, 2010, 30 (2) : 465-468. ) (0) [4] BONIN-FONT F, ORTIZ A, OLIVER G. Visual navigation for mobile robots: a survey[J]. Journal of Intelligent and Robotic Systems, 2008, 53 (3) : 263-296. doi: 10.1007/s10846-008-9235-4 (0) [5] HU W, XIE D, FU Z, et al. Semantic-based surveillance video retrieval[J]. IEEE Transactions on Image Processing, 2007, 16 (4) : 1168-1181. doi: 10.1109/TIP.2006.891352 (0) [6] REMONDINO F. 3-D reconstruction of static human body shape from image sequence[J]. Computer Vision and Image Understanding, 2004, 93 (1) : 65-85. doi: 10.1016/j.cviu.2003.08.006 (0) [7] WRIGHT J, YANG A Y, GANESH A, et al. Robust face recognition via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31 (2) : 210-227. doi: 10.1109/TPAMI.2008.79 (0) [8] WANG S, LU H, YANG F, et al. Superpixel tracking [C]// Proceedings of the 2011 IEEE International Conference on Computer Vision. Piscataway, NJ: IEEE, 2011:1323-1330. (0) [9] DINH T B, VO N, MEDIONI G. Context tracker: exploring supporters and distracters in unconstrained environments [C]// Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2011:1177-1184. (0) [10] BABENKO B, YANG M H, BELONGIE S. Robust object tracking with online multiple instance learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33 (8) : 1619-1632. doi: 10.1109/TPAMI.2010.226 (0) [11] SANTNER J, LEISTNER C, SAFFARI A, et al. PROST: parallel robust online simple tracking [C]// Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2010:723-730. (0) [12] YU Q, DINH T B, MEDIONI G. Online tracking and reacquisition using co-trained generative and discriminative trackers [C]// Proceedings of the 10th European Conference on Computer Vision. Berlin: Springer, 2008: 678-691. (0) [13] AVIDAN S. Ensemble tracking[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29 (2) : 261-271. doi: 10.1109/TPAMI.2007.35 (0) [14] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60 (2) : 91-110. doi: 10.1023/B:VISI.0000029664.99615.94 (0) [15] GRABNER H, BISCHOF H. On-line boosting and vision [C]// Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society, 2006: 260-267. (0) [16] GRABNER H, LEISTNER C, BISCHOF H. Semi-supervised on-line boosting for robust tracking [C]// ECCV '08: Proceedings of the 10th European Conference on Computer Vision. Berlin: Springer, 2008: 234-247. (0) [17] KALAL Z, MATAS J, MIKOLAJCZYK K. P-N learning: boot-strapping binary classifiers by structural constraints [C]// Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2010: 49-56. (0) [18] PERNICI F, DEL BIMBO A. Object tracking by oversampling local features[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36 (12) : 2538-2551. doi: 10.1109/TPAMI.2013.250 (0)