稀疏圖像重構非凸Lp問題的分裂方法

朱永貴，劉 平，叢 佳

(中國傳媒大學理學院，北京100024)

Candes等［1］和Donoho［2］于2006年提出了壓縮感知(Compressed Sensing)理論。根據壓縮感知理論，如果稀疏信號或圖像的測量數據滿足不相關性［3］，那么稀疏信號或圖像可以從非常有限的抽樣數據中重構出來，而這些測量數據被稱作原始稀疏信號或圖像的壓縮。對于二維圖像可以按一列一列地排列形成一個向量信號。用u表示由圖像形成的長度為N的向量信號。如果A表示一個M×N(M≤N)的觀測矩陣，那么在壓縮感知中b=Au是信號u的觀測數據即壓縮。原始信號u的重構可以通過求解最優化問題(1)實現。式中:代表‖u‖0中不等于零的分量個數。求解問題(1)是一個NP難問題［4］，因此該問題的求解依賴于計算機進行數值計算難以實現。Trzasko等［5］于2009年提出了L0擬范數的同倫逼近壓縮感知重構方法，這一方法能夠從抽樣率非常低的頻域數據中精確重構出MR原始圖像。由于該方法涉及連續性求解過程，其計算時間很長，并且該方法目前僅能用于特殊類型的MR圖像重構上，而不能用于其它類型如自然圖像、視頻圖像上，因此該方法不具有普遍性。盡管L0問題是NP難問題，但Candes等［6］證明了在一定條件下，問題(1)可以轉化為如下L1范數最小化問題

L1最小化問題是一個凸最優化問題，利用最優化方法可以求解。目前求解最優化問題(2)的主要流行方法有內點法［7］、不動點連續性方法FPC［8－9］、Bregman迭代方法［10］、分裂 Bregman迭代法［11］、偏微分方程方法［12］和共軛梯度下降法［13］。最近我們也提出了求解問題(2)的凸分裂算法［14］。

當0＜p＜1時，用于壓縮感知求解的最優化問題變為如下非凸最優化問題

同L0最小化問題一樣，問題(3)是非凸最優化問題，但從計算角度看Lp(0＜p＜1)問題比L0問題容易處理。與問題(2)相比，問題(3)無論從理論分析還是數值計算，都非常困難。目前求解Lp(0＜p＜1)非凸問題已經成為壓縮感知研究領域的一個熱點，引起了眾多科學家的重視。2007年Jung等［15］和Ye等［16］使用FOCUSS方法求解了最優化問題(3)，取得了比較好的壓縮感知重構結果。同年美國洛斯阿拉莫斯國家實驗室的Chartrand教授［17］建立了求解Lp(0＜p＜1)問題的Fourier基最小化方法，這一方法已成為壓縮感知研究的主要方法。這一重要成果促進了許多專家研究壓縮感知中求解Lp問題新的最優化方法。例如Sidky等［18］使用Lp(0＜p＜1)方法利用非常少的 Views頻域抽樣精確重構出原始圖像。Chartrand等［19］給出了壓縮感知的重加權迭代法。Chartrand［20］于2009年將其非凸最優化的Fourier基算法推廣到核磁共振成像(Magnetic Resonance Imaging，MRI)領域中，得到了MR圖像重建非凸壓縮感知的快速算法。

本文是利用半二次罰函數法的算子分裂思想給出了求解壓縮感知Lp(0＜p＜1)非凸最優化問題的分裂算法。其基本思想是將原問題分裂成兩個子問題:X子問題和Y子問題。然后對形成的X子問題通過光滑函數求導的方法給出X問題的閉形式解，對于Y子問題通過不動點方法迭代求解。最后通過這兩個子問題的交替求解形成原問題的交替求解數值方法。我們從理論上分析和證明了Lp(0＜p＜1)非凸問題的分裂算法的收斂性。通過對X子問題和Y子問題的交替求解，能夠在誤差容許的范圍內求得圖像壓縮感知Lp問題的精確重構解。由于該方法的快速性使它不僅能夠進行一維稀疏信號和二維稀疏圖像的精確重構，而且還可應用于核磁共振(MR)圖像的快速精確重構。

1 非凸Lp最優化問題的求解方法

在不考慮噪聲的情況下非凸Lp最優化問題即為最優化問題(3)。根據最優化理論和凸分析知識，可以將問題(3)化為如下無約束形式

式中:‖·‖是指Euclid范數，x∈RN。

在含有噪聲污染的情況下，非凸Lp最優化問題為如下形式

式中:n為高斯白噪聲。問題(5)的無約束形式如下

在MR圖像壓縮感知中，A=PFΦ－1，P∈RM×N，F是離散Fourier變換矩陣，Φ表示正交基如小波變換基、余弦變換或稀疏字典等。在數值模擬實驗部分，將利用核磁共振圖像進行壓縮感知重構實驗，并采用正交小波基作為稀疏基。

我們已在文獻［14］中利用半二次罰函數法，給出了壓縮感知凸最優化問題的分裂算法。本文仍采用半二次罰函數法的思想將問題(6)變為

當β→∞時，模型(7)等價于模型(6)，所以對于足夠大的β可以用式(7)的解去逼近式(6)的解。

還可以從設計階段來合理控制建筑結構設計對造價成本的影響。設計階段需要充分關注建筑物的空間高度、使用功能以及內部平面設計等方面，通過對這些方面的科學合理設計可以促進結構設計工作的有效開展。例如，在高層建筑中，隨著建筑層數的增多，水平荷載也成為建筑結構設計的控制因素。

下面給出x－子問題和y－子問題的求解方法。對于x－子問題，由于目標函數是光滑函數，所以通過求導的方法可以得到其最優解

而y－子問題是一個非凸問題，可以利用不動點方法求解，現在介紹具體的求解過程。

根據Lp范數的定義可以將y－子問題化為如下形式

因為y的各分量y1，y2，…，yN與x的各分量x1，x2…，xN是相互獨立的，因此子問題(9)又可以變為分量形式

從而可以求解yj的不動點迭代公式

下面證明和分析迭代算子是收縮的。

定理1 對于0＜p＜1，實數域R中的任何兩個點y(n+1)和y(n)，對于足夠大的β有

證明 不適一般性，不妨設y(n+1)和y(n)都大于0，則有

由于0＜p＜1，β足夠大，所以

證畢。

2 數值模擬

在數值模擬實驗中，采用信噪比(SNR)和相對誤差(Relative Error)評價壓縮感知圖像重構的質量。信噪比和相對誤差的定義分別如下

式中:x和x0各自代表計算重構的圖像和原始圖像。

在下面的數值模擬實驗中，所采用的噪聲是均值為0，方差為0.01的Gauss白噪聲，稀疏基采用正交Harr小波。并且用非凸分裂算法進行數值模擬實驗過程中，假設圖像的初始值x(0)=0，令μ=1000，p=1/3，取迭代終止準則為:

圖1(a)、(b)分別給出220×220的心臟MR原始圖像和對其進行77 Views頻域抽樣圖。對圖1采用非凸分裂算法進行重構實驗，其結果如圖2所示。

圖1 原始圖像和頻域空間中的77 ViewsFig.1 Original images and 77 Views in frequency space

圖2 非凸分裂算法重構的圖像Fig.2 Reconstructions by non-convex splittingmethod

計算得到非凸分裂算法重構的大腦MR圖像的信噪比和相對誤差分別為 17.802 1 dB和0.134 2。

現在對大腦MR圖像進行121Views頻域抽樣(見圖3(a))，并采用凸分裂算法進行重構實驗，重構結果如圖3(b)所示。凸分裂算法重構的大腦MR圖像的信噪比和相對誤差分別為15.361 2 dB和0.187 1。從重構圖像的結果可以看出非凸分裂算法重構的圖像質量明顯好于凸分裂算法重構的圖像，但非凸分裂算法的抽樣率僅是凸分裂算法的67.77%。

圖3 頻域空間中的121Views和凸分裂算法重構的圖像Fig.3 121Views and Rec.by convex splitting method

下面給出的身體MR圖像(見圖4(a))，對其進行抽樣率為23.56%的笛卡爾線形抽樣(見圖4(b))。

圖4 原始圖像和頻域空間中的笛卡爾線型抽樣Fig.4 O riginal images and Cartesian frequency sam p ling

現采用非凸分裂方法進行重構實驗，重構結果如圖5所示。其信噪比為15.532 9 dB，相對誤差為0.124 1。

圖5 非凸分裂算法重構的圖像Fig.5 Reconstructions by non-convex splittingmethod

對身體MR圖像進行抽樣率為40.87%的笛卡爾線形頻率抽樣(見圖6(a))，并采用凸分裂算法進行重構實驗，重構結果如圖6(b)。重構圖像的信噪比為13.421 3 dB，相對誤差為0.213 5。

圖6 40.87%的笛卡爾抽樣和凸分裂算法重構的圖像Fig.6 40.87%sam pling and Rec.by convex method

從重構圖像的結果可以看出非凸分裂算法重構的圖像質量明顯好于凸分裂算法重構的圖像，而且抽樣率僅是凸分裂算法的57.65%。

3 結束語

本文給出了求解壓縮感知中稀疏圖像重構Lp問題的非凸分裂方法。通過數值模擬實驗對非凸分裂方法與凸分裂方法進行了比較，實驗結果表明:

(1)非凸分裂方法重構的圖像比凸分裂方法重構的圖像具有更高的精度和更低的頻域抽樣率。

(2)通過主觀觀察，在圖像壓縮感知中非凸分裂方法較凸分裂方法具有更好的圖像重構質量。

本文給出的壓縮感知中稀疏圖像重構的非凸分裂方法可以降低稀疏重構的抽樣率，能夠用于核磁共振快速成像，在醫學成像領域中具有一定的應用價值。

［1］Candes E J，Romberg J，Tao T.Robust uncertainty principles:Exact signal reconstruction from highly incompletee frequency information［J］.IEEE Trans Inform Theory，2006，52(2):489－509.

［2］Donoho D L.Compressed sensing［J］.IEEE Trans Inform Theory，2006，52(4):1289－1306.

［3］Candes E J，Romberg J.Sparsity and incoherence in compressive sampling［J］.Inverse Problems，2007，23 (3):969－985.

［4］Natarajan B K.Sparse approximation solutions to linear systems［J］.SIAM JComput，1995，24(2):227－234.

［5］Trzasko J，Manduca A，Borisch E.Highly undersampled magnetic resonance image reconstruction via homotopic L0－minimization［J］IEEE Transactions on Medical Imaging，2009，28(1):106－121.

［6］Candes 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.

［7］Kim S J，Koh K，Lustig M.An interior－pointmethod for large－scale l1－regularized least squares［J］.IEEE Trans.on Selected Topics in Signal Processing，2007，1 (4):606－617.

［8］Hale E，Yin W，Zhang Y.Fixed－point continuation for l1 minimization:Methodology and convergence［J］.SIAM Journal on Optimization，2008，19(3):1107－1130.

［9］Hale E，Yin W，Zhang Y.Fixed－point continuation applied to compressed sensing:Implementation and numerical experiments［J］.Journal of Computational Mathematics，2010，28(2):170－194.

［10］Yin W，Osher S，Goldfarb D.Bregman iterative algori thm for l1－minimization with applications to compressed sensing［J］.SIAM J.Image Sciences，2008，1(1):143－168.

［11］Goldstein T，Osher S.The split bregman method for L1－regularized problems［J］.SIAM J.Image Sciences，2009，2(2):323－343.

［12］He L，Chang TC，Osher S，et al.MR image reconstruction by using the iterative refinementmethod and nonlinear inverse scale space methods［R］.UCLA CAM Report，2006:6－35.

［13］Lustig M，Donoho D，Pauly J.Sparse MRI:The application of compressed sensing for rapid MR imaging［J］. Magnetic Resonance in Medicine，2007，58(6):1182－1195.

［14］朱永貴，楊曉蘭.稀疏MR圖像重構的快速算法［J］.中國圖象圖形學報，2011，16(9):1736－1744.

Zhu Yong－gui，Yang Xiao－lan.Fast reconstructionmethod for sparse MR image［J］.Journal of Image and Graphics，2011，16(9):1736－1744.

［15］Jung H，Ye J，Kim E.Improved k－t blask and k－t sense using focuss［J］.Phys Med Biol，2007，52(11):3201－3226.

［16］Ye J C，Tak S，Han Y et al.Projection reconstruction MR imaging using FOCUSS［J］.Magnetic Resonance in Medicine，2007，57(4):764－775.

［17］Chartrand R.Exact reconstruction of sparse signals via nonconvexminimization［J］.IEEE signal Letters，2007，14(10):707－710.

［18］Sidky E Y，Chartrand R，Pan X.Image reconstruction from few views by non－convex optimization［R］. IEEE transaction Medical Imaging Conference Record，2007.

［19］Chartrand R，Yin W.Iteratively reweighted algorithms for compressive sensing［C］//33rd International Conference on Acoustics Speech，and Signal Processing，2008.

［20］Chartrand R.Fast algorithms nonconvex compressive sensing:MRI reconstruction from very few data［R］. IEEE International Symposium on Biomedical Imaging，2009.