壓縮感測的時頻分析方法

由於硬體方面的快速發展，運算資源相較於數十年前更加容易取得。近年來，壓縮感測藉由運算速度的提升拓展了我們的視野，與限制於著名的夏農取樣定理(Shannon’s sampling theorem) 的傳統取樣方法有所不同。壓縮感測利用了訊號的稀疏性來達成突破傳統取樣率的限制，讓我們認為也可以利用其他方面的特性來達成同樣的效果。因此，我們嘗試使用在信號處理領域常見的時頻分析工具來做為突破點。眾所周知的是，一個訊號的最低取樣點數限制與時頻分析圖上的面積有著正相關，而這正是我們要用來設計壓縮演算法的關鍵概念。在這篇碩士論文中，我們將會運用時頻分析來實作對於壓縮聲音訊號的應用。不同於廣泛出現在生活中的MP3與M4A壓縮演算法，被捨棄的資料並非由人類的聽覺範圍決定，取而代之的是時頻分析圖上小於臨界值的點或是面積較小的區塊。時頻分析的結果會被分為各個不同的區塊，作為初步的切割結果。接著，我們將切割完的時頻分析做時頻重配(time-frequency reassignment)，運用提出的預切法(pre-cut scheme)、間隙連接法(gap connection scheme)、頭尾法(head and tail scheme)以及頻寬估計(fixed bandwidth estimation)，因而得到更進一步的信號成分分割結果。我們的下一步為近似信號成分的分割結果。對於每個信號成分，我們使用一般化調變(generalized modulation)來進行降頻並且降低單一成分的最大頻寬。接著，我們使用兩種方法來對調變過後的信號成分近似並壓縮，分別為降採樣法(the downsampling method)及勒壤得多項式法(the Legendre polynomial method)。降採樣法由於信號成分較小的頻寬，可以有效降低所需要的採樣點數，進而達到壓縮的效果。勒壤得多項式法則是經由勒壤得多項式來尋找信號成分的稀疏表達方式，轉換成較少係數的結果。壓縮過後的資料與還原資料所需要的參數共同被編碼為一個封包，得到最後的壓縮結果。封包結果容易解碼且只需逆向操作即可進行還原重建。我們所提出的演算法，藉由在時頻分析上切割信號，以降低時頻分析圖上多餘的空白處，因而減少需要儲存的壓縮信號。雖然運算的時間相對較長，但在部分信號相較於常見的壓縮格式，可以同時擁有較高壓縮率以及較低重建誤差率的明顯較佳結果。

關鍵字

壓縮感測；時頻分析；時頻重配；一般化調變；降採樣法；勒壤得多項式法

並列摘要

Due to the fast developments in hardware, the computation resources are available more easily than decades ago. In recent years, compressive sensing broadens our horizons by the promotion of the computation speed, which is different from the conventional sampling approaches limited to the celebrated Shannon’s theorem. The sparsity properties of signals are utilized by compressive sensing to break thorough the limitation of the traditional sampling rate, which makes us consider that the identical effect can be achieved by the characteristics in other aspects. As a result, we manage to take advantage of the time-frequency analysis tool commonly used in the field of the signal processing as a breakthrough point. It is known that the lower bound of the number of sampling points is positively associated with the area of the time-frequency analysis, which is exactly the key concept of designing our algorithm to compress the target signal. In this master thesis, we use the time-frequency analysis to implement the application of the vocal signal compression. Different from the widespread MP3 and M4A compression algorithms in life, the data discarded is determined by the pixels below the threshold or the blocks with small area instead of the human hearing capability. The consequence of the time-frequency analysis is divided into several blocks as the primary segmentation result. Then, we execute the time-frequency reassignment to the segmentation result with proposed schemes, such as the pre-cut scheme, the gap connection scheme, the head and tail scheme, and the fixed bandwidth estimation, to obtain the further signal components segmentation result. Our next step is to approximate the segmentation result of the signal components. For each component, we utilized the generalized modulation to lower the frequency and decrease the maximum bandwidth of single component. Then, we adopt two methods to approximate and compress the modulated signal components, which are the downsampling method and the Legendre polynomial method. The downsampling method can effectively decrease the number of sampling points to compress the data due to the smaller bandwidths of the signal component, while the Legendre polynomial method manages to find the sparse representations of the signal components by the Legendre polynomials and transforms the signal into less coefficients. The compressed data and the parameters needed for recovering the data are encoded into a package, which is the final compression result. The packages are easily decoded and able to be reconstructed with only reverse operation. Our proposed algorithm divides the target signal with the time-frequency analysis to reduce the redundant space on the figure and hence decreases the compressed signal for storage. In spite of relatively large computation time, the better result of higher compression ratio and lower reconstruction error holds in the meanwhile in some cases, compared to common compression formats.

並列關鍵字

compressive sensing ； time-frequency analysis ； time-frequency reassignment ； generalized modulation ； downsampling method ； Legendre polynomial method

參考文獻

[1] E. Candès and M. Wakin. “An introduction to compressive sampling.” IEEE Signal Processing Magazine, vol. 25, no. 2, pp. 21-30, Mar. 2008.

Google Scholar

[2] D.L. Donoho and X. Huo, "Uncertainty principles and ideal atomic decomposition," IEEE Transaction on Information Theory, vol. 47, no. 7, pp. 2845-2862, Nov. 2001.