Program Links : https://github.com/JJJYmmm/Image-Classification-with-SIFT-and-BOW

ReadMe

使用SIFT+BOW+SVM实现的一个图像分类器。SIFT负责提取图片中的尺度不变特征，词袋模型BOW则负责描述一张图片的SIFT特征分布，将结果送入SVM进行学习。项目参考https://github.com/CV-xueba/A01_cvclass_basic_exercise，不过修复了其中的SPM特征提取代码bug，具体修复见Vocabulary.py中的calSPMFeature函数。

项目结构如下：

• main.py : 程序入口点
• DataProcess.py : 读取图像，提取图像的SIFT特征
• ImageInfo.py : 图像相关信息的类，包括类别、大小、SIFT特征的位置和描述符等
• Vocabulary.py : 词袋模型，将所有SIFT特征进行聚类得到单词，并提取每个图像的SPM特征
• ClassifierKernel.py : SVM学习BOW特征的实现

结果见项目output.txt

以下是测试集的混淆矩阵

摘要

本篇主要介绍目标检测的一些基本概念，以及一个人脸检测的实例来加深印象，最后还谈了以下HOG特征的提取。

简单介绍(非常简单)

目标检测就是在负责在一幅图中检测出感兴趣的物体，一般采用滑动窗口来实现。但是实际应用中，检测效果依赖于光照、物体姿态、视角等影响。具体来说，目标检测需要考虑以下几个问题：

• 如何选择滑动窗口的大小，从而克服检测物体的尺度变化
• 如何建模图片的特征
• 如何找到物体对应的特征
• 如何克服不同摄影角度的问题(最原始的方法是训练多个视角的模型)

人脸检测

本次介绍基于adaboost的人脸检测模型，它广泛用在相机、手机摄影的人脸检测器。

boosting模型

首先介绍boosting模型，它是一种投票式的判别模型，相比于直接训练一个强分类模型，它的思想是训练多个弱分类器，取长补短达到强分类的效果。

训练过程如下，最终目的是训练一个分类器可以分辨红蓝数据点。刚开始所有数据点的权重为1。

接下来训练多个弱分类器，例如线性分类器组。找到一个正确率最高的分类器，将其保留。

这里有个先验假设，我们总能找到一个正确率大于50%的分类器。原因是如果所有分类器的准确率都小于50%,那我们只需要选正确率最低的那个分类器，然后跟他反着预测即可。

我们选出来的分类器性能并不高，他会有一些分类错误的数据点，对于这些数据点，我们扩大它们的权重。(在代码中，我们选择缩小正确预测的数据点的权重，这里方便观察使用另外一种思路)

在新的权重比例下，我们再次训练多个线性分类器，得到一个表现最好的分类器，将其保留。因为我们扩大了第一个分类器分类错误的那些数据点的权重，所以第二个分类器会更加关注这些点的分类。通俗的来说，第二个分类器可以解决第一个分类器没有解决的错误。

同理，我们扩大第二个分类器的分类错误点的权重，并训练第三个分类器。

最后，我们通过多个弱分类器得到一个强分类器。这就是boosting的思想。

当对一个测试图像分类时，使用投票的方式进行预测，如果投票分数大于全局分数的半数，那么就将其分类为真。

人脸检测

回到人脸检测领域，我们选择的弱分类器非常简单，其实就是一个卷积模板。如下图所示，选择一个固定位置的卷积核，卷积核分为白色区域和黑色区域，卷积结果就是白色区域的像素值和与黑色区域的像素值和的差。这个也叫harr-like算子。

例如人脸鼻翼区域的卷积核，因为光照的原因，鼻翼下方的像素值普遍比鼻翼位置的像素值低，因此对于人脸来说，整个模板的值往往小于0，这就组成了一个Weak Classifier。

在实际运算中，为了解决运算成本，我们一般使用二维前缀和对图像的区域值计算进行加速。

接下来的思路就和boosting一致，我们寻找多个模板构成多个弱分类器。然后参考boosting的训练机制得到一个人脸的强分类器。

不过对于一个准确率达到95%的强分类器，还是需要200个弱分类器参与运算。这效率还是不高，因为实际检测还需要通过滑动窗口确定人脸范围。

因此为了加快速率，采用强分类器的级联结构。具体来说，就是训练多个强分类器(每个强分类器里面都有多个弱分类器)。第一个强分类器的准确率不需要太高，比50%高一点就可以；第二个强分类器则处理第一个强分类器无法解决的错误；第三个分类器则解决第二个分类器无法解决的问题.....(这个思想也很像boosting)。最后通过多个强分类器检测的滑动窗口区域才认为存在人脸，否则直接pass。

这里为什么可以加快效率呢，因为强分类器不要求有很高的准确率，他只要保证可以让绝大部分正样本都通过，让部分负样本通过即可。通过多个强分类器的级联可以逐步过滤假阳样本。

假如第一个强分类器的准确率只需要50%，那么它大概只需要两个弱分类器就可以达到目的，这个远远低于95%准确率分类器的200个弱分类器。并且在检测过程中，大部分非人脸都会在这里被拒绝。所以可以提高检测效率。

以上级联特点也启示我们，对于越明显的特征检测器(比如刚刚提到的鼻翼位置的harr-like算子)，放在越前面，将进一步提高检测效率。

说白了，强分类器的级联，其实可以理解成强分类器组的boosting

行人检测

行人检测主要介绍一个HOG特征。行人检测一般就是给定窗口，通过计算窗口中的HOG特征，利用SVM判断窗口中是否包含行人。

HOG的计算过程如下：

• 首先计算图像的梯度大小和方向图。
• 将图像分为若干个8x8大小的小单元，对于每个单元，统计其梯度直方图。统计直方图分成9份，即一个小单元对应一个9维向量。
• 四个小单元为一个block，那么一个block对应一个36维向量。对于每个block中的36维向量进行归一化，这一步可以降低光照等环境影响。
• 滑动窗口大小为一个blcok，步长为一个cell，所以对于一个8x16小单元的图像，最后可以得到$(8-1)*(16-1)=105$个block，那么这张图片的HOG特征长度就为$105*36=3780$。

摘要

图像分类是一个经典的视觉任务。无论是分类、识别、检测等任务，都容易受到视角变化、光照、尺度、变形、遮挡、背景、类内实体等因素的影响，所以寻找合适的图像特征表示是一个比较重要的任务。本篇主要介绍了词袋模型表示。

图像表示

图像表示有很多方法，例如之前提到的SIFT特征、纹理特征、HOG特征，甚至直接对图像分块、随机选择图像块也可以表示图像。

词袋模型

词袋模型也可以用来表示一张图像。词袋模型简单来说就是选取一些图像基元构成字典。对于一张图片，首先对其进行分割，统计这些图像块在字典中的统计直方图，根据统计直方图特征确定图片属于哪种类别。

以下述三幅图为例，训练时，每幅图首先分别选出三张基元(如何选取见下文)，因此得到了9个基元的词袋。

对于一张测试图像，同样提取图像块并和字典中的9个基元比较，统计其出现个数，根据统计特征进行分类。

词袋模型其实也广泛用在自然语言处理中,比如可以用它来做主题推断等等。

最后一部分是图像块(基元)的提取，这里有许多方法可以提取。例如对于一张图片，可以使用SIFT提取几个区域，并用SIFT描述符来描述。这样一张图片就表示成多个SIFT描述符形成的文档，而多张图片形成多个文档。

对于所有的SIFT描述符，可以做聚类操作，挑出具有代表性的几个描述符，将其作为词袋模型的单词。(这些单词会分割整个特征空间，对于任意一个SIFT描述符输入，都可以把它归类为某个单词，从而可以统计单词分布)根据这些单词，我们可以知道训练图片的单词分布。当来了一张新的图片，我们同样对其进行SIFT变换，得到文档及其单词分布，通过对比训练库中各类图片的单词分布，可以确定一个最相近的类，完成图像分类的目的。

有时候，对于一整张图片使用词袋模型进行分类会存在问题。例如对于"我爱中国"和"爱我中国"两句话，它们四个字都相同，即单词分布一致，但是却表达了不同的意思。因此对于图像分类来说，我们可以使用空间金字塔表示，例如将图片分块，去比较小块图片的单词分布，从而提高分类的准确率。

生成式模型和判别式模型

以判断一张图片中是否有斑马为例，可以通过贝叶斯公式求得一张照片中有斑马的概率。如下图所示，如果$posterior-ratio$大于1，可以认为这张图含有斑马。$posterior-ratio$通过贝叶斯公式可以表示为极大似然概率比$likelihood-ratio$与先验概率比$prior-ratio$的乘积。

对于判别式模型，它直接建模$posterior-ratio$，也就是求$P(x|y)$。

对于生成式模型，它建模极大似然比，再通过先验概率比得到最终识别结果。关于贝叶斯公式先验公式等内容的理解，可以参考这篇：理解贝叶斯定理(prior/likelihood/posterior/evidence) - 知乎 (zhihu.com)

目标识别

传统目标识别都是采用滑动窗口的搜索方法：不断移动窗口，直到窗口中检测到物体。

摘要

语义分割任务是将一张图像做像素级别的分割，将一些原始数据(例如平面图像）作为输入并将它们转换为具有突出显示的感兴趣区域的掩模。它的难度会比图像分类和物体识别更难。当然我们这里讨论的分割效果还是从像素的一些统计特征出发，并没有引入人的先验认知知识(其实也多少引入了一点，例如格式塔理论，不过基于这个理论的算法难以建模)，所以效果是比较差的。

格式塔理论

格式塔理论其实是一种心理学理论，它表明人类视觉是整体的：我们的视觉系统自动对视觉输入构建结构，并在神经系统层面上感知形状、图形和物体，而不是只看到互不相连的边、线和区域。最经典的问题就是比较线段长短。

格式塔理论给我们了一些设计语义分割的思路，它给出了一些像素点分类的指导思想。例如通过地理位置、相似性、平行、对称等关系去分类像素点，实现分割。

这里其实就是自底向上的分割思路。人类看到一张图像做分割，应该是根据已有的知识，自顶向下地去分离物品，比如从人的分离、再到人身上衣服、首饰的分离；而机器做分割，都是从像素出发做分割，单从像素点没办法理解分割操作，这就需要格式塔理论给出的一些人眼视觉的底层模式来指导自底向上的分割了。

实际上，格式塔理论给出的这些模式虽然符合人的视觉特性，但是用算法难以建模。所以只有一部分模式被用在算法中。

基于聚类的分割

分割最简单的一个方法就是聚类，通过将相似的像素点聚在一起，将其认为是一个分割块，最终聚类的分类结果就是分割结果。聚类采用的特征可以是简单的RGB值，也可以是带有位置信息的RGB值，当然也可以是灰度值。

以下是不加入位置信息的灰度图、RGB图的聚类结果。可以发现这种分割并不能分割不同实例，比如两个辣椒连同西兰花都被聚在了一起。

如果加入位置信息，不同实例由于空间位置不同，就有可能被区分，例如下图的两个黄瓜片。

聚类的方式有很多，常见的就是KMeans。具体算法及其优缺点可以参考之前的博客~

Mean shift聚类与分割

先看两张Mean shift做分割的两张结果，还是挺惊艳的。

总的来说，Mean shift有点像基于密度的算法(例如DBSCAN这种)，它是计算给定圆框的重心位置，不断让圆框的圆心逼近重心的方向，从而找到密度最大的那个点。在这个过程中，圆框框住的那些数据点，都可以理解是同一个类。给两张图感受一下就懂了。

算法思想是比较简单的，就是找到一张图像的多个密度中心，每个密度中心认为是一个类。当然为了提高效率，算法还做了一些trick，比如label扩散等等。

Mean Shift有以下优缺点

优点：

• 不用假定数据簇的形状(因为基于密度)
• 只需要一个简单参数，即圆窗的大小
• 可以找到不同的模式(因为只依赖数据点密度)
• 对于外点鲁棒

缺点：

• 效果取决于圆窗大小
• 计算量比较大
• 无法对付高维特征(之前在KMeans也提到过，就是高维灾难，数据点在高维空间是稀疏的，通过密度不好迭代)

图论分割

图论分割的思想是：把图像认为是一个图G(V;E)，首先计算相邻像素点之间的距离Dis，再通过Dis为图中的每条边建模相似度Similarity，然后找到一个最小cost的切割，将整张图切成两份，完成二分类的切割，重复多次就完成语义的分割。

具体例子如下，边的权值代表相似度。

找到一个最小分割，就把最不相似的两份数据点分离开。

当然如果只找最小cost的切割，容易出现孤立点的情况。

所以引入图论中的正则化切割，将cost重新建模为

$$ cost = \frac {w(A,B)}{w(A,V)} + \frac {w(A,B)}{w(B,V)} $$

最终计算最小切割的流程如下：

• 计算W矩阵，即邻接矩阵，代表任意两点之间的相似度
• 计算D矩阵，D矩阵为对角矩阵，对角内容为W矩阵对应行的和
• 最小正则化损失表示为下式，其中y是01向量，代表图中数据点的分类情况

$$ normalized-cost=\frac {y^T(D-W)y}{y^TDy} $$

• 接下来求上式最小值，可以转换成求解以下方程$(D-W)y=\lambda Dy$,进一步转换成$D^{-1}(D-W)y=\lambda y$，即求$D^{-1}(D-W)$矩阵的倒数第二小特征值(因为矩阵有最小特征值0)，对应的特征向量y就是结果。

纹理特征聚类进行分割

我们也可以使用之前提到的纹理特征提取图像信息，再通过聚类将相似的像素点聚在一起，达到分割的目的。

不过纹理特征聚类这种方法在边缘表现不好，会将一个物体的边缘部分也作为一个实体。

摘要

通过纹理特征，我们可以确定物体表面的方向和形状。同时通过纹理特征，我们可以做语义分割、分类、纹理生成等任务。

纹理特征的获取

纹理就是从重复的局部模式组成，局部模式可以通过不同滤波器进行寻找，然后再通过梯度的直方图对局部模式进行表达。梯度直方图的生成做法是给定一个滑动窗口，每次统计窗口中各个像素的梯度方向信息，从而得到这个窗口的梯度直方图信息，然后将窗口移到下一个区域(HOG特征不同窗口之间有重叠，梯度方向信息则是通过不同的核得到)。例如上面四种动物的梯度方向直方图如下图所示，不同直方图之间存在较为明显的差异。

具体来说，我们可以使用之前用过的两个偏导核(其实就是边缘检测)对一张照片进行卷积，得到两个响应图。

使用红色窗口比对两个图片同一位置中的边缘点个数，列成表格。这个表格也就刻画了一个窗口的两维特征，这两维特征是通过两个偏导核得到的。进一步，我们可以把窗口的二维特征画到二维平面，大概能看到四个类。基本对应平坦区域、竖边、横边、拐点几种纹理。

事实上，我们可以采用多个模板去提取纹理信息，如下图所示，有检测边、条纹、斑点的模板。

不同模板提取出来的信息不同，那么对于图像中的一个像素点，我们可以得到他的多维表示。(38个核就对应一个38维向量)

通过多个模板的响应，我们也可以做简单的分类操作。如下图所示，通过响应值较大的模板去推断图片的纹理信息。