基于冗余小波变换的运动估计算法研究
|
摘要
传统的视频编码标准均采用基于块的空间域运动估计技术来减少视频帧的时间冗余。由于小波变换在静态图像编码应用中的优良特性,基于小波变换的运动估计技术也成为了近来研究的热点。然而,离散小波变换具有移变性,这使得在小波域里难以获得精确的运动估计与补偿效果。冗余小波变换克服了小波变换的移变性,在冗余小波域进行运动估计可以达到很好的效果,但是算法的计算复杂度过高。
本文主要研究基于冗余小波变换的运动估计算法。由于在冗余小波域进行运动估计计算复杂度高,因此,本文在分析视频序列的运动特性和已有的运动估计算法的基础上,利用冗余小波变换的特性,提出了一种基于冗余小波变换的快速多分辨率运动估计算法。此方法首先在冗余小波域提取潜在运动块并对图像块进行运动剧烈程度划分,在此基础上对不同类型的图像块采取不同的搜索策略,从而有效减少了运动估计过程中不必要的搜索。另外,本文将可变块多分辨率运动估计的思想引入冗余小波域,运动估计的过程首先在低频子带进行,之后在高频子带以较小的搜索范围细化运动矢量。此方法在估计精度和计算复杂度上取得了较好均衡,解决了现有的基于冗余小波变换的运动估计算法中存在的计算复杂度过高的问题。
试验结果表明,本文方法较经典的基于冗余小波变换的运动估计算法在估计精度以及计算复杂度方面都具有优势。
Block-based motion estimation in the spatial domain is widely employed in modern video compression systems. However, given the promising performance of wavelet-based still-image compression algorithms, now one hot spot in the research of video codec is the motion estimation algorithm based on the Discrete Wavelet Transform (DWT). However, the fact that the usual critically sampled DWT is shift variant greatly hinders the motion estimation process when deployed in the wavelet domain. Because the Redundant Discrete Wavelet Transform (RDWT) is shift invariant, the motion estimation algorithms in the redundant wavelet domain have good performance, but very high computational complexity.
This paper mainly researches on the RDWT-based motion estimation algorithms. Because of the high computational complexity of such algorithms, so based on the analysis of the motion characters of video sequences and the existing motion estimation algorithms, utilizing the characteristic of RDWT, this paper proposes a fast multi-resolution motion estimation algorithm based on the RDWT. Firstly, this method by identifying the potential motion blocks and dividing the blocks into different degrees of motion in the RDWT domain takes different search schemes to blocks of different types, so the search area is decreased efficiently. In addition, this paper introduces the multi-resolution motion estimation into the redundant wavelet domain. Motion estimation first happens in the low-band, and then the motion vectors are refined in the high-band with a smaller search area. This motion estimation algorithm gets a tradeoff between the precision and the computational complexity, and overcomes the high computational complexity of the existing RDWT-based motion estimation algorithms.
The experimental results prove that this approach has a superior performance compared with the traditional method in terms of the precision and the computational complexity.
本文主要研究基于冗余小波变换的运动估计算法。由于在冗余小波域进行运动估计计算复杂度高,因此,本文在分析视频序列的运动特性和已有的运动估计算法的基础上,利用冗余小波变换的特性,提出了一种基于冗余小波变换的快速多分辨率运动估计算法。此方法首先在冗余小波域提取潜在运动块并对图像块进行运动剧烈程度划分,在此基础上对不同类型的图像块采取不同的搜索策略,从而有效减少了运动估计过程中不必要的搜索。另外,本文将可变块多分辨率运动估计的思想引入冗余小波域,运动估计的过程首先在低频子带进行,之后在高频子带以较小的搜索范围细化运动矢量。此方法在估计精度和计算复杂度上取得了较好均衡,解决了现有的基于冗余小波变换的运动估计算法中存在的计算复杂度过高的问题。
试验结果表明,本文方法较经典的基于冗余小波变换的运动估计算法在估计精度以及计算复杂度方面都具有优势。
Block-based motion estimation in the spatial domain is widely employed in modern video compression systems. However, given the promising performance of wavelet-based still-image compression algorithms, now one hot spot in the research of video codec is the motion estimation algorithm based on the Discrete Wavelet Transform (DWT). However, the fact that the usual critically sampled DWT is shift variant greatly hinders the motion estimation process when deployed in the wavelet domain. Because the Redundant Discrete Wavelet Transform (RDWT) is shift invariant, the motion estimation algorithms in the redundant wavelet domain have good performance, but very high computational complexity.
This paper mainly researches on the RDWT-based motion estimation algorithms. Because of the high computational complexity of such algorithms, so based on the analysis of the motion characters of video sequences and the existing motion estimation algorithms, utilizing the characteristic of RDWT, this paper proposes a fast multi-resolution motion estimation algorithm based on the RDWT. Firstly, this method by identifying the potential motion blocks and dividing the blocks into different degrees of motion in the RDWT domain takes different search schemes to blocks of different types, so the search area is decreased efficiently. In addition, this paper introduces the multi-resolution motion estimation into the redundant wavelet domain. Motion estimation first happens in the low-band, and then the motion vectors are refined in the high-band with a smaller search area. This motion estimation algorithm gets a tradeoff between the precision and the computational complexity, and overcomes the high computational complexity of the existing RDWT-based motion estimation algorithms.
The experimental results prove that this approach has a superior performance compared with the traditional method in terms of the precision and the computational complexity.
引文
[1] Iain E G Richardson. H.264 和 MPEG-4 视频压缩:新一代多媒体的视频编码技术[M].欧阳合,韩军译.长沙:国防科技大学出版社,2004.26～85.
[2] 宋传鸣,王相海.小波域视频运动估计研究进展[J].计算机学报,2005,28(10):1716～1727.
[3] H W Park,H S Kim. Motion estimation using low-band-shift method for wavelet-based moving-picture coding[J]. IEEE Transactions on Image Processing,2000,9(4):577～587.
[4] Y Andreopoulos,A Munteanu,G Van der Auwera,et al. Scalable wavelet video-coding with in-band prediction implementation and experimental results[C]. In:Proceedings of the International Conference on Image Processing,Rochester,NY,2002,3:729～732.
[5] Cui Suxia,Wang Yonghui,and Fowler J E. Mesh-based motion estimation and compensation in the wavelet domain using a redundant transform[C]. In:Proceedings of the International Conference on Image Processing,Rochester,NY,2002,1:693～696.
[6] Cui Suxia. Motion estimation and compensation in the redundant wavelet domain[D]. Mississippi State,Mississippi,USA: Mississippi State University,2003.
[7] Cui Suxia,Wang Yonghui,and Fowler J E. Multihypothesis motion compensation in the redundant wavelet domain[C]. In:Proceedings of the International Conference on Image Processing,Barcelona,Spain,2003,2:53～56.
[8] Rafael C Gonzalez,Richard E Woods.数字图像处理[M].阮秋琦,阮宇智译.北京:电子工业出版社,2003.276～322.
[9] Zhang Yaqin,Sohail Zafar. Motion-compensated wavelet transform coding for color video compression[J]. IEEE Transactions on Circuits and Systems for Video Technology,1992,2(3):285～296.
[10] Wei Jie,Li Zenian. An enhancement to MRMC scheme in video compression[J]. IEEE Transactions On Circuits and Systems for Video Technology,1997,7(3):564～568.
[11] Zhao Tingrong,Tatsuo Ohtsuki. A fast MRME scheme for video compression based on coefficients masking in the wavelet domain[C]. In:Proceedings of the IEEE Region 10 Conference,Cheju Island,South Korea,1999,1:127～130.
[12] 许洁斌,韦岗,布礼文.一种基于形态变换的小波分解运动补偿编码新算法[J].中国图象图形学报,1998,3(9):727～733.
[13] 刘红梅,黄金科,肖自美,等.基于区域分割的小波分解运动补偿编码算法[J].中国图象图形学报,2002,7(A)(3):292～296.
[14] 于立柱.基于模型的小波域的视频压缩编码[D].大连:大连理工大学,2004.
[15] 尚艳霞.基于小波域的视频压缩编码硕士学位论文[D].大连:大连理工大学,2003.
[16] 张磊,涂国防.一种新型小波域运动估计算法[J].电子与信息学报,2007,29(5):1131～1135.
[17] 宋传鸣,王相海.一种新的小波域视频可分级运动估计方案[J].计算机学报,2006,29(12):2112～2118.
[18] 王兵,赵荣椿,程英蕾.一种基于小波域的运动估计方法[J].电子与信息学报,2005,27(5):757～761.
[19] 王光学,曹长修,王健,孙光宇.小波域中几种块匹配运动估计的比较研究[J].计算机工程与设计,1999,20(6):10～13.
[20] 龚涛,丁润涛.基于小波变换的块匹配运动估计方法.天津大学学报[J],2003,36(3):320～324.
[21] 张郑擎.基于小波变换的图象/视频压缩编码及其数字水印嵌入方法的研究[D].上海:上海大学,2001.
[22] 张文琴.先进的小波视频压缩方法及其应用研究[D].北京:中国科学院研究生院,2005.
[23] 房胜,田淑珍,梁永全,等.RDWT 域全相位子带运动补偿视频编码方法[J].小型微型计算机系统,2006,27(4):762～765.
[24] 房胜,梁永全,钟玉琢.一种基于小波域规则三角形网格运动补偿的可扩展视频编码方法[J].中国图象图形学报,2007,12(1):21～26.
[25] 房胜,梁永全,钟玉琢.一种小波域三角形网格运动补偿方法[J].计算机学报,2005,28(12):2089～2095.
[26] 房胜, 钟玉琢.用于视频编码的小波域三角形网格构造方法[J].计算机辅助设计与图形学学报,2005,17(8):1656～1661.
[27] 潘健,汪一鸣.冗余小波域内的多分辨率运动估计[J].苏州大学学报(工科版),2006,26(3):61～64.
[28] 曲昕.基于网格模型的运动补偿算法的研究[D].天津:河北工业大学,2006.
[29] 贺文伟.视频编码中运动估计算法的研究[D].济南:山东大学,2006.
[30] 郭华南.基于小波变换的视频压缩技术[D].天津:天津大学,2004.
[31] 王拯洲.基于小波的视频压缩算法在视频会议中的应用[D].西安:西北工业大学,2007.
[32] Nakaya Y, Harashima H. Motion Compensation Based on Spatial Transformation[J]. IEEE Transactions on Circuits and Systems for Video Technology,1994,4(3):339～356.
[2] 宋传鸣,王相海.小波域视频运动估计研究进展[J].计算机学报,2005,28(10):1716～1727.
[3] H W Park,H S Kim. Motion estimation using low-band-shift method for wavelet-based moving-picture coding[J]. IEEE Transactions on Image Processing,2000,9(4):577～587.
[4] Y Andreopoulos,A Munteanu,G Van der Auwera,et al. Scalable wavelet video-coding with in-band prediction implementation and experimental results[C]. In:Proceedings of the International Conference on Image Processing,Rochester,NY,2002,3:729～732.
[5] Cui Suxia,Wang Yonghui,and Fowler J E. Mesh-based motion estimation and compensation in the wavelet domain using a redundant transform[C]. In:Proceedings of the International Conference on Image Processing,Rochester,NY,2002,1:693～696.
[6] Cui Suxia. Motion estimation and compensation in the redundant wavelet domain[D]. Mississippi State,Mississippi,USA: Mississippi State University,2003.
[7] Cui Suxia,Wang Yonghui,and Fowler J E. Multihypothesis motion compensation in the redundant wavelet domain[C]. In:Proceedings of the International Conference on Image Processing,Barcelona,Spain,2003,2:53～56.
[8] Rafael C Gonzalez,Richard E Woods.数字图像处理[M].阮秋琦,阮宇智译.北京:电子工业出版社,2003.276～322.
[9] Zhang Yaqin,Sohail Zafar. Motion-compensated wavelet transform coding for color video compression[J]. IEEE Transactions on Circuits and Systems for Video Technology,1992,2(3):285～296.
[10] Wei Jie,Li Zenian. An enhancement to MRMC scheme in video compression[J]. IEEE Transactions On Circuits and Systems for Video Technology,1997,7(3):564～568.
[11] Zhao Tingrong,Tatsuo Ohtsuki. A fast MRME scheme for video compression based on coefficients masking in the wavelet domain[C]. In:Proceedings of the IEEE Region 10 Conference,Cheju Island,South Korea,1999,1:127～130.
[12] 许洁斌,韦岗,布礼文.一种基于形态变换的小波分解运动补偿编码新算法[J].中国图象图形学报,1998,3(9):727～733.
[13] 刘红梅,黄金科,肖自美,等.基于区域分割的小波分解运动补偿编码算法[J].中国图象图形学报,2002,7(A)(3):292～296.
[14] 于立柱.基于模型的小波域的视频压缩编码[D].大连:大连理工大学,2004.
[15] 尚艳霞.基于小波域的视频压缩编码硕士学位论文[D].大连:大连理工大学,2003.
[16] 张磊,涂国防.一种新型小波域运动估计算法[J].电子与信息学报,2007,29(5):1131～1135.
[17] 宋传鸣,王相海.一种新的小波域视频可分级运动估计方案[J].计算机学报,2006,29(12):2112～2118.
[18] 王兵,赵荣椿,程英蕾.一种基于小波域的运动估计方法[J].电子与信息学报,2005,27(5):757～761.
[19] 王光学,曹长修,王健,孙光宇.小波域中几种块匹配运动估计的比较研究[J].计算机工程与设计,1999,20(6):10～13.
[20] 龚涛,丁润涛.基于小波变换的块匹配运动估计方法.天津大学学报[J],2003,36(3):320～324.
[21] 张郑擎.基于小波变换的图象/视频压缩编码及其数字水印嵌入方法的研究[D].上海:上海大学,2001.
[22] 张文琴.先进的小波视频压缩方法及其应用研究[D].北京:中国科学院研究生院,2005.
[23] 房胜,田淑珍,梁永全,等.RDWT 域全相位子带运动补偿视频编码方法[J].小型微型计算机系统,2006,27(4):762～765.
[24] 房胜,梁永全,钟玉琢.一种基于小波域规则三角形网格运动补偿的可扩展视频编码方法[J].中国图象图形学报,2007,12(1):21～26.
[25] 房胜,梁永全,钟玉琢.一种小波域三角形网格运动补偿方法[J].计算机学报,2005,28(12):2089～2095.
[26] 房胜, 钟玉琢.用于视频编码的小波域三角形网格构造方法[J].计算机辅助设计与图形学学报,2005,17(8):1656～1661.
[27] 潘健,汪一鸣.冗余小波域内的多分辨率运动估计[J].苏州大学学报(工科版),2006,26(3):61～64.
[28] 曲昕.基于网格模型的运动补偿算法的研究[D].天津:河北工业大学,2006.
[29] 贺文伟.视频编码中运动估计算法的研究[D].济南:山东大学,2006.
[30] 郭华南.基于小波变换的视频压缩技术[D].天津:天津大学,2004.
[31] 王拯洲.基于小波的视频压缩算法在视频会议中的应用[D].西安:西北工业大学,2007.
[32] Nakaya Y, Harashima H. Motion Compensation Based on Spatial Transformation[J]. IEEE Transactions on Circuits and Systems for Video Technology,1994,4(3):339～356.