基于中层特征的精细图像分类-论文.doc

基于中层特征的精细图像分类摘 要现如今，图像处理中目标分类与检测越来越多的得到了人们的关注与研究。目标分类一般分为两种，一种是基础图像分类，另一种是越来越受到人们关注的精细图像分类。基础图像分类是为了区分具有不同形状以及视觉特征的物体（例如给出一个鸟的图片，基础图像分类就是为了要区分出这张图片是鸟的图片还是狗的图片）。精细图像分类则是要区分具有相似形状以及外貌特征的物体（例如给出一副鸟的图片，精细分类就是要判断出这只鸟究竟属于哪一类鸟）。在这篇文章中，我们主要研究了图像的精细分类问题，在现实生活中它比图像的基础分类更加具有实用性。我们所使用的数据库是目前比较有挑战性的CUB-200以及Stanford_Dogs数据库。我们结合了高效匹配核函数（EMK）与带有权重的空间金字塔以达到最优的分类表现。实验用EMK与词包（BoW）作对比，其中，BoW也可以看做是一种核函数匹配方法，EMK是找出词表主要成分的相互关系，并且在核函数的框架中找到一种新的映射。EMK是通过映射，将局部特征映射到一个低维的特征空间并且将结果向量平均化以形成一个特征层集合。实验结果表明，这可以很好的改进系统的性能。关键词：高效匹配核函数（EMK）；词包（BoW）；细粒度图像分类ABSTRACTIn recent days, object classification and detection in image processing are getting more and more attention and research. Object classification include two sides, one is basic classification, another is fine-grained classification which attract more and more people to study. basic classification is to classify the object which have the different shapes and visual appearance(e.g.: for a picture of bird,the basic classification is to identify the object in the picture is a bird or dog ). Fine-grained classification is to classification the object with the similar shapes and visual appearance(e.g.: for a picture of bird,the fine-grained classification is to identify which kind of birds it belongs to). In this paper, we study the problem of fine-grained image categorization, which is much more useful in real applications than basic image classification. Based on the most challenge dataset, CUB-200, Stanford_Dogs_Dataset.We combine Efficient match kernel (EMK) with the weighted spatial pyramid to achieve state-of-art performance. Comparison with BoW, which can also be viewed as kernel matching approach, EMK digs the relations among vocabulary bases and finds a new mapping in kernel framework. By it, local features are mapped to a low dimensional feature space and average the resulting vectors to form a set level feature in EMK. It is proved that it is helpful to improve the system performance.第1章 绪论1.1精细图像分类的研究背景及意义伴随着网络和多媒体技术的飞速发展，越来越多的声音、图形、图像、视频和动画等数字信息越来越多的出现在人们的工作、学习和生活当中。而图像作为一种内容丰富、表现生动的媒体信息，也越来越受到了人们的关注。在现实生活中，时时刻刻都会有大量的图像产生，对于如何从这些给定的图像信息中找出符合人们所需求的图像就是研究者们需要解决的问题。图像分类其实就是模式识别的过程，它是利用计算机来对图像进行定量分析，把图像中的每个像素元或区域转化成一种计算机识别的特征类别，用来代替人的视觉判读。现如今百度、google等网络公司使用的都是传统的图像分类方法，为了能够实现图像更精确的分类也都有做图像精细分类方面的研究，如果可以实现图像的精细分类，那么在网络搜索中，我们可以快速的实现图像的匹配，以此来实现精确图像的搜索。而不会像在传统的图像分类中那样，在图像匹配方面只能实现粗略的匹配而使得图像搜索结果多而不精。随着智能机器的不断发展进步，人们对于图像分类的要求越来越高，它要求我们对于图像能够实现越来越精细的分类。而传统的图像分类只能进行粗略的图像分类，它一般都是利用图像的纹理、灰度、形状位置等底层特征对图像进行分类，而在图像的搜索查找方面一般都是选用关键词来进行查找。而在本文中，我们所要实现的是图像分类能够根据图像的底层特征以及利用中层特征思想的方法来实现图像的精细分类，并且可以根据未知图片来搜索相关信息。1.2国内外研究现状基于精细图像分类的研究是从11年以后才开始有相关研究的，且只有斯坦福大学、加利福尼亚大学等少数的学校在做。其中以斯坦福大学Li Fei-Fei等人在2011年、2012年在CVPR上发表的Combining Randomization and Discrimination for Fine-Grained Image Categorization以及A Codebook-Free and Annotation-Free Approach for Fine-Grained Image Categorization最为突出。下面我们介绍几种图像分类的方法。1、基于编码簿（code book）的编码方法现如今大多数的最优的图像分类系统是基于局部图像块编码的视觉代码，但是这种视觉代码是经常导致图像块详细信息丢失的粗糙编码。现如今，一些最新的研究开始使用稀疏编码SC（Sparce Code）来获得更准确的图像块编码，并且这种方法已被证明在许多的图像分类的任务中使得分类性能得到了改进。但是在这种方法中，图像信息的丢失也是没有办法避免的。2、基于注释的方法图像分类中，为了在细粒度分类问题中说明重要目标的特性以及与其它的相似目标的细微区别，越来越多的工作都试图从人类方面来吸收更多的输入信息，包括要求人们点击目标区域、回答关于目标特性问题的人类循环方法。它是一个关于鸟类识别的改进的postlet-like算法，并且在Caltech-UCSD鸟类数据库中获得了良好的性能。但是这种方法需要人们对于目标特性或者关键点位置的冗长的注释，这对那些需要全自动学习来进行区分图像信息的情况构成了严峻的考验。而且将这种方法使用到新的细粒度目标层中所需要付出的代价是很昂贵的，因为特征查询和目标关键点通常需要由领域的专家仔细设计，尤其是那些没有明显关键区域或者直接特性的目标，例如树、水、食物等等。3、基于模板的方法基于模板的算法是一个需要获得带有大量随机生成的映像模板来匹配图像特征响应的映射。这种方法在思想上类似于最近大量使用的各种预定义滤波器来生成图像响应特征的研究，例如目标检测，人体部分探测器以及图像区域的聚类中心。虽然这些方法在基础层目标和场景分类任务中已经展现了很好的结果，但是它们仍然面临着粗糙编码或者冗长的人类注释的问题，而且这些代表方法目前还没有一个用在细粒度图像分类上。4、细粒度图像分类方法细粒度图像分类方法是用各种数据库来进行细粒度图像分类，它是最近研究比较多的。这种方法可以识别数据中的具有相似外表的图像。这也是我们这次设计的主要思想，具体详见下文。5、其它图像分类方法这些超出了我们这篇文章的讨论大型目标分类工作的范畴，例如一些基于局部模型工作在最小范围的分类目标或从背景中局部化目标可以完成的很好。然而，在怎样使用这些方法来区分那些有相似视觉外表的细粒度目标并且展示这些目标的的重要部分还不清楚。1.3文章框架精细图像分类是解决限制人类视觉效能以达到区分相似目标的有效方法。例如当人看到一种自己并不认识的花或鸟时，很想知道这种花或鸟的具体名称以及其相关信息，但是人的视觉以及学识可能会不能帮助人们区分这种花或鸟，这时，细粒度图像分类就会帮助人们来解决这个问题。而在文章中，我们主要想做的也是细粒度图像分类，这种方法亦可以广泛扩展到其它领域中，并且其分类范围也可以广泛运用到任何的数据库中。在文章中，为了实现图像的细粒度图像分类，整个实验步骤如图1-1：BoWSVM空间金字塔特征提取使用包围盒截取图片图片RFEMK图1-1 细粒度图像分类实验过程文章我们采用了以下框架：1、特征提取在文章的第二章中我们介绍了整个程序中的特征提取，而在特征提取的过程中，我们采用了两种特征描述子来提取图片的特征信息以作后续分类结果的对比。而这两个特征我们采取了尺度不变特征转换（SIFT）特征以及方向梯度直方图（HOG）特征。对全文的精细图像分类起到基础作用。2、使用中层特征在文章的第三章中，我们介绍了将第二章中所提取的特征进一步处理以达到我们的精细图像分类要求。在这一章中，我们介绍了我们在实验过程中所用到过的词包（BoW，Bag of Word），高效匹配核函数（EMK，Efficient Match Kernel）以及空间金字塔（SP，Spatial Pyramid）。对比了相互之间的关系以及差别，对全文的精细图像分类起到很重要的作用。3、分类器介绍在文章的第四章中，我们介绍了本实验的最后一步匹配环节，在这一环节中，我们使用了支持向量机（SVM，Support Vector Machine）以及随机森林（RF，Random Forest）这两种方法。在第四章中，我们重点介绍了每种分类器的特点、结构以及优缺点。4、实验环节在文章的第五章中，我们介绍了整个文章的实验环节。首先介绍了我们实验中所使用的数据库，之后介绍了实验结果以及实验结果分析。第2章 底层特征文章中对于底层特征的描述，我们采用了局部描述子SIFT特征以及HOG特征，对于这两种基本特征的详细描述如下。2.1 SIFT算法介绍尺度不变特征转换(Scale-invariantfeaturetransform或SIFT)是David Lowe在1999年提出的一种局部特征描述子算法，并且在2004年进行了更深入的发展和完善。SIFT算法是一种电脑视觉的算法，它可以用来检测与描述图像中的局部性特征。该算法通过求一幅图片中的特征点（interest points,or corner points），包括这些特征点的尺度（scale）以及方向（orientation）的描述子来得到特征描述子，并进行图像特征点匹配，这种方法获得了良好效果。SIFT特征不仅仅具有尺度不变性，即使改变其图像亮度、旋转角度或拍摄视角，仍然能够得到好的检测效果。而且对视角变化、噪声也能够保持一定的稳定性。整个SIFT算法分为以下几个部分：1、 尺度空间的极值检测：第一阶段的计算搜索了所有的尺度和图片位置信息。通过使用差分高斯（difference-of-Gaussian或DoG）函数来有效的区分具有潜在的尺度以及方向不变的兴趣点；2、 关键点定位：在每一个可能的位置，找出具有决定性的位置和尺度所匹配的详细模型，然后基于它们的稳定性来选择关键点；3、 分配方向：基于局部图像的梯度方向，每一个关键点位置都被分配了一个活多个方向。对于图像数据都会转换成相应的特征点，而每个特征点都会分配尺度、方向以及位置信息，这些是以后我们图像分类操作的基础，因此，我们应提供这些转换过程一个不变性；4、 关键点描述子：局部图像的梯度是由我们所选择的在每个关键点周围区域的尺度得出来的，这些使得在光照改变以及发生局部形变时这些特征点仍具有代表性。2.1.1SIFT算法的具体步骤： 1、 构建尺度空间首先，要构建一个尺度空间，这是一个初始化的操作，该尺度空间理论的目的在于模拟图像数据的多尺度特征。Koenderink (1984) and Lindeberg (1994)已经证明，在各种合理的假设下，高斯函数是唯一可能的尺度空间函数。由于高斯卷积核是实现尺度变换的唯一线性核，因此，我们可以将一副图像的尺度空间定义为： (2-1)其中，*代表卷积运算，是尺度可变高斯函数， 在公式（2-1）中（x，y）是空间坐标，同时也是尺度坐标。值的大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度则对应图像的细节特征。大的值对应粗糙尺度（低分辨率），反之，则对应精细尺度（高分辨率）。不同所对应的尺度空间如下图：图2-1 不同所对应的尺度空间为了能够有效的在尺度空间检测稳定的关键点坐标，Lowe于1999年提出了使用高斯差分尺度空间（DOG scale-space）来计算尺度空间的极值。它是利用不同尺度的高斯差分核函数来卷积图像I生成。可以由两个被一常量因子所分开的相邻尺度间的差别来计算。即(2-2)对于选择这个函数的方法有很多种。首先，这个函数要是一个能计算出来的有效函数，例如给出一副平滑图像，我们需要在任意尺度空间特征描述子情况下都能计算出L,而D能由简单的图像差分来计算。除此之外，由Lindeberg (1994).的研究我们可以得到，高斯差分函数可以近似的看做一种高斯函数的拉普拉斯标准尺度变换，。Lindeberg研究表明，带有因子的拉普拉斯变换的标准化需要尺度不变性。在详细的实验对比中，Mikolajczyk (2002)发现，的最大值和最小值相比于其它的如梯度或者Harris角函数这些可能的图片函数所得到的图片特征更加稳定。和之间的关系就参数而言可以从热扩散方程方面理解。即（2-3）从公式（2-3）可以看到，可以由有限差分逼近来计算，这就利用了在以及这两个相邻出度空间的的不同处，即（2-4）因此有：（2-5）公式2-5表明，当差分高斯函数具有尺度而不同于一个常量时，它就已经包含了标准化所需的拉普拉斯尺度不变性。方程中的在所有的尺度中都是一个常数，因此不会影响到极值的定位。近似误差也会由0到1，但是在实际实验中，近似误差对极值检测的稳定性或在尺度中显著差异的定位几乎没有影响。在SIFT算法过程中，一般要建立图像金字塔：如何建立图像金字塔如下：对于一幅图像I，需要建立其在不同尺度（scale）的图像，也称为塔或子八度（octave），这是为了图像能够具有尺度不变性（scale-invariant），也就是在任何尺度都能有对应的特征点，第一层子八度的尺度为原图大小，后面的每一层子八度都为其上一层子八度降采样的结果，即为原图的1/4（长宽分别减半），构成了下一个子八度（高一层的金字塔）。例如1塔的第0层可以由0塔的第3层down sample得到，然后进行与0塔类似的高斯卷积操作。如何建立一个有效的可以由图2-2得到：图2-2：图像的左侧表示对于每一个尺度空间的子八度，初始化后的图片就会由高斯函数不停的卷积以生成图像尺度空间的集合。图的右侧表示，相邻的高斯图像依次相减以生成差分高斯图像。在每一个八度后，高斯图像进行降采样。之后过程重复。首先，最初的图像逐渐由高斯函数进行卷积，生成被常数在尺度空间内分割的图像，即图2-2的左边部分。我们选择将尺度空间中的每一个子八度分成s层，所以就有，而对于每一个子八度中的大量模糊图片，我们必须生成幅图片，这样最后的极值检测才能覆盖整个的子八度。相邻的图像尺度相减后得到图2-2中右面的差分高斯图像。在完成该尺度空间的处理后，我们就会以重新采样高斯图像。关于的采样准确率和之前子八度的采样准确率是没有差别的。但是计算却简单了很多。一般来说，我们由图片的大小来决定建几个子八度，每层子八度几层图像(S一般为3-5层)。0层子八度的第0层是原始图像(或是我们取双精度（double）后的图像)，往上每一层是对其下一层进行差分高斯卷积变换（其中值是越来越大的，例如可以是, , 等等），从直观上看，越往上图片就越模糊。2、 局部极值点检测为了检测局部的极大值与极小值，每一个样本点都要和它周围所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点的大或者小。即每个样本点都要和它周围同尺度的八个点以及上下相邻两层的个点，共26个点进行比较，以确保在尺度空间和二维图像空间都检测到极值点。 一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点,如图所示。图2-3：差分高斯图像的极大值与极小值的检测，是通过比较一个像素点在的区域内与其相邻的26个相邻像素点的比较得来的在极值比较的过程中，同一组中的相邻尺度（由于k的取值关系）肯定是上下层之间进行寻找，每一组图像的首末两层是无法进行极值比较的，为了满足尺度变化的连续性，我们在每一组图像的顶层继续用高斯模糊生成了3幅图像，高斯金字塔有每组S+3层图像。DOG金字塔每组有S+2层图像。3、 关键点定位一个可能的关键点已经经由对比像素周围的值得到，第二步就是要形成一个详细的适合位置、尺度和主曲率的数据。这就允许我们放弃一些具有低对比度（对噪声比较敏感）的点，或者在图像边缘的边缘响应点。这种方法的初步实现仅仅是定位在某一位置、尺度的中央采样点处确定关键点。然而，最近Brown提出了一个新的方法来确定关键点。它通过拟和三维的二次函数到局部采样点，以检测最大值的曲线位置。实验证明，这个方法对图像的匹配和稳定性具有实质性的改进。（1）去除低对比度的点这个方法使用了尺度空间函数泰勒展开式（展开到二次项），所以在采样点处，公式（2-2）可以转换成：（2-6）其中D和它的一维及二维导数在采样点处均可求，是采样点处的补偿。将公式（2-6）对x求导，并令导数为0，得到的即可得到精确位置，即：（2-7）正如Brown 提出的那样，Hessian 和D的导数在通过使用不同的相邻的采样点是近似的。的线性系统可以以最小的消耗来得到解决。如果在任一维度的值大于0.5，这就说明极值点考进来一个不同的采样点，这种情况下，采样点就会由插入的采样点代替。最后的代入采样点的位置以获得插值的极值点。将公式（2-7）代入公式（2-6）中即可得到极值，它可以有效的去除低对比度的关键点和不稳定的点。为：（2-8）若，该特征点就保留下来，否则就舍去。（2） 去除边缘响应点为了特征点的稳定，光去除低对比度的点是不够的，边缘点对于高斯差分函数有强烈的影响。因为边缘响应点是不容易确定的，因此，即使一点点的噪声也会对边缘点残生很大的干扰。一个定义不好的高斯差分函数的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率可以通过一个的Hessian矩阵H求出:（2-9）D的主曲率和H的特征值成正比，借用Harris and Stephens (1988)的方法，我们可以避免明确的结算特征值，因为我们只需要考虑它们的比例问题。令为较大特征值，为较小的特征值，我们可以从H以及行列式中计算出特征值的和： （2-10）（2-11）令r为最大特征值与最小特征值之间的比率，即令，有；（2-12）由此可见，这个公式仅取决于特征最大值与最小值的比例r，的值在两个特征值相等的时候最小，随着r的增大而增大，因此，为了检测主曲率是否在某域值r下，只需检测（2-13）如果则舍掉，对于本文章来说，我们通常按Lowe文章中的经验值取。4、 方向分配上一步中我们确定了每幅图中的特征点，接下来要为每个特征点计算一个方向，对于每一个基于局部图像特性的关键点分配一个一直的方向，则关键点描述子就会由它的方向表示，这个方法和Schmid andMohr (1997)的方向不变描述子具有相似性。在这里，每一幅图片的特性都是由旋转不变性测量来的。关键点的尺度用来寻找高斯平滑图像L，依照这个方向做进一步的计算，对每一幅图像在某一尺度进行采样得，梯度幅值为和方向。利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。（2-14）公式（2-14）为(x,y)处梯度的模值和方向公式。其中L所用的尺度为每个关键点各自所在的尺度。至此，图像的关键点已经检测完毕，每个关键点有三个信息：位置，所处尺度、方向，由此可以确定一个SIFT特征区域。由关键点区域内的梯度方向的采样点可以形成梯度直方图。梯度直方图的范围是0360度，其中每10度一个柱，总共36个柱。随着距离中心点越远的领域其对直方图的贡献也响应减小.在实际计算时，我们在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0360度，其中每45度一个柱，总共8个柱, 或者每10度一个柱，总共36个柱。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。图2-4直方图中的峰值就是主方向，其它的达到最大值80%的方向可作为辅助方向图2-5由梯度方向直方图确定主梯度方向图2-6通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。5、 局部图像描述子首先将坐标轴旋转为关键点的方向，以确保旋转不变性。以关键点为中心取88的窗口。图2-7：16*16的图中其中1/4的特征点梯度方向及scale，右图为其加权到8个主方向后的效果。图中的左部分的中央为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，利用公式求得每个像素的梯度幅值与梯度方向，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，然后用高斯窗口对其进行加权运算。图中蓝色的圈代表高斯加权的范围（越靠近关键点的像素梯度方向信息贡献越大）。然后在每44的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点，如图右部分示。此图中一个关键点由22共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的效能，同时对于含有定位误差的特征匹配也提供了较好的容错性。计算关键点周围的16*16的窗口中每一个像素的梯度，而且使用高斯下降函数降低远离中心的权重。图2-8：在每个4*4的1/16象限中，通过加权梯度值加到直方图8个方向区间中的一个，计算出一个梯度方向直方图。这样每个特征就可以形成一个维的描述子，每一维都可以表示个格子中一个的尺度或方向。将这个向量归一化之后，就进一步去除了光照的影响。最后经过SIFT运算后得到的图像特征点如图所示： 图2-9 狗和鸟类的特征点提取2.1.2 SIFT算法的特点：SIFT特征作为局部特征，它是基于物体上的一些局部外观的兴趣点形成的，与影像的大小和旋转无关。对于光线、噪声、些微视角改变的容忍度也相当高。它的信息量大，适合在大亮点数据库中做快速准确匹配。SIFT算法的优缺点：1.SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性；2.独特性（Distinctiveness）好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；3.多量性，即使少数的几个物体也可以产生大量的SIFT特征向量；4.高速性，经优化的SIFT匹配算法甚至可以达到实时的要求；5.可扩展性，可以很方便的与其它形式的特征向量进行联合；6、缺点是SIFT特征为128维，维数高、且是不完全的仿射不变。2.2 HOG特征方向梯度直方图（Histogram of Oriented Gradient, HOG）特征是一种在计算机视觉和图像处理中用来进行物体检测的特征描述子。它通过计算和统计图像局部区域的梯度方向直方图来构成特征。 HOG特征是一种局部区域描述符,它通过计算局部区域上的梯度方向直方图来构成人体特征,能够很好地描述人体的边缘。而且它对光照变化和小量的偏移不敏感。2.2.1 36维HOG特征提取算法的实现HOG特征提取步骤如下：（1）颜色空间灰度化 在HOG算法中由于颜色信息的作用不大，所以我们通常将所要检测的图像先转化为灰度图像（即将要检测的图像看作一个灰度的三维图像）在进行HOG特征提取。（2）标准化gamma空间为了减少光照因素的影响，首先需要将整个图像进行规范化（归一化）。在图像的纹理强度中，局部的表层曝光贡献的比重较大，所以，这种压缩处理能够有效地降低图像局部的阴影和光照变化。在文中采用Gamma校正法对输入图像进行颜色空间的标准化（归一化）；目的是调节图像的对比度，降低图像局部的阴影和光照变化所造成的影响，同时可以抑制噪音的干扰；压缩图像的方法是将院图像进行（gamma）幂指数处理。即Gamma压缩公式为：（2-15）一般可以取Gamma=1/2。（3）梯度计算检测器的性能对梯度的计算方法是非常敏感的，但是最简单的方法被证明也是最好的方法。我们在一个离散导数后使用高斯平滑计算图像横坐标和纵坐标方向的梯度，并据此计算每个像素位置的梯度方向值。求导操作不仅能够捕获图像的轮廓，人影和一些纹理信息，还能进一步减弱光照对此的影响。在一幅图像中像素点(x,y)的水平以及垂直梯度为：（2-16）式中分别表示输入图像中像素点处的水平方向梯度、垂直方向梯度和像素值。像素点处的梯度幅值和梯度方向分别为：（2-17）一般来说，最常用的求梯度的方法是：首先用-1,0,1梯度算子对原图像做卷积运算，得到x轴方向（水平方向，以向右为正方向）的梯度分量的梯度，然后用1,0,-1T梯度算子对原图像做卷积运算，得到y轴方向（竖直方向，以向上为正方向）的梯度分量的梯度y。然后再利用公式（2-17）计算该像素点的梯度大小和方向。（4）为每个细胞单元构建梯度方向直方图我们将图像分成若干个“单元格（cell）”，例如一个单元格为6*6个像素。假设我们采用9个通道的直方图来统计这6*6个像素的梯度信息。那么也就是将单元格的梯度方向360度分成9个方向块。起初令方向块的每一个的值都为0，当单元格内的像素的梯度方向在某一方向块内，则这一方块的值加1。例如，如果这个像素的梯度方向是20-40度，符合直方图的第二个方向块，则直方图的第2个方向块内的计数就加一。这样，对单元格内每个像素用梯度方向在直方图中进行加权投影（映射到固定的角度范围），就可以得到这个单元格的梯度方向直方图了，就是该单元格对应的9维特征向量（因为有9个方向块）。如图所示：图2-10将360度分成9个方向块梯度大小就是作为投影的权值的。例如：某一像素的梯度方向是20-40度，假设它的梯度大小是2，那么直方图第2个方向块的计数就是加2。（5）合并细胞单元，归一化梯度直方图由于局部光照的变化以及前景-背景对比度的变化，使得梯度强度的变化范围非常大。这就需要对梯度强度做归一化。归一化能够进一步地对光照、阴影和边缘进行压缩。我们所采取的办法是：将各个细胞单元组合成一个大的、空间上连通的区域块（blocks）。在我们的实验中，一般采用Dalal提出的Hog特征提取，也就是每相邻的4个细胞单元构成一个区域块（block）。通常情况下，我们所使用HOG特征中一般都采用9个方向块，即每个细胞单元有9个特征。所以每个区域块内就有个特征向量。这样由于每个细胞单元这样，一个块内所有单元格的特征向量串联起来便能得到这个块内的HOG特征。但是这些区域块有些是相互重叠的，这也就意味着：每一个单元格的特征会以不同的结果，重复出现在最后的特征向量中。我们将归一化之后的块描述子（向量）就称之为HOG描述子。（6）合并HOG特征将各个区域块中的特征描述子串联起来就可以得到该图像的HOG特征描述子，即最后的HOG特征向量。例如一副64*128维的图像，以8个像素点为步长，那么在该图像的水平方向将会有8个扫描窗口，垂直方向将会有16个扫描窗口，则该图像所能得到的HOG特征向量为8*16*36，共有8*16*36=4608个特征。图像36维HOG特征示意图如下： 图2-11 狗和鸟的36维HOG特征2.2.2 HOG特征的降维在本实验中，我们采用的是31维的HOG特征。这一特征是从大量各种分辨率的图片中收集了很多36维的HOG特征，并在这些特征向量上进行主成分分析（PCA）分析得来的。图2-12展示了分析出的主成分，从中我们发现了很多有趣的现象。图2-12HOG特征的PCA分析。由图2-12可以看到，每个特征向量(eigenvector)都显示为的矩阵，所以每一特征向量的一行对应一个归一化因子，每一列对应一个方向块。每个特征向量所对应的特征值在特征向量上方。由前11个主特征向量所定义的线性子空间基本上包含了HOG特征的所有信息。注意到，所有主特征向量沿着其矩阵表达的行或列是定值。由前11个主特征向量(eigenvector)所定义的线性子空间基本上间包含了HOG特征的所有信息 。实际上，我们用起初的36维特征以及向主特征向量投影所得到的11维特征在目标分类上所得到的结果都差不多。而且使用低维特征可以产生参数较少的模型，并且能够加速学习和检测算法。但是由于在计算特征金字塔的时候需要相对比较耗时的投影步骤，这就减少了获得的加速优势。36维的HOG特征向量是来自4个不同的归一化的9维方向直方图，所以36维的HOG特征向量也可以很自然地看做一个的矩阵。而在图2-12中的主特征向量中，有一个非常特殊的结构：它们沿其矩阵表达的行或列(近似)是定值。所以主特征向量所依赖的线性子空间可由沿其矩阵表达的某一行或列为定值的稀疏向量定义。令，其中和都是36维向量，其的矩阵表达式满足下列条件：（2-18）（2-19），例如，定义一个13维向量，其中的元素是36维HOG特征与每个和的点积。HOG特征向每个的投影并通过计算对应方向的4个归一化值的和(即矩阵表达的某列的和)来获得，HOG特征向每个的投影通过计算对应归一化方法的9个方向值的和(即矩阵表达的某行的和)来获得。(注：13维特征并不是36维特征向量V的线性投影，因为和不是正交的。事实上，由V定义的线性子空间的维数是12)使用11维PCA特征和使用36维HOG特征或由V定义的13维特征进行图像分类可以获得同样的性能表现。然而，由于和是稀疏向量 ，所以计算由V定义的13维特征比计算向PCA主特征向量的投影要简单的多。此外，13维特征有还可以看做是9个方向特征和反应单元格周围区域的梯度能量的4个特征。我们也可以定义对比度敏感的低维特征。我们发现有些目标类别适合使用对比度敏感特征，有些目标类别又适合用对比度不敏感特征。所以在实际中我们既使用对比度敏感特征又使用对比度不敏感特征。设C是聚合有9个对比度不敏感方向的像素级特征映射而获得的基于单元格的特征映射，D是聚合有18个对比度敏感方向的像素级特征而获得的基于单元格的特征映射。定义C和D的4种归一化因子。可以获得一个4*(9+18)=108维的特征向量F(i,j)。实际中我们使用的是此108维向量的一个解析投影，此投影由下面几个统计量定义：27个在不同归一化因子上的累加和(即列的和)，F中的每个方向通道对应一个；以及4个在不同方向(9维对比度不敏感方向)上的累加和(即行的和)，每个归一化因子对应一个。最终的特征映射是31维向量 G(i,j)，其中27维对应不同的方向通道(9个对比度不敏感方向和18个对比度敏感方向)，其中4维捕获(i,j)周围4个单元格组成的block的梯度能量。形成31维特征向量的解释图如图：图2-13 31维特征向量解释图下图为利用31维HOG特征所提取的狗和鸟的图像特征示意图： 图2-14 狗和鸟的31维HOG特征2.2.3 HOG特征优缺点：与其它的特征描述方法相比，HOG有很多优点。1、 HOG表示的是边缘梯度的结构特征，因此可以用来描述局部形状信息；2、 HOG特征在位置和方向空间的量化，在一定程度上可以抑制图像旋转和平移所带来的影响；3、 HOG特征将局部区域也归一化成直方图，这样可以减弱光照变化所带来的影响；4、 由于在HOG特征中可以忽略光照对图像的影响，使得图像所需要表示特征的数据位数降低；5、 由于HOG特征有将数据进行分块和分单元格的处理方式，使得图像的局部像素点之间的关系得到很好的表达。HOG的缺点：1、 HOG的特征描述子生成过程比较长，这样就使得提取特征的速度较慢，实时性差；2、 HOG特征很难处理遮挡的图像；3、 由于梯度自身的性质，HOG特征对噪声比较敏感。2.3 小结HOG及SIFT算法都是局部特征，其中Hog没有旋转和尺度不变性，因此计算量小；而SIFT中每个特征需要用128维的向量来描述，因此计算量相对很大。对于两种不同的底层特征，各有其自身优势。所以我们选用这两个特征作为本实验的底层特征。3、 中层特征目前，基于局部特征的模型在视觉目标分类中都取得了较好的结果。而中层特征就是利用这些原始的图像的特征向量将其进行整理，以使原始图像的局部特征向量更具有代表性，能更好的实现目标分类。在这一章中，我们重点介绍了我们所使用的中层特征有：词包（BoW）模型以及高效匹配核函数（EMK）模型。具体介绍见下文。3.1 BoW（Bag of Word）模型BoW模型的全称为Bag of Words，早先是为了处理文本数据而在文本处理领域提出的一种简单有效的分类方法。由于其简单易行的原理，图像分类领域中也开始使用这种分类模型。本节我们将对BoW这一经典模型的概念以及具体实现进行详细的阐述。由于图像可以类比为文档(document), 图像中的单词(words)可以定义为一个图像块(image patch)的特征向量. 那么图像的BoW模型即是 “图像中所有图像块的特征向量得到的直方图”。将图像表达为BoW模型的类似于图像3-1：图3-1 对于图像的BoW模型表示示意图BoW的关键之处在于将局部特征描述子映射到一个新的特征空间空间中去，而这个特征空间的基础就是视觉单词所组成的向量。在新的映射空间中，一副图片中的局部特征向量被转换成了一组新的向量。而在做图像匹配时，可以由欧几里德距离等来计算。BoW模型在图像分类中的具体实现的流程示意图如图：图3-2：BoW模型在图像分类中的具体实现的流程示意图建立BoW模型主要分为如下几个步骤:1. 特征提取假设共有N张图像, 第i张图像图像由n(i)个图像块组成, 即可以用n(i)个特征向量来表达这张图像。则所有图像的的特征向量的总和就是BoW的单词。特征向量可以根据特征问题自行设计, 常用特征有Color histogram, SIFT, LBP等.在第二章中，我们已经讲述了我们所用来提取特征的算法为SIFT特征算法以及HOG特征算法。这里不再叙述。2. 生成字典/码本(codebook)在提取完图像的特征向量后，我们接下来的任务就是要将这些特征向量转换成能够表示为图像的“关键词”，并将全部关键词结合起来完成码本的构建。为了能够得到码本，我们将第一步中所得到的特征向量进行聚类。在文章中，我们使用的聚类方法是K-means聚类方法。K-means聚类算法是最简单的一种聚类算法。由于简洁和效率，K-means聚类算法成为人们最广泛使用的聚类算法。它在一个给定数据点集合和需要的聚类中心数目k（k由用户指定）的情况下，根据某一个距离函数，反复的把数据分入到k个聚类中心中去。K-means聚类算法的一般步骤是：（1）在给定对象集合的情况下，随机选取k个值作为起始的聚类中心。注：这个过程大多数情况都是采用随机选取的办法，或者针对不同的聚类情况选取特定的聚类中心；（2）计算每个聚类对象到各个聚类中心的距离，将每一个对象归类到离它最近的那个聚类中心。聚类中心及所分配给它的对象就表示一个聚类；（3）当对象集合中的所有对象都被分配给某一个聚类中心时，每个聚类的聚类中心就会根据它所被分配的对象被重新计算；（4）由于K-means聚类的结果过度依赖于初值的选取。我们不能保证在每一次的聚类中都会取得收敛到全局的最优解的。因此是用新的聚类中心，重复第二步，一直到迭代到聚类中心基本不在变化为止。3. 根据码本生成直方图将K-means聚类中每个聚类中心及被分配给该聚类中心的对象转化成直方图，这样就可以得到该图片对应于该码本的BoW表示。聚类过程的示意图如下：图3-3：聚类过程示意图3.2 EMK（Efficient match kernel）高效匹配核函数（EMK）方法是一种特殊的核函数方法，所以在介绍EMK之前，我们要先知道什么是核函数方法，核函数方法可以用来解决不同维数集合的匹配问题。它可以用来解决在将低维线性不可分空间通过非线性映射到高维特征空间中实现线性可分的时候所带来的在高维空间中位数过高问题的一种方法。核函数方法使得高维空间的特征位数减少，大大的减少了计算量。它是除了BoW之外另一种计算局部无序特征相似性的方法。核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法。而论文6也证明了BoW也可以看做是一个特殊视觉核函数。通常情况下，核函数方法都需要明确的求出所有核函数的矩阵，因此它们需要的空间以及时间复杂度是图片数量的二次方。而高效匹配核函数（EMK）这一结合了BoW和核函数集合的方法就被提了出来。我们将图像的局部特征映射到低维度的特征空间中去并且通过平均这个结果特征向量构建一个特征层集合。所以EMK不需要计算全部的核函数矩阵，这就使得在有大量的图片进行处理时，它的时间以及空间复杂度都是线性的。3.2.1 核函数框架目前，基于局部特征的模型方法在许多视觉目标识别实验中都取得了很好的结果。对于一幅图片，它可以由其块中所提取的局部特征集合来表示。由于不同图像所提取的局部特征集合不一定相同，因此在匹配过程中，如何将这写局部特征集合所有的技术不同的图片进行匹配就成了一个需要重点决定的问题。核函数方法是就用来解决不同维数集合图像的匹配问题的。对于具有不同模的图像集合X和集合Y，我们可以使用公式(3-1)来进行集合的匹配过程：(3-1)基于数学中的封闭属性，我们可以确定只要是正定的，则就是一个正定的核函数。为了方便起见，我们将看做是一个局部核函数，我们可以看到这个核函数在计算的过程中，需要计算所有的匹配函数的和，也就是说，对于一个由向量定义的单独的核函数的来说，它的计算复杂度是而不是O(1)这就使得这个核分别花费和度来存储和计算所有的核函数矩阵。其中n为训练集中的图像数目，d是描述子的维数，m是所有集合的平均基数。对于图片分类来说，m可以是成千上万个单元，因此，它的计算花费能够以n的四次方的形式快速增长。核函数方法除了在训练时需要花费很高的代价外，它在测试方面所花费的代价也是非常高的。对于一些稀疏的核函数分类方法，它在各个方面所花费的代价在一定程度上能够得到降低，但是由于稀疏的层数往往都会随着n线性增长，所以还是不会改变其其复杂度。3.2.2 用核函数的方法重新审视BoW在监督类图像分类中，我们给出了图片的训练集合以及这些图片所对应的标签。我们的目的就是为了训练一个分类器，使得我们能够标注出那些看不到的图像。我们就采用了特征包的方法。令，分别为图片、的局部特征集合。为词表，即视觉单词的集合，其中为词表大小。是基于词典的的编码系数向量。在BoW中，每一个特征向量都被量化到D维的二进制向量中去，在通常情况下采用硬性分配，令，则有当时的值即为1，否则为0。即如下公式：（3-2） 由公式（3-2）我们可以知道，很明显是一个正定函数。而且会被分配到此表中与其最近的词汇。在稀疏编码中，匹配的整个过程都是与公式（3-2）相似，除了它不仅仅是属于稀疏编码中的一个基础，也就是说在中，不仅仅只有一个元素是非零的。对于图片的直方图，我们可以将其看成在公式（3-2）中，稀疏编码中的对于的一种合并求和的方法。即为：（3-3）在实际的许多应用中，一幅图片的表示并不是我们所要求的最终结果，而是为了得到在图像匹配的过程中所需要图片之间的相似性。为了比较图片之间的相似性，我们一般会采用计算直方图之间距离的方法。假设图片以及它们的直方图，一般来说，最常见的匹配方法就是计算的直方图之间的欧几里德距离。那么和之间的距离表示如下：（3-4）在公式（3-4）中，如果我们采用内积的方法来代替欧几里德距离，则公式（3-4）会转化为如下形式：（3-5）也可以将公式（3-5）写成（3-6）其中，并且。这就将BoW看成核函数方法的过程。3.2.3 EMK的实现过程在核函数方法的实际应用当中，我们在3.2.1节中已经知道，公式（3-1）对于核函数矩阵的计算复杂度是，其中n是训练集中图片的张数，d是描述子的维数，m是所有集合的平均基数。它的昂贵的计算代价阻碍了核函数方法在一些大数据集中的应用。由于受到公式（3-6）的启发，如果在公式（3-1）中我们使，那么公式（3-1）就会变成如公式（3