肖暢，樊曉宇

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

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

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

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

1 CS模型

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

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

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

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

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

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

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

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

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

2 基于GASA的CS信號重構(gòu)方法

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

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

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

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

（1）設(shè)定群體與編碼方案。CS重構(gòu)問題的最優(yōu)解用數(shù)字串表示，每個數(shù)字串為一個染色體。結(jié)合CS理論，將所求稀疏信號等效為染色體進行群體設(shè)定，產(chǎn)生的群體集合表示為。群體初始溫度設(shè)為 T0。

（2）目標函數(shù)定義為：

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

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

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

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

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

（6）交叉和變異。設(shè)置的交叉概率Pc與變異概率Pm可以動態(tài)調(diào)節(jié)，以克服“早熟”現(xiàn)象，同時達到算法加快搜索速度的效果。Pc與Pm隨適應(yīng)度值自動改變的表達式為：

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

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

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

退火函數(shù)定義為：

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

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

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

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

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

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

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

2.3 GASA的CS重構(gòu)方法

GASA的CS重構(gòu)方法流程為：

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

（4）設(shè)定代溝值 GAP，GAP∈（0，1）；將 L（1-GAP）個最優(yōu)個體復制到下一代，構(gòu)成集合x?1；

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

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

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

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

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

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

圖1 GASA的CS重構(gòu)方法流程圖

3 實驗結(jié)果及分析

3.1 GASA的CS重構(gòu)方法對一維稀疏信號重構(gòu)

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

若Em值越小，則表示重構(gòu)方法的優(yōu)化能力越好，信號重構(gòu)的精確越高。

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

圖2 GASA的CS重構(gòu)方法對稀疏信號的重構(gòu)效果

3.2 GASA的CS重構(gòu)方法對圖像的重構(gòu)

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

圖3 GASA重構(gòu)方法的圖像重構(gòu)效果

3.3 GASA的CS重構(gòu)方法對圖像重構(gòu)的精度

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

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

圖4 三種圖像重構(gòu)方法的相對誤差曲線圖

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

4 結(jié)論

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