用於壓縮腦波訊號之壓縮感知與霍夫曼編碼結合架構

A Framework for EEG Compression with Compressive Sensing and Huffman Coding

李致翰(Li, Chih Han)

指導教授 ： 馬席彬

國立清華大學/電機資訊學院/電機工程學系/碩士(2014年)

摘要

壓縮感知為一個新興的壓縮技術，在這篇論文裡，我們將它應用在腦波訊號。而壓縮感知有兩個使用的條件，一個為稀疏性，另一個為非相關性，但由於腦波不夠稀疏，所以腦波訊號無法高度壓縮，因為高度壓縮的訊號會無法被重建，因此我們希望能找到讓壓縮感知提升壓縮率的方法。
而文獻中的方法可分為三類，第一類是加強解壓縮端的重建演算法，第二類為尋找一個適當的轉換，讓訊號經轉換後能變稀疏，第三類為結合其他壓縮辦法，而在這裡我們採用了第一和第三類方式去實現。首先，我們提出一個複雜度為O(KMN) 的重建演算法─改良版疊代偽反乘法 (MIPIM) ( N 為原始訊號維度，M 為量測向量的維度，K 為稀疏程度 )， 其優勢在於複雜度比大部分重建方法還低，接者我們還將這個改良版疊代偽反乘演算法延伸成多量測向量 (MMV) 的版本，稱作同步的改良疊代偽反乘法 (SMIPIM)，其目的在於一次重建全部通道上的訊號和利用不同通道訊號的相關性來提升重建品質。壓縮上一般是使用正規化均方誤差 (NMSE) 來評斷重建的好壞，而在重建訊號的比較上，同步的改良疊代偽反乘法相較於經典重建方法誤差可以減少0.06。
另外在結合其他壓縮辦法的部分，我們改良一個已發表的系統，此系統的架構為壓縮感知和霍夫曼編碼的結合，其運作是先於接收端進行通道資訊運算，之後再將資訊傳給發送端，發送端收到後，就能利用它將壓縮感知和霍夫曼編碼有效地結合，提升壓縮的能力，但上述的系統有個缺陷，計算通道資訊上耗費的時間過長，導致無法實現即時的遠端醫護，因此，我們在這邊提出了一個新演算法來取代它，將原本複雜度為O(L^5)降成O(L^2) (L 為通道數目)，此外我們還有測試運算時間，在同設定下，我們的演算法快了10^5 倍。
最後在整個系統的模擬方面，我們用了上述的架構並配合我們的演算法來計算通道資訊並壓縮，而接收端我們用了同步的改良疊代偽反乘法進行重建，結果顯示當壓縮比為3 比1，我們系統的正規化均方誤差為0.0672，若只用壓縮感知搭配塊稀疏貝氏學習演算法(BLBL-BO) 重建出的誤差為0.1554 (塊稀疏貝氏學習為目前最強力的重建演算法)，另一方面，在最低容忍誤差為0.09 的條件下，我們測得了相對應的壓縮率為0.31，並使用這個壓縮率去估算有限頻寬下能傳輸的通道數目，估測結果為藍芽2.0 傳輸可多傳16 個通道的訊號，而紫蜂的話能多傳35 個通道。

關鍵字

壓縮感知 ； 腦波訊號壓縮

並列摘要

Compressive sensing (CS) is an emerging technique for data compression in recent years. In this thesis, it is used to compress electroencephalogram (EEG) signals. CS includes two major principles. The one is the sparsity, and the other is incoherence. However, the EEG
signal is not sparse enough. Thus, CS can only recover the compressed EEG signals in low compression ratios. Under high compression ratios, the recovery of compressed EEG signals fails after the compression. The compression ratios where EEG can be reconstructed with high quality is not high enough to let the system become energy-efficient, so the compression will be not meaningful. Thus, we want to find a solution to make CS become practical in compressing EEG signals when high compression ratios are adopted.
From surveying literatures, the approaches to increase performance in CS can be separated into three classes. First, design a more strong reconstruction algorithm. Second, find a dictionary where the EEG signals can have sparse presentation in such transform domain. Lastly, combine the CS with other compression techniques. Here we take the first and third approaches to achieve the goal. First of all, we proposed a modified iterative pseudo-inverse multiplication (MIPIM) with the complexity O(KMN) where M is the dimension of the measurements, N is the dimension of the signal, and K is the sparse level. This complexity is lower than the most existing algorithms. Next, we extend MIPIM into a multiple measurements (MMV) algorithm. It is called as simultaneously MIPIM (SMIPIM). This aims at recovering all channel signals at the same time and taking the correlation among channels to increase performance. The SMIPIM can reduce normalized mean square error (NMSE) by 0.06 comparing with the classical algorithms in CS.
For the part of combining the CS with other compression techniques, we adopt an existing framework which takes an information from server or receiver node to combine CS and Huffman coding efficiently. The framework was proposed to increase the compression to apply to the telemedicine with EEG signals, but we found a shortcoming. It takes a long computational time on running the algorithm which produces information. It will make the instant telemedicine unavailable because sensors can not transmit data until the information are received. Therefore, we propose an algorithm to replace the existing one. The complexity changes from O(L^5) to O(L^2) where L is the number of channels. In our experiment, our algorithm is faster 10^5 times than the existing one.
Finally, we carried out the simulation of entire system. We simulated the framework with our proposed algorithm for computing the information of correlation of channels and our SMIPIM for reconstruction. In a compression ratio 3 : 1, the NMSE is 0.0672 , and the
original CS framework with Block Sparse Bayesian Learning Bound Optimization (BSBLBO) is 0.1554. On the other hand, depending on the minimum acceptable NMSE which is
0.09 for EEG signals, we have a compression ratio 0.31. Moreover, we take the compression ratio to estimate how many channels we can transmit in a fixed transmission bandwidth. The result shows that the number of channels can increase 16 with Bluetooth 2.0 and 35 with ZigBee for wireless transmission after the work.

並列關鍵字

Compressive Sensing ； EEG compression

參考文獻

[1] E. Candes and M. Wakin, “An introduction to compressive sampling,” IEEE Signal Processing

[2] L. Merino and L. Mendoza, “Robust Compression Using Compressive Sensing (CS),”

“A cmos-based microelectrode array for information processing with natural neurons,”

in 3rd International IEEE/EMBS Conference on Neural Engineering, (CNE), May 2007,

A. Ikeda, F. Jose C Luccas, and P. Rappelsburger, “Ifcn standards for digital recording