informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-288Research ArticleОБРАБОТКА СИГНАЛОВ, ИЗОБРАЖЕНИЙ, РЕЧИ, ТЕКСТА И РАСПОЗНАВАНИЕ ОБРАЗОВSIGNAL, IMAGE, SPEECH, TEXT PROCESSING AND PATTERN RECOGNITIONАЛГОРИТМ БЫСТРОГО ВЫЧИСЛЕНИЯ ОПТИЧЕСКОГО ПОТОКА ПРИ ПОМОЩИ SSE2-ИНСТРУКЦИЙ ПРОЦЕССОРОВ СЕМЕЙСТВА x86КравчонокА. И.Объединенный институт проблем информатики НАН БеларусиBelarus20120203201802(34)1937Copyright © Кравчонок А.И., 20182018Кравчонок А.И.Кравчонок А.И.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/288

Представлен алгоритм быстрого вычисления оптического потока при помощи SSE2-инструкций на персональном компьютере. Алгоритм имеет константную сложность в зависимости от радиуса окна оптического потока, применяет SSE2 SIMD-инструкции на всех этапахвычислений, при работе на многоядерных процессорах использует параллельный режим работы. Алгоритм позволяет значительно ускорить вычисление оптического потока, что делает возможным его применение в режиме реального времени на персональных компьютерах.

ReferencesFaugeras, O. Real time correlation-based stereo: Algorithm, implementations and applications / O. Faugeras, B. Hotz, H. Mathieu // Technical Report RR-2013. – France : INRIA, 1993.Faugeras, O. Real time correlation-based stereo: Algorithm, implementations and applications / O. Faugeras, B. Hotz, H. Mathieu // Technical Report RR-2013. – France : INRIA, 1993.Yokoyama, M. A Contour-Based Moving Object Detection and Tracking / M. Yokoyama,Yokoyama, M. A Contour-Based Moving Object Detection and Tracking / M. Yokoyama,T. Poggio // 2d Joint IEEE Intern. Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance. – Breckenridge, Colorado, USA, 2005. – P. 271–276.T. Poggio // 2d Joint IEEE Intern. Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance. – Breckenridge, Colorado, USA, 2005. – P. 271–276.Denman, S. An Adaptive Optical Flow Technique for Person Tracking Systems / S. Denman,Denman, S. An Adaptive Optical Flow Technique for Person Tracking Systems / S. Denman,V. Chandran, S. Sridharan // Pattern Recognition Letters. – 2007. – Vol. 28, № 10. – P. 1232–1239.V. Chandran, S. Sridharan // Pattern Recognition Letters. – 2007. – Vol. 28, № 10. – P. 1232–1239.Kang, S. Estimation of Moving Information for Tracking of Moving Objects / S. Kang, J. Park, S. Jeong // Journal of Mechanical Science and Technology. – 2001. – Vol. 15, № 3. – P. 300–308.Kang, S. Estimation of Moving Information for Tracking of Moving Objects / S. Kang, J. Park, S. Jeong // Journal of Mechanical Science and Technology. – 2001. – Vol. 15, № 3. – P. 300–308.Sadykhov, R. Fast cross correlation algorithm for optical flow estimation / R. Sadykhov,Sadykhov, R. Fast cross correlation algorithm for optical flow estimation / R. Sadykhov,D. Lamovsky // Proc. of Nordic Signal Processing Symposium (NORSIG’2006). – Reykjavik, Iceland, 2006. – P. 322–325.D. Lamovsky // Proc. of Nordic Signal Processing Symposium (NORSIG’2006). – Reykjavik, Iceland, 2006. – P. 322–325.Sadykhov, R. Estimation of the cross correlation based optical flow for video surveillance / R. Sadykhov, D. Lamovsky // Computing. – 2006. – Vol. 5, № 3. – P. 112–117.Sadykhov, R. Estimation of the cross correlation based optical flow for video surveillance / R. Sadykhov, D. Lamovsky // Computing. – 2006. – Vol. 5, № 3. – P. 112–117.Tian, Y. Robust Salient Motion Detection with Complex Background for Real-time VideoTian, Y. Robust Salient Motion Detection with Complex Background for Real-time VideoSurveillance / Y. Tian, A. Hampapur // IEEE Computer Society Workshop on Motion and Video Computing. – Breckenridge, Colorado, USA, 2005. – Vol. 2. – P. 30–35.Surveillance / Y. Tian, A. Hampapur // IEEE Computer Society Workshop on Motion and Video Computing. – Breckenridge, Colorado, USA, 2005. – Vol. 2. – P. 30–35.Intel Corp. Block-Matching in Motion Estimation Algorithms Using Streaming SIMD Extensions 3. – USA : Intel Applications Notes, 2003.Intel Corp. Block-Matching in Motion Estimation Algorithms Using Streaming SIMD Extensions 3. – USA : Intel Applications Notes, 2003.Intel Corp. Motion Estimation with Intel® Streaming SIMD Extensions 4 (Intel® SSE4)Intel Corp. Motion Estimation with Intel® Streaming SIMD Extensions 4 (Intel® SSE4)[Electronic resource]. – Mode of access : http://software.intel.com/en-us/articles/motion-estimationwith-intel-streaming-simd-extensions-4-intel-sse4/. – Date of access : 09.09.11.[Electronic resource]. – Mode of access : http://software.intel.com/en-us/articles/motion-estimationwith-intel-streaming-simd-extensions-4-intel-sse4/. – Date of access : 09.09.11.Tran, T. Performance Enhancement of Motion Estimation Using SSE2 Technology /Tran, T. Performance Enhancement of Motion Estimation Using SSE2 Technology /T. Tran, H. Cho, S. Cho // World Academy of Science, Engineering and Technology. – 2008. –T. Tran, H. Cho, S. Cho // World Academy of Science, Engineering and Technology. – 2008. –Vol. 40. – P. 168–171.Vol. 40. – P. 168–171.Chen, Z. Efficient Block Matching Algorithm for Motion Estimation / Z. Chen // Intern.Chen, Z. Efficient Block Matching Algorithm for Motion Estimation / Z. Chen // Intern.Journal of Signal Processing. – 2009. –Vol. 5, № 2. – P. 133–137.Journal of Signal Processing. – 2009. –Vol. 5, № 2. – P. 133–137.Chen, Y. Fast block matching algorithm based on the winner-update strategy / Y. Chen,Chen, Y. Fast block matching algorithm based on the winner-update strategy / Y. Chen,Y. Hung, C. Fuh // IEEE Transactions on Image Processing. – 2001. – Vol. 10, № 8. – P. 1212–1222.Y. Hung, C. Fuh // IEEE Transactions on Image Processing. – 2001. – Vol. 10, № 8. – P. 1212–1222.Kanade, T. Development of a video-rate stereo machine / T. Kanade, H. Kato, S. Kimura //Kanade, T. Development of a video-rate stereo machine / T. Kanade, H. Kato, S. Kimura //In Proc. of Intern. Robotics and Systems Conference (IROS’95). – Pittsburgh, Pennsylvania, USA, 1995. – Vol. 3. – P. 95–100.In Proc. of Intern. Robotics and Systems Conference (IROS’95). – Pittsburgh, Pennsylvania, USA, 1995. – Vol. 3. – P. 95–100.Sun, A. Fast Stereo Matching Method / A. Sun // Proc. of Digital Image Computing: Techniques and Applications. – Auckland, New Zealand, 1997. – P. 95–100.Sun, A. Fast Stereo Matching Method / A. Sun // Proc. of Digital Image Computing: Techniques and Applications. – Auckland, New Zealand, 1997. – P. 95–100.Sun, C. Multi-Resolution Rectangular Subregioning Stereo Matching Using Fast Correlation and Dynamic Programming Techniques / C. Sun // CMIS Report 98/246. – Australia : CSIRO, 1998.Sun, C. Multi-Resolution Rectangular Subregioning Stereo Matching Using Fast Correlation and Dynamic Programming Techniques / C. Sun // CMIS Report 98/246. – Australia : CSIRO, 1998.Sun, C. Multi-Resolution Stereo Matching Using Maximum-Surface Techniques / C. Sun //Sun, C. Multi-Resolution Stereo Matching Using Maximum-Surface Techniques / C. Sun //Proc. of Digital Image Computing: Techniques and Applications. – Perth, Australia, 1999. – P. 195–200.Proc. of Digital Image Computing: Techniques and Applications. – Perth, Australia, 1999. – P. 195–200.Sun, C. Fast Stereo Matching Using Rectangular Subregioning and 3D Maximum-SurfaceSun, C. Fast Stereo Matching Using Rectangular Subregioning and 3D Maximum-SurfaceTechniques / C. Sun // Intern. Journal of Computer Vision. – 2002. – Vol. 47, № 1. – P. 99–117.Techniques / C. Sun // Intern. Journal of Computer Vision. – 2002. – Vol. 47, № 1. – P. 99–117.Sun, C. Fast Algorithms for Stereo Matching and Motion Estimation / C. Sun // Proc. ofSun, C. Fast Algorithms for Stereo Matching and Motion Estimation / C. Sun // Proc. ofAustralia-Japan Advanced Workshop on Computer Vision. – Adelaide, Australia, 2003. – P. 38–48.Australia-Japan Advanced Workshop on Computer Vision. – Adelaide, Australia, 2003. – P. 38–48.Sun, C. Fast Panoramic Stereo Matching Using Cylindrical Maximum Surfaces / C. Sun,Sun, C. Fast Panoramic Stereo Matching Using Cylindrical Maximum Surfaces / C. Sun,S. Peleg // IEEE Transactions on Systems, Man, and Cybernetics. Part B. – 2004. – Vol. 34, № 1. – P. 760–765.S. Peleg // IEEE Transactions on Systems, Man, and Cybernetics. Part B. – 2004. – Vol. 34, № 1. – P. 760–765.Hirschmüller, H. Real-Time Correlation-Based Stereo Vision with Reduced Border Errors / H. Hirschmüller, P. Innocent, J. Garibaldi // International Journal of Computer Vision. – 2002. – Vol. 47, № 1–3. – P. 229–246.Hirschmüller, H. Real-Time Correlation-Based Stereo Vision with Reduced Border Errors / H. Hirschmüller, P. Innocent, J. Garibaldi // International Journal of Computer Vision. – 2002. – Vol. 47, № 1–3. – P. 229–246.Stefano, L. A Fast Area-Based Stereo Matching Algorithm / L. Stefano, M. Marchionni,Stefano, L. A Fast Area-Based Stereo Matching Algorithm / L. Stefano, M. Marchionni,S. Mattoccia // Image and Vision Computing. – 2004. – Vol. 22, № 12. – P. 983–1005.S. Mattoccia // Image and Vision Computing. – 2004. – Vol. 22, № 12. – P. 983–1005.Stefano, L. A PC-based Real-Time Stereo Vision System / L. Stefano, M. Marchionni,Stefano, L. A PC-based Real-Time Stereo Vision System / L. Stefano, M. Marchionni,S. Mattoccia // Machine Graphics & Vision. – 2004. – Vol. 13, № 3. – P. 197–220.S. Mattoccia // Machine Graphics & Vision. – 2004. – Vol. 13, № 3. – P. 197–220.Sun, C. Fast Optical Flow Using Cross Correlation and Shortest-Path Techniques / C. Sun // Proc. of Digital Image Computing: Techniques and Applications. – Perth, Australia, 1999. – P. 143–148.Sun, C. Fast Optical Flow Using Cross Correlation and Shortest-Path Techniques / C. Sun // Proc. of Digital Image Computing: Techniques and Applications. – Perth, Australia, 1999. – P. 143–148.Sun, C. Fast optical flow using 3d shortest path techniques / C. Sun // Image and visionSun, C. Fast optical flow using 3d shortest path techniques / C. Sun // Image and visioncomputing. – 2002. – Vol. 20, № 13/14. – P. 981–991.computing. – 2002. – Vol. 20, № 13/14. – P. 981–991.Zhao, P. Near Real-Time Optical Flow / P. Zhao, M. Spetsakis // Proc. of the 14th Intern.Zhao, P. Near Real-Time Optical Flow / P. Zhao, M. Spetsakis // Proc. of the 14th Intern.Conf. on Vision Interface. – Ottawa, ON, Canada, 2001. – P. 47–55.Conf. on Vision Interface. – Ottawa, ON, Canada, 2001. – P. 47–55.Садыхов, Р.Х. Инструментальная система для обработки видеоинформации / Р.Х. Садыхов, Д.В. Ламовский // Доклады БГУИР. – 2007. – № 4 (20). – C. 175–180.Садыхов, Р.Х. Инструментальная система для обработки видеоинформации / Р.Х. Садыхов, Д.В. Ламовский // Доклады БГУИР. – 2007. – № 4 (20). – C. 175–180.Chang, M. Optical Flow Measurement Based on Boolean Edge Detection and Hough Transform / M. Chang, I. Kim, J. Park // Intern. Journal of Control, Automation and Systems. – 2003. – Vol. 7, № 5. – P. 788–798.Chang, M. Optical Flow Measurement Based on Boolean Edge Detection and Hough Transform / M. Chang, I. Kim, J. Park // Intern. Journal of Control, Automation and Systems. – 2003. – Vol. 7, № 5. – P. 788–798.Lu, N. Motion Detection Based On Accumulative Optical Flow and Double Background Filtering / N. Lu, J. Wang, L. Yang // Proc. of World Congress on Engineering. – London, UK, 2007. – P. 602–607.Lu, N. Motion Detection Based On Accumulative Optical Flow and Double Background Filtering / N. Lu, J. Wang, L. Yang // Proc. of World Congress on Engineering. – London, UK, 2007. – P. 602–607.Krauchonak, A. Detection of Moving Objects on Videosequences Based on Region Growing Optical Flow / A. Krauchonak // Proc. of the 10th International Conference «Pattern Recognition and Image Analysis: New Informational Technologies» (PRIA-10-2010), St. Petersburg, Russian Federation, December 5–12, 2010. – St. Petersburg, 2010. – Vol. 1. – P. 223–226.Krauchonak, A. Detection of Moving Objects on Videosequences Based on Region Growing Optical Flow / A. Krauchonak // Proc. of the 10th International Conference «Pattern Recognition and Image Analysis: New Informational Technologies» (PRIA-10-2010), St. Petersburg, Russian Federation, December 5–12, 2010. – St. Petersburg, 2010. – Vol. 1. – P. 223–226.Kravchonok, A. Detection of moving objects in video sequences by the computation of optical flow based on region growing / A. Kravchonok // Pattern Recognition and Image Analysis. – 2011. – Vol. 21, № 2. – P. 283–286.Kravchonok, A. Detection of moving objects in video sequences by the computation of optical flow based on region growing / A. Kravchonok // Pattern Recognition and Image Analysis. – 2011. – Vol. 21, № 2. – P. 283–286.Barron, J. Performance of optical flow techniques / J. Barron, D. Fleet, S. Beauchemin // Intern. Journal of Computer Vision. – 1994. – Vol. 12, № 1. – P. 43–77.Barron, J. Performance of optical flow techniques / J. Barron, D. Fleet, S. Beauchemin // Intern. Journal of Computer Vision. – 1994. – Vol. 12, № 1. – P. 43–77.Horn, B. Robot Vision / B. Horn. – MIT Press. Cambridge, 1986. – 509 p.Horn, B. Robot Vision / B. Horn. – MIT Press. Cambridge, 1986. – 509 p.Lucas, B. An Iterative Image Registration Technique with an Application to Stereo Vision / B. Lucas, T. Kanade // Proc of Intern. Joint Conference on Artificial Intelligence. – Vancouver, BC, Canada, 1981. – P. 674–679.Lucas, B. An Iterative Image Registration Technique with an Application to Stereo Vision / B. Lucas, T. Kanade // Proc of Intern. Joint Conference on Artificial Intelligence. – Vancouver, BC, Canada, 1981. – P. 674–679.Anandan, P. A Computational Framework and an Algorithm for the Measurement of Visual Motion / P. Anandan // Intern. Journal of Computer Vision. – 1989. – Vol. 2. – P. 283–310.Anandan, P. A Computational Framework and an Algorithm for the Measurement of Visual Motion / P. Anandan // Intern. Journal of Computer Vision. – 1989. – Vol. 2. – P. 283–310.Bartolini, F. Motion Estimation and Tracking for Urban Traffic Monitoring / F. Bartolini,Bartolini, F. Motion Estimation and Tracking for Urban Traffic Monitoring / F. Bartolini,V. Cappellini, C. Giani // Proc of IEEE Intern. Conf. on Image Processing. – Lausanne, Switzerland, 1996. – P. 787–790.V. Cappellini, C. Giani // Proc of IEEE Intern. Conf. on Image Processing. – Lausanne, Switzerland, 1996. – P. 787–790.Stefano, L. Vehicle Detection and Tracking Using the Block Matching Algorithm / L. Stefano, E. Viarani // Proc. of Intern. Multiconference on Circuits, Systems, Communications and Computer. – Athens, Greece, 1999. – P. 4491–4496.Stefano, L. Vehicle Detection and Tracking Using the Block Matching Algorithm / L. Stefano, E. Viarani // Proc. of Intern. Multiconference on Circuits, Systems, Communications and Computer. – Athens, Greece, 1999. – P. 4491–4496.Mattoccia, S. Efficient and optimal block matching for motion estimation / S. Mattoccia,Mattoccia, S. Efficient and optimal block matching for motion estimation / S. Mattoccia,F. Tombari, L. Stefano // 14th IAPR Intern. Conf. on Image Analysis and Processing (ICIAP 2007). – Modena, Italy, 2007. – P. 705–710.F. Tombari, L. Stefano // 14th IAPR Intern. Conf. on Image Analysis and Processing (ICIAP 2007). – Modena, Italy, 2007. – P. 705–710.Toivonen, T. A New Algorithm for Fast Full Search Block Motion Estimation Based onToivonen, T. A New Algorithm for Fast Full Search Block Motion Estimation Based onNumber Theoretic Transforms / T. Toivonen // Proc. of the 9th Intern. Workshop on Systems, Signals, and Image Processing. – Manchester, United Kingdom, 2002. – P. 90–94.Number Theoretic Transforms / T. Toivonen // Proc. of the 9th Intern. Workshop on Systems, Signals, and Image Processing. – Manchester, United Kingdom, 2002. – P. 90–94.McDonnell, M. Box-filtering techniques / M. McDonnell // Computer Graphics and ImageMcDonnell, M. Box-filtering techniques / M. McDonnell // Computer Graphics and ImageProcessing. –1981. – Vol. 17, № 1. – P. 65–70.Processing. –1981. – Vol. 17, № 1. – P. 65–70.Intel Corp. Absolute-Difference Motion Estimation for Intel® Pentium® 4 Processors [Electronic resource]. – Mode of access : http://software.intel.com/en-us/articles/absolute-differencemotion-estimation-for-intel-pentiumr-4-processors/. – Date of access : 31.08.10.Intel Corp. Absolute-Difference Motion Estimation for Intel® Pentium® 4 Processors [Electronic resource]. – Mode of access : http://software.intel.com/en-us/articles/absolute-differencemotion-estimation-for-intel-pentiumr-4-processors/. – Date of access : 31.08.10.

The authors declare that there are no conflicts of interest present.