杨 明 陈玲玲* 尹忠科

基于改进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