分类：
http://blog.csdn.net/AIchipmunk/article/details/8712384
物体识别一直是机器视觉与人工智能方面的研究热门，其方法更是多彩多样。有没有一种能够在线学习，且学习或特征提取速度快，同时鲁棒性好的方法呢？答案是肯定的，而且方法还不止一种。最近实现了一个基于稀疏表征（Sparse Representation）的物体分类算法，可以称作字典学习（Dictionary Learning），就能达到上述目的。不过这里说是字典学习有些牵强，毕竟并没有真正学习字典（MOD或KSVD），不过找不到别的叫法，就姑且这样吧。
稀疏表征： 既然是基于稀疏表征的方法，有必要看看与之有关的知识。 稀疏，简单的来说就是对于一个N维向量x，其中的元素大多数都为零，只有很少一部分元素为非零。对于一个分类问题，我们假设有k个不同的类在训练集中，同时每个类有n个样本，那么对于一个类，我们可以表示为：
其中v是每一个样本的特征向量，i代表第i个类。现在我们假设，待分类的物体可以表示为它所属类中所有样本的线性组合，即如下式：
现在我们将所有类放在一起，用C表示，则有：
然后令：
其中：
也就是说，x是待分类物体y的组合系数的向量。由于y只属于某一类，所以x中的系数只有y所属的那一类为非零值，其他无关类的系数统统为零，因此我们说x是稀疏的。 现在的问题就是，已知C和y，能否求出x，并使x足够稀疏。这也是经典的范数最小化问题。 由于“使x足够稀疏”这个条件的存在，导致求二阶范数最小化的方法不可取，即下式：
因为这样求出的x是稠密的，也就是说x中的系数有很多是非零值。于是问题转向求x的零阶范数最小化问题，x的零阶范数就是x中非零项的个数，让非零项个数最少，显然就是最稀疏的解，但很可惜，这是一个NP-Hard问题，当样本数量增多时，计算量显著增加，实用性不大。 研究表明，如果x的解足够稀疏，零阶范数最小化问题可以等价于一个一阶范数最小化问题，而一阶范数最小化问题是可解的，属于凸优化问题。解决这类问题的方法目前主要有匹配追踪（Match Pursuit）、基追踪（Basis Pursuit）等等。匹配追踪最简单，速度较快，同时也保证了较好的准确性，因此得到广泛使用。具体算法可参见维基百科http://zh./wiki/%E5%8C%B9%E9%85%8D%E8%BF%BD%E8%B9%A4。
字典学习： 现在可以来看看字典学习了，字典学习的第一步是建立字典，也就是上文中的C，C由很多类组成，每一类又有很多样本。这里我们主要对图片进行识别，所以类中的每一个样本就是一副20x20的图片（具体尺寸没有限制，不过小尺寸可以加快计算），比如我有一个类为可乐，那么我的样本就像下面这样：
这里只是举个例子，所以样本并不多，而且很多样本长得差不多，实际上应该尽可能选择不同形态或状态的图片作为样本，有助于提高算法的鲁棒性。 有了这些样本后，我们要把它变成特征向量的形式，也就是上文中的v。可能有人会想到使用SIFT或SURF什么的提取特征向量了。但在字典学习中，我们不需要，我们直接将图片的像素值排成一个列向量即可，比如一副20x20的图片，排列之后得到一个400维的向量。这也是字典学习的一大优点——学习过程非常简单迅速，同时不失准确性。 到此，我们就获得了这个类中样本的特征向量v，对所有类做相同的操作，就可以得到所有向量，完成对字典C的构建。 算法会将这个字典存入内存中，当我们输入一副待识别图片（大小必须和训练采用的大小一致）时，算法就会使用匹配追踪去求解一个稀疏的解x。最后我们可以观察x中系数的分布来判断这幅输入图片属于哪一类。一般来说，系数会集中分布于该图片所属的那一类，而其他类的系数会很小。如果输入的图片不属于字典中的任何一类，x中的系数几乎均匀的分布于所有类。因此，字典学习算法除了有识别已知物体的能力外，还能判断未知物体，一般不会将未知物体错分为某一类。
进一步： 到这里，可能大家已经发现了字典学习的一个缺点——所需存储空间大，尤其当类别或样本数量很庞大时，每个样本都是一个图像，这样的代价还是挺大的。有什么方法可以降低内存的消耗呢？——将图片缩小！这确实是一种方法，但往往任意缩小图片可能会丢失很多信息，造成算法性能的下降。使用SIFT或SURF提取高级特征，这种方法确实很好，不过SIFT和SURF算法不是免费的（天朝例外，呵呵），不方便用于商业应用。 这里介绍另外一种方法，该方法来源于大名鼎鼎的压缩感知（Compressive Sensing）。还记得上文中的公式 y=Cx 吗？我们将这个式子修改一下，两边都乘上一个矩阵R，如下：
其中，R是一个m行n列的矩阵（m << n)，假定C中每个样本的特征向量是一个n维列向量，那么R乘以C后，相当于将n维特征向量降维到了m维。同时注意到，这一操作并没有影响x，也就是说该方程的解和原来是一样的。了解压缩感知的童鞋可能知道，要保证降维后的特征向量保留尽可能多的信息，对矩阵R是有要求的。一般会使用正态分布矩阵，即矩阵中每一个元素均满足正态分布，由此可知，矩阵中的大多数元素都为零或很小的值，即R是一个稀疏矩阵。 当然，R还可以取很多其他形式，比如在压缩跟踪算法（见我的上一篇文章）中，作者所使用的随机投影矩阵，其中每个元素满足下面的分布：
当s大于2时，该矩阵能满足压缩感知的要求。该矩阵最大的优点就是计算方便，只需一个随机数生成器即可，并且比正态分布矩阵更稀疏，可以只保存非零元素，从而节约内存。 这样，我们在生成字典时，就可以用R对每一个样本都进行降维，然后再放入字典，在识别时，也先将待识别图片用R降维，再进行识别。一般取m=50就能达到很好的效果了，这种方法尤其适用于图片较大的时候，比如100x100或更大！
小结： 以上就是字典学习所涉及到的主要类容，几乎都是我在做相关项目时的经验总结，也包括读了很多文献后的感想。有用词不妥还请谅解，有理解错误还请指出。希望与更多的朋友一起讨论。
|
|
|
