2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于学习字典的机器人图像稀疏表示方法

郭俊锋 李育亮

郭俊锋, 李育亮. 基于学习字典的机器人图像稀疏表示方法. 自动化学报, 2020, 46(4): 820-830. doi: 10.16383/j.aas.2018.c170352
引用本文: 郭俊锋, 李育亮. 基于学习字典的机器人图像稀疏表示方法. 自动化学报, 2020, 46(4): 820-830. doi: 10.16383/j.aas.2018.c170352
GUO Jun-Feng, LI Yu-Liang. Sparse Representation of Robot Image Based on Dictionary Learning Algorithm. ACTA AUTOMATICA SINICA, 2020, 46(4): 820-830. doi: 10.16383/j.aas.2018.c170352
Citation: GUO Jun-Feng, LI Yu-Liang. Sparse Representation of Robot Image Based on Dictionary Learning Algorithm. ACTA AUTOMATICA SINICA, 2020, 46(4): 820-830. doi: 10.16383/j.aas.2018.c170352

基于学习字典的机器人图像稀疏表示方法


DOI: 10.16383/j.aas.2018.c170352
详细信息
    作者简介:

    郭俊锋  兰州理工大学机电工程学院副教授.主要研究方向为先进控制技术, 信号检测, 压缩感知.E-mail:junf_guo@163.com

    通讯作者: 李育亮  兰州理工大学硕士研究生.主要研究方向为机器人图像处理, 稀疏表示算法.本文通信作者.E-mail: lyl931206@163.com
  • 本文责任编委 黎铭
  • 基金项目:

    国家自然科学基金 51465034

Sparse Representation of Robot Image Based on Dictionary Learning Algorithm

More Information
    Author Bio:

    GUO Jun-Feng   Associate professor at the College of mechanical and electrical engineering, Lanzhou University of Technology. His research interest covers advanced control technology, signal detection, and compression sensing

    Corresponding author: LI Yu-Liang  Master student at the College of mechanical and electrical engineering, Lanzhou University of Technology. His research interest covers robot image processing and sparse representation algorithm. Corresponding author of this paper
  • Recommended by Associate Editor LI Ming
  • Fund Project:

    National Natural Science Foundation of China 51465034

  • 摘要: 针对机器人图像压缩感知(Compressed sensing, CS)过程中稀疏字典训练时间过长的问题, 本文提出了一种更加高效的字典学习方法.通过对MOD、K-SVD、SGK等字典学习算法研究, 从参与更新的字典原子列数入手, 将残差项变形为多列原子同时更新, 进而利用最小二乘法连续地更新字典中的多个原子.本文算法是对SGK算法字典学习效率的进一步提高, 减少了单次迭代的计算量, 加快了字典学习速度.实验表明, 本文算法与K-SVD和SGK算法相比, 在字典稀疏性和重构图像质量变化很小的情况下, 字典训练时间得到较明显缩短.
    本文责任编委 黎铭
    Recommended by Associate Editor LI Ming
  • 图  1  本文字典学习算法流程图

    Fig.  1  The flow chart of the dictionary learning algorithm in this paper

    图  2  原始图像及其加噪图像

    Fig.  2  Original image and noisy image

    图  3  重构效果对比图

    Fig.  3  The reconstruction effect comparison

    图  4  不同迭代次数下的字典学习时间

    Fig.  4  Time consumption of dictionary learning for different iteration times

    图  5  不同噪声程度下的字典学习时间

    Fig.  5  Time consumption of dictionary learning for different noise levels

    图  6  自然场景图像重构效果对比

    Fig.  6  Comparison of image reconstruction effects in natural scenes

    表  1  不同字典原子选取方式效果对比

    Table  1  Comparison of the effects for different selections of dictionary atoms

    选取待更新字典原子的方式 顺次选取连续的2列 随机选取连续的2列 随机选取离散的2列
    字典学习时间(s) 3.994 5.268 6.788
    峰值信噪比PSNR (dB) 32.092 31.968 31.866
    平均结构相似度MSSIM 0.3183 0.3152 0.3114
    下载: 导出CSV

    表  2  同时更新不同字典列数效果对比

    Table  2  Effect comparison of updating different numbers of dictionary columns at the same time

    同时更新原子列数 2 4 8 16 32 64
    字典学习时间(s) 4.117 4.194 3.630 3.744 4.032 4.093
    峰值信噪比PSNR (dB) 32.092 32.065 32.081 32.145 32.058 32.045
    平均结构相似度MSSIM 0.3183 0.3176 0.3177 0.3173 0.3164 0.3181
    下载: 导出CSV

    表  3  不同算法的重构效果

    Table  3  Reconstruction effect with different algorithms

    算法 DCT字典 K-SVD字典 SGK字典 本文算法字典
    字典学习时间(s) -- 20.079 4.254 3.605
    峰值信噪比PSNR (dB) 30.915 31.950 31.935 31.947
    平均结构相似度MSSIM 0.3022 0.3149 0.3137 0.3144
    下载: 导出CSV

    表  4  不同迭代次数重构图像质量

    Table  4  The quality of the reconstructed image with different numbers of iteration

    迭代次数 K-SVD字典 SGK字典 本文算法字典
    PSNR (dB) MSSIM PSNR (dB) MSSIM PSNR (dB) MSSIM
    3 31.4559 0.30762 31.4459 0.30779 31.4603 0.30825
    6 31.9951 0.31384 31.9291 0.31171 31.9265 0.31207
    9 31.9704 0.31386 31.9490 0.31287 31.9194 0.31313
    12 32.2901 0.31418 32.2661 0.31423 32.2416 0.31279
    15 32.3571 0.31986 32.3297 0.31898 32.2724 0.31921
    18 32.4407 0.32208 32.3781 0.32182 32.3485 0.32141
    21 32.4489 0.32209 32.4040 0.32206 32.3971 0.32172
    下载: 导出CSV

    表  5  不同噪声水平下重构图像质量

    Table  5  The quality of the reconstructed image with different noise levels

    标准差 K-SVD字典 SGK字典 本文算法字典
    PSNR (dB) MSSIM PSNR (dB) MSSIM PSNR (dB) MSSIM
    10 35.9741 0.45381 35.9440 0.45390 35.9620 0.45430
    20 33.2254 0.34207 33.1664 0.34219 33.2006 0.34282
    30 31.3615 0.30139 31.2992 0.29996 31.3157 0.29984
    40 29.4226 0.26534 29.3889 0.26387 29.4074 0.26427
    50 28.0932 0.23598 28.0699 0.23470 28.0908 0.23485
    60 26.8134 0.20862 26.8110 0.20815 26.8230 0.20744
    70 25.6137 0.18573 25.6164 0.18493 25.6238 0.18591
    下载: 导出CSV

    表  6  不同图像信号的重构效果

    Table  6  Reconstruction effect of different image signals

    图像 算法 时间(s) MSSIM PSNR (dB)
    lena K-SVD 18.343162 0.27010 25.8505
    SGK 3.891636 0.26863 25.8154
    本文算法 3.102337 0.26916 25.8230
    peppers K-SVD 19.244135 0.35640 26.1407
    SGK 4.141303 0.35574 26.1445
    本文算法 3.092842 0.35545 26.1353
    barbara K-SVD 19.438234 0.35642 25.2067
    SGK 4.114145 0.35763 25.1997
    本文算法 3.197942 0.35774 25.2009
    下载: 导出CSV

    表  7  不同场景自然图像信号的重构效果

    Table  7  Reconstruction effect of image signals in different natural scenes

    图像 时间(s) MSSIM PSNR (dB)
    K-SVD SGK 本文算法 K-SVD SGK 本文算法 K-SVD SGK 本文算法
    (a)明 20.196063 4.470679 3.958860 0.35006 0.35036 0.35019 26.3382 26.3285 26.3339
    (a)暗 19.138866 4.303163 3.779787 0.25134 0.25155 0.25157 27.0640 27.0637 27.0611
    (b)视角1 19.294378 4.068634 3.263159 0.29148 0.29095 0.29066 25.9845 25.9772 29.9781
    (b)视角2 21.498433 4.167165 3.233882 0.30110 0.30121 0.30176 28.2839 28.2803 28.2971
    (c)清晰 20.856516 4.534554 4.031721 0.35926 0.35839 0.35854 26.0795 26.0734 26.0601
    (c)模糊 18.319955 3.874162 2.932584 0.41004 0.41013 0.40993 29.4348 29.4386 29.4385
    下载: 导出CSV
  • [1] Candes E J. Compressive sampling. In: Proceedings of International Congress of Mathematicians. Madrid, Spain: European Mathematical Society Publishing House, 2006. 1433-1452
    [2] 任越美, 张艳宁, 李映.压缩感知及其图像处理应用研究进展与展望.自动化学报, 2014, 40(8): 1563-1575 doi:  10.3724/SP.J.1004.2014.01563

    Ren Yue-Mei, Zhang Yan-Ning, Li Ying. Advances and perspective on compressed sensing and application on image processing. Acta Automatica Sinica, 2014, 40(8): 1563-1575 doi:  10.3724/SP.J.1004.2014.01563
    [3] 占新.基于字典学习与稀疏模型的SAR图像压缩技术研究[Ph. D. dissertation].中国科学技术大学, 2015

    Zhan Xin. Research on Dictionary Learning-based SAR Image Compression Techbique[Ph. D. dissertation], University of Science and Technology of China, China, 2015
    [4] Olshausen B A, Field D J. Emergency of simple-cell receptive fleld properties by learning a sparse code for natural images. Nature, 1996, 381(6583): 607-609 doi:  10.1038/381607a0
    [5] Engan K, Aase S O, Husoy J H. Method of optimal directions for frame design. In: Proceedings of the 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing. Phoenix, AZ, USA: IEEE, 1999. 2443-2446
    [6] Aharon M, Elad M, Bruckstein A M. The K-SVD: an algorithm for designing of overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 2006, 54(11): 4311-4322 doi:  10.1109/TSP.2006.881199
    [7] 王强, 张培林, 王怀光, 吴定海, 张云强.基于稀疏分解的振动信号数据压缩算法.仪器仪表学报, 2016, 37(11): 2497-2505 doi:  10.3969/j.issn.0254-3087.2016.11.012

    Wang Qiang, Zhang Pei-Lin, Wang Huai-Guang, Wu Ding-Hai, Zhang Yun-Qiang. Data compression algorithm of vibration signal based on sparse decomposition. Chinese Journal of Scientific Instrument, 2016, 37(11): 2497-2505 doi:  10.3969/j.issn.0254-3087.2016.11.012
    [8] 易可夫, 王东豪, 万江文.基于优化字典学习算法的压缩数据收集.北京航空航天大学学报, 2016, 42(6): 1203-1209 http://d.old.wanfangdata.com.cn/Periodical/bjhkhtdxxb201606015

    Yi Ke-Fu, Wang Dong-Hao, Wan Jiang-Wen. Optimized dictionary learning algorithm for compressive data gathering.Journal of Beijing University of Aeronautics and Astronautics, 2016, 42(6): 1203-1209 http://d.old.wanfangdata.com.cn/Periodical/bjhkhtdxxb201606015
    [9] 陆婉芸, 王继周, 曹萌.变序字典学习AO-DL的资源三号遥感影像云去除, 测绘学报, 2017, 46(5): 623-630 http://d.old.wanfangdata.com.cn/Periodical/chxb201705011

    Lu Wan-Yun, Wang Ji-Zhou, Cao-Meng. Cloud removal in ZY-3 remote sensing image based on atoms-reorded dictionary learning AO-DL. Acta Geodaetica et Cartographica Sinica, 2017, 46(5): 623-630 http://d.old.wanfangdata.com.cn/Periodical/chxb201705011
    [10] Sahoo S K, Makur A. Replacing K-SVD with SGK: Dictionary training for sparse representation of images. In: Proceedings of the 2015 IEEE International Conference on Digital Signal Processing. Singapore, Singapore: IEEE, 2015. 614-617
    [11] 练秋生, 石保顺, 陈书贞.字典学习模型、算法及其应用研究进展.自动化学报, 2015, 41(2): 240-260 doi:  10.16383/j.aas.2015.c140252

    Lian Qiu-Sheng, Shi Bao-Shun, Chen Shu-Zhen. Research advances on dictionary learning models, algorithms and applications. Acta Automatica Sinica, 2015, 41(2): 240-260 doi:  10.16383/j.aas.2015.c140252
    [12] Sahoo S K, Makur A. Dictionary training for sparse representation as generalization of K-means clustering. IEEE Signal Processing Letters, 2013, 20(6): 587-590 doi:  10.1109/LSP.2013.2258912
    [13] Sahoo S K, Makur A. Image denoising via sparse representations over Sequential Generalization of K-means (SGK). In: Proceedings of the 9th IEEE International Conference on Information, Communications and Signal Processing. Tainan, China: IEEE, 2014. 1-5
    [14] Wang Z, Bovik A, Sheikh H, et al. Image quality assessment: from error visibility to structural similarity. IEEE Transactions on Image Processing, 2004, 13(4): 600-612 doi:  10.1089-fpd.2009.0394/
  • [1] 陈晓云, 廖梦真. 基于稀疏和近邻保持的极限学习机降维[J]. 自动化学报, 2019, 45(2): 325-333. doi: 10.16383/j.aas.2018.c170216
    [2] 汤红忠, 李骁, 张小刚, 张东波, 王翔, 毛丽珍. Fisher准则下面向判别性特征的字典学习方法及其组织病理图像分类研究[J]. 自动化学报, 2018, 44(10): 1842-1853. doi: 10.16383/j.aas.2017.c160814
    [3] 杨国铮, 禹晶, 肖创柏, 孙卫东. 基于形态字典学习的复杂背景SAR图像舰船尾迹检测[J]. 自动化学报, 2017, 43(10): 1713-1725. doi: 10.16383/j.aas.2017.c160274
    [4] 马名浪, 何小海, 滕奇志, 陈洪刚, 卿粼波. 基于自适应稀疏变换的指纹图像压缩[J]. 自动化学报, 2016, 42(8): 1274-1284. doi: 10.16383/j.aas.2016.c150815
    [5] 王琴, 沈远彤. 基于压缩感知的多尺度最小二乘支持向量机[J]. 自动化学报, 2016, 42(4): 631-640. doi: 10.16383/j.aas.2016.c150296
    [6] 田金鹏, 刘小娟, 郑国莘. 一种变步长稀疏度自适应子空间追踪算法[J]. 自动化学报, 2016, 42(10): 1512-1519. doi: 10.16383/j.aas.2016.c150801
    [7] 郑思龙, 李元祥, 魏宪, 彭希帅. 基于字典学习的非线性降维方法[J]. 自动化学报, 2016, 42(7): 1065-1076. doi: 10.16383/j.aas.2016.c150557
    [8] 沈燕飞, 李锦涛, 朱珍民, 张勇东, 代锋. 基于非局部相似模型的压缩感知图像恢复算法[J]. 自动化学报, 2015, 41(2): 261-272. doi: 10.16383/j.aas.2015.c140210
    [9] 练秋生, 石保顺, 陈书贞. 字典学习模型、算法及其应用研究进展[J]. 自动化学报, 2015, 41(2): 240-260. doi: 10.16383/j.aas.2015.c140252
    [10] 汤红忠, 张小刚, 陈华, 程炜, 唐美玲. 带边界条件约束的非相干字典学习方法及其稀疏表示[J]. 自动化学报, 2015, 41(2): 312-319. doi: 10.16383/j.aas.2015.c140183
    [11] 彭向东, 张华, 刘继忠. 基于过完备字典的体域网压缩感知心电重构[J]. 自动化学报, 2014, 40(7): 1421-1432. doi: 10.3724/SP.J.1004.2014.01421
    [12] 任越美, 张艳宁, 李映. 压缩感知及其图像处理应用研究进展与展望[J]. 自动化学报, 2014, 40(8): 1563-1575. doi: 10.3724/SP.J.1004.2014.01563
    [13] 陈思宝, 赵令, 罗斌. 基于局部保持的核稀疏表示字典学习[J]. 自动化学报, 2014, 40(10): 2295-2305. doi: 10.3724/SP.J.1004.2014.02295
    [14] 刘芳, 武娇, 杨淑媛, 焦李成. 结构化压缩感知研究进展[J]. 自动化学报, 2013, 39(12): 1980-1995. doi: 10.3724/SP.J.1004.2013.01980
    [15] 杜卓明, 耿国华, 贺毅岳. 一种基于压缩感知的二维几何信号压缩方法[J]. 自动化学报, 2012, 38(11): 1841-1846. doi: 10.3724/SP.J.1004.2012.01841
    [16] 孙明轩, 毕宏博. 学习辨识:最小二乘算法及其重复一致性[J]. 自动化学报, 2012, 38(5): 698-706. doi: 10.3724/SP.J.1004.2012.00698
    [17] 孙玉宝, 肖亮, 韦志辉, 邵文泽. 基于Gabor 感知多成份字典的图像稀疏表示算法研究[J]. 自动化学报, 2008, 34(11): 1379-1387. doi: 10.3724/SP.J.1004.2008.01379
    [18] 刘丹, 孙金玮, 魏国, 刘昕. 移动最小二乘法在多功能传感器数据重构中的应用[J]. 自动化学报, 2007, 33(8): 823-828. doi: 10.1360/aas-007-0823
    [19] 张颖, 冯纯伯. 闭环系统辨识的偏差最小二乘法[J]. 自动化学报, 1997, 23(3): 308-313.
    [20] 张颖, 冯纯伯. 应用最小二乘法辨识闭环系统[J]. 自动化学报, 1996, 22(4): 452-455.
  • 加载中
图(6) / 表(7)
计量
  • 文章访问数:  2545
  • HTML全文浏览量:  616
  • PDF下载量:  186
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-06-26
  • 录用日期:  2018-03-06
  • 刊出日期:  2020-04-24

基于学习字典的机器人图像稀疏表示方法

doi: 10.16383/j.aas.2018.c170352
    基金项目:

    国家自然科学基金 51465034

    作者简介:

    郭俊锋  兰州理工大学机电工程学院副教授.主要研究方向为先进控制技术, 信号检测, 压缩感知.E-mail:junf_guo@163.com

    通讯作者: 李育亮  兰州理工大学硕士研究生.主要研究方向为机器人图像处理, 稀疏表示算法.本文通信作者.E-mail: lyl931206@163.com
  • 本文责任编委 黎铭

摘要: 针对机器人图像压缩感知(Compressed sensing, CS)过程中稀疏字典训练时间过长的问题, 本文提出了一种更加高效的字典学习方法.通过对MOD、K-SVD、SGK等字典学习算法研究, 从参与更新的字典原子列数入手, 将残差项变形为多列原子同时更新, 进而利用最小二乘法连续地更新字典中的多个原子.本文算法是对SGK算法字典学习效率的进一步提高, 减少了单次迭代的计算量, 加快了字典学习速度.实验表明, 本文算法与K-SVD和SGK算法相比, 在字典稀疏性和重构图像质量变化很小的情况下, 字典训练时间得到较明显缩短.

本文责任编委 黎铭

English Abstract

郭俊锋, 李育亮. 基于学习字典的机器人图像稀疏表示方法. 自动化学报, 2020, 46(4): 820-830. doi: 10.16383/j.aas.2018.c170352
引用本文: 郭俊锋, 李育亮. 基于学习字典的机器人图像稀疏表示方法. 自动化学报, 2020, 46(4): 820-830. doi: 10.16383/j.aas.2018.c170352
GUO Jun-Feng, LI Yu-Liang. Sparse Representation of Robot Image Based on Dictionary Learning Algorithm. ACTA AUTOMATICA SINICA, 2020, 46(4): 820-830. doi: 10.16383/j.aas.2018.c170352
Citation: GUO Jun-Feng, LI Yu-Liang. Sparse Representation of Robot Image Based on Dictionary Learning Algorithm. ACTA AUTOMATICA SINICA, 2020, 46(4): 820-830. doi: 10.16383/j.aas.2018.c170352
  • 智能机器人通过多种传感器与外界交流, 据研究表明, 其中约70 %的外部信息来自视觉图像.传统的视觉图像采样是基于采样频率不能低于模拟信号频谱中最高频率的2倍的香农采样定理, 这种采样方式将会得到巨量的数据, 后期处理工作量大速度慢, 导致机器人运行迟钝行为缓慢.近些年来, Candes提出的全新的信号压缩采样方法压缩感知(Compressed sensing, CS) [1], 能大大降低数据的维数, 减少数据量, 其得到的测量值包含有能够重构出原图像信号的丰富信息.对机器人视觉来说, 图像处理的主要目的是获取图像的特征信息, 并不需要完整的原始图像, 因此只须在压缩域对低维数据进行处理并获取其特征信息, 进而提高机器人的反应和运行速度.压缩感知的前提条件是图像信号在变换基或者说字典上具有稀疏性, 其直接影响着压缩测量数, 图像在所选择稀疏字典上越稀疏, 其所需要的压缩测量数就越少, 后期处理就越快, 反之若选择的稀疏字典不能很好地满足要求, 其数据量就越多且重构图像质量也越差.只有获得最佳稀疏矩阵, 才能最有效并简洁地表示原始信号, 才能保证所恢复信号的精确性[2].

    信号的稀疏表示一般分为两大类方法:第一类是分析字典, 如DCT (Discrete cosine transform)字典、小波字典、脊波字典、曲线波字典等; 第二类就是根据数据或者信号本身训练的过完备字典[3].前者构造简单, 但字典原子形态单一不能对复杂的自然图像进行有效的稀疏表示; 而通过学习获得的冗余字典具有更好地自适应重构图像的能力, 字典中原子与待重建图像具有相关性, 能更有效表达图像局部结构特点, 使得信号在字典上有更稀疏的表示.而且, 由于部分噪声在字典上是非稀疏的, 而图像信号在字典上具有稀疏性, 因此基于学习字典对图像进行稀疏表示具有一定去噪作用.综上, 用学习字典的方法对图像进行稀疏表示具有较大优势.

    在权威的《自然》杂志上Olshausen等提出一种Sparsenet算法的字典学习方法[4], 其采用梯度下降算法和最大似然估计算法获得字典训练的更新, 字典学习的理论雏形由此诞生.受广义聚类算法的启发, Engan等在Sparsenet字典学习算法的基础上提出了MOD (Method of optimal directions)字典学习算法[5], 它直接采用最小二乘法解决目标函数的优化问题, 但其过程需要大矩阵的乘法和求逆计算, 对存储容量的要求高.为了降低MOD算法的计算复杂度尤其是空间复杂度, Aharon等提出了K-SVD (K-singular value decomposition)算法[6], 使字典逐列更新, 提高了字典学习速度, 但其应用SVD分解使计算复杂度依旧较大.王强等[7]提出利用改进的K-SVD算法进行稀疏分解, 在每次奇异值分解后对多列字典原子同时赋值, 减少了迭代时间, 但信号重构质量有所下降.易可夫等[8]提出了一种优化字典学习算法来构造压缩数据收集中的稀疏字典, 提高了压缩数据收集对多样化传感数据的适应能力, 同时抑制环境噪声对数据收集精度的影响, 但其字典学习效率并未提高.陆婉芸等[9]在字典原子训练的过程中加入某种特定的排序规则, 使得各个影像字典在拥有各自影像属性的同时其原子也具备相似的排列顺序, 减小影像间差异的干扰, 但其仍沿用传统的K-SVD算法更新字典计算复杂度较高.

    上述方法对字典更新速度上并没有大幅度提高, 计算复杂度较大, 不能适用于机器人图像的稀疏表示.最近, 一种被称作SGK (Sequential generalization of k-means)的字典学习算法[10]被作为经典K-SVD算法的有效替代, 相比于K-SVD它具有更快的执行速度和与之相媲美的字典训练效果.但SGK算法仅通过单列字典的更新, 计算复杂度较高, 时间消耗仍然较多.为此本文提出了一种基于SGK算法的改进算法, 将SGK算法中的残差项变形为多列原子同时更新, 进而利用最小二乘法更新字典中的$r$个原子, 减少了单次迭代的计算量和稀疏表示的时间, 提高了字典学习效率.

    • MOD、K-SVD和SGK算法及在其基础上改进算法的思想核心都来自聚类算法, 且算法的主要步骤都包括字典的初始化、对稀疏系数矩阵$A$的稀疏编码和对字典$D$的更新这三步.其目标函数模型可以表示为:

      $$ \begin{equation} \mathop {\min }\limits_{D, A}\{\|X-DA\|_F^2 \} \quad {\rm s.\, t.} \quad \forall _i\|{\pmb \alpha}_{i}\|_0\le T_0 \end{equation} $$ (1)

      式中, $X$表示样本信号, $D$表示过完备字典, ${\pmb \alpha}_{i}$是稀疏系数矩阵$A=\left[{{\pmb \alpha}_{1}, {\pmb \alpha}_{2}, \cdots, {\pmb \alpha}_{N} } \right]$的列, $\left\| {\left. A \right\|} \right._F $是矩阵$A$的Frobenius范数, $T_0 $为用于表示信号$X$所使用的字典原子数, 即稀疏系数向量${\pmb \alpha}_{i} $中非零元素个数.字典的初始化有两种选择:一种是任意给定一个字典(如过完备离散余弦DCT字典)进行初始化; 另一种是从训练样本集中随机地选取$K$个元素.稀疏编码阶段一般是固定初始化后的过完备字典$D$, 求解稀疏系数矩阵$A$.稀疏编码阶段常用的方法有匹配追踪(Matching pursuit, MP)、正交匹配追踪(Orthogonal matching pursuit, OMP)、基追踪(Basic pursuit, BP)等.字典更新阶段是固定稀疏编码后得到的$A$, 进一步求取字典$D$的过程.对于一组训练样本信号$X=\left[{{\pmb x}_{1}, {\pmb x}_{2}, \cdots, {\pmb x}_{N}} \right]$, 最优字典$D$是根据最小化表示误差$\left\| {X-DA} \right\|_F^2 $逐步迭代得到的, 因此训练字典$D$相比于分析字典将产生更好的稀疏表示效果.各种字典学习算法的主要区别在于字典更新方法上.

      MOD算法是根据信号样本$X$与稀疏编码阶段获得的稀疏系数矩阵$A$, 利用最小二乘法直接更新字典$D$:

      $$ \begin{align} D^{(t)}=\;& \arg \mathop {\min }\limits_D \left\| {X-D^{(t-1)}A^{(t)}} \right\|_F^2= \nonumber \\ & X(A^{(t)})^{\rm T}[A^{(t)}(A^{(t)})^{\rm T}]^{-1} \end{align} $$ (2)

      式中, $t$为迭代次数.若$\left\| {X-D^{(t-1)}A^{(t)}} \right\|_F^2 $足够小, 则迭代停止, $D=D^{(t)}$.由上式可以看出MOD算法在更新字典过程中每进行一次迭代就需要更新字典所有的列, 并进行大矩阵的乘法和求逆, 这将占用大量内存, 增加字典学习的计算复杂度.

      K-SVD算法在更新字典原子的同时也更新稀疏系数向量.其字典更新步骤如下:

      1) 先固定系数矩阵$A$与字典$D$中除待更新原子${\pmb d}_{k} $外的$K-1$个原子, 残差可表示为

      $$ \begin{align} \;&\left\| {X-D^{(t-1)}A^{(t)}} \right\|_F^2 = \left\|{X-\sum\limits_{j=1}^K {{\pmb d}_{j}^{(t-1)} {\pmb \alpha} _{rowj}^{(t)} } } \right\|_F^2 = \nonumber \\ &\qquad\left\| {(X-\sum\limits_{j\ne k} {{\pmb d}_j^{(t-1)}{\pmb \alpha} _{rowj}^{(t)} )-{\pmb d}_k^{(t-1)}{\pmb \alpha} _{rowk}^{(t)} } } \right\|_F^2 = \nonumber \\ &\qquad\left\| {E_k^{(t)} -{\pmb d}_k^{(t-1)} {\pmb \alpha} _{rowk}^{(t)} } \right\|_F^2 \end{align} $$ (3)

      式中, ${\pmb d}_j^{(t-1)} $为第$t-1$次迭代得到字典的第$j$列, ${\pmb \alpha} _{rowj}^{(t)} $为第$t$次迭代的稀疏矩阵第$j$行.由上式可以看出, 在K-SVD字典更新过程中$\sum\nolimits_{j\ne k} {{\pmb d}_j^{(t-1)}{\pmb \alpha} _{rowj}^{(t)} } $是固定的$K-1$项, ${\pmb d}_k^{(t-1)} {\pmb \alpha}_{rowk}^{(t)} $是待更新项, 则$E_k^{(t)} $就是除第$k$个待求解原子外的残差项.同MOD一样, 极小化式(3)就是寻找最佳${\pmb d}_k^{(t-1)} $和${\pmb \alpha}_{rowk}^{(t)} $来对$E_k^{(t)} $进行逼近.

      2) 为减少SVD分解过程中计算量, 将稀疏系数向量中非零原子所在列的标号$j$提取出来, 定义标号数组${\pmb \omega}_k=\left\{{j\left| {{\pmb \alpha} _{rowj}^{(t)} } \right.\left(j \right)\ne 0, 1\le j\le K} \right\}$; 再定义矩阵$\Omega $, 并令其元素$({\pmb \omega}_k (j), j)$为1, 其他位置元素为0.进而, 获得$X^\ast =X\omega$、$E_k^{(t)\ast}=E_k^{(t)}\omega $、${\pmb \alpha_rowk}^{(t)\ast}={\pmb \alpha} _{rowk}^{(t)} \omega $, 完成去零收缩.

      3) 对$E_k^{(t)\ast} $进行SVD分解: $E_k^{(t)\ast} =USV^{\rm T}$, 且$U$、$V$为正交矩阵, $S$为对角矩阵, 其元素非负且降序排列.将$U$的第一列作为更新后的原子${\pmb d}_k^{(t+1)}$, 矩阵$S$的$S(1, 1)$乘以$V$的第一列作为更新后的稀疏行向量${\pmb\alpha} _{rowk}^{(t+1)}$.从K-SVD更新过程可以看出, 字典是逐列更新的, 字典原子更新的同时稀疏系数向量又更新了一次, 虽然较MOD算法字典更新阶段避免了大矩阵求逆, 但总体算法时间复杂度依旧比较大, 消耗时间较多.

      在字典更新步骤中K-SVD算法会破坏稀疏系数的结构, MOD虽然不会破坏稀疏系数的结构, 但原子更新不是顺序更新的且计算复杂度更高[11].针对这些问题, Sahoo等提出了SGK (Sequential generalization of k-means)算法[12-13], 该算法具有不破坏稀疏系数结构的优点, 不仅能够逐列更新原子, 而且算法复杂度比K-SVD更低[11].类似于K-mean算法, SGK和K-SVD都是通过迭代来训练字典的, 通过稀疏编码(对${\pmb \alpha}$)和字典更新(对${\pmb d}$)的交替重复直到收敛, 不同之处在于字典更新部分.

      SGK算法的字典更新阶段沿用K-SVD算法中固定$K-1$项$\sum\nolimits_{j\ne k} {{\pmb d}_j^{(t-1)}{\pmb \alpha} _{rowj}^{(t)} } $, 剩下的一项${\pmb d}_k^{(t-1)} {\pmb \alpha} _{rowk}^{(t)} $为待求解项, 残差依旧可以写成式(3).虽然MOD能适合所有稀疏表示的应用, 在稀疏系数和字典上不计约束, 但它需要更多的计算资源去处理.相对的, 像K-SVD和K-means这样的顺序算法可以只需较少的资源就可以完成字典更新.因此Sahoo等对K-SVD中的模型${{\pmb d}_k^{(t)}, {\pmb \alpha} _{rowk}^{(t)}} =\arg \mathop {\min }\nolimits_{{\pmb d}_k, {\pmb \alpha} _{rowk} } \left\| {E_k^{(t)} -{\pmb d}_{_k }^{(t-1)}{\pmb \alpha} _{_{rowk} }^{(t)} } \right\|_F^2 $进行修改.如果保持${\pmb \alpha} _{rowk}^{(t)} $不变或者说字典更新这一步中不同时更新稀疏系数, 将不会有稀疏性损失和结构损失, 因此提出连续字典更新模型:

      $$ \begin{equation} {\pmb d}_k^{(t)} =\arg \mathop {\min }\limits_{{\pmb d}_k } \left\| {E_k^{(t)} -{\pmb d}_k^{(t-1)} {\pmb \alpha} _{rowk}^{(t)} } \right\|_F^2 \end{equation} $$ (4)

      通过与解MOD算法中模型如式(2)相同的方法(最小二乘法), 求解式(4)得:

      $$ \begin{equation} {\pmb d}_k^{(t)} =E_k^{(t)} ({\pmb \alpha} _{rowk}^{(t)})^{\rm T} \left[ {{\pmb \alpha} _{rowk}^{(t)} ({\pmb \alpha} _{rowk}^{(t)}{\rm {T}})} \right]^{-1} \end{equation} $$ (5)

      通过在更新序列中连续用${\pmb d}_k^{(t)} $代替${\pmb d}_k^{(t-1)}$, 这个过程依次重复所有字典原子, 类似K-SVD和K-means.但SGK算法仅通过单列字典的顺序更新, 运算次数依然较多, 时间消耗较大.

    • 本文从参与更新的字典原子列数入手, 将SGK算法中的残差项变形为多列原子同时更新, 减少了单次迭代的计算量, 进一步提高了字典学习效率.算法本身依旧包含两大主要部分, 即稀疏编码和字典更新, 具体算法流程如下.

      程序:初始化$t=0$, 选定初始字典$D^{(0)}\in {\bf {R}}^{n\times K}$.

      1) 稀疏编码阶段:对$X=\left[{{\pmb x}_{1}, {\pmb x}_{2}, \cdots, {\pmb x}_{N}} \right]\in {\bf{R}}^{n\times N}$稀疏编码得到稀疏矩阵$A^{(t)}$

      $$ \begin{equation} \forall _i , {\pmb \alpha} _i^{(t)} =\arg \mathop {\min }\limits_{{\pmb \alpha} _i } \left\| {\left. {{\pmb \alpha} _i } \right\|} \right._0 ; \left\| {{\pmb x}_i -D^{(t-1)}{\pmb \alpha} _i } \right\|_2^2 \le \xi \end{equation} $$ (6)

      其中, $\xi $表示容许误差, $A^{(t)}=\left[{{\pmb \alpha}_{1}, {\pmb \alpha}_{2}, \cdots, {\pmb \alpha}_{N} } \right]\in {\bf{R}}^{K\times N}$, ${\pmb \alpha}_{i}$在这里指的是矩阵$A^{(t)}$的列.

      2) 字典更新阶段:用稀疏编码所获得的稀疏矩阵$A^{(t)}$更新字典$D^{\left({t-1} \right)}$

      $$ \begin{equation} D^{\left( t \right)}=\arg \mathop {\min }\limits_D \left\| {X-D^{(t-1)}A^{(t)}} \right\|_F^2 \end{equation} $$ (7)

      并令迭代次数$t=t+1$.

      初始化字典选用DCT字典, 稀疏编码方法采用OMP算法, 由于自然信号的稀疏性未知, 所以必须使用一个基于约束最小化的表示误差$\xi$.

      字典更新阶段不同于K-SVD和SGK算法中单列原子更新, 而是$r$个原子同时更新.根据不同原子列数在稀疏分解过程中的迭代收敛次数、时间消耗与重构图像的质量, 确定最佳的字典更新的列数$r$.则残差可以写成式(8):

      $$ \begin{align} \;&\left\| {X-D^{(t-1)}A^{(t)}} \right\|_F^2 = \left\|{X-\sum\limits_{j=1}^K {{\pmb d}_{j}^{(t-1)} {\pmb \alpha} _{rowj}^{(t)} } } \right\|_F^2 = \nonumber \\ &\qquad \left\| {E_r^{(t)} -D_r^{(t-1)} A_{rowr}^{(t)} } \right\|_F^2 \end{align} $$ (8)

      其中, $E_r^{(t)}=X-\sum\nolimits_{j\ne i+1, \cdots, i+r} {\pmb d}_j^{(t-1)} {\pmb \alpha} _{rowj}^{(t)} $, 而$D_r^{(t-1)} A_{rowr}^{(t)}={\pmb d}_{i+1}^{(t-1)} {\pmb \alpha} _{rowi}^{(t)}, \cdots +{\pmb d}_{i+r}^{(t-1)} {\pmb \alpha} _{rowi+r}^{(t)} $.

      $D_r^{(t-1)}$为第$t-1$次迭代字典$D^{(t-1)}$的第$i+1$到$i+r$列(或者说原子), $A_{rowr}^{(t)}$为第$t$次迭代稀疏矩阵$A^{(t)}$的第$i+1$到$i+r$行, $E_r^{(t)}$为除了第$i+1$到$i+r$个待求解原子外的残差项.式中固定$K-r$项$\sum\nolimits_{j\ne i, \cdots, i+r} {{\pmb d}_j^{(t-1)} {\pmb \alpha} _{rowj}^{(t)} } $, 剩下的$r$项${\pmb d}_j^{(t-1)} {\pmb \alpha} _{rowj}^{(t)} +\cdots +{\pmb d}_{j+r}^{(t-1)} {\pmb \alpha} _{rowj+r}^{(t)} $是待求解的(${\pmb d}_j^{(t-1)} $为第$t-1$次迭代得到字典的第$j$列, ${\pmb \alpha} _{rowj}^{(t)} $为第$t$次迭代的稀疏矩阵第$j$行).同样的, 在字典更新之前需要对信号$X$、残差项$E_r^{(t)}$和稀疏矩阵$A_{rowr}^{(t)}$进行去零收缩, 其方法可参见K-SVD [7]算法的去零收缩, 与以往不同的是本文改进算法是索引$r$行稀疏系数中非零元素所在列, 继而得到$X^\ast=X\Omega$、$E_r^{(t)\ast}=E_r^{(t)}\Omega$、$A_{rown}^{(t)\ast}=A_{rowr}^{(t)}\Omega$减少了矩阵运算计算量.

      与解MOD算法模型中相同的方法即最小二乘法, 并结合式(8)得到代价函数的解为:

      $$ \begin{align} D_r^{(t)} =\, &\arg \mathop{\min}\limits_{D_r}\left\|{E_r^{(t)\ast}-D_r^{(t-1)} A _{rowr}^{(t)\ast}} \right\|_F^2 = \nonumber \\ &E^{\ast_r^{(t)}}A_{rowr}^{(t)\ast{\rm T}}(A_{rowr}^{(t)\ast} A_{rowr}^{(t)\ast{\rm T}})^{-1} \end{align} $$ (9)

      其中, $A _{rowr}^{(t)\ast} A _{rowr}^{(t)\ast{\rm T}}$为$r\times r$的方阵, $A _{rowr}^{(t\ast)} $必须满足行满秩, 否则$A _{rowr}^{(t)\ast} A _{rowr}^{(t)\ast{\rm T}}$不可逆, $r$为一次性更新的原子个数.其证明如下:

      证明.因为矩阵的F-范数为矩阵全部元素平方和的平方根, 所以对于残差$\left\| {E _r^{(t)\ast} -D_r^{(t-1)} A _{rowr}^{(t)\ast}} \right\|_F^2 $可以获得如下变形:

      $$ \begin{align} & \left\| {E _r^{(t)\ast} -D_r^{(t-1)} A _{rowr}^{(t)^\ast}} \right\|_F^2= \nonumber \\ &\qquad(E _r^{(t)\ast} -D_r^{(t-1)} A_{rowr}^{(t)}\ast{\rm T}) (E_r^{(t)\ast}-\nonumber \\ &\qquad D_r^{(t-1)} A _{rowr}^{(t)\ast}) = (E_r^{(t)\ast{\rm T}}-A_{rowr}^{(t) \ast{\rm T}}D_r^{{(t-1)}{\rm T}})\times\nonumber \\ &\qquad(E_r^{(t) \ast}-D_r^{(t-1)} A _{rowr}^{(t)\ast}) = \nonumber \\ &\qquad E _r^{(t)\ast\rm T}E_r^{(t)\ast} -E_r^{(t)\ast{\rm T}}D_r^{(t-1)} A_{rowr}^{(t)\ast} -\nonumber \\ &\qquad A_{rowr}^{(t)\ast{\rm T}} D_r^{(t-1){\rm T}}E _r^{(t)\ast}+ \nonumber \\ &\qquad(A_{rowr}^{(t)\ast{\rm T}}D_r^{(t-1){\rm T}})(D_r^{(t-1)}A_{rowr}^{(t)\ast}) \end{align} $$ (10)

      求$D_r^{(t)} =\arg \mathop {\min }\nolimits_{D_r } \left\| {E _r^{(t)\ast} -D_r^{(t-1)} A _{rowr}^{(t)\ast} } \right\|_F^2 $, 即求残差的极小值问题, 其等价于求残差对变量$D_r^{(t-1)} $导数为0的情况.式(10)中, $E _r^{(t)\ast {\rm T}}E _r^{(t)\ast }$因为不含$D_r^{(t-1)} $求导为零, $(E _r^{(t)\ast} {\rm T})D_r^{(t-1)} A _{rowr}^{(t)\ast} $和$(A _{rowr}^{(t)\ast){\rm T}}(D_r^{(t-1)})^{\rm T}E _r^{(t)\ast} $对$D_r^{(t-1)} $求导都为$E_r^{(t)\ast} A _{rowr}^{(t)\ast} $, $[(A _{rowr}^{(t)\ast})^{\rm T}(D_r^{(t-1)})^{\rm T}](D_r^{(t-1)} A _{rowr}^{(t)\ast})$对$D_r^{(t-1)} $求导为$2D_r^{(t-1)} A _{rowr}^{(t)\ast} A _{rowr}^{(t)\ast{\rm T}}$, 因此将式(10)进行求导得:

      $$ \begin{align} \;& \frac{\partial \left\| {E _r^{{(t)}\ast} -D_r^{(t-1)} A_{rowr}^{{(t)}\ast} } \right\|_F^2}{\partial D_r^{(t-1)}}= \nonumber \\ & \qquad -E_r^{ {(t)}\ast} A_{rowr}^{ {(t)}\ast} -E_r^{ {(t)}\ast} A_{rowr}^{{(t)}\ast} + \nonumber \\ & \qquad 2D_r^{(t-1)} A_{rowr}^{ {(t)}\ast} (A_{rowr}^{ {(t)}\ast})^{\rm T} =0 \end{align} $$ (11)

      将等式(11)等价变形为:

      $$ \begin{align} &2E_r^{ {(t)}\ast} A_{rowr}^{ {(t)}\ast} =2D_r^{(t)} A_{rowr}^{ {(t)}\ast} (A_{rowr}^{ {(t)}\ast})^{\rm T} \Leftrightarrow \nonumber \\& \qquad E_r^{{(t)}\ast} A_{rowr}^{{(t)}\ast} =D_r^{(t)} A_{rowr}^{ {(t)}\ast} (A_{rowr}^{{(t)}\ast})^{\rm T} \Leftrightarrow \nonumber \\& \qquad D_r^{(t)} =E_r^{\ast {(t)}} A_{rowr}^{ {(t)}\ast} [A_{rowr}^{ {(t)}\ast} (A_{rowr}^{{(t)}\ast })^{\rm T}]^{-1} \end{align} $$ (12)

      即证式(9).

      用$D_r^{(t)} $代替$D^{(t-1)}$中的$i+1$到$i+r$列, 依次重复所有$D^{(t-1)}$中的原子, 完成一次字典更新.同K-SVD和SGK算法一样, 本文算法也是通过稀疏编码(对$A$)和字典更新(对$D$)交替重复迭代, 直致达到预定迭代次数或误差要求才结束.本文算法不仅不会破坏稀疏系数的结构, 而且在顺序更新字典原子的同时大大提高字典学习速度, 多原子同时更新, 减少了单字典原子更新时重复多次迭代的计算时间复杂度.算法流程图如图 1.

      图  1  本文字典学习算法流程图

      Figure 1.  The flow chart of the dictionary learning algorithm in this paper

      改进算法具体运算步骤如下:

      1) 对迭代停止条件、同时更新的字典列数等参数设定.字典的初始化, 选择DCT字典为初始字典;

      2) 稀疏编码阶段利用OMP算法求得稀疏系数矩阵;

      3) 利用本文算法进行字典更新;

      4) 重复步骤2)、步骤3), 直到满足迭代停止条件;

      5) 完成字典训练, 获得字典$D$.

    • 本文的所有数据实验均在MATLAB R2014a进行编程运行, 试验用计算机配置为:处理器为主频3.3 GHz的AMD FX8300、8 GB内存, 操作系统为Windows 7 64位.为验证压缩测量后保存图像信息的完整性, 本文将测量后的信号进行重构, 重构图像质量的好坏代表了获得字典质量的优劣.原始图像大小为$256\times 256$, 字典大小为$64\times 256$, 当显示每个原子字典为图像时, 每个原子占据一个$8\times 8$像素的图像单元. OMP算法中重构信号允许表示误差为$\sigma \times C$, $C=1.15$, $\sigma $为加入高斯白噪声的标准差.稀疏字典是从噪声图像块自身训练出来的, 字典学习过程包含了对每块大小为$8\times 8$的噪声图像块的稀疏编码步骤.为了方便对图像重构效果直观地比较, 一般情况下取字典训练迭代次数为10次, 取学习字典的初始字典为DCT字典, 图像重构算法都采用OMP算法.实验内容主要包括: 1)本文算法性能及其参数分析, 包括待更新字典原子的选取方式和同时更新字典的列数; 2) K-SVD、SGK和本文算法结果对比验证, 包括不同噪声条件和不同迭代次数下各算法效果对比; 3)对不同来源图像情况下算法效果的稳定性比较.

    • 本文采用峰值信噪比PSNR (Peak signal to noise ratio)来衡量图像重构质量, 其定义为:

      $$ \begin{equation} MSE=\frac{1}{mn}\sum\limits_{i=0}^{m-1} {\sum\limits_{j=0}^{n-1} {\left\| {\hat {X}(i, j)-X(i, j)} \right\|} } ^2 \end{equation} $$ (13)
      $$ \begin{equation} {\rm PSNR}=20\cdot \lg \left(\frac{X_{\max } }{\sqrt {MSE} }\right) \end{equation} $$ (14)

      其中, $\hat {X}(i, j)$为重构图像, $X(i, j)$为原始图像, $X_{\max } $是表示图像点颜色的最大数值, 原图每个采样点用8位表示, 则$X_{\max } $取255, PSNR的单位为dB. PSNR值越大, 就代表失真越少, 重构效果就越好. PSNR是图像空间域统计特性评价方法, 可以提供和主观感知较为相统一的判断, 是一种性能良好的噪声失真评价标准; 而对于结构性失真, 由于其并未考虑人眼的视觉特性, 不能有效评判图像质量.

      结构相似度SSIM [14] (Structural similarity Index)是一种衡量两幅图像相似性的指标. SSIM计算了亮度、对比度和结构三部分的失真, 通过获得分块图像的失真度量, 最后求均值获得整幅图像的失真度.图像块结构相似度SSIM和平均结构相似度MSSIM定义如下:

      $$ \begin{equation} {\rm SSIM}({\pmb x}, \hat {{\pmb x}})=\frac{(2\mu _{\hat {{\pmb x}}} \mu _{\pmb x} +C_1)(2\delta _{{\pmb x}\hat {{\pmb x}}} +C_2)}{(\mu _{\hat {{\pmb x}}}^2 +\mu _{\pmb x}^2 +C_1)(\delta _{\hat {{\pmb x}}}^2 +\delta _{\pmb x}^2 +C_2)} \end{equation} $$ (15)
      $$ \begin{equation} {\rm MSSIM}(X, \hat {X})=\frac{1}{M}\sum\limits_{m=1}^M {SSIM} ({\pmb x}_m , \hat {\pmb x}_m) \end{equation} $$ (16)

      $\mu _{\pmb x} $、$\mu _{\hat {{\pmb x}}} $分别表示图像块${\pmb x}$和$\hat {{\pmb x}}$的均值, $\delta _{\pmb x} $、$\delta _{\hat {{\pmb x}}} $分别表示图像块${\pmb x}$和$\hat {{\pmb x}}$的方差, $\delta _{{\pmb x}\hat {{\pmb x}}} $表示其协方差, $C_1 $、$C_2 $为常数, $M$为一幅图像分块总数. MSSIM取值范围[0, 1], 值越大, 表示图像失真越小, 当两幅图像完全一样时值为1.

    • 文首先选取house图像为仿真实验用图像.图 2为原始图像和加入噪声图像对比图, 高斯白噪声标准差$\sigma $为25, 加噪后图像PSNR值为20.1875 dB.本文算法在字典更新过程中, 采用字典的$r$列原子同时更新, 但选取同时更新原子的次序对字典更新时间和重构图像效果有很大影响.用于更新的字典原子选取的方式有顺次选取连续的$r$列、随机选取连续的$r$列和随机选取离散的$r$列这3种方式.为方便比较以上三种字典原子选取方式暂时选取$r=2$列原子同时更新的情况.

      图  2  原始图像及其加噪图像

      Figure 2.  Original image and noisy image

      表 1可以看出选取待更新字典原子时, 用顺次选取连续$r$列方法的字典训练时间要明显短于随机选取连续$r$列和随机选取离散$r$列, 而且从重构图像质量上, 顺次选取连续$r$列方法的峰值信噪比和平均结构相似度也明显高于其他两种方式.因此, 本文算法在下面的实验中采用的字典原子选择方式都为顺序选取连续的$r$列的方式.

      表 1  不同字典原子选取方式效果对比

      Table 1.  Comparison of the effects for different selections of dictionary atoms

      选取待更新字典原子的方式 顺次选取连续的2列 随机选取连续的2列 随机选取离散的2列
      字典学习时间(s) 3.994 5.268 6.788
      峰值信噪比PSNR (dB) 32.092 31.968 31.866
      平均结构相似度MSSIM 0.3183 0.3152 0.3114

      为了不重复且完整地更新完字典所有的列, 同时更新字典原子列数必须可以被字典总列数整除, 由于字典原子个数为256, 所以一次更新原子数量可以为2、4、8、16等.当同时更新原子列数较少时, 虽然更新次数较多, 但在式(9)中求逆矩阵的计算复杂度较小; 在同时更新原子列数很大时, 求逆矩阵的计算复杂度变大, 但也同时减少了多次迭代的计算量.如表 2所示, 在同时更新字典原子个数不同的情况下, 从字典学习速度和重构图像质量考虑, 在保证重构图像质量基本不变的情况下同时更新8列或16列原子其字典学习时间具有明显优势.为了简单直观显示本文算法优势, 在下面的实验中将字典同时更新的原子数定为8列.

      表 2  同时更新不同字典列数效果对比

      Table 2.  Effect comparison of updating different numbers of dictionary columns at the same time

      同时更新原子列数 2 4 8 16 32 64
      字典学习时间(s) 4.117 4.194 3.630 3.744 4.032 4.093
      峰值信噪比PSNR (dB) 32.092 32.065 32.081 32.145 32.058 32.045
      平均结构相似度MSSIM 0.3183 0.3176 0.3177 0.3173 0.3164 0.3181
    • 本文采用DCT字典、K-SVD字典、SGK字典和本文方法进行仿真对比, 以house图像为例, 在加入标准差$\sigma$为25的高斯白噪声、字典迭代次数为10次、其他条件相同的情况下, 得到的重构效果对比如图 3.由图 3和与之对应的表 3可知用K-SVD字典、SGK字典与本文算法学习出的字典进行稀疏表示图像重构, 其图像质量相近, 且明显好于离散余弦字典.

      图  3  重构效果对比图

      Figure 3.  The reconstruction effect comparison

      表 3  不同算法的重构效果

      Table 3.  Reconstruction effect with different algorithms

      算法 DCT字典 K-SVD字典 SGK字典 本文算法字典
      字典学习时间(s) -- 20.079 4.254 3.605
      峰值信噪比PSNR (dB) 30.915 31.950 31.935 31.947
      平均结构相似度MSSIM 0.3022 0.3149 0.3137 0.3144

      在字典学习时间上, 分别通过10次完整的运算求运算时间平均值. SGK字典学习算法是K-SVD算法所用时间的21 %, 而本文算法是K-SVD算法所用时间的18 %, 相当于为SGK字典学习算法的85 %, 进一步提高了字典学习效率, 降低了字典学习的计算复杂度.

      在稀疏表示的过程中, 字典训练的效果随迭代次数的增加而不断提高, 但训练所消耗的时间也随之不断变长, 为探究训练随迭代次数增加字典更新的效果进行如下实验.图 4表 4实验以标准差$\sigma $为25的高斯白噪声house图像为实验对象, 字典迭代次数为3$\, \sim\, $21次.本文算法相对于K-SVD算法、SGK算法, 其运算速度有较明显的提高, 在迭代次数增加的情况下其字典训练时间差距不断变大如图 4所示.

      图  4  不同迭代次数下的字典学习时间

      Figure 4.  Time consumption of dictionary learning for different iteration times

      表 4  不同迭代次数重构图像质量

      Table 4.  The quality of the reconstructed image with different numbers of iteration

      迭代次数 K-SVD字典 SGK字典 本文算法字典
      PSNR (dB) MSSIM PSNR (dB) MSSIM PSNR (dB) MSSIM
      3 31.4559 0.30762 31.4459 0.30779 31.4603 0.30825
      6 31.9951 0.31384 31.9291 0.31171 31.9265 0.31207
      9 31.9704 0.31386 31.9490 0.31287 31.9194 0.31313
      12 32.2901 0.31418 32.2661 0.31423 32.2416 0.31279
      15 32.3571 0.31986 32.3297 0.31898 32.2724 0.31921
      18 32.4407 0.32208 32.3781 0.32182 32.3485 0.32141
      21 32.4489 0.32209 32.4040 0.32206 32.3971 0.32172

      对于在字典学习基础上的图像压缩重构算法, 字典更新迭代次数的增加使图像质量也随之提高.由表 4可以看出, 本文算法相比于K-SVD算法、SGK算法, 其图像重构效果十分接近.结合图 4, 在迭代次数不同的情况下可以得出本文算法相比于传统方法, 其重构图像质量相同且字典学习效率有了较明显提高.

      在现实场景中, 噪声的影响在机器人图像中是十分重要的因素, 用通过训练得到的字典来重构图像具有一定去噪效果. 图 5表 5实验以加入标准差$10\le \sigma \le70$高斯白噪声的house图像为研究对象, 在其他条件与之前相同情况下, 通过对不同程度噪声下各个字典学习算法的训练时间和图像重构效果进行比较验证本文算法的优势.

      图  5  不同噪声程度下的字典学习时间

      Figure 5.  Time consumption of dictionary learning for different noise levels

      表 5  不同噪声水平下重构图像质量

      Table 5.  The quality of the reconstructed image with different noise levels

      标准差 K-SVD字典 SGK字典 本文算法字典
      PSNR (dB) MSSIM PSNR (dB) MSSIM PSNR (dB) MSSIM
      10 35.9741 0.45381 35.9440 0.45390 35.9620 0.45430
      20 33.2254 0.34207 33.1664 0.34219 33.2006 0.34282
      30 31.3615 0.30139 31.2992 0.29996 31.3157 0.29984
      40 29.4226 0.26534 29.3889 0.26387 29.4074 0.26427
      50 28.0932 0.23598 28.0699 0.23470 28.0908 0.23485
      60 26.8134 0.20862 26.8110 0.20815 26.8230 0.20744
      70 25.6137 0.18573 25.6164 0.18493 25.6238 0.18591

      图 5可知, 随着加入噪声的标准差的变大, 字典训练时间在不断变短.当噪声标准差大于30后, 本文字典训练时间开始明显低于SGK算法.在$\sigma =50$时达到基本稳定, 此时本文算法完成10次迭代更新字典耗时2.679 s, K-SVD算法和SGK算法分别耗时17.996 s、3.607 s, 本文算法仅为K-SVD算法耗时的14.8 %和SGK算法的74.3 %, 降低了计算复杂度, 节省了字典更新的时间.

      表 5可以看出, 随着加入噪声的标准差的变大, 重构图像的质量也在变差, 但随噪声的增大, 本文算法重构图像质量略微优于其他两种方法, 也就是说仅从实验数据上看在较强噪声环境下, 用本文算法获得的字典重构图像的质量能够达到甚至优于K-SVD算法和SGK算法.

    • 为进一步验证本文改进算法对图像信号的稀疏分解效果, 将常用于图像处理的包含不同纹理的lena、peppers、barbara图像用于K-SVD字典、SGK字典与本文算法的字典训练和稀疏分解中, 实验中统一将其处理为$256\times 256$的图像, 本文算法中标准差取$\sigma =50$, 顺次连续选取同时更新的字典原子数为8列, 各个算法迭代次数都为10次, 其他参数保持不变, 比较其重构图像质量和完成字典学习所用时间如表 6所示.

      表 6  不同图像信号的重构效果

      Table 6.  Reconstruction effect of different image signals

      图像 算法 时间(s) MSSIM PSNR (dB)
      lena K-SVD 18.343162 0.27010 25.8505
      SGK 3.891636 0.26863 25.8154
      本文算法 3.102337 0.26916 25.8230
      peppers K-SVD 19.244135 0.35640 26.1407
      SGK 4.141303 0.35574 26.1445
      本文算法 3.092842 0.35545 26.1353
      barbara K-SVD 19.438234 0.35642 25.2067
      SGK 4.114145 0.35763 25.1997
      本文算法 3.197942 0.35774 25.2009

      表 6中数据为通过10次实验求得的平均值, 从表中可以看出, 本文算法能够有效降低字典训练的时间, 且图像的重构质量相比其他两种算法并无明显差距.在不同纹理复杂度图片情况下, 本文算法相比SGK算法, lena图像的字典训练时间减少了20.3 %, 平均结构相似度提高了0.00053, 图像峰值信噪比提高了0.0076 dB; peppers图像字典训练时间减少了25.3 %, 平均结构相似度下降了0.00029, 图像峰值信噪比下降了0.0092 dB; barbara图像字典训练时间下降了22.3 %, 平均结构相似度提高了0.00011, 图像峰值信噪比提高了0.00127 dB.仿真结果表明本文算法能够在图像质量变化很小的前提下, 有效缩短字典学习所耗费的时间, 降低字典学习过程的计算复杂度, 提高图像压缩感知的效率.

      由于机器人通常所在的环境和所处理的图像为自然场景或自然图像, 其复杂度高, 场景随机性大, 所以本文最后将处理的对象变成在不同环境中获得的场景图像, 并提前将其处理成尺寸为$256\times 256$的灰度图像应用于仿真实验.如图 6所示经过OMP算法重构获得三个对比场景图像重构效果对比图, (a)为明暗场景, (b)为不同视角场景图, (c)为模糊清晰场景图.对上述三种场景图像分别应用K-SVD、SGK和本文算法进行字典训练, 试验参数同lena等3张图片相同.

      图  6  自然场景图像重构效果对比

      Figure 6.  Comparison of image reconstruction effects in natural scenes

      图 6 (a)表 7中比较了在明暗两种情况下本文算法相对于其他两种算法的效果, 实验结果表明在图像变暗的情况下字典训练速度有所加快, 单从字典学习方法来说, 在图像质量变化较小的情况下(MSSIM差距不超过0.001, PSNR差距不超过0.02 dB)本文算法无论在哪种环境中本文字典学习速度都优于其他两种算法.由图 6 (b)表 7可以看出视角1字典训练速度比视角2快, 但在同一视角来说MSSIM差距不超过0.001、PSNR不超过0.02 dB, 本文算法字典训练耗时是K-SVD算法的15 %$\, \sim\, $20 %、是SGK算法的75 %$\, \sim\, $85 %. 图 6 (c)表 7表明在图像越不清楚的情况下字典学习速度越快, 其同一清晰度下本文算法与另两种算法重构图像的MSSIM差距不超过0.005、PSNR不超过0.01 dB, 字典学习速度明显提高, 耗时显著减少.

      表 7  不同场景自然图像信号的重构效果

      Table 7.  Reconstruction effect of image signals in different natural scenes

      图像 时间(s) MSSIM PSNR (dB)
      K-SVD SGK 本文算法 K-SVD SGK 本文算法 K-SVD SGK 本文算法
      (a)明 20.196063 4.470679 3.958860 0.35006 0.35036 0.35019 26.3382 26.3285 26.3339
      (a)暗 19.138866 4.303163 3.779787 0.25134 0.25155 0.25157 27.0640 27.0637 27.0611
      (b)视角1 19.294378 4.068634 3.263159 0.29148 0.29095 0.29066 25.9845 25.9772 29.9781
      (b)视角2 21.498433 4.167165 3.233882 0.30110 0.30121 0.30176 28.2839 28.2803 28.2971
      (c)清晰 20.856516 4.534554 4.031721 0.35926 0.35839 0.35854 26.0795 26.0734 26.0601
      (c)模糊 18.319955 3.874162 2.932584 0.41004 0.41013 0.40993 29.4348 29.4386 29.4385
    • 本文仅对字典更新阶段进行算法的复杂度分析, 比较了本文算法和SGK算法字典更新阶段所需要浮点运算次数.为了计算时间复杂度本文假设每个长度为$n$的信号可以用$m$个非零项稀疏表示, 且信号$X$中有$N$个这样的训练信号.为了更公平地比较, 我们讨论就参数$K$而言的所有变化.

      一般来说信号的维数$n={\rm O}(K)$, 训练样本的数量$N={\rm O}(K^{1+a})$, 其中$a\ge0$.对于获得最小复杂度条件可以通过对稀疏度$m={\rm O}(K^b)$推算得到, 稀疏系数向量中非零原子所在列的标号$j$提取出来, 定义标号数组${\pmb \omega}_k =\left\{ {j\left| {{\pmb \alpha} _{rowj}^{(t)} } \right.\left(j \right)\ne 0, 1\le j\le N} \right\}$, 再定义矩阵$\omega $, 并令其元素$({\pmb \omega}_k (j), j)$为1, 其他位置元素为0.更新完所有原子一次所需非零原子个数为$\sum\nolimits_K {\left| \omega \right|} =mN$.

      SGK算法是单列字典原子依次更新的, 其中$E_k^{(t)} =X-\sum\nolimits_{j\ne k} {{\pmb d}_j^{(t)} {\pmb \alpha} _{rowj}^{(t)} } $的求解需要$2nm\left| \omega \right|$次浮点运算, $E_k^{(t)} ({\pmb \alpha} _{rowk}^{(t)})^{\rm T}$需要$n(2\left| \omega \right|-1)$次运算, ${\pmb \alpha} _{rowk}^{(t)} ({\pmb \alpha} _{rowk}^{(t)})^{\rm T}$需要$2\left| \omega \right|-1$次运算, 求得的${\pmb \alpha} _{rowk}^{(t)} ({\pmb \alpha} _{rowk}^{(t)})^{\rm T}$为一个非负数值, 求其逆即求倒数运算$[{\pmb \alpha} _{rowk}^{(t)} ({\pmb \alpha} _{rowk}^{(t)})^{\rm T}]^{-1}$需要进行$n$次浮点运算.综上, 完成一列字典原子更新需要进行$2nm\left| \Omega \right|+2\left| \Omega \right|-1$次浮点运算, 那么完整更新一次字典的所有列需要的浮点运算次数为

      $$ \begin{align} T_{SGK} =\, &\sum\limits_K {2nm\left| \Omega \right|+2\left| \Omega\right|-1}=\nonumber\\ &2nm^2N+2mN-K \end{align} $$ (17)

      对于本文所提出的算法需要对多列字典原子同时更新.假设同时更新$r$列字典原子, $E_r^{(t)} =X-\sum\nolimits_{j\ne k\cdots k+r} {{\pmb d}_j^{(t)}{\pmb \alpha} _{rowj}^{(t)} } $需要$n\left| \Omega \right|(m-r)$次运算求和与$n\left| \Omega \right|(m-r)$次运算乘积, 总共也就是$2n\left| \Omega \right|(m-r)$次浮点运算; 对于$E_r^{(t)} (A_{rowr}^{(t)})^{\rm T}$需要$nr(\left| \Omega \right|-1)$次运算求和与$nr\left| \Omega \right|$次运算乘积, 总共也就是$2nr\left| \Omega \right|-nr$次浮点运算; $A_{rowr}^{(t)} (A_{rowr}^{(t)})^{\rm T}$需要$r^2(\left| \Omega \right|-1)$次运算求和与$r^2\left| \Omega \right|$次运算乘积, 总共也就是$2r^2\left| \Omega \right|-r^2$次浮点运算; 得到的$A_{rowr}^{(t)} (A_{rowr}^{(t)})^{\rm T}$是一个$r\times r$的正定矩阵, 求$[A_{rowr}^{(t)} (A_{rowr}^{(t)})^{\rm T} ]^{-1}$需要${r^3}/{2}-{r^2}/{2}$次求和、${r^3}/{2}+3{r^2}/{2}$次求积和$r$次运算来进行平方根计算, 即$r^3+r^2+r$次浮点运算.综上合计, 更新$r$列字典原子需要$(2mn+2r^2)\left| \Omega\right|-nr+r^3+r$次浮点运算, 则更新所有的字典列需要浮点运算次数为

      $$ \begin{align} T_r =\, &\sum\limits_{\frac{K}{r}} {(2mn+2r^2)\left| \Omega \right|-nr+r^3+r} =\nonumber\\ &\frac{2nm^2N}{r}+2mNr+K(1+r^2-n) \end{align} $$ (18)

      为更清楚比较本文算法和原始SGK算法在字典更新过程中的计算复杂度, 需要获得字典$D\in {\bf{R}}^{n\times K}$的具体尺寸$n=64$、$K=256$和稀疏系数行向量${\pmb \alpha} _{rowk}^{(t)} \in {\bf{R}}^N$维数或训练信号集$X=\left\{ {{\pmb x}_1, \cdots, {\pmb x}_N } \right\}\in {\bf{R}}^{n\times N}$中信号的个数$N=62\, 001$, 稀疏度水平$m$的选择本文取$m=1$.若本文算法能减小计算复杂度则${T}_\Delta ={ T}_r -{T}_{SGK} <0$.

      $$ \begin{align} {T}_\Delta =\, &2nm^2N\left(\frac{1}{r}-1\right)+\nonumber\\ & 2mN(r-1)+K(2+r^2-n) =\nonumber\\ &\frac{7\, 936\, 128}{r}+124\, 002r+256r^2-8\, 044\, 258 \end{align} $$ (19)

      其中, $r=2, 4, 8, 16, \cdots, 256$.对${T}_\Delta $求最小值得$ T_{\Delta \min } =-6.0441\times 10^6$, $r_{\min } =7.873$.因此, 同时更新字典列数$r=8$列时计算复杂度最低, 约减少600万次浮点运算.选取不同参数情况下结果有所不同, 但${ T}_\Delta <0$证明了通过本文算法确实能降低字典更新阶段计算复杂度.

    • 对机器人图像压缩采样过程中数据计算量大、计算时间长的问题, 引入压缩感知算法, 改进了原始学习字典稀疏表示计算时间复杂度大、耗时长的缺点.改进的算法是对SGK算法效率的进一步提高, 从参与更新的字典原子列数入手, 将残差项变形为多列原子同时更新, 进而利用最小二乘法连续地更新字典中的多个原子, 减少了单次迭代的计算量, 提高了字典学习效率.通过学习获得的冗余字典具有更好的重建图像的能力, 字典中原子与待重建图像具有相关性, 能更有效表达图像局部结构特点, 使得信号在字典上有更稀疏的表示.利用不同情况下获得的图像, 在相同计算参数下, 本文算法相比于原SGK字典学习算法, 压缩采样后保存了基本相同的信息量, 基于各自冗余字典重构的图像质量近似相同, 且字典学习计算速度提高明显, 相比于主流的K-SVD算法更大大提高了字典的学习效率.

参考文献 (14)

目录

    /

    返回文章
    返回