基于信念传播算法的运动目标检测
|
摘要
随着计算机硬件和软件的发展,计算机视觉技术受到了人们越来越多的关注。尤其在军事、航空航天、计算机辅助设计、智能机器人等领域,计算机视觉技术得到了广泛的应用。在计算机视觉技术中,基于视频序列的视觉技术是最为重要的,因此也成为人们研究的重点和难点。视频序列中运动目标的检测与跟踪,又是基于视频序列的计算机视觉技术的基础和关键,所以对它们的研究就显得格外的重要。
本文在阅读相关文献的基础上,对运动目标检测方法的发展及研究现状进行了总结。然后介绍了马尔可夫随机场(MRF)和期望最大化(EM)算法的相关概念和基本原理。
本文实现了一种基于信念传播算法的运动目标检测方法。该方法采用基于帧差图像的运动目标检测方法,首先根据差分图像采用期望最大化算法将图像中每个像素分为目标与背景两类。因其结果中会存在一些噪声,需要一种平滑算法消除噪声。本文选择平滑效果较好的信念传播算法实现图像平滑,该算法结合马尔可夫随机场模型与图模式理论,根据每个像素节点的信念计算其状态值,通过消息传播将每个节点的信念传播到其邻域,从而实现了数据的平滑。本文在定义信念传播算法的相容函数时结合了空间梯度信息——梯度算子,用梯度算子约束数据平滑,使平滑效果更为准确。本文采用一种的基于方向信息的边缘提取算子,该算子提取的边缘比普通边缘提取算子的结果更完整。
由于两帧差分图像信息本身不完整的特点,经平滑后的结果仍有可能覆盖不了完整目标。通过计算目标区域最近的闭合边缘的方法估计出准确的目标。
文中最后介绍了算法的仿真实现并给出了实验结果。实验证明,该算法能较好地分割出运动目标。
With the development of hardware and software of computer, computer vision technology is attracted more and more attention by people. Especially in these fields, which include military affairs、aviation spaceflight、CAD、smart android and so on, computer vision technology is used widely. The vision technology which is based on video frequency image sequences is the most important computer vision technology, so it has became hot points and difficult points in investigate works of people. Motion objects detection and tracking which is based on video frequency ,is also the basic and key of computer vision technology.
First, on the basis of studying related literatures, methods and development of motion object detection are introduced. Second, the related concept of the basic principles about Markov Random Field (MRF) and Expectation Maximum(EM)are introduced and methods are studied in detail.
In this paper, a motion object detection method based on belief propagation is proposed, which is based on the time-differenced image of the moving object detection method. In the method, pixels in the image will be divided into two types of background and target, according to the difference image. But there are some noises in the result and a smooth algorithm to remove the noise is needed to make the result more precisely. In the time-differenced image, motion pixels are mainly focused on the edge of the larger gradient, and the goal is often more empty, so a belief propagation algorithm with a larger effort to disseminate the trust is chosen to smooth, which is combined with a gradient of space-gradient operator. Gradient operator is used to constrain smooth and more accurate results can be got. Results from Expectation Maximum(EM) algorithm for classification are smoothed in order to achieve the target partition movement.
Finally, the algorithm describes the realization of simulation, experiment is performed and results are given. It proves that the algorithm has a better performance for motion objects detection.
本文在阅读相关文献的基础上,对运动目标检测方法的发展及研究现状进行了总结。然后介绍了马尔可夫随机场(MRF)和期望最大化(EM)算法的相关概念和基本原理。
本文实现了一种基于信念传播算法的运动目标检测方法。该方法采用基于帧差图像的运动目标检测方法,首先根据差分图像采用期望最大化算法将图像中每个像素分为目标与背景两类。因其结果中会存在一些噪声,需要一种平滑算法消除噪声。本文选择平滑效果较好的信念传播算法实现图像平滑,该算法结合马尔可夫随机场模型与图模式理论,根据每个像素节点的信念计算其状态值,通过消息传播将每个节点的信念传播到其邻域,从而实现了数据的平滑。本文在定义信念传播算法的相容函数时结合了空间梯度信息——梯度算子,用梯度算子约束数据平滑,使平滑效果更为准确。本文采用一种的基于方向信息的边缘提取算子,该算子提取的边缘比普通边缘提取算子的结果更完整。
由于两帧差分图像信息本身不完整的特点,经平滑后的结果仍有可能覆盖不了完整目标。通过计算目标区域最近的闭合边缘的方法估计出准确的目标。
文中最后介绍了算法的仿真实现并给出了实验结果。实验证明,该算法能较好地分割出运动目标。
With the development of hardware and software of computer, computer vision technology is attracted more and more attention by people. Especially in these fields, which include military affairs、aviation spaceflight、CAD、smart android and so on, computer vision technology is used widely. The vision technology which is based on video frequency image sequences is the most important computer vision technology, so it has became hot points and difficult points in investigate works of people. Motion objects detection and tracking which is based on video frequency ,is also the basic and key of computer vision technology.
First, on the basis of studying related literatures, methods and development of motion object detection are introduced. Second, the related concept of the basic principles about Markov Random Field (MRF) and Expectation Maximum(EM)are introduced and methods are studied in detail.
In this paper, a motion object detection method based on belief propagation is proposed, which is based on the time-differenced image of the moving object detection method. In the method, pixels in the image will be divided into two types of background and target, according to the difference image. But there are some noises in the result and a smooth algorithm to remove the noise is needed to make the result more precisely. In the time-differenced image, motion pixels are mainly focused on the edge of the larger gradient, and the goal is often more empty, so a belief propagation algorithm with a larger effort to disseminate the trust is chosen to smooth, which is combined with a gradient of space-gradient operator. Gradient operator is used to constrain smooth and more accurate results can be got. Results from Expectation Maximum(EM) algorithm for classification are smoothed in order to achieve the target partition movement.
Finally, the algorithm describes the realization of simulation, experiment is performed and results are given. It proves that the algorithm has a better performance for motion objects detection.
引文
[1]D.Zhang,G.Lu.Segmentation of moving objects in image sequence:A review.Circuits Syst.Signal Process.2001,20:143-183P
[2]王长军,朱善安.基于统计模型和GVF-Snake的彩色目标检测与跟踪.中国图象图形学报,2006,11(1):13-18页
[3]杜峥,张桂林,洪靖云.视频监控系统中的一种运动检测算法.机械与电子,2004,11(6):45-47页
[4]张春森,崔卫红.序列图像中运动目标的分割定位.计算机工程与应用,2005,26(10):89-91页
[5]王晓卫,宁固.一种改进的基于光流的运动目标的检测算法.武汉大学学报.信息科学版.2003,3(28):352-353页.
[6]Barron J,Fleet D and Beauchemin S.Performance of optical t7ow techniques.International Journal of Computer Vision.1994,12(1):42-77P
[7]Andrea Giachetti,Marco Campani,Vincent Torre.The Use of Optical Flow for Road Navigation.IEEE Transactions on Robotics and Automation.1998,1(14):34-47P
[8]P.Batavia,D.Pomerleau,C.Thorpe.Overtaking Vehicle Detection Using Implicit Optical Flow.Proc.IEEE Transportation Systems Conf.1997:729- 734P
[9]Strings E.Morphological change detection algorithms for surveillance applications.In:British Machine Vision Conference,Bristol,UK.2000:402-411P
[10]Barron J,Fleet D and Beauchemin S.Performance of optical t7ow techniques.International Journal of Computer Vision.1994,12(1):42-77P
[11]McKenna S et al,Tracking groups of people.Computer Vision and ImageUnderstanding.2000,80(1):42-56P
[12]Stauffer C and Crimson W.Adaptive background mixture models for real-time tracking.In:Proc IEEE Conference on Computer Vision and Pattern Recognition,Fort Collins,Colorado.1999,2:246-252P
[13]I.Haritaoglu,D.Harwood and L.S.Davis.W4:Rea-Time Surveillance of People and Their Activities.IEEE Transactions on Pattern Analysis and Machine Intelligence.2000,8(22):809-830P
[14]Karmann K and Brandt A.Moving object recognition using an adaptive background memory.In:V Cappellini,Time-varying Image Processing and Moving Object Recognition.2.Elsevier,Amsterdam,The Netherlands,1990:728-733P
[15]Kilger M.A shadow handler in a video-based real-time traffic monitoring system.In:Proc IEEE Workshop on Applications of Computer Vision,Palm Springs,CA.1992:1060-1066P
[16]Valera M,Velastin S A.Intelligent distributed surveillance systems:a review.IEE Proceedings of Vision,Image,and Signal Processing,2005,152(2):192-204P
[17]陈睿,邓宇,向世明等.结合强度喝边界信息的非参数前景/背景分割方法.计算机辅助设计与图形学学报.2005,7(6):1278-1284页
[18]Pamela C Cosman,Greg T.Kogut,Mohan M.Trivedi.Moving Shadow and Object Detection in Traffic Scenes.IEEE International Conference on Computer Vision,2000,20(10):321-324P
[19]J.Meniere.System for monitoring a swimming pool to prevent drowning accidents.US.Pat,2000,18(6):101-105P
[20]侯自强,韩崇昭.基于像素灰度归类的背景重构算法.软件学报,2005,16(9):1568-1576页
[21]周西汉,刘勃,周菏琴.一种基于对称差分和背景消减的运动检测方法.计算机仿真.2005,22(4):117-123页
[22]A Monnet,A.Mittal,N.Paragios,and A.Monnet.A method for scene modeling and change detection.US Patent pending,2003,11(9):1011- 1018P
[23]Lipton A,Fujiyoshi H and Patil R.Moving target classification and tracking from real-time video.In:Proc IEEE Workshop on Applications of Computer Vision,Princeton NJ.1998:8-14P
[24]Anderson C,Bert P and Vander Wal G.Change detection and tracking using pyramidstransformation techniques.In:Proc SPIE Conference on Intelligent Robots and Computer Vision,Cambridge,MA.1985,579:72-78P
[25]Collins R et al.A system for video surveillance and monitoring:VSAM final report.Carnegie Mellon University,Technical Report:CMU-RI-TR-00-12,2000(2):56-62P
[26]Barton J,Fleet D and Beauchemin S.Performance of optical t7ow techniques.International Journal of Computer Vision.1994,12(1):42-77P
[27]杨威,张田文.复杂景物环境下运动变化区域检测的新方法.计算机研究与发展.1998,8(35):724-728P
[28]D.Koller,KDanilidis,H.H.Nagel.Motion-Based Object Tracking in Monocular Iinage Sequences of Road Traffic Scenes.Joumal of Computer Vsion,1993,10(3):257-281P
[29]Mohamed F.Abdekader,Rama Chellappa,Qinfen Zheng.Integratcd Motion Detection and Tracking for Visual Surveillance.IEEE International Conference on Computer Vision System,2002,27(5)30-36P
[30]Zhao Ming-ying,Zhao Jun,Zhao Shu-guang,et al.A novel method for moving object detection in intelligent video surveillance systems.In:International Conference on Computational Intelligence and Security,2006:1797-1800P
[31]沈海浪,平西建,周利莉等.一种基于差分图象的多运动目标检测方法.中国图象图形学报.2003,8(spec.):702-705页
[32]杨莉,李玉山,刘洋等.复杂背景下多运动目标轮廓检测.电子与信息学报.2005,27(2):306-309页
[33]朱明早,罗大庸,曹倩霞.帧间差分与背景差分相融合的运动目标检测算法.计算机测量与控制.2005,13(3):215-217页
[34]吴思,张勇东,林守勋,李豪杰.动态场景视频序列中的前景区域自动提取.计算机辅助设计与图形学学报.2005,17(2):359-363页
[35]Ming Jiang.Mathematical Models in Computer Vision and Image Processin.http://ct.radiology.uiowa.edu/-jiangm/courses/mm-cv-ip/vision.html 2001.7
[36]T.Simchony,R.Chellappa,and Z.Lichtenstein.Relaxation algorithms for MAP estimation of gray-level images with multiplicative noise.IEEE Trans.on Information Theory,1990,36(3):608-613P
[37]Papps T N,An adaptive clustering algorithm for image segmentation.IEEE Transactions on Signal Processing,1992,40(4):901-914P
[38]Liu J Q,Yang Y H,Multi-resolution color-image segmentation.IEEE Transaction on Pattern Analysis and Machine Intelligence,1994,16(7):689-700P
[39]Andrey P,Tarroux P,Unsupervised segmentation of Markov random field modeled textured images using selection relaxation.IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(3):252-262P
[40]詹劲峰,戚飞虎,王海龙.基于时空马尔可夫随机场的运动目标分割技术.通信学报.2000,21(11):63-68页
[41]J.A.Bilmes.A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models.Department of Electrical Engineering and Computer Science U.C.Berkeley,Technical Report.1998:1-13P
[42]温经纬,罗四维等.基于Bayesian的期望最大化方法一BEM算法.计算机研究与发展.2001,38(7):821-824页
[43]张士峰.混合正态分布参数极大似然估计的EM算法.飞行器测控学报.2004,23(4):47-52页
[44]T.K.Moon.The Expectation-Maximization Algorithm.IEEE Signal Processing Magazine.1996,13(6):47-60P
[45]Dempster A.P.,LairdN.M.,RubinD.B..Maximum-likelihood from incomplete data via the EM algorithm.Journal of the Royal Statistical Society,Series B(Methodological),1977,39(1):1-38P
[46]M.Kim,J.G..Choi,D.Kim,M.H.Lee,C.Ahn and Y.S.Ho.A VOP Generation Tool:Automatic Segmentation of Moving Objects in Image Sequences Based on Spatio-Temporal Information.IEEE Trans.On Circuits and Systems for Video Technology,1999,9(8):1216-1226P
[47]朱辉,李在铭.视频序列中运动目标检测技术.信号处理.2002(5):449-451页
[48]Freeman W.T.,Pasztor E.C.,Carmichael O.T.,"Learning Low-Level Vision", International Journal of Computer Vision,October 2000,Vol 50,Issue 1,pps 25-57P
[49]E.Rodemich,R.j.McEliece and J.F.Cheng,"The Turbo decision algorithm.1995.366-379P
[50]Y.Weiss,"Belief propagation and revision in networks with loops",In NIPS97,work ongraphical models,1997
[51]仲兴荣,黄贤武等.基于快速EM算法的马尔科夫随机场模型运动目标自动分割.微电子学与计算机学报.2004,21(1):102-105页
[52]Zhaozheng Yin and ROBert Collins.Belief Propagation in a 3D Spatiotemporal MRF for Moving Object Detection.IEEE Computer Vision and Pattern Recognition(CVPR),2007(6):17-22P
[53]Yongseok Yoo.A Moving Object Detection Algorithm for Smart Cameras.IEEE Computer Society Conference 2008,(6):1-8P
[54]孙瑾,顾宏斌等.一种基于梯度方向信息的运动目标检测算法.中国图象图形学报.2008(13):571-579页
[55]Marshall F.Tappen,William T.Freeman.Comparison of graph cuts with belief propagation for stereo,using identical MRF parameters,IEEE International Conference.2003(10):900-906P
[2]王长军,朱善安.基于统计模型和GVF-Snake的彩色目标检测与跟踪.中国图象图形学报,2006,11(1):13-18页
[3]杜峥,张桂林,洪靖云.视频监控系统中的一种运动检测算法.机械与电子,2004,11(6):45-47页
[4]张春森,崔卫红.序列图像中运动目标的分割定位.计算机工程与应用,2005,26(10):89-91页
[5]王晓卫,宁固.一种改进的基于光流的运动目标的检测算法.武汉大学学报.信息科学版.2003,3(28):352-353页.
[6]Barron J,Fleet D and Beauchemin S.Performance of optical t7ow techniques.International Journal of Computer Vision.1994,12(1):42-77P
[7]Andrea Giachetti,Marco Campani,Vincent Torre.The Use of Optical Flow for Road Navigation.IEEE Transactions on Robotics and Automation.1998,1(14):34-47P
[8]P.Batavia,D.Pomerleau,C.Thorpe.Overtaking Vehicle Detection Using Implicit Optical Flow.Proc.IEEE Transportation Systems Conf.1997:729- 734P
[9]Strings E.Morphological change detection algorithms for surveillance applications.In:British Machine Vision Conference,Bristol,UK.2000:402-411P
[10]Barron J,Fleet D and Beauchemin S.Performance of optical t7ow techniques.International Journal of Computer Vision.1994,12(1):42-77P
[11]McKenna S et al,Tracking groups of people.Computer Vision and ImageUnderstanding.2000,80(1):42-56P
[12]Stauffer C and Crimson W.Adaptive background mixture models for real-time tracking.In:Proc IEEE Conference on Computer Vision and Pattern Recognition,Fort Collins,Colorado.1999,2:246-252P
[13]I.Haritaoglu,D.Harwood and L.S.Davis.W4:Rea-Time Surveillance of People and Their Activities.IEEE Transactions on Pattern Analysis and Machine Intelligence.2000,8(22):809-830P
[14]Karmann K and Brandt A.Moving object recognition using an adaptive background memory.In:V Cappellini,Time-varying Image Processing and Moving Object Recognition.2.Elsevier,Amsterdam,The Netherlands,1990:728-733P
[15]Kilger M.A shadow handler in a video-based real-time traffic monitoring system.In:Proc IEEE Workshop on Applications of Computer Vision,Palm Springs,CA.1992:1060-1066P
[16]Valera M,Velastin S A.Intelligent distributed surveillance systems:a review.IEE Proceedings of Vision,Image,and Signal Processing,2005,152(2):192-204P
[17]陈睿,邓宇,向世明等.结合强度喝边界信息的非参数前景/背景分割方法.计算机辅助设计与图形学学报.2005,7(6):1278-1284页
[18]Pamela C Cosman,Greg T.Kogut,Mohan M.Trivedi.Moving Shadow and Object Detection in Traffic Scenes.IEEE International Conference on Computer Vision,2000,20(10):321-324P
[19]J.Meniere.System for monitoring a swimming pool to prevent drowning accidents.US.Pat,2000,18(6):101-105P
[20]侯自强,韩崇昭.基于像素灰度归类的背景重构算法.软件学报,2005,16(9):1568-1576页
[21]周西汉,刘勃,周菏琴.一种基于对称差分和背景消减的运动检测方法.计算机仿真.2005,22(4):117-123页
[22]A Monnet,A.Mittal,N.Paragios,and A.Monnet.A method for scene modeling and change detection.US Patent pending,2003,11(9):1011- 1018P
[23]Lipton A,Fujiyoshi H and Patil R.Moving target classification and tracking from real-time video.In:Proc IEEE Workshop on Applications of Computer Vision,Princeton NJ.1998:8-14P
[24]Anderson C,Bert P and Vander Wal G.Change detection and tracking using pyramidstransformation techniques.In:Proc SPIE Conference on Intelligent Robots and Computer Vision,Cambridge,MA.1985,579:72-78P
[25]Collins R et al.A system for video surveillance and monitoring:VSAM final report.Carnegie Mellon University,Technical Report:CMU-RI-TR-00-12,2000(2):56-62P
[26]Barton J,Fleet D and Beauchemin S.Performance of optical t7ow techniques.International Journal of Computer Vision.1994,12(1):42-77P
[27]杨威,张田文.复杂景物环境下运动变化区域检测的新方法.计算机研究与发展.1998,8(35):724-728P
[28]D.Koller,KDanilidis,H.H.Nagel.Motion-Based Object Tracking in Monocular Iinage Sequences of Road Traffic Scenes.Joumal of Computer Vsion,1993,10(3):257-281P
[29]Mohamed F.Abdekader,Rama Chellappa,Qinfen Zheng.Integratcd Motion Detection and Tracking for Visual Surveillance.IEEE International Conference on Computer Vision System,2002,27(5)30-36P
[30]Zhao Ming-ying,Zhao Jun,Zhao Shu-guang,et al.A novel method for moving object detection in intelligent video surveillance systems.In:International Conference on Computational Intelligence and Security,2006:1797-1800P
[31]沈海浪,平西建,周利莉等.一种基于差分图象的多运动目标检测方法.中国图象图形学报.2003,8(spec.):702-705页
[32]杨莉,李玉山,刘洋等.复杂背景下多运动目标轮廓检测.电子与信息学报.2005,27(2):306-309页
[33]朱明早,罗大庸,曹倩霞.帧间差分与背景差分相融合的运动目标检测算法.计算机测量与控制.2005,13(3):215-217页
[34]吴思,张勇东,林守勋,李豪杰.动态场景视频序列中的前景区域自动提取.计算机辅助设计与图形学学报.2005,17(2):359-363页
[35]Ming Jiang.Mathematical Models in Computer Vision and Image Processin.http://ct.radiology.uiowa.edu/-jiangm/courses/mm-cv-ip/vision.html 2001.7
[36]T.Simchony,R.Chellappa,and Z.Lichtenstein.Relaxation algorithms for MAP estimation of gray-level images with multiplicative noise.IEEE Trans.on Information Theory,1990,36(3):608-613P
[37]Papps T N,An adaptive clustering algorithm for image segmentation.IEEE Transactions on Signal Processing,1992,40(4):901-914P
[38]Liu J Q,Yang Y H,Multi-resolution color-image segmentation.IEEE Transaction on Pattern Analysis and Machine Intelligence,1994,16(7):689-700P
[39]Andrey P,Tarroux P,Unsupervised segmentation of Markov random field modeled textured images using selection relaxation.IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(3):252-262P
[40]詹劲峰,戚飞虎,王海龙.基于时空马尔可夫随机场的运动目标分割技术.通信学报.2000,21(11):63-68页
[41]J.A.Bilmes.A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models.Department of Electrical Engineering and Computer Science U.C.Berkeley,Technical Report.1998:1-13P
[42]温经纬,罗四维等.基于Bayesian的期望最大化方法一BEM算法.计算机研究与发展.2001,38(7):821-824页
[43]张士峰.混合正态分布参数极大似然估计的EM算法.飞行器测控学报.2004,23(4):47-52页
[44]T.K.Moon.The Expectation-Maximization Algorithm.IEEE Signal Processing Magazine.1996,13(6):47-60P
[45]Dempster A.P.,LairdN.M.,RubinD.B..Maximum-likelihood from incomplete data via the EM algorithm.Journal of the Royal Statistical Society,Series B(Methodological),1977,39(1):1-38P
[46]M.Kim,J.G..Choi,D.Kim,M.H.Lee,C.Ahn and Y.S.Ho.A VOP Generation Tool:Automatic Segmentation of Moving Objects in Image Sequences Based on Spatio-Temporal Information.IEEE Trans.On Circuits and Systems for Video Technology,1999,9(8):1216-1226P
[47]朱辉,李在铭.视频序列中运动目标检测技术.信号处理.2002(5):449-451页
[48]Freeman W.T.,Pasztor E.C.,Carmichael O.T.,"Learning Low-Level Vision", International Journal of Computer Vision,October 2000,Vol 50,Issue 1,pps 25-57P
[49]E.Rodemich,R.j.McEliece and J.F.Cheng,"The Turbo decision algorithm.1995.366-379P
[50]Y.Weiss,"Belief propagation and revision in networks with loops",In NIPS97,work ongraphical models,1997
[51]仲兴荣,黄贤武等.基于快速EM算法的马尔科夫随机场模型运动目标自动分割.微电子学与计算机学报.2004,21(1):102-105页
[52]Zhaozheng Yin and ROBert Collins.Belief Propagation in a 3D Spatiotemporal MRF for Moving Object Detection.IEEE Computer Vision and Pattern Recognition(CVPR),2007(6):17-22P
[53]Yongseok Yoo.A Moving Object Detection Algorithm for Smart Cameras.IEEE Computer Society Conference 2008,(6):1-8P
[54]孙瑾,顾宏斌等.一种基于梯度方向信息的运动目标检测算法.中国图象图形学报.2008(13):571-579页
[55]Marshall F.Tappen,William T.Freeman.Comparison of graph cuts with belief propagation for stereo,using identical MRF parameters,IEEE International Conference.2003(10):900-906P