基于CUDA的粒子滤波并行算法研究
|
摘要
作为计算机视觉的核心内容,视觉跟踪在智能视频监控,机器人视觉,人机交互,人工智能等领域有重大应用价值,成为研究的热点。NVIDIA公司推出的CUDA平台可以启动大量的线程并行工作,提高算法运行速度,同样被广泛应用于图像处理,视频播放,信号处理,人工智能等领域。
相比其他视觉跟踪算法,粒子滤波算法对复杂场景具备更好的鲁棒性,但很难满足实时性要求。因此,基于CUDA平台实现粒子滤波并行算法以提高算法执行效率,同时研究运动目标表观模型以提高跟踪的准确性,是十分必要的。
在分析粒子滤波理论的基础上,实现了基于颜色模型的粒子滤波算法,分析了不同的预测策略和颜色空间对算法准确性的影响。实验证明基于颜色信息的粒子滤波算法跟踪准确,但计算复杂度高,且具有一定局限性。针对粒子滤波算法计算复杂度高的问题,充分利用CUDA并行运算性能,分析了粒子滤波算法的并行性,实现了基于CUDA的粒子滤波并行算法,有效加快算法运行速度,实验证明该算法可以有效加速2.5倍。针对基于颜色信息粒子滤波跟踪算法局限性,引入一种特征描述符—协方差矩阵,设计并实现了基于协方差矩阵的粒子滤波并行算法,实验表明该算法比基于颜色信息的粒子滤波算法更具有鲁棒性。
As the core of computer vision in recent years, visual tracking has a great research value in intelligent video surveillance, robot vision and some other fields.Based on NVIDIA’s CUDA platform, it can start a lot of threads working in parallel. And CUDA is widely used in image processing, video play, signal processing, artificial intelligence and some other fields.
Compared with other algorithms, particle filter algorithm is more robust in some complex scenes, but it is difficult to meet the requirements of real-time tracking. So it is necessary to study the parallel particle filter algorithm and make related improvements in full use of the parallel computing advantages of GPU.
Firstly, it analysis the theory of particle filter algorithm, and establishes a color model embedded particle filter algorithm, tests and compares the tracking results in different prediction methods and different color space. The result shows that the color model is robust but with a high computing complexity. Also it has some limits. Then, based on the fact that the algorithm can not satisfy the real-time requirements, it presents a GPU-based parallel particle filter algorithm to make full use of GPU parallel computing advantages. The experiments shows that it can speed up 2.5 times. Finally, as to the algorithm’s limit, it introduces a more robust feature descriptor than the color model -- covariance matrix .Using covariance matrix as a feature descriptor, it implements the particle filter algorithm on GPU. Experimental results show that the algorithm is more robust.
相比其他视觉跟踪算法,粒子滤波算法对复杂场景具备更好的鲁棒性,但很难满足实时性要求。因此,基于CUDA平台实现粒子滤波并行算法以提高算法执行效率,同时研究运动目标表观模型以提高跟踪的准确性,是十分必要的。
在分析粒子滤波理论的基础上,实现了基于颜色模型的粒子滤波算法,分析了不同的预测策略和颜色空间对算法准确性的影响。实验证明基于颜色信息的粒子滤波算法跟踪准确,但计算复杂度高,且具有一定局限性。针对粒子滤波算法计算复杂度高的问题,充分利用CUDA并行运算性能,分析了粒子滤波算法的并行性,实现了基于CUDA的粒子滤波并行算法,有效加快算法运行速度,实验证明该算法可以有效加速2.5倍。针对基于颜色信息粒子滤波跟踪算法局限性,引入一种特征描述符—协方差矩阵,设计并实现了基于协方差矩阵的粒子滤波并行算法,实验表明该算法比基于颜色信息的粒子滤波算法更具有鲁棒性。
As the core of computer vision in recent years, visual tracking has a great research value in intelligent video surveillance, robot vision and some other fields.Based on NVIDIA’s CUDA platform, it can start a lot of threads working in parallel. And CUDA is widely used in image processing, video play, signal processing, artificial intelligence and some other fields.
Compared with other algorithms, particle filter algorithm is more robust in some complex scenes, but it is difficult to meet the requirements of real-time tracking. So it is necessary to study the parallel particle filter algorithm and make related improvements in full use of the parallel computing advantages of GPU.
Firstly, it analysis the theory of particle filter algorithm, and establishes a color model embedded particle filter algorithm, tests and compares the tracking results in different prediction methods and different color space. The result shows that the color model is robust but with a high computing complexity. Also it has some limits. Then, based on the fact that the algorithm can not satisfy the real-time requirements, it presents a GPU-based parallel particle filter algorithm to make full use of GPU parallel computing advantages. The experiments shows that it can speed up 2.5 times. Finally, as to the algorithm’s limit, it introduces a more robust feature descriptor than the color model -- covariance matrix .Using covariance matrix as a feature descriptor, it implements the particle filter algorithm on GPU. Experimental results show that the algorithm is more robust.
引文
[1] Robert Collins, Alan Lipton, Takeo Kanade. A System for Video Surveilance and Monitoring. Technical. Report. CMU-RI-TR-00-12,Robotics Institute, Carnigie Mellon University, Pittsburgh, PA, May 2000
[2] B.Coifman, D.Beymer, P.McLauchlan. A Real-Time Computer Vision System for Vehicle Tracking and Traffic Surveillance. Transportation Research: Part C.1998,6(4):271-288
[3]侯志强,韩崇昭.视觉跟踪技术综述.自动化学报. 2006,32(4):603-617
[4] P.Viloa, M.J. Jones. Robust Real-Time Face Detection. International Journal of Computer Vision(IJCV). 2004, 57(2):137-154
[5] Michael Oren, Constantine Papageorgiou, Pawan Sinha. Pedestrian Detection Using Wavelet Templates. In IEEE International Conference on Computer Vision and Pattern Recogination.(CVPR) 1997. San Juan, Puerto Rico:1997. 193-197
[6] David Ross, Jongwoo Lim, Ruei-Sung Lin. Incremental Learing for Robust Visual Tracking. International Journal of Computer Vision(IJCV), 2008, 77(1):125-141
[7] Harris C, Stephens M. A Combined Corner and Edge Detection. In the Proceedings of The Fourth Alvey for Vision. 1988. Manchester, UK:1988,147–151
[8] Lowe D.G. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision(IJCV),2004, 60(2):91-110
[9] Fukunaga K, Hostetler L. The estimation of the gradient of a density function with applications in pattern recognition. IEEE Transactions on Information Theory. 1975, Jan 21(1):32-40
[10] Y.Z. Cheng. Mean Shift Mode Seeking and Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI). 1995, 17(8):790-799
[11] D.Comaniciu, P.Meer. Mean Shift: A Robust Approach Toward Feature Space Analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI). 2002,24(5):603-619
[12] D.Comaniciu. Visvanathan Ramesh. Peter Meer. Kernel-Based Object Tracking. InIEEE International Conference on Computer Vision and Pattern Recognition(CVPR), 2003. Madison, Wisconsin: 2003. 564-577
[13] Anbang Yao. Guijin Wang, Xinggang Lin. Kernel Based Articulated Object Tracking with Scale Adaptation and Model Update. In IEEE International Conference of Computer Vision and Pattern Recognition (CVPR), 2008. Anchorage, Alaska: 2008: 564-577
[14] C. Tomasi, T. Kanade. Shape and Motion from Image Streams. A Factorization Method Part 3– Detection and tracking of point features, 1991
[15] Oncel Tuzel, Fatih Porikli, Peter Meer. Region Covariance: A Fast Descriptor for Detection and Classification. In the Proceedings of the European Conference on Computer Vision (ECCV), 2006. Graz, Austria:2006.591-600
[16] M. Sanjeev Arulampalam, Simon Maskell, Neil Gordon. A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking. IEEE Transactions on Signal Processing, 2002,50(2):174-187
[17] Greg Welch, Gary Bishop. An Introduction to the Kalman Filter. SIGGRAPH Course. 2001
[18] Michael Isard, Andrew Blake. Condensation-Conditional Density Propagation for Visual Tracking. International Journal of Computer Vision(IJCV). 1998, 29(1),1998:5-28
[19] Carine Hue, Jean-Pierre Le Cadre. Tracking Multiple Objects with Particle Fitering. IEEE Transactions on Aerospace and Electronic System. 2003:313-318
[20] Zia Khan, Tucker Balch, Frank Dellaert. MCMC-Based Particle Filtering for Tracking a Variable Number of Interacting Targets. IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI). 2005, 27(11):1805-1819
[21] Wen-Chieh Lin, Yanxi Liu. Tracking Dynamic Near-regular Texture under Occlusion and Rapid Movements. In the Proceedings of the European Conference on Computer Vision(ECCV)2006. Graz, Austria:2006. 44-55
[22] Helio Palaio, Jorge Batista. A region covariance embedded in a particle filter for multi-objects tracking. In The Eighth International Workshop on Visual Surveillance-VS 2008. Marseille,France:2008. 33-40
[23] Junqiu Wang, Yagi, Y. Integrating Shape and Color Features for Adaptive Real-time Object Tracking. Robotics and Biomimetics. 2006. Kunming,China: 2006. 1-6
[24] Xue Mei ,Haibin Ling. Robust Visual Tracking using `1 Minimization. Computer Vision, 2009 IEEE 12th International Conference on. (ICCV) 2009: 1436 - 1443
[25] Shen C, Brooks M, Hengel A. Augmented particle filtering for efficient visual tracking. In Proceedings of the IEEE International Conference on Image Processing,(ICIP) 2005. Genoa, Italy:2005. 856-865
[26] Maggio. E, Cavallaro, A. Hybrid Particle Filter and Mean Shift tracker with adaptive transition model. In Proceedings of IEEE International Conference on Acoustics,Speech, and Signal Processing(ICASSP 2005): 221-224
[27] Nan Zhang, Yun-shan Chen, Jian-li Wang. Image parallel processing based on GPU. In International Conference on Advanced Computer Control(ICACC), 2010. Shenyang:2010.367-371
[28]李培华.一种新颖的基于颜色信息的粒子滤波器跟踪算法.计算机学报,2009,32(12):2454-2463
[29] Midhun M, Neethu K Chandran, Real-time face tracking with GPU acceleration. In Conference of Process Innovation and Performance Optimization, INNOPT’08:128-134
[30] Mark Evans, Francois du Plessis. GPU Particle Filter For Computer Vision Used In Mobile Robitcs. In International Conference of CAD/CAM. Robotics & Factories of the Future Conference. Pretoria. South Africa:2010. 125-130
[31] Claus Lenz, Giorgio Panin, Alois Knoll. A GPU-accelerated particle filter with pixel-level likelihood. In Conference of Vision Modeling and Visualization Workshop, VMV 2008:2008:250-258
[32] Antonio S Montemayor, Juan Jos′e Pantrigo, Ra′ul Cabido. Improving GPU Particle Filter with Shader Model 3.0 for Visual Tracking. In the Conference of Special Interest Group on Computer Graphics and Interactive Techniques. SIGGRAPH 2006. Boston,USA:2006. 231-234
[33] Breitbart, J. Data structure design for GPU based heterogeneous systems. In International Conference on High Performance Computing & Simulation,(HPCS)2009. Leipzig:2009.44-49
[34] Gang Chen, Guobo Li, Songwen Pei. High Performance Computing Via a GPU. In International Conference on Information Science and Engineering(ICISE), 2009. Nanjing:2009.238-242
[35] Wu-chun Feng, Shucai Xiao. To GPU synchronize or not GPU synchronize?. In Proceedings of 2010 IEEE International Symposium on Circuits and Systems(ISCAS). Paris, France:2010.3801-3805
[36]胡士强;敬忠良.粒子滤波算法综述. 2005(4):361-365
[37] Arnaud Doucet. Adam M. Johansen. A Tutorial on Particle Filtering and Smoothing:Fifteen years later. In Handbook of Nonlinear Filtering. University Press: 2009
[38] A. Doucet, J. F. G. de Freitas, N. J. Gordon. An introduction to sequential Monte Carlo methods in Sequential Monte Carlo Methods in Practice. Edition 1 USA: Springer, 2010: 17-28
[39] N. Bergman, Recursive Bayesian estimation. Navigation and tracking applications. Ph.D. dissertation, Link?ping Univ., Link?ping, Sweden,1999
[40] S. Godsill, A. Doucet, M. West, Methodology for Monte Carlo smoothing with application to time-varying autoregressions. Journal of the American Statistical Association. 2004, 99(465):156-168,
[41] David Aldous . Jim Fill, Reversible Markov Chains and Random Walks on Graphs, http://stat-www.berkeley.edu/users/aldous/RWG/book.html.
[42]吕效国;王金华;马阿芹.自回归模型的自回归分析及其应用.扬州大学学报(自然科学版). 2010(3):31-35
[43] Comaniciu D, Ramesh V, Meer P., Real-time Tracking of Non-rigid Objects Using Mean Shift. In IEEE International Conference on Computer Vision and Pattern Recognition, (CVPR) 2000. SC, USA: 2000.142-149.
[44]杨振海,程维虎.非均匀随机数的产生.数理统计与管理,2006,25(6):751-756
[45] Wolfgang F?rstner, Boudewijn Moonen, Fdpdq Gdq A Metric for Covariance Matrices. TR Dept. of Geodesy and Geoinformatics, Stuttgart University, 1999
[46] Paul Viola ,Michael Jones. Rapid Object Detection using a Boosted Cascade ofSimple Features. In IEEE International Conference on Computer Vision And Pattern Recognition (CVPR), 2001. Kauai, USA:2001.511-518
[47] X. Pennec, P. Fillard, N. Ayache. A Riemannian frame-work for tensor computing. International. Journal. of Computer Vision(IJCV),2006,66(1):41–66
[48] Blelloch G. E. Prefix sums and their applications. USA: Morgan Kaufmann, 1993:35-60.
[2] B.Coifman, D.Beymer, P.McLauchlan. A Real-Time Computer Vision System for Vehicle Tracking and Traffic Surveillance. Transportation Research: Part C.1998,6(4):271-288
[3]侯志强,韩崇昭.视觉跟踪技术综述.自动化学报. 2006,32(4):603-617
[4] P.Viloa, M.J. Jones. Robust Real-Time Face Detection. International Journal of Computer Vision(IJCV). 2004, 57(2):137-154
[5] Michael Oren, Constantine Papageorgiou, Pawan Sinha. Pedestrian Detection Using Wavelet Templates. In IEEE International Conference on Computer Vision and Pattern Recogination.(CVPR) 1997. San Juan, Puerto Rico:1997. 193-197
[6] David Ross, Jongwoo Lim, Ruei-Sung Lin. Incremental Learing for Robust Visual Tracking. International Journal of Computer Vision(IJCV), 2008, 77(1):125-141
[7] Harris C, Stephens M. A Combined Corner and Edge Detection. In the Proceedings of The Fourth Alvey for Vision. 1988. Manchester, UK:1988,147–151
[8] Lowe D.G. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision(IJCV),2004, 60(2):91-110
[9] Fukunaga K, Hostetler L. The estimation of the gradient of a density function with applications in pattern recognition. IEEE Transactions on Information Theory. 1975, Jan 21(1):32-40
[10] Y.Z. Cheng. Mean Shift Mode Seeking and Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI). 1995, 17(8):790-799
[11] D.Comaniciu, P.Meer. Mean Shift: A Robust Approach Toward Feature Space Analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI). 2002,24(5):603-619
[12] D.Comaniciu. Visvanathan Ramesh. Peter Meer. Kernel-Based Object Tracking. InIEEE International Conference on Computer Vision and Pattern Recognition(CVPR), 2003. Madison, Wisconsin: 2003. 564-577
[13] Anbang Yao. Guijin Wang, Xinggang Lin. Kernel Based Articulated Object Tracking with Scale Adaptation and Model Update. In IEEE International Conference of Computer Vision and Pattern Recognition (CVPR), 2008. Anchorage, Alaska: 2008: 564-577
[14] C. Tomasi, T. Kanade. Shape and Motion from Image Streams. A Factorization Method Part 3– Detection and tracking of point features, 1991
[15] Oncel Tuzel, Fatih Porikli, Peter Meer. Region Covariance: A Fast Descriptor for Detection and Classification. In the Proceedings of the European Conference on Computer Vision (ECCV), 2006. Graz, Austria:2006.591-600
[16] M. Sanjeev Arulampalam, Simon Maskell, Neil Gordon. A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking. IEEE Transactions on Signal Processing, 2002,50(2):174-187
[17] Greg Welch, Gary Bishop. An Introduction to the Kalman Filter. SIGGRAPH Course. 2001
[18] Michael Isard, Andrew Blake. Condensation-Conditional Density Propagation for Visual Tracking. International Journal of Computer Vision(IJCV). 1998, 29(1),1998:5-28
[19] Carine Hue, Jean-Pierre Le Cadre. Tracking Multiple Objects with Particle Fitering. IEEE Transactions on Aerospace and Electronic System. 2003:313-318
[20] Zia Khan, Tucker Balch, Frank Dellaert. MCMC-Based Particle Filtering for Tracking a Variable Number of Interacting Targets. IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI). 2005, 27(11):1805-1819
[21] Wen-Chieh Lin, Yanxi Liu. Tracking Dynamic Near-regular Texture under Occlusion and Rapid Movements. In the Proceedings of the European Conference on Computer Vision(ECCV)2006. Graz, Austria:2006. 44-55
[22] Helio Palaio, Jorge Batista. A region covariance embedded in a particle filter for multi-objects tracking. In The Eighth International Workshop on Visual Surveillance-VS 2008. Marseille,France:2008. 33-40
[23] Junqiu Wang, Yagi, Y. Integrating Shape and Color Features for Adaptive Real-time Object Tracking. Robotics and Biomimetics. 2006. Kunming,China: 2006. 1-6
[24] Xue Mei ,Haibin Ling. Robust Visual Tracking using `1 Minimization. Computer Vision, 2009 IEEE 12th International Conference on. (ICCV) 2009: 1436 - 1443
[25] Shen C, Brooks M, Hengel A. Augmented particle filtering for efficient visual tracking. In Proceedings of the IEEE International Conference on Image Processing,(ICIP) 2005. Genoa, Italy:2005. 856-865
[26] Maggio. E, Cavallaro, A. Hybrid Particle Filter and Mean Shift tracker with adaptive transition model. In Proceedings of IEEE International Conference on Acoustics,Speech, and Signal Processing(ICASSP 2005): 221-224
[27] Nan Zhang, Yun-shan Chen, Jian-li Wang. Image parallel processing based on GPU. In International Conference on Advanced Computer Control(ICACC), 2010. Shenyang:2010.367-371
[28]李培华.一种新颖的基于颜色信息的粒子滤波器跟踪算法.计算机学报,2009,32(12):2454-2463
[29] Midhun M, Neethu K Chandran, Real-time face tracking with GPU acceleration. In Conference of Process Innovation and Performance Optimization, INNOPT’08:128-134
[30] Mark Evans, Francois du Plessis. GPU Particle Filter For Computer Vision Used In Mobile Robitcs. In International Conference of CAD/CAM. Robotics & Factories of the Future Conference. Pretoria. South Africa:2010. 125-130
[31] Claus Lenz, Giorgio Panin, Alois Knoll. A GPU-accelerated particle filter with pixel-level likelihood. In Conference of Vision Modeling and Visualization Workshop, VMV 2008:2008:250-258
[32] Antonio S Montemayor, Juan Jos′e Pantrigo, Ra′ul Cabido. Improving GPU Particle Filter with Shader Model 3.0 for Visual Tracking. In the Conference of Special Interest Group on Computer Graphics and Interactive Techniques. SIGGRAPH 2006. Boston,USA:2006. 231-234
[33] Breitbart, J. Data structure design for GPU based heterogeneous systems. In International Conference on High Performance Computing & Simulation,(HPCS)2009. Leipzig:2009.44-49
[34] Gang Chen, Guobo Li, Songwen Pei. High Performance Computing Via a GPU. In International Conference on Information Science and Engineering(ICISE), 2009. Nanjing:2009.238-242
[35] Wu-chun Feng, Shucai Xiao. To GPU synchronize or not GPU synchronize?. In Proceedings of 2010 IEEE International Symposium on Circuits and Systems(ISCAS). Paris, France:2010.3801-3805
[36]胡士强;敬忠良.粒子滤波算法综述. 2005(4):361-365
[37] Arnaud Doucet. Adam M. Johansen. A Tutorial on Particle Filtering and Smoothing:Fifteen years later. In Handbook of Nonlinear Filtering. University Press: 2009
[38] A. Doucet, J. F. G. de Freitas, N. J. Gordon. An introduction to sequential Monte Carlo methods in Sequential Monte Carlo Methods in Practice. Edition 1 USA: Springer, 2010: 17-28
[39] N. Bergman, Recursive Bayesian estimation. Navigation and tracking applications. Ph.D. dissertation, Link?ping Univ., Link?ping, Sweden,1999
[40] S. Godsill, A. Doucet, M. West, Methodology for Monte Carlo smoothing with application to time-varying autoregressions. Journal of the American Statistical Association. 2004, 99(465):156-168,
[41] David Aldous . Jim Fill, Reversible Markov Chains and Random Walks on Graphs, http://stat-www.berkeley.edu/users/aldous/RWG/book.html.
[42]吕效国;王金华;马阿芹.自回归模型的自回归分析及其应用.扬州大学学报(自然科学版). 2010(3):31-35
[43] Comaniciu D, Ramesh V, Meer P., Real-time Tracking of Non-rigid Objects Using Mean Shift. In IEEE International Conference on Computer Vision and Pattern Recognition, (CVPR) 2000. SC, USA: 2000.142-149.
[44]杨振海,程维虎.非均匀随机数的产生.数理统计与管理,2006,25(6):751-756
[45] Wolfgang F?rstner, Boudewijn Moonen, Fdpdq Gdq A Metric for Covariance Matrices. TR Dept. of Geodesy and Geoinformatics, Stuttgart University, 1999
[46] Paul Viola ,Michael Jones. Rapid Object Detection using a Boosted Cascade ofSimple Features. In IEEE International Conference on Computer Vision And Pattern Recognition (CVPR), 2001. Kauai, USA:2001.511-518
[47] X. Pennec, P. Fillard, N. Ayache. A Riemannian frame-work for tensor computing. International. Journal. of Computer Vision(IJCV),2006,66(1):41–66
[48] Blelloch G. E. Prefix sums and their applications. USA: Morgan Kaufmann, 1993:35-60.