- 學位論文
運用進階熵編碼以及機器學習預測的資料壓縮技術
Data Compression Using Advanced Entropy Coding Techniques and Machine Learning Based Prediction
摘要
在大部分的資料壓縮演算法當中，熵編碼是其中不可或缺的一環，它可以被用來將複雜的中繼符號轉換成用來儲存的01二元符號。常被使用的熵編碼演算法有像是赫夫曼編碼，算數編碼等，以及最近其的非對稱數值系統。就壓縮率而言，算數編碼在編碼效能上能夠最逼近該數值分布理論上的熵值，因此在近期的研究中被廣泛運用。 在本論文中，我們先提出了改良式漸進算數編碼的研究成果，這之中使用了五樣技術以改進算數編碼的壓縮效能，包括：初始頻率表的設計、漸進式增加的調整幅度、廣域調整、交互學習、暫時／局部的頻率表設計。我們也提供了這些技術應用在許多壓縮演算法中所得到的模擬結果，像是無失真／失真圖片壓縮、文字壓縮。模擬結果也顯示出我們提出的這五項技術確實能使編碼效能更高。此外，由於絕大多數的壓縮演算法都有熵編碼的設計在內。因此，我們提出的這五項技術可以被廣泛運用在各式各樣的壓縮演算法之中。 一直以來，資料壓縮的研究員們試圖將各式各樣的訊號處理技術應用在資料壓縮上。而近年隨著機器學習的興起，以及針對機器學習設計的硬體輔佐，使得在這近一、二十年間使用機器學習理論去做壓縮的演算法技術有逐漸增多的趨勢。然而，由於一些機器學習理論及技術的限制，絕大多數相關的演算法所得到的壓縮效能都無法和其他傳統訊號處理的技術比擬。 在此論文中，我們提出了一個相當有效混合傳統訊號處理及機器學習的壓縮演算法架構。而其中的機器學習技術使用的是一般在該領域相當常見的二元分類問題。 我們將它應用到一個類似於JPEG2000的壓縮演算法之中，首先影像先經過二維的小波轉換並量化。然後，在反量化後的小波係數域中，我們透過鄰近的小波係數以及更高層頻帶的小波係數來預測當前的小波係數是否為0。透過這樣的設計，我們將這個預測結果帶入JPEG2000原先的編碼系統之中，再運用前文參考的算數編碼去做壓縮。這個混合傳統訊號處理以及機器學習的系統可以被應用在各式各樣基於多解析度的壓縮演算法之中。此架構的精髓在於，我們可以基於一個本身就相當不錯的架構，再套用機器學習的技術來加強。如此得到的編碼效能必然會比原先的結果來得好，而不是像近年許多基於機器學習的壓縮技巧用了很多複雜的理論技術但僅能勉強達到「不輸傳統技術太多」的效能。 資料壓縮亦被廣泛使用在生醫訊號的壓縮上，因為像是心電圖之類的生理量測訊號往往是長時間記錄的，因此如果無損儲存的話，會耗費相當大量的存儲資源。在本論文中，我們也提出了一個非常有效的心電圖壓縮技術。首先我們先透過既有的針對節律的切割排序方法，將一維的心電圖轉換成二維的心電圖，再使用一個新穎的頻帶間的預測編碼技術，最後再使用如前段所述混合機器學習的架構去做壓縮。模擬結果顯示，我們提出的心電圖壓縮技術遠勝於早些時候的心電圖壓縮技術，也能夠略勝或可比擬於近期的一些研究成果。
並列摘要
In most compression algorithms, entropy coding, such as Huffman code and arithmetic code is applied as a means for coding the source symbols into bits with respect to their entropy. Arithmetic codes have been proven to be the most efficient, since it could theoretically achieve bitrates arbitrarily close to the entropy. In this thesis, we propose several efficient techniques that could be applied in arithmetic coding, including table initialization, increasing adjusting step, range adjustment, mutual learning, and the design of local frequency tables. We also provide examples of using the proposed techniques to compress texts, lossless image compression, and lossy image compression. Simulation results show that with these techniques applied, arithmetic coding could have a better coding efficiency. Above all, our proposed techniques on improving arithmetic code could be used in any compression algorithms. Data compression researchers have been applying various analysis techniques in each domain to further improve their compression efficiency. In recent years, machine learning has been a trending research area that was made available by the growth of hardware infrastructures, and people have been applying it on all kinds of tasks. In the past two decades, there have been several machine learning based compression techniques. However, their performances weren’t relatively promising to other signal processing methods. In this thesis, we propose an efficient and robust compression framework that uses machine learning based classification. We applied it on a JPEG2000-like image compression algorithm. First, the image is transformed using discrete wavelet transform (DWT) and each subband is quantized individually. For each DWT coefficient, we use its neighboring dequantized coefficients and dequantized coefficients in its higher-level subband to predict whether or not the current quantized coefficient is zero. Then the binary prediction result is emitted as an additional context, and coded along with the final context-based adaptive binary arithmetic coder (CABAC). Even though our framework is based on the JPEG2000 codec, but it could also be applied to any other compression algorithms that uses multilevel decomposition and context based entropy coding. The essence of this proposed framework is that, instead of building a machine learning based coder from scratch and struggle to compete with other traditional codecs, we build it upon an already decent coder. Thus, it guarantees that it could be at least as good as the coder, and be further improved using the machine learning techniques. Data compression has also been a crucial part in biomedical signals, since signals such as electrocardiogram (ECG), are recorded for a long duration, and could easily overwhelm its storage device if no compression is applied. In this thesis, we also proposed an ECG compression algorithm that aligns the ECG signal into 2D and utilize the framework mentioned previously for image compression with some domain adaptation such as inter-subband DPCM. Results show that our proposed method yields significant improvement over recent works.