臺灣博碩士論文加值系統

現今的無線手機上，即時視訊編碼之應用，如錄影與視訊會議，已經很普遍。最新的視訊壓縮標準H.264其視訊編碼器採用多個編碼工具以達到高編碼效率，但必須花費很高的運算複雜度。然而手機上即時視訊編碼所被允許的運算複雜度是有限的，因此控制編碼器的運算複雜度使其低於複雜度限制並且維持最佳位元率-失真效能是很重要的，本論文提出一個基於編碼增益之複雜度控制法，適用於以一般處理器編碼視訊之無線手機。
在基於編碼增益之複雜度控制法中，我們提出了分析編碼工具之編碼效率的程序，且提出了這些工具的使用策略。藉由使用這些策略與分配較多複雜度給編碼效率較高的工具，這控制法可以使整個編碼器的編碼效益達到最佳。這控制法本身的運算複雜度很小，是一實用的方法。雖然編碼工具之編碼效率因平台而異，本論文提出一個設計程序，使設計者可以針對不同平台設計出高效率的複雜度控制方法。
因為動態預估、轉換、與熵編碼的運算複雜度最高，這三個編碼工具之複雜度分配會明顯影響整個編碼器的位元率-失真表現。本論文提出一個基於精減模型之複雜度分配法以獲得這三個工具的最佳複雜度。這分配法由二個演算法組成。第一個演算法做編碼工具間之複雜度分配，基於一個新的複雜度-位元率-失真模型，這方法分配接近最佳的複雜度給針對所有巨集區塊的動態預估、轉換、與熵編碼。根據這個模型，這演算法能以很小的代價獲得每個編碼工具之接近最佳的複雜度。基於一個新的動作預估的複雜度-失真模型，第二個演算法做巨集區塊間之複雜度分配，以進一步分配接近最佳的複雜度給每一個巨集區塊。實驗結果顯示這二個演算法比既有的演算法擁有較低的運算複雜度代價，且有較佳的位元率-失真表現。

Applications of real-time video encoding, such as video recording and video conference, commonly exist in modern wireless handsets. An H.264 video encoder adopts multiple encoding tools to achieve high coding efficiency at the expense of high computational complexity. The allowable computational complexity for real-time video encoding, however, is generally limited in a wireless handset. Therefore, a complexity control mechanism that well allocates the computational complexity of video encoding under the complexity constraint while maintaining optimal rate-distortion performance is important. This dissertation proposes a Coding-Gain-Based (CGB) complexity control for wireless handsets where video encoding is executed by a general-purpose processor.
In the Coding-Gain-Based (CGB) complexity control, we describe the procedure to obtain the coding efficiency of each encoding tool and present a utilization strategy for these tools. By using the utilization strategy and allocating more complexity to the encoding tools which have higher coding efficiency, the CGB method is able to maximize the overall coding efficiency of the encoder. The complexity overhead of this method is very small, and is a practical method. Though the coding efficiency of encoding tools may vary with different platforms, this research provides a design procedure which allows designers to develop a high efficient complexity control algorithm on different platforms.
Because Motion Estimation (ME), transform, and entropy coding are the most complexity-consuming tools, complexity allocation among these three tools influences the R-D performance of the encoder significantly. This dissertation proposes a Concise-Model-Based (CMB) complexity allocation to obtain the optimal complexity for these three tools. The CMB allocation is composed of two algorithms. The first algorithm performs Complexity Allocation among Encoding Tools (CAET) to allocate complexity to ME, PRECODING, and entropy coding for all MBs in a frame based on a new Complexity-Rate-Distortion (C-R-D) model. This model precisely reveals how ME, PRECODING, and entropy coding influence the C-R-D performance of the encoder with concise formulas. With respect to the model, the algorithm obtains the near-optimal complexity of ME, PRECODING, and entropy coding by a closed-form solution with small complexity overhead. Based on a new C-D model of Motion Estimation (ME), this work proposes the second algorithm that performs Complexity Allocation among Macro-Blocks (CAMB) to further allocate suitable complexity to each MB. Experiments performed on a software-optimized source code show that these two algorithms yield superior performance to the existing algorithms.

摘 要 I
ABSTRACT III
誌 謝 V
CONTENTS VI
LIST OF FIGURES VIII
LIST OF TABLES XI
1. INTRODUCTION 1
2. COMPLEXITY ANALYSIS AND THE EXISTING MODEL-BASED COMPLEXITY CONTROL 6
2-1. COMPLEXITY ANALYSIS OF H.264 VIDEO ENCODER 6
2-2. COMPLEXITY SCALABILITY OF ME, PRECODING, AND ENTROPY CODING 8
2-3. THE EXISTING CAET ALGORITHM 9
2-4. THE EXISTING CAMB ALGORITHM FOR ME 11
3. CODING-GAIN-BASED COMPLEXITY CONTROL 13
3-1. CODING EFFICIENCY ANALYSIS OF ENCODING TOOLS 14
3-2. CGB COMPLEXITY CONTROL ALGORITHM 22
3-3. EXPERIMENTAL RESULTS 28
4. CONCISE-MODEL-BASED COMPLEXITY ALLOCATION 35
4-1. THE NEW C-R-D MODEL OF VIDEO ENCODER 36
4-1-1. C-R-D Model of PRECODING 36
4-1-2. C-D Model of ME 43
4-1-3. The Overall C-R-D Model 45
4-1-4. The Optimal Algorithm of CAET 49
4-2. THE OPTIMAL ALGORITHM OF CAMB 51
4-2-1. CAMB for PRECODING and Entropy Coding 51
4-2-2. CAMB for ME 53
4-3. THE PROCEDURE OF CMB COMPLEXITY ALLOCATION 58
4-4. EXPERIMENTAL RESULTS 60
4-4-1. Comparison between the proposed and existing CAET algorithms 60
4-4-2. Comparison between the proposed algorithm and global search for CAET 60
4-4-3. Comparison between CAMB algorithms for ME 62
5. CONCLUSIONS AND FUTURE WORK 65
REFERENCES 66
APPENDIX 71

[1]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 Syst. Mag., vol. 4, no. 1, pp. 7–28, Apr. 2004.
[2]R. Min, T. Furrer, and A. Chandrakasan, “Dynamic voltage scaling techniques for distributed microsensor networks,” Proc. IEEE Computer Society Workshop VLSI (WVLSI’00), pp. 43–46, Apr. 2000.
[3]M. C. Chien, J. Y. Huang, and, P. C. Chang “Complexity control for H.264 video encoding over power-scalable embedded systems,” Proc. IEEE Symposium on Consumer Electronics, pp. 43–46, Apr. 2009.
[4]S. Kannangara, I. E. G. Richardson, A. J. Miller, “Computational complexity management of a real-time H.264/AVC encoder,” IEEE Trans. Circuits Syst. Video Technol., vol. 18, no. 9, pp. 1191–1200, Sep. 2008.
[5]I. E. G. Richardson, H.264 and MPEG-4 video compression. John Wiley & Sons, 2003.
[6]Z. He, Y. Liang, L. Chen, I. Ahmad, and D. Wu, “Power-rate-distortion analysis for wireless video communication under energy constraints,” IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 5, pp. 645-658, May 2005.
[7]ISO/IEC ITU-T Rec. H264: Advanced Video Coding for Generic Audiovisual Services, Joint Video Team (JVT) of ISO-IEC MPEG & ITU-T VCEG, Int. Standard, May 2003.
[8]S. Kannangara, I. E. G. Richardson, M. Bystrom, and Y. Zhao, “Complexity control of H.264 based on mode-conditional cost probability distributions,” IEEE Trans. on multimedia, vol. 11, no. 3, pp. 433–442, Apr. 2009.
[9]L. Su, Y. Lu, F. Wu, S. Li, and W. Gao, “Complexity-constrained H.264 video encoding,” IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 4, pp. 1-14, Apr. 2009.
[10]Y. Chen, T. Chen, C. Tsai, S. Tsai, and L. Chen, “Algorithm and architecture of power-oriented H.264/AVC baseline profile encoder for portable devices,” IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 8, pp. 1118-1128, Aug. 2009.
[11]H. Chang, J. Chen, B. Wu, C. Su, J. Wang, and J. Guo, “A dynamic quality-adjustable H.264 video encoder for power-aware video applications,” IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 12, pp. 1739-1753, Dec. 2009.
[12]S. W. Lee and C. C. Jay Kuo, “Complexity modeling for motion compensation in H.264/AVC decoder,” Proc. IEEE International Conference on Image Process, pp. 313–316, Oct. 2007.
[13]S. W. Lee and C. C. Jay Kuo, “Complexity modeling of spatial and temporal compensations in H.264/AVC decoding,” Proc. IEEE International Conference on Image Process, pp. 2504–2507, Oct. 2008.
[14]S. W. Lee and C. C. Jay Kuo, “Complexity modeling of H.264/AVC CAVLC/UVLC entropy decoders,” Proc. IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1616–1619, June 2008.
[15]N. Kontorinis, Y. Andreopoulos, and M. Van Der Schaar, “Statistical Framework for Video Decoding Complexity Modeling and Prediction,” IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 7, pp. 1000-1013, July 2009.
[16]W. Zia and F. Shafait, “Complexity reduction techniques for long-term memory motion compensated prediction based on spectral distortion analysis,” PCS, April 2006.
[17]Joint Model reference software version 10, Available: http://iphome.hhi.de/suehring/tml/index.htm.
[18]x264, Available: http://developers.videolan.org/x264.html.
[19] “Text description of joint model reference encoding methods and decoding concealment methods,” Munich, Germany, 2004, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG Doc.JVT-K049.
[20]T. Berger, Rate distortion theory. Englewood Cliffs, NJ: Prentice-Hall, 1984.
[21]C. Kim and J. Xin, “Hierarchical complexity control of motion estimation for H.264/AVC,” MITSUBISHI ELECTRIC RESEARCH LABORATORIES, TR2006-004, Dec. 2006. Available: http://www.merl.com.
[22]K. P. Chong and H. Zak, An introduction to optimization. John Wiley & Sons, 2001.
[23]T. Chiang and Y. Zhang, “A new rate control scheme using quadratic rate control model,” IEEE Trans. Circuits Syst. Video Technol., vol. 7, pp. 246-250, Feb. 1997.
[24]Z. He and S. Mitra, “A linear source model and a unified rate control algorithm for DCT video coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 11, pp. 970-982, Nov. 2002.
[25]Z. Chen, P. Zhou, and Y. He, “Fast integer pel and fractional pel motion estimation in for JVT,” JVT-F017r1.doc, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 6th meeting, Awaji, Island, JP, 5-13 Dec. 2002.
[26]Y. F. Ou, Z. Ma, T. Liu, Y. Wang, “Perceptual quality assessment of video considering both frame rate and quantization artifacts,” IEEE Trans. Circuits Syst. Video Technol., on line available.
[27]Goldstein, Abstract algebra. Prentics-Hall, 1973.
[28]T. Wiegand, H. Schwarze, A. Joch, F. Kossentini, and G. J. Sullivan, “Rate-constrained coder control and comparison of video coding standards,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 688-703, Jul. 2003.
[29]Lapin, Modern engineering statistics. International Thomson Publishing Asia, 1997.
[30]D. Wang, F. Speranza, A. Vincent, T. Martin, and P. Blanchfield, “Towards optimal rate control: a study of the impact of spatial resolution, frame rate, and quantization on subjective Video quality and bit rate,” in Proc. of VCIP’03, pp. 198–209.
[31]Y. Wang, S.-F. Chang, and A. Loui, “Subjective preference of spatio- temporal rate in video adaptation using multi-dimensional scalable coding,” in Proc. of ICME’04, vol. 3, Jun. 2004, pp. 1719–1722.
[32]G. Yadavalli, M. Masry, and S. S. Hemami, “Frame rate preference in low bit rate video,” in Proc. of ICIP, vol. 1, Nov. 2003, pp. I–441–4.
[33]J. McCarthy, M. A. Sasse, and D. Miras, “Sharp or smooth ?: Comparing the effects of quantization vs. frame rate for streamed video,” in Proc. of ACM CHI on Human Factors in Computing Systems, Apr. 2004, pp. 535–542.
[34]J. Y. C. Chen and J. E. Thropp, “Review of low frame rate effects on human performance,” IEEE Trans. on Systems, Man and Cybernetics, vol. 37, pp. 1063–1076, Nov. 2007.
[35]Z. Lu, W. Lin, B. C. Seng, S. Kato, S. Yao, E. Ong, and X. K. Yang, “Measuring the negative impact of frame dropping on perceptual visual quality,” in Proc. SPIE Human Vision and Electronic Imaging, vol. 5666, Jan. 2005, pp. 554–562.
[36]K. C. Yang, C. C. Guest, K. El-Maleh, and P. K. Das, “Perceptual temporal quality metric for compressed video,” IEEE Trans. on Multimedia, vol. 9, pp. 1528–1535, Nov. 2007.
[37]H. T. Quan and M. Ghanbari, “Temporal aspect of perceived quality of mobile video broadcasting,” IEEE Trans. on Broadcasting, vol. 54, no. 3, pp. 641–651, Sept. 2008.
[38]E. Ong, X. Yang, W. Lin, Z. Lu, and S. Yao, “perceptual quality metric for compressed videos,” in Proc. of ICASSP, vol. 2, Mar. 2005, pp. 581– 584.
[39]A. Bhat, I. Richardson, and S. Kannangara,” A new percetual quality metric for compressed video,” ICASSP ,v01.51, n0.3, pp. 933- 936, 2009.
[40]R. Feghali, D. Wang, F. Speranza, and A. Vincent, “Video quality metric for bit rate control via joint adjustment of quantization and frame rate,” IEEE Trans. on Broadcasting, vol. 53, no. 1, pp. 441–446, Mar. 2007.