本論文針對H.264/AVC提出數個位元率-失真函式，以降低其計算複雜度，並改善其效能。首先，我們提出有效之頻域中位元率-失真估計方法來降低 Lagrangian成本函式之運算。此外我們亦提出用於位元率控制與模式選擇之時域與簡化之頻域中位元率-失真分析。最後，我們提出改良之巨區塊層級位元控制方法，其中包含了位元率重新分配之機制。
在視訊編碼器中，每個編碼區塊之最佳模式可藉由完整的運算位元率 -失真成本耗費來決定，這同時考量了所有模式之失真與位元消耗。為了避免如此龐大的成本運算，我們發展了用於畫面間預測模式選擇，頻域中位元率估計與失真衡量方法，其依據量化與反量化後之整數轉換係數。利用我們所提出的方式，模式選擇流程中，實際的熵編碼，反轉換與像素重建均可省去。我們所發展的方法搭配快速動態估測與快速模式選擇演算法，可以達到40%成本函式運算時間的降低，與17%整個編碼時間之節省。
轉換係數可用Laplacian分佈來做模擬，且其參數可以用時域中統計資料來決定，例如平均絕對誤差，因此我們建議由時域資料以獲得位元率與失真的函式。利用我們所提出之估測方式，可決定H.264/AVC位元率控制時，於編碼階段前之量化參數。另外，直接利用轉換係數，我們亦提出簡化之位元率-失真衡量，其利用量化為基礎之臨界值法與數學運算。接著，位元率-失真成本由非零量化係數個數，整數轉換係數絕對值和與整數轉換係數之平方和來模擬。相較於需要真正運算位元率與失真的高複雜度失真函式，我們提出的有效成本函式可分別達到79.93%成本運算與22.61%編碼時間之節省；且整體效能只有些微下降：1.05%位元率之上昇與0.049dB PNSR之下降。
最後，利用所提出之估計方式，我們發展了巨區塊層級之位元率控制，來提升編碼效能。改良之位元重新分配機制是根據巨區塊實際與預測之複雜度來達成。簡化後的頻域位元率函式可被使用來決定動態估計後階段中模式選擇時所需量化參數。位元重新分配之模式選擇機制強化了H.264/AVC之位元率控制，提升之客觀視訊品質範圍約從0.05至1dB。

In this dissertation, we propose several rate-distortion functions to reduce the computational complexity and improve the performance of H.264/AVC coder. First, an efficient rate-distortion estimation algorithm in the transform-domain is proposed to reduce the complexity of the Lagrangian cost calculation. Secondly, spatial-domain and simplified transform-domain rate-distortion analyses are utilized for rate control and mode decision, respectively. Finally, an improved macroblock-layer rate-control with a bit-reallocation strategy is investigated.
In video coders, the optimal coding mode decision for each coding block can be achieved by exhaustively calculating the rate-distortion cost, which simultaneously considers the distortion performance and the coding bit consumption of all possible modes. The best mode is chosen from the one with the minimum Lagrange cost. To avoid the expensive computation of Lagrange costs, we propose transform-domain bit-rate estimation and distortion measures, based on quantized and inverse quantized integer transform coefficients, for inter-mode decision of H.264/AVC coders. With the proposed scheme, entropy coding, inverse transform, and pixel-reconstructions are not required in the rate-distortion optimization. With negligible degradation in coding performance, simulations demonstrate that the proposed estimation method achieves about 40% reduced computation time of the rate-distortion cost for the inter-mode decision, and saves about 17% total encoding time while combining with fast motion estimation and fast mode decision algorithms.
The transform coefficients can be modeled by a Laplacian distribution and its
iii
parameters can be determined by the spatial-domain statistics such as mean of absolute difference (MAD). Therefore, we suggest estimations of bit-rate and distortion functions obtained from spatial-domain data. By exploiting the proposed estimations, the quantization parameter can be predicted in the pre-encoding stage of rate control in H.264/AVC video encoding. Also, directly from the transform coefficients, a simplified rate-distortion measurement is introduced with quantization-based thresholding and manipulations. The rate-distortion cost is then modeled by the number of nonzero quantized coefficients, the sum of absolute integer transformed differences (SAITD), and sum of squared integer transformed differences (SSITD). Comparing to the high-complexity cost function, which should be calculated from real bit-consumption and true reconstructed distortion for each coding mode, the proposed efficient cost function can achieve 79.93% and 22.61% time savings of computing the rate-distortion cost and overall encoding, respectively, while introducing only slight degradation with 1.05% bit-rate increment and 0.049dB PSNR drop.
Finally, based on the proposed estimations, a rate-control scheme for the macroblock layer is also proposed to improve the coding efficiency. An improved bit-reallocation according to both the actual and predicted complexity of a macroblock is investigated. The simplified transform-domain rate function can be utilized to determine the quantization parameter in the post motion estimation stage for mode decision. The bit-reallocated mode-decision enhances the rate-control scheme for H.264/AVC by improving the objective video quality ranges from about 0.05 to 1 dB.

1 ISO/IEC, Information Technology-Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to About 1.5 Mbit/s: Video, ISO/IEC 11172-

2 (MPEG-1 Video), 1993. 2 ISO/IEC, Information Technology-Generic Coding of Moving Pictures and Associated Audio Information: Video, 13818-2-ITU-T Rec. H.262 (MPEG-2 Video), 1995.

3 ISO/IEC, Information Technology-Generic Coding of Audio-Visual Objects Part 2: Visual, ISO/IEC 14496-2 (MPEG-4 Video), 1999.

4 “Video coding for low bitrate communication,” ITU-T Recommendation H.263 Ver-sion 1, 1995. Version 2, Sept. 1997.

5 Joint Video Team, “Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification (ITU-T Rec.H.264 | ISO/IEC 14496-10 AVC),” Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, JVT-G050, March 2003.

6 M. Wien, “Variable block-size transforms for H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 604–613, July 2003.

7 S. Gordon, “Adaptive block transform for film grain reproduction in high definition sequences,” in Joint Video Team (JVT) Doc. JVT-H029, May 2003.

8 Society of Motion Picture and Television Engineers (SMPTE), “Proposed SMPTE Standard for Television: VC-1 Compressed Video Bitstream Format and Decoding Process,” 2005.

9 S. Srinivasan, P. Hsu, T. Holcomb, K. Mukerjee, S. L. Regunathan, B. Lin, J. Liang, M.-C. Lee, J. Ribas-Corbera “Windows media video 9: overview and applications,” Signal Processing: Image Commun., vol. 19, pp. 851–875, Oct. 2004.

10 G. J. Sullivan and T. Wiegand, “Rate-distortion optimization for video compression,” IEEE Signal Processing Mag., vol. 15, pp. 74–90, Nov. 1998.

11 A. Ortega and K. Ramchandran, “Rate-distortion methods for image and video com-pression: an overview,” IEEE Signal Processing Mag., pp. 23–50, Nov. 1998.

12 T. Wiegand, M. Lightstone, D. Mukherjee, T. G. Campbell, and S. K. Mitra, “Rate-distortion optimized mode selection for very low bit rate video coding and the emerging H.263 standard,” IEEE Trans. Circuits Syst. Video Technol.,
vol. 6, pp. 182–190, Apr. 1996.

13 D. Mukherjee and S. K. Mitra, “Combined mode selection and macroblock quantiza-tion step adaptation for the H.263 video encoder,” in Proc. Int. Conf. Image Process-ing, Aug. 1997, pp. 37–40.

14 H. Kim, N. Kamaci, and Y. Altunbasak, “Low-complexity rate-distortion optimal macroblock mode selection and motion estimation for MPEG-like video coders,” IEEE Trans. Circuits Syst. Video Technol., vol. 15, pp. 823–834, July 2005.

15 G. J. Sullivan and R. L. Baker, “Rate-distortion optimized motion compensation for video compression using fixed or variable size blocks,” in Global Telecomm. Conf. (GLOBECOM’91), pp. 85–90, Dec. 1991.

16 M. C. Chen and A. N. Willson, Jr., “Rate-distortion optimal motion estimation algo-rithms for motion-compensated transform video coding,” IEEE Trans. Circuits Syst. Video Technol. vol. 8, pp. 147–158, Apr. 1998.

17 W. C. Chung, F. Kossentini, and M. J. T. Smith, “An efficient motion estimation tech-nique based on a rate-distortion criterion,” in Proc. Int. Conf. Acoust., Speech, Signal Processing, vol. 43, Nov. 1995, pp. 2771–2783.

18 Y.-K. Chen and S. Y. Kung, “Rate optimization by true motion estimation,” in Proc. IEEE Workshop on Multimedia Signal Processing, Jun. 1997.

19 P. Subramanian and W.-Y. Chan, “Reduced-complexity rate-distortion optimization of multiresolution motion field and prediction residual,” in Proc. Int. Conf. Image Proc-essing, vol. 2, Aug. 1997, pp. 799–802.

20 W. Ding and B. Liu, “Rate control of MPEG video coding and recording by rate-quantization modeling,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 12–20, Feb. 1996.

21 H.-M. Hang and J.-J. Chen, “Source model for transform video coder and its applica-tion—part I: fundamental theory,” IEEE Trans. Circuits Syst. Video Technol., vol. 7, pp. 287–298, Apr. 1997.

22 L.-J. Lin, A. Ortega, Bit-rate control using piecewise approximated rate-distortion characteristics, IEEE Trans. Circuits Syst. Video Technol., vol. 8, pp. 446–459, Aug. 1998.

23 H.-J. Lee, T. Chiang, and Y.-Q. Zhang, “Scalable rate control for MPEG-4 video,” IEEE Trans. Circuits Syst. Video Technol., vol. 10, pp. 878–894, Sept. 2000.

24 T. Chiang and Y.-Q. Zhang, “A new rate control scheme using quadratic rate distor-tion model,” IEEE Trans. Circuits and Syst. Video Technol., vol. 7, pp. 246–250, Feb. 1997.

25 J. Ribas-Corbera and S. Lei, “Rate control in DCT video coding for low-delay com-munications,” IEEE Trans. Circuits and Syst. Video Technol., vol. 9, pp.172–185, Feb. 1999.

26 Z. He, Y. K. Kim and S. K. Mitra, “low-delay rate control for DCT video coding via ρ-domain source modeling,” IEEE Trans. Circuits and Syst. Video Technol., vol. 11, pp. 928–940, Aug. 2001.

27 Z. He and S. K. Mitra, “Optimum bit allocation and accurate rate control for video coding via ρ–domain source modeling,” IEEE Trans. Circuits and Syst. Video Tech-nol., vol. 12, pp. 840–849, Oct. 2002.

28 Z. He and S. K. Mitra, “A linear source model and a unified rate control algorithm for DCT video coding,” IEEE Trans. Circuits and Syst. Video Technol., vol. 12, pp. 970–982, Nov. 2002.

29 J. Ribas-Corbera and S. Lei, “A frame-layer bit allocation for H.263+,” IEEE Trans. Circuits and Syst. Video Technol., vol. 10, pp.1154–1158, Oct. 2000.

30 Y. Shoham and A. Gersho, “Efficient bit allocation for an arbitrary set of quantizers,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 36, pp. 1445–1453, Sept. 1988.

31 G. M. Schuster and A. K. Katsaggelos, “A theory for the optimal bit allocation be-tween displacement vector field and displaced frame difference,” IEEE J. Selected Areas Commun., vol. 15, 1739–1751, Dec. 1997.

32 G. M. Schuster and A. K. Katsaggelos, “A video compression scheme with optimal bit allocation among segmentation, motion, and residual error,” IEEE Trans. Image Process., vol. 6, pp. 1487–1502, Nov. 1997.

33 K. Ramchandran, A. Ortega, and M. Vetterli, Bit allocation for dependent quantization with applications to multiresolution and MPEG video coders,” IEEE Trans. Image Process., vol. 3, pp. 533–545, Sept. 1994.

34 K. Ramchandran and M. Vetterli, “Rate-distortion optimal fast thresholding with complete JPEG/MPEG decoder compatibility,” IEEE Trans. Image Process., vol.3, pp. 700–704, Sept, 1994.

35 M. Crouse and K. Ramchandran, “Joint thresholding and quantizer selection for transform image coding: entropy-constrained analysis and applications to baseline JPEG,” IEEE Trans. Image Process., vol. 6, pp. 285–297, Feb. 1997.

36 I.-M. Pao and M.-T. Sun, “Encoding DCT coefficients based on rate-distortion meas-urement,” Journal of Visual Communication and Image Representation, pp. 29–43, Mar. 2001.

37 H. Everett, “Generalized lagrange multiplier method for solving problems of optimum allocation of resources,” Oper. Res., vol. 11, pp. 399–417, 1963.

38 T. Wiegand, H. Schwarz, 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, July 2003.

39 T. Wiegand and B. Girod, “Lagrange multiplier selection in hybrid video coder con-trol,” in Proc. Int. Conf. Image Processing (ICIP’01), Oct. 2001, pp. 542–545.

40 F. Pan, X. Lin, R. Susanto, K. P. Lim, Z. G. Li, G. N. Feng, D. J. Wu, and S. Wu, “Fast mode decision for intra prediction,” in Joint Video Team (JVT) Doc. JVT-G013, Mar. 2003.

41 K. P. Lim, S. Wu, D. J. Wu, S. Rahardja, X. Lin, F. Pan and Z. G. Li, “Fast inter mode selection,” in Joint Video Team (JVT) Doc. JVT-I020, Sept. 2003.

42 B. Jeon and J. Lee, “Fast mode decision for H.264,” in Joint Video Team (JVT) Doc. JVT-J033, Dec. 2003.

43 Y. H. Kim, J. W. Yoo, S. W. Lee, J. Shin, J. Paik, and H. K. Jung, “Adaptive mode de-cision for H.264 encoder,” Electron. Lett., Vol. 40, No. 19, September 2004.

44 Y.-K. Tu, J.-F. Yang, M.-T. Sun and Y. Tsai, “Fast variable-size block motion estima-tion for efficient H.264/AVC encoding,” Signal Process.: Image Commun., vol. 20, issue 7, pp. 595-623, Aug. 2005.

45 P. Yin, H. Y. Cheong, A. M. Tourapis, and J. Boyce, “Fast mode decision and motion estimation for JVT/H.264,” in Proc. Int. Conf. Image Processing, vol. 3, Sep. 2003, pp. 853–856.

46 J. Ribas-Corbera and D. L. Neuhoff, “Optimizing block size in motion compensated video coding,” J. Electronic Imaging, vol. 7, pp. 155–165, Jan. 1998.

47 M. Flierl, T. Wiegand, and B. Girod, “Rate-constrained multihypothesis prediction for motion-compensated video compression,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, Nov. 2002.

48 M. Flierl and B. Girod, “Generalized B pictures and the draft H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 587–597, July 2003.

49 T. Wiegand, X. Zhang, and B. Girod, “Long-term memory motion-compensated pre-diction,” IEEE Trans. Circuits Syst. Video Technol., vol. 9, Feb. 1999.

50 J. Ribas-Corbera and David L. Neuhoff, “Optimizing motion-vector accuracy in block-based video coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 11, Apr. 2001.

51 T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion compensated in-terframe coding for video conferencing,” in Proc. Nat. Telecommun. Conf., New Or-leans, LA, Nov. 29–Dec. 3 1981, pp. G5.3.1–5.3.5.

52 R. Li, B. Zeng, M. L. Liou, A new three-step search algorithm for block motion esti-mation, IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 438-442, Aug. 1994.

53 L. M. Po, W. C. Ma, A novel four-step search algorithm for fast block motion estima-tion, IEEE Trans. Circuits Syst. Video Technol., vol. 6, 313–317, June 1996.

54 S. Zhu, 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.

55 C. Zhu, X. Lin, L.-P. Chau, Hexagon-based search pattern for fast block motion esti-mation, IEEE Trans. Circuits Syst. Video Technol., vol. 12, pp. 349–355, May 2002.

56 J. Xin, M.-T. Sun, V. Hsu, “Diversity-based fast block motion estimation,” in Proc. Int. Conf. on Multimedia and Expo. (ICME’03), vol. 3, July 2003, pp. III–525–528.

57 K.-L. Chung, L.-C. Chang, A new predictive search area approach for fast block mo-tion estimation, IEEE Trans. Image Process., vol. 12, pp. 648–652, June 2003.

58 J. Chalidabhongse, C.-C. Kuo, Fast motion vector estimation using multiresolu-tion-spatio-temporal correlations, IEEE Trans. Circuits Syst. Video Technol., vol. 7, pp. 477–488, June 1997.

59 Z. Chen, P. Zhou and Y. He, “Fast integer pel and fractional pel motion estimation for JVT,” in Joint Video Team (JVT) Doc. JVT-F017, Dec. 2002.

60 Z. Chen, P. Zhou and Y. He, “Fast motion estimation for JVT,” in Joint Video Team (JVT) Doc. JVT-G016, Mar. 2003.

61 A. M. Tourapis, H.-Y. Cheong and P. Topiwala, “Fast ME in the JM reference soft-ware,” in Joint Video Team (JVT) Doc. JVT-P026, July 2005.

62 X. Yi, J. Zhang, N. Ling and W. Shang, “Improved and simplified fast motion estima-tion for JM,” in Joint Video Team (JVT) Doc. JVT-P021, July 2005.

63 S.-C. Chang, J.-F. Yang, C.-F. Lee and J.-N. Hwang, “A novel rate predictor based on quantized DCT indices and its rate control mechanism,” Signal Process.: Image Commun., vol. 18, pp. 427–441, July 2003.

64 J. Bai, Q. Liao, X. Lin, X. Zhuang, “Rate-distortion model based rate control for real-time VBR video coding and low-delay communications,” Signal Process.: Image Commun., vol. 17, pp. 187–199, Feb. 2002.

65 “MPEG-2 video test model 5,” in ISO/IEC JTC1/SC29/WG11 MPEG93/457, 1993.

66 Video codec test model, TMN8, ITU-T/SG15, June 1997.

67 “Text of ISO/IEC 14496-2 MPEG4 video VM—Version 8.0,” in ISO/IEC JTC1/SC29/WG11 Coding of Moving Pictures and Associated Audio MPEG 97/W1796. Stockholm, Sweden: Video Group, 1997.

68 Z. Li, F. Pan, K. P. Lim, G. Feng, X. Lin and S. Rahardja “Adaptive basic unit layer rate control for JVT,” in Joint Video Team (JVT) Doc. JVT-G012, Mar. 2003.

69 S. Ma, F. Wu, and Z. Li, “Draft for adaptive rate control With HRD considerations,” in Joint Video Team (JVT) Doc. JVT-H017, May 2003.

70 G. Sullivan, T. Wiegand and K.-P. Lim, “Joint model reference encoding methods and decoding concealment methods,” in Joint Video Team (JVT) Doc. JVT-I049, Sept. 2003.

71 I.-H. Shin, Y.-L. Lee, H.W. Park, “Rate control using linear rate-ρ model for H.264,” Signal Process.: Image Commun., vol. 19, pp. 341–352, Apr. 2004.

72 N. Kamaci, Y. Altunbasak, and R. M. Mersereau, “Frame bit allocation for the H.264/AVC video coder via Cauchy-density-based rate and distortion models, IEEE Trans. Circuits Syst. Video Technol., vol. 15, pp. 994–1006, August 2005.

73 S. Ma, W. Gao, and Y. Lu, “Rate-distortion analysis for H.264/AVC video coding and its application to rate control,” IEEE Trans. Circuits Syst. Video Technol., vol. 15, pp. 1533-1544, Dec. 2005.

74 M. Jiang, X. Yi, and N. Ling, “Improved frame-layer rate control for H.264 using MAD ratio,” in IEEE Int. Symp. on Circuits and Systems (ISCAS’04), vol. 3, May 2004, pp. III–813–816.

75 M. Jiang and N. Ling, “An improved frame and macroblock layer bit allocation scheme for H.264 rate control,” in IEEE Int. Symp. on Circuits and Systems (ISCAS’05), vol. 2, May 2005, pp. 1501–1504.

76 A. Hallapuro and M. Karczewicz, “Low complexity transform and quantization,” in Joint Video Team (JVT) Docs. JVT-B038 and JVT-B039, Jan. 2002.

77 H. Yu, F. Pan, Z. Lin and Y. Sun, “A perceptual bit allocation scheme for H.264,” in Proc. Int. Conf. on Multimedia and Expo. (ICME’05), July 2005, pp.
313–316.

78 Joint Video Team (JVT) Reference Software. [Online]. Available: http://bs.hhi.de/~suehring/tml/download/

79 J. Xin, A. Vetro, H. Sun, “Efficient macroblock coding-mode decision for H.264/AVC video coding", in Proc. Picture Coding Symposium (PCS 2004), San Francisco, CA, December 2004.

80 Q. Chen and Y. He, “A fast bits estimation method for rate-distortion optimization in H.264/AVC,” in Proc. Picture Coding Symposium (PCS 2004), San Francisco, CA, Dec. 2004.

81 Y.-K. Tu, J.-F. Yang, and M.-T. Sun, “Rate-Distortion Estimation for H.264/AVC Coders,” in Proc. IEEE Int. Conf. on Multimedia and Expo (ICME’05), Amsterdam, The Netherlands, July 2005, pp. 554–557.

82 G. Bjontegaard, “Calculation of average PSNR differences between RD-curves,” ITU-T Q.6/SG16 VCEG 13th Meeting, Doc. VCEG-M33, Austin, TX, Apr. 2001.

83 A. K. Jain, Fundamentals of Digital Image Processing. Englewood Cliffs, NJ: Pren-tice-Hall, 1989.

84 I.-M. Pao and M.-T. Sun, “Modeling DCT coefficients for fast video encoding,” IEEE Trans. Circuits Syst. Video Technol., vol. 9, pp. 608–616, June 1999.

85 E. Y. Lam and J. W. Goodman, “A mathematical analysis of the DCT coefficient dis-tributions for images,” IEEE Trans. Image Process., vol. 9, no. 10, pp. 1661–1666, Oct. 2000.

86 J. Ribas-Corbera, P. A. Chou, and S. L. Regunathan, “A generalized hypothetical ref-erence decoder for H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 674–686, July 2003.

87 Y.-K. Tu, J.-F. Yang, and M.-T. Sun, “Statistical Rate-Distortion Estimation for H.264/AVC Coders,” IEEE Int. Symp. on Circuits and Systems (ISCAS’06), will be held on the Island of Kos, Greece, May 21-24, 2006, pp. 365–368.

88 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.