当前位置： >>
基于过完备字典稀疏表示的图像超分辨率研究
计算机光盘软件与应用IT 工程技术 Computer CD Software and Applications 2013 年第 03 期基于过完备字典稀疏表示的图像超分辨率研究刘骅，徐义奎，杜晶，凌佳俊 （宁波大学 信息科学与工程学院，浙江宁波 315211）摘 要：提出一种基于过完备字典稀疏表示的通用图像超分辨率算法。利用过完备字典代替稀疏基，采用学习的方 法得到低分辨率图像和高分辨率图像之间的关系，最终从高分辨率图像块的字典中重构出超分辨率图像。实现了基于 matlab 的稀疏表示(omp 算法)和字典更新(K-SVD 算法)的字典学习算法，并通过仿真实验，以 PSNR 等指标论证了编码算 法的有效性。 关键词：超分辨率；稀疏表示；字典学习 中图分类号：TP391.41 文献标识码：A 文章编号： (6-021 引言现在是信息社会，我们获取的信息当中，多为图像信 息。由于受成像系统硬件的限制和拍摄过程中环境因素的 影响，获取的模糊图像无法满足进一步的需求。超分辨率 技术，自提出以来，即得到广泛应用。其中基于学习的方 法对噪声有很好的鲁棒性，相较于插值带来的棋盘现象和 重建模型的诸多限制， 它更加重视对图像内容结构的理解。 Chang 等在假设 LR 和 HR 图像块的局部流形相似的前提 下，得到对应的 HR 图像块，大大降低了训练集的数目， 但容易产生欠拟合或过拟合现象。Yang[1]等则利用线性规 划， 实现 LR 图像块的稀疏表示， 再用 HR 图像块进行线性 组合，进而得到 HR 图像。但计算复杂。 本文研究基于过完备字典的图像稀疏表示理论， 实现了 图像的超分辨率：从给定的高低分辨率图像数据库中，采集 图像块构成低分辨率和高分辨率字典对，并利用 omp 算法 求解测试图像块在低分辨率字典（Dl）中的稀疏系数α，同 时利用 K-SVD 算法逐步实现字典更新和稀疏优化，然后用 α从高分辨率字典（Dh）中重构出所需要的高分辨率图像。min ? 0 s.t. ? ? D? ? ?（4）其中ξ为一正的常数，当ξ=0 时，有最优的稀疏解。 但由于 L0 范数求解问题的非凸性，上式的求解变成了一个 NP 难问题。稀疏分解算法中，凸优化算法，用 L1 范数代 替 L0 范数，用线性规划来求解，精度高，计算复杂。相对 来说，贪婪算法原理简单，易于理解，且计算复杂度较低， 包括 MP（匹配追踪） 、OMP（正交匹配追踪） 、BP（基追 踪）等。3 实验主要算法描述相较 MP 算法，OMP 算法要对原子进行正交化处理， 因此 OMP 的算法收敛速度更快[2]。R fm2?R m f , ?m2?m2? R m ?1 f2（5）2 算法基本原理? y ? P * x, Dl ? P * Dh; ? ? y ? Dl *? , x ? Dh *? ;（1）x 表示高分辨率图像块， y 表示与其对应的低分辨率图 像块，P 表示下采样矩阵。Dh、Dl 表示高低分辨率字典， L 行 N 列，L 为信号长度，N 为原子列的个数，当 N≥L 时，字典冗余。y 在 Dl 上的分解表示如下：M可见，随着迭代次数的增加，残差项会越来越小。 K-SVD 算法很灵活，可以和任何追踪方法一起工作 （e.g，基追踪，匹配追踪，正交匹配追踪等） ； 通过 K-SVD 算法训练好的字典可用于信号/图像压缩，去噪等。K-SVD 算法可以实现字典原子的自适应更新。 K-SVD 算法结合过完备字典的构建和优化，以待分解的 图像来训练原子库，从而使其更加有效的反应图像的各种特 征。本文中用到的字典对，其中包含的 1024 个原子，是由 100000 幅高、低分辨率图像块对训练而成的。这些图像块对 又是从与被处理图像不相关的图像库中随机采样得到的。4 数值试验A.输入图像 （2）（ ）y ? ? ? ? d? ? R (M )? ?1B.双线性插值α={αγ，1≤γ≤L}，为 y 在 Dl 下的分解系数，R M 是 经过 M 项逼近后的残差项。 关于稀疏系数的求解问题，我们可以采用 L0 范数：Lmin ? 0 s.t.? ? ? ? ? d ?? ?1（3） C.Yang 算法 D.本文算法 图 1 lena 图像的超分辨率结果 （下转第 118 页）― 116 ―式中?0是 ? 的 L0 范数，表示非零元素的个数。计算机光盘软件与应用IT 工程技术 Computer CD Software and Applications 2013 年第 03 期其肯定会被新的计算机科学技术取代。在此我将一些正在 研究阶段的新型计算机技术作简要概括。 以 DNA 存储技术为依托的生物计算机。 生物计算机的以生物芯片取代传统半导体硅芯片，由 美国学者阿德勒曼最先提出。他根据 DNA 信息传递的启 发， 将 DNA 单链巧妙组合起来， 得到具有信息价值的 DNA 链。 阿曼德的成功迅速引起了世界各国科学家的广泛关注， 科学家们开始讨论以 DNA 为依托的生物计算机的可行性。 以色列科学家在 2001 年研制成功世界第一台 DNA 生 物计算机，尽管只有一滴水大小，它却是未来生物计算机 的雏形。就在 2013 年的 3 月，英国生物信息研究院的科学 家们将莎士比亚的 154 首十四行诗的 mp3 文件和相关数码 照片编入了 DNA 序列，储存密度达到了惊人的每克 2.2PB （1PB=1024TB） 。这条消息引爆了人们对信息存储概念的 认识大转变。 基于 DNA 的存储技术诞生以及得以实现， 坚 定了科学家研制生物计算机的信念。 生物计算机物无论是在原材料还是体积运算速度方 面，都是传统计算机无法比拟的。也许不久的将来，传统 计算机成为历史，生物计算机满街都是。 用光子做信息传递的光子计算机。 光子计算机使用光束代替电子来进行运算和存储，这 一点与传统硅芯片计算机有着本质不同，克服了传统计算 机的诸多缺点。与传统计算机相比，光子计算机存在以下 好处： （1）光是一种电磁波，因此不带电荷，我们知道，光 在自由空间中传播时可以相互交叉而彼此不发生干扰。 （2） 光子是没有质量的。它不受介质的干扰，可以在真空和各 种介质中传播，并且光子的速度是电子在导线中传播速度 的 1000 倍。可以预料，光子计算机的运算速度必将大大优 于传统计算机。 （3）用光子互联的计算机芯片的密度可以 达到很高。由于光子不像电子一样在高密度下受到量子效 应的干扰，因此用光子在自由空间进行互联，可以有效提 （上接第 116 页） A 为原图，B 为双线性插值（PSNR=32.79467dB） ，C 为 原 算 法 （ PSNR=33.98459dB ）， D 为 本 文 算 法 （PSNR=34.84137dB） 从客观评价体系来看，基于学习的结果要比基于插值 的结果优越，具有更好的峰值信噪比。主观评价体系，即 比较经不同方法处理的同一块区域， 得到的肩部图像来看， 本文算法得到的结果含有更丰富的纹理信息。高芯片集成密度。 但是想要研制出能实际使用的光子计算机，就必须先 开发出可用光束控制的“光学晶体管” 。现有的光学“晶体 管”庞大而笨拙， 因此在现有的技术条件下要想短期内使光 子计算机实用化还比较困难。 以量子理论为根基的量子计算机。 所谓量子计算机，就是在原子尺度上根据量子理论制 造出来的全新概念的计算机。其处理信息的基本数据单元 是量子比特，而不是传统的“0”和“1” 。量子比特和著名 的薛定谔猫一样没有确定的状态，可以同时处于两种状态 的叠加态。 使得其有着相比于传统比特流得天独厚的优势。 基于量子计算机超高的运算能力，目前世界各个国家 的科学家们都对量子计算机的研制给与了密切的关注。美 国和中国的科学家们已经在实验室里成功实现了对多个量 子比特的同时操作。这使得人类距制造量子计算机的梦想 又近了一步。 现在的量子计算机还是个实验室的理论模型，距离实 用以及大规模生产还有很长一段路要走。但是科学的发展 充满了不确定性。 在世界各国科学家们齐心协力的努力下， 相信在不久的将来，量子计算机的梦想会变成现实。 此外，根据哲学里的模糊思想，模糊计算机也将是计 算机科学技术未来的一个可能的发展方向。4 结语以史为镜，与时俱进，迎接未来。我们有理由相信， 在科学家们的不懈努力下，在各个学科的不断交融不断促 进下，在各种现代化技术的支撑下，计算机科学与技术的 未来必将充满无限希望。参考文献：[1]陈相吉.未来计算机与计算机技术的发展[J].法制与 社会,2009,10. [2]蔡芝蔚.计算机技术发展研究[J].电脑与电信,2008,2. [3]甘黛娴.计算机科学与技术的发展趋势探析[J],2012,6. 技术尴尬，也突破了固定设备的固有分辨率的限制，从而 最大限度地降低了技术成本，同时提高了图像的分辨率。参考文献：[1]Yang Jian chao, Wright J. Image Super―Resolution as Sparse Representation of Raw Image Patches[J].Proc of t he IEEE, Anchorage, USA,2008: l-8. [2]王建英,尹忠科,张春梅.信号与图像的稀疏分解与初 步应用[M].成都：西南交通大学出版社.2006:69. [3]Jianchao Yang， Student Member, IEEE, John Wrig ht, Member, IEEE Thomas Huang, Life Fellow， IEEE. Ima ge Super-Resolution via Sparse Representation[J].IEEE 图像 处理,): .5 结论与展望实验结果表明，本文算法实现的图像重构质量无论从 视觉效果还是参数指标上，都要优于插值等传统方法。图 像超分辨率技术不仅瓦解了进一步提高传感器像素密度的― 118 ―基于过完备字典稀疏表示的图像超分辨率研究作者： 作者单位： 刊名： 英文刊名： 年，卷(期)： 刘骅， 徐义奎， 杜晶， 凌佳俊 宁波大学 信息科学与工程学院,浙江宁波 315211 计算机光盘软件与应用 Computer CD Software and Applications 2013(3)本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjgprjyyy.aspx
基于稀疏表示的单帧图像超分辨重建算 法研究 杨学锋 设计(论文)题目: 指导教师...是稀疏编码阶 段的计算量较大,另一方面,得到一个具有广泛表示能力的过完备字典...和多尺度几何分析方法的图像稀疏表示,重点研究了基于过完备字典的图像稀疏 表示...其中包括识别、去噪、超 分辨率等,引起了同行的关注,并在国际上造成了一定的...由于稀疏表示 和过完备字典学习有利于减少运算量, 同时能够准确简洁地表示图像, 因而近期的研究热点 集中在了基于稀疏表示理论的过冗余字典学习的超分辨率重构方法 ...【关键词】超分辨率;图像重建;过完备稀疏表示 0 引言 超分辨率图像重建[1]是...1 基于插值的超分辨率方法 基于多帧图像插值技术的方法是超分辨率研究中最直观的...基于深度卷积网络的图像超分辨率摘要:提出一种深度...我们进一步证明传统基于稀疏编码的 SR 方法也可以被...这些研究 不同于如何学习一个紧凑的字典或多 个...本文主要研究观测是无噪 声的,模糊核是狄拉克δ ...基于 SRM 的超分辨率与压缩感知 (CS) 理论有着...Ψ 傅里叶词典可能不会导致对自然图像的稀疏表示。...稀疏表示的字典_文献翻译_计算机软件及应用_IT/计算机...有关通用过完备字典的研究主要开始于过去的十年中,...多分辨率:19 世纪 80 年代最重大的概念上的进展是...研究很快被从一维信号推广到二维信号图像的研究上。 ...是较早将稀疏表示理论应用于图像去噪与超分辨率 的...基于 k-svd 训练得到的过完备字典,取得了较好的...中北大学 2014 届毕业论文 毕业设计说明书基于稀疏表示的图像去噪算法研究 学生姓名: 系专别: 业: 指导教师: 朱祥 学号: 光电工程系 电子信息科学与...自训练过完备字典和稀疏表示的语音增强 作者:崔晓 ...迭代阈值; 字典训练; 语音增强 中图分类号: TN912...基于冗余字典的信号超完... 2286人阅读 6页 1下载...
All rights reserved Powered by
www.tceic.com
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。[转载]​稀疏表示介绍
已有 3387 次阅读
|个人分类:|系统分类:|文章来源:转载
&声明 之前虽然听过压缩感知和稀疏表示，实际上昨天才正式着手开始了解，纯属新手，如有错误，敬请指出，共同进步。主要学习资料是 Coursera 上 Duke 大学的公开课—— 第 9 课。由于对图像处理的了解也来自与该课程，没正经儿看过几本图像方面的书籍，有些术语只能用视频中的英文来表达，见谅哈！&1. Denoising 与 MAP故事从 denoising 说起，话说手头上有一张含有噪音的图片 Lena，如何除去噪音得到好的 clean image 呢？对于上面的问题，用 x 值表示某个像素的灰度值，我们可以建立这样一个最小化的数学模型：其中， y 表示已知的观测值，也就是含有噪声的原图， x 表示要恢复成 clean image 的未知值。模型的第一项的直观作用就是，预测值 x 不要离观测值 y 太远。数学上的解释是， x 的取值概率可以看做是以 y 为均值的高斯分布，即图像带有 Gaussian noise， 第二项是规则化项。由来如下：假设 x 本来是就带有某种先验概率的分布，现在又已知观测值 y， 根据贝叶斯原理， 现在 x 的分布（后验）正比于先验概率分布与高斯分布的乘积。如果先验概率分布也正是指数分布，将乘积取负对数，就可以得到上述在机器学习里非常常见的 MAP 模型。现在的问题是：最好的先验 (prior) 究竟是什么？ G(x) 应该取什么形式？ 定义图像信号的最好空间是什么？在学术界，这方面的工作已经做得非常多，对这个问题的探讨过程可以比喻成类人猿向人类进化的过程:第一张图， prior 假设 clean image 能量尽量小， x 要尽可能地小。第二张图， prior 认为恢复后的图像要光滑，于是产生了 Laplacian 和 low energy 的结合，朝前进化了一步。第三张图，prior 认为要考虑 edges 是不光滑滴，需要不同情况不同处理…… Sparse and Redundant 是正在讨论的问题，目前是最新的进化版本，而后面也有一些算法，虽然也成功进化成人类，可惜太胖了，行动不便—— computationally expensive and difficult。 Sparse modeling 的先验究竟是什么？要回答这个问题，还需要了解一些基础概念。&2. Sparsity and Lp NormHow to Represent Sparsity表示一个向量的稀疏程度可以用 Lp norm， 对于 alpha 向量的某一个元素为 x， Lp norm 的计算公式和函数图像如下：我们希望不管 x 多大，它非零的惩罚是相同的，L0 norm 正好满足这个要求，它表示的意思是数出 alpha 向量中非零的个数。Sparse Modeling of Signal一张 8×8 的图片，可以表示成 64 维的向量 x ，如何进行稀疏表示？下图中假设 N = 64：左边矩阵 D 是字典矩阵，由 K 个 N 维的列向量组成。 根据 K 与 N 的关系，又可以划分为：K & N: over-complete, 这种情况在稀疏表示里面最常见K = N: complete, 例如傅里叶变换和 DCT 变换都是这种情况K & N: under-complete&中间列向量 alpha 是一个稀疏向量，特点是非零项很少，图中只有三个非零项，代表 D 矩阵对应行向量的线性组合。最后 x 向量表示恢复后的向量。atoms 表示 D 的列向量实际上 DCT 变换也可以看做是一种稀疏表示，它的 D 向量是由固定的且刚好完备的正交基向量组成，并且 alpha 向量也具有一定稀疏性。对于上图，假设 D 矩阵 K & N，并且是满秩的，那么对于任意个 N 维的向量 b （图中是 x ），肯定有 Ax = b。现在加入 Lp norm 的约束条件，限制只能用少量的 A 的列向量 (atoms 作为基，向量 b 就被固定在某个 span 内，成为了一个 Lp 优化问题：用紫色表示平面，用青色表示 norm 取同一个值的球形(等高线)，问题如下：在平面 Ax = b 平面内选出 norm 最小的最优解当 p &= 1时，norm ball和平面的交点有多个。这是一个凸优化问题，可以用拉格朗日乘子来解决这个问题。当 0 & p & 1 时， norm ball 可行解十分稀疏，是一个非凸优化问题，解决这类问题很难，但是却有很好的稀疏性。当 p = 0 时， norm ball 上的点除了坐标轴，其他部分无限收缩，与平面的交点在某一个坐标轴上，非零系数只有一个。回到第一节将的 MAP 模型， Sparse Modeling 模型就是非零系数限制在 L 个之内（意味着解在至多 L 个 atoms 组成的 span 里），尽可能接近平面:这样，我们用少量的 atoms 组合成真实信号，而 noise cannot be fitted very well, 在投影到低维空间的过程中起到了降噪的作用。 &&3. Some Issues： 模型可以改成 L0 norm 的形式和其他形式来计算或者求近似吗？解集 alpha 向量是唯一的吗？我们可以求它的近似吗？如果可以，如何估计近似程度?应该采用什么样的字典矩阵 D 才能较好地消除噪声？字典 D 如何确定？&&&声明之前虽然听过压缩感知和稀疏表示，实际上昨天才正式着手开始了解，纯属新手，如有错误，敬请指出，共同进步。主要学习资料是 Coursera 上 Duke 大学的公开课—— 第 9 课。由于对图像处理的了解也来自与该课程，没正经儿看过几本图像方面的书籍，有些术语只能用视频中的英文来表达，见谅哈！&1. Uniqueness假设我们已知字典矩阵 D 和稀疏向量 a， 计算出一个信号 x，即 Da = x, x 存在一个关于 D 的稀疏表示。反过来现在已知前面的 D 和 x，根据 L0 的优化问题，可以归纳为： 的解是唯一的吗？显然不一定。比如， D 中某些 atoms 恰好相等，或者 column1 = column2 + column3, 以前由 column2 和 column3 现在只用 column1 表示即可。当然也有正面的例子，比如 DCT 变换, 基向量完全正交，解是唯一的。这与 D 中 atoms 的不相关性和数目 K 有关。&2. Sparse Coding和上面一样，现有字典 D 和带有噪声的信号 y，进行稀疏编码的问题可以表示的 L0 优化问题：这是一个组合优化问题。假设 alpha 的非零项数目为 L (sparse Level)， 先令 L = 1, 每一个列向量尝试一遍，看看是否又满足条件的，共有 K 种组合。如果没有，再令 L = 2, 再次尝试，共有 K(K-1)/2 中组合。还没有满足条件的，则令 L = 3......组合的数目呈指数增长，这是一个 NP-hard 的问题。 实际应用中的 K = 1000, L = 10, 要穷尽所有的排列组合大概需要计算几百万年，因此要采用近似算法, 目前主要有 relaxation methods 和 greedy methods。Relaxation Methods - the Basis Pursuit (BP)我们知道， L0 norm 可以数出向量中非零 entries 的数目，具有很好的现实意义，但是由于它数学特性（求导等）极差，非常不适合作为一个优化模型中目标函数。在线性分类器中，你可以把误分点的数目作为目标函数，但是没法优化，所以，我们看到的线性分类器的的目标函数一般是 L1 norm（感知器算法）， L2 norm（LMS 算法和最小二乘法）以及最大熵（Logistic Regresson）等，也能达到比较好的效果。在上一篇博客中，可以看到 L1 是菱形， L2 是球体，L1 具有更好的稀疏性(解更靠近坐标轴)，所以我们采用松弛方法将 L0 norm 转换为 L1 norm：虽然我们把 count number 变成了 count the magnitude， 但是在某些条件下，上式的解与松弛之前的解等价。上述方法也叫 BP，新定义的问题是一个凸优化问题，解决的方法很多，有 Interior Point methods, Sequential shrinkage for union of ortho-bases, Iterative shrinkage 等。&Greedy Methods - Matching Pursuit (MP)第一步，找到最接近(平行) y 的 atom， 等效与在 alpha 向量上仅取一个非零项，求出最接近的 atom， 保留下来第二步，计算误差是否满足要求，如果满足，算法停止，否则，计算出残差信号，和第一步类似，找到最接近残差向量的 atom， 保留下来第三步，调整已选向量的系数，使得 Da 最接近 y，重复第二步 (OMP, Orthogonal Matching Pursuit)总结一下解决这个问题的算法有：&3. Dictionary Learning - K-SVD字典学习的一个假设是——字典对于一张 good-behaved 的图像具有稀疏表示。因此，选择字典的原则就有能够稀疏地表达信号。有两种方法来设计字典，一种是从已知的变换基中选择，或者可以称为 beyond wavelet 变换，比如 DCT 实际上就是一个稀疏表示（高频部分系数趋向于 0），这种方法很通用，但是不能够 adapted to the signal。第二种方法是字典学习，即通过已有的大量图片数据进行训练和学习。比如，现在有 P 个信号（张图片）要进行稀疏表示，如何学习一个字典？上式字典矩阵 D 和 alpha 组成的稀疏表示 A 矩阵都是可变量，目前有几种算法解决这个问题，下面介绍 K-SVD 算法（K-Means的一种变种），idea 非常简单。假设现在有原始信号矩阵 X^T, 该矩阵的每一行表示一个信号或者一张图片， D 矩阵是字典矩阵，右下方是 sparse coding 矩阵，红色的点表示非零项：算法步骤如下：&Step 1: Initialize。在 X^T 矩阵中随机挑选一些行向量(一些原图），填满矩阵 D。（ K-means 随机选点初始化) Step 2: Sparse Coding. 用上一小节的方法（松弛或者贪婪法）进行稀疏编码，Row-by-Row 计算出稀疏矩阵。Step 3: Dictionary Update. 字典以列向量为基，自然要 Column-by-Column 地更新字典。比如现在更新某一列, 下方对应的红点，根据红点找到对应的信号（图像），然后除掉其他不相关的图像，得到示意图如下：上图中字典的 atom 对四张图片都有贡献，我们调整 atom 的目的是使得这个贡献更大，从而使稀疏性表示效果更好。当然，一个 atom 只能表示一条直线，三张图片的信号极有可能不在这条直线上，我们要做的是将中间的误差降到最小，这其实就是一个最小二乘（MSE）的问题。具体做法是将最右下角的矩阵进行 SVD 分解(SVD 相关知识可参考之前我写的)，找出主成分，然后回到 Step2, 迭代。 &声明之前虽然听过压缩感知和稀疏表示，实际上前两天才正式着手开始了解，纯属新手，如有错误，敬请指出，共同进步。主要学习资料是 Coursera 上 Duke 大学的公开课—— 第 9 课。由于对图像处理的了解也来自与该课程，没正经儿看过几本图像方面的书籍，有些术语只能用视频中的英文来表达，见谅哈！&1. From Local to Global Treatment图片尺寸有大有小，在 DCT 变换中，我们一般取 8×8 的方块作为一组 64 维的变换信号，在稀疏表示中，我们同样也不能把整张图片作为 X^T 矩阵，而是在大图片中取一定尺寸的 patch (假设是 8×8 的方块)作为一个 signal。对于图片中的所有的 patch (假设 ij 是 patch 的左上角坐标)组成的信号，已知字典 D 和噪声图片 y ，估计公式如下：y: 带有噪音的图片—— the whole imagex: 要恢复的 clear imageRij x: 以 i，j 为左上角坐标的 patch， Rij 是从 x 中提取 patch 的 0-1 矩阵D： 字典 for all the overlapping patches字典 D 从哪里学习？第一种选择是基于图片的数据库，第二种是直接使用要降噪的图片进行训练。还有一种可能性是：首先基于图片的数据库得到字典 D (off-line)，接着来了一张要降噪的图片，我们的做法是新建一个以 D 为初始化的字典，在要处理的图片上再进行迭代(on-line)，得到新字典，这个新字典更适合降噪，代价是多一些计算。&2. K-SVD Image Denoising在上一小节中，我们提出的可能性是 D 也需要根据要降噪的图片进行再适应，所以，图片降噪的公式多了一参数：有三个变量，处理方法是先固定其中两个，优化一个，然后迭代。从整体上来说，先用 K-SVD 算法得到字典矩阵 D 和系数编码 alpha，保持它们不动，再优化 x：x 的最优解实际上就是所有包含 x 像素点的 patch 的平均值，比如 patch 的大小是 8×8， 那么包含图片中某一个像素点的 patch 就有 64 个，这个像素点最优解就是取这 64 个patch 对应位置的平均值。当然，你也可以用权重来调节不同位置的 patch 对 pixel 的影响，比如 pixel 在中间的 patch，权重大，pixel 在 patch 边边角角的地方，权重小。&3. Compressed Sensing前面我们探讨了 sparse represent 的等式，这里主要讲 compressed sensing 的概念，即在稀疏表示的等号两边同时乘以矩阵 Q：就变成了：用公式可以表达为：可以看到，变换后的信号被大大压缩了。在一直 x波浪 和 D波浪 的情况下求 alpha 这个问题和前面 sparse coding 非常类似。一个关键问题是：在什么条件下由已知信号 x波浪 的情况下恢复稀疏表示 alpha？显然，这个问题与矩阵 Q，字典 D 和 alpha 的 sparse level 有关，背后涉及很多数学理论。&4. Structured Sparse Models and GMM待续...&5. Sparse Modeling and Classification-Activity Recognition 待续...作者：daniel-D 出处：http://www.cnblogs.com/daniel-D/ 欢迎转载或分享，但请务必声明文章出处。&参考资料：[1]: 第 9 课[2] &作者：daniel-D 出处：http://www.cnblogs.com/daniel-D/ 欢迎转载或分享，但请务必声明文章出处。
转载本文请联系原作者获取授权，同时请注明本文来自王海罗科学网博客。链接地址：
上一篇：下一篇：
当前推荐数：0
推荐到博客首页
评论 ( 个评论)
扫一扫，分享此博文
作者的其他最新博文
热门博文导读
Powered by
Copyright &[转载]高维数据稀疏表示-什么是字典学习（过完备词典）
高维数据稀疏表示-什么是字典学习（过完备词典）
稀疏表示理论背景
稀疏表示的由来
稀疏表示理论最早是在研究信号处理应用中发展起来得。其基础是多尺度分析理论，在此基础上拓展，形成了相应的理论框架。主要是通过少数的稀疏稀疏来逼近原信号。近年来，稀疏表示的方法主要应用于信号处理和图像处理方面。
啥是高维数据
这里，信号和图像都可以看成是一个数据对象在所有维度上的信号，本文统称为“数据对象”。因此，不难看出，这种数据对象必然是一个高维的。何为高维？举个栗子：比如对一个10个人的薪酬表的描述。表的行是这10个人；列是这是个人的属性，比如姓名、生日、职位、基本工资、工作年限等一共20个属性。那么这个表就是一个10*20的表。每个人即一个数据对象，是20维的。那么问题来了，比如一个人脸的图像（简化一下，不是自拍照，是一寸照。再简化一下，比如这个图像要求的清晰度不高，只要32*32像素的）。那么可以理解成这个图像有32*32个点，每个点有一个表示颜色的数值（再进一步简化，这是黑白照片，每个点的数值表示的是这个点的深浅程度）。那么这个照片就有32*32=1024个点。如果我们有这要的照片100张，每张照片都有1024个表示颜色深浅的数据，那么就得到了一个100*1024的表。这明显是高维了。而真正的图像中，不可能是32*32的吧（难道都是小霸王里的超级玛丽？），要再是彩色的，俺的苍天啊，这个维度就更高了，高到我不想举例子了。在实际工作的研究领域，一般20维以上即可以算作是高维数据了。
高维数据的特点
维灾：这个名字太贴切了，维度增加带来的灾难。这个概念是一个叫Bellman的大叔在1962年提出来的（好像不是大叔，大爷都不止了）。意思是对于一个多变量的函数，随着维数的增加（变量的增加），这样高维数据问题往往转化成为了一个多变量的优化求解问题。但由于维度太高了，传统的算法就不行了。比如，每个数据对象理解成一个点，我们一般用k近邻的概念时要找到距离这个点最近的k个点。但是在高维空间中，最近的点和最远的点的距离随维度增加而减小，换句话说，维度增加让远点和近点的差异减小，趋近于零。所以单纯用传统办法解决高维问题，没戏了。（这里的例子实际上是高维聚类问题）
未标记（UNlabeled）：所谓标记，就是上面薪酬例子里的，姓名，年龄，这些东西，可以理解成为属性（即维度）的名字。但是现在这个社会，得到的大量数据往往是未标记的。比如，一个电子商务系统中，大量不同商品评论的情感分析，如果去手动标注情感倾向（比如积极的、消极的、中立的）十分不现实，要有愚公移山的精神，那就是子子孙孙无穷匮也。但这样显然没有意义。这里针对有标记的数据的学习过程一般称为有监督的学习，无标记的，自然就是无监督（Unsupervised）学习了。而我们说的字典学习往往就是应用在无监督学习中。
稀疏表示原理
看了高维数据的特点，怎么解决呢？既然维度高了，那就降下来吧。所以问题就变成了，把高维数据用低维度表示的问题了。线代学得好的人这里可能想到了什么正交啊，基的问题。差不多就是这个意思。举个不是特别贴切的例子（实在找不到好理解的例子了），比如，你现在的位置怎么表述，东经多少，北纬多少，海拔多少，三个维度。但其实换一个说法，宿舍床上。一个维度。为啥维度变了呢，参照物变了，也就是所谓的基变了。这里的字典就是这个基。
学术一点表示，字典就是一个矩阵（n维），这个矩阵比之前的的高维数据（k维）的维度要低得多，即n&&k。数据对象y可以表示成y=a1
x1&+…+an&xn
其中，xi&是字典的列向量，ai&是一个线性组合，称之为稀疏表示系数，整个ai&构成的矩阵记为A。所谓的稀疏表示，其实就是求这个系数的矩阵。为了实现稀疏，系数矩阵的很多值，都是0。
过完备字典完成稀疏表示理论计算理论
稀疏求解的方法
通常情况下，构造一个目标函数，让A里面尽可能的出现0，这里就出现了L0&范数的概念。但开始一般用L_
1范数求解。为什么L1&可以实现稀疏化，这要从L0&（0范数）说起。L0&范数表示向量中非零元素的个数。Donoho证明了在完备字典构成的矩阵满足一定条件的时候，L0范数优化问题是有解的，而且是唯一解。这样的稀疏化即直观（稀疏就是让变量变少，也就是很多变量的系数变为0)，同时还有唯一解，为什么不用L0&范数，一定要o用L1&呢。很简单，L0&范数优化求解问题（L0&范数最小化）属于NP难问题（靠，又是这个东西）。当然，你可以用BMP，ROMP,OMP,OOMP,ORMP,SAMP等去求解L0&问题。然而，这些求解方法都是基于贪婪算法，效率很低，也就是说了等于白说。这时候，人类出大招了，Tao和Candes提出了近似求解该问题的方案，证明了在求解向量足够稀疏的情况下，L0&范数优化问题等价于L1&范数优化问题，即各向量分量绝对值之和。这样在多项式时间内就可以求解了，方法很多，不赘述了。
总之，L1&主要追求了稀疏化，对应的作为牺牲，则不能保证数据对象接近稀疏表示y，也就是说数据对象间的局部结构特征没有完全地体现出来。这也是LASSO的一个不足之处。
字典构造的方法
字典的构造式寻找稀疏表示下的最优基的构造，既要满足系数条件唯一性的约束，同时要得到更精确和更稀疏的表示。主要有两类方法：基于数据模型的字典构造和基于学习算法的字典构造。
基于基于数据模型的字典构：运用组合正交基等一定的数学分析工具得到稀疏字典，主要包括小波变化、离散余弦变换等等，好多。
基于学习算法的字典构造：这个方法是使用机器学习相关技术从训练样本集中学习字典，包括了稀疏表示和字典更新，也就是说，字典可以自动更新，找到更好的解了。听起来更加高大上了吧。经典的基于学习的构建方法是是产生K-means聚类过程的K-SVD算法，K-SVD通过迭代策略结合稀疏表示的更新一更新字典，从而加速收敛。
说白了，什么是字典学习呢？主要是在面对高维数据时，我们不好处理，所以变成好处理的低维数据（降维）。在这个过程中，有基于模型的方法，也有更高大上的基于学习的方法，这时候需要字典学习。这个工作的主要就是求一个稀疏表示系数矩阵A。
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。