以图像分类为目标的字典学习算法
2013-03-29徐健常志国赵小强
徐健 常志国 赵小强
摘 要：综述了字典学习算法的主要研究方向之一，即以图像分类为目标的稀疏表示字典学习算法。从空间变换法和类别指示法两个角度，分析各种算法的优缺点，并对相应的实验结果进行比较。总结了利用这类算法进行图像分类时所面临的其他一些关键问题，如模式识别中的旋转不变性和计算速度等。依据目前已有的技术和应用需求，探寻该领域未来的研究方向。
关键词：图像分类；稀疏表示；字典训练；原子
中图分类号：TN391?34 文献标识码：A 文章编号：1004?373X（2013）02?0022?04
信号稀疏分解方法被广泛的应用于图像处理的各个领域。但是与具有完美数学形式的信号分解算法，如离散傅里叶变换（Discrete Fourier Transform，DFT）[1]、离散小波变换（Discrete Wavelet Transform，DWT）[2]和传统的主成分分析法（Principle Component Analysis，PCA）不同，近年来许多人提出的信号稀疏分解算法不再要求稀疏表示矩阵为正交完备基底[3?4]。非正交过完备的表示矩阵被人们称为字典。稀疏表示矩阵可以由机器学习算法产生，这类算法称为字典学习算法。人们已经证明了当使用非正交过完备字典对信号进行稀疏表示时，能够最稀疏表示一个样本的字典系数是惟一的[5]。
1959年David Hubel和Toresten Wiesel通过对猫的视觉条纹皮层简单细胞感受野的研究得出一个结论：主视皮层V1区神经元的感受野能对视觉感知信息产生一种“稀疏表示”，证明了稀疏表示符合视觉感知特性[6]。1993年Mallat等首次提出了应用过完备冗余原子库对信号进行稀疏分解的思想，并引入了匹配追踪算法，为非正交过完备字典的应用提供了理论基础[7?8]。自2009年以来，过完备冗余字典的稀疏表示方法成为图像处理领域和模式识别领域的研究热点，被广泛应用于解决计算机视觉方面的问题，如图像去噪、图像修补、图像超分辨率放大和图像分类等[9?11]。从目前的研究现状来看，这类字典学习算法已经成为一个研究热点，专为图像分类而设计的字典学习算法就有几十种。人们希望通过稀疏字典学习算法真正揭示人类视觉特性和图像语义之间的关系。本文将这些字典学习算法的研究思路总结为两大类，并根据目前的研究提出该领域未来可能的发展方向。
1 图像分类
图像分割、图像识别等问题都可以归为图像分类问题。在利用稀疏表示进行的图像分类研究中，如何设计对特征提取有效的字典和投影是决定算法性能最关键的因素[3]。
传统的基于逼近的稀疏表示字典训练模型为：
式中：[X]为训练样本矩阵，每列代表一个训练样本；[D]为待训练的字典；[A]为表示系数；[ai]是组成[A]矩阵的列向量；[?F]表示矩阵的F范数；[?0]表示向量的0范数。该字典训练模型的意义是在满足[ai]的0范数约束情况下能达到残差最小。为了完成图像分类任务，人们在该模型的基础上思考出许多改进方案。
在解决图像分类问题的过程中，根据对稀疏表示特征的利用方式不同，利用稀疏表示进行图像分类的方案可以分为2类：
（1）设计字典把图像变化到有利于分类的空间上，把稀疏系数放入传统分类器进行分类，称之为空间变换法。
（2）设计字典原子与语义直接对应， 利用稀疏系数大小所表示出的样本属性进行分类。称之为类别指示法。
式（1）所示的问题是双变量优化问题，因此在迭代过程中大多使用固定一个变量优化另一个变量的交替优化算法[4]。本文后续所综述的算法，凡是涉及字典学习算法的双变量优化问题，均使用交替迭代的优化算法进行，本文后续的内容只描述字典训练模型，不再赘述优化算法。
2 空间变换法
当样本本身不易分类时，可以利用稀疏表示字典将其变换到易于分类的空间上去。为了让这个空间有利于分类，需要在式（1）所示的字典训练模型的基础上加入一些约束。
文献[12]建立字典训练模型时，针对每个类训练一个字典。该算法的字典训练模型为式（2）。
[minDjNj=1i=1…Nl∈SiCλiR*xl，DjNj=1+λγR*xl，Di，yj=R*xl，Dj，Cλiy1，y2，…，yN=logj=1Ne-λyj-yi，R*x，D=x-Da*x，D22，a*x，D=argminα∈?kx-Da22，s.t. a0L] （2）
式中：[xl]是第[l]个训练样本；[Dj]是第[j]个类别对应的字典；[L]是稀疏度。式（2）中在减少稀疏残差的基础上，将优化目标变成残差之间大小关系，其中的[Cλi]使用了logistic函数，保证了这些字典在对自己所对应类别的样本进行稀疏表示时残差比较小，在对其他类别的样本进行稀疏表示时残差比较大。该算法本质是将样本矢量[x]映射为高维矢量[a]，然后使用K近邻算法判断类别。
但是由于logistic函数的运算量较大，该算法在考虑迭代算法时需要进行二阶泰勒近似以降低运算复杂度。并且该算法针对每个类别都要训练一个字典。在分类时，样本需要在所有的字典下根据稀疏度约束进行稀疏表示，对比其残差才能确定类别。因此算法复杂度较高。为了降低分类时算法的复杂度，文献[13]提出了只用一个字典就能区分多个类别的字典训练模型，如式（3）所示：
[minD，θ（i=1mμCS*xi，D，θ，-yi-S*xi，D，θ，yi+1-μS*xi，D，θ，yi）+λ2θ22，Sai，xi，D，θ，yi=Cyifxi，ai，θ+λ0xi-Dai22+λ1ai1，yi=R*xi，DCx=log1+e-x，fx，a，θ=wTa+b或fx，a，θ=xTWa+b，θ=W∈Rn×k，b∈R] （3）
该算法借助了支持向量机（Support Vector Machine，SVM）思想，试图将线性分类器和字典[D]均作为训练对象。优化目标兼顾正确判决的[S*]和错误判决[S*]之差及稀疏表示残差，并加入了线性分类器（或双线性分类器）的条件。通过理论分析，得出该算法在研究分类框架时兼顾了泛化能力，这样就避免了过拟合现象，并且提高了该算法的鲁棒性。但是该算法没有解决线性组合系数[μ]如何选取的问题。而且，尽管分类时算法复杂度降低了，分类器训练的过程算法复杂度仍然很高。无法针对维数较高的样本进行训练。
文献[14]提出了一种图像分类算法，其主要思路是在优化稀疏表示残差的同时降低字典间的相关性。其字典训练模型如式（4）所示：
[minDi，AiXi-DiAi2F+ηj≠iDTjDi，ai0 式中：[Xi]为第[i]类样本；[Di]是对应第[i]类样本的字典[Ai]是表示系数，[η]是拉格朗日参数。该字典训练方法不但考虑了在固定稀疏度情况下的稀疏表示残差，还把字典间的相关性作为约束条件。 实际上，如图1所示，假设[Dj∈Rmj×nj]是固定的，[dkjnjk=1]是[Dj]中的原子。那么训练得到的[Di]，如果和[Dj]互不相交的话，那么[Di]的所有原子只能位于[Dj]的正交补[Φ]上。如果[Dj]是过完备且列满秩的字典，理论上[Di]不可能和[Dj]完全正交。因此它们之间一定存在不正交的原子。为了提高字典间的正交性，每个字典尽量都不占用更大的空间。这一点可以通过降低字典维数来得到。由于相关性的要求，每个类别的字典的训练过程都被限制在与其他字典尽量不相关的狭小空间内寻找原子，而这些狭小空间未必能够以较小残差对该类样本进行稀疏表示。因此相关性降低和稀疏表示残差是一对矛盾。较小的相关性必然带来较大的残差，而较小的残差会导致相关性增强。 因此对这类字典进行训练的迭代算法必须要平衡相关性和残差之间的矛盾。并且该算法没有解决在同时优化字典和系数2个变量时如何选取最优步长的问题。不合适的步长将会导致2个变量不能同时收敛。 [minW∈Rm×p，D∈DEy，xlog1+e-yxTWα*x，D+v2W2F] （5） 随后文献[15]中对前面提出的算法做出了改进，提出了如式（5）描述的字典训练模型。 该算法对logistic函数的运算结果的均值作为优化目标，并且使用双线性函数训练分类器提高了算法的泛化能力。尽管双线性函数的参数众多导致训练复杂度提高，但是却为分类器提供了更多灵活性，避免了过拟合现象。但是该算法仅仅在手写数字识别等问题上进行了测试。对于更加大型或复杂问题的实验仍然有待进一步研究。上述几种算法都针对MNIST和USPS手写数字识别进行了实验，每个文章中算法的最佳实验结果如表1所示。REC是使用式（1）所示的字典训练模型训练字典得到的分类错误率。A是文献[13]的最佳实验结果。B是文献[14]的实验结果。C是文献[15]提出的算法在无监督学习过程中的实验结果。D是文献[15]提出的算法在有监督学习过程中的实验结果。K?NN是K近邻算法分类的实验结果（其中K为10）。SVM?Gauss是SVM算法在使用高斯核函数时的实验结果[16]。 文献[12?15]都是将稀疏表示系数作为特征进行图像分类，其本质是将图像映射到便于分类的空间上去，然后运用传统的分类算法（如K近邻，SVM算法）进行分类。由于稀疏表示本身对于噪声具有鲁棒性。因此，运用该方法的分类算法有较低的错误率。 表该算法首先对图像进行极坐标映射。假设[a，b]是图像本身的坐标，则通过式（6）将其映射为[ξ，η]。然后再通过Rapid变换将其变为平移不变特征。最后将变换过的具有平移不变性的图像作为训练样本进行字典学习。这样学习得到的字典可以提取到图像的平移和旋转不变的特征。由于目前存在的字典学习算法都采用双变量迭代更新的方法，且迭代步骤中都存在奇异值分解等运算规模较大的步骤，因此大多数都是利用低于100维的数据进行字典学习[20?21]。当遇到了较大图像的字典学习问题，都采用将数据分割成小块分别处理[10]。为了加快字典学习速度，文献[22]提出了使用GPU并行技术来解决较大图像的分类识别问题。利用GPU技术来提高各种图像处理算法的速度将是未来图像处理发展的趋势。 5 结 论 从上述研究现状来看，目前的用于分类识别的稀疏字典训练还缺乏字典参数与语义之间的关系的论证，因此下一步的研究应当关注如何从字典训练过程揭示图像语义方面的问题。另外，稀疏表示的特征提取方法还处于起步阶段。 上述文献所涉及算法仅仅在小规模的较简单的分类问题上进行了测试，还没有触及更加大型和复杂的问题。因此，对这类方法的应用还有待进一步开发。稀疏表示的字典训练往往涉及优化问题，需要大量的样本参与运算，算法复杂度较高。尽管已经有少部分研究人员利用GPU技术进行仿真实验，但是如何专门为GPU设计迭代算法，充分发挥GPU的并行计算能力，也是该领域未来的发展方向。 随着基于训练的字典模型理论的完善，信号处理将不再局限于以传统的正交完备基为理论基础。非正交过完备字典以其符合人眼感知机理、系数稀疏性、鲁棒性和灵活性等优势将成为未来信号处理研究的主流。 参考文献 [1] 季虎，夏胜平，郁文贤.快速傅里叶变换算法概述[J].现代电子技术，2001，24（8）：11?14. [2] 周义明，张超，张化民.样条小波的构造方法及其应用[J].现代电子技术，2009，32（8）：36?40. [3] WRIGHT J， MA Y， MAIRAL J， et al. Sparse representation for computer vision and pattern recognition [J]. Proceedings of the IEEE， 2010， 98（6）： 1031?1044. [4] AHARON Michal， ELAD Michael， BRUCKSTEIN Alfred. K?SVD： An algorithm for designing overcomplete dictionaries for sparse representation [J]. IEEE Transactions on Signal Processing， 2006， 54（11）： 4311?4322.
[5]AHARON M， ELAD M， BRUCKSTEIN A M. On the uniqueness of overcomplete dictionaries， and a practical way to retrieve them [J]. Linear algebra and its applications， 2006， 416（1）： 48?67.
[6] HUBEL D H， WIESEL T N. Receptive fields of single neurones in the cat's striate cortex [J]. The Journal of physiology， 1959， 148（3）： 574?591.
[7]王建英，尹忠科，张春梅.信号与图像的稀疏分解及初步应用[M].成都：西南交通大学出版社，2006.
[8] MALLAT S G， ZHANG Z. Matching pursuits with time?frequency dictionaries [J]. IEEE Transactions on Signal Processing， 1993， 41（12）： 3397?3415.
[9] XU Z， SUN J. Image inpainting by patch propagation using patch sparsity [J]. IEEE Transactions on Image Processing， 2010， 19（5）： 1153?1165.
[10] ELAD M， AHARON M. Image denoising via sparse and redundant representations over learned dictionaries [J]. IEEE Transactions on Image Processing， 2006， 15（12）： 3736?3745.
[11] ZHANG Hai?chao， ZHANG Yan?ning， HUANG THOMAS S. Efficient sparse representation based image super resolution via dual dictionary learning [C]// IEEE International Conference on Multimedia and Expo. Barcelona， Spain： IEEE， 2011： 1?6.
[12] MAIRAL J， BACH F， PONCE J， et al. Discriminative learned dictionaries for local image analysis [C]// IEEE Conference on Computer Vision and Pattern Recognition. Anchorage， Alaska， USA： IEEE， 2008： 1?8.
[13] MAIRAL J.， BACH F.， PONCE J.， et al. Supervised dictionary learning[C]//Annual Conference on Neural Information Processing Systems. Vancouver， BC， Canada： CNIPS， 2008： 1?6.
[14] RAMIREZ I， SPRECHMANN P， SAPIRO G. Classification and clustering via dictionary learning with structured incoherence and shared features [C]// IEEE Conference on Computer Vision and Pattern Recognition. San Francisco， CA， USA： IEEE， 2010： 3501?3508.
[15] MAIRAL J， BACH F， PONCE J. Task?driven dictionary learning [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（4）： 791?804.
[16] LECUN Y， BOTTOU Y， BENGIO Y. Gradient?based learning applied to document recognition [J]. Proceedings of IEEE， 1998， 86（11）： 2278?2324.
[17] WRIGHT J， YANG A Y， GANESH A， et al. Robust face recognition via sparse representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（2）： 210?227.
[18] YANG M， ZHANG L. Gabor feature based sparse representation for face recognition with Gabor occlusion dictionary [C]// Proceedings of the 11th European Conference on Computer Vision. Berlin： Springer?Verlag， 2010： 448?461.
[19] BAR L， SAPIRO G. Hierarchical dictionary learning for invariant classification [C]// Proceedings of 2010 IEEE International Conference on Acoustics， Speech， and Signal Processing. Dallas， TX， USA： IEEE， 2010： 3578?3581.
[20] MAIRAL J， BACH F， PONCE J， et al. Online dictionary learning for sparse coding [C]// Proceedings of Annual International Conference on Machine Learning. Montreal， QC， Canada： AICML， 2009： 689?696.
[21] ZOLTAN S， BARNABAS P， ANDRAS L. Online group?structured dictionary learning [C]// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Colorado Springs， CO， USA： IEEE， 2011： 2865?2872.
[22] NAGESH P， GOWDA R， LI B. Fast GPU implementation of large scale dictionary and sparse representation based vision problems [C]// Proceedings of 2010 IEEE International Conference on Acoustics， Speech， and Signal Processing. Dallas， TX， USA： IEEE， 2010： 1570?1573.
