基于遺傳模擬退火算法的壓縮感知重構(gòu)方法

肖暢，樊曉宇

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

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

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

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

1 CS模型

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

若長(zhǎng)度為N的離散實(shí)值原信號(hào)f∈RN，在某正交基Ψ=［ψ1，ψ2，…，ψN］上是K稀疏的（1≤K<

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

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

為了測(cè)試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)圖像的相對(duì)誤差Em，其中，基于CD的CS重構(gòu)方法用于自然圖像重構(gòu)時(shí)，對(duì)文獻(xiàn)［1］的圖像重構(gòu)模型進(jìn)行了相應(yīng)變化。

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

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

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

4 結(jié)論

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