摘要
准确,鲁棒的跟踪性能是跟踪学者们所追求的目标,为此,本论文选择了对目标模型和噪声没有限制的蒙特卡洛滤波算法。通过查阅国内外文献及软件仿真,对蒙特卡洛滤波算法的原理进行了深入的分析和研究,针对传统的蒙特卡洛滤波算法存在的主要问题——计算复杂度大和样本退化问题,分别提出了改进措施。
好的模型是跟踪成败的关键,针对传统模型不能去除背景干扰的问题,论文提出了新的目标表观建模方案——基于轮廓的表观模型提取。首先通过边缘检测,直线段检测等一系列步骤提取出给定区域内目标的轮廓,用轮廓曲线内的信息表示目标,接下来用颜色信息和形状信息相结合的方式描述目标特征,使得特征描述符可以抵抗光照变化及旋转缩放等复杂情况。实验结果表明,在PC机上用VC++6.0实现时,对于300*300像素的区域以内的目标,这种建模方法提取模型时间<1ms,几乎可以忽略,匹配过程中,用新模板的匹配时间平均可以达到用原模板匹配时间的1/2。
针对蒙特卡洛算法的样本退化问题,论文提出了基于人眼机制的样本集建立方案和半采样半重采样的样本集传播策略。初始帧需要建立样本集合,按照与中心距离越近样本越密集,反之越稀疏的原则建立样本集合;样本传播过程中,将样本集合分成优劣两类,对优样本集合通过重采样传播,对劣样本集合用样本建立方法重新采样代替。实验结果表明,这种样本集建立传播策略解决了样本的退化问题。
针对Mean Shift算法不能很好解决非线性目标跟踪以及蒙特卡洛算法实时性差的问题,提出了一种自适应选择Mean Shift算法与蒙特卡洛算法的目标跟踪策略。引入一个跟踪方式选择标志,通过计算当前跟踪窗内的目标与模板的相似度来决定该标志的值,当目标与模板的相似度大于某个阈值时,选择实时性好的基于梯度最速下降的Mean Shift跟踪策略,以实现跟踪的实时性;否则选择基于随机采样、对目标模型没有限制的蒙特卡洛跟踪策略,使得位置预测结果更加准确。实验结果表明:与蒙特卡洛算法相比,该算法在跟踪性能不受影响的前提下,有效节省了系统时间,当目标简单运动时,对于100*56像素的目标,平均计算时间由原来的82ms降低为小于1ms;与Mean Shift算法相比,该算法在牺牲一些系统时间的基础上能够更加鲁棒地解决非线性目标跟踪问题。
To track target accurately and robustly, this paper chooses Monte Carlo filtering algorithm which is free from target motion model and noise. Have been referred to a great deal of overseas or domestic literatures, and many simulator experiments, deeply analyze and research on the fundamental theories of Monte Carlo Filtering. Traditional Monte Carlo Filtering has two fatal problems——the large computational load and samples degeneracy. To solve these two problems, new methods are presented.
Good model has a key position on tracking problem. Traditional model could not resist the interference of background. So, a new model building method which is based on the outline is proposed. Firstly, get the target outline which is in a given region through a set of steps such as edge detection, line detection and so on. Describe the target using the information which is inside the outline. Secondly, describe target feature combining color and shape information. So the feature description can resist the change of backlight and target itself. Experimental results show the time of building model less than 300*300 pixels is less than 1 millisecond using VC++, which could be almost ignored. The matching time using new model is greatly decreased than that of using original model.
Traditional Monte Carlo filtering algorithm has the problem of sample degeneracy. To solve this problem, this paper proposed samples building method based on visual principle and samples propagation method using half sampling and half re-sampling. At original frame, build the samples according to the distance from the center. Get denser samples where near the center and get sparser samples where far away from the center. During the samples propagation, classify the samples into good samples and bad samples. Re-sample the good samples for propagating and get new samples to replace the bad samples. Experimental results show the sample degeneracy problem is solved by this method.
Mean Shift deals badly with non-linear problems and Monte Carlo method increases the computational load greatly. In order to solve these problems, a new target tracking method that chooses Mean Shift and Monte Carlo method to track object adaptively is proposed. Introduce a sign that denotes the tracking method to this article for choosing Mean Shift and Monte Carlo. The sign is confirmed by the match degree of current target and the model. When the match degree is above a given threshold, real- time Mean Shift method which is based on gradient method is chosen to track the target fast. Otherwise, Monte Carlo method which is based on random sampling and free from target model is chosen to track the target exactly. The basic theories and the whole frame of the tracking system are given. Experimental results prove that compared with Monte Carlo, proposed method has the same tracking performance and costs less time. When the target moves linearly, the average time is 82 milliseconds for Monte Carlo and is less than 1 millisecond for proposed method when the target is 100*56 pixels. Compared with Mean Shift, proposed method is more robust to non-linear problems.
引文
[1] R. Cipolla, A. Pentland. Computer vision for human-machine interaction[M]. Cambridge University Press.1998.
[2]陈爱华.复杂环境下多模式融合的视频跟踪算法研究[D]. [博士学位论文].长春:中国科学院长春光学精密机械与物理研究所.2009.
[3]孟勃.局部最优粒子滤波目标跟踪算法的研究和应用[D].[博士学位论文].长春:中国科学院长春光学精密机械与物理研究所.2008.
[4]刘洋.运动视觉中目标的精确提取与跟踪技术[D].[博士学位论文].西安:西安电子科技大学,2007.
[5]马颂德,张正友.计算机视觉[M].上海:科学出版社,1998.
[6]郑南宁.计算机视觉与模式识别[M].第一版.北京:国防工业出版社. 1998.
[7]李玉山.数字视觉视频技术[M].西安:西安电子科技大学. 2006.
[8]贾云得.机器视觉[M].第一版.北京:科学出版社. 2000.
[9]李安平.复杂环境下的视频目标跟踪算法研究[D].[博士学位论文].上海:上海交通大学,2006.
[10]王建宇.基于序列蒙特卡洛滤波算法的视觉目标跟踪[D].[博士学位论文].哈尔滨:哈尔滨工业大学.2006.
[11]倪军,周进,袁家虎,等.空间目标序列图像相关跟踪算法[J].光电工程.2006,vol. 33(4):1-5.
[12]张云峰,宋建中.利用图像边沿特征实现相关跟踪[J].仪器仪表学报.2004,vol.25(4): 698-708.
[13]李善祥,孙一翎,李景镇.时间序列动态散斑相关跟踪测量原理及其应用[J].光子学报. 2005,vol.34(7):1066-1068.
[14]周斌,王军政,沈伟.一种基于边缘幅值分布的相关跟踪算法[J].光电工程.2009,vol. 36(5):28-33.
[15] Weichao Zhou,Wenhua Jiang,Mei Li,et al..Real-time area correlation tracker implementation based on absolute difference algorithm[J].Optical Engineering.2003,vol.42(9):2755-2760.
[16] R Venkateswarlu, B Venkateswara Rao, PVS Raju. Real time hardware implementation for area correlation tracker[J].Acquisition, Tracking, and Pointing VI.1992, SPIE vol.1697:224-234.
[17] WK Pratt. Correlation Techniques of Image Registration[J].IEEE Trans. Aerosp.Electron. Syst.1974, vol.AES-10:353-358.
[18]姚建敏.粒子滤波跟踪方法研究[D].[博士学位论文].长春:中国科学院长春光学精密机械与物理研究所. 2004.
[19] Huihua Zhang, Zhongbao Xu, Shuang Zhang.Recognition and tracking of target based on three-dimensional joint[C].2008 International Conference on Optical Instruments and Technology: Optical Systems and Optoelectronic Instruments. 2008, SPIE vol.7156,71561J:71561J_1-71561J_10.
[20] Ryan A. Kerekes and B. V. K. Vijaya Kumar.Multiple target detection in video using quadratic multi-frame correlation filtering[J].Optical Pattern Recognition XIX.2008,vol.6977 697705:1-15
[21] Zhou Feng, Meng Xiu-yun.Adaptive Kalman Filter of Transfer Alignment with Un-modeled Wing Flexure of Aircraft[J].Journal of Beijing Institute of Technology,2008,vol.17(4):434-438.
[22]刘建锋,江涌,丁传红.基于Kalman光纤陀螺的随机信号处理[J].宇航学报.2009,vol.30(2):604-608.
[23]赵龙,吴康.新型自适应Kalman滤波算法及其应用[J].压电与声光.2009,vol.31(6): 908-911.
[24]贾静平,赵荣椿.使用Mean Shift进行自适应序列图像目标跟踪[J].计算机应用研究.2005(2):247-251.
[25]张旭光,张叶,王延杰.基于Mean Shift算法的灰度人脸跟踪[J].光电工程.2008,35(1):45-54.
[26] COMANICIU D, RAMESH V, MEER P. Real-time tracking of non-rigid objects using Mean Shift[C], IEEE Conference on Computer Vision and Pattern Recognition, Hilton Head Island, SC, USA, 2000, 142-149.
[27] CHEN Xiao Ping, YU Sheng Sheng, MA Zhi Long. An improved mean-shift algorithm for object tracking[C]. Proceedings of the 7th world congress on intelligent control and automation, IEEE, 2008, 5111-5114.
[28] NUMMIARO K, KOLLER-MEIER E, VAN_GOOL L. An Adaptive Color-Based Particle Filter[J]. Image and Vision Computing, 2003 ,vol.21(01):99-110.
[29] K. Punithakumar, T. Kirubarajan and A.Sinha. A Sequential Monte Carlo Probability Hypothesis Density Algorithm for Multitarget Track-Before-Detect [J]. Signal and Data Processing of Small Target 2005. vol. 5913 59131S:1-8.
[30] G. Kitagawa. Monte Carlo Filter and Smoother for Non-Gaussian Nonlinear State Space Models. J. Computational and Graphical Statistics.1996, vol.5:1-25.
[31] GORDON N J, SALMOND D, SMITH A. Novel approach to nonlinear and non-Gaussian Bayesian state estimation[J], IEEE Proceedings-F, 1993, 140(2): 107-113.
[32] SIMON M, GORDON N. A tutorial on particle filters for on-line non-linear/non-Gaussian Bayesian tracking[J], IEEE Transaction on SignalProcessing, 2002,vol.50:174-188.
[33] N.J.Gordon, A. Doucet. Sequential Monte Carlo for Manoeuvring Target Tracking in Clutter[C].Part of the SPIE Conference on Signal and Data Processing of Small Target 1999, Vol.3809:493-500.
[34] M. Isard and A. Blake. CONDENSATION: Unifying low-level and high-level tracking in a stochastic framework[C]. Proc. Eur. Conf. Computer Vision.1998,vol.1: 767-781.
[35] ISARD M, BLAKE A. CONDENSATION-conditional density propagation for visual tracking[J]. International Journal on Computer Vision. 1998,vol.1(29):5-28.
[36] A. Doucet.On sequential Monte Carlo Methods for Bayesian Filtering[R].Technical Report, University of Cambirge, UK, Department of Engineering,1998.
[37] Nick Everett,Shien-Shin Tham and David Salmond. A Novel MCMC Tracker for Stressing Scenarios[J].Signal and Data Processing of Small Targets.2004, vol.5428:330-341.
[38] Rasmussen, C. and G. Hager, Probabilistic Data Association Methods for Tracking Complex Visual Objects. IEEE Transactions on Pattern Analysis and Machine Intelligence[J], 2001,vol.23(6):560-567.
[39] M. Briers, S. Maskell, and R. Wright. A Rao-Blackwellised Unscented Kalman Filter[J]. In Proceedings of the 6th International Conference on Information Fusion. 2003:55-61.
[40] A. Logothetis and A. Doucet. Markov chain Monte Carlo methods for tracking a manoeuvring target in clutter[C]. IEEE Conference on Decision and Control.1998:754-759.
[41] C. Andrieu and A. Doucet. Joint Bayesian model selection and estimation of noisy sinusoids via reversible jump MCMC[J]. IEEE Transactions on Signal Processing. 1999, vol.47(10):2667-2676.
[42] Murray D. W., McLauchlan P. F., Reid I. D., and Sharkey P. M., Reactions to Peripheral Image Motion Using a Head/Eye Platform[C], In Proceedings of the 4th International Conference on Computer Vision, 1993, 403-411.
[43] Davsion A. J. and Muray D. W., Mobile Robot Localization Using Active Vision[C], In Proceedings of the 5th European Conference on Computer Vision, 1998, 805-825.
[44] Fukunaga K.Introduction to Statistical Pattern Recognition[M].Boston:Academic Press,1990.
[45] Carine Hue, Jean-Pierre Le Cadre. Sequential Monte Carlo Methods for Multiple Target Tracking and Data Fusion[J], IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2002,vol.50:309-325.
[46]黄陈蓉,张正军,吴慧中.多尺度加权邻域Gap算子图像边缘检测算法[J].计算机科学,2005,vol.32(7):168-172.
[47]朱娟,刘艳滢,王延杰.一种基于Hough变换的新直线段检测算法[J].微电子学与计算机.2008,Vol.25(12):60-63.
[48]康文静等,基于改进Hough变换的直线图形快速提取算法[J],光电工程,2007,34(3):105-117.
[49] J. Illingworth,A survey of the Hough Transform, Computer Vision Graphics and Image Processing[J],1988, 44(1):87-116.
[50] D. C. W. Pao,Shapes Recognition Using the Straight Line Hough Transform: Theory and Generalization, IEEE Transactions on PAMI,1992,14(11):1076-1089.
[51] Kass M,Witkin A, Terzppoulos D. Snakes: Active Contour Models[J]. International Journal of Computer Vision.1987:321-331.
[52]李天庆,张毅,刘志,等.Snake模型综述[J].计算机工程.2005,31(9):1-3.
[53] Beis J,Lowe D G.Shape indexing using approximate nearest-neighbour search in high-dimensional spaces[C]. In:Conference on Computer Vision and Pattern Recognition, Puerto Rico,1997:1000-1006.
[54] Di Xiao, David Zahra, Pierrick Bourgeat, et.al.. An improved 3D shape context registration method for non-rigid surface registration.Medical Imaging 2010: Image Processing, Proc. Of SPIE vol.7623.
[55]周宏仁,敬忠良,王培德。机动目标跟踪[M].北京:国防工业出版社.1991.
[56] BLOM H A P, BAR-SHALOM Y. The interacting multiple model algorithm for systems with Markovian switching coefficients[J].IEEE Trans Automatic Control. 1988,33(8):780-783.
[57]王永生,范洪达.机动目标跟踪的IMM和IMM-LS自适应滤波算法[J].计算机仿真,2002,vol.19(5):48-52.
[58] Michael E. Welser, Scott T. Acton. Projection model snakes for tracking using a Monte Carlo approach[J].Journal of Electronic Imaging,2004:13(2):384-398.
[59] Peter S. Shoenfeld. A Particle Filter Algorithm for the Multi-Target Probability Hypothesis Density[J].Signal Processing, Sensor Fusion and Target Recognition XIII, Proceedings of SPIE. Vol.5429:315-325.
[60] N. Nandakumaran and T. Kirubarajan. Maneuvering Target Tracking Using Probability Hypothesis Density Smoothing[J].Signal Processing, Sensor Fusion and Target Recognition XVIII. Proc. Of SPIE 2009,vol.7336,73360F:1-10.
[61] K. Punithakumar, T. Kirubarajan and A.Sinha. Multiple model probability hypothesis density filter for tracking maneuvering targets[J]. IEEE Trans. On Aerospace and Eletronic Systems. 2008, vol.44(1):87-98.
[62] K. Punithakumar, T. Kirubarajan and A.Sinha. A multiple model probability hypothesis density filter for tracking maneuvering targets[C]. Proc. SPIE Conference on Signal and Data Processing of Small Targets. 2004,vol.5428:113-121.
[63] K. Punithakumar, T. Kirubarajan and A.Sinha. A Distributed implementation of a Sequential Monte Carlo Probability Hypothesis Density Filter for Sensor Networks. Signal Processing, Sensor Fusion, and Target Recognition XV. vol. 6235(2006).
[64] K. Punithakumar and T. Kirubarajan. Spline Filter for Nonlinear/Non-Gaussian Bayesian Tracking. Signal and Data Processing of Small Target 2007. vol. 6699(2007).
[65] ZHU Juan, WANG Shuai, Wang Da-wei, et.al.. Monte Carlo tracking method with threshold constraint. 2nd International Congress On Image and Signal Processing (CISP).2009,vol.7:3382-3385.
[66] M. Black and A. Jepson. A probabilistic framework for matching temporal trajectories: Condensation-based recognition of gestures and expressions[C]. in European Conference on ComputerVision, 1998, vol. 1:909–924.
[67] Craig S. Agete and Kevin J. Sullivan. Road-Constrained Target Tracking and Identification Using a Particle Filter[J].Signal and Data Processing of Small Targets.2003, vol.5204:532-543.
[68] S. Arulampalam and B. Ristic. Comparison of the particle filter with range-parameterised and modified polar EKFs for angle-only tracking[C]. Proceedings of SPIE Conference on Signal and Data Processing of Small Targets. 2000,vol.4048:288-299.
[69] R. A. Iltis. State estimation using an approximate reduced statistics algorithm[J]. IEEE Transactions on Aerospace and Electronic Systems.1999,vol. AES-35:1161-1172.
[70] R. Bucy and K. Senne. Digital synthesis of non-linear filters[J]. Automatica 7.1971:287-298.
[71] H. Sorenson and D. Alspach. Recursive Bayesian estimation using Gaussian sums. Automatica 7.1971:465-479.
[72] Zhangfeng Yue, Pramod Lakshmi Narasimha, Pankaj Topivala.Improved target tracking in aerial video using particle filtering[J].Airborne Intelligence, Surveillance, Reconnaissance Systems and Applications VI. 2009, vol.7307 73070K:1-9.
[73] K. Toyama and A. Blake. Probabilistic tracking in a metric space[C]. Proc. IEEE Int. Conf. Computer Vision.2001:50-59.
[74]郭娟,林冬,戚文芽.基于加权Fisher准则的线性鉴别分析及人脸识别[J].计算机应用.2006(5):1037-1039,1049
[75] J.S.Liu, R. Chen. Sequential Monte Carlo for Dynamic Systems[J]. Journal of the American Statistical Association.1998,vol.93:1031-1041.
[76] S. Zhou, R. Chellappa, B. Moghaddam. Visual tracking and recognition using appearance-based modeling in particle filters[J]. IEEE Transactions on Image Processing.2004, vol.13(11):1491-1506.
[77] R. Hartley, A. Zisserman. Multiple View Geometry in Computer Vision[M].England: Cambridge University Press.2000.
[78] A. Doucet, N. de Freitas and N. Gordon.Sequential Monte Carlo Methods in Practice[M].New York:Springer-Verlag.2001.
[79] Espiau B, Chaumete F, and Rives P. A New Approach to Visual Servoing in Robotics[J], IEEE Transactions on Robotics and Automation, 1992,vol. 8(3): 313-326.
[80]姚剑敏,辛琦,郭太良.一种基于粒子滤波的自适应相关跟踪算法[J].武汉理工大学学报信息与管理工程版.2008,vol.30(1):6-9.
[81]朱胜利.Mean Shift及相关算法在视频跟踪中的研究[D]. [博士学位论文].杭州:浙江大学,2006.
[82]文志强,蔡自兴.一种基于Mean Shift的鲁棒性目标跟踪方法[J].计算机应用研究.2008,vol.25(6):1753-1758.
[83] Cheng Y. Mean Shift, mode seeking, and clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence.1995,vol.17(8):790-799.
[84] Comaniciu D, Ramesh V, Meer P. Real-time tracking of non-rigid object using mean shift[C]. Proc of IEEE Conf on Computer Vision and Pattern Recognition.2000: 142-149.
[85] Comaniciu D, Ramesh V, Meer P. Kernel-based object tracking[J]. IEEE Trans on Pattern Analysis and Machine Intelligence,2003, vol.25(5):564-577.
[86] Comaniciu D. Image segmentation using clustering with saddle point detection[C]. Proc of IEEE Int’1 Conf on Image Processing,2002:297-300.
[87] Georgescu B, Shimshoni I, Meer P. Mean Shift based clustering in high dimensions: a texture classification example[C]. Proc of ICCV. 2003:456-463.
[88] Comaniciu D. An algorithm for data-driven bandwidth selection[J]. IEEE Trans on Pattern Analysis and Machine Intelligence.2003,vol.25(2):281-288.
[89]彭宁嵩,杨杰,刘志等. Mean Shift跟踪算法中核函数窗宽的自动选取[J].软件学报.2005,vol.16(9):1542-1550.
[90] Comaniciu D., Meer P. Mean Shift: A robust approach toward feature space analysis[J].IEEE Trans on Pattern Analysis and Machine Intelligence. 2002,vol.24(5):603-619.
[91] Collins R.T. Mean Shift blob tracking through scale space[C].Proc of Conf on Computer Vision and Pattern Recognition.2003:234-240.
[92] Peng N S, Yang J,Liu Z. Mean Shift blob tracking with kernel histogram filtering and hypothesis testing[J].Pattern Recognition Letters.2005,vol.26(5):605-614.
[93] Collins R T, Liu Y,Leordeanu M. Online selection of discriminative tracking features[J].IEEE Trans on Pattern Analysis and Machine Intelligence.2005, vol.27(10):1631-1643.
[94]许海霞,王耀南,袁小芳等.一种分层Mean Shift目标跟踪算法[J].自动化学报.2009,vol.35(4):401-409.
[95]康文静,丁雪梅,刘功亮等.带宽自适应Mean Shift跟踪算法[J].光电子激光.2008,vol.19(1):135-138.
[96]邸男,朱明.一种复杂背景下的实时目标跟踪算法.中国图像图形学报,2008(13):1758-1765.
[97] Di Nan, Zhu Ming, Wang Yinan. Real Time Method for Airport Runway Detection in Aerial Images[C]. International Conference on Audio, Language and Image Processing(ICALIP), 2008(1):563-567.
[98] Yang C, Duraiswami R, Davis L. Similarity Measure for Nonparametric Kernel Density Based Object Tracking[J]. In:submitted to NIPS 2004,2004.
[99] Kailath T. The Divergence and Bhattacharyya Distance Measures in Signal Selection[J]. IEEE Trans. Comm. Thchnology., 1967,15: 52-60.
[100]胡士强,敬忠良.粒子滤波算法综述[J].控制与决策. 2005,vol.20(4):361-371.
[101]孙俊喜,孙中森,宋建中.基于粒子滤波的目标实时跟踪系统[J].视频技术应用与工程.2007,vol.31(3):85-87.
[102]李忠范,高文森.数理统计与随机过程[M].吉林大学出版社.第一版
[103]盛骤.概率论与数理统计.高等教育出版社[M].第二版.
[104] HwangRyol Ryu and Manfred Huber.A Particle Filter Approach for Multi-Target Tracking[C].Proceedings of the 2007 IEEE International Conference on Intelligent Roberts and Systems San Diego.2007:2753-2760.
[105] M Isard and J. MacCormick. Bramble. A Bayesian multiple-blob tracker[J].in ICCV.2001:34-41.
[106] Thomas B. Moeslund and Erik Granum. Sequential Monte Carlo Tracking of Body Parameters in a Sub-Space[J].Proceedings of the IEEE International Workshop on Analysis and Modeling of Faces and Gestures.2003.
[107] Fujun Pei, Pingyuan Cui, Yangzhou Chen. Adaptive MCMC Particle Filter for Nonlinear and Non-Gaussian State Estimation[C]. The 3rd International Conference on Innovative Computing Information and Control.2008.
[108] NUMMIARO, KOLLER M E, GOOL L V. Color features for tracking non-rigid object. Special Issue on Vision Surveillance[J], Image and Vision Computing. 2003, 29(3): 345-355.
[109] Wang Hongling, Yang Bo, Tian Guodong, et al..Object Tracking by Applying Mean-Shift Algorithm into Particle Filteringp[J]. Proceedings of IC-BNMT2009. 2009:550-554.
[110] Kejia Bai, Weiming Liu. Improved Object Tracking with Particle Filter and Mean Shift[C].IEEE International Conference on Automation and Logistics.2007: 431-435.
[111] V.Venkatrswar, R. Chellappa. Extracting Straight Lines in Aerial Images[J]. IEEE Trans. On Pattern Analysis and Machie Intelligent. 1992, 14(11): 1111-1114.
[112]宋华军.基于支持向量机目标跟踪技术研究[D].[博士学位论文].长春:中国科学院长春光学精密机械与物理研究所. 2005.
