[發明專利]基于進化正交匹配追蹤的壓縮感知信號恢復方法

有效

• 申請號: 201410571392.7
• 申請日: 2014-10-23
• 公開（公告）號: CN104392412A
• 公開（公告）日: 2015-03-04
• 發明（設計）人: 焦李成;張思博;李玲玲;楊淑媛;郝紅俠;尚榮華;馬文萍;馬晶晶
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06T5/00
• 分類號: G06T5/00
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱衛星

技術領域

本發明屬于信號處理技術領域，特別涉及一種壓縮感知信號恢復方法。可用于一維信號和二維圖像信號在低采樣率隨機觀測下的恢復問題。

背景技術

壓縮感知是一種高效的信號獲取手段，它僅通過少量的觀測即可恢復出原始信號。壓縮感知的基本假設是：信號可以被某組基原子稀疏地線性表示，即大多數原子系數為零，只有極少數原子系數為非零。在這種假設下，通過滿足一定條件的觀測，即可準確地恢復出信號。由于壓縮感知是非凸欠定問題，很難給出一個閉合解形式。解決這類問題最常用的技術是貪婪追蹤，經典的算法有匹配追蹤、正交匹配追蹤、子空間追蹤、分段正交匹配追蹤和正則化正交匹配追蹤。

正交匹配追蹤算法的基本思想是：首先初始化觀測誤差為觀測向量，在每次迭代中，計算觀測誤差與壓縮感知矩陣中每個原子的內積；然后，選擇對應內積絕對值最大的原子到支撐集當中去，并用最小二乘法計算支撐集中原子的系數；最后，更新觀測誤差，進入下一次迭代。通過這個迭代過程，使觀測誤差逐步減少，實現對原始信號的逼近。

子空間追蹤算法由正交匹配追蹤算法改進而來，它引入了回溯技術來淘汰掉不可信的原子，其基本思想為：假設原子非零系數的個數為K，首先，初始化觀測誤差為觀測向量，并計算觀測誤差與壓縮感知矩陣中每個原子的內積，將內積絕對值最大的K個原子添加到支撐集中去，然后利用最小二乘法求這K個原子的系數，并更新觀測誤差；在每次迭代中，再次計算觀測誤差與壓縮感知矩陣中每個原子的內積，并且將內積絕對值最大的K個原子添加到支撐集中去，這樣得到了2K個原子的支撐集；然后，利用最小二乘法求解這2K個原子的系數；之后，將支撐集中2K個原子系數絕對值最大的K個保留，將剩下的原子刪除，這樣得到了一個K個原子的支撐集；再利用最小二乘法求解這K個原子的系數；最后，更新觀測誤差，進入下一次迭代。

雖然許多基于正交匹配追蹤的改進算法對于信號的恢復概率和誤差獲得了很大的提升，但是由于匹配追蹤算法自身過于貪婪和搜索范圍有限等局限性，經常會使搜索陷入局部最優。

發明內容

本發明的目的在于改善傳統追蹤算法過于貪婪，回溯能力差的問題，來提高信號的恢復概率和恢復精度。是一種基于進化正交匹配追蹤的壓縮感知信號恢復方法，用于對一維信號和二維圖像信號在低采樣率隨機觀測下的恢復問題。本發明在進化計算的框架下來求解壓縮感知信號恢復問題，根據貪婪算法中觀測誤差與原子的相關性大小引入了基因活性的概念，利用基因活性作為整個種群的啟發式知識，來操作不同個體之間的交叉和變異，從而使得整個種群能夠不斷地迭代尋優。

本發明的技術方案是：首先初始化父代種群，計算其中所有個體的適應度和基因活性，并記錄下最優個體。然后對父代種群中的個體隨機兩兩配對，根據基因活性對每一對個體實施交叉操作，將得到的新個體存入子代種群，并計算它們的適應度和基因活性。之后，根據整體基因活性對子代種群中的每一個個體進行變異，每變異一個個體都要及時更新其適應度、基因活性和整體基因活性。最后，根據適應度好壞，在父代和子代中選擇出新的父代種群到下一次迭代中，直到迭代停止。其具體步驟包括如下：

(1)輸入壓縮感知矩陣D_cs和觀測向量y，初始化一個含有S個個體的父代種群P_f＝{p_i}_1≤i≤S，置計數器t＝0；

(2)計算父代種群的適應度和基因活性，并且記錄適應度最大的個體為最優個體p_best；

(3)對父代種群進行交叉操作，得到子代種群

(4)計算子代種群的適應度和基因活性；

(5)對子代種群進行變異操作，變異過程中更新每個個體的適應度、基因活性和整體基因活性；

(6)從父代種群和子代種群中選擇出新的父代種群并且更新最優個體p_best，置計數器t＝t+1；

(7)設最大迭代次數為T_max，若t<T_max，返回步驟(3)；否則，輸出最優結果。

本發明結合了進化計算和貪婪追蹤技術，將壓縮感知中稀疏系數的求解轉化為弱貪婪的啟發式種群搜索過程，并且引入貪婪算法中觀測誤差與原子的相關性作為種群搜索的啟發式知識，它具有如下優點：

(A)、基于群體的啟發式搜索改善了傳統貪婪追蹤算法陷入局部最優的問題；

(B)、對于一維信號的恢復概率和恢復精度有明顯的提高；

(C)、對于二維圖像的恢復，具有更小的恢復誤差和更少的塊效應。