臺灣博碩士論文加值系統

傳統視訊位元率控制演算法通常追求影像失真總量最小化，然而往往付出影值大幅度變動的代價，特別是在視訊內容較激烈且經常性場景變換時。為了減輕影值變動所帶來的負面作用，許多演算法追求全部影值均等。如某些研究者指出，雖然現有演算法已能產生影值均等的視訊，但是這些演算法經常無法精確地使用分配的位元來減少失真總量。本論文嘗試一次達成三個目標。即平穩視訊品質、失真總量最小化、精準地使用位元預算等。我們共提供三個演算法，針對兩種不同應用，定速率與變速率通道，來完成這些目標。其中兩個演算法適用於定速率通道，如儲存應用；一個演算法適用於變速率通道，如網際網路傳輸應用。
第一個演算法使用籬柵圖(Trellis-Based)架構來達成具備一致性品質的視訊。我們第一個貢獻是推導出，失真最小化問題與位元預算最小化問題的等效條件。第二，籬柵圖狀態定義為失真量，方便於一致性品質控制。第三，只需在提出的演算法中調整一個參數，一個介於，最小失真總量與固定品質的視訊解，可以被求得。第二個演算法結合拉格蘭乘數（Lagrange Multiplier）、快速分支延展與最佳化程序。與第一個演算法比較，它的峰信雜比效能只有些微的降低，但是運算複雜度顯著地降低。模擬結果顯示，這兩個演算法都只比MPEG 所提JM位元率控制演算法的平均峰信雜比些微低。當與近期發表的MultiStage與LPF演算法比較，我們所提演算法能夠較準確地使用分配位元預算，且輸出最大的峰信雜比與很小的峰信雜比變動率。
第三個演算法在變速率通道追求優雅的品質變動。我們取代一致性品質限制，換成最大相鄰幀間影值變動限制。因為這個演算法在單獨GOP內運作，相鄰GOP品質控制需求也需要被考量。每個GOP通道位元率被設定成給定的頻寬晃動模型。模擬結果顯示，我們的峰信雜比曲線函數很平滑，且在每個GOP邊界並沒有品質突然掉落。我們所提演算法也能夠準確地利用分配位元預算值。
總結，我們發展出彈性的影值控制架構，提出三個演算法。這些解能滿足三個目標，品質變動最小化、失真總量最小化、精準地使用位元預算。此外，附錄A呈現通道編碼效能分析結果，未來可用於整合視訊與通道編碼研究。

A conventional video rate control algorithm typically minimizes the total distortion at the cost of large temporal quality variation, especially for videos with high motion and frequent scene changes. To alleviate the negative effect of video quality variation, a few algorithms have been proposed to target on the constant quality across the entire sequence. As being pointed out by some researchers, although the existing proposals can produce constant-quality videos, they often fail to accurately utilize the available bits to minimize the global distortion. In this thesis, we would like to achieve three goals simultaneously. They are (1) producing smooth video quality (2) minimizing the total distortion, and (3) meeting the bit budget strictly. Three algorithms are proposed to accomplish this set of goals for two application scenarios: constant bitrate channels and variable bitrate channels. Two algorithms are designed for the constant bitrate channels, which may be used on the storage applications. And one algorithm is designed for the variable bitrate channels, which is needed for, say, Internet transmission applications.
The first algorithm uses the trellis-based structure to achieve the consistent quality video. Our first contribution is to derive an equivalent condition between the distortion minimization problem and the budget minimization problem. Second, the trellis state (tree node) is defined in terms of distortion, which facilitates the consistent quality control. Third, by adjusting one key parameter in our algorithm, a solution in between the minimum total distortion and the constant quality criteria can be obtained. The second algorithm combines the Lagrange multipliers together with the proposed fast branch expansion process and optimization procedure. Compared to the first algorithm, its PSNR performance is degraded slightly but the computational complexity is significantly reduced. Simulation results show that our two algorithms produce a much smaller PSNR variation at a slight average PSNR loss as compared to the MPEG committee JM rate control. When they are compared to the recently published MultiStage and LPF algorithms, our proposed algorithms can meet the bit budget more accurately and produce the largest average PSNR at a small PSNR variation.
The third algorithm aims at graceful quality variation for time-varying channels. We replace the consistent quality constraint in the second algorithm by a maximal inter-frame quality variation constraint. Because this algorithm operates on individual GOP’s, the quality variation across GOP boundaries has also to be considered. In our experiments, the channel bit rate for each GOP is set to follow the given bandwidth fluctuation pattern. Simulation results show that our PSNR curve has a smoother shape and has no sudden drop at the GOP boundaries. Also, the proposed algorithm meets the budget bits very accurately.
In summary, we develop a flexible quality control framework that leads to 3 separate algorithms. They are nearly optimal solutions that achieve the triple goal: minimizing quality variation, minimizing global distortion, and satisfying the bit budget constraint. In addition, a channel coding study is presented in Appendix A for solving combined source-channel coding in the future.

目錄　　　　　　
摘要　　　　　　 iii
ABSTRACT v
誌謝　　　　　　 vii
目錄　　　　　　 ix
List of Tables xi
List of Figures xii
Chapter 1 Introduction 1
1.1 Motivation and Discussed Topics 1
1.2 Organization of the Thesis 3
1.3 Contributions of the Thesis 4
Chapter 2 Overview of Lossy Video Coding 5
2.1 Dependent and Independent Video Coding 5
2.2 Rate-Distortion bound and Optimality 6
2.3 Rate-Distortion Optimization Criteria 8
2.4 Trellis Representation of the Tree Structure 9
2.5 Rate-Distortion Optimization Techniques 10
2.5.1 Lagrange Multiplier 10
2.5.2 Lagrange Relaxation 11
2.5.3 Dynamic Programming 12
2.6 Joint Source-Channel Coding 13
Chapter 3 Consistent Quality Control Algorithms 14
3.1 Problem Formulation and Distortion-Rate Function 14
3.1.1 Dependent MINAVE Bit Allocation Problem 14
3.1.2 Uniqueness of Distortion-Rate Function 16
3.2 Consistent Quality Control Algorithm 17
3.2.1 Trellis-Based Coding Scheme 17
3.2.2 Branch Expansion and Frame-level Bit Allocation 19
3.2.3 Fast Branch Expansion Process 21
3.2.4 Technique based on the Lagrange Multipliers 22
3.3 Simulation Results 25
3.3.1 Performance Comparison with Constant QP and JM 26
3.3.2 LCQC Performance Comparison with LPF and MultiStage Algorithms 30
3.3.3 Effects of Quality Variation Constraint on PSNR and Complexity 34
3.3.4 Effects of Cluster Size on PSNR and Complexity 37
3.4 Summary 38
Chapter 4 Graceful Quality Control Algorithm 40
4.1 Graceful Quality Variation Problem 40
4.2 Graceful Quality Control Algorithm 41
4.3 Simulation Results 43
4.3.1 LGQC Performance Comparison with JM 44
4.3.2 Effects of Quality Variation Constraint on PSNR and Complexity 47
4.4 Summary 50
Chapter 5 Conclusions and Future Research Topics 52
Appendix A Performance Analysis for Serially Concatenated FEC in IEEE802.16a over Wireless Channels 54
A.1 Introduction 54
A.2 System Mode 55
A.3 Performance of Serially Concatenated FEC 57
A.3.1 Union Upper Bound on the BER of RCPC Codes 57
A.3.2 Union Upper Bound on BER of RS Codes 58
A.4 Simulation Results 58
A.5 Conclusions 62

Bibliography
[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 Version 1, 1995. Version 2, Sept. 1997.
[5] T.Wiegand, G.-J. Sullivan, G. Bjontegarrd, and A. Luthra, “Draft ITU-T Rec. H.264/ISO/IEC 14496-10 AVC,” Joint Video Team of ISO/IEC MPEG and ITU-T VCEG, Doc. JVT-G050r1, Mar. 2003.
[6] Joint Video Team of ISO/IEC MPEG and ITU-T VCEG, “Joint Final Committee of Joint Video Specification (Draft ITU-T Rec. H.264/ ISO/IEC 14496-10 AVC),” Doc. JVT-D157, Aug. 2002.
[7] T.Wiegand, G.-J. Sullivan, G. Bjontegarrd, and A. Luthra, “Overview of the H.264/AVC video coding standard,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 560-576, Jul. 2003.
[8] A.-E. Mohr, “Bit allocation in sub-linear time and the multiple-choice knapsack problem,” in Proc. IEEE. Data Compression Conf., pp. 352-361, Mar. 2002.
[9] K. Ramchandran, A. Ortega, and M. Vetterli, “Bit allocation for dependent quantization with application to multi-resolution and MPEG video coders,” IEEE Trans. Image Processing, vol. 3, no. 5, pp. 533-545, Sep. 1994.
[10] Y. Sermadevi and S.-S. Hemami, “Efficient bit allocation for dependent video coding,” in Proc. IEEE. Data Compression Conf., pp. 232-241, Mar. 2004.
[11] A. Ortega, K. Ramchandran, and M. Vetterli, “Optimal trellis-based buffered compression and fast approximations,” IEEE Trans. Image Processing, vol. 3, pp. 26-40, Jan. 1994.
[12] A. Ortega and K. Ramchandran, “Rate-distortion methods for image and video compression,” IEEE Signal Processing Magazine, Nov., 1998.
[13] H.-M. Hang and J.-J. Chen, “Source model for video transform coder and its application – part I: fundamental theory,” IEEE Trans. Circuits Syst. Video Technol., vol. 7, pp. 287-298, Apr. 1997.
[14] J.-J. Chen and H.-M. Hang, “Source model for video transform coder and its application – part II: variable frame rate coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 7, pp. 299-311, Apr. 1997.
[15] T. Chiang and Y.-Q. Zhang, “A new rate control scheme using quadratic rate distortion model,” IEEE Trans. Circuit Syst. Video Technol., vol. 7, pp. 246-250, Feb. 1997.
[16] Z. He and S.-K. Mitra, “A unified rate-distortion analysis framework for transform coding,” IEEE Trans. Circuit Syst. Video Technol., vol. 11, pp. 1221-1236,Dec. 2001.
[17] L.-J. Lin and A. Ortega, “Bit-rate control using piecewise approximated rate-distortion characteristics,” IEEE Trans. Circuit Syst. Video Technol., vol. 8, pp. 446-459, Aug. 1998.
[18] G.-M. Schuster, G. Melnikov, and A.-K. Katsaggelos, “A overview of the minimum maximum criterion for optimal bit allocation among dependent quantizers,” IEEE Trans. Multimedia, vol. 1, pp. 3-17, Mar. 1999.
[19] Y. Shoham, and A. Gersho, “Efficient bit allocation for an arbitrary set of quantizers,” IEEE Trans. Acoustics, Speech and Signal Processing, vol. 36, no. 9, pp. 1445-1453, Sep. 1988.
[20] J. Ribas-Corbera and S. Lei, “Rate control in DCT video coding for low-delay communications,” IEEE Trans. Circuits Syst. Video Technol., vol. 9, no. 1, pp. 172-185, Feb. 1999.
[21] Z. He and S.-K. Mitra, “Optimum bit allocation and accurate rate control for video coding via -domain source modeling,” IEEE Trans. Circuit Syst. Video Technol., vol. 12, pp. 840-849, Oct. 2002.
[22] D.-K. Kwon, M.-Y. Shen, and C.-C. Jay Kuo, “Rate control for H.264 video with enhanced rate and distortion models,” IEEE Trans. Circuit Syst. Video Technol., vol. 17, no. 5, pp. 517-529, May 2007.
[23] Y. Yu, J. Zhou, Y. Wang, and C.-W Chen, “A novel two-pass VBR coding algorithm for fixed-size storage application,” IEEE Trans. Circuit Syst. Video Technol., vol. 11, no. 3, pp. 345-356, Mar. 2001.
[24] Z. He, W. Zeng, and C.-W Chen, “Low-Pass filtering of rate-distortion functions for quality smoothing in real-time video communication,” IEEE Trans. Circuit Syst. Video Technol., vol. 15 , no. 8 pp. 973-981, Aug. 2005.
[25] B. Xie, and W. Zeng, “A sequence-based rate control framework for consistent quality real-time video,” IEEE Trans. Circuit Syst. Video Technol., vol. 11, no. 3, pp. 56-71, Jan. 2006.
[26] Y. Sermadevi and S.-S. Hemami, “Lexicographic bit allocation for MPEG video coding,” in Proc. IEEE. Data Compression Conf., pp. 101-110, Mar. 1997.
[27] N. Cherniavsky, et al., “MultiStage: a MINMAX bit allocation algorithm for video coders,” IEEE Trans. Circuit Syst. Video Technol., vol. 17, no. 1, pp. 59-67, Jan. 2007.
[28] S.-Y. Lee and A. Ortega, “Optimal rate control for video transmission over VBR channels based on a hybrid MMAX/MMSE criterion,” in Proc. IEEE Int. Conf. Multimedia Expo, vol. 2 , pp. 93-96, Aug. 2002.
[29] G.-D. Forney, “The Viterbi algorithm,” in Proc. IEEE., vol. 1 ,no. 61, pp. 268-278, Mar. 1973.
[30] W.-Y. Lee and J.-B. Ra, “Fast algorithm for optimal bit allocation in a rate-distortion sense,” in Electronics Letters, vol. 32, no. 20, pp. 1871-1873, Sep. 1996.
[31] C.E. Shannon, “A mathematical theory of communication,” Bell Syst. Tech. Journal, vol. 27, pp. 379-423, 1948.
[32] C.E.Shannon, “Coding theorems for a discrete source with a fidelity criterion,” in IRE National Convention Record, Part 4, pp. 142-163, 1959.
[33] T.Berger, Rate-Distortion Theory. A Mathematical Theory for Data Compression. Prentice-Hall, 1971.
[34] A.-R. Reibman and B.-G. Haskell, “Constraints on variable bit-rate video for ATM networks,” IEEE Trans. Circuit Syst. Video Technol., vol. 2, pp. 361-372, Dec. 1992.
[35] J.-J. Chen and D.W. Lin, “Optimal bit allocation for coding of video signals over ATM networks,” IEEE J. Selected Areas in Communication., vol. 3, pp. 1002-1015, Aug. 1997.
[36] K.-L. Huang and H.-M. Hang, “Consistent picture quality control strategy for dependent video coding,” IEEE Trans. Image Processing, vol. 18, no. 5, pp. 1004-1014, May 2009.
[37] J.Hagenauer, “Rate-compatible punctured convolutional codes (RCPC Codes) and their applications,” IEEE Trans. Communications, vol. 36, no. 4, pp. 389-400, Apr. 1988.
[38] K.-L. Huang and H.-M. Hang, “Performance analysis for serially concatenated FEC in IEEE802.16a over wireless channels,” 5th Pacific Rim Conference on Multimedia, pp. 672-679, Dec. 2004.
[39] IEEE Std. 802.16-2004, “IEEE standard for local and metropolitan area networks–part 16: air interface for fixed broadband wireless access systems,” Oct. 2004.
[40] G. Solomon and H. C. A. van Tilborg, “A connection between block and convolutional codes,” Slam J. Appl. Mathematics, vol. 37, no. 2, pp. 358-369, Oct. 1979.
[41] J.Hagenauer, “Viterbi decoding of convolutional codes for fading- and burst-channels,” in Proc. Int. Seminar Digital Commun., Zurich, Switzerland, pp. G2.1-G2.7, Mar. 1980.
[42] G. Begin, D.Haccoun, and C. Paquin, “Further results on high-rate punctured convolutional codes for Viterbi and sequential decoding,” IEEE Trans. Communications, vol. 38, no. 11, pp. 1922-1928, Nov. 1990.
[43] J. G. Proakis, Digital Communication, 3rd ed. New York, McGraw-Hill, 1995.