本論文主要針對H.264/AVC無失真壓縮技術以及HEVC快速演算法設計兩個主題作研究。傳統的H.264/AVC無失真壓縮系統主要是利用既有的框內預測程序(Intra Prediction)來進行差值編碼。但為達到無失真的目的，其失真編碼系統中常用的能量轉換(Transform)與量化(Quantization)程序都會被略過，因此造成壓縮效率大幅下降。為了提升H.264/AVC無失真編碼系統的壓縮效率，本論文首先改變傳統H.264/AVC無失真編碼系統的架構，提出了階層式無失真編碼系統，主張保留原始H.264/AVC失真編碼系統的架構，並將編碼過程中所產生的失真資料送到第二層編碼系統進行編碼，以確保無失真的結果以及增加壓縮效能。接著為了改善H.264/AVC無失真壓縮系統的框內預測效能，更提出了利用不同內插方法所產生的新的框內預測模式，提升了壓縮效能。最後，為了將整體系統最佳化，本論文嘗試導入哥倫布編碼(Golomb-Rice coding)來對失真資料進行編碼，以改善熵編碼的編碼效率，同時為了進一步提升壓縮效能，也針對階層式無失真編碼系統另外提出一個新的位元率預測模型，以利找到最佳的量化參數，達到最佳的壓縮效率。經過實驗結果的驗證，證實了本論文所提出的方法能確實改善無失真壓縮的壓縮效能。
在HEVC快速演算法設計方面，我們首先針對HEVC框內預測模式以及四分樹架構進行加速，由於在HEVC編碼系統中，新的框內預測模式高達35種，其中與角度方向相關的框內預測模式佔了33種。雖然新的框內預測模式可以有效提升整體的壓縮效率，但複雜度卻也是相對的提高。為了降低HEVC的框內預測編碼複雜度，我們首先將一個最大編碼單元(LCU)切割成數個2x2大小的區塊，利用哈達瑪轉換(Hadmard-Transform)來分析每個區塊所呈現的能量分佈是偏屬於哪個角度，透過統計分析每個角度的能量大小、出現頻率以及空間相似性後找出每個不同大小編碼單元的最適合角度，並以最適角度來當作框內預測的最終方向以及四元樹是否分割的依據。另外，在HEVC框外預測(Inter Prediciton)的部分則是提出了可適性運動搜尋範圍決策機制(Adaptive Motion Search Range Decision)，讓HEVC在框外預測的運動向量搜尋過程(Motion Estimation)中可以有選擇性的決定搜尋範圍，以降低HEVC的編碼複雜度。根據實驗結果也證實了本論文提出的方法能確實改善HEVC的壓縮速度。

In this dissertation, it includes two major researches. The first one is about the lossless coding technology of H.264/AVC, and the second one is to develop fast algorithms for high efficiency video coding (HEVC) standard. In lossless coding technology, we firstly propose a hierarchical lossless video coding architecture that based on H.264/AVC lossy coding system to improve the compression ratio. To improve the coding efficiency, we further proposed a new intra prediction process to replace the sample-by-sample DPCM method of intra prediction. Finally, we try to optimize the lossless coding architecture, we proposed a hierarchical lossless coding method where the input video will be firstly encoded by H.264/AVC coder with a QP selector in the base layer and the coded error is encoded by a QP-adaptive Rice coder in the enhancement layer. Simulation results show that the proposed hierarchical lossless coding architecture achieves better compression ratio than the traditional H.264/AVC based lossless coding systems.
To develop fast algorithm of HEVC, a fast intra mode decision algorithm with an early CU splitting termination strategy is proposed to reduce the computation complexity. In HEVC, the intra prediction needs to try 35 modes for different combinations of variable-size CUs such that the complexity becomes extremely high. To reduce the coding complexity, we firstly divide a LCU into non-overlapped 2x2 blocks and then use the Hadamard transform (HT) coefficients to analyze their vertical and horizontal magnitudes to predict the direction orientation and direction strength of 2x2 blocks. To decide the best intra mode, we estimate the fitness of each intra mode by considering appearance probability and direction strength. In the same time, we also employ the evaluation of weighted directional consistency to design an early termination decision algorithm. In addition, we also proposed an adaptive motion search range decision algorithm to reduce the coding complexity of the HEVC inter prediction procedure. The performance of motion estimation (ME) highly depended on the selection of motion vector predictor (MVP). With this point of view, we analyze the relationship of motion vector difference (MD) between MVP and motion vector (MV) to design an adaptive motion search range algorithm. Experimental results show that the proposed algorithms not only decrease the coding complexity but also keep the coding performance.

[1] T. Wiegand, G. J. Sullivan, G. Bjontegaard, and A. Luthra, “Overview of the H.264/AVC Video Coding Standard,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 560–576, Jul. 2003.
[2] I. E. G. Richardson, H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia, Chichester, UK: John Wiley & Sons, 2003.
[3] ITU-T Recommendation H.264 & ISO/IEC 14496-10 AVC, Advanced Video Coding for Generic Audiovisual Services, version 3, 2005.
[4] K. Wahid, V. Dimitrov, and G. Jullien, ”New Encoding of 8 8 DCT to make H.264 Lossless,” in proc. Asia Pacific Conf. Circuits and Syst. (APCCAS 2006), Dec. 2006, pp. 780–783.
[5] S. T. Wei, S. R. Shen, B. D. Liu, J. F. Yang, “Lossless image and video coding based on H.264/AVC intra predictions with simplified interpolations,” in proc. Int. Conf. Image Process. (ICIP 2009), Cairo, Egypt, Nov. 2009, pp. 633–636.
[6] Q. Zhang, Y. Dai, and C. C. J. Kuo, “Lossless video compression with residual image prediction and coding (RIPC),” in proc. Int. Symp. Circuits and Syst. (ISCAS 2009), Taipei, Taiwan, May 2009, pp. 617–620.
[7] Y. L. Lee, K. H. Han, and S. C. Lim, Lossless Intra Coding for Improved 4:4:4 Coding in H.264/MPEG-4 AVC, ISO/IEC JTC1/SC29/WG11 and ITU-T Q6/SG16 Joint Video Team document JVT-P016, Jul. 2005.
[8] Y. L. Lee and K. H. Han, Complexity of the Proposed Lossless Intra, ISO/IEC JTC1/SC29/WG11 and ITU-T Q6/SG16, Document JVT-Q035r1, Oct. 2005.
[9] ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6, Lossless Coding and QP Range Selection, Document JVT-C023, May, 2002.
[10] ISO/IEC JTC1/SC29/WG11 and ITU T SG16 Q.6, Draft Text of H.264/AVC Fidelity Range Extensions Amendment, Document JVT-L047, Jul. 2004.
[11] B. Bross, W. J. Han, G. J. Sullivan, J. R. Ohm, and T. Wiegand, High Efficiency Video Coding (HEVC) Text Specification Draft 9, document JCTVC-K1003, ITU-T/ISO/IEC Joint Collaborative Team on Video Coding (JCT-VC), Oct. 2012.
[12] G. J. Sullivan, J. R. Ohm, W. J. Han, and T. Wiegand, “Overview of the High Efficiency Video Coding (HEVC) Standard,” IEEE Trans. Circuits Syst. Video Technol., 22, (12), pp. 1649-1668, Dec. 2012.
[13] J. R. Ohm, G. J. Sullivan, H. Schwarz, T. K. Tan, and T. Wiegand, “Comparison of the coding efficiency of video coding standards— Including High Efficiency Video Coding (HEVC),” IEEE Trans. Circuits Syst. Video Technol., 22, (12), pp. 1669–1684, Dec. 2012.
[14] F. Bossen, B. Bross, K. Sühring, and D. Flynn, “HEVC complexity and implementation analysis,” IEEE Trans. Circuits Syst. Video Technol., 22, (12), pp. 1685–1696, Dec. 2012.
[15] Y. L. Lee, K. H. Han, and G. J. Sullivan, “Improved Lossless Intra Coding for H.264/MPEG-4 AVC,” IEEE Trans. on Image Processing, vol. 15, no. 9, pp. 2610 – 2615, Sep. 2006.
[16] Y. L. Lee, K. H. Han, and Y. K. Lee, “Method and apparatus for lossless encoding and decoding,” U.S. Patent 2005/0271142 A1, Dec. 2005.
[17] J. R. Ding, J. Y. Chen, F. C. Yang, and J. F. Yang, “Two-layer and adaptive entropy coding algorithms for H.264-based lossless image coding,” in proc. Int. Conf. on Acoustics Speech Signal Process (ICASSP 2008), Las Vegas, Nevada, Mar. 2008, pp. 1369–1372.
[18] S. T. Wei, C. W. Tien, B. D. Liu, and J. F. Yang, “Adaptive Truncation Algorithm for Hadamard-Transformed H.264/AVC Lossless Video Coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 21, no. 5, pp. 538–549, May 2011.
[19] H.264/AVC JM Reference Software [Online]. Available: http://iphome.hhi.de/suehring/tml
[20] Y. K. Tu, J. F. Yang, and M. T. Sun, “Efficient Rate-Distortion Estimation for H.264/AVC Coders,” IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 5, pp. 600–611, May 2006.
[21] K. Y. Liao, J. F. Yang, and M. T. Sun, “Rate-Distortion Cost Estimation for H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 20, no. 1, pp. 38–49, Jan. 2010.
[22] JCT-VC, “WD1: Working Draft 1 of High-Efficiency Video Coding”, JCTVC-C403, JCT-VC Meeting, Guangzhou, Oct. 2010.
[23] J. Heo, and Y. S. Ho, “Efficient Level and Zero Coding Methods for H.264/AVC Lossless Intra Codin,” IEEE Trans. Signal Process Letters, vol. 17, no. 1, pp. 87–90, Jan. 2010.
[24] R. G. Gallager and D. C. Van Voorhis, “Optimal Source Codes for Geometri- cally Distributed Integer Alphabets,” IEEE Trans. on Inform. Theory, vol 21, pp.228 - 230, Mar. 1975.
[25] N. Merhav, G. Seroussi, and M. J. Weinberger, “Coding for sources with two-sided geometric distributions and unknown parameters,” IEEE Trans. on Inform. Theory, vol. 46, pp. 121– 135, Jan. 2000.
[26] P. G. Howard and J. S. Vitter, “Fast and Efficient Lossless Image Compression,” Proc. of Data Compression Conference, pp. 351–360, 1993.
[27] J. Lainema, F. Bossen, W. J. Han, J. Min, and K. Ugur, “Intra Coding of the HEVC Standard,” IEEE Trans. Circuits Syst. Video Technol., 22, (12), pp. 1792–1801, Dec. 2012.
[28] J. Lainema, and K. Ugur, “Angular intra prediction in high efficiency video coding (HEVC),” Proc. of the 13th International Workshop on Multimedia Signal Processing (MMSP), Oct. 2011, pp. 1–5.
[29] A. Tanizawa, J. Yamaguchi, T. Shiodera, T. Chujoh, and T. Yamakage, Improvement of intra coding by bidirectional intra prediction and dimensional directional unified transform, document JCTVC-B042, MPEG-H/JCT-VC, Geneva, Switzerland, Jul. 2010.
[30] Y. Piao, J. Min, and J. Chen, Encoder improvement of unified intra prediction, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, Document: JCTVC-C207, Guangzhou, Oct. 2010.
[31] T. L. da Silva, L. V. Agostini, L. A. da Silva Cruz, "Fast HEVC intra prediction mode decision based on ANGLE direction information," Proc. of the 20th European Signal Processing Conference (EUSIPCO), Aug. 2012, pp.1214-1218.
[32] W. Jiang, H. Ma, Y. Chen, "Gradient based fast mode decision algorithm for intra predicion in HEVC," Proc. of the 2nd International Conference on Consumer Electronics, Communications and Networks (CECNet), Apr. 2012, pp. 1836-1840.
[33] A. C. Tsai, A. Paul, J. C. Wang, and J. F. Wang, “Intensity gradient technique for efficient intra-prediction in H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 18, no. 5, pp. 694–698, May 2008.
[34] Y. H. Huang, T. S. Ou, and H. Chen, “Fast decision of block size, prediction mode, and intra block for H.264 intra prediction,” IEEE Trans. Circuits Syst. Video Technol., vol. 20, no. 8, pp. 1122–1132, Aug. 2010.
[35] K. Bharanitharan, B.-D. Liu, J. F. Yang, and W. C. Tsai, “A low complexity detection of discrete cross differences for fast H.264/AVC intra prediction,” IEEE Trans. Multimedia, vol. 10, no. 7, pp. 1250–1260, Nov. 2008.
[36] C. H. Tseng, H. M. Wang, and J. F. Yang, “Enhanced intra-4x4 mode decision for H.264/AVC coders,” IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 8, pp. 1127–1132, Aug. 2006.
[37] H. Zeng, K. K. Ma, and C. Cai, “Hierarchical intra mode decision for H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 20, no. 6, pp. 907–912, Jun. 2010.
[38] M. H. Chan, Y. B. Yu, and A. G. Constantinides, “Variable size block matching motion compensation with applications to video coding,” IEE Proc. of Communications, Speech and Vision, 137, (4), pp. 205-212, Aug. 1990.
[39] G. J. Sullivan, and R. L. Baker, “Efficient quadtree coding of images and video,” IEEE Trans. on Image Processing, 3, (3), pp. 327-331, May 1994.
[40] G. Bjontegaard, Calculation of average PSNR difference between RD-curves, 13th VCEG-M33 Meeting, Austin, TX, Apr. 2-4, 2001.
[41] W. Yang, O. C. Au, C. Pang, J. Dai, F. Zou, X. Wen, and Y. Liu, “An efficient motion vector coding algorithm based on adaptive predictor selection,” Proc. IEEE ISCAS, June 2010, pp. 2175-2178.
[42] C. C. Lou, S. W. Lee and C. C. Jay Kuo, “Motion vector search window prediction in memory-constrained systems,” Proc. SPIE, vol. 7443, pp. 1-12, Aug. 2009.
[43] S. Fukushima, H. Nakamura, and H. Takehara, “Simplification of AMVP spatial candidate derivation,” Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, Doc. JCTVC-H0078, February 2012.
[44] Y. H. Ko, H. S. Kang, and S. W. Lee, “Adaptive search range motion estimation using neighboring MVDs,” IEEE Transactions on Consumer Electronics, vol. 57, no. 2, May 2011, pp. 726-730.
[45] I. K. Kim, S. I. Sekiguchi, W. J. Han, K. McCann, and B. Bross, “High efficiency video coding (HEVC) test model 5 encoder description,” Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, Doc. JCTVC-G1102 Nov. 2011.