低計算複雜度的增強型零樹編碼演算法之研究

Abstract

本論文提出一種低計算複雜度的增強型零樹編碼(zerotree coding)演算法，以應用在影像壓縮上。該演算法的重點分為三個部份。第一個部分是轉換的部份，包括推廣形狀適應的小波轉換(shape-adaptive discrete wavelet transform; SA-DWT)到平移不變的SA-DWT (translation-invariant SA-DWT; TI-SA-DWT)和針對奇對稱濾波器(odd symmetric filters)所提出來的快速摺積(fast convolution; FC)演算法。第二個部分是壓縮性能的部份，包括提出一個計算上簡單的適應性多頻帶分割法(adaptive multi-subband decomposition; AMSD)來提昇訊號雜音比(peak-signal to noise ratio; PSNR)，以及提出頻帶旗號方式(band flag scheme; BFS)來加快零樹編碼的速度。第三個部分是低記憶體的執行部分，包括如何利用遞迴式程式設計(recursive programming)和以高位元(top bits)作為旗號記錄編碼的狀態，來達到減少記憶體的目的，進而減少硬體實現上的成本。在廣泛的影像資料中，所作的實驗結果顯示：以轉換的時間而言，有使用FC的結果比沒有使用的結果在DWT和IDWT上分別減少至少13%和37%的轉換時間；以PSNR而言，有使用AMSD的結果比沒有使用的結果，可以提高0.1~4dB；以零樹編碼對係數的比較次數而言，有使用BFS 的結果平均比沒有使用的結果減少60 %以上的計算量；而以記憶體的使用量而言，對一張768*512的彩色影像，使用所提出來的方法比集合分割在階層樹(set partitioning in hierarchical trees; SPIHT)的方法減少約5.3Mbytes的記憶體空間。實驗結果證實，所提出來的方法確實可行並且有其優越性，可以廣泛地被應用在各種不同影像的壓縮上。

In this study, we present a low computational complexity enhanced zerotree coding algorithm and apply it to the coding of arbitrarily shaped images. The algorithm contains three main parts. The first part is about transformation, including extending the shape-adaptive discrete wavelet transform (SA-DWT) to translation-invariant SA-DWT (TI-SA-DWT), and presenting a fast convolution algorithm for the filtering with odd length symmetric filters. The second part is about compression performance, including proposing an computationally simple adaptive multi-subband decomposition (AMSD) to elevate the peak-signal to noise ratio (PSNR), and designing a band flag scheme (BFS) to speed up the execution of zerotree coding. The third part is about low memory implementation, including using recursive programming and using the top bits of coefficients to serve as flags so that the working memory can be reduced significantly and the cost of hardware implementation can be decreased. Experimental results show that in transform time, using the fast convolution algorithm can reduce at least 13% of DWT time and 37% of inverse DWT time; in PSNR value, using AMSD can further elevate the value by 0.1~4dB; in the number of comparisons for searching zerotrees, using BFS can reduce the number of comparisons up to 60% of the original one; in memory requirement, for a 768*512 color image, using the proposed method can reduce the amount of memory up to 5.3 MBytes compared with the state-of-the-art zerotree coder, set partitioning in hierarchical trees (SPIHT). Experimental results verify that the proposed algorithm is indeed executable and outperforms the other related techniques. Therefore, it can be extensively applied to the coding of various images. 1.1. Background and Motivation 1.2. Problem formulation and contribution 1.3. Organization of This dissertation 1.4. Brief Review of SPIHT 2. TRANSFORMATION 2.1. Translation Invariant Wavelet Transforms for Arbitrarily Shaped Image Coding 2.1.1. Introduction 2.1.2. Overview of proposed transform scheme A. SA-DWT for both analysis filters being of odd length B. SA-DWT for both analysis filters being of even length 2.1.3. Design of TI-SA-DWT for arbitrarily shaped image coding 2.1.4. Example 2.1.5. Conclusion 2.2. Fast convolution algorithm for symmetric odd length filters 2.2.1 Introduction 2.2.2. Design of fast convolution algorithm for DWT 2.2.3. Design of fast convolution algorithm for IDWT 2.2.4. Computational complexity 2.2.5. Experimental results 2.2.6. Conclusion 3. COMPRESSION PERFORMANCE 3.1. Introduction 3.2. Adaptive Multi-Subband Decomposition 3.2.1. Design of adaptive multi-subband decomposition 3.2.2. Experimental results 3.3. Band Flag Scheme 3.3.1. Band flag scheme by using the real values of transformed coefficients 3.3.2. Analysis of Wavelet Coefficients 3.3.3. Band flag scheme by using the theoretical values of transformed coefficients 3.3.4. Controlling tree depths 3.3.5. Experimental Results 3.4. Conclusion 4. LOW MEMORY IMPLEMENTATION 4.1. Introduction 4.2. Coding Algorithm 4.3. Complexity Analysis 4.4. Experimental Results 4.5. Conclusion 5. CONCLUSION 5.1. Summary of Research Work 5.2. Further Developments Bibliography