基于局部字典搜索和多原子匹配追踪的图像逼近算法

计算机工程与科学

基于局部字典搜索和多原子匹配追踪的图像逼近算法

黄亚飞1,2,梁昔明1,樊绍胜2

(1.中南大学信息科学与工程学院，湖南长沙 410083；

2.长沙理工大学智能电网运行与控制湖南省重点实验室，湖南长沙 410114)

收稿日期:2016-02-23 修回日期:2016-10-17 出版日期:2018-01-25 发布日期:2018-01-25
基金资助:
国家自然科学基金(61473049)；中央支持地方项目(PXM 2013_014210_000173)

Image approximation based on local dictionary

searching and multi-atom matching pursuit

HUANG Ya-fei1,2,LIANG Xi-ming1,FAN Shao-sheng2

(1.School of Information Science and Engineering,Central South University,Changsha 410083;

2.Hunan Province Key Laboratory of Smart Grids Operation and Control,

Changsha University of Science and Technology,Changsha 410114,China)

Received:2016-02-23 Revised:2016-10-17 Online:2018-01-25 Published:2018-01-25

摘要/Abstract

摘要：

鉴于全局搜索和单原子选择的逼近方式是导致图像稀疏分解贪婪算法复杂度高的主要原因，对传统的匹配追踪(MP)算法进行改进，提出基于局部字典搜索和多原子匹配追踪(LMMP)的逼近算法。

采用基于二维快速哈莱特变换的内积批量计算方法，实验计算发现核原子在MP算法相邻代中的位序基本稳定，最佳原子只需在排序靠前的原子组成的局部字典中搜索，一次迭代搜索多个非相干原子，进一步提高匹配追踪算法速度，逐原子依次更新残差可减小逼近误差。
理论分析表明，LMMP算法是收敛的，且时间复杂度比MP算法低数个数量级。从实验结果看出，LMMP算法与其他全局搜索算法相比，在运算速度和逼近性能上有明显优势。

关键词: 匹配追踪, 局部搜索, 快速哈特莱变换, 多原子

Abstract:

Global searching in dictionary with single atom being selected in each iteration leads to greedy algorithms’ high complexity in sparse decomposition. Given this, we propose an improved matching pursuit (MP) algorithm named local dictionary searching and multi-atoms matching pursuit (LMMP).

Calculation showed that the order of kernel atoms in the adjacent generation of MP algorithm is basically stable, the best atom just to search in local dictionary consisting of the front order atoms. Searching for multiple incoherent atoms on single iteration to further improve the speed of MP algorithm. Reduce the approximation error by updating the residual image one by one atom in turn.

Theoretical analysis indicates that the LMMP algorithm is convergent and its time complexity is several orders of magnitude lower than the MP. Experimental results show that the LMMP algorithm outperforms other global searching methods in computational speed and approximation performance.

Key words: matching pursuit, local search, fast Hartley transform, multi-atom

黄亚飞1,2,梁昔明1,樊绍胜2. 基于局部字典搜索和多原子匹配追踪的图像逼近算法[J]. 计算机工程与科学.

HUANG Ya-fei1,2,LIANG Xi-ming1,FAN Shao-sheng2.

Image approximation based on local dictionary

searching and multi-atom matching pursuit

[J]. Computer Engineering & Science.

[1]	胡春安, 熊昱然. 多策略改进的混沌哈里斯鹰优化算法[J]. 计算机工程与科学, 2023, 45(09): 1648-1660.
[2]	杨炳媛, 袁杰, 郭园园. 一种自适应鲸鱼快速优化算法[J]. 计算机工程与科学, 2023, 45(01): 145-153.
[3]	宋强. Beam-PSO优化算法在多行程车辆路径问题的应用[J]. 计算机工程与科学, 2019, 41(10): 1882-1891.
[4]	林要华1，王维2. 基于逐维策略的布谷鸟搜索增强算法[J]. 计算机工程与科学, 2017, 39(01): 165-172.
[5]	刘汉强,郑朋. 局部搜索自适应核模糊聚类方法[J]. 计算机工程与科学, 2016, 38(08): 1735-1740.
[6]	臧培荃，孙晨骜，顾晓峰，吴滨，周长喜. 具有自适应趋向性和引导因子的人工蜂群算法[J]. J4, 2015, 37(09): 1692-1697.
[7]	罗晖，刘洁丽，祁美丽. 基于稀疏表示的WMSN红外和可见光图像融合[J]. J4, 2014, 36(05): 957-962.
[8]	包云，姜华，郑丽萍. 基于和声搜索的阻塞流水车间调度问题的算法优化[J]. J4, 2013, 35(7): 108-112.
[9]	罗敏1，郑明辉2. 结合小波变换和稀疏表征的鲁棒人脸识别[J]. J4, 2012, 34(12): 130-133.
[10]	刘一丹1,王子牛2 ,陈洁1 , 李少博1. 基于DEXEL和离散点阵法的数控加工仿真研究[J]. J4, 2011, 33(1): 171-175.
[11]	向佐勇[1,2] 刘正才[2]. 一种改进的混合遗传算法研究[J]. J4, 2008, 30(9): 53-57.
[12]	赵同昇[1] 朱文兴[2]. MAX—SAT问题一种改进的局部搜索算法[J]. J4, 2008, 30(11): 50-52.
[13]	郑雅燕[1] 朱文兴[2]. TSP问题的一种改进的GRASP算法[J]. J4, 2008, 30(11): 60-64.
[14]	蒋皓石杜谋辉林嘉宇. 说话人识别中随机局部搜索算法的研究[J]. J4, 2006, 28(7): 85-86.
[15]	韩丽霞[1] 王宇平[2]. 求解旅行商问题的一个新的单亲遗传算法[J]. J4, 2006, 28(2): 72-73.