臺灣博碩士論文加值系統

移動估測的概念在視訊壓縮編碼的架構中，佔有重要的地位，主要的目的是去除連續影像之間的關聯性，因此移動估測演算法的優劣，會影響估測時所需的運算量以及估測後的影像品質。
全域搜尋法（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.

中文摘要........................................................................................................................i
英文摘要.......................................................................................................................ii
誌謝..............................................................................................................................iii
目錄..............................................................................................................................iv
圖表目錄......................................................................................................................vi
第一章 緒論................................................................................................................1
1.1 研究背景與動機…………………………………………………………...1
1.2 研究目的及方法…………………………………………………………...2
1.3 論文組織…………………………………………………………………...2
第二章 移動估測演算法相關研究與分析................................................................4
2.1 移動估測與補償…………………………………………………………...4
2.2 區塊匹配法則……………………………………………………………...6
2.3 快速搜尋演算法…………………………………………………………...9
2.3.1 新三步搜尋演算法…………………………………………………...9
2.3.2 四步搜尋演算法…………………………………………………….12
2.3.3 菱形搜尋演算法…………………………………………………….14
2.3.4 預測搜尋演算法…………………………………………………….16
2.3.5 基於模糊推論有效率區塊匹配演算法…………………………….18
第三章 預測型風箏十字菱形搜尋演算法..............................................................24
3.1 風箏十字菱形搜尋演算法……………………………………………….24
3.2 預測型風箏十字菱形搜尋演算法……………………………………….30
第四章 實驗結果.......................................................................................................34
4.1 實驗介紹………………………………………………………………….34
4.2 實驗數據與分析………………………………………………………….35
第五章 結論與未來方向..........................................................................................62
5.1 結論……………………………………………………………………….62
5.2 未來方向………………………………………………………………….62
參考文獻 ...................................................................................................................63
作者簡介......................................................................................................................66

[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.