基于可变形块匹配的运动估计与补偿
|
摘要
本文主要讨论基于可变形块匹配(DBMA)的运动估计与补偿,用以减小传统方块匹配算法(BMA)的预测误差,提高帧间运动估计的准确性,实现对非平移运动的预测。提出了基于节点搜索的可变形块匹配算法(NS-DBMA),并在此基础上提出几个优化方法,进一步降低运算量和提高预测质量,弥补了BMA的不足。
本文首先介绍视频压缩编码的系统结构,分析运动估计与补偿的基本原理与重要作用;介绍BMA的发展和几种有代表性的快速算法,分析快速BMA的共同特点并对加快匹配速度的方法进行总结。然后分析视频信号的实际属性,从根本上解释了BMA所采用的平移模型的缺陷,提出了适合实际运动特性的基于节点位移的可变形块运动模型。为了实现此模型的运动估计,首先介绍基于梯度的可变形块匹配算法(GB-DBMA),并指出GB-DBMA的预测精度和运算量都达不到实际应用的要求;进而提出NS-DBMA,它能有效提高预测精度,并降低运算量,有效地预测帧间非平移运动。在NS-DBMA的基础上,进一步提出了计算过程的优化方法、结合BMA和DBMA的双模式混合估计方法、在预测质量足够好时结束搜索的适可而止估计方法、使用简化点阵的交叉搜索算法和提高预测质量的分数像素精度预测算法,使DBMA更加适合实际应用的要求。
测试结果表明,NS-DBMA的运算量仅为GB-DBMA的一半,而预测质量平均提高0.71dB,能得到更好的主客观预测质量,且更易于硬件实现;综合各种改进方法的DBMA的运算量只相当于全搜索法BMA的42%,而预测质量平均提高1.53dB,可以替代BMA应用在实际视频压缩系统中。
Motion estimation and compensation using deformable block matching algorithm (DBMA) is discussed. DBMA is developed to reduce the prediction error of traditional block matching algorithm (BMA), that is, to increase the accuracy of motion estimation and to estimate the nontranslational motion. Here we propose a Nodal-search based DBMA. Some ameliorative methods are further proposed, which can alleviate the computation and improve the quality more effectively.
This thesis first describes the video compression system to indicate the importance of motion estimation and compensation. Then the famous BMA and some typical fast algorithms are introduced. Finally some fundamental characteristics of fast BMAs are summarized. By analyzing the property of real video sequence, the translational model adopted by BMA is demonstrated to be inaccurate in the interframe prediction, and a nodal-displacement-based deformation model is proposed. To estimate the nodal displacements, we developed a nodal search-based algorithm (NS-DBMA), which has lower computation and better performance than original gradient-based algorithm (GB-DBMA). Some improved methods are further proposed, such as the two-mode hybrid method which combines BMA and DBMA, the auto-terminate method which stops searching when the prediction is good enough, the cross-search method which uses simple search pattern, the sub-pixel accuracy prediction which denotes motion more accurately and computing optimization method.
Experimental results show that the basic NS-DBMA has only half computation of GB-DBMA but gets better subjective and objective quality, and is much easier to implement by VLSI. The most effective method, which synthesizes all ameliorative methods, has only 42% computation of the Full Search while outperforms 1.53dB. It could be used as a substitute for BMA in real coding system.
本文首先介绍视频压缩编码的系统结构,分析运动估计与补偿的基本原理与重要作用;介绍BMA的发展和几种有代表性的快速算法,分析快速BMA的共同特点并对加快匹配速度的方法进行总结。然后分析视频信号的实际属性,从根本上解释了BMA所采用的平移模型的缺陷,提出了适合实际运动特性的基于节点位移的可变形块运动模型。为了实现此模型的运动估计,首先介绍基于梯度的可变形块匹配算法(GB-DBMA),并指出GB-DBMA的预测精度和运算量都达不到实际应用的要求;进而提出NS-DBMA,它能有效提高预测精度,并降低运算量,有效地预测帧间非平移运动。在NS-DBMA的基础上,进一步提出了计算过程的优化方法、结合BMA和DBMA的双模式混合估计方法、在预测质量足够好时结束搜索的适可而止估计方法、使用简化点阵的交叉搜索算法和提高预测质量的分数像素精度预测算法,使DBMA更加适合实际应用的要求。
测试结果表明,NS-DBMA的运算量仅为GB-DBMA的一半,而预测质量平均提高0.71dB,能得到更好的主客观预测质量,且更易于硬件实现;综合各种改进方法的DBMA的运算量只相当于全搜索法BMA的42%,而预测质量平均提高1.53dB,可以替代BMA应用在实际视频压缩系统中。
Motion estimation and compensation using deformable block matching algorithm (DBMA) is discussed. DBMA is developed to reduce the prediction error of traditional block matching algorithm (BMA), that is, to increase the accuracy of motion estimation and to estimate the nontranslational motion. Here we propose a Nodal-search based DBMA. Some ameliorative methods are further proposed, which can alleviate the computation and improve the quality more effectively.
This thesis first describes the video compression system to indicate the importance of motion estimation and compensation. Then the famous BMA and some typical fast algorithms are introduced. Finally some fundamental characteristics of fast BMAs are summarized. By analyzing the property of real video sequence, the translational model adopted by BMA is demonstrated to be inaccurate in the interframe prediction, and a nodal-displacement-based deformation model is proposed. To estimate the nodal displacements, we developed a nodal search-based algorithm (NS-DBMA), which has lower computation and better performance than original gradient-based algorithm (GB-DBMA). Some improved methods are further proposed, such as the two-mode hybrid method which combines BMA and DBMA, the auto-terminate method which stops searching when the prediction is good enough, the cross-search method which uses simple search pattern, the sub-pixel accuracy prediction which denotes motion more accurately and computing optimization method.
Experimental results show that the basic NS-DBMA has only half computation of GB-DBMA but gets better subjective and objective quality, and is much easier to implement by VLSI. The most effective method, which synthesizes all ameliorative methods, has only 42% computation of the Full Search while outperforms 1.53dB. It could be used as a substitute for BMA in real coding system.
引文
[1] ISO/IEC JTC1/SC29 11172-2: MPEG-1, International standard for coding of moving pictures and associated audio for digital storage media at up to about 1.5Mbit/s, 1991.
[2] ISO/IEC JTC1/SC29 13818-2: MPEG-2, International standard for coding of moving pictures and associated audio information: video. 1996.
[3] The MPEG-4 specification, ISO/IEC 14496-1: 2001.
[4] CCITT Rec. H.261, Video coding for audio visual services at p*64Kbit/s, 1990.
[5] ITU-T Rec. H.263(draft), Video coding for low bit rate communication, 1997.
[6] ITU-T Rec. H.264/ISO/IEC 11496-10, “Advanced video coding”, Final committee draft.
[7] Yao Wang. 视频处理与通信[M]. 侯正信等译. 北京:电子工业出版社,2003.
[8] Stiller, C., and J. Konrad. Estimation motion in image sequences. IEEE signal processing Magazine (July 1999). 16:70-91).
[9] Wang Y., and O. Lee. Active mesh-a feature seeking and tracking image sequence representation scheme. IEEE Trans. Image Process. (Sept. 1994), 3:610-24.
[10] Altunbasak, Y., and A.M. Tekalp. Closed-form connectivity-preserving solutions for motion compensation using 2D meshes. IEEE Trans. Image Process. (Sept. 1997), 6:1255-1269.
[11] Altunbasak, Y., and A.M. Tekalp. Occlusion-adaptive, content-based mesh design and forward tracking. IEEE Trans. Image Process. (Sept. 1997), 6:1270-80.
[12] Duda, R. O., and P.E. Hart. Pattern Classification and Scene Analysis. New York: John Wiley & Sons, 1973.
[13] Wang, Y., X.-M. Hsieh, J.H. Hu, and O. Lee. Region segmentation based on active mesh representation of motion: comparison of parallel and sequential approaches. IEEE Int. Conf. on Image Proc.(ICIP’95)(Oct. 1995),185-88, Washington, DC.
[14] Hsu, S., P. Anandan, and S.Peleg. Accurate computation of optical flow using layered motion representations. In IEEE Int. Conf. Patt. Recog.(Oct. 1994), 743-46, Jerusalem, Israel.
[15] Wiegand, T., M. Lightstone, D. Mukherjee, T. Campell and S.K. Mitra. Rate-distortion optimized mode selection for very low bit rate video coding and the emerging H.263 standard. IEEE Trans. Circuits Syst. For Video Technology (April 1996), 6(2): 182-90.
[16] Xiaoming Li and Cesar Gonzales. A locally quadratic model of the motion estimation error criterion function and its application to subpixel interpolations. IEEE Trans. Circuits and Sys. for Video Tech. Vol.6, NO.1, pp:118-122. Feb.1996.
[17] Bierling, M., Displacement estimation by hierarchical block matching. In SPIE Conf., Visual Comm. Image Processing (Nov. 1998), SPIE-1001: 942-951.
[18] Iain E.G. Richardson. H.264 and MPEG-4 Video Compression for next generation multimedia. John Wiley & Sons, 2003.
[19] Komarek, T. and P. Pirsch. Array architecture for block matching algorithms. IEEE Trans. Circuits and Systems, 36: 269-277. Oct. 1989.
[20] P. Pirsch, N. Demassieux and W. Gehrke. VLSI architecture for video compression-a survey. Proceedings of the IEEE. Vol 83, NO.2. pp:220-246. Feb.1995.
[21] T.Koga, K.Iinuma, A.Hirano, Y.Iijima and T.Ishiguro. Motion compensated interframe coding for video confere- ncing[J]. in Proc.NTC81, New Orleans, LA. Nov. 1981. pp.C9.6.1-9.6.5.
[22] S. Zhu and K.K. Ma. A new diamond search algorithm for fast block-matching motion estimation[J]. IEEE Trans. Image proc., vol.9, no.2, pp.287-290. Feb. 2000.
[23] A.M. Tourapis, O.C. Au and M.L. Liou. Highly efficient prediction zonal algorithm for fast block-matching motion estimation[J]. IEEE Trans. Circuits Syst. Video Technol., vol.12, no.10, pp.934-947. Oct. 2002.
[24] R. Srinivasan and K.R. Rao. Predictive coding based on efficient motion estimation[J]. IEEE Trans. Commun., vol.COM-33, pp.1011-1015, July 1985.
[25] J.R. Jain and A.K. Jain. Displacement measurement and its application in interframe image coding[J]. IEEE Trans. Commun., vol.COM-29, pp.1799-1808, Dec. 1981.
[26] R. Li, B. Zeng and M.L. Liou. A new three-step search algorithm for block motion estimation[J]. IEEE Trans. Circuits Syst. Video Technol., vol.4, no.4, Aug. 1994.
[27] L.K. Liu and E.Feig. A block-based gradient descent search algorithm for block motion estimation in video coding[J]. IEEE Trans. Circuits Syst. Video Technol., vol.6, no.4, pp.419-422. Aug. 1996.
[28] L.J. Luo, C.R. Zou X.Q. Gao and Z.Y He. A new prediction search algorithm for block motion estimation in video coding[J]. IEEE Trans. Cons. Elec, vol,43, no.1, pp.56-61. Feb. 1997.
[29] Ismaeil I., Docef A., Kossentini F. and Ward, R. Efficient motion estimation using spatial and temporal motion vector prediction[A]. Image Processing, 1999. ICIP 99. Proceedings, vol.1, pp.70-74.
[30] P.I. Hosur and K.K. Ma. Motion vector field adaptive fast motion estimation[A]. Proc. 2nd Int. Conf. Information, Communications and Signal Processing(ICICS’99), Singapore, Dec. 7-10, 1999.
[31] J.B. Xu L.M. Po and C.K. Cheung. Adaptive motion tracking block matching algorithm for video coding[J]. IEEE Trans. Circuits Syst. Video Technol., vol.9, no.7, pp.1025-1029. Oct. 1999.
[32] Mann, S. and R.W. Picard. Video orbits of the projective group: A simple approach to featureless estimation of parameters. IEEE Trans. Image Process.(Sept. 1997), 6:1281-95.
[33] Nogaki, S. and M. Ohta. An overlapped block motion compensation for high quality motion picture coding. IEEE Int. Conf. Circuits and Systems (May 1992), 184-187.
[34] Orchard, M. T. and G. J. Sullivan. Overlapped block motion compensation: An estimation-theoretic approach. IEEE Trans. Image Process. (1994), 3:693-99.
[35] Girod, B. Motion compensation: Visual aspects, accuracy and fundamental limits. In M. I. Sezan and R. L. Lagendijk, eds., Motion Analysis and Image Sequence Processing, Boston: Kluwer Academic Publishers, 1993, 126-52.
[36] Lee,O. and Y.Wang. Motion-compensated prediction using nodal based deformable block matching[J]. Journal of Visual Communications and Image Representation (March 1995). 6:26-34.
[37] O.C.Zienkewicz and R.L.Taylor. The Finite Element Method[M]. Prentice-Hall, Englewood Cliffs, NJ, 1989.
[38] P.E. Gill et al. Practical Optimization[M]. Academic Press, New York, 1981.
[39] Lee,O. and Y.Wang. A deformable block matching algorithm for motion-compensated prediction[C]. Proceedings of Picture Coding Symposium, Sacramento.CA. Sept. 1994. pp. 223-226.
[40] 数字图像处理(第二版),(美)冈萨雷斯(Gonzalez, R.C.)等著;阮秋琦等译-北京: 电子工业出版社, 2003.3.
[41] E. Knuth, Searching and Sorting, Vol. 3. The Art of Computer Programming. Reading, MA; Addison-Wesley, 1973.
[42] Jaswant R. Jain and Anil K. Jain, Displacement Measurement and Its Application in Interframe Image Coding, IEEE Trans. Commun, Vol.COM -29,NO.12. pp.1799-1808, Dec.1981.
[43] M.GHANBARI. The cross-search algorithm for motion estimation. IEEE Trans. Commun. Vol.38, NO.7, pp:950-953. July 1990.
[2] ISO/IEC JTC1/SC29 13818-2: MPEG-2, International standard for coding of moving pictures and associated audio information: video. 1996.
[3] The MPEG-4 specification, ISO/IEC 14496-1: 2001.
[4] CCITT Rec. H.261, Video coding for audio visual services at p*64Kbit/s, 1990.
[5] ITU-T Rec. H.263(draft), Video coding for low bit rate communication, 1997.
[6] ITU-T Rec. H.264/ISO/IEC 11496-10, “Advanced video coding”, Final committee draft.
[7] Yao Wang. 视频处理与通信[M]. 侯正信等译. 北京:电子工业出版社,2003.
[8] Stiller, C., and J. Konrad. Estimation motion in image sequences. IEEE signal processing Magazine (July 1999). 16:70-91).
[9] Wang Y., and O. Lee. Active mesh-a feature seeking and tracking image sequence representation scheme. IEEE Trans. Image Process. (Sept. 1994), 3:610-24.
[10] Altunbasak, Y., and A.M. Tekalp. Closed-form connectivity-preserving solutions for motion compensation using 2D meshes. IEEE Trans. Image Process. (Sept. 1997), 6:1255-1269.
[11] Altunbasak, Y., and A.M. Tekalp. Occlusion-adaptive, content-based mesh design and forward tracking. IEEE Trans. Image Process. (Sept. 1997), 6:1270-80.
[12] Duda, R. O., and P.E. Hart. Pattern Classification and Scene Analysis. New York: John Wiley & Sons, 1973.
[13] Wang, Y., X.-M. Hsieh, J.H. Hu, and O. Lee. Region segmentation based on active mesh representation of motion: comparison of parallel and sequential approaches. IEEE Int. Conf. on Image Proc.(ICIP’95)(Oct. 1995),185-88, Washington, DC.
[14] Hsu, S., P. Anandan, and S.Peleg. Accurate computation of optical flow using layered motion representations. In IEEE Int. Conf. Patt. Recog.(Oct. 1994), 743-46, Jerusalem, Israel.
[15] Wiegand, T., M. Lightstone, D. Mukherjee, T. Campell and S.K. Mitra. Rate-distortion optimized mode selection for very low bit rate video coding and the emerging H.263 standard. IEEE Trans. Circuits Syst. For Video Technology (April 1996), 6(2): 182-90.
[16] Xiaoming Li and Cesar Gonzales. A locally quadratic model of the motion estimation error criterion function and its application to subpixel interpolations. IEEE Trans. Circuits and Sys. for Video Tech. Vol.6, NO.1, pp:118-122. Feb.1996.
[17] Bierling, M., Displacement estimation by hierarchical block matching. In SPIE Conf., Visual Comm. Image Processing (Nov. 1998), SPIE-1001: 942-951.
[18] Iain E.G. Richardson. H.264 and MPEG-4 Video Compression for next generation multimedia. John Wiley & Sons, 2003.
[19] Komarek, T. and P. Pirsch. Array architecture for block matching algorithms. IEEE Trans. Circuits and Systems, 36: 269-277. Oct. 1989.
[20] P. Pirsch, N. Demassieux and W. Gehrke. VLSI architecture for video compression-a survey. Proceedings of the IEEE. Vol 83, NO.2. pp:220-246. Feb.1995.
[21] T.Koga, K.Iinuma, A.Hirano, Y.Iijima and T.Ishiguro. Motion compensated interframe coding for video confere- ncing[J]. in Proc.NTC81, New Orleans, LA. Nov. 1981. pp.C9.6.1-9.6.5.
[22] S. Zhu and K.K. Ma. A new diamond search algorithm for fast block-matching motion estimation[J]. IEEE Trans. Image proc., vol.9, no.2, pp.287-290. Feb. 2000.
[23] A.M. Tourapis, O.C. Au and M.L. Liou. Highly efficient prediction zonal algorithm for fast block-matching motion estimation[J]. IEEE Trans. Circuits Syst. Video Technol., vol.12, no.10, pp.934-947. Oct. 2002.
[24] R. Srinivasan and K.R. Rao. Predictive coding based on efficient motion estimation[J]. IEEE Trans. Commun., vol.COM-33, pp.1011-1015, July 1985.
[25] J.R. Jain and A.K. Jain. Displacement measurement and its application in interframe image coding[J]. IEEE Trans. Commun., vol.COM-29, pp.1799-1808, Dec. 1981.
[26] R. Li, B. Zeng and M.L. Liou. A new three-step search algorithm for block motion estimation[J]. IEEE Trans. Circuits Syst. Video Technol., vol.4, no.4, Aug. 1994.
[27] L.K. Liu and E.Feig. A block-based gradient descent search algorithm for block motion estimation in video coding[J]. IEEE Trans. Circuits Syst. Video Technol., vol.6, no.4, pp.419-422. Aug. 1996.
[28] L.J. Luo, C.R. Zou X.Q. Gao and Z.Y He. A new prediction search algorithm for block motion estimation in video coding[J]. IEEE Trans. Cons. Elec, vol,43, no.1, pp.56-61. Feb. 1997.
[29] Ismaeil I., Docef A., Kossentini F. and Ward, R. Efficient motion estimation using spatial and temporal motion vector prediction[A]. Image Processing, 1999. ICIP 99. Proceedings, vol.1, pp.70-74.
[30] P.I. Hosur and K.K. Ma. Motion vector field adaptive fast motion estimation[A]. Proc. 2nd Int. Conf. Information, Communications and Signal Processing(ICICS’99), Singapore, Dec. 7-10, 1999.
[31] J.B. Xu L.M. Po and C.K. Cheung. Adaptive motion tracking block matching algorithm for video coding[J]. IEEE Trans. Circuits Syst. Video Technol., vol.9, no.7, pp.1025-1029. Oct. 1999.
[32] Mann, S. and R.W. Picard. Video orbits of the projective group: A simple approach to featureless estimation of parameters. IEEE Trans. Image Process.(Sept. 1997), 6:1281-95.
[33] Nogaki, S. and M. Ohta. An overlapped block motion compensation for high quality motion picture coding. IEEE Int. Conf. Circuits and Systems (May 1992), 184-187.
[34] Orchard, M. T. and G. J. Sullivan. Overlapped block motion compensation: An estimation-theoretic approach. IEEE Trans. Image Process. (1994), 3:693-99.
[35] Girod, B. Motion compensation: Visual aspects, accuracy and fundamental limits. In M. I. Sezan and R. L. Lagendijk, eds., Motion Analysis and Image Sequence Processing, Boston: Kluwer Academic Publishers, 1993, 126-52.
[36] Lee,O. and Y.Wang. Motion-compensated prediction using nodal based deformable block matching[J]. Journal of Visual Communications and Image Representation (March 1995). 6:26-34.
[37] O.C.Zienkewicz and R.L.Taylor. The Finite Element Method[M]. Prentice-Hall, Englewood Cliffs, NJ, 1989.
[38] P.E. Gill et al. Practical Optimization[M]. Academic Press, New York, 1981.
[39] Lee,O. and Y.Wang. A deformable block matching algorithm for motion-compensated prediction[C]. Proceedings of Picture Coding Symposium, Sacramento.CA. Sept. 1994. pp. 223-226.
[40] 数字图像处理(第二版),(美)冈萨雷斯(Gonzalez, R.C.)等著;阮秋琦等译-北京: 电子工业出版社, 2003.3.
[41] E. Knuth, Searching and Sorting, Vol. 3. The Art of Computer Programming. Reading, MA; Addison-Wesley, 1973.
[42] Jaswant R. Jain and Anil K. Jain, Displacement Measurement and Its Application in Interframe Image Coding, IEEE Trans. Commun, Vol.COM -29,NO.12. pp.1799-1808, Dec.1981.
[43] M.GHANBARI. The cross-search algorithm for motion estimation. IEEE Trans. Commun. Vol.38, NO.7, pp:950-953. July 1990.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |