基于雙迭代聚能量字典學(xué)習(xí)的數(shù)據(jù)壓縮算法

代少飛，劉文波，王鄭毅，李開宇

（1.南京航空航天大學(xué)自動(dòng)化學(xué)院，南京 211106；2.高速載運(yùn)設(shè)施的無(wú)損檢測(cè)監(jiān)控技術(shù)工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室，南京 211106）

引 言

近年來(lái)，隨著實(shí)際工業(yè)生產(chǎn)要求的不斷提高，計(jì)算機(jī)和數(shù)據(jù)處理設(shè)備日益普及滲透到各行各業(yè)，而模擬通信幾乎已被數(shù)字技術(shù)所取代。日益增長(zhǎng)的信息量給傳輸帶寬、存儲(chǔ)容量和處理速度帶來(lái)很大壓力。例如，Tektronix公司的LPD64示波器的采樣率為25 Gb/s，分辨率為12 bit，單通道每秒鐘將產(chǎn)生300 Gb的數(shù)據(jù)量。

為解決海量數(shù)據(jù)帶來(lái)的“維數(shù)災(zāi)難”，Candes等提出了壓縮感知（Compressed sensing，CS）［1?3］。式（1）表達(dá)了原始信號(hào)x∈Rm的稀疏分解，CS的目的是使用一個(gè)過完備字典D∈Rm×s，使得原始信號(hào)x在字典D下足夠稀疏，其稀疏系數(shù)表示為α∈Rs。式（2）是壓縮感知的數(shù)學(xué)表達(dá)式，原始信號(hào)被觀測(cè)矩陣Φ∈Rd×m觀測(cè)得到觀測(cè)信號(hào)y∈Rd（d?m），實(shí)現(xiàn)信號(hào)的壓縮。在觀測(cè)矩陣的維度d滿足一定下限時(shí)，原始信號(hào)x可以從觀測(cè)信號(hào)中被唯一重構(gòu)［3］。

該理論結(jié)合了信號(hào)的可壓縮性、稀疏性和非相干性，運(yùn)用壓縮與采樣相結(jié)合的方式，測(cè)量經(jīng)過投影之后得到包含信號(hào)全部有效信息的觀測(cè)值，從而使得有限維度的稀疏信號(hào)可以通過遠(yuǎn)少于奈奎斯特定理要求的采樣頻率進(jìn)行采樣，使得低于二倍原信號(hào)帶寬采樣成為可能［2］。

CS系統(tǒng)的壓縮率與重構(gòu)精度依賴于完備字典的建立，越是能夠?qū)?shù)據(jù)稀疏表示的字典，在保證圖像重構(gòu)誤差的條件下越是能夠獲得更大的信號(hào)壓縮比。因此，字典學(xué)習(xí)在基于稀疏分解的數(shù)據(jù)壓縮過程中有著重要的作用。

針對(duì)字典學(xué)習(xí)問題，國(guó)內(nèi)外學(xué)者做出了大量研究。文獻(xiàn)［4］提出了一種適應(yīng)字典的新穎算法動(dòng)態(tài)稀疏字典學(xué)習(xí)（K?sparse variation dictionary，K?SVD），以實(shí)現(xiàn)稀疏信號(hào)表示。文獻(xiàn)［5］針對(duì)人臉圖像壓縮問題，提出了迭代循環(huán)對(duì)齊結(jié)構(gòu)字典（Iterative alignment structure dictionary，ITAD）。文獻(xiàn)［6］根據(jù)字典的雙稀疏性（Double sparsity），提出了自適應(yīng)性的圖像壓縮算法。文獻(xiàn)［7］首先考慮了增量字典學(xué)習(xí)及其在石油管道在線泄漏檢測(cè)中的應(yīng)用?；谖墨I(xiàn)［8］中的方法，使用帶標(biāo)簽的未見樣本對(duì)有監(jiān)督的增量字典進(jìn)行訓(xùn)練。文獻(xiàn)［9］提出了一種基于K?SVD的在線批處理算法，用于學(xué)習(xí)多個(gè)連續(xù)任務(wù)。該方法為持續(xù)學(xué)習(xí)提供了一種有效的算法。最近，文獻(xiàn)［10］提出了一種增量式K?SVD（或增量式動(dòng)態(tài)稀疏字典學(xué)習(xí)（Incremental K?sparse variation dictionary，IKSVD））算法，用于有效表示時(shí)空遙感大數(shù)據(jù)的變化。字典原子每次更新一次，同時(shí)允許在需要時(shí)添加新原子。筆者使用基于熵的標(biāo)準(zhǔn)來(lái)選擇新原子的初始值，方法是先使用舊字典矩陣對(duì)新數(shù)據(jù)進(jìn)行稀疏編碼，然后計(jì)算每個(gè)稀疏系數(shù)向量的熵。熵最大的樣本對(duì)應(yīng)于稀疏且不能由舊字典矩陣準(zhǔn)確表示的樣本，用于初始化新原子。為了加快低比特率視頻編碼中學(xué)習(xí)詞典的收斂速度，文獻(xiàn)［11］提出了一種時(shí)空在線詞典學(xué)習(xí)（Spatio?temporal online diction?ary learning，STOL）算法，以提高K?SVD算法對(duì)原始自適應(yīng)正則化字典學(xué)習(xí)的復(fù)雜度和計(jì)算復(fù)雜度。文獻(xiàn)［12］提出了一種新的遞歸算法，用于在未知的數(shù)據(jù)樣本使用快速正交匹配追蹤（Orthogonal match?ing pursuit，OMP）聯(lián)合執(zhí)行字典學(xué)習(xí)和稀疏編碼。完成增量式字典學(xué)習(xí)，同時(shí)保持性能并大幅減少計(jì)算量。

以上方法都是基于CS框架，都通過一定的已知測(cè)試樣本訓(xùn)練出完備字典D，最后使用觀測(cè)矩陣對(duì)原始信號(hào)進(jìn)行有效壓縮，同時(shí)必須服從有限等距性質(zhì)（Restricted isometry property，RIP），RIP條件要求CS系統(tǒng)的觀測(cè)矩陣的維度d在一定條件下必須高于某一個(gè)限定值，觀測(cè)信號(hào)y才能被唯一重構(gòu)［13］，如此極大地限制了信號(hào)的壓縮率，導(dǎo)致信號(hào)壓縮率有限。鄭思龍等結(jié)合降維算法中保留數(shù)據(jù)結(jié)構(gòu)特征和CS算法中數(shù)據(jù)恢復(fù)能力的優(yōu)點(diǎn)。提出了聚能量字典學(xué)習(xí)（Concentrated dictionary learning，CDL）算法，CDL算法使得測(cè)量矩陣能夠在CS中RIP下界的維數(shù)限制之外具有一定的信號(hào)重建能力［13］。

CDL算法主要通過字典的Г更新和基于K?SVD的字典學(xué)習(xí)得到高維字典D與低維字典P。相比于基于CS框架的數(shù)據(jù)壓縮，CDL算法有更好的數(shù)據(jù)壓縮效果。但是，CDL算法也有許多不足：

（1）CDL算法中的Г更新僅僅是對(duì)字典D做奇異值分解，暴力增加奇異值的數(shù)值。因此，Г更新盡管在數(shù)值上增加了字典的“聚能量”能力，但是破壞了字典的表達(dá)能力。導(dǎo)致信號(hào)的重構(gòu)誤差增大，極大地降低了字典訓(xùn)練過程的收斂速度。

（2）CDL算法的目的通過字典學(xué)習(xí)訓(xùn)練出高維字典D與低維字典P，但在訓(xùn)練過程中僅僅對(duì)高維字典D與原始信號(hào)x基于高維字典D的高維稀疏表達(dá)系數(shù)αH進(jìn)行訓(xùn)練，而忽略了低維字典P與低維信號(hào)y基于低維字典P的低維稀疏表達(dá)系數(shù)αL，導(dǎo)致原始信號(hào)的重構(gòu)誤差增大。

針對(duì)現(xiàn)有算法的不足，本文提出雙迭代的聚能量字典學(xué)習(xí)（Dual?iteration concentrated dictionary learning，DICDL）算法，建立矩陣聚能量變換矩陣與雙循環(huán)迭代訓(xùn)練，增加了字典的奇異性，讓字典的能量更加集中，同時(shí)增加數(shù)據(jù)的重構(gòu)精度。為驗(yàn)證算法的有效性，將DICDL算法與CDL［13］、CS+K?SVD等算法的數(shù)據(jù)壓縮性能作比較。結(jié)果表明，相比于CDL算法，本文提出算法字典學(xué)習(xí)收斂速度提升了3倍以上，此外，該方法既可以得到較高的壓縮比又有著更高質(zhì)量的重構(gòu)信號(hào)。

1 CDL算法

1.1 CDL算法原理

CDL算法是以CS框架為基礎(chǔ)，但不同于觀測(cè)矩陣Φ的選取方式，CDL算法直接將原始信號(hào)x∈Rm基于高維字典D∈Rm×s的高維稀疏系數(shù)A∈Rs通過低維字典P∈Rd×s投影到低維子空間y∈Rd（d?m）中，如式（3）所示，稀疏系數(shù)A作為高維原始信號(hào)x與低維信號(hào)y的連接橋梁［13］。

式中：噪聲ε1∈Rm，ε2∈Rs。

為了減小原始信號(hào)x的重構(gòu)誤差，保留信號(hào)的特征，低維字典P需要滿足

式中：σ1、σ2為ε1、ε2的方差。

由式（4），可認(rèn)為低維字典P是高維字典D的主成分，在CDL算法中低維字典P的計(jì)算公式為

式中UTd為高維字典D的奇異值分解的左奇異矩陣U的前d列的轉(zhuǎn)置。

1.2 CDL算法字典預(yù)處理

為了保證原始信號(hào)x在高維字典D下表示系數(shù)足夠稀疏以及低維字典P保留字典D更多的主成分。CDL算法對(duì)字典D做Г更新，Г更新的具體細(xì)節(jié)如下：

（1）奇異值分解

式中Λd為DTD的奇異值分解的奇異值矩陣Λ的前d行d列。

（2）奇異值更新

式中：k表示字典的列數(shù)，td表示主成分閾值。

（3）對(duì)D奇異值分解

（4）更新字典的奇異值矩陣

（5）更新字典

2 DICDL算法

2.1 基于初等變換的字典聚能量變換

CDL算法為了使字典D的前d維聚集更多的能量，采用Г更新暴力增加字典D的奇異值，但改變了字典D的表達(dá)能力，增大了信號(hào)的重構(gòu)誤差，導(dǎo)致CDL算法訓(xùn)練的收斂速度慢。然而，奇異值往往對(duì)應(yīng)著矩陣中隱含的重要信息，且重要性和奇異值大小正相關(guān)。矩陣越“奇異”，其越少的奇異值蘊(yùn)含了更多的矩陣信息，矩陣的信息熵越小，其行（或列）向量彼此越相關(guān)［14］。DICDL算法利用初等變換不改變字典的秩與表達(dá)能力的特性［15］，建立了?變換，用于增大字典D列向量間的相關(guān)性，使字典D的前d維聚集更多的能量，但保證數(shù)據(jù)在字典D下表示系數(shù)足夠稀疏。

為了增大字典D列向量間的相關(guān)性和字典D的冗余度，使得字典D能量更加集中，同時(shí)不影響字典D的表達(dá)能力，建立了變換矩陣Q，DICDL算法?變換具體實(shí)現(xiàn)步驟如下：

（1）建立變換矩陣Q為

式中：r為變換的調(diào)節(jié)參數(shù)，Qi表示單位方陣En×n的第i列向量第1行與第i行的值分別為r，1-r。

（2）更新字典

式中D為K?SVD訓(xùn)練出的字典。

上述過程記作

使用本文提出算法的?變換（r=0.76）和CDL算法的Г（td=0.9）更新對(duì)DCT字典進(jìn)行更新，分別得到DICDL字典與CDL字典。如圖1所示，DCT字典的前16維主成分占DCT字典6%的能量，CDL字典的前16維主成分占CDL字典28%的能量，DICDL字典的前16維主成分占DICDL字典52%的能量。因此，本文提出的?變換比CDL算法的Г更新更能集中字典的主成分能量。

圖1 不同字典的奇異值分布Fig.1 Singular values distribution of differ?ent dictionaries

2.2 理論推導(dǎo)

DICDL算法中?變換的目的是在保證數(shù)據(jù)在字典D下表示系數(shù)足夠稀疏的同時(shí)，使字典D的前d維聚集更多的能量。圖1中的實(shí)驗(yàn)結(jié)果表明，DICDL算法中?變換比CDL算法的Г更新更能集中字典的主成分能量，下面將分別證明?變換字典D經(jīng)歷?變換后最大的奇異值σmax增大，最小的奇異值σmin減小，且字典D依然能夠稀疏表達(dá)原始數(shù)據(jù)。

記字典D=［d1d2d3…dn］，原始數(shù)據(jù)集為X=［x1，x2，…，xn］（xi∈Rm），假設(shè)數(shù)據(jù)xi在字典D下表示稀疏系數(shù)有4個(gè)非零項(xiàng)，記為Ai=［…ao…am…ap…aq…］（Ai∈Rs）。

字典D經(jīng)歷?變換的結(jié)果為

式中：在Q矩陣對(duì)角線元素最小值對(duì)應(yīng)位置為1，其他位置為0；?在Q矩陣對(duì)角線元素最大值對(duì)應(yīng)位置為1，其他位置為0；且兩者均為列向量。

由式（17、18）可以看出?變換能夠使字典的小奇異值變得更小，把更多的能量集中在較大奇異值上，使字典D的前d維聚集更多的能量。通過式（20）可以看出，字典D經(jīng)過?變換處理后得到的字典D?依然能夠稀疏地表示原始數(shù)據(jù)xi。

2.3 DICDL算法實(shí)現(xiàn)

CDL算法通過字典學(xué)習(xí)訓(xùn)練出高維字典D與低維字典P，在訓(xùn)練的過程中僅僅對(duì)高維字典D與原始信號(hào)x基于高維字典D的高維稀疏表達(dá)系數(shù)A進(jìn)行訓(xùn)練，而忽略了低維信號(hào)y與稀疏表達(dá)系數(shù)A的訓(xùn)練。導(dǎo)致原始信號(hào)的重構(gòu)誤差增大。如圖2所示，為了減小信號(hào)的重構(gòu)誤差，本文提出了雙迭代的聚能量字典訓(xùn)練，在訓(xùn)練過程中對(duì)高維字典D，低維字典P和稀疏系數(shù)A同時(shí)訓(xùn)練，有效地減小了數(shù)據(jù)的重構(gòu)誤差。

圖2 DICDL算法示意圖Fig.2 Schematic diagram of DICDL algorithm

DICDL算法的詳細(xì)實(shí)現(xiàn)步驟如下所示：

輸入：訓(xùn)練數(shù)據(jù)集X，迭代次數(shù)T。

輸出：訓(xùn)練好的高維字典D與低維字典P。

初始化：把數(shù)據(jù)集X分割為數(shù)據(jù)列xi（256×1），令X=［x1，x2，…，xn］（xi∈Rm），字典D初始化為DCT字典。

（1）對(duì)字典D作奇異值分解：D=UΘVT；

（2）分別利用式（5）計(jì)算低維字典P和式（3）計(jì)算低維信號(hào)Y=［y1，y2，…，yn］（yi∈Rs）；

（3）使用正交匹配追蹤算法得到稀疏表示系數(shù)A=［A1，A2，…，An］（Ai∈Rs）［16?17］：

（7）根據(jù)式（8）對(duì)字典D做奇異值分解得到Ud，使用式（5）計(jì)算得到低維字典P。

3 仿真實(shí)驗(yàn)及結(jié)果

為驗(yàn)證本文提出算法的有效性，選擇鋼軌裂紋的差分渦流檢測(cè)數(shù)據(jù)［18］中不同檢測(cè)速度（50、70、100、150、200、250、300 km/h）的I路、Q路、幅值和相位共28組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)中分別把28組信號(hào)分成兩個(gè)部分分別作為訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)。實(shí)驗(yàn)以CS+KSVD［19］與CDL［13］作為對(duì)比算法，其中，CDL算法的主成分閾td=0.9，DICDL算法的變換調(diào)節(jié)參數(shù)r=0.3。實(shí)驗(yàn)中以訓(xùn)練誤差收斂速度，壓縮比（Compression ratio，CR），重構(gòu)信號(hào)質(zhì)量選用百分比均方根誤差（Percentage root?mean?square differ?ence，PRD）等作為實(shí)驗(yàn)評(píng)價(jià)指標(biāo)。

CR與PRD的計(jì)算公式如下

式中：Sin為原始信號(hào)的大小，Sout為信號(hào)被壓縮后的大小，X為原始信號(hào)，X?為重構(gòu)信號(hào)。

基于稀疏分解的數(shù)據(jù)壓縮過程主要分為3個(gè)部分，如圖3所示，分別為字典學(xué)習(xí)（離線）、稀疏分解（編碼端）和信號(hào)重構(gòu)（解碼端）。實(shí)驗(yàn)預(yù)處理階段把數(shù)據(jù)分為兩組，分別為訓(xùn)練數(shù)據(jù)集與測(cè)試數(shù)據(jù)集，兩組數(shù)據(jù)均被截取為256個(gè)點(diǎn)長(zhǎng)度的均勻分塊，字典尺寸設(shè)置為256×256，并且去除信號(hào)直流分量；實(shí)驗(yàn)中使用正交匹配追蹤算 法（Orthogonal matching pursuit，OMP）［20?22］作為稀疏分解算法。

圖3 壓縮與解壓縮流程圖Fig.3 Data compression and decompression process

如圖4所示是28組信號(hào)在DICDL、CDL以及KSVD+CS算法壓縮下，當(dāng)壓縮比分別為64和16時(shí)重構(gòu)信號(hào)質(zhì)量對(duì)比。其中，圖4（a）中信號(hào)壓縮比CR=64，圖4（b）信號(hào)壓縮比CR=16。從圖4中結(jié)果對(duì)比可以發(fā)現(xiàn)，本文提出的DICDL算法相比于CDL算法和KSVD+CS算法，在相同的壓縮比下，信號(hào)的重構(gòu)失真度更低。在壓縮比CR=64時(shí)，DICDL算法對(duì)信號(hào)的重構(gòu)失真度低于9.6%；在壓縮比CR=16時(shí)，DICDL算法對(duì)信號(hào)的重構(gòu)失真度低于7.6%。

圖4 不同壓縮比的渦流信號(hào)恢復(fù)質(zhì)量Fig.4 Restoration quality of eddy current signals with different compression ratios

實(shí)驗(yàn)中分別使用DICDL、CDL以及KSVD+CS算法對(duì)檢測(cè)速為50 km/h的相位信號(hào)進(jìn)行壓縮，分別改變DICDL和CDL低維字典的維度，以及KSVD+CS的觀測(cè)矩陣維度，DICDL、CDL以及KSVD+CS算法在各自字典下對(duì)實(shí)驗(yàn)信號(hào)進(jìn)行重構(gòu)。如圖5所示，3種算法對(duì)信號(hào)的重構(gòu)精度隨著測(cè)量維度的增加而增加，在相同的測(cè)量維度下，本文提出DICDL算法的重構(gòu)精度要高于其他兩種算法。究其原因，本文提出DICDL算法訓(xùn)練出的聚能量字典比一般字典學(xué)習(xí)算法訓(xùn)練出的字典能量更加集中。因此，當(dāng)保留字典較少的維度時(shí)，保留了更多的信號(hào)。此外，DICDL算法采用了高維字典與低維系數(shù)的雙迭代聯(lián)合訓(xùn)練，增加了高維字典與低維字典的耦合性，增加了信號(hào)的重構(gòu)精度。

圖5 信號(hào)在不同測(cè)量維度下的重構(gòu)精度（PRD）Fig.5 Signal reconstruction accuracy(PRD)under different measurement dimensions

如圖6所示，實(shí)驗(yàn)使用本文提出的DICDL算法對(duì)檢測(cè)速度70 km/h的幅值信號(hào)做壓縮比分別為64與16的數(shù)據(jù)壓縮，并對(duì)信號(hào)進(jìn)行重構(gòu)。由圖6（a~f）波形對(duì)比可知，DICDL算法對(duì)信號(hào)壓縮比CR=64時(shí)，重構(gòu)信號(hào)依然擁有很高的精度。因此，DICDL算法能夠在高壓縮比的同時(shí)保證重構(gòu)信號(hào)高質(zhì)量。

圖6 在不同壓縮比下的重構(gòu)信號(hào)Fig.6 Reconstructed signals under different compression ratios

為了進(jìn)一步驗(yàn)證本文提出DICDL算法的性能，實(shí)驗(yàn)分別實(shí)驗(yàn)DICDL算法與CDL算法對(duì)28組信號(hào)進(jìn)行字典學(xué)習(xí)，并記錄了字典學(xué)習(xí)過程中的誤差收斂速度，為了方便討論分別把不同的幅值信號(hào)，相位信號(hào)，I路信號(hào)與Q路信號(hào)的收斂迭代次數(shù)取平均數(shù)，具體結(jié)果如表1所示。由實(shí)驗(yàn)結(jié)果可知，本文提出DICDL算法相比于CDL算法擁有更快的收斂速度，速度提升了3倍以上。究其原因，本文提出DICDL算法的?變換比CDL算法的Г更新聚能效果更好，且不改變字典的表達(dá)能力，測(cè)試信號(hào)在?變換后的聚能量字典下的表達(dá)系數(shù)依然稀疏。因此，DICDL算法比CDL算法字典學(xué)習(xí)過程的收斂更加迅速。

表1 不同信號(hào)訓(xùn)練的平均迭代次數(shù)Table 1 Average iterations for different signal train?ing methods

4 結(jié)束語(yǔ)

本文提出了一種雙迭代的聚能量字典學(xué)習(xí)算法，該算法根據(jù)矩陣的奇異值特性，引入了?變換，增加字典的能量集中性；同時(shí)利用聚能量高維字典與低維字典的關(guān)系，建立了雙循環(huán)迭代訓(xùn)練。增加字典的能量集中性與字典的表達(dá)能力。實(shí)驗(yàn)結(jié)果表明，相比于傳統(tǒng)壓縮方法，DICDL算法不僅字典訓(xùn)練的收斂速度快，并且訓(xùn)練出的聚能量字典用于數(shù)據(jù)壓縮將擁有更高的重構(gòu)精度。因此，可以預(yù)見本文算法在不同維度數(shù)據(jù)壓縮的應(yīng)用中具有巨大的應(yīng)用潛力。然而，DICDL算法盡管擁有更快的收斂速度，但面對(duì)海量的數(shù)據(jù)壓縮仍然略顯不足，在未來(lái)的工作中，作者將考慮優(yōu)化基于DICDL算法的重構(gòu)算法，增加基于DICDL壓縮算法的實(shí)時(shí)性，降低數(shù)據(jù)傳輸、存儲(chǔ)和處理過程的資源消耗。