降低快速搜索算法中局部最优误差的研究
|
摘要
运动估计是视频编码器的重要组成部分，占整个压缩编码50％以上的计算量。而块匹配搜索又是运动估计的核心，全局搜索算法由于运算复杂度较大，没有实用价值，为了降低搜索量，科研人员提出了各种快速搜索算法，如：三步法、四步法、钻石法等。
快速搜索算法虽然能够有效的降低搜索量，由于它是对搜索窗有选择的搜索，容易陷入局部最优产生误差，称为局部最优误差，如何解决局部最优问题一直是研究的热点。通过分析，降低局部最优误差的方法一般分为两类：一类是改进搜索算法，另一类是改进搜索方案，本文就是基于这两类方法展开讨论。
在对经典快速搜索算法分析的基础上，本文提出了一种改进的快速搜索算法——两阶段搜索算法，主要通过提高第一步的搜索量来达到降低局部最优误差的目的。
但如何评价一个快速搜索算法的好坏是提出新算法时要面临的问题。由于相对快速搜索算法而言，全局搜索算法具有搜索量最大、搜索精度最高的特征，本文提出把全局搜索算法作为一个参考点，所有待评价的快速搜索算法都与这个参考点进行比较，得出一个量值，该量值就作为快速搜索算法质量值，通过比较质量值来达到比较快速搜索算法的目的。
多分辨率运动估计是一种搜索方案的改进，它不再仅局限于对相邻帧原图进行搜索，而是通过选择初始搜索点的方法来降低快速搜索算法的局部最优误差。小波域多分辨率运动估计就是在这个基础上发展起来的，它利用小波变换良好的多尺度特性，得到不同分辨率的子图，构造出多分辨率塔型结构。本文通过实验分析得出：相对空间域搜索而言，基于小波域多分辨率运动估计的快速搜索算法确实能够降低快速搜索算法局部最优误差，但增加了搜索层数，在一定程度上增加了运动估计的复杂度。为解决这个问题本文提出了基于小波域的越级多分辨率运动估计思想，并结合快速搜索算法，在降低局部最优误差的前提下，有效的降低运算复杂度。
Motion Estimation plays a very important part in video encoder, which accounted for more than 50% of the amount of coding. Because of computational complexity of exhaustive search, it has no practical value. In order to reduce the amount of computation, the researchers put forward a variety of fast search algorithms such as three step search, four step search, diamond search, etc.
Although fast search algorithms can effectively reduce the amount of search, because of their choice to search in the search window, it can easily fall into local optimal and thus produce error, which is called as local optimal error. How to solve local optimal problem has always been a hot topic. Through analysis, the approach to reduce the local optimal error can generally be divided into two types: one is to improve the search algorithm, the other is to improve search plan, and this paper is to further the discussion on the base of the two methods.
On the basis of the analysis of the classical fast search algorithms, this paper proposes a modified fast search algorithm, two-phase search algorithm. It mainly adopts improving the first step search volume to achieve the purpose of reducing local optimal error.
But how to assess the quality of a fast search algorithm is the problem faced when proposes a new algorithm. In comparison to fast search algorithms, the exhaustive search algorithm has the features of the largest and highest accuracy of search, so this paper proposed exhaustive search algorithm as a reference point. All fast search algorithms for the evaluation compare with the reference point, and get a value. The value is as the quality value of a fast search algorithm.
Multi-resolution motion estimation is an improvement to the search plan, and it no longer limited to the search of two adjacent frames, but by choosing initial search point to reduce the local optimal error of the fast search algorithms. The wavelet-based multi-resolution motion estimation is developed on this basis. It uses multi-scale feature of the wavelet to get sub-images which own different resolution, and then constructs the pyramid structure of multi-resolution. In comparison to relative fast search algorithms
快速搜索算法虽然能够有效的降低搜索量，由于它是对搜索窗有选择的搜索，容易陷入局部最优产生误差，称为局部最优误差，如何解决局部最优问题一直是研究的热点。通过分析，降低局部最优误差的方法一般分为两类：一类是改进搜索算法，另一类是改进搜索方案，本文就是基于这两类方法展开讨论。
在对经典快速搜索算法分析的基础上，本文提出了一种改进的快速搜索算法——两阶段搜索算法，主要通过提高第一步的搜索量来达到降低局部最优误差的目的。
但如何评价一个快速搜索算法的好坏是提出新算法时要面临的问题。由于相对快速搜索算法而言，全局搜索算法具有搜索量最大、搜索精度最高的特征，本文提出把全局搜索算法作为一个参考点，所有待评价的快速搜索算法都与这个参考点进行比较，得出一个量值，该量值就作为快速搜索算法质量值，通过比较质量值来达到比较快速搜索算法的目的。
多分辨率运动估计是一种搜索方案的改进，它不再仅局限于对相邻帧原图进行搜索，而是通过选择初始搜索点的方法来降低快速搜索算法的局部最优误差。小波域多分辨率运动估计就是在这个基础上发展起来的，它利用小波变换良好的多尺度特性，得到不同分辨率的子图，构造出多分辨率塔型结构。本文通过实验分析得出：相对空间域搜索而言，基于小波域多分辨率运动估计的快速搜索算法确实能够降低快速搜索算法局部最优误差，但增加了搜索层数，在一定程度上增加了运动估计的复杂度。为解决这个问题本文提出了基于小波域的越级多分辨率运动估计思想，并结合快速搜索算法，在降低局部最优误差的前提下，有效的降低运算复杂度。
Motion Estimation plays a very important part in video encoder, which accounted for more than 50% of the amount of coding. Because of computational complexity of exhaustive search, it has no practical value. In order to reduce the amount of computation, the researchers put forward a variety of fast search algorithms such as three step search, four step search, diamond search, etc.
Although fast search algorithms can effectively reduce the amount of search, because of their choice to search in the search window, it can easily fall into local optimal and thus produce error, which is called as local optimal error. How to solve local optimal problem has always been a hot topic. Through analysis, the approach to reduce the local optimal error can generally be divided into two types: one is to improve the search algorithm, the other is to improve search plan, and this paper is to further the discussion on the base of the two methods.
On the basis of the analysis of the classical fast search algorithms, this paper proposes a modified fast search algorithm, two-phase search algorithm. It mainly adopts improving the first step search volume to achieve the purpose of reducing local optimal error.
But how to assess the quality of a fast search algorithm is the problem faced when proposes a new algorithm. In comparison to fast search algorithms, the exhaustive search algorithm has the features of the largest and highest accuracy of search, so this paper proposed exhaustive search algorithm as a reference point. All fast search algorithms for the evaluation compare with the reference point, and get a value. The value is as the quality value of a fast search algorithm.
Multi-resolution motion estimation is an improvement to the search plan, and it no longer limited to the search of two adjacent frames, but by choosing initial search point to reduce the local optimal error of the fast search algorithms. The wavelet-based multi-resolution motion estimation is developed on this basis. It uses multi-scale feature of the wavelet to get sub-images which own different resolution, and then constructs the pyramid structure of multi-resolution. In comparison to relative fast search algorithms
引文
[1] Rafael C.Gonzalez, Richard E.Woods．数字图像处理(第二版)．北京：电子工业出版社，2004
[2] Rafael C.Gonzalez，Richard E.Woods．数字图像处理(MATLAB版)．北京：电子工业出版社，2005
[3] 朱红．数字图像处理基础．北京：科学出版社，2005
[4] 丁贵广，技文平，郭宝龙．Visual C++6.0数字图像编码．北京：机械工业出版社，2004
[5] 张旭东，卢国栋，冯健．图像编码基础和小波压缩技术——原理、算法和标准．北京：清华大学出版社，2004
[6] Jain J.R., Jain A.K.. Displacement measurement and its application in interframe image coding. IEEE Trans. Communication, 1981, Vol.29 (No.12): 1799-1806
[7] T. Koga, K. Linuma, A. Hirano, et al. Motion compensated inter-frame coding for video conferencing. In Proc. Nat. Telecommun. Conf.. New Orleans, LA. 1981: G5.3.1-G5.3.5
[8] R. Li, B. Zeng, M. L. Liou. A new three step search algorithm for block motion estimation. IEEE Trans Circuits Syst Video Technol., 1994, Vol.4 (No.4): 438-442
[9] Ghanbari M.. The cross-search algorithm for motion estimation. IEEE Trans. Communication, 1990, Vol.38 (No.7): 950-953
[10] Po L. M., Ma W. C.. A novel four-step search algorithm for fast block motion estimation. IEEE Trans Circuits Syst Video Technol., 1996, Vol.6 (No.3): 313-317
[11] Tham Jo Yew, Ranganath Surendra, Ranganath, Maitreya, et al. Novel unrestricted center-biased diamond search algorithm for block motion estimation. IEEE Trans Circuits Syst Video Technol., 1998, Vol.8 (No.4): 369-377
[12] Zhu S., Ma K. K.. A new diamond Search algorithm for fast block-matching motion estimation. IEEE Trans Circuits Syst Video Technol., 2000, Vol.9 (No.2): 287-290
[13] 沈兰荪，卓力．小波编码与网络视频传输．北京：科学出版社，2005
[14] 飞思科技产品研发中心．小波分析理论与MATLAB7实现．北京：科学出版社，2005
[15] 吴宇新．基于小波变换的图像编码算法研究：[博士学位论文]．保存地点：上海交通大学图书馆，1999
[16] Thomas Sikora. Trends and perspectives in image and video coding. Proceedings of the IEEE, 2005, Vol.93 (No.1): 6-17.
[17] 王相海，张跃平．基于小波的图像及视频编码研究进展．计算机工程与应用，2004，No．11：78-80
[18] 童小平．基于小波变换的低比特率视频图像压缩编码的研究：[硕士学位论文]．保存地点：重庆大学图书馆，2004
[19] 张宗平，刘贵忠．基于小波的视频图像压缩研究进展．电子学报，2002，Vol．30 (No．6)：883-889
[20] 张文琴．先进的小波视频压缩方法及其应用研究：[硕士学位论文]．保存地点：中国科学院研究生院图书馆，2005
[21] 宋传鸣，王相海．小波域视频运动估计研究进展．计算机学报，2005，Vol．28 (No．10)：1716-1727
[22] 张文琴．先进的小波视频压缩方法及其应用研究：[硕士学位论文]．保存地点：中国科学院研究生院图书馆：2005
[23] 伍长庆，王志中，薛琦．基于ICGI运动补偿的视频小波编码技术．计算机工程，2000，Vol．26(No．10)：138-139
[24] 丁贵广，郭宝龙，戴琼海．基于提升技术的运动补偿三维小波视频编码．系统工程与电子技术，2004，Vol．26(No．9)：1296-1298
[25] 区聘．基于运动补偿技术和三维小波变换的视频编码器研究：[硕士学位论文]．保存地点：重庆大学图书馆，2004
[26] 谭毅华．完全可伸缩小波视频编码及后处理技术研究：[博士学位论文]．保存地点：华中科技大学图书馆，2004
[27] Yao Wang，Jorn Ostermann，Ya-Qin Zhang．视频处理与通信．候正信，杨喜，王文全．北京：电子工业出版社，2003
[28] 乔轩，潘翔，顾伟康等．一种运动估计的小菱形分层快速搜索算法．传感技术学报，2005，Vol．18(No．4)：923-926
[29] 张鹏，郭宝龙．基于多模板搜索的快速运动估计算法．计算机工程与应用，2006，Vol．8：66-69
[30] 王洁，张太镒，乐培玉．基于运动复杂度的快速运动估计算法．计算机应用，2006，Vol．26(No．3)：295-297
[31] 刘海华，雷奕，谢长生．基于块匹配的运动估计搜索算法研究与实现．计算机应用，2006，Vol．26(No．6)：66-69
[32] 李子印，朱善安．基于运动矢量预测的六边形块运动估计搜索算法．信号处理，2006，Vol．22(No．2)：193-197
[33] Ce Zhu, Xiao Lin, Lap-Pui Chau. Hexagon-based search pattern for fast block motion estimation. IEEE Trans Circuits Syst Video Technol., 2002, Vol. 12 (No.5):349-355
[34] 曹宇辉．H．264运动估计整像素部分算法的改进与实现：[硕士学位论文]．保存地点：浙江大学图书馆，2006
[35] Chun-Ho Cheung, Lai-Man Po. Novel cross-diamond-Hexagonal search algorithms for fast block motion estimation. IEEE Trans. on Multimedia, 2005, Vol.7 (No.1): 16-22
[36] 丁贵广，郭宝龙．基于线性搜索的快速运动估计算法．西安交通大学学报，2004，Vol．38(No．2)：136-139
[37] 邹晓春．基于快速块匹配的图象序列运动估计技术研究：[硕士学位论文]．保存地点：西北工业大学图书馆，2005
[38] 自然施．视频压缩中的运动估计技术的研究：[硕士学位论文]．保存地点：汕头大学图书馆，2003
[39] Hsien-Wen Cheng, Lan-Rong Dung. A content-based methodology for power-aware motion estimation architecture. IEEE Trans. on Circuits and Systems—Ⅱ: Express Briefs, 2005, Vol.52 (No. 10): 631-635
[40] 贺玉文，赵黎，钟玉琢等．快速鲁棒的全局运动估计算法．软件学报，2001，Vol．12(No．8)：1210-1228
[41] Ishfaq Ahmad, Weiguo Zheng, Jiancong Luo, et al. A Fast Adaptive Motion Estimation Algorithm. IEEE Trans Circuits Syst Video Technol., 2006, Vol.16 (No.3): 420-438
[42] Ioannis Patras, Marcel Worring, Rein van den Boomgaard, Dense motion estimation using regularization constraints on local parametric models. IEEE Transactions on Image Processing, 2004, Vol. 13 (No. 11): 1432-1443
[43] Yao Nie, Kai-Kuang Ma. Adaptive irregular pattern search with matching prejudgment for fast block-matching motion estimation. IEEE Trans Circuits Syst Video Technol., 2005, Vol. 15 (No.6): 789-794
[44] Xuan-Quang Banh, Yap-Peng Tan. Adaptive dual-cross search algorithm for block-matching motion estimation. IEEE Transactions on Consumer Electronics, 2004, Vol. 50 (No.2): 766-775
[45] 张博，吴芝路，张欣宇等．基于矢量叠加和自适应中止的快速运动估计．Video Engineering，2006，No．4：7-9
[46] 施建良．甚低码率视频编码中运动估计和运动分割研究：[博士学位论文]．保存地点：上海交通大学图书馆，1999
[47] 张旭东，王德生，彭应宁．高效多分层半像素精度块匹配运动估计算法．清华大学学报(自然科学版)，1999，Vol．39(No．5)：58-60
[48] Ya-Qin Zhang, Sohail Zafar. Motion-compensated wavelet transform coding for color video compression. IEEE Trans Circuits Syst Video Technol., 1992, Vol.2 (No.3): 285-296
[49] 区聘．基于运动补偿技术和三维小波变换的视频编码器研究：[博士学位论文]．保存地点：重庆大学图书馆，2004
[50] 张宗平，刘贵忠．基于小波的视频图像压缩研究进展．电子学报，2002，Vol．30(No．6)：883-889
[51] Jinwen Zan, M. Omair Ahmad, M. N. S. Swamy. Comparison of wavelets for multiresolution motion estimation. IEEE Trans Circuits Syst Video Technol., 2006, Vol.16 (No.3): 439-446
[52] 张鹏，郭宝龙．基于多模板搜索的快速运动估计算法．计算机工程与应用，2006，No．08：66-69
[53] Shih-Ta Hsiang, John W. Woods, Jens-Rainer Ohm. Invertible temporal subband/wavelet filter banks with half-pixel-accurate motion compensation. IEEE Transactions on Image Processing, 2004, Vol. 13 (No.8): 1018-1028
[54] Cho-Chun Cheng, Wen-Liang Hwang, Zuowei Shen, et al. Subjective and objective comparison of advanced motion compensation methods for blocking artifact reduction in a 3-D wavelet coding system. IEEE Trans Circuits Syst Video Technol., 2006, Vol.16 (No.9): 1134-1141
[2] Rafael C.Gonzalez，Richard E.Woods．数字图像处理(MATLAB版)．北京：电子工业出版社，2005
[3] 朱红．数字图像处理基础．北京：科学出版社，2005
[4] 丁贵广，技文平，郭宝龙．Visual C++6.0数字图像编码．北京：机械工业出版社，2004
[5] 张旭东，卢国栋，冯健．图像编码基础和小波压缩技术——原理、算法和标准．北京：清华大学出版社，2004
[6] Jain J.R., Jain A.K.. Displacement measurement and its application in interframe image coding. IEEE Trans. Communication, 1981, Vol.29 (No.12): 1799-1806
[7] T. Koga, K. Linuma, A. Hirano, et al. Motion compensated inter-frame coding for video conferencing. In Proc. Nat. Telecommun. Conf.. New Orleans, LA. 1981: G5.3.1-G5.3.5
[8] R. Li, B. Zeng, M. L. Liou. A new three step search algorithm for block motion estimation. IEEE Trans Circuits Syst Video Technol., 1994, Vol.4 (No.4): 438-442
[9] Ghanbari M.. The cross-search algorithm for motion estimation. IEEE Trans. Communication, 1990, Vol.38 (No.7): 950-953
[10] Po L. M., Ma W. C.. A novel four-step search algorithm for fast block motion estimation. IEEE Trans Circuits Syst Video Technol., 1996, Vol.6 (No.3): 313-317
[11] Tham Jo Yew, Ranganath Surendra, Ranganath, Maitreya, et al. Novel unrestricted center-biased diamond search algorithm for block motion estimation. IEEE Trans Circuits Syst Video Technol., 1998, Vol.8 (No.4): 369-377
[12] Zhu S., Ma K. K.. A new diamond Search algorithm for fast block-matching motion estimation. IEEE Trans Circuits Syst Video Technol., 2000, Vol.9 (No.2): 287-290
[13] 沈兰荪，卓力．小波编码与网络视频传输．北京：科学出版社，2005
[14] 飞思科技产品研发中心．小波分析理论与MATLAB7实现．北京：科学出版社，2005
[15] 吴宇新．基于小波变换的图像编码算法研究：[博士学位论文]．保存地点：上海交通大学图书馆，1999
[16] Thomas Sikora. Trends and perspectives in image and video coding. Proceedings of the IEEE, 2005, Vol.93 (No.1): 6-17.
[17] 王相海，张跃平．基于小波的图像及视频编码研究进展．计算机工程与应用，2004，No．11：78-80
[18] 童小平．基于小波变换的低比特率视频图像压缩编码的研究：[硕士学位论文]．保存地点：重庆大学图书馆，2004
[19] 张宗平，刘贵忠．基于小波的视频图像压缩研究进展．电子学报，2002，Vol．30 (No．6)：883-889
[20] 张文琴．先进的小波视频压缩方法及其应用研究：[硕士学位论文]．保存地点：中国科学院研究生院图书馆，2005
[21] 宋传鸣，王相海．小波域视频运动估计研究进展．计算机学报，2005，Vol．28 (No．10)：1716-1727
[22] 张文琴．先进的小波视频压缩方法及其应用研究：[硕士学位论文]．保存地点：中国科学院研究生院图书馆：2005
[23] 伍长庆，王志中，薛琦．基于ICGI运动补偿的视频小波编码技术．计算机工程，2000，Vol．26(No．10)：138-139
[24] 丁贵广，郭宝龙，戴琼海．基于提升技术的运动补偿三维小波视频编码．系统工程与电子技术，2004，Vol．26(No．9)：1296-1298
[25] 区聘．基于运动补偿技术和三维小波变换的视频编码器研究：[硕士学位论文]．保存地点：重庆大学图书馆，2004
[26] 谭毅华．完全可伸缩小波视频编码及后处理技术研究：[博士学位论文]．保存地点：华中科技大学图书馆，2004
[27] Yao Wang，Jorn Ostermann，Ya-Qin Zhang．视频处理与通信．候正信，杨喜，王文全．北京：电子工业出版社，2003
[28] 乔轩，潘翔，顾伟康等．一种运动估计的小菱形分层快速搜索算法．传感技术学报，2005，Vol．18(No．4)：923-926
[29] 张鹏，郭宝龙．基于多模板搜索的快速运动估计算法．计算机工程与应用，2006，Vol．8：66-69
[30] 王洁，张太镒，乐培玉．基于运动复杂度的快速运动估计算法．计算机应用，2006，Vol．26(No．3)：295-297
[31] 刘海华，雷奕，谢长生．基于块匹配的运动估计搜索算法研究与实现．计算机应用，2006，Vol．26(No．6)：66-69
[32] 李子印，朱善安．基于运动矢量预测的六边形块运动估计搜索算法．信号处理，2006，Vol．22(No．2)：193-197
[33] Ce Zhu, Xiao Lin, Lap-Pui Chau. Hexagon-based search pattern for fast block motion estimation. IEEE Trans Circuits Syst Video Technol., 2002, Vol. 12 (No.5):349-355
[34] 曹宇辉．H．264运动估计整像素部分算法的改进与实现：[硕士学位论文]．保存地点：浙江大学图书馆，2006
[35] Chun-Ho Cheung, Lai-Man Po. Novel cross-diamond-Hexagonal search algorithms for fast block motion estimation. IEEE Trans. on Multimedia, 2005, Vol.7 (No.1): 16-22
[36] 丁贵广，郭宝龙．基于线性搜索的快速运动估计算法．西安交通大学学报，2004，Vol．38(No．2)：136-139
[37] 邹晓春．基于快速块匹配的图象序列运动估计技术研究：[硕士学位论文]．保存地点：西北工业大学图书馆，2005
[38] 自然施．视频压缩中的运动估计技术的研究：[硕士学位论文]．保存地点：汕头大学图书馆，2003
[39] Hsien-Wen Cheng, Lan-Rong Dung. A content-based methodology for power-aware motion estimation architecture. IEEE Trans. on Circuits and Systems—Ⅱ: Express Briefs, 2005, Vol.52 (No. 10): 631-635
[40] 贺玉文，赵黎，钟玉琢等．快速鲁棒的全局运动估计算法．软件学报，2001，Vol．12(No．8)：1210-1228
[41] Ishfaq Ahmad, Weiguo Zheng, Jiancong Luo, et al. A Fast Adaptive Motion Estimation Algorithm. IEEE Trans Circuits Syst Video Technol., 2006, Vol.16 (No.3): 420-438
[42] Ioannis Patras, Marcel Worring, Rein van den Boomgaard, Dense motion estimation using regularization constraints on local parametric models. IEEE Transactions on Image Processing, 2004, Vol. 13 (No. 11): 1432-1443
[43] Yao Nie, Kai-Kuang Ma. Adaptive irregular pattern search with matching prejudgment for fast block-matching motion estimation. IEEE Trans Circuits Syst Video Technol., 2005, Vol. 15 (No.6): 789-794
[44] Xuan-Quang Banh, Yap-Peng Tan. Adaptive dual-cross search algorithm for block-matching motion estimation. IEEE Transactions on Consumer Electronics, 2004, Vol. 50 (No.2): 766-775
[45] 张博，吴芝路，张欣宇等．基于矢量叠加和自适应中止的快速运动估计．Video Engineering，2006，No．4：7-9
[46] 施建良．甚低码率视频编码中运动估计和运动分割研究：[博士学位论文]．保存地点：上海交通大学图书馆，1999
[47] 张旭东，王德生，彭应宁．高效多分层半像素精度块匹配运动估计算法．清华大学学报(自然科学版)，1999，Vol．39(No．5)：58-60
[48] Ya-Qin Zhang, Sohail Zafar. Motion-compensated wavelet transform coding for color video compression. IEEE Trans Circuits Syst Video Technol., 1992, Vol.2 (No.3): 285-296
[49] 区聘．基于运动补偿技术和三维小波变换的视频编码器研究：[博士学位论文]．保存地点：重庆大学图书馆，2004
[50] 张宗平，刘贵忠．基于小波的视频图像压缩研究进展．电子学报，2002，Vol．30(No．6)：883-889
[51] Jinwen Zan, M. Omair Ahmad, M. N. S. Swamy. Comparison of wavelets for multiresolution motion estimation. IEEE Trans Circuits Syst Video Technol., 2006, Vol.16 (No.3): 439-446
[52] 张鹏，郭宝龙．基于多模板搜索的快速运动估计算法．计算机工程与应用，2006，No．08：66-69
[53] Shih-Ta Hsiang, John W. Woods, Jens-Rainer Ohm. Invertible temporal subband/wavelet filter banks with half-pixel-accurate motion compensation. IEEE Transactions on Image Processing, 2004, Vol. 13 (No.8): 1018-1028
[54] Cho-Chun Cheng, Wen-Liang Hwang, Zuowei Shen, et al. Subjective and objective comparison of advanced motion compensation methods for blocking artifact reduction in a 3-D wavelet coding system. IEEE Trans Circuits Syst Video Technol., 2006, Vol.16 (No.9): 1134-1141