半張量積壓縮感知模型的快速重構方法

王金銘，葉時平，尉理哲，許森，蔣燕君

?

半張量積壓縮感知模型的快速重構方法

王金銘，葉時平，尉理哲，許森，蔣燕君

（浙江樹人大學信息科技學院，浙江 杭州 310015）

壓縮感知；觀測矩陣；半張量積；存儲空間；重構時間

1 引言

隨著壓縮感知（CS, compressed sensing）[1-3]理論研究的深入，壓縮感知在大尺寸圖像壓縮采樣和重構的應用研究中一直存在著亟待改善和解決的問題。

1) 信號壓縮采樣方面，雖然利用隨機觀測矩陣進行壓縮采樣具有理論上的完美特性，但由于其具有的隨機特性，隨機矩陣在硬件實現、存儲分配和重構算法構造上，都需要占用大量的存儲空間和內存空間，在實際應用中受到很大的限制。

2) 信號優化重構方面，隨著圖像尺寸的增大，重構過程運算量將呈指數級增長，這使圖像的重構過程非常耗時，大大降低了壓縮感知重構的實時性。當設定采樣率為0.5時，利用迭代重加權（IRLS, iterative re-weighted least square）[4-5]算法重構一幅256像素×256像素大小的圖像，所需時間約為60 s左右；若重構一幅512像素×512像素大小的圖像，則約需1 000 s；但若重構一幅大小為1 024像素×1 024像素大小的圖像，其重構時間則是無法忍受的。

針對問題1)，相關科研人員分別提出了分塊壓縮感知（BCS, block compressed sensing）[6-8]、Kronecker壓縮感知[9-11]、結構化觀測矩陣[12-13]、低秩觀測矩陣[14-15]、確定性觀測矩陣[16-17]等方法，用于降低觀測矩陣所需的存儲空間。而針對重構實時性問題，雖然有一些重構算法具備較快的重構速度，如正交匹配追蹤算法（OMP, orthogonal matching pursuit）[18]，但其重構精度卻稍劣于IRLS的重構方法[19]。

因此，找到一種在保證重構質量的前提下，既能有效降低觀測矩陣（特別是隨機觀測矩陣）的存儲空間，又能降低計算復雜度、有效提升重構實時性的重構算法，仍是一個需要研究的課題。

本文將討論一種基于半張量積的壓縮感知（STP-CS, semi-tensor product CS）方法。該方法利用低階隨機矩陣對原始信號進行全局采樣，通過對測量值進行分組處理，再結合IRLS方法進行重構。利用該方法既可成倍降低觀測矩陣的存儲空間，又可在保證重構精度的前提下，大大提升重構的實時性。

2 半張量積壓縮感知方法

根據附錄1中所述的半張量積理論，本文的半張量積壓縮感知模型定義為

或

2.1 相關性分析

展開式(3)，有

(4)

對于式(4)，利用半張量積矩陣乘法定義，有

根據自相關定義，有

=++…++…+=(8)

整理式(8)，有

=(10)

對于一個選定的觀測矩陣，有

且>0，則有

從而，對于式(11)，有

2.2 測量數下限

展開式(12)，有

利用半張量積乘法原理，有

由式(14)可知，利用STP-CS模型在對原始信號進行采樣的過程中，并沒有改變線性采樣的本質，測量值同樣是用原始信號的線性組合來表示的。為了更加清晰地了解STP-CS的壓縮采樣過程，令=16，=12，=4，則有

觀察式(15)，將測量值12×1進行分組，有

從另一個角度來看，本文所述的STP-CS方法也具備了分布式壓縮感知的功能，即將長度為的原始信號劃分成組信號群，且該組信號群能在同一個稀疏基上進行稀疏表示，并利用低階觀測矩陣對組信號群分別進行壓縮采樣，得到組測量群。

此外，據式(16)~式(19)所示，本文所述的STP-CS的壓縮采樣方法，完全與傳統壓縮感知方法一樣，能夠保留原始信號所攜帶的信息，從而能保證對原始信號的精確重構。

便能保證精確重構長度為的原始信號。

2.3 重構算法

雖然IRLS具有較高的重構精度，但由于IRLS算法的天然特性，利用其對大尺寸圖像進行全局重構時，實時性仍有待提升。為此，本文結合STP-CS壓縮采樣特點，提出了一種基于IRLS的分組重構方法，可以有效提升重構的實時性，且保持了信號的重構質量。

從而，本文所涉及的l-范數(0<<1)的迭代重加權分組重構算法如下。

1) 初始化=1，取列測量值中的第列；

2) 根據式(21)對該列測量值進行分組；

10) 執行=+1，判斷=？若不滿足，返回步驟3)，繼續迭代計算，若滿足則退出迭代；

2.4 計算復雜度

以上，本文著重討論了利用半張量積壓縮感知原理對原始信號進行壓縮采樣和分組重構的理論方法。由于觀測矩陣在壓縮感知的采樣及重構過程中擔任著關鍵角色，其矩陣大小是影響數據存儲量及計算復雜度的關鍵因素。從而利用本文所述方法采用低階觀測矩陣既有益于降低數據的存儲空間和計算復雜度，同時利用分組重構方法也有益于提升重構的實時性。

3 實驗結果與分析

為驗證本文所述方法的有效性，本文針對2維灰度圖像設計了2組驗證實驗，第一組設定不同的采樣率，分別構建不同大小的高斯隨機矩陣進行采樣，然后利用l-范數(0<<1)的IRLS方法進行重構，比較重構圖像的峰值信噪比（PSNR, peak signal to noise ratio）和重構時間。第二組設定不同的采樣率，與BCS[6]和Kronecker[10]等低存儲壓縮感知方法進行了比較。

實驗中采用的2維灰度圖像分別為256像素×256像素的Peppers、512像素×512像素的Lena、1 024像素×1 024像素的Mandrill以及2 048像素×2 048像素的Cameraman。實驗平臺配備了Intel i7- 4600 CPU，2.1 GHz主頻，8 GB內存，64位Windows 8操作系統，仿真軟件采用Matlab R2010b。

首先利用低階觀測矩陣結合式(2)進行半張量積壓縮采樣后，得到對應的測量值；隨后對測量信號進行分組，并利用本文所述的l-范數方法進行重構，得到重構的小波系數；通過對重構結果重新進行排列，進而得到重組后的重構小波系數；最后利用小波逆變換，得到重構圖像。實驗中，對于每一幅灰度圖像的稀疏系數，根據設定的采樣率及觀測矩陣的大小，分別進行了50次測試，以觀察其重構圖像質量，并對重構圖像的峰值信噪比和重構時間進行評估。由于篇幅問題，僅在圖1~圖3中列出了采樣率為0.5時的Peppers、Lena及Mandrill的重構結果，其重構圖像是在50次重構結果中隨機選取的。

圖1~圖3中的(b)分別表示對2維原始圖像的重構結果。從圖1~圖3可知，對于3種不同大小的原始圖像，當=2、4、8、16、32時，其相應的重構圖像質量與傳統壓縮采樣方法（=1）基本一致。為進一步對重構圖像的質量進行評估，表2和表3分別列出了利用6種不同大小的高斯隨機觀測矩陣進行50次采樣和重構后，其重構圖像峰值信噪比和重構時間的平均值。

表1 半張量積壓縮感知模型的觀測矩陣大小(=0.5)

圖1 不同大小的觀測矩陣采樣重構2維圖像比較（Peppers，M=128，N=256）

圖2 不同大小的觀測矩陣采樣重構2維圖像比較（Lena，M=256，N=512）

圖3 不同維數觀測矩陣重構2維圖像比較（Mandrill，M=512，N=1 024）

表2 不同大小的高斯隨機觀測矩陣重構2維圖像峰值信噪比

表3列出了上述50次壓縮采樣和重構所需的時間。由表3可知，當=1時，對于全部采樣率，Peppers重構所需的平均時間約為61.25 s；當=2時，重構的平均時間約為17.875 s，速度提升了3倍多；隨著繼續增大，重構所需的時間持續降低，速度最快提升了近11倍多（當=8時）。隨著圖像尺寸的增大，其重構時間呈指數級增加，例如Lena，當=1時，對于全部采樣率，Lena重構所需的平均時間約為1 579 s；當=2時，重構的平均時間約為268 s，速度提升了近6倍；隨著繼續增大，重構所需的時間持續降低，速度最快提升了近69倍（當=16時，平均重構時間僅約為23 s）。而對于Mandrill而言，當=1時，隨著采樣率的增加，其所需的重構時間是無法忍受的，而采用本文所述的分組重構方法，其重構所需的平均時間僅約為99 s（當=32時），重構速度加快了近260倍，極大地提升了大尺寸圖像重構的實時性。

綜上所述，利用本文所述的低階觀測矩陣進行壓縮全局采樣和分組重構的方法，在保證重構質量的前提下，既可成倍降低觀測矩陣所需的存儲空間，又可大大提升重構的實時性，這對于進一步拓展壓縮感知的實際應用有非常積極的意義。

本文旨在保證重構質量的前提下，針對大尺寸圖像數據，降低觀測矩陣的存儲空間并且同時提高重構實時性，為進一步驗證本文所述方法的有效性，我們利用2 048像素×2 048像素大小的Cameraman圖像進行了一組測試，設定采樣率為0.5，分別取1、8、16、32或64，實驗進行了10次，其重構圖像峰值信噪比和重構時間的平均值如表4所示。

表3 不同大小的高斯隨機觀測矩陣重構2維圖像重構時間

表4 不同大小的高斯隨機觀測矩陣重構Cameramen圖像測試結果（2 048像素×2 048像素，=0.5）

由表4可知，本文所述方法適用于大尺寸圖像，特別是在圖像重構的實時性上有非常大的提升作用。

為了更為直觀地展示本文所述方法的有效性，我們選取了=1、16及32時Lena圖像的重構值和重構時間繪制了關于重構時間、值和采樣率的3維視圖，如圖4所示。圖4展現了本文所述方法在重構實時性上的提升作用。

圖4 不同維數觀測矩陣重構2維圖像性能比較（Lena，=0.5）

第二組與其他低存儲壓縮感知方法的對比實驗中，主要與文獻[6]所示的分塊壓縮感知方法和文獻[10]中的Kronecker壓縮感知方法進行了比較。BCS壓縮采樣時人為地將原始圖像分成大小相等的若干塊（如16×16），隨后根據設定的采樣率，構建觀測矩陣對原始圖像進行分塊采樣和重構；Kronecker壓縮感知方法首先根據設定的采樣率構建一個或若干個低階觀測矩陣，隨后利用Kronecker運算構建一個大小與傳統壓縮感知方法一樣的觀測矩陣（×）進行壓縮采樣并進行全局重構；本文所述的STP-CS方法根據設定的采樣率首先構建一個較小的觀測矩陣（>1）對原始信號進行全局采樣，隨后進行分組重構。對于3種不同的低存儲化壓縮感知方法，從本質上來說就是采用的觀測矩陣大小與壓縮采樣方式的區別。

根據表5中值所示，對于相同的采樣率，利用本文所述方法，即便采用=32時的高斯隨機觀測矩陣，其所得重構圖像的值均明顯高于文獻[10]的Kronecker方法所得結果，且相比文獻[6]的BCS方法，本文方法均能接近或超過BCS方法所得結果。此外，對于表6中所示的重構時間，本文方法明顯快于Kronecker方法；且隨著采樣率的提高，本文所述方法的重構速度要明顯優于BCS方法。

需要指出的是，在對比實驗中，對于BCS方法，其塊大小的選擇對重構質量有非常大的影響，且對于Kronecker方法，其進行Kronecker運算的2個觀測矩陣大小對重構質量也同樣有著非常大的影響。而利用本文所述方法，其選用的觀測矩陣大小基本對重構質量沒有影響。

綜上所述，本文所述的STP-CS壓縮感知模型可以利用低階觀測矩陣實現對原始信號的壓縮采樣，且在保證重構質量的前提下，極大地提升重構的實時性，也成倍地降低了隨機觀測矩陣所需的存儲空間。

表5 與其他低存儲壓縮感知方法比較的峰值信噪比（Lena 512像素×512像素）

壓縮感知方法峰值信噪比/dB 0.125 00.250 00.375 00.437 50.500 00.562 50.625 00.750 0 本文t=225.458 230.192 034.216 335.767 936.506 837.436 639.727 842.287 9 本文t=425.412 329.578 134.124 735.086 436.342 237.493 039.270 542.433 7 本文t=825.751 429.734 733.225 835.286 436.226 637.530 138.591 041.950 1 本文t=1625.369 530.683 733.117 535.002 936.594 237.237 438.991 942.083 8 本文t=3224.926 429.219 533.015 734.907 136.035 937.795 838.317 141.254 6 文獻[6]BCS24.331 429.633 332.984 734.657 536.334 937.436 738.628 141.490 3 文獻[10]KroneckerCS25.060 928.349 729.528 131.121 533.785 334.981 035.296 137.237 2

表6 與其他低存儲壓縮感知方法比較的重構時間（Lena 512像素×512像素）

壓縮感知方法重構時間/s 0.125 00.250 00.375 00.437 50.500 00.562 50.625 00.750 0 本文t=273.29145.95241.79283.20299.61327.55357.10421.12 本文t=427.3345.2270.3386.1886.9399.4197.01102.31 本文t=815.5224.4031.6537.2441.0941.31344.2044.87 本文t=1617.7219.0025.1827.1522.7825.74825.6726.58 本文t=3224.7726.5628.3428.9526.5026.63326.4826.15 文獻[6]BCS24.149 326.918 835.4355.6071.3194.93122.27196.38 文獻[10]KroneckerCS230.79542.66989.491 212.81 649.61879.12 132.22 448.3

4 結束語

針對壓縮感知在大尺寸圖像應用中存在的隨機觀測矩陣占用較大的存儲空間、重構實時性差等問題，提出了一種利用低階觀測矩陣對原始信號進行全局壓縮采樣和分組重構的方法。利用該方法，既可以大大降低觀測矩陣所需的存儲空間，又使其重構的實時性得到有效的提升。

但基于半張量積理論的壓縮感知方法還有一些問題亟需進一步的深入研究：1) 需要在理論上進一步分析低階觀測矩陣與傳統觀測矩陣對原始信號進行壓縮采樣后，與原始信號之間的差別；2) 需要進一步提升采用低階觀測矩陣后的重構質量，目前的方法從本質上來說并沒有提升信號的重構質量，為此，亟需能找到一種適合低階觀測矩陣壓縮采樣的重構方法，使其既能提升重構質量，又能降低觀測矩陣的存儲空間并進一步提升重構的實時性。

利用本文所述方法，結合實際應用環境與條件，選擇合適大小的觀測矩陣，對于壓縮感知的硬件實現有非常積極的意義。

附錄1 半張量積理論

半張量積乘法（STP, semi-tensor product）是一種新型矩陣乘法。它是介于傳統矩陣乘法與張量積乘法之間的一種新運算，即當2個矩陣和滿足的列數和的行數呈倍數關系時，兩者之間即可進行左半張量積乘法[20]。

展開式(26)，有

由此便實現了矩陣和的左半張量積運算。

性質2 2個矩陣的左半張量積的維數可以很容易地根據消去前一個矩陣的列數和后一個矩陣的行數的公因子來計算得到，如

[1] DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[2] CANDèS E J, ROMBERG J, TAO T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.

[3] CANDèS E J, ROMBERG J K, TAO T. Stable signal recovery from incomplete and inaccurate measurements[J]. Communications on Pure and Applied Mathematics, 2006, 59(8): 1207-1223.

[4] DAUBECHIES I, DEVORE R, FORNASIER M, et al. Iteratively reweighted least squares minimization for sparse recovery[J]. Communications on Pure and Applied Mathematics, 2010, 63(1): 1-38.

[5] 程曉良, 鄭璇, 韓渭敏. 求解欠定線性方程組稀疏解的算法[J]. 高校應用數學學報, 2013, 28(2): 235-248.

CHENG X L, ZHENG X, HAN W M. Algorithms on the sparse solution of under-determined linear systems[J]. Applied Mathematics A Journal of Chinese Universities, 2013, 28(2): 235-248.

[6] ABOLGHASEMI V, FERDOWSI S, SANEI S. A block-wise random sampling approach: compressed sensing problem[J]. Journal of AI and Data Mining, 2015, 3(1): 93-100.

[7] WANG J, ZHANG J, WANG W, et al. A perturbation analysis of nonconvex block-sparse compressed sensing[J]. Communications in Nonlinear Science & Numerical Simulation, 2015, 29(1-3): 416-426.

[8] 付寧, 喬立巖, 曹離然. 面向壓縮感知的塊稀疏度自適應迭代算法[J]. 電子學報, 2011, 39(3A): 75-79.

FU N, QIAO L Y, CAO L R. Block sparsity adaptive iteration algorithm for compressed sensing[J]. Acta Electronica Sinica, 2011, 39(3A): 75-79.

[9] DUARTE M F, BARANIUK R G. Kronecker compressive sensing[J]. IEEE Transactions on Image Processing, 2012, 21(2): 494-504.

[10] ZHANG B J, TONG X, WANG W, et al. The research of Kronecker product-based measurement matrix of compressive sensing[J]. EURASIP Journal on Wireless Communications and Networking, 2013, 2013(1): 1-5.

[11] 胡曉偉, 童寧寧, 何興宇, 等. 基于Kronecker壓縮感知的寬帶MIMO雷達高分辨三維成像[J]. 電子與信息學報, 2016, 38(6): 1475-1481.

HU X W, TONG N N, HE X Y, et al. High-resolution 3D image via wideband MIMO radar based on kronecker compressive sensing[J]. Journal of Electronics & Information Technology, 2016, 38(6): 1475-1481.

[12] DO T T, GAN L, NGUYEN N H, et al. Fast and efficient compressive sensing using structurally random matrices[J]. IEEE Transactions on Signal Processing, 2012, 60(1): 139-154.

[13] HAIMI-COHEN R, MARK L Y. Compressive measurements generated by structurally random matrices[J]. Signal Processing, 2016, 120(C): 71-87.

[14] OTAZO R, CANDèS E, SODICKSON D K. Low-rank plus sparse matrix decomposition for accelerated dynamic MRI with separation of background and dynamic components[J]. Magnetic Resonance in Medicine, 2015, 73(3): 1125-1136.

[15] CAI T T, ZHANG A R. Sparse representation of a polytope and recovery of sparse signals and low-rank matrices[J]. IEEE Transactions on Information Theory, 2014, 60(1): 122-132.

[16] 朱志臻, 周崇彬, 劉發林, 等. 用于壓縮感知的二值化測量矩陣[J]. 微波學報, 2014, 30(2): 79-83, 96.

ZHU Z Z, ZHOU C B, LIU F L, et al. Binarized measurement matrix for compressive sensing[J]. Journal of Microwaves, 2014, 30(2): 79-83.

[17] 王俠, 王開, 王青云, 等. 壓縮感知中的確定性隨機觀測矩陣構造[J]. 信號處理, 2014, 30(4): 436-442.

WANG X, WANG K, WANG Q Y, et al. Deterministic random measurement matrices construction for compressed sensing[J]. Journal of Signal Processing, 2014, 30(4): 463-442.

[18] TROPP J A, GILBERT A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666.

[19] 董博, 姚治海, 李喆, 等. 壓縮感知OMP算法與IRLS算法在計算鬼成像中的對比分析[J]. 長春理工大學學報(自然科學版), 2016, 2016(1): 21-27.

DONG B, YAO Z H, LI Z, et al. Contrast analysis of compressive sensing OMP and IRLS algorithm in the computational ghost imaging[J]. Journal of Changchun University of Science and Technology (Natural Science Edition), 2016, 2016(1): 21-27.

[20] CHEN D Z, QI H S, LI Z Q. Analysis and control of boolean networks: a semi-tensor product approach[M]. Springer, 2011.

Fast reconstruction method for compressed sensing model with semi-tensor product

WANG Jinming, YE Shiping, YU Lizhe, XU Sen, JIANG Yanjun

Collage of Information Science & Technology, Zhejiang Shuren University, Hangzhou 310015, China

compressed sensing, measurement matrix, semi-tensor product, storage space, reconstruction time

TN911.73

A

10.11959/j.issn.1000?436x.2018111

2017?07?21；

2018?06?01

尉理哲，great_baby@outlook.com

浙江省自然科學基金資助項目（No.LY14E070001）；浙江省公益技術應用研究計劃基金資助項目（No.LGJ18F020001, No.LGG18F010007）

The Natural Science Foundation of Zhejiang Province (No.LY14E070001), The Science and Technology Project of Zhejiang Province (No.LGJ18F020001, No.LGG18F010007)

王金銘（1978?），男，浙江富陽人，浙江樹人大學副教授，主要研究方向為非線性信息處理、圖像處理、壓縮感知等。

葉時平（1967?），男，浙江麗水人，浙江樹人大學教授，主要研究方向為圖像處理、智能系統、地理信息系統等。

尉理哲（1983?），女，內蒙古呼倫貝爾人，浙江樹人大學講師，主要研究方向為車聯網、WSN、深度學習等。

許森（1982?），男，湖北荊門人，浙江樹人大學講師，主要研究方向為人工智能、智能控制、物聯網等。

蔣燕君（1973?），男，浙江諸暨人，博士，浙江樹人大學教授，主要研究方向為智能電網、圖像處理等。