簡易檢索 / 詳目顯示
| 研究生： |
葉明岳 Ming-Yueh Yeh |
|---|---|
| 論文名稱： |
預測型風箏十字菱形搜尋演算法用於快速區塊移動估測 A Predictive Kite-Cross-Diamond Search Algorithm for Fast Block Motion Estimation |
| 指導教授： |
王乃堅
Nai-Jian Wang |
| 口試委員: |
姚立德
none 鍾順平 none 白宏達 none 陳建中 none |
| 學位類別： |
碩士 Master |
| 系所名稱： |
電資學院 - 電機工程系 Department of Electrical Engineering |
| 論文出版年： | 2006 |
| 畢業學年度： | 94 |
| 語文別： | 中文 |
| 論文頁數： | 66 |
| 中文關鍵詞： | 移動估測 、區塊匹配 、預測型風箏十字菱形搜尋 |
| 外文關鍵詞： | motion estimation, block matching, predictive kite-cross-diamond search |
| 相關次數： | 點閱：166 下載：3 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
移動估測的概念在視訊壓縮編碼的架構中，佔有重要的地位，主要的目的是去除連續影像之間的關聯性，因此移動估測演算法的優劣，會影響估測時所需的運算量以及估測後的影像品質。
全域搜尋法（full-search, FS）是傳統視訊壓縮所使用的搜尋演算法，使用此方法能獲得最佳的視訊品質，但缺點是運算量過大。所以近年來不斷地有人提出快速搜尋演算法，一方面企圖減少運算量，另一方面希望能維持一定的影像估測品質。
本篇論文所提出的預測型風箏十字菱形搜尋演算法（predictive kite-cross- diamond search algorithm, PKCDS）主要利用實際生活中影像變化不大的特色，縮小第一步的搜尋圖樣。再加上利用同張影像相鄰區塊有相似的移動特性，使用預測的概念，更進一步的減少搜尋點數。在實驗過程中，我們將本篇論文所提出的演算法與其它數種快速搜尋演算法作比較，結果發現預測型風箏十字菱形搜尋演算法在不同的比較準則下都有不錯的效果。
Motion estimation plays an important role in the architecture of video coding. The main purpose of the motion estimation is to remove the redundancy between continuous video frames. So the search algorithm of estimation will influence the computation complexity and the quality of video frames.
Full-search method is a traditional search algorithm. It exhaustively searches all possible candidate motion vectors in the search area, so it has the optimum perfor- mance for the estimated video frames. However, high computational cost is its drawback, therefore many fast search algorithms are proposed to improve this problem.
In this thesis, we propose a predictive kite-cross-diamond search（PKCDS） algorithm. It adopts a small cross-shaped pattern in the first step in order to fit the center-biased characteristic of the real world video sequences. Then, it uses the predictive concept by utilizing the similar motion characteristic of adjacent blocks at the same frame to further reduce the number of search points. In our experiment, we compare PKCDS algorithm with other fast search algorithms. The results show that PKCDS algorithm is particularly faster and more accurate in some kinds of sequences.
[1] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion- compensated interframe coding for video conferencing,” in Proc. of NTC81, New Orleans, LA, 1981, pp. G5.3.1-G..5.3.5.
[2] R.Li, B. Zeng, and M. L. Liou, “A new three-step search algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 4, no. 4, pp. 438-442, Aug. 1994.
[3] L. M. Po and W. C. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 3, pp. 313-317, June 1996.
[4] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, “A novel unrestricted center-biased diamond search algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 8, no.4, pp. 369-377, Aug. 1998.
[5] C. W. Lam, L. M. Po, and C. H. Cheung, “A novel kite-cross-diamond search algorithm for fast block matching motion estimation,” Circuits and Systems, 2004, ISCAS ’04, Proceedings of the 2004 International Symposium on, vol. 3, pp. 729-732, May 2004.
[6] “Information Technology—Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1.5Mbit/s—Part 2: Video,” JTC1/SC29/WG11, ISO/IEC 11 172-2 (MPEG-1 Video), 1993.
[7] “Generic Coding of Moving Pictures and Associated Audio Information— Part 2: Video,” ITU-T and ISO/IEC JTC 1, ITU Rec. H.262 – ISO/IEC 13 818-2 (MPEG-2 Video), 1994.
[8] “Information Technology—Coding of Audio Visual Objects—Part 2 Visual,” JTC1/SC29/WG11, ISO/IEC 14 469-2 (MPEG-4 Visual), 2000.
[9] “Video Codec for Audiovisual Services at p 64 kbit/s,” ITU-T SG15, ITU-T Rec. H.261, 2 ed., 1993.
[10] “Video Coding for Low Bit Rate Communication,” ITU-T SG16, ITU-T Rec. H.263, 3rd ed., 2000.
[11] H. Schwarz and T. Wiegand, “The emerging JVT/H.26L video coding stand- ard,” in Proc. of IBC 2002, Amsterdam, The Netherlands, Sep. 2002.
[12] “Draft ITU-T Rec. and Final Draft international Standard of Joint Video Specification (ITU-T Rec. H.264-ISO/IEC 14 496-10 AVC),” Joint Video Team (JVT) of ITU-T and ISO/IEC JTC1, Geneva, JVT of ISO/IEC MPEG and ITU-T VCEG, JVT-G050r1, 2003.
[13] C. Zhu, X. Lin, and L. P. Chau, “Hexagon-based search pattern for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 5, pp. 349-355, May 2002.
[14] C. H. Cheung and L. M. Po, “A novel cross-diamond search algorithm for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 12, pp. 1168-1177, Dec. 2002.
[15] W. Li and E. Salari, “Successive elimination algorithm for motion estimation,” IEEE Trans. Image Processing, vol. 4, no. 1, pp. 105-107, Jan. 1995
[16] L. Luo, C. Zou, X. Gao, and Z. He, “A new prediction search algorithm for block motion estimation in video coding,” IEEE Trans. Consumer Electronics, vol. 43, no. 1, pp. 56-61, Feb. 1997.
[17] Y. T. Roan and P. Y. Chen, “A fuzzy search algorithm for the estimation of motion vectors,” IEEE Trans. on Broadcasting, vol. 46, no. 2, pp. 121-127, June 2000.
[18] P. Y. Chen and J. M. Jou, “An efficient blocking-matching algorithm based on fuzzy reasoning,” IEEE Trans. on Systems, Man, and Cybernetics—Part B: Cybernetics, vol. 31, no. 2, pp. 253-259, April 2001.
