在視訊壓縮的演算法中以動態估計的運算為最關鍵的技術，為了降低「完全搜尋法」高度的運算量，很多著名演算法，如「對數搜尋法」、「三步驟搜尋法」、「鑽石搜尋法」紛紛被提出。本篇論文採用的策略是參考適合硬體實現的「預測線性搜尋法」，另外我們提出透過改良後的「可調性動態預估」，在與原本的「預測線性搜尋法」比較之下，可再節省40％~50％的計算量，以PSNR衡量影像品質來說也有相當近似的表現。結合以上兩種理論，本論文提出一個管線式硬體架構，並藉此硬體的特性加速動態估計的運算過程；除此之外由於「預測線性搜尋法」搜尋過程是有規律性的，運用到大量的資料重複使用性，硬體實現上可降低記憶體頻寬，達到更好的加速效果。

Motion estimation’s computation is a key technique in most algorithms for video compression. In order to reduce the extremely high complexity of the “Full Search” approach, many fast algorithms for motion estimation’s computation have been proposed. The “Logarithm Search”, “Three-Step Search”, “Diamond Search” are among the most famous fast algorithms. In this thesis, we introduce the theory “Predictive Line Search” which is adaptive to the hardware implementation, and we also provide that the improved theory “Motion Adaptive Search”. By applying these two methods, 40% to 50% performance improvement in speed is gained while yielding nearly the same quality measured in PSNR. Combining the above-mentioned two theories, a kind of pipeline hardware architecture can be introduced in this thesis, and the Motion Estimation’s computation can be speed up by the proposed hardware’s property. In addition “Predictive Line Search” has regular search pattern, data reuse can be applied and less memory bandwidth is needed that is more appropriate for hardware strategy implementation and better speeding.

[1] J.R. Jain and A.K. Jain, “Displacement measurement and its application in interframe image coding,” IEEE Trans. On Communications, vol. COM-29, pp.1799-808, Dec’81.

[2] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion compensated interframe coding for video conferencing,” Proc. Nat. Telecommun. Conf., New Orleans, LA, pp. G5.3.1-G5.3.5, Dec’81.

[3] S. Zhu and K.K. Ma, “A new diamond search algorithm for fast block matching motion estimation,” Proc. of Int. Conf. Information, Communications and Signal Processing, vol.1, pp.292-6, 1997.

[4] Yu-Wen Huang, Shyh-Yih Ma, Chun-Fu Shen, and Liang-Gee Chen,“Predictive Line Search: An Efficient Motion Estimation Algorithm for MPEG-4 Encoding Systems on Multimedia Processors,” IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 13, NO. 1, JANUARY 2003.

[5] Prabhudev Irappa Hosur, Member, “Motion Adaptive Search for Fast Motion Estimation,” IEEE Transactions on Consumer Electronics, Vol. 49, No. 4, NOVEMBER 2003.

[6] P.Baglietto, M. Maresca, A. Migliaro and M. Migliardi, “Parallel Implementation of the Full Search Block Matching Algorithm for Motion Estimation,” IEEE 1995.

[7] Peter Kuhn, “Algorithms, Complexity Analysis And VLSI Architectures For MPEG-4 Motion Estimation,” KLUWER ACADEMIC PUBLISHERS.

[8] Joan L. Mitchell, William B. Pennebaker, Chad E. Fogg, and Didier J. Legall, “MPEG VIDEO COMPRESSION STANDARD,” Library of Congress Cataloging-in-Publication Data.

[9] “INTERNATIONAL ORGANISATION FOR STANDARDISATION ORGANISATION INTERNATIONALE DE NORMALISATION ISO/IEC JTC 1/SC 29/WG 11 CODING OF MOVING PICTURES AND AUDIO,” Maui, December 1999.

[10] Nios II Processor Reference Handbook for http://www.altera.com/

[11] 戴顯權, “資料壓縮,” 紳藍出版社.

[12] 鍾國亮, “影像處理與電腦視覺,” 東華書局.

[13] 鍾國亮, “資料壓縮的原理與應用,” 全華書局.

[14] 鄭信源, “Verilog 硬體描述語言數位電路設計實務,” 儒林書局.

[15] 林銘波, “FPGA System Design Class Notes,” Department of Electronic Engineering National Taiwan University of Science and Technology, NTUST.

[16] http://www.altera.com/ , altera 網頁

[17] http://www.cipr.rpi.edu/resource/sequences/sif.html , Sequence下載處

[18] http://www.xvid.org/ , XVID source code 網頁