视频压缩中的运动估计技术的研究
|
摘要
在多媒体传输和存储中，由于表示视频信息的数字需要大量的比特数，对信道带宽和存储空间提出了很高的要求，已成为阻碍人类有效获取和使用信息的瓶颈之一。运动估计是视频编码的关键技术，它是一种帧间编码的方法，其最基本的原理是利用帧间的时间相关性，减少时间冗余度。一种优秀的运动估计技术应该能得到精确的运动矢量。用当前部分在相邻帧中寻找最相似的部分作为匹配部分，用运动矢量指向匹配部分，再用匹配部分与当前部分之间的差形成误差部分，以匹配部分和误差部分来重建压缩图像的过程叫运动补偿。为此，以运动估计技术为核心的视频编码中，搜索运动矢量的速度和运动矢量的准确度是影响视频最大因子。
本课题深入系统地研究了运动估计技术的基本原理，在总结现有经典算法的基础上，着手研究运动估计存在的问题，从不同的角度提出新的运动估计方案，得到了几种不同的运动搜索算法。主要工作在以下几个方面：
1、总结现有经典的估计算法，给出了较完整的实验数据和比较结果，经过实际实验数据，整理、提出了运动估计的一些理论基础；
2、从相位相关的角度对运动估计进行了研究，提出了一种新的基于相位相关的运动估计技术。
3、研究了运动矢量的时空相关性和中心偏向特性，提出了一种新的基于运动相关特性和中心偏向特性的快速运动估计算法；
4、对块匹配算法产生的块效应进行了研究。对块效应的产生进行了详细的分析，介绍并比较块效应的几种度量和消除方法。
利用运动估计技术，结合对数据压缩编码的研究，解决视频消息数据量大的问题，具有重要的理论和实际意义，是一个图像处理领域和图像通信领域极其重要的研究课题。它的研究和应用必将促进计算机通信、图像通信和多媒体技术的发展。
In multimedia-transmission and storage, as the image for video information needs a mount of bits, high quality of channel bandwidth and huge storage space are required. This has been one of the key points to get and use information efficiently. Motion estimate is the key skill in video coding, a way of between frames coding. It bases on the theory of temporal correlation between frames, to reduce temporal redundancy. An outstanding method of motion estimate can get an accurate motion vector. Finding out the most resembled part as the matching part in the neighbor by using the present part, pointing at it by motion vector, then finding out the different part between the matching part and the present part, at last rebuilding the compressed frame by the matching part and the different part, this process is called motion compensation. Therefore, in the video coding whose key skill is motion estimate, the speed of searching motion vectors and the accuracy of motion vectors are the most important factors to video effect.
This thesis expatiates deeply and systematically on the basic theory of motion estimate technique. On the base of present classical algorithms, we focuses on researching the disadvantages of those existing algorithms of motion estimate, and initiating some new ways in our own view. The main content as follows:
1. Summarize the current classical algorithms of motion estimate, present integrated experimental data and comparisons, trim and put forward some basic theories of motion estimate.
2. Research motion estimate by phase correlation way, bring forward a new technique of motion estimate on the base of phase correlation.
3. Study space-time correlation and center biased distribution of motion vector, on which initiate a new fast search algorithm of motion estimate.
4. Research the blocking effect of block matching algorithms. Analyze deeply the reason of blocking effect, introduce and compare several measure criterions and theories and ways to reducing blocking effect. It is significant in both theoretics and practicality to combine the
motion estimate technique and research of data compressed coding to solve the problem of huge information data in video, which is an important question for discussion in image processing field and image communication field. The research and application of it inevitably promote the development of computer communication, image communication and multi-media technique.
本课题深入系统地研究了运动估计技术的基本原理，在总结现有经典算法的基础上，着手研究运动估计存在的问题，从不同的角度提出新的运动估计方案，得到了几种不同的运动搜索算法。主要工作在以下几个方面：
1、总结现有经典的估计算法，给出了较完整的实验数据和比较结果，经过实际实验数据，整理、提出了运动估计的一些理论基础；
2、从相位相关的角度对运动估计进行了研究，提出了一种新的基于相位相关的运动估计技术。
3、研究了运动矢量的时空相关性和中心偏向特性，提出了一种新的基于运动相关特性和中心偏向特性的快速运动估计算法；
4、对块匹配算法产生的块效应进行了研究。对块效应的产生进行了详细的分析，介绍并比较块效应的几种度量和消除方法。
利用运动估计技术，结合对数据压缩编码的研究，解决视频消息数据量大的问题，具有重要的理论和实际意义，是一个图像处理领域和图像通信领域极其重要的研究课题。它的研究和应用必将促进计算机通信、图像通信和多媒体技术的发展。
In multimedia-transmission and storage, as the image for video information needs a mount of bits, high quality of channel bandwidth and huge storage space are required. This has been one of the key points to get and use information efficiently. Motion estimate is the key skill in video coding, a way of between frames coding. It bases on the theory of temporal correlation between frames, to reduce temporal redundancy. An outstanding method of motion estimate can get an accurate motion vector. Finding out the most resembled part as the matching part in the neighbor by using the present part, pointing at it by motion vector, then finding out the different part between the matching part and the present part, at last rebuilding the compressed frame by the matching part and the different part, this process is called motion compensation. Therefore, in the video coding whose key skill is motion estimate, the speed of searching motion vectors and the accuracy of motion vectors are the most important factors to video effect.
This thesis expatiates deeply and systematically on the basic theory of motion estimate technique. On the base of present classical algorithms, we focuses on researching the disadvantages of those existing algorithms of motion estimate, and initiating some new ways in our own view. The main content as follows:
1. Summarize the current classical algorithms of motion estimate, present integrated experimental data and comparisons, trim and put forward some basic theories of motion estimate.
2. Research motion estimate by phase correlation way, bring forward a new technique of motion estimate on the base of phase correlation.
3. Study space-time correlation and center biased distribution of motion vector, on which initiate a new fast search algorithm of motion estimate.
4. Research the blocking effect of block matching algorithms. Analyze deeply the reason of blocking effect, introduce and compare several measure criterions and theories and ways to reducing blocking effect. It is significant in both theoretics and practicality to combine the
motion estimate technique and research of data compressed coding to solve the problem of huge information data in video, which is an important question for discussion in image processing field and image communication field. The research and application of it inevitably promote the development of computer communication, image communication and multi-media technique.
引文
[1] [美]Tekalp A M.崔之祜，江春，陈丽鑫译．数字视频处理．北京：电子工业出版社，1998
[2] Kappagantula S, Rao K R. Motion compensated interframe image prediction. IFEE Trans on Communications. 1985, COM-33(10): 1011-1015
[3] Gharavi H, Mills M. Block matching motion estimation algorithms-new results. IEEE Trans on Circuits and Systems, 1990, 37(5):6 49～6 51
[4] LiR, Zeng B, Lieu M L. A new three-step search algorithm for block motion estimation. IEEE Trans on Circuits and Systems For Video Technology, 1994, 4(4):43 8～442
[5] Po L M, Ma W C. A novel four-step algorithm for fast block motion estimation. IEEE Trans on Circuits and Systems for Video Technology, 1996 , 6(3):313～317
[6] M. Chanbari, The cross-search algorithm for motion estimation. IEEE Trans on Communication. Vol. 38, No. 7, July 1990, pp950-953
[7] Sinivasan R, Rao K R. Predictive Coding Based on Efficient Motion Estimation. IEEE Trans on Communications, 1985, COM-33:888～896
[8] Jain J R, Jain A K. Displacement measurement and its Application in Interframe Image Coding. IEEE Trans on Communication, 1981, COM-29:1799～1808
[9] Xu J B, Po L M, Cheung C K. Adaptive Motion Tracking Block Matching Algorithms for Video Coding. IEEE Trans on Circuits and System for Video Technology, 1999, 9(7): 1025～1029
[10] Jou J M, Chert P Y, Sun J M. The Gray Prediction Search Algorithm for Block Motion Estimation. IEEE Trans on Circuits and System for video Technology, 1999, 9(6) : 843～848
[11] Luo L J, Zou C R, Gao X Q, etal. A New Prediction Search Algorithm for Block Motion Estimation in Video Coding. IEEE Trans on Consumer Electronics, 1997, 43 (1): 56～60
[12] 沈兰荪，图像编码与异步传输。北京：人民邮电出版社，1998
[13] Castleman K R. Digital image processing. Prentice Hall, 1996
[14] Tekalp A M. Digital Video processing. Prentice Hall, 1995
[15] Song J X, Bi H J. Perceptual quality metric for compressed video. Proceedings of ICCT, 1998, 1: S16-02-1-S16-02-5
[16] Jia Z K, Cui H J, Tang K. Perceptual adaptive quantisation scheme for H. 263 video coder. Electronics Letters 2000, 36(17): 1454-1456
[17] Tian Dong, Shen Lansun, Yao Zhiheng. Motion Activity Based Wireless Video Quality Perceptual Metric. Proceedings of 2001 International Symposium on Intelligent Multimedia, Video & Speech Processing, Hong Kong, 2001
[18] Song Hwangjun, Kim Jong Won and Kuo C-C Jay. Real-time motion-based H. 263+ frame rate control. SPIE Visual Communication and Image Processing' 99, San Jose, USA, 1999
[19] Borko Furht, Joshua Greenberg, Raymond Westwater, Motion estimation algorithms for video compression. Boston: Kluwer Academic Publishers, 1997.
[20] Cheng-Chang Lien, Chung-Lin Huang, and Jhy-Gau Chen, "Complex-subband transform for subband-based motion estimation/compensation and coding," IEEE Trans. Image Processing vol. 6, pp. 694-702, May 1997.
[21] Robert W. Young and Nick G. Kingsbury,"Frequency-domain motion estimation using a complex lapped transform," IEEE Trans Image Processing, vol. 2, pp. 2-17, January 1993.
[22] H.S. Malver and D.H. Staelin, "The LOT: Transform coding without blocking effect," IEEE Trans. Acoust., Speech, Signal Processing vol. 37, pp. 553-559, Apr. 1989.
[23] Frederic Dufaux and Fabrice Moscheni, "Motion estimation technique for digital TV: a review and a new contribution," Proceedings of The IEEE, vol. 83, pp. 858-876, June 1995.
[24] Christoph Stiller and Janusz Konrad, "Estimating motion in image sequences," IEEE Signal Processing Magazine, pp. 70-90, July 1999.
[25] Rajesh Rajagopalan, Ephraim feig and Michael T. Orchard, "Motion optimization of ordered block motion compensation," IEEE Trans. Circuits and Systems for Video Technology, vol. 8, pp. 119-123, April 1998.
[26] Jonathan K. Su and Russell M. Mersereau, "Motion estimation methods for overlapped block motion compensation," IEEE Trans. Image Processing, vol. 9, pp. 1509-1521, Sept. 2000.
[27] M.T. Orchard and G.J. Sullivan. "Overlapped block motion compensation: An estimation-theoretic approach," IEEE Trans Image Processing vol. 3, pp. 693-699, Sept.1994.
[28] H. Watanabe and S. Singhal, "Windowed motion compensation," Proc. SPIE vol. 1605, pp.582-589, Nov. 1991.
[29] H.S. Malvar and D.H. Staelin, "Reduction of blocking effects in image coding with a lapped orthogonal transform," IEEE Proc. ICASSP, pp. 781-784, 1988.
[30] R. W. Young and N. G. Kingsbury, "Video compression using lapped transforms for motion estimation/compensation and coding," Opt. Eng., vol. 32, pp. 1451-1463, July 1993.
[31] Aisbett, "Optical flow with intensity-weighted smoothing," IEEE Trans Pattern anal. Machine intell., vol. 11, pp. 512-522, May 1989.
[32] M. Chang, A. Tekalp, and M. Sezan, "Simultaneous motion estimation and segmentation," IEEE Trans. Image Processing, vol. 6, pp. 1326-1333, Sept. 1997.
[33] V. Seferidis and M. Ghanbari, "General approach to block-matching motion estimation," Opt. Eng., vol. 32, no. 7, pp. 1464-1474, July 1993.
[34] D. J. Fleet and A. D. Jepson, "Computation of component image velocity from local phase information," Int. J. Computer Vision, vol. 5, pp. 77-104, 1990.
[35] D. LeGall, "MPEG: A video compression standard for multimedia," Commun. ACM, vol. 34, no. 4, pp. 47-58, Apr. 1991.
[36] ISO/IEC JTC1/SC29/WG11 Moving Picture Experts Group. MPEG2 test model 4,1993.
[37] D. LeGall, "The MPEG video compression algorithm," Signal Processing: Image Commun., vol. 4, no. 2, pp. 129-140, Apr. 1992.
[38] B. Liu and A. Zaccarin, "New fast algorithms for the extimation of block motion vectors," IEEE Trans Circ. And Sys. For Video Tech. Vol. CSVT-3, no. 2, pp. 148-157, Apr. 1993.
[39] Cafforio, C.,Rocca, F., "The differential method for image motion estimation," in Image Sequence Processing and Dynamic Scene Analysis, T. S. Huang, Ed,, Berlin, Germany, Spring-Verlag, 1983, 104.
[40] Ghanbari, M., "The Cross-search algorithm for motion estimation," IEEE Trans. Commun., 1990, 38(7): 950-953.
[41] Wang, Q., Clarke, R. J., "Motion estimation and conpensation for image sequence coding," Signal Processing: Image Communication, 1992, 4(2): 161-174.
[42] B. Liu and A. Zaccarin, "New fast algorithms for the estimation of block motion vectors," IEEE Trans. Circ. And Sys. Video Tech., vol. 3, no. 2, pp. 148-157, Apr. 1993.
[43] Y. Nakaya and H. Harashima, "Motion compensation based on spatial transformations," IEEE Trans. CAS Video Tech., vol. 4, pp. 339-356, June 1994.
[44] Y. M. Erkam, M. I. Sezan, and A. T. Erdem, "A hierarchical phase-correlation method for motion estimation," Proc. Conf on Info. Scien. and System, Baltimore MD, Mar. 1993, pp. 419-424.
[45] J. N. Driessen, L. Boroczky, and J. Biemond, "Pel-rescursive motion field estimation from image sequences," J. Vis. Comm. Image Rep., vol. 2, no. 3, pp. 259-280, 1991.
[46] Jianhua Lu and Ming L. Liou, "A simple and efficient search algorithm for block-matching motion estimation," IEEE Trans. On CSVT, vol. 7, no. 2, Apr. 1997, pp.429-433
[47] Mark R. Pickering, John F. Arnold and Michael R. Frater, "An adaptive search length algorithm for block matching motion estimation," IEEE Trans. On CSVT, vol. 7, no. 6, Dec. 1997, pp. 906-912.
[48] 邹博，张文军，余松煜，“相关块匹配运动估计算法，”上海交通大学学报，vol．31，no．5，1997．
[49] 吴镇扬，《数字信号处理的原理与实现》，东南大学出版社，1997。
[50] 王汇源，《数字图像通信原理与技术》，国防工业出版社，2000。
[51] 钟玉琢，王琪，贺玉文，《基于对象的多媒体数据压缩编码国际标准》，科学出版社，2000。
[52] 王耀南，李树涛，毛建旭，《计算机图像处理与识别技术》，高教教育出版社，2001。
[53] 余松煜，张文军，孙军，《现代图像信息压缩技术》，科学出版社，1998。
[54] 李素芝，万建伟，《时域离散信号处理》，国防科技大学出版社，1994。
[2] Kappagantula S, Rao K R. Motion compensated interframe image prediction. IFEE Trans on Communications. 1985, COM-33(10): 1011-1015
[3] Gharavi H, Mills M. Block matching motion estimation algorithms-new results. IEEE Trans on Circuits and Systems, 1990, 37(5):6 49～6 51
[4] LiR, Zeng B, Lieu M L. A new three-step search algorithm for block motion estimation. IEEE Trans on Circuits and Systems For Video Technology, 1994, 4(4):43 8～442
[5] Po L M, Ma W C. A novel four-step algorithm for fast block motion estimation. IEEE Trans on Circuits and Systems for Video Technology, 1996 , 6(3):313～317
[6] M. Chanbari, The cross-search algorithm for motion estimation. IEEE Trans on Communication. Vol. 38, No. 7, July 1990, pp950-953
[7] Sinivasan R, Rao K R. Predictive Coding Based on Efficient Motion Estimation. IEEE Trans on Communications, 1985, COM-33:888～896
[8] Jain J R, Jain A K. Displacement measurement and its Application in Interframe Image Coding. IEEE Trans on Communication, 1981, COM-29:1799～1808
[9] Xu J B, Po L M, Cheung C K. Adaptive Motion Tracking Block Matching Algorithms for Video Coding. IEEE Trans on Circuits and System for Video Technology, 1999, 9(7): 1025～1029
[10] Jou J M, Chert P Y, Sun J M. The Gray Prediction Search Algorithm for Block Motion Estimation. IEEE Trans on Circuits and System for video Technology, 1999, 9(6) : 843～848
[11] Luo L J, Zou C R, Gao X Q, etal. A New Prediction Search Algorithm for Block Motion Estimation in Video Coding. IEEE Trans on Consumer Electronics, 1997, 43 (1): 56～60
[12] 沈兰荪，图像编码与异步传输。北京：人民邮电出版社，1998
[13] Castleman K R. Digital image processing. Prentice Hall, 1996
[14] Tekalp A M. Digital Video processing. Prentice Hall, 1995
[15] Song J X, Bi H J. Perceptual quality metric for compressed video. Proceedings of ICCT, 1998, 1: S16-02-1-S16-02-5
[16] Jia Z K, Cui H J, Tang K. Perceptual adaptive quantisation scheme for H. 263 video coder. Electronics Letters 2000, 36(17): 1454-1456
[17] Tian Dong, Shen Lansun, Yao Zhiheng. Motion Activity Based Wireless Video Quality Perceptual Metric. Proceedings of 2001 International Symposium on Intelligent Multimedia, Video & Speech Processing, Hong Kong, 2001
[18] Song Hwangjun, Kim Jong Won and Kuo C-C Jay. Real-time motion-based H. 263+ frame rate control. SPIE Visual Communication and Image Processing' 99, San Jose, USA, 1999
[19] Borko Furht, Joshua Greenberg, Raymond Westwater, Motion estimation algorithms for video compression. Boston: Kluwer Academic Publishers, 1997.
[20] Cheng-Chang Lien, Chung-Lin Huang, and Jhy-Gau Chen, "Complex-subband transform for subband-based motion estimation/compensation and coding," IEEE Trans. Image Processing vol. 6, pp. 694-702, May 1997.
[21] Robert W. Young and Nick G. Kingsbury,"Frequency-domain motion estimation using a complex lapped transform," IEEE Trans Image Processing, vol. 2, pp. 2-17, January 1993.
[22] H.S. Malver and D.H. Staelin, "The LOT: Transform coding without blocking effect," IEEE Trans. Acoust., Speech, Signal Processing vol. 37, pp. 553-559, Apr. 1989.
[23] Frederic Dufaux and Fabrice Moscheni, "Motion estimation technique for digital TV: a review and a new contribution," Proceedings of The IEEE, vol. 83, pp. 858-876, June 1995.
[24] Christoph Stiller and Janusz Konrad, "Estimating motion in image sequences," IEEE Signal Processing Magazine, pp. 70-90, July 1999.
[25] Rajesh Rajagopalan, Ephraim feig and Michael T. Orchard, "Motion optimization of ordered block motion compensation," IEEE Trans. Circuits and Systems for Video Technology, vol. 8, pp. 119-123, April 1998.
[26] Jonathan K. Su and Russell M. Mersereau, "Motion estimation methods for overlapped block motion compensation," IEEE Trans. Image Processing, vol. 9, pp. 1509-1521, Sept. 2000.
[27] M.T. Orchard and G.J. Sullivan. "Overlapped block motion compensation: An estimation-theoretic approach," IEEE Trans Image Processing vol. 3, pp. 693-699, Sept.1994.
[28] H. Watanabe and S. Singhal, "Windowed motion compensation," Proc. SPIE vol. 1605, pp.582-589, Nov. 1991.
[29] H.S. Malvar and D.H. Staelin, "Reduction of blocking effects in image coding with a lapped orthogonal transform," IEEE Proc. ICASSP, pp. 781-784, 1988.
[30] R. W. Young and N. G. Kingsbury, "Video compression using lapped transforms for motion estimation/compensation and coding," Opt. Eng., vol. 32, pp. 1451-1463, July 1993.
[31] Aisbett, "Optical flow with intensity-weighted smoothing," IEEE Trans Pattern anal. Machine intell., vol. 11, pp. 512-522, May 1989.
[32] M. Chang, A. Tekalp, and M. Sezan, "Simultaneous motion estimation and segmentation," IEEE Trans. Image Processing, vol. 6, pp. 1326-1333, Sept. 1997.
[33] V. Seferidis and M. Ghanbari, "General approach to block-matching motion estimation," Opt. Eng., vol. 32, no. 7, pp. 1464-1474, July 1993.
[34] D. J. Fleet and A. D. Jepson, "Computation of component image velocity from local phase information," Int. J. Computer Vision, vol. 5, pp. 77-104, 1990.
[35] D. LeGall, "MPEG: A video compression standard for multimedia," Commun. ACM, vol. 34, no. 4, pp. 47-58, Apr. 1991.
[36] ISO/IEC JTC1/SC29/WG11 Moving Picture Experts Group. MPEG2 test model 4,1993.
[37] D. LeGall, "The MPEG video compression algorithm," Signal Processing: Image Commun., vol. 4, no. 2, pp. 129-140, Apr. 1992.
[38] B. Liu and A. Zaccarin, "New fast algorithms for the extimation of block motion vectors," IEEE Trans Circ. And Sys. For Video Tech. Vol. CSVT-3, no. 2, pp. 148-157, Apr. 1993.
[39] Cafforio, C.,Rocca, F., "The differential method for image motion estimation," in Image Sequence Processing and Dynamic Scene Analysis, T. S. Huang, Ed,, Berlin, Germany, Spring-Verlag, 1983, 104.
[40] Ghanbari, M., "The Cross-search algorithm for motion estimation," IEEE Trans. Commun., 1990, 38(7): 950-953.
[41] Wang, Q., Clarke, R. J., "Motion estimation and conpensation for image sequence coding," Signal Processing: Image Communication, 1992, 4(2): 161-174.
[42] B. Liu and A. Zaccarin, "New fast algorithms for the estimation of block motion vectors," IEEE Trans. Circ. And Sys. Video Tech., vol. 3, no. 2, pp. 148-157, Apr. 1993.
[43] Y. Nakaya and H. Harashima, "Motion compensation based on spatial transformations," IEEE Trans. CAS Video Tech., vol. 4, pp. 339-356, June 1994.
[44] Y. M. Erkam, M. I. Sezan, and A. T. Erdem, "A hierarchical phase-correlation method for motion estimation," Proc. Conf on Info. Scien. and System, Baltimore MD, Mar. 1993, pp. 419-424.
[45] J. N. Driessen, L. Boroczky, and J. Biemond, "Pel-rescursive motion field estimation from image sequences," J. Vis. Comm. Image Rep., vol. 2, no. 3, pp. 259-280, 1991.
[46] Jianhua Lu and Ming L. Liou, "A simple and efficient search algorithm for block-matching motion estimation," IEEE Trans. On CSVT, vol. 7, no. 2, Apr. 1997, pp.429-433
[47] Mark R. Pickering, John F. Arnold and Michael R. Frater, "An adaptive search length algorithm for block matching motion estimation," IEEE Trans. On CSVT, vol. 7, no. 6, Dec. 1997, pp. 906-912.
[48] 邹博，张文军，余松煜，“相关块匹配运动估计算法，”上海交通大学学报，vol．31，no．5，1997．
[49] 吴镇扬，《数字信号处理的原理与实现》，东南大学出版社，1997。
[50] 王汇源，《数字图像通信原理与技术》，国防工业出版社，2000。
[51] 钟玉琢，王琪，贺玉文，《基于对象的多媒体数据压缩编码国际标准》，科学出版社，2000。
[52] 王耀南，李树涛，毛建旭，《计算机图像处理与识别技术》，高教教育出版社，2001。
[53] 余松煜，张文军，孙军，《现代图像信息压缩技术》，科学出版社，1998。
[54] 李素芝，万建伟，《时域离散信号处理》，国防科技大学出版社，1994。