應用於二維可分離式離散小波轉換之高效能演算法和架構設計

Abstract

近幾年來，離散小波轉換已成為一個強大的工具並且被應用在不同的領域諸如：影像的壓縮和分析､材質的辨別､碎形分析和圖案辨認等等。由於在時域和頻譜域上的局部化特性使得小波轉換在移除訊號相關性的能力上優於已往的離散餘弦轉換和傅立葉轉換。同時，以小波轉換為依據的影像壓縮技術其效能已被證實是優於用離散餘弦轉換的，尤其是在相當低的位元率情況下。基於這些優點，即將到來的JPEG 2000和MPEG 4國際標準已採納了離散小波轉換的使用。在這篇論文中，我們將專注在小波轉換於靜態影像壓縮的應用上。我們將簡單的介紹小波轉換的原理和仔細的探討用於二維小波轉換的 Circular-Parallel 架構。除此之外，一些以小波轉換為依據的相關影像壓縮演算法也將在本篇論文被提及。從這些演算法我們可以更清楚的瞭解離散小波轉換模組在整個系統所扮演的角色。這將有助於我們去設計離散小波轉換模組的輸入輸出使得將來此模組能夠不必耗費太多的努力就能和其他系統模組順利的連接運作。我們提出架構的關鍵點在於利用不同階層濾波段係數的依存關係，進而利用此關係做係數運算的排序。和過去被提出的架構和演算法比較起來，我們的架構能夠有較簡單的記憶體輸入輸出介面和較低的硬體代價。而且此架構能適合各種即時的影像應用以列接著一列的方式來完成二維的離散小波轉換運算。 在TSMC SPTM 0.6um 的製程下，我們用COMPASSTM 0.6um高性能的標準元件（Standard Cells）來實現此架構。這顆晶片整合了大約160k個電晶體於5.4mm x 5.3mm的矽面積上並且能夠處理高達8個濾波器係數和12.5Mhz的輸入取樣率。此一處理速度能夠滿足目前許多的影像和動態視訊會議的編碼應用。

In recent years, the Discrete Wavelet Transform (DWT) has become a powerful tool in many areas, such as image compression and analysis, texture discrimination, fractal analysis, pattern recognition and so on. Due to the localization property both in time and frequency domain, wavelet transform is more efficient than Short Time Fourier Transform (STFT) or Discrete Cosine Transform (DCT) in de-correlating the time domain signal correlation. Also, it has been proved that the wavelet based image compression scheme has better performance than that with DCT based especially in very low bit rate. Due to these advantages, the DWT has been included in the coming JPEG2000 and MPEG4 standards. In this thesis, we focus on the still image compression application of wavelet transform. We will give a brief introduction of wavelet transform and describe the proposed Circular-Parallel architecture (CPA) for 2-D DWT computation in detail. In addition, some wavelet based coding algorithms are presented in this thesis. From these coding algorithms, we can clearly understand the role of DWT module in the overall system. This helps us to design the I/O of the DWT module such that it can incorporate with the other modules in the system without too much additional effort. The key point of the proposed architecture is to exploit the dependence of different filter bank coefficients and further to schedule the computation order of these coefficients based on the dependence. As compared with some previously proposed architectures, our architecture has simpler memory I/O interface and lower hardware cost. And it can process the 2-D DWT in line by line fashion that is suitable for many real-time image coding applications. Based on TSMC SPTM 0.6um process technology, we use COMPASSTM 0.6um high performance cell library to implement the proposed CPA architecture. The chip integrates about 44k gates in 5.4mm x 5.3mm silicon area with the capability to process 8-tap filter and 12.5 MHz input sample rate that can meet many image and videoconference real-time applications.