基于改進ACFOA的圖像一維OMP稀疏分解

楊 明 陳玲玲* 尹忠科

基于改進ACFOA的圖像一維OMP稀疏分解

楊 明1陳玲玲1*尹忠科2

1(吉林化工學院信息與控制工程學院 吉林 吉林 132022)

2(西南交通大學信息科學與技術學院 四川 成都 610031)

針對二維圖像稀疏分解運算復雜度高的問題，提出一種基于改進自適應混沌果蠅優化算法的圖像一維正交匹配追蹤OMP(Orthogonal Matching Pursuit)稀疏分解方法。算法首先將圖像從二維空間轉換到一維空間，然后對自適應混沌果蠅優化算法ACFOA(Adaptive Chaos Fruit Fly Optimisation Algorithm)的味道濃度判定值和混沌映射函數進行了改進，提高了算法的全局尋優性能，最后將改進后的ACFOA算法應用到圖像一維OMP分解之中。實驗結果表明，在相同實驗條件下，圖像一維OMP稀疏分解的速度是二維分解的1.12倍。

圖像稀疏分解 正交匹配追蹤 自適應混沌果蠅優化算法 計算復雜度 全局最優

0 引 言

在信號處理領域，傳統的信號分解方法主要有余弦變換、傅里葉變換、哈特萊變換、小波變換、哈達瑪變換等，這些變換都是正交變換，其分解基都是正交的。而傳統的基于“基”的信號分解方法具有明顯的局限性，通常不能夠達到對信號的稀疏表示。為了達到對信號的簡約表達形式，出現了基于過完備原子庫的新的信號分解方法，這種方法稱之為稀疏分解[1]。由于稀疏分解可以靈活地選取分解基，自適應地稀疏表示信號，其在信號處理的多個方面有了廣泛的應用。比如信號去噪[2]、信號識別[3]、信號譜分析[4]、地震數據處理[5]等。由于稀疏分解的自身優勢，其在出現不久便被應用到二維圖像信號的研究分析上。Mallat等于1994年提出了圖像稀疏分解的匹配追蹤算法MP(Matching Pursuit)，而目前圖像稀疏分解已經有了多種方法，正交匹配追蹤算法OMP便是其中之一。OMP繼承了MP算法的原子搜索策略，首先在過完備原子庫中找到與待分解的原信號或信號殘差最為匹配的原子，然后通過對已選原子的正交化，提升了稀疏分解的收斂速度[6]。但由于在MP分解每一步最優原子搜索過程中都需要進行大量復雜的內積計算，運算復雜度高；而OMP的后續的原子正交化過程中又引入了內積計算，使得整個分解過程的復雜度進一步上升。所以，OMP算法收斂速度的增加是以提升計算復雜度為代價的。為了使得圖像稀疏分解能夠應用于實際生活，必須降低算法的復雜度。

人工智能算法是一種高效的全局尋優方法，它通用性強，適用于并行處理。目前，實際應用中主要有遺傳算法、粒子群算法、魚群算法、蟻群算法等。由于稀疏分解每步最優原子的搜索過程實際上都是一個全局尋優問題，所以完全可以將智能算法應用到稀疏分解當中，提升最優原子的搜索效率[7-10]。果蠅優化算法FOA(Fruit Fly Optimization Algorithm)是一種新生的智能仿生算法，其通過模擬果蠅的覓食行為來進行全局尋優[11]。雖然果蠅優化算法出現較晚，但憑借其自身的優勢，已經廣泛應用于多個領域。但同其他智能算法一樣，FOA也會陷入局部最優，出現早熟收斂現象，嚴重影響尋優的準確度和精確度。針對這一問題，出現了多種改進方案。其中，韓俊英等提出了自適應混沌果蠅優化算法ACFOA。算法主要根據對FOA的收斂情況進行判斷，當其處于局部最優時自適應地采用混沌方法進行優化，跳出局部最優，保持種群的多樣性，提升尋優效果[12]。

文獻[13]提出了一種新的圖像稀疏分解快速算法——圖像1DFFT—MP法。將二維圖像信號和二維分解原子均轉為一維信號，并將一維原子信號進行集合劃分，然后利用一維信號的FFT—MP法進行稀疏分解和重建，提升算法的運算速度和重建質量。本文通過對OMP和ACFOA的研究，結合文獻[13]的思想，將ACFOA應用到圖像OMP稀疏分解當中，并針對ACFOA的味道濃度判定值進行了改進。同時用概率密度更均勻、遍歷性更好的Cat映射取代Logistic映射，以達到對信號的更快更好的稀疏分解結果。

1 基于OMP的信號稀疏分解

匹配追蹤(MP)算法是一個典型的貪婪算法，其在分解的每一步中都需要計算信號或分解殘差和原子庫中每一個原子的內積，并找到最大值，將此最大值對應的原子作為最佳原子。而同為貪婪算法的另一種方案，正交匹配追蹤(OMP)算法則繼承了MP算法的原子選擇規則，并將所選取的原子通過Gram-Schmidt正交法進行正交化處理，然后再將分解殘差在正交化后的原子上進行投影，得到其在該原子上的分量和新的殘差，隨后用同樣的方法再次分解新殘差。在OMP分解過程中，所選原子仍然滿足最佳匹配原則，而遞推地對已選原子進行正交化，則保證了迭代的最優性，使得算法的收斂性得到提高。OMP信號稀疏分解的主要流程為：

(1) 在過完備原子庫中選擇與原始信號f最為匹配的原子gγ1，即滿足：

(1)

式中，{gγ}γ∈Γ為過完備原子庫，sup為最大值運算。

(3) 在OMP的第k步，選擇最佳原子gγk：

(2)

(4) 對最佳匹配原子gγk進行Gram-Schmidt正交化：

(3)

(5) 將上一步分解殘差Rk-1f在ek上投影，更新分解殘差：

Rkf=Rk-1f-〈Rk-1f,ek〉ek

(4)

(6) 若滿足下式：

(5)

則分解終止，否則k=k+1，轉到步驟(3)。

因此，分解N步以后，可以到信號f的近似表示：

(6)

2 果蠅優化算法

果蠅優化算法(FOA)由臺灣學者潘文超于2011年提出，是一種全新的智能仿生群體算法。由于果蠅具有靈敏的嗅覺和發達的視覺，其可以順利地找到遠在四五十公里之外的食物。模仿這一特性出現的果蠅優化算法，是一種尋求全局尋優的新方法，是一個全新的領域，尚處于發展完善階段。與其他的智能算法相比，其算法簡單，控制參數少，易于理解和學習，整體處理過程可以總結如下[11]：

(1) 初始值設定：最大迭代數Maxgen，群體規模SizePop，隨機的果蠅群體初始化位置InitX_axis、InitY_axis；

(2) 給定果蠅個體利用嗅覺覓食的隨機方向與距離：

(7)

(3) 由于食物位置未知，所以事先估計與原點的距離Disti，并計算下一位置的味道濃度判定值Si(距離的倒數)：

(8)

(9)

(4) 將Si代入味道濃度判定函數(適應度函數)，計算果蠅個體所在位置的味道濃度Smelli：

Smelli=Function(Si)

(10)

(5) 計算出整個群體中味道濃度最佳的果蠅：

[bestSmellbestindex]=max(Smelli)

(11)

(6) 記錄最佳味道濃度值bestSmell與其對應的坐標，此時果蠅群體依靠敏銳視覺飛向該坐標：

Smellbest=bestSmellX_axis=X(bestindex)Y_axis=Y(bestindex)

(12)

(7) 開始迭代循環，重復步驟(2)-步驟(5)，若當前最佳味道濃度優于前一迭代最佳味道濃度，且迭代次數小于最大迭代數，則執行步驟(6)。

3 自適應混沌果蠅優化算法ACFOA

由于傳統FOA在迭代尋優過程中易于陷入局部最優，而非全局最優，降低了收斂速度和收斂精度，文獻[12]中結合混沌理論提出了一種新的改進方案——自適應混沌果蠅優化算法(ACFOA)。該算法整體上以FOA算法為基礎，在尋優過程中對FOA的收斂狀態進行判斷。若處于局部最優狀態，則自適應地進入混沌操作，利用混沌的遍歷性、多樣性、隨機性，更新果蠅個體的位置。當新位置的味道濃度優于當前全局最優位置的味道濃度時，完成位置的更新，保持了種群的多樣性，解決了FOA的早熟收斂問題。

ACFOA主要流程如下：

(1) 參數設定：最大迭代數Maxgen，群體規模SizePop，隨機的果蠅群體初始化位置InitX_axis、InitY_axis，味道濃度方差閾值δ，混沌遍歷次數M；

(2) 執行FOA的步驟(2)-步驟(6)；

(3) 計算群體平均味道濃度Smellavg及味道濃度方差σ2：

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(8) 重復步驟(2)-步驟(7)，直到達到最大迭代次數。

4 改進ACFOA

4.1 味道濃度判定值的修正

由于FOA易于陷入局部最優，無法得到全局最優，故出現了多種FOA改進方案。其中，FOA陷入局部最優的一個原因是味道濃度判定值Si的自身缺陷[14]。Si為距離Disti的倒數，為非負數。為此出現了針對Si進行改進的FOA算法，其在Si上加入一個跳脫參數Δ，通過此參數在一定程度上可以達到擺脫局部最優找到全局最優的目的。修正的Si如下：

(21)

因此，本文將此修正的味道濃度判定值Si應用到ACFOA之中，以提升算法的全局尋優能力。

4.2 映射函數的改變

混沌現象廣泛存在于自然界之中，是一種非線性現象，具有內在隨機性、初始條件敏感性、有界性和遍歷性等特點。目前，混沌算法已經在各種優化算法中有了廣泛的應用。在優化算法中，通常所使用的混沌映射是Logistic映射，但其生成的混沌序列是非均勻的，遍歷性不足。為了改變Logistic映射的這一現象，前蘇聯學者Arnold提出了一種新的映射方案，由于其在演示時經常使用一幅貓圖，故稱之為Cat映射[15]。

Cat映射是一個可逆二維映射，其動力學方程為：

(22)

由于其系數矩陣的行列式為1，所以Cat映射具有區域保留性(Area-preserving)。當a=1,b=1時，即為經典Arnold Cat映射。式(22)中，mod1表示只取小數部分，故xn、yn均在[0,1]之間，滿足混沌變量要求。

Cat映射生成序列分布均勻，對初始值敏感性強，相比于Logistic映射，更適用于優化算法的改進。隨著技術的發展，近年來在圖像加密領域出現了廣義高維貓映射，相比于低維貓映射，Lyapunov指數更大，分布均勻，遍歷性好，運算效率高。因此，本文將CAT映射應用于ACFOA之中，取代Logistic映射，以進一步提升算法的尋優性能。

5 基于改進ACFOA的一維OMP圖像分解

圖像OMP分解復雜度高，分解緩慢，不便于實際應用。而稀疏分解的復雜度主要集中在分解過程中最優原子的搜索過程中，所以可以將具有良好并行性能的智能算法應用到最優原子搜索過程來降低計算復雜度。本文將改進ACFOA算法應用到OMP圖像分解當中，并結合圖像1DFFT—MP法[13]，將圖像二維OMP分解轉換為一維OMP分解。 對于M×N的圖像，具體分解流程如下：

(1) 將圖像由二維空間轉換到一維空間；

(3) 利用味道濃度判定值修正后的FOA算法對一維化后的圖像信號進行OMP分解，味道濃度判定函數Smelli為：

(23)

(4) 對FOA分解過程中是否陷入局部最優進行判斷，若陷入局部最優則采用Cat混沌操作，提升全局尋優精度；

(5) 循環操作，直至達到最大迭代數Maxgen。

分解流程如圖1所示。

圖1 基于改進ACFOA的圖像一維OMP稀疏分解流程

本文算法對ACFOA的味道濃度判定值進行了修正，避免了其無法取得負值的缺陷；用Cat混沌映射取代Logistic映射，初值敏感性更強，遍歷性更好。這兩方面使得本文算法相比原始的ACFOA具有更好的全局尋優效果。本文算法在提升尋優能力的同時，也在一定程度上增加了計算量。但稀疏分解本身的復雜度主要集中在內積計算上，而本文改進方案并不涉及內積計算。

6 實驗結果及分析

D =MN×5(log2M-1)×5(log2N-1)×min(M,N)

=1.6384×108

表1 不同大小的圖像一維和二維OMP稀疏分解速度比

圖2為256長信號不同OMP算法的信號殘差歸一化范數比較圖。從圖2可以看出，隨著稀疏分解原子數目的增加，本文算法(Modified ACFOA)、ACFOA和FOA三種方法的信號殘差歸一化范數越來越小。當分解原子數等于信號長度時，信號殘差的范數趨近于零，這是OMP算法的快速收斂性決定的；而對于相同的分解原子數，本文算法的信號殘差歸一化范數最小，FOA法最大。原因在于FOA算法在最佳原子搜索過程中會陷入局部最優，ACFOA對局部最優自適應地采用混沌操作，本文算法在ACFOA的基礎上進行了味道濃度判定值和混沌映射函數的改進，保持了種群的多樣性，進一步提升了算法的全局尋優性能。圖3為以上三種不同算法的圖像一維OMP稀疏分解重建結果，表2為不同算法一維OMP分解速度和重建圖像峰值信噪比(PSNR)對比結果。由這兩個實驗結果可以看出，重建圖像無論是在視覺效果上，還是在PSNR上，本文算法均優于ACFOA和FOA，說明本文算法的收斂性是最好的，收斂速度最快。對于同樣120個重建原子，本文算法重建圖像的PSNR較ACFOA和FOA分別提高了0.55 db和1.31 db。同時，由于本文算法進行了改進，計算量有所增大，分解用時分別為ACFOA和FOA的1.017倍和1.033倍，分解速度整體影響不大。

圖2 不同方法的OMP信號殘差歸一化范數比較

圖3 不同算法圖像一維OMP重建結果

算法分解速度(s)PSNR(db)FOA13.6134.87ACFOA13.8335.63ModifiedACFOA14.0636.18

7 結 語

稀疏分解用較少的原子，很好地表示了原始信號，充分表明了算法的優越性。目前，稀疏分解已經在交通圖像壓縮、超光譜圖像壓縮和腦CT圖像壓縮等方面取得了良好的應用。圖像壓縮需要用較少的原子表示原始圖像，從而達到較好的壓縮效果，而OMP算法相比于MP算法，收斂速度更快，在相同分解原子數目下，分解殘差更小，重建圖像質量更好。所以，OMP算法在圖像壓縮方面，有著良好的應用前景。但圖像稀疏分解計算復雜度高，運算耗時，阻礙了其在現實生活中的應用。本文將圖像稀疏分解由二維空間轉換到一維空間，實現了基于改進ACFOA的圖像一維OMP稀疏分解，很好地降低了計算的復雜度，提升了分解效率，為圖像稀疏分解的實際應用創造了有利條件。

[1] 沈益青.基于改進的匹配追蹤算法的信號稀疏分解[D].浙江大學,2013.

[2] 史麗麗.基于稀疏分解的信號去噪方法研究[D].哈爾濱工業大學,2013.

[3] 李雨昕,尹忠科,王建英.MP稀疏分解快速算法及其在語音識別中的應用[J].計算機工程與應用,2010,46(1):122-124.

[4] 陶少飛.匹配追蹤算法的優化及其在滾動軸承故障診斷中的應用[D].上海交通大學,2012.

[5] 劉婧玉.基于稀疏分解的地震數據壓縮編碼[D].西南交通大學,2010.

[6] 楊愚.利用粒子群算法實現信號OMP稀疏分解[J].微計算機信息,2008,24(12):178-179,201.

[7] 吳怡之,劉文軒.基于GA的心電信號稀疏分解MP算法改進[J].計算機工程,2013,39(9):250-253.

[8] 王菊,王朝暉,劉銀.基于PSO和LM的信號稀疏分解快速算法[J].激光與紅外,2012,42(2):227-230.

[9] 齊愛玲,馬宏偉.基于人工魚優化的MP超聲微弱信號提取方法研究[J].鐵道學報,2011,33(1):47-51.

[10] 房小娟.基于種群優化的稀疏分解算法研究[D].北京工業大學,2013.

[11] 肖正安.語音信號稀疏分解的FOA實現[J].計算機工程與應用,2013,49(10):232-234.

[12] 韓俊英,劉成忠.自適應混沌果蠅優化算法[J].計算機應用,2013,33(5):1313-1316.

[13] 李小燕,尹忠科.圖像1DFFT—MP稀疏分解算法研究[J].計算機科學,2010,37(10):246-250.

[14] 潘文超.果蠅最佳化演算法[M].2版.臺北:滄海書局,2013.

[15] 田漢清,全吉成,程紅,等.一種結合Cat映射和Henon映射的圖像加密技術[J].計算機應用與軟件,2010,27(9):286-288.

IMAGE 1D OMP SPARSE DECOMPOSITION BASED ON MODIFIED ACFOA

Yang Ming1Chen Lingling1*Yin Zhongke2

1(CollegeofInformationandControlEngineering,JilinInstituteofChemicalTechnology,Jilin132022,Jilin,China)2(SchoolofInformationScienceandTechnology,SouthwestJiaotongUniversity,Chengdu610031,Sichuan,China)

2D image sparse decomposition has the problem of high computational complexity. In order to solve this, we presented the image 1D orthogonal matching pursuit (OMP) sparse decomposition algorithm, which is based on modified adaptive chaos fruit fly optimisation algorithm (ACFOA). First, the algorithm converts the image from 2D space to 1D space. Then it modifies the flavour concentration determination value and chaotic mapping function of the ACFOA, improves the global optimisation performance of the algorithm. Finally, we applied the improved ACFOA in image 1D OMP decomposition. Experimental results showed that the speed of image 1D OMP algorithm was 1.12 times faster than 2D decomposition under the same condition.

Image sparse decomposition Orthogonal matching pursuit (OMP) Adaptive chaos fruit fly optimisation algorithm (ACFOA) Computational complexity Global optimum

2014-11-04。吉林省教育廳“十二五”科研規劃項目([2013]325)；吉林化工學院校級科研項目([2013]120)。楊明，講師，主研領域：信號與信息處理，圖像處理與傳輸。陳玲玲，講師。尹忠科，教授。

TP391.43

A

10.3969/j.issn.1000-386x.2016.04.048