在視訊編碼技術中，移動補償是資料可以大量壓縮的關鍵技術，透過移動補償去除視訊資料中大量時間上的冗餘，因此在視訊編碼系統中，用來取得移動向量的移動估測模組是不可或缺的，然而移動估測為了取得準確的移動向量，往往採取全搜尋法，因此含有非常高的計算複雜度與記憶體存取量，造成即時視訊編碼系統設計上的瓶頸。因此有許多的方法被提出來解決這些的問題，然而許多演算法並不適合硬體實現，同時也會造成編碼效能下降的問題。

傳統全搜尋演算法雖然計算複雜度高，但擁有以下優點：較佳的視訊編碼效能、規則資料流，提供較佳的設計彈性，易於平行化與資料再利用設計。可以透過調整搜尋範圍，降低計算複雜度，使編碼系統符合即時編碼條件。過去有許多的自適應搜尋範圍演算法被提出，透過對自然視訊的觀察，發現相鄰的區塊若是屬於同一個物件，通常有相近的移動向量，利用此特性，認為若相鄰區塊具高移動量，則採用較大的搜尋範圍，反之則可縮小搜尋範圍。然而這些方法並未考慮位元率失真成本的概念，當採用預測的搜尋中心時，即使區塊具有高移動量，並非真的需要大的搜尋範圍。

本篇論文提出基於移動一致性自適應搜尋範圍 (Adaptive Search Range based on Motion Consistency) 演算法，透過判斷相鄰區塊的移動一致性，調整搜尋範圍，當相鄰的區塊若是屬於同一個物件，通常具有移動一致性，最佳的移動向量會靠近預測的搜尋中心，即使目前區塊具高移動量，也僅需要小的搜尋範圍。實驗結果顯示，穩定有效減少 50% ~ 70% 的移動估測運算時間，而品質失真部分，經 PSNR 比較，失真微乎其微，最多下降 0.0064 dB，位元率增幅大多在 0.5% 以下，整體編碼效能，非常接近原始全搜尋演算法移動估測。

硬體架構方面，為了符合即時編碼需求，最大搜尋範圍需要採用八組平行處理單元陣列設計，當自適應搜尋範圍演算法採用較小的搜尋範圍時，則可以關閉部分處理單元陣列，除了減少記憶體存取功率消耗也減少處理單元功率消耗。硬體實作使用TSMC 90nm 製程，操作頻率為 200 MHz，總邏輯閘數為 632 K，記憶體大小為 9 KB，可支援 HDTV 1080p 的即時視訊編碼，設定參考畫面1張，最大搜尋範圍 64 × 64。

In video coding technique, motion compensation is a key technique that data can be compressed greatly. Using motion compensation can remove a large amount of temporal redundancy of video data. Therefore, motion estimation used to obtain motion vectors is indispensable in the video encoder system. In order to obtain accurate motion vectors, however, the widely used full search algorithm would bring very large numbers of computational complexity and memory accesses. It is the bottleneck of a real-time video encoder system. Therefore, there are many methods proposed to solve these problems. However, most of these algorithms are not suitable for hardware implementation. Therefore, this will cause significant coding efficiency drop.

While the conventional full search algorithm contains high computational complexity, it has the following advantages: a better coding efficiency, regular dataflow, suitable for parallelism and data reuse design. It can decrease computational complexity by adjusting the search range to meet the real-time constraint. There are many adaptive search range algorithms proposed. Through the observation of natural video we can find that if the adjacent blocks belong to the same object, they usually have similar motion vectors. We can exploit this characteristic that if adjacent blocks have high motions, we can adopt a larger search range. On the contrary, if the adjacent blocks have lower magnitudes of motion, the search range can be shrunk. However, the above method doesn’t consider the concept of rate-distortion cost. When adopting the predictive search center, even if the blocks have high motions, we don’t really require a large search range.

In this thesis, we propose the Adaptive Search Range based on Motion Consistency algorithm, which can adaptive adopt different sizes of search range according to motion consistency between adjacent blocks. When the adjacent blocks belong to the same object, which is usually motion consistency. The best-match location of the motion vector is close to predictive search center. It only requires a small search range even though the current block contains high motions. Simulation results show that about 50% ~ 70% motion estimation computation time can be reduced with negligible quality drop and bitrate increase. The PSNR drops at most 0.0064 dB in the worst case and the bitrate increases less than 0.5%. The overall coding performance is very close to the original full search algorithm.

To meet the real-time encoding requirement, the proposed hardware architecture for the largest search range required to use 8-parallel processing element array design. When the adaptive search range algorithm adopts a smaller search range, it can disable part of processing element array. In addition to reducing the power consumption of memory accesses, the power consumption can also be reduced. We use TSMC 90 nm process to implement the proposed architecture, which can operate at 200 MHz. The total number of logic gate counts is 632 K and 9 KB on-chip memory is used. It can support HDTV 1080p real-time video encoding while number of reference frame is set to 1 and the maximum search range is 64 × 64.

[1] Cisco Systems, Inc. “Cisco Visual Networking Index (VNI): Global Mobile Data Traffic Forecast Update,” 2014–2019 White Paper, Feb 2015.
[2] “ITU-T Recommendation H.264 and ISO/IEC 14496-10 AVC”, Joint Video Team, Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification, 2003.
[3] T. Wiegand, G. J. Sullivan, G. Bjøntegaard, and A. Luthra, “Overview of the H.264/AVC Video Coding Standard,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 560-576, July 2003.
[4] T. Wiegand , H. Schwarz , A. Joch , F. Kossentini and G. J. Sullivan, “Rate-Constrained Coder Control and Comparison of Video Coding Standards,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 688 -703, 2003.
[5] T. C. Chen, S. Y. Chien, Y. W. Huang, C. H. Tsai, C. Y. Chen, T. W. Chen, and L. G. Chen, “Analysis and Architecture Design of an HDTV720p 30 Frames/s H.264/AVC Encoder,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 6, pp. 673-688, June 2006.
[6] J. Ostermann , J. Bormans , P. List , D. Marpe , M. Narroschke , F. Pereira , T. Stockhammer and T. Wedi, “Video Coding with H.264/AVC: Tools, Performance, and Complexity, ” IEEE Circuits and Systems Magazine, vol. 4, no. 1, pp. 7 -28, 2004.
[7] A. Puri , X. Chen and A. Luthra, “Video coding using the H.264/MPEG-4 AVC compression standard, ” Signal Processing: Image Communication, vol. 19, no. 9, pp. 793 -849 2004.
[8] G. J. Sullivan and T. Wiegand, “Video Compression—From Concepts to the H.264/AVC Standard,” Proceedings of the IEEE, vol. 93, no. 1, pp. 18–31, Jan. 2005.
[9] Iain E. G. Richardson, “H.264 and MPEG-4 Video Compression : Video Coding for Next Generation Multimedia,” John Wiley & Sons Ltd., Dec. 2003.
[10] Iain E. G. Richardson, “The H.264 Advanced Video Compression Standard, Second Edition,” John Wiley & Sons Ltd., Apr. 2010.
[11] L. M. Po and W. C. Ma, “A Novel Four-Step Search Algorithm for Fast Block Motion Estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 3, pp. 313–317, Jun. 1996.
[12] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, “A Novel Unrestricted Center-biased Diamond Search Algorithm for Block Motion Estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, no. 4, pp. 369–377, Aug. 1998.
[13] C. Zhu, X. Lin, and L. P. Chau, “Hexagon-based Search Pattern for Fast Block Motion Estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 5, pp. 349–355, May 2002.
[14] O. Ndili and T. Ogunfunmi, “Algorithm and Architecture Co-Design of Hardware-Oriented Modified Diamond Search for Fast Motion Estimation in H.264/AVC”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 21, no. 9, Sept. 2011.
[15] J. Zhou, D. Zhou, G. He, and S. Goto, “A 1.59 Gpixel/s Motion Estimation Processor with -211 to +211 Search Range for UHDTV Video Encoder,” IEEE Journal of Solid-State Circuits, vol. 49, no. 4, pp. 827-837, Apr. 2014.
[16] Y. N. Pan and T. H. Tsai, “Fast Motion Estimation and Edge Information Inter-Mode Decision On H.264 Video Coding,” IEEE International Conference on Image Processing, vol. 2, pp. 473-476, Sep. 2007.
[17] T. H. Tsai and Y. N. Pan, “High Efficiency Architecture Design of Real-Time QFHD for H.264/AVC Fast Block Motion Estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 21, no. 11, pp. 1646-1658, Nov. 2011.
[18] S. Saponara and L. Fanucci, “Data-Adaptive Motion Estimation Algorithm and VLSI Architecture Design for Low-Power Video Systems,” Proc. IEE Computers and Digital Techniques, vol. 151, no. 1, pp. 51-59, 2004.
[19] S. Goel, Y. Ismail, and M. A. Bayoumi, “Adaptive Search Window Size Algorithm for Fast Motion Estimation in H.264/AVC Standard,” in Proc. Midwest Symposium on Circuits and Systems, pp. 1557–1560, Aug. 2005.
[20] T. Yamada, M. Ikekawa, and I. Kuroda, “Fast and Accurate Motion Estimation Algorithm by Adaptive Search Range and Shape Selection”, Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.897-900, Mar. 2005.
[21] N. F. F. Chew and N. Badruddin, “Block Motion Estimation Using Directional Adaptive Search Window,” in TENCON 2006. 2006 IEEE Region 10 Conference, Hong Kong, pp. 1–4, Nov. 2006.
[22] Z. X. Chen, Y. Song, T. Ikenaga, and S. Goto, “A Dynamic Search Range Algorithm for Variable Block Size Motion Estimation in H.264/AVC,” in Proc. IEEE Int. Conf. Information, Communications & Signal Processing, pp. 1–4, Dec. 2007.
[23] J. Jung, J. Kim, and C.-M. Kyung, “A Dynamic Search Range Algorithm for Stabilized Reduction of Memory Traffic in Video Encoder,” IEEE Trans. Circuits Syst. Video Technol., vol. 20, no. 7, pp. 1041-1046, July 2010.
[24] Y. Ismail, J. B.McNeely, et al. “Fast Motion Estimation System Using Dynamic Models for H.264/AVC Video Coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol.22, no.1, pp. 28-42, January 2012.
[25] C. Y. Chen, S. Y. Chien, Y.W. Huang, T.C. Chen, T.C. Wang, and L.G. Chen, “Analysis and Architecture Design of Variable Block-Size Motion Estimation for H.264/AVC,” IEEE Transactions on Circuits and Systems—I: Regular Papers, vol. 53, no. 2, pp. 578-593, Feb. 2006.
[26] J. C. Tuan, T. S. Chang, and C. W. Jen, “On the Data Reuse and Memory Bandwidth Analysis for Full-Search Block-Matching VLSI Architecture,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 1, pp. 61–72, Jan. 2002.
[27] C. Y. Chen, C. T. Huang, and L. G. Chen, “Level C+ Data Reuse Scheme for Motion Estimation With Corresponding Coding Orders,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 4, pp. 553-558, Apr. 2006.
[28] Joint Video Team (JVT) H.264/AVC Reference Software JM 18.6 (July. 2014) [Online], Available: http://iphome.hhi.de/suehring/tml/download/
[29] Y. T. Chang, W. H. Chung, “A Dynamic Search Range Algorithm for H.264/AVC Full-Search Motion Estimation,” Circuits and Systems (APCCAS), 2010 IEEE Asia Pacific Conference on, pp. 124-127, 6-9 Dec. 2010.
[30] Z. Liu, Y. Song, M. Shao, S. Li, L. Li, S. Ishiwata, M. Nakagawa,S. Goto, and T. Ikenaga, “HDTV1080p H.264/AVC Encoder Chip Designand Performance Analysis,” IEEE J. Solid-State Circuits, vol. 44, no. 2, pp. 594–608, Feb. 2009.
[31] C. Y. Kao and Y. L. Lin, “A Memory-Efficient and Highly Parallel Architecture for Variable Block Size Integer Motion Estimation in H.264/AVC,” IEEE Transactions on VLSI systems, vol. 18, no. 6, pp. 866-874, June 2010.
[32] A. C. Tsai, K. Bharanitharan, J. F. Wang, and K. I. Lee, “Effective Search Point Reduction Algorithm and Its VLSI Design for HDTV H.264/AVC Variable Block Size Motion Estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 22, no. 7, pp. 981-988, July 2012.