基于遺傳模擬退火算法的壓縮感知重構方法

肖暢，樊曉宇

（1.合肥工業大學 計算機與信息學院，合肥 230601；2.安徽科技學院 電氣與電子工程學院，蚌埠 233030）

壓縮感知（Compressed Sampling，CS）是一種數據壓縮與重構理論，CS對具有稀疏性或在變換域上稀疏的信號在滿足特定條件下，可通過遠低于奈奎斯特采樣定理的隨機采樣完成原信號的精確重構。這種新穎的壓縮與采樣同時進行的信號處理方式，能夠有效降低信號采樣、傳輸和存儲的代價，使信號的處理方式得到一次深刻的變革［1-4］。

CS主要包括三個問題，即信號在某個域上的稀疏變換、觀測矩陣的構造和信號重構算法的設計，本文設計的方法是針對信號重構環節進行的。CS的有效信號重構算法諸多，主要包括：直接求解l0范數最小化問題的匹配追蹤算法［5］和把l0范數最小化轉化為l1范數最小化，通過線性規劃求解的基追蹤算法［6］。目前出現了一些改進算法，如正交匹配追蹤法、梯度追蹤法等［7-10］。然而，上述的有些算法需要已知信號的稀疏度，這給應用帶來很大不便。劉亞新［11］、高睿［12］、張宗念等人［13］分別提出了信號稀疏度未知條件下的信號重構算法，但是這些算法主要歸結于匹配追蹤，其缺點是算法需要進行有效的子空間擴充與跟蹤，將導致算法需要大量的循環次數才能保證重構信號逼近原信號。朱豐等人［14］研究了運用遺傳迭代思想，在稀疏度未知情況下，可準確重構出原信號，避免了子空間跟蹤，但遺傳算法（Genetic Algorithm，GA）的局部搜索能力較差，這導致了基于單純遺傳算法的壓縮感知重構方法具有一定的缺陷。

本文提出一種基于遺傳模擬退火算法（Genetic and Simulated Annealing Algorithm，GASA）的CS信號重構方法，它是采用遺傳算法和模擬退火算法思想，將CS的信號重構問題等效為生物學中染色體復制、選擇與交叉的遺傳處理以及模擬退火過程的退火最優化處理，通過不斷迭代來逼近最優的信號重構結果，獲得稀疏性信號重構結果中各非零元素的位置信息，再使用最小二乘法來計算各非零元素的幅度信息，從而完成信號重構的整個過程。本文將提出的CS信號重構方法應用于基于CS理論的一維信號與二維圖像信號重構處理，以考察本文方法的有效性。

1 CS模型

壓縮感知的前提是：要求信號滿足在某種變換基下是稀疏的或可壓縮的，即信號稀疏變換后非零或較大系數的個數遠遠小于信號本身的非零個數。此時，利用較少的有限系數就可以精確地表示原信號的絕大部分信息。再利用測量矩陣與信號進行乘積，可以獲得原始信號在該測量矩陣作用下的投影信息。然后，利用該投影信息結合CS的信號重構算法就可以精確地重構出原始信號。

若長度為N的離散實值原信號f∈RN，在某正交基Ψ=［ψ1，ψ2，…，ψN］上是K稀疏的（1≤K<

式中，x是N×1維的投影系數列向量，且僅有K（K<

若信號f滿足稀疏性，可采用與Ψ不相關的M×N測量矩陣Φ（M<

式中，y是M×1的觀測向量，其元素個數小于等于f元素個數，實現了對信號f的壓縮采樣。

將式（1）代入式（2），得：

式中，Θ =ΦΨT為CS的信息算子，其列向量稱為原子。因測量維數M遠小于信號維數N，所以無法直接從y的M個觀測值中解出信號f。由于式（3）中x是稀疏的，可通過求解式（3）的逆問題解得x，然后將x代入式（1），求得原信號f。

CS重構問題是在已知測量矩陣Φ及觀測向量y的情況下重構出原信號f。用觀測值y重構原信號f可通過求解l0范數下的最優化問題來完成，即：

若原始信號f能夠以高概率精確重構，則Θ需要具備有限等距性質［15-17］。

2 基于GASA的CS信號重構方法

GASA是將GA與模擬退火算法（Simulated An‐nealing Algorithm，SA）相融合而構成的一種優化算法。與GA操作過程相似，GASA從隨機產生的初始群體進行全局最優解的搜尋，首先通過染色體復制、選擇、交叉和變異的遺傳操作獲得一組新個體，隨后再對新個體進行模擬退火操作，將操作結果視為下一代群體的個體。該操作過程進行反復迭代，直到達到終止條件。GASA將GA和SA的優點充分結合，大大提高了算法的效率。

由CS理論可知，由觀測值y通過重構算法可求解出稀疏性信號?，再利用稀疏反變換即可獲得原始信號?。基于GASA的CS信號重構方法是以優化模型的目標函數為起點，將信號的重構過程等效為染色體的復制、選擇、交叉和變異等遺傳操作，再將遺傳操作獲得的新個體進行模擬退火最優化操作，通過迭代近似獲得信號最優的重構結果，從而得到稀疏結果非零元素的位置信息。然后，使用最小二乘法求解出非零元素的幅度信息［14］，整個GASA的CS信號重構過程類似于傳統處理方法的反過程。

2.1 確定稀疏表示的各非零元素位置信息

GASA的CS重構方法是由GA與SA確定CS重構中稀疏表示結果的非零元素位置信息，本文構造的GASA重構方法求解過程的步驟為：

（1）設定群體與編碼方案。CS重構問題的最優解用數字串表示，每個數字串為一個染色體。結合CS理論，將所求稀疏信號等效為染色體進行群體設定，產生的群體集合表示為。群體初始溫度設為 T0。

（2）目標函數定義為：

式中，λ∈（0，1）。最終目標是使目標函數g取得最小值，即求得min{g}。本文使用的適應度函數Fi定義為：

式中，gmax是目標函數g的最大值。每個染色體的適應度值由適應度函數確定，適應度值Fi越大，染色體集合越接近式（4）的最優解，優化目標是尋找參數集合使目標函數g最小。

（3）算法終止條件。通過每代群體最小目標函數gmin的變化來判斷算法是否停止。滿足設定誤差δ，算法收斂，輸出最優結果；否則，進行步驟（4）。

（4）復制。設定父代與子代的代溝值GAP，GAP∈（0，1），群體的個體數量L乘以（1-GAP）的值作為最優個體直接復制到下一代的數量，而其他個體由選擇操作產生。該過程保留了群體的最優解，算法能夠以高概率收斂于全局最優解，使算法具有收斂性。

（5）選擇。由適應度函數值進行個體選擇，選擇方法采用輪盤賭法，最終目標是使目標函數g取得最小值。個體i被選中到下一代的概率為：

（6）交叉和變異。設置的交叉概率Pc與變異概率Pm可以動態調節，以克服“早熟”現象，同時達到算法加快搜索速度的效果。Pc與Pm隨適應度值自動改變的表達式為：

式中，k1、k2為常系數；gavg為當前群體目標函數的平均值。通常，個體的適應度值小，則具有較大的Pc和Pm，能夠加快算法搜尋速度。若GA取得局部極值，適應度值較大個體的Pc、Pm也將增大，能夠避免“早熟”現象。當｜gmin-gavg｜＜ε時，固定Pc、Pm值，以避免原解空間被破壞，ε為任意小的數，且ε>0。

交叉操作是以交叉概率Pc進行單點交叉，產生兩個新個體。變異操作是以變異概率Pm進行基本位變異，產生新一代個體。通過由選擇、交叉和變異操作獲得的個體，利用回溯思想，將它們與復制操作直接復制到下一代的個體進行合并，然后再進行步驟（7）。

（7）確定初溫及退溫操作。

退火函數定義為：

式中，n為GA的第n次迭代；α為溫度調節系數，取值范圍為（0，1）；溫度T由初始溫度緩慢降到0。

（8）接受退火操作產生的個體。將GA操作產生的群體作為退火操作的初始群體，利用Metropolis準則產生下一代群體。在個體i的鄰域中隨機產生新個體j，i和j競爭進入下一代群體的準則是：令 ΔF=Fj-Fi，若 ΔF>0，新個體 j優于原個體i，則接受新個體j；若ΔF≤0，原個體i優于新個體j，要先用式（11）計算概率P，然后進行判斷。

式中，Tn為第n迭代的溫度。然后再產生［0，1］間的隨機數r，若P>r，則新個體j被接受；否則，i被接受，j被拋棄。Metropolis準則保證了群體多樣性，避免陷入局部最優解。

綜上一系列操作，通過反復迭代就可收斂到最優染色體，即為最優解。方法獲得的最優染色體由0或1組成，其中1為信號稀疏表示的非零元素，其位置信息對應信號稀疏表示的非零元素位置。

2.2 確定稀疏表示的各非零元素幅度信息

利用最小二乘法在信號稀疏表示的非零元素位置進行投影來確定幅度信息［14］。若信號稀疏表示的第l位是非零元素，則該非零位置的幅度為：

式中，Θ為恢復矩陣；Θl為Θ =ΦΨ的第l列；<·>為內積運算。由該計算可得稀疏表示的各非零元素幅度信息。

2.3 GASA的CS重構方法

GASA的CS重構方法流程為：

（1）初始化：L個隨機產生的染色體作為初始群體Z（0），

（4）設定代溝值 GAP，GAP∈（0，1）；將 L（1-GAP）個最優個體復制到下一代，構成集合x?1；

（5）將（3）中的其他個體i按照式（7）以概率Pi選擇，選擇的個體i遺傳到下一代；

（6）設置系數 k1、k2值，并分別按式（8）和式（9）計 算 Pc和 Pm。 若 gavg→gmin，Pc、Pm增 大 ；若，固定 Pc、Pm，ε 為任意小，且 ε>0。然后分別以Pc、Pm對步驟（5）選擇操作獲得的個體進行交叉和變異，構成集合x?2；

（8）退火操作 Tn= αTn-1，α∈（0，1）；得到新群體Z（n+1）；

（9）計算 Z（n+1）的目標函數值，令 s=gmin；判斷s

（10）設置 q、δ值，n ≥ q時，若 s*在 δ范圍內，滿足終止條件，則以s*為最終解輸出，算法結束；否則，返回步驟（3）；

該算法的流程圖如圖1所示。

圖1 GASA的CS重構方法流程圖

3 實驗結果及分析

3.1 GASA的CS重構方法對一維稀疏信號重構

采用GASA的CS重構方法對長度為N=200的稀疏信號進行重構，觀測值數目M=100，L=20，G=0.15，k1=0.7，k2=0.05，q=50。最終各原子是以GASA重構方法最優解s*串的“1”所在位置從字典中選取的，然后進行各原子的線性組合重構出原信號。原信號與重構信號分別用f與?表示，相對誤差Em定義為：

若Em值越小，則表示重構方法的優化能力越好，信號重構的精確越高。

利用GASA重構方法對原信號重構的相對誤差隨著降維比的增大而迅速下降，如圖2（a）所示。由圖2（a）可知，當信號的降維比大于10%時，GASA重構方法的重構信號與原信號相對誤差很小，其值小于10-15數量級，該方法能夠對原信號進行精確重構。信號降維比為10%時，采用GASA的CS重構方法信號重構的實驗結果如圖2（b）所示，由圖2（b）可知重構信號與原信號誤差很小。實驗證實了GASA的CS重構方法對稀疏信號的重構精度高、效果好。

圖2 GASA的CS重構方法對稀疏信號的重構效果

3.2 GASA的CS重構方法對圖像的重構

實驗圖像為四幅512×512的自然圖像Pep‐pers和 Lena、核磁（Magnetic Resonance，MR）圖像Brain和foot［18］。每幅圖像在含高斯白噪聲情況下，利用GASA的CS重構方法進行MATLAB實驗，獲得每幅圖像的PSNR及圖像重構視覺效果。實驗中，L=30，G=0.1，k1=0.85，k2=0.05，q=40，ε=δ=0.01，算法的迭代次數m=100。每幅自然圖像都利用小波基db3為正交基矩陣，其投影的測量值為y；每幅MR圖像經傅里葉變換后在采樣率為10%的2D變密度隨機采樣［19］下的測量值為y。四幅圖像使用GASA的CS重構方法，圖像重構結果的PSNR值分別為31.26 dB、32.64 dB、33.12 dB和32.87 dB，圖像重構結果如圖3所示。圖3（a）-圖3（d）分別為原始的Peppers、Lena、Brain和foot圖像，圖3（e）-圖3（h）分別為GASA的CS重構方法圖像重構的結果。由圖3可見，GASA的CS重構方法能夠重構出自然圖像和MR圖像，在保持圖像的結構細節信息和邊緣輪廓方面具有一定的優越性。實驗表明，GASA的CS重構方法在GA中融入模擬退火和回溯過程后，獲得了較高的圖像重構PSNR值以及較好的圖像重構視覺效果。實驗證實了GASA的CS重構方法對自然圖像和MR圖像重構的有效性。

圖3 GASA重構方法的圖像重構效果

3.3 GASA的CS重構方法對圖像重構的精度

為了測試GASA的CS重構方法的圖像重構精度和方法的全局搜索性能，本文以512×512的Lena與Brain圖像為例，比較GA的CS重構方法、基于卡通-紋理分解（Cartoon-texture decomposi‐tion，CD）的CS重構方法［1］、GASA的CS重構方法重構圖像的相對誤差Em，其中，基于CD的CS重構方法用于自然圖像重構時，對文獻［1］的圖像重構模型進行了相應變化。

對Lena與Brain圖像采用GA、CD和GASA的CS重構方法進行的圖像重構實驗中，Lena圖像利用小波基db3為正交基矩陣，Brain圖像經傅里葉變換后利用采樣率為5%的偽射線采樣［19］，其不同迭代次數的相對誤差Em的實驗結果如圖4所示。

圖4 三種圖像重構方法的相對誤差曲線圖

由圖 4（a）、圖 4（b）可知，Lena和 Brain圖像采用GA、CD的CS重構方法獲得重構圖像的相對誤差較大，GASA的CS重構方法獲得重構圖像的相對誤差較小，即GASA的CS重構方法相比GA、CD的CS重構方法圖像重構的精度較高。圖4（a）、圖 4（b）中，Lena和Brain圖像利用GASA的CS重構方法相比GA的CS重構方法達到算法收斂時，迭代次數較少，即該方法的收斂速度較快。這是因為在圖像重構時，GASA的運算融合了SA，避免了GA的局部搜索能力差及“早熟”現象。從理論分析和實驗都證實了GASA的CS重構方法相對GA的CS重構方法圖像重構的精度較高，迭代次數較少。然而，GASA的CS重構方法相比CD的CS重構方法圖像重構達到收斂時，迭代次數較大。這是因為GASA方法中的GA與SA算法在圖像重構過程的收斂速度與CD的CS重構方法相比較慢。

4 結論

GASA的CS重構方法能夠增強搜索全局和局部最優解的能力，將其應用于一維信號和二維圖像的重構，實驗結果表明在合適的參數下，該方法能夠精確地重構出原信號，具有較好的圖像重構質量和效果。同時，該方法的收斂迭代次數較小，能夠提高整個方法的運算效率。GASA的CS重構方法融合了遺傳算法和模擬退火算法的優點，在信號的壓縮感知應用研究方面取得了較好的進展。