在新一代的H.264/AVC影像壓縮標準中，畫間編碼依然是一個十分耗費運算量的核心技術。因為在H.264裡頭它採用了以往在MPEG1/2、H.261、H263壓縮標準中不常見的編碼方法；像是可變區塊大小的移動估測、非整數的移動估測，還有多重參考畫面…等的設計。這些新的技術雖然可以提高H.264的壓縮視訊品質以及降低視訊壓縮的編碼位元數，但是所帶來的負面影響則是增加了整個編碼器的運算複雜度，而且讓H.264不易應用在即時的影像壓縮上。因此我們希望提出一個可以改善原始編碼架構的編碼流程來降低整個運算複雜度，另外再設計一個VLSI硬體來輔助計算H.264的可變動區塊大小的移動估測。
在我們所設計的畫間模式選擇演算法中，我們將原始要用全模式偵測的方法來找到最佳解模式的編碼器，改變成利用[21]的統計分析方法來預測一個模式的編碼器。在本篇論文中，我們使用統計分析方法配合移動向量合併的兩個技巧設計出第一個演算法；但是第一個演算法的效能差強人意，於是我們就針對第一個演算法的缺點進行改良。最後利用壓縮位元率回授控制的方法設計出第二個演算法，從第二個演算法的實驗結果發現，我們可以有效的改善第一個演算的缺點。從實驗結果發現這個演算法的確可以達到加速壓縮的目的，而且對於低移動複雜度的影像可以達到較好的壓縮效果。
在硬體設計上，我們利用了二維心脈陣列的架構當作我們SAD運算核心，另外我們同時考量MVCost的cost成本，使得整個硬體架構對於畫間編碼運算更為完整。不僅如此，在我們的硬體設計上還加入一個額外設計的快速移動向量搜尋演算法，由於快速演算法的加入使得我們處理一個方塊所需的運算次數可以大幅減少。最後我們將整個硬體架構利用Synopsys的Design Compiler和TSMC 0.13μm 1P8M 的製程做合成，從合成的實驗結果可以看到我們硬體能操作在200MHz的頻率，佔了約191k的邏輯閘數目；最後一樣將我們的實驗結果與其他的會議論文和期刊論文做比較得知我們的硬體使用率也是有不錯的效能表現。

Inter frame coding has been a serious problem for a long time, particularly in the emerging coding standard, H.264/AVC, many novel features are adopted, i.e. variable block size motion estimation, sub-pixel motion estimation, multi reference frame… etc. It results in a heavy computation and coding time for inter frame coding. Therefore many related fast algorithms and VLSI architectures are proposed to reduce the complexity of inter frame coding.
In this thesis, we proposed a fast inter mode decision algorithm and design a 2-D systolic array for VBSME. These are the two main modules of inter frame coding in H.264/AVC. For the proposed fast inter mode decision algorithm, we took advantage of stochastic analysis method proposed by [21] to predict the spatial correlation in one MB and further improved the stochastic analysis by the rate feedback scheme. Our proposed algorithm is integrated into the JVT reference software JM11.0. From the simulation results, it reveals that our proposed fast inter mode decision algorithm can efficiently save the coding time up to 35.72% with negligible PSNR loss and Bits increasing.
As for the VLSI architecture of VBSME, we presented a hardware oriented fast motion estimation (FME) algorithm first and implemented the proposed FME algorithm into a 2-D systolic array based on AS2 proposed by [25]. To verify the FME algorithm we implement it in JM11.0 and the simulation result shows that the FME algorithm can speed up 73.02% coding time over standard with slightly PSNR loss and bit rate increases. Hence we could implement the FME in hardware design using Synopsys Design Complier and Artisan Memory compiler. The chip is realized in CMOS TSMC 0.13μm 1P8M technology, it can work 200MHz and the gate count is 191k including the memory modules. Compare with previous works our hardware IP can archive the best throughput rate.

[1] H. Sun, X. Chen, and T. Chiang, "Digital Video Transcoding for Transmission and Storage," CRC Press, 2005
[2] ISO/IEC JTC1 IS 14386 (MOEG-4), "Generic coding of moving pictures and associated audio," 2000.
[3] Iain E. G. Richardson, "H.264 and MPEG-4 Video Compression: Video Coding for Next Generation Multimedia," John Wiley Press, 2003
[4] B. Jeon, and J. Lee, "Fast mode decision for H.264," 10th Meeting: JVT-J033, Hawaii, USA, December 2003
[5] Y. W. Huang, B. Y. Hsieh, S. Y. Chen, S.Y. Ma and L. G. Chen, "Analysis complexity reduction of multiple reference frames motion estimation of H.264/AVC," IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 4, April 2006
[6] L. M. Ho, "Variable Block Size Motion Estimation Hardware for Video Encoders," Computer Science and Engineering, The Chinese University of Hong Kong, November 2006.
[7] D. Salomon, "Data Compression: The Complete Reference," Springer, 2004.
[8] P. D. Symes, "Digital Video Compression," McGraw-Hill, 2004.
[9] Y. H. Su, and W. Y. Su, "A Progressive Design Flow and Its Application to H.264 BP RDO Encoder VLSI Design," Computer Science and Information Engineering, National Cheng Kung University
[10] I. Choi, J. Lee, and B. Jeon, "Fast Coding Mode Selection with Rate-Distortion Optimization for MPEG-4 Part-10 AVC/H.264," IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 12, December 2006
[11] C. Grecos and M. Y. Yang, "Fast Inter Mode Prediction for P Slice in the H.264 Video Coding Standard," IEEE Trans. Broadcasting, vol. 51, no. 2, June 2005.
[12] D. Wu, F. Pan, K. P. Lim, S. Wu, Z. G. Li, X. Lin, S. Rahardja, and C. C. Ko, "Fast Intermode Decision in H.264/AVC Video Coding, "IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 6, July 2005.
[13] X. J. Zhu and S. A. Zhu, "Fast Mode Decision and Reduction of Reference Frames for H.264 Encoder," IEEE Int'l Conference on Control and Automation (ICCA), June 2005.
[14] P. Yin, H. Y. Tourapis, A. M. Tourapis, and J. Boyce, "Fast Mode Decision and Motion Estimation for JVT/H.264," IEEE Int'l Conference on Image Processing, vol. III, pp.853-856, September 2003
[15] D. Wu, S. Wu, K. P. Lim, F. Pan, and X. Lin, "Block inter mode decision for fast encoding of H.264," IEEE Int'l Conference on Speech, Acoustics, and Signal Processing, vol. III, pp. 181-184, May 2004
[16] B. Feng, G. Zhu, and W. Liu, "Fast Adaptive Inter-Prediction Mode Decision Method for H.264 Based on Spatial Correlation," IEEE Int'l Symposium on Circuits and Systems (ISCAS), 2006.
[17] Andrew R. Webb, QinetiQ Ltd., Malvern, "Statistical Pattern Recognition," John Wiley Press, 2002
[18] Simon Haykin, "Adaptive Filter Theory," Prentice-Hall Press, 2002
[19] Stan Z. Li, "Markov Random Field Modeling in Image Analysis," Springer-Verlag Press, 2001
[20] M.R. El-Sakka and M.S. Kamel, "A Segmentation Criterion for Digital Image Compression," Proc of ICASSP, vol. 4, May 1995.
[21] C. S. Won, "Variable Block Size Segmentation for Image Compression Using Stochastic Models," IEEE 1996
[22] G. Bjontegaard, "Calculation of Average PSNR Differences Between RD-Curves Doc," VCEG-M33, Austin, TX. April 2001.
[23] JVT Reference Software Version JM 11.0, [available] http://iphome.hhi.de/suehring/tml
[24] V. Liguori and K. Wong, "Designing A Real-Time HDTV 1080p Baseline H.264/AVC Encoder Core," Ocean Logic Pty Ltd
[25] T. Komare, P. Pirsch, "Array Architecture for Block Matching Algorithms," IEEE Trans. Circuits and Sys., vol. 36, no. 10, October 1989.
[26] S. Y. Yap and V. McCanny, "A VLSI Architecture for Variable Block Size Video Motion Estimation," IEEE Trans. Circuits Syst. – II, vol. 51, no. 7, July 2004.
[27] L. Deng, W. Gao, M. Z. Hu, and Z. Z. Ji, "An Efficient Hardware Implementation for Motion Estimation of AVC Standard," IEEE Trans. Consumer Electronics, vol. 51, no. 4, November 2005.
[28] C. Y. Chen, S. Y. Chine, Y. W. Hung, 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 IEEE Trans. Circuits Syst. – I, vol. 53, no. 2, Feb. 2006.
[29] Y. Song, Z. Y. Liu, S. GOTO, and T. Ikenaga, "Scalable VLSI Architecture for Variable Block Size Integer Motion Estimation in H.264/AVC,"IEICE Trans. Fundamentals, vol. E89-A, no. 4, April 2006.
[30] J. B. Kim, S. C. Byun, Y. H. Kim, and B. H. Ahn, "Fast Full Search Motion Estimation Algorithm Using Early Detection of Impossible Candidate Vectors," IEEE Trans. Signal Processing , vol. 50, no. 9, September 2002.
[31] C.C. Wang, J. Y. Kao, and Y. K. Lin, "Efficient Motion Estimation Using a Sorting-Based Early Termination Algorithm in H.264 Video Coding," IEEE Int'l Symposium on Multimedia (ISM), December 2006.
[32] 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 Trans. Circuits Syst. Video Technol., vol. 12, no. 1, January 2002
[33] AI Bovik, "Handbook of Image & Video Processing," Elsevier Academic Press, 2005
[34] N. Carlson, "Video Compression and the Future," Networking, April 2006.
[35] J. Xu, and Y. He, "A Novel Rate Control for H.264," IEEE Int'l Symposium on Circuits and Systems (ISCAS), 2004
[36] C. W. Lin, and S. M. Guo, "Enhanced Block Motion Estimation Based on Dynamic Threshold Schema for H.264/AVC Video Coding," Computer Science and Information Engineering, National Cheng Kung University
[37] H. W. Cheng, and W. Y. Su, "Mode Decision of H.264/AVC Motion Estimation with RDO," Computer Science and Information Engineering, National Cheng Kung University
[38] T. Y. Kuo, and C. H. Chan, "Fast Variable Block Size Motion Estimation for H.264 Using Likelihood and Correlation of Motion Field," IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 10, October 2006
[39] Richardson, Iain E. G, "Video codec Design : Developing Image and Video compression systems," Wiley 2002
[40] Singh, Ajit, "Optic flow Computation : A unified perspective," IEEE Computer Society, 1991
[41] Spiegelhalter, D. J. Richardson, S. Gilks, and W. R., "Markov chain Monte Carlo in practice," Chapman & Hall/CRC, 1995
[42] C. Wei, M. Z. Gang, "A Novel VLSI Architecture for VBSME in MPEG-4 AVC/H.264," IEEE Int'l Symposium on Circuits and Systems (ISCAS), May 2005.
[43] Y. W. Huang, T. C. Wang, B. Y.Hsieh, "Hardware Architecture Design for Variable Block Size Motion Estimation in MPEG-4 AVC/JVT/ITU-T H.264," IEEE Int'l Symposium on Circuits and Systems (ISCAS), 2003
[44] M. Kim, I. Hwang, S. I. Chae, "A Fast VLSI Architecture for Full-Search Variable Block Size Motion Estimation in MPEG-4 AVC/H.264," Asia and South Pacific Design Automation Conference (ASP-DAC), 2005.
[45] L.deVos, N. Schobinger, "VLSI Architecture for a flexible block matching processor," IEEE Trans. Circuits Syst. Video Tchnol., May 1995.
[46] J. F. Shen et al., "A novel low-power full-search block matching motion estimation design for H.263+," IEEE Trans. Circuits Syst. Video Technol., 2001
[47] C. Wei, M. Z. Gang, L. Z. Qiang, Z. Yan, "VLSI Architecutre design for variable-size block motion estimation in MPEG-4 AVC/H.264," IEEE Asia Pacific Conference on Circuits and Systems, December 2004.
[48] E. Sifakis, L. Grinias, and G. Tziritas, "Video Segmentation Using Fast Marching and Region Growing Algorithms," EURASIP Journal on Applied Signal Prcoseeing, vol. 4, 2004.
[49] Q. Liu, R. J. Sclabassi, C. C. Li, and M. Su, "An Application of MAP-MRF to Change-Dectection in Image Sequence Base on Mean Filed Theory," EURASIP Journal on Applied Signal Processing, vol. 13, 2005.
[50] Alan C. Bovik, "Handbook of image and video processing," Academic Press; 1st edition May 31, 2000
[51] F. Forbes, and N. Peyrard, "Hidden Markov Random Field Model Selection Criteria Based on Mean Field-Like Approximations," IEEE Trans on Pattern Analysis and Machine Intelligence, vol. 25, no. 9, September 2003.