臺灣博碩士論文加值系統

漸進式影像壓縮編碼器之超大型積體電路設計
學生：簡偉勝 指導教授：董蘭榮 博士
國立交通大學電機與控制工程研究所
摘 要
為了因應頻寬有限的多媒體應用需求，在影像壓縮技術中，漸進式影像傳輸愈來愈受重視。在現有的漸進式影像傳輸的演算法中，大部分都不適合硬體實現，主要原因是由於記憶體需求量的龐大，像目前被公認效能最好的SPIHT演算法就需要大量的記憶體來提供三個列表儲存小波係數的座標。我們針對這個缺點，提出了一個適合於硬體實現的演算法：階層樹旗標設定編碼。我們以三個旗標來代替SPIHT的三個座標列表，大量減少了記憶體的使用量。以處理一張256×256的影像為例，記憶體需求可由原本的250 K bytes減少至18 K bytes。本篇論文以矽智產的型式來實現此演算法，以便搭配其他電路來做成各類多媒體應用系統晶片。最後，本論文實際合成可處理256×256影像的漸進式影像壓縮編碼器同時考量功率節省。合成出來的矽智產面積成本低，邏輯電路部分只需2560個邏輯閘數，電路工作頻率可高達150 MHz。

A VLSI Progressive Coding for Image Compression
Student：Wei-Sheng Jian Advisor：Dr. Lan-Rong Dung
Department of Electrical and Control Engineering
National Chiao Tung University
ABSTRACT
Progressive image coding is becoming crucial for multimedia signal processing. Much research on image compression has paid much attention on progressive image coding. Nevertheless, the conventional progressive image coding notoriously is costly and memory-consuming. The SPIHT, for instance, is the most popular algorithm for progressive coding and the implementation requires large memory to save three coordinate tables. Thus, the thesis proposes a hardware-efficient algorithm that significantly reduce memory requirement. The algorithm is called Tag Setting In Hierarchical Trees (TSIHT). Instead of using coordinate tables to track the coding tree, the TSIHT uses tags to flag the image coefficients for generating the bitstream. Finally, the thesis implement the algorithm in the form of silicon intelligent property. As a result, the encoder for a 256×256 image requires 18 Kbytes memory that is much less than the memory requirement of SPIHT.

第一章 緒論………………………………………………………1
1.1 研究動機…………………………………………1
1.2 章節安排…………………………………………3
第二章 背景介紹…………………………………………………5
2.1 漸進式影像傳輸…………………………………5
2.2 嵌入式零樹小波編碼法…………………………6
2.2.1 嵌入式編碼法…………………… 7
2.2.2 小波係數的零樹結構…………… 8
2.2.3 小波係數的搜尋順序……………10
2.2.4 演算法敘述………………………11
2.3 各種實現EZW之演算法…………………………13
2.3.1 頻帶內部分割編碼法……………13
2.3.2 階層樹分割編碼…………………16
2.3.3 比較分析…………………………23
2.4 記憶體需求…………………………………… 25
第三章 階層樹旗標設定編碼………………………………… 26
3.1 基本原理……………………………………… 26
3.2 演算法改進歷程……………………………… 29
3.2.1 第一版……………………………29
3.2.2 第二版……………………………30
3.3 演算法說明…………………………………… 32
3.3.1 演算法敘述………………………32
3.3.2 討論………………………………34
3.4 Matlab模擬驗證……………………………… 35
第四章 硬體架構……………………………………………… 41
4.1 架構簡介……………………………………… 41
4.2 重要部分細說………………………………… 45
4.2.1 位址產生器………………………45
4.2.2 門檻值產生器……………………51
4.2.3 位元流產生器……………………52
4.2.4 旗標存取控制單元………………53
4.2.5 除頻器……………………………54
4.3 模擬結果……………………………………… 56
4.4 測試策略……………………………………… 57
第五章 合成結果與效能分析………………………………… 59
5.1 設計流程……………………………………… 59
5.2 合成結果……………………………………… 60
5.3 電路佈局……………………………………… 62
5.4 效能分析……………………………………… 63
第六章 結論與未來發展……………………………………… 65
6.1 結論…………………………………………… 65
6.2 未來發展……………………………………… 66
第七章 參考資料……………………………………………… 67

[1] J. M. Shapiro, “Embedded image coding using zerotrees of
wavelet coefficients,” IEEE Trans. on Signal Processing,
vol. 41, pp. 3445-3462, Dec. 1993.
[2] 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 Systems for Video
Technology, vol. 6, no. 3, pp.243-50, June 1996.
[3] M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies,
“Image coding using wavelet transform,” IEEE Trans. on
Image Processing, vol. 1, pp. 205-220, Apr. 1992.
[4] Zhen Liu and L. J. Karam, “An efficient embedded zerotree
wavelet image codec based on intraband partitioning,” IEEE
International Conference on Image Processing, vol. 3, pp.
162-165, 2000.
[5] Wen-Kuo Lin, Brian Wai-Him Ng, and Neil Burgess, “Reduced
memory zerotree coding algorithm for hardware
implementation,” IEEE International Conference on
Multimedia Computing and Systems, vol. 2, pp.57-61, 1999.
[6] Jongwoo Bae and Viktor K. Prasanna, “A fast and area-
efficient VLSI architecture for embedded image coding,”
Proceedings International Conference on Image Processing,
vol.3, pp. 452-455, Oct. 1995.
[7] L. Ang, H. N. Cheung, and K. Eshraghian, “VLSI
architecture for embedded zerotree wavelet coding,”
Proceedings 5th International Symposium on DSP for
Communication Systems, pp. 128-133, Feb. 1999.
[8] L. Ang, H. N. Cheung, and K. Eshraghian, “VLSI decoder
architecture for embedded zerotree wavelet algorithm,”
Proceedings 1999 IEEE International Symposium on Circuits
and Systems, pp. 141-144, May 1999.
[9] L. Ang, H. N. Cheung, and K. Eshraghian, “Depth-first
search implementation of embedded zerotree wavelet
algorithm,” Proceedings 5th International Symposium on
Signal Processing and its Applications, pp. 75-78, Aug.
1999.
[10] J. M. Zhong, C.H.Leung, and Y. Y. Tang, “An improved
embedded zerotree wavelet image compression algorithm based
on significance checking in wavelet trees,” Proceedings
IEEE International Conference on Systems, Man, and
Cybermetics, pp. 4567-4571, Oct. 1998.
[11] Shen-Fu Hsiao, Yor-Chin Tai, and Kai-Hsiang Chang, “VLSI
design of an efficient embedded zerotree wavelet coder with
function of digital watermarking,” IEEE Tranc. on Consumer
Electronics, vol. 46, pp.628-636, Aug. 2000.
[12] S.A. Martucci, I. Sodagar, T. Chiang, and Y. Zhang, “A
zerotree wavelet video coder,” IEEE Trans. Circuits and
Systems for Video Technology, vol. 7, No. 1, pp. 109-118,
Feb. 1997.
[13] L. Ang, H. N. Cheung, and K. Eshraghian, “VLSI
architecture for embedded image coding,” Proceedings
International Conference on Image Processing, vol. 3, pp.
452-455, Oct. 1995.
[14] M. Vetterli and J. Kovacevic, “Wavelets and subband
coding”, Prentice-Hall, New Jersey, 1995.
[15] B. Vanhoof, M. Peon, G. Lafruit, J. Bormans, M. Engels,
and I. Bolsens, “A scalable architecture for MPEG-4
embedded zero tree coding,” Custom Integrated Circuit,
1999. Proceedings of the IEEE 1999, 1999 Page(s):65-68.
[16] Wen-Kuo Lin and Neil Burgess, “Low memory color image
zerotree coding,” Information, Decision ant Control, 1999.
IDC 99. Proceedings. 1999, Page(s):91-95.
[17] R. Y. Omaki,G. Fujita, T. Onoye, and I. Shirakawa,
“Architecture of embedded zerotree wavelet based real-
time video coder,” ASIC/SOC Conference, 1999.
Proceedings. Twelfth Annual IEEE International, 1999 Page
(s):137-141.
[18] R. Y. Omaki,G. Fujita, T. Onoye, and I. Shirakawa,
“Embedded zerotree wavelet based algorithm for video
compression,” TENCON 99. Proceedings of the IEEE Region 10
Conference, vol. 2, 1999 Page(s):1343-1346.
[19] B.F. Wu and C.Y. Su, “Low computational complexity
enhanced zerotree coding for wavelet-based image
compression,” Signal Proceeding: Image Communication,
vol.16, pp. 401-411, 2000.
[20] C. Y. Su and B. F. Wu, “Image coding based on embedded
recursive zerotree,” In ISMIP ’97, page(s):387-392,
Taipei, Taiwan, Dec. 1997.
[21] http://www.jpeg.org/