楊 明 陳玲玲* 尹忠科

基于改進(jìn)ACFOA的圖像一維OMP稀疏分解

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

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

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

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

圖像稀疏分解 正交匹配追蹤 自適應(yīng)混沌果蠅優(yōu)化算法 計(jì)算復(fù)雜度 全局最優(yōu)

0 引 言

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

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

文獻(xiàn)[13]提出了一種新的圖像稀疏分解快速算法——圖像1DFFT—MP法。將二維圖像信號(hào)和二維分解原子均轉(zhuǎn)為一維信號(hào)，并將一維原子信號(hào)進(jìn)行集合劃分，然后利用一維信號(hào)的FFT—MP法進(jìn)行稀疏分解和重建，提升算法的運(yùn)算速度和重建質(zhì)量。本文通過(guò)對(duì)OMP和ACFOA的研究，結(jié)合文獻(xiàn)[13]的思想，將ACFOA應(yīng)用到圖像OMP稀疏分解當(dāng)中，并針對(duì)ACFOA的味道濃度判定值進(jìn)行了改進(jìn)。同時(shí)用概率密度更均勻、遍歷性更好的Cat映射取代Logistic映射，以達(dá)到對(duì)信號(hào)的更快更好的稀疏分解結(jié)果。

1 基于OMP的信號(hào)稀疏分解

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

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

(1)

式中，{gγ}γ∈Γ為過(guò)完備原子庫(kù)，sup為最大值運(yùn)算。

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

(2)

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

(3)

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

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

(4)

(6) 若滿足下式：

(5)

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

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

(6)

2 果蠅優(yōu)化算法

果蠅優(yōu)化算法(FOA)由臺(tái)灣學(xué)者潘文超于2011年提出，是一種全新的智能仿生群體算法。由于果蠅具有靈敏的嗅覺(jué)和發(fā)達(dá)的視覺(jué)，其可以順利地找到遠(yuǎn)在四五十公里之外的食物。模仿這一特性出現(xiàn)的果蠅優(yōu)化算法，是一種尋求全局尋優(yōu)的新方法，是一個(gè)全新的領(lǐng)域，尚處于發(fā)展完善階段。與其他的智能算法相比，其算法簡(jiǎn)單，控制參數(shù)少，易于理解和學(xué)習(xí)，整體處理過(guò)程可以總結(jié)如下[11]：

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

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

(7)

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

(8)

(9)

(4) 將Si代入味道濃度判定函數(shù)(適應(yīng)度函數(shù))，計(jì)算果蠅個(gè)體所在位置的味道濃度Smelli：

Smelli=Function(Si)

(10)

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

[bestSmellbestindex]=max(Smelli)

(11)

(6) 記錄最佳味道濃度值bestSmell與其對(duì)應(yīng)的坐標(biāo)，此時(shí)果蠅群體依靠敏銳視覺(jué)飛向該坐標(biāo)：

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

(12)

(7) 開(kāi)始迭代循環(huán)，重復(fù)步驟(2)-步驟(5)，若當(dāng)前最佳味道濃度優(yōu)于前一迭代最佳味道濃度，且迭代次數(shù)小于最大迭代數(shù)，則執(zhí)行步驟(6)。

3 自適應(yīng)混沌果蠅優(yōu)化算法ACFOA

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

ACFOA主要流程如下：

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

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

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

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

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

4 改進(jìn)ACFOA

4.1 味道濃度判定值的修正

由于FOA易于陷入局部最優(yōu)，無(wú)法得到全局最優(yōu)，故出現(xiàn)了多種FOA改進(jìn)方案。其中，F(xiàn)OA陷入局部最優(yōu)的一個(gè)原因是味道濃度判定值Si的自身缺陷[14]。Si為距離Disti的倒數(shù)，為非負(fù)數(shù)。為此出現(xiàn)了針對(duì)Si進(jìn)行改進(jìn)的FOA算法，其在Si上加入一個(gè)跳脫參數(shù)Δ，通過(guò)此參數(shù)在一定程度上可以達(dá)到擺脫局部最優(yōu)找到全局最優(yōu)的目的。修正的Si如下：

(21)

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

4.2 映射函數(shù)的改變

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

Cat映射是一個(gè)可逆二維映射，其動(dòng)力學(xué)方程為：

(22)

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

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

5 基于改進(jìn)ACFOA的一維OMP圖像分解

圖像OMP分解復(fù)雜度高，分解緩慢，不便于實(shí)際應(yīng)用。而稀疏分解的復(fù)雜度主要集中在分解過(guò)程中最優(yōu)原子的搜索過(guò)程中，所以可以將具有良好并行性能的智能算法應(yīng)用到最優(yōu)原子搜索過(guò)程來(lái)降低計(jì)算復(fù)雜度。本文將改進(jìn)ACFOA算法應(yīng)用到OMP圖像分解當(dāng)中，并結(jié)合圖像1DFFT—MP法[13]，將圖像二維OMP分解轉(zhuǎn)換為一維OMP分解。 對(duì)于M×N的圖像，具體分解流程如下：

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

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

(23)

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

(5) 循環(huán)操作，直至達(dá)到最大迭代數(shù)Maxgen。

分解流程如圖1所示。

圖1 基于改進(jìn)ACFOA的圖像一維OMP稀疏分解流程

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

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

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

=1.6384×108

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

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

圖2 不同方法的OMP信號(hào)殘差歸一化范數(shù)比較

圖3 不同算法圖像一維OMP重建結(jié)果

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

7 結(jié) 語(yǔ)

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

[1] 沈益青.基于改進(jìn)的匹配追蹤算法的信號(hào)稀疏分解[D].浙江大學(xué),2013.

[2] 史麗麗.基于稀疏分解的信號(hào)去噪方法研究[D].哈爾濱工業(yè)大學(xué),2013.

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

[4] 陶少飛.匹配追蹤算法的優(yōu)化及其在滾動(dòng)軸承故障診斷中的應(yīng)用[D].上海交通大學(xué),2012.

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

[6] 楊愚.利用粒子群算法實(shí)現(xiàn)信號(hào)OMP稀疏分解[J].微計(jì)算機(jī)信息,2008,24(12):178-179,201.

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

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

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

[10] 房小娟.基于種群優(yōu)化的稀疏分解算法研究[D].北京工業(yè)大學(xué),2013.

[11] 肖正安.語(yǔ)音信號(hào)稀疏分解的FOA實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(10):232-234.

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

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

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

[15] 田漢清,全吉成,程紅,等.一種結(jié)合Cat映射和Henon映射的圖像加密技術(shù)[J].計(jì)算機(jī)應(yīng)用與軟件,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。吉林省教育廳“十二五”科研規(guī)劃項(xiàng)目([2013]325)；吉林化工學(xué)院校級(jí)科研項(xiàng)目([2013]120)。楊明，講師，主研領(lǐng)域：信號(hào)與信息處理，圖像處理與傳輸。陳玲玲，講師。尹忠科，教授。

TP391.43

A

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