移動估測是視訊編碼中計算量最為巨大的元件。近年來，有許多節省運算量的快速搜尋演算法陸續被發表。這些快速搜尋演算法使用了各式各樣最佳化的技巧以簡化計算量，例如針對可能的移動特性提出各種搜尋樣板。然而，僅使用單一演算法並不足以因應多媒體應用南轅北轍的需求。在本論文中，基於移動估測演算法間的相依性，我們提出了一個高彈性，粗糙紋理型的可重組化移動估測器，除了因應廣泛應用的多種需求外，並致力於降低硬體設計所付出的面積成本。我們的架構主要利用可重組化架構本質上的高靈活特性，以支援多種移動估測演算法。本論文採用全搜尋法，三步驟搜尋法及菱形搜尋法做為演算法整合樣板。為達資源共享及頻寬需求，我們更提出了一種嶄新的統合性記憶體配置方法，可以更進一步地消弭各種演算法本身的差異性。此外，我們亦提出一個簡化的適應性演算法，其可根據物件移動特性，在以上三種搜尋演算法中做切換。
我們所提出的架構具有下列幾項優點：(1)藉由可重組化架構、靈活的連接網絡、及統合性的記憶體配置方式，我們以一種極為有效率的設計方法減少整合多種演算法在面積上所必須付出的硬體成本;(2)除了提供單一移動估測演算法，我們的架構尚能依據畫面特性，在編碼過程中藉由簡化的演算法切換器，適應性地轉換演算法以提升編碼效率;(3)能有效處理不同應用的多樣需求或是存在於畫面間的各種差異性。
本篇論文所提出之支援多元移動估測演算法之可重組化架構，輔以16384位元記憶體配置空間，約佔95.4千個邏輯閘。訊號雜訊比及每個巨區塊 (macroblock) 之平均搜尋點的實驗結果皆顯示，我們的架構可充份利用三個演算法各自的編碼優勢，並且在135 MHz之工作頻率下，足以即時應用於標準電視畫質的視訊。

Motion Estimation (ME) is the most computation-intensive part in video encoding. Several fast block matching algorithms have been presented to diminish the computational complexity. A variety of optimization schemes have been adopted such as those introducing a pre-defined search pattern according to possible motion structures. In practice, it is hard for one method to meet the requirements of all applications. In this thesis, based on the algorithmic similarity of ME algorithms, a coarse-grained reconfigurable architecture is proposed to obtain design flexibility with a lower hardware cost and to satisfy various requirements of wide range applications. The proposed coarse-grained reconfigurable motion estimator (CRME) can support multiple search algorithms. Three different algorithms, the full search (FS), three step search (TSS) and diamond search (DS), are taken as the basis of our supporting algorithms. Furthermore, a unified memory management scheme is introduced to mitigate the overhead of considering the intrinsic diversity of each algorithm. Additionally, we propose a simple algorithm switcher for the reconfigurable motion estimator; the search procedure can adaptively switch among the three search patterns above according to the current motion contents. The developed architecture has the following advantages. (1) With the reconfigurable array, flexible interconnection network and unified memory organization, the area overhead of merging multiple ME algorithms is reduced in a very efficient way. (2) In addition to supporting a single algorithm, our reconfigurable architecture is able to utilize three search patterns alternately with a simple adaptive algorithm switcher during the encoding processes. (3) It can effectively deal with various applications with different video contents.
Experimental results of the PSNR and the average number of checking points per macroblock (MB) exhibit that our reconfigurable fabric, consisting of about 95.4k gate counts accompanied by an on-chip memory of 16.384k bits, can take advantages of the three search algorithms and support the standard-definition (SD, 704x480x30) video sequence in real-time applications when operated in 135 MHz.

[1] MPEG-2 Generic Coding of Moving Pictures and Associated Audio Information, ISO/IEC 13818, 1996.
[2] MPEG-4 – Information Technology – Coding of Audio-Visual Objects – Part 2: Visual, ISO/IEC 14496-2, 2000.
[3] Video Codec for Low Bitrate Communication, ITU-T Rec. H.263, 1998.
[4] T. Wiegand, Final Draft International Standard for Joint Video Specification H.264 2003, JVT of ISO/IEC MPEG and ITU-T VCEG, JVT-G050.
[5] T. Dias, N. Roma, L. Sousa, and M. Ribeiro, “Reconfigurable Architectures and Processors for Real-Time Video Motion Estimation,” Journal of Real-Time Image Process., vol. 2, pp. 191-205, Nov. 2007.
[6] W.M. Chao, C.W. Hsu, Y.C. Chang, and L.G. Chen, “A Novel Hybrid Motion Estimation Supporting Diamond Search and Fast Full Search,” in Proc. of 2002 IEEE Int. Sym. Cir. and Sys., vol. 2, pp. 492-495, May 2002.
[7] J. R. Jain and A. K. Jain, “Displacement Measurement and Its Application in Interframe Coding,” IEEE Trans. on Commun., vol. 29, no. 12, pp.1799-1808. Dec. 1981.
[8] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion Compensated Interframe Coding for Video Conferencing,” in Proc. of Nat. Telecommun. Conf., New Orleans, LA, pp. G5.3.1-5.3.5, Nov. 1981.
[9] S. Zhu and K. –K. Ma, “A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation,” IEEE Trans. Image Process., vol. 9, pp. 287-290, Feb. 2000.
[10] C. Zhu, X. Lin, L. Chau, and L. –M. Po, “Enhanced Hexagonal Search for Fast Block Motion Estimation,” IEEE Trans. Cir. Sys. Video Techno., vol. 14, pp. 1210-1214, Oct. 2004.
[11] G. G. Lee et al., “Algorithm/Architecture Co-Design of 3-D Spatio-Temporal Motion Estimation for Video Coding,” IEEE Trans. Multim., vol. 9, pp. 455-465, Apr. 2007.
[12] Y. Nie and K.K. Ma, “Adaptive Irregular Pattern Search with Matching Prejudgment for Fast Block-Matching Motion Estimation,” IEEE Trans. Cir. and Sys. Video Techno., vol. 15, pp. 789-794, June 2005.
[13] Y. Nie and K.K. Ma, “Adaptive Rood Pattern Search for Fast Block-Matching Motion Estimation,” IEEE Trans. Image Process., vol. 11, pp. 1442-1449, Dec 2002.
[14] C. Wang, S. Yang, C. Liu and T. Chiang, “A Hierarchical N-Queen Decimation Lattice and Hardware Architecture for Motion Estimation,” IEEE Trans. Cir. and Sys. Video Techno., vol. 14, pp. 429-440, Apr. 2004.
[15] K. Lenqwehasatit and A. Orteqa, “Probabilistic Partial-Distance Fast Matching Algorithms for Motion Estimation,” IEEE Trans. Cir. and Sys. Video Techno., vol. 11, pp. 139-152, Feb. 2001.
[16] M. Bierling, “Displacement Estimation by Hierarchical Block-Matching,” in Proc. of SPIE, vol. 1001, pp.942-951, 1988.
[17] S.Y. Huang, C.Y. Cho, and J.S. Wang, “Adaptive Fast Block-Matching Algorithm by Switching Search Patterns for Sequence With Wide-Range Motion Content,” IEEE Trans. Cir. and Sys. Video Techno., vol. 15, pp. 1373-1384, Nov. 2005.
[18] K.H. Nq, L.M. Po and K.M. Wong, “Search Patterns Switching for Motion Estimation Using Rate of Error Descent,” in Proc. of IEEE Int. Conf. Multim. and Expo., pp.1583-1586, June 2007.
[19] Reventflow et al., “Chip Set for Motion Estimation Based on Phase Correlation and Block Matching,” presented at 4th. Int. Workshop HDTV and Beyond, 1991.
[20] Santanu Dutta, and Wayne Wolf, “A Flexible Parallel Architecture Adapted to Block-Matching Motion-Estimation Algorithms,” IEEE Trans. Cir. and Sys. Video Techno., vol. 6, pp.74-86 , Nov. 1996.
[21] J. Choi, N. Togawa, M. Yanagisawa, and T. Ohtsuki, “VLSI Architecture for a Flexible Motion Estimation with Parameters, ” In Proc. of the 15th Int. Conf. on VLSI Design, pp. 452-457, Jan. 2002.
[22] X.D. Zhang and C.Y. Tsui, “An Efficient and Reconfigurable VLSI Architecture for Different Block Matching Motion Estimation Algorithms,” in Proc. of ICASSP, vol. 1, pp. 603-606, Apr. 1997.
[23] S. Li et al., “A Hardware Implementation of a Content-Based Motion Estimation Algorithm for Real-Time MPEG-4 Video Coding,” IEICE Trans. Fund., vol. E89-A, pp. 932-940, April 2006.
[24] L. Zhang, and W. Gao, “Reusable Architecture and Complexity-Controllable Algorithm for the Integer/Fractional Motion Estimation of H.264,” IEEE Trans. Consum. Electron., vol. 53, pp. 749-756, May 2007.
[25] A. Ben Atitallah, et al.,“HW/SW FPGA Architecture for a Flexible Motion Estimation,” in Proc. of the 14th Int. Conf. ICECS, pp. 30-33, Dec. 2007.
[26] R. Tessier and W. Burleson, “Reconfigurable Computing for Digital Signal Processing: A Survey,” Journal of VLSI Signal Processing, vol. 28, pp. 7-27, June 2001.
[27] K. Bondalapati and V.K. Prasanna, “Reconfigurable Computing Systems,” in Proc. of IEEE, vol. 90, pp. 1201-1217, July 2002.
[28] K. Compton and S. Hauck, “Reconfigurable Computing: A Survey of Systems and Software,” ACM Computing Surveys, vol. 34, pp. 171-210, June 2002.
[29] T.J. Todman et al., “Reconfigurable Computing: Architectures and Design Methods,” in Proc. of IEE Comp. and Dig. Techno., vol. 152, pp. 193-206, Mar. 2005.
[30] C. Y. Chen et al., “Analysis and Architecture Design of Variable Block Size Motion Estimation for H.264 / AVC,” IEEE Trans. Cir. and Sys. – I: Fund. Theory and Appl., vol. 53, pp. 578 – 593, Mar. 2006
[31] H. M. Jong, L. G. Chen, and T. D. Chiueh, “Parallel Architectures for 3-Step Hierarchical Search Block-Matching Algorithm,” IEEE Trans. Cir. and Sys. Video Techno., vol. 4, pp.407-416, Aug. 1994.
[32] R. Hartenstein, “Coarse Grain Reconfigurable Architectures,” in Proc. of 2001 ASP-DAC, Yokohama, Japan, Jan. 2001.
[33] S. Ramachandran and S. Srinivasan, “A Dynamically Reconfigurable Video Compression Scheme Using FPGAs with Coarse-Grain Parallelism,” VLSI Design, vol. 15, pp. 521-528, Mar. 2002.
[34] S. Vassiliadis and I. Sourdis, “Reconfigurable Fabric Interconnects,” in Int. Sym. System-on-Chip, pp. 1-4, Nov. 2006.
[35] H. Zhang et al., “Interconnect Architecture Exploration for Low-Energy Reconfigurable Single-Chip DSPs,” in Proc. of WVLSI, Orlando, Florida, USA, April 1999.
[36] H. Singh et al., “MorphoSys: A Reconfigurable Architecture for Multimedia Applications,” in Proc. of the 11th Brazilian Sym. Integrated Circuit Design, pp.134-139, Sep. 1998.
[37] J.C. Chen, C.F. Shen and S.Y. Chien, “Coarse-Grained Reconfigurable Image Stream Processor for Digital Still Camera and Camcorders,” in Proc. of IEEE Custom Integ. Cir. Conf., San Jose, USA, Sep. 2007.
[38] S.M. Carta, D. Pani and L. Raffo, “Reconfigurable Coprocessor for Multimedia Application Domain,” Journal of VLSI Signal Process. Sys., vol. 44, pp. 135-152, Aug. 2006.
[39] R. Hartenstein, “A Decade of Reconfigurable Computing: A Visionary Retrospective,” in Proc. of 2001 DATE, pp. 642-649, 2001.