臺灣博碩士論文加值系統

　　視訊壓縮成為熱門的研究領域已經有很多年了。大多數的壓縮標準像是H.26X和MPEG-X是將影像分成區塊的方式以離散餘弦轉換 (Discrete Cosine Transform) / 差分調制 (Differential Modulation) 的方法來進行壓縮。近年來，MPEG-4標準和其它方法的壓縮效率比較起來已經勝過很多。然而，以MPEG-4編碼器的複雜度來看，將要花費很高的成本來達成其硬體解決方案。如果要達到即時壓縮的效果更必須要有一顆強而有力的CPU來當控制器。
近年來，和使用離散餘弦轉換的JPEG壓縮標準比較起來，使用離散小波轉換 (Discrete Wavelet Transform) 來進行影像壓縮的方法有越來越普及的趨勢，這是因為它們具有高壓縮比的優勢。在這篇論文中將展現一個將影像分成區塊的方式以離散小波轉換結合差分調制來進行視訊壓縮的編解碼器。為了使硬體設計更簡單和容易，這裡使用改良式階層樹分割編碼(Modified Set Partitioning in Hierarchical Trees) 演算法和低複雜度的提升式 (Lifting Scheme) 離散小波轉換。跟MPEG-4比較起來，這種簡單而不用查表的設計策略更容易用硬體設計的方式來實現。如果有必要的話，甚至整個編解碼器完全可以不用CPU來當控制器而直接設計一個簡單電路來完全控制所有的編碼流程。這裡要特別點明的是，如果採用更複雜的方法來進行壓縮，整體的壓縮效率還會更為提升。在使用Synopsys和TSMC .35的元件資料庫來設計時，整體邏輯閘數目將少於95000。當系統在40MHz的時脈下運作時，壓縮速度在VGA解析度下可達到每秒30張圖。應用在成本和能源消耗都有限制的可攜式資訊家電(Information Appliance) 上將非常具有競爭力。這個系統已在Altera APEX 20K FPGA實驗板上驗證過。

Video codec have been an active research area for years. Most standards such as H.26X and MPEG-X are block DCT (Discrete Cosine Transform) / DM (Differential Modulation) based. Recently, MPEG-4 provides very good coding efficiency compared to other methods. However, the complexity of a MPEG-4 encoder makes hardware solutions very expensive. Furthermore, it usually requires a powerful CPU as the controller if real-time compression is desired.
Recently, Wavelet based image coding methods become more and more popular when compared to DCT based JPEG because they usually enjoy higher compression ratio. In this thesis, a block Wavelet based video codec combined with DM coding scheme is presented. An efficient modified SPIHT (Set Partitioning in Hierarchical Trees) is proposed for easy hardware implementation. A low complexity lifting based DWT (Discrete Wavelet Transform) is also designed. Straightforward coding strategies and coding without table make the hardware implementation much easier compared to MPEG-4. The entire codec can be hardwired without the use of a CPU controller if desired. Note that the overall performance can be further improved if more complicated coding schemes are used. The overall gate count is less than 85000 when designed with Synopsys and TSMC .35 cell library. When the system runs at 40 MHz clock rate, it achieves VGA resolution at 30 frames per second. Low cost and high quality make the proposed design very attractive for portable IA (Information Appliance) devices where cost and power consumption are critical. The proposed system is also verified over an Altera APEX 20K FPGA evaluation board.

1　研究動機與目的.....................................................1
　1.1　研究動機.......................................................1
　1.2　研究目的.......................................................3
2　基本研究...........................................................5
　2.1　離散小波轉換(Discrete Wavelet Transform)與影像壓縮.............5
　　2.1.1　離散小波轉換與濾波器組(DWT and Filter Banks)...............8
　　2.1.2　提升式離散小波轉換(Lifting Scheme DWT)....................10
　2.2　階層樹分割編碼(Set Partitioning in Hierarchical Trees)........13
　　2.2.1　漸進式影像傳輸(Progressive Image Transmission)............13
　　2.2.2　小波係數的特性............................................14
　　2.2.3　集合分割排序法(Set Partitioning Sorting Algorithm)........15
　　2.2.4　階層樹分割編碼演算法說明..................................16
　2.3　改良式階層樹分割編碼(Modified SPIHT)..........................18
　　2.3.1　小波係數重新排列..........................................19
　　2.3.2　標記式座標表示法..........................................22
　　2.3.3　改良式階層樹分割編碼演算法說明............................23
　　2.3.4　軟體模擬..................................................25
　　2.3.5　討論......................................................26
　2.4　動態估測與動態補償(Motion Estimation and Motion Compensation).27
　　2.4.1　完全搜尋法(Full Search)...................................28
　　2.4.2　三步搜尋法(Three Step Search).............................29
　　2.5　區塊效應(Blocking Effect)消除法.............................30
3　硬體設計..........................................................31
　3.1　編碼流程......................................................31
　3.2　硬體架構......................................................33
　3.3　提升式小波轉換................................................35
　　3.3.1　效能評估與電路合成........................................37
　3.4　改良式階層樹分割編碼..........................................38
　　3.4.1　有限狀態機狀態說明........................................40
　　3.4.2　效能評估..................................................45
　　3.4.3　電路合成..................................................48
　3.5　軟硬體整合測試................................................49
　3.6　結論..........................................................51
4　結論與未來發展方向................................................52
5　參考文獻..........................................................53

[1] Weiping Li, Jens-Rainer Ohm, Mihaela van der Schaar, Hong Jiang, Shipeng Li,“MPEG-4 Video Verification Model version 18.0,”ISO/IEC JTC1/SC29/WG11 N3908, January 2001/Pisa
[2] W. B. Pennebaker and J. L. Mitchell,“JPEG: Still Image Data Compression Standard,”New York: Van Nostran Reinhold, 1993.
[3] ISO/IEC JTC1/SC29/WG11,“JPEG-8-R8 Committee Draft,”1990.
[4] ISO,“JPEG 2000 Image Coding System,”ISO/IEC 155444-1, Dec. 2000.
[5] D. Taubman,“High performance scalable image compression with EBCOT,”Image Processing, IEEE Transactions on, Volume: 9 Issue: 7, July, 2000, pp. 1158-1170.
[6] A. Said and W. A. Pearlman,“A new fast and efficient image codec based on set partitioning in hierarchical trees”, IEEE Trans. On Circuits and System for Video Technology 6, 99. 243-250, June 1996.
[7] J.M. Shapiro,“Embedded image coding using Zerotree of wavelets coefficients,”IEEE Trans. Signal Processing, vol. 41,pp. 3445-3462, Dec.1993.
[8] S.Mallat,“A Theory for Multi-resolution Signal Decomposition : The Wavelet Representation,”IEEE Trans. Pattern Anal. And Machine Intell., Vol. 11, no. 7, pp.674-693, July 1989.
[9] M. Vetterli and C. Herley, Wavelets and Filter Banks : Theory and Design,”IEEE Transactions on Signal Processing, vol. 40, pp. 2207-2232, Sep. 1992.
[10] M. Vetterli, Filter Banks Allowing Perfect Reconstruction,”Signal Processing, vol. 10, pp. 219-244, April 1986.
[11] ISO/IEC JTC1/SC29/WGIN 1013,“Low Memory Line-based Wavelet Transform Using Lifting Scheme,”1998.
[12] K. Chow and M. L. Liou,“Genetic motion search algorithm for video compression,”IEEE Trans. Circuits Syst. Video Technol., no. 6, pp. 440—445, Dec. 1993.
[13] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, "Motion Compensated Interframe Coding for Video Conferencing," in Proc. Nat. Telcommun. Conf., New Orleans, LA, Nov. 1981, pp. 5.3.1~5.3.5
[14] K. Ramkishor, Pravin Karandikar,“A simple and efficient deblocking algorithm for low bit-rate video coding,”http://www.ee.cityu.edu.hk/~ISCE2000/024.doc