多特征编码融合的图像分类研究∗

胡湘萍，代江华

(1.河南经贸职业学院计算机工程学院，河南 郑州 450018；2.长江大学计算机科学学院，湖北 荆州 434023)

图像分类是计算机视觉与模式识别领域的重要研究课题之一，其研究目标是为了给一幅图像赋予某一类标签。随着电子产品的日新月异及普及，获取图像已经变得越来越容易，大量的图像需要有效地分类与管理，因而，图像分类被应用到不同的领域，如视频监控、网络图像分析、生物信息学等。虽然经历了十几年的发展，图像分类仍然面临着以下几个方面的困难[1]:(1)由于光照变化、拍摄角度不同、遮挡等因素，同一类别的物体往往在图像上的表现形式大不相同；(2)即使是同一类别的物体，其外观、形态等表现形式也存在很大的差异；(3)在很多情况下，需要考虑图像中不同物体之间的上下文关系或者物体与背景之间的依存关系，缓解单个物体时对赋予类别的不确定程度。

基于词袋(Bag-of-Words，BoW)模型(又被称为特征袋(Bag-of-Features，BoF)模型)的图像表示方法是图像分类研究中应用最广泛同时也是最有效的体系框架之一[2]。文献[3]将词袋模型划分为五个步骤:(1)划分图像块。该过程以整个图像作为输入，其输出为图像块，即将整幅图像划分为大小相等的小图像块，以用于后续处理。在对图像划分的过程中可以采用密集采样方式或者稀疏采样方式，两种不同的采样方式对分类准确度和计算代价都有一定的影响。一般而言，密集的采样方式有助于提高图像分类准确度，但需要更多的计算资源。(2)特征表示。对上一步得到的图像块给出恰当的表示，常用的特征表示有:图像的颜色直方图[4]、纹理特征[5]、SIFT 特征[6]等。(3)生成字典。图像分类的词袋模型来源于文本分类[7]，其本质是统计相关特征出现的频次。字典的生成通常通过聚类算法实现，最常用的是K均值聚类。字典中的每个元素被称为视觉词(visual words)。(4)特征编码。用于分类的图像大小、特征数量并不完全相同，因此，需要将图像特征结合字典进行编码，将图像表示为字典中相应视觉词的出现频次。特征编码方式有很多，常用的有:硬编码[2]、软编码[8]、稀疏编码[9]等。(5)特征联合(features pooling)。软编码和稀疏编码得到的是编码矩阵，需要将编码矩阵表示为单个直方图来对整个图像进行描述。在此步骤之后，所有图像拥有相同维度的直方图表示，方便图像之间的相似性比较和判定。常用的特征联合方法有:平均联合(average pooling)和最大联合(max pooling)。

将图像划分为多个图像块有两个方面的优势:(1)在一定程度上缓解物体遮挡和复杂背景对图像分类任务造成的困难；(2)在一定程度上弥补对图像采用直方图表示而丢弃了图像的空间信息的不足。

不可否认，基于词袋模型的图像分类框架取得了很大的成功，但是，仍然存在一些仍需解决的难题:(1)字典的构造对分类性能有一定的影响，字典的最佳表示方式仍然没有公论；(2)图像特征的选择、图像划分时的采样策略、特征编码方式等因素都会对分类性能产生一定的影响。一般来说，在词袋模型中字典越大，表示图像的直方图维度就越高，直方图的判别性就越强，因而分类准确度也越高。然而，字典越大，需要更多的计算资源和存储资源，这对于大数据场景下变得很不适用。因此，对于词袋模型来讲，需要在分类准确度和计算资源之间取一个恰当的折中。

本文的研究目标是通过对多个小字典下获取的特征编码，以一种在线加权融合的方式进行融合，使得融合后的结果与大字典下获取的特征编码一样具有较强的判别性，即具有较高的分类准确度。与传统的词袋模型方法不同的是，本文通过在线学习的方式加权融合由多个小字典获取的特征编码，用于图像分类任务。与传统的词袋模型方法及近年主要研究成果相比，在采用相同的字典学习方法和特征编码方式的情况下，本文方法能够获得与采用大字典的词袋模型方法类似的分类准确度，同时，所需的计算资源和存储代价更小。

1 本文方法

本文方法大体上可以分为三个层次。第一层是字典生成过程，与传统的词袋模型不同的是，本文方法在这个过程中生成多个小字典而不是一个大的字典。第二层是特征编码层，在这一层本文采用硬编码(hard coding)，将每幅图像表示为多个低维直方图，并对不同字典下得到的直方图采用直方图交核(histogram intersection kernel)构建相应的核矩阵。第三层采用在线学习方法对不同字典下的直方图交核进行加权融合，获得加权之后的核矩阵。最后，用简单的分类器，如支持向量机(SVM)等，对图像进行分类。本文的总体框架如图1 所示。

图1 本文方法总体框架图

1.1 字典生成

对每一幅图像，我们以密集采样方式提取图像的尺度不变特征变换(Scale Invariant Feature Transform，SIFT)特征。以行列每隔3 个像素进行采样，将图像划分为像素且有部分重叠的图像块。对每个图像块，采用与文献[6]相同的方式构建图像像素梯度直方图的SIFT 描述符，特征表示为F＝(f1，…，f16)，其中16 为图像被划分的图像块的个数，F为128 维的SIFT 特征。SIFT 特征提取的是图像的局部特征，为了能够处理物体尺度的变化，在本文中在尺度空间理论(scale-space theory)[10]指导下，使用多个不同协方差的高斯函数对图像块进行平滑。

提取图像特征之后，本文使用K均值聚类算法生成字典。选取K均值聚类算法源于其存在如下优点[11]:(1)时间复杂度和空间复杂度相对于数据样本个数而言是线性的；(2)算法确保收敛，且收敛速度为二次的；(3)其聚类结果不依赖于数据样本的排列顺序。其中，时间复杂度和空间复杂度是图像分类研究领域中需要重点考虑的因素之一，尤其是在大数据或者实时应用需求环境下。

在这一层中，对于不同大小的字典，可以运行K均值算法多次，每次设定不同的聚类个数K；倘若需要的字典大小相同，可以通过输出K均值聚类过程不同阶段的结果作为相应的字典。本文实验中，仅给出了第一种方式获取图像集的字典。

1.2 特征编码

特征编码在图像分类任务中起着关键性的作用，文献[12]的研究表明，在稀疏编码框架下对图像进行分类，编码策略比字典学习更为重要。本文考虑的虽然是在词袋模型下进行图像分类，特征编码仍然是关键因素。

硬编码[2]策略是对图像的每个特征赋予字典中其对应的最近距离的视觉词，然后统计字典中每个视觉词被赋予的特征个数。编码结果则为归一化的上述统计直方图。

由于词袋模型丢弃了图像的空间信息，空间金字塔匹配模型[13](Spatial Pyramid Matching，SPM)在一定程度上弥补了空间信息的丢失，因此，本文在特征编码阶段应用空间金字塔匹配模型。SPM 以一种简单的方式将图像由粗到细划分为不同金字塔层的多个子区域，不同层次不同区域的图像特征单独编码，从而形成维度更高的直方图图像表示。本文将图像划分为3 个层次，每个层次的子区域为2ℓ×2ℓ，ℓ＝0，1，2。金字塔的第一层为最粗划分，是整个图像，最细层将图像划分为22×22＝16 个子区域。经过3 个层次的金字塔划分之后，最终得到的图像直方图维度是字典大小的21 倍。

式中:i，j分别为Ii和Ij的索引，mt为第t个字典的视觉词个数。因此，在特征编码层中，我们既可以直接输出图像的特征编码直方图，又可以输出对应的直方图交核集合K＝，其中d是第一层生成的字典个数。本文采用直方图交核集合作为这一层的输出结果。

1.3 加权组合

上述讨论得知，在第二层已经获取了直方图交核集K＝由于不同字典对图像分类任务的贡献大小不相同，因此，需要给相应的直方图交核赋予不同的权值，即

本文加权融合的目的是使得相同类别标签的图像相似性程度要高于不同类别标签的图像。理想情况下，希望权值向量η能够满足如下要求

即，

式中:Γ＝{(i，p，n)｜yi＝yp，yi≠yn}是图像索引三元组，yi是图像Ii的类别标签。

在实际应用场景下，公式(3)所示的理想条件不可能完全满足，于是，允许小部分图像违背该条件。类比于SVM 软分类情形，本文引入松弛变量ξipn≥0，公式(3)的软条件可表述为

公式(4)中的ξipn可以看作是对不满足限制条件(3)的惩罚项或损失项。在公式(4)的表述下，我们希望总损失值应该 最小，即∑i，p，n ξipn应 该最小。因此，类比于SVM，我们将上述限制条件和目标函数表示为二次限制优化问题:

目标函数中项‖η‖2是正则化项，其目的在于避免过拟合现象的发生，常数C是为了权衡经验损失∑i，p，n ξipn和正则化项‖η‖2。

二次优化问题(5)可以由数学优化软件直接求解，如Libsvm[15]，Mosek[16]等。然而，直接求解优化问题(5)其计算复杂度通常是O(n3)，其中n是数据样本的个数。因此，直接使用优化软件求解二次优化问题(5)对于图像分类任务并不适用。本文采用通过对数据采样在线学习加权权值η，下一节将进行详细介绍。

2 在线权值学习

本文采用OPA(Online Passive-Aggressive)算法[17]来求解上述二次优化问题(5)。OPA 算法是基于数据采样的在线学习算法，该算法的目标函数需要取一个折中，这个折中是在当前训练数据下损失函数最小和当前迭代参数与上一次迭代参数距离最小之间实现。

我们定义三元组(i，p，n)的损失函数如下:

由1.3 节讨论知，我们的目标是使得总损失函数在所有采样的三元组(i，p，n)下最小，即∑i，p，nL(η)要最小。

类似于文献[18]，我们将上述二次优化问题(5)转化为OPA 在线学习问题，

于是，在每一次迭代i，权值参数ηi的取值需要在是否与上一次迭代权值ηi－1距离很近和在当前采样三元组下使得损失函数L(η)之间进行折中。

公式(7)同样是一个限制条件下的二次优化问题，为了求解该问题，我们定义其拉格朗日(Lagrange)函数如下:

其中，拉格朗日乘数子τ≥0，λ≥0。上式对参数η求偏导数，并令偏导数等于零，可得

式中:κ(i，p)＝[K1(i，p)，…，Kd(i，p)]为直方图交核对应元素组成的向量，t＝1，…，d是字典索引。由此，新一次迭代时，加权参数η的更新表达式为

同样，t＝1，…，d是字典索引。至此，我们仍需要确定参数的取值。

进一步，令拉格朗日函数对参数ξipn求偏导数，有

已知参数λ≥0，因此，τ≤C。

更进一步，将公式(8)和公式(9)代入到拉格朗日函数中，对参数τ求偏导数，并令其为零，有

于是，我们可得参数τ的取值

式中:L为公式(6)中的损失函数。

由公式(9)，我们可以确定参数τ的取值为

综上所述，算法1 总结了本文采用OPA 算法进行在线权值学习的过程。该算法给出了权值更新的闭式解，在计算效率上有很大的优势。

算法1 基于OPA 算法的在线权值学习

3 实验结果及分析

为了验证本文算法的有效性，我们在两个图像集上进行试验验证，这两个数据集是:Caltech－101数据集[19]和Scene－15 数据集[13]。对于特征提取，我们使用开源软件包VLFeat[20]按照1.1 节所述方式提取密集的SIFT 特征；在训练分类器阶段，我们使用LIBSVM[15]软件包，使用预定义的核矩阵选项和默认的多分类选项。对于1.1 节生成的多个字典，实验中使用K均值算法生成3 个字典，设定字典大小分别为50，100，150。对算法1 中的三元组采样，设置采样总数为105，即在训练数据中随机(可重复)采样105个三元组对权值η进行更新。在词袋模型[2]中，我们设定其字典分别为400，1 000和4 000 分别进行对比实验。另外，本文方法还与SPM[13]方法、软编码[8]方法以及基于稀疏编码的LLC[21]方法进行了实验对比，这三个方法的实验结果是对其论文的直接引用。为了实验的公平性，所有实验均运行10 次，取其均值和方差作为最终对比结果。下面对两组数据集的实验结果分别进行叙述。

3.1 Caltech－101 数据集

Caltech－101 数据集包含了101 个图像类别(不包括背景类)，每个类别包括的图像数目从31 个到800 个不等，整个数据集包含8 677 幅图像，平均分辨率为300 pix×300 pix。在本文实验中，我们在每个图像类别中随机选取15 幅图像和30 幅图像作为训练集，进行两组实验。

图像分类准确度结果如表1 所示，表中的词袋模型为我们采用3 层金字塔匹配模型实现的经典词袋模型[2]，该实验使用本文方法一样的特征和编码方式。词袋模型后面括号里的数字表示对应的字典大小，如词袋模型(400)表示采用字典大小为400的词袋模型实现。实验结果部分后面括号里表示的是相应算法在10 次运行过程中分类结果的方差。

表1 的实验结果表明，在Caltech－101 数据集上，对于词袋模型而言，字典大小的不同对图像分类结果的影响比较大，虽然直观上来说，字典越大，其字典包含的图像内容越精细，分类准确度也通常会越好。然而，从表1 看到，字典大小为400 时，在每类30 个训练图像下，其分类准确度为72.02%，略高于字典大小为4 000 时的71.24%。这个现象很可能是因为K均值聚类算法在获取字典时的随机性造成的。本文提出的图像分类方法取得了最佳的分类准确度。与稀疏编码[21]方法相比，本文算法同样取得较高的分类准确度。

表1 Caltech－101 数据集图像分类准确度对比

图2 给出了本文算法在Caltech－101 数据集采用随机选取30 幅图像作为训练集时的混淆矩阵图像表示，图3 给出了通过在线权值学习之后得到的直方图交核图像表示。

图2 本文算法在Caltech－101 上的混淆矩阵

图3 在线权值学习后的直方图交核图像

从图2 可以看到，本文提出的图像分类方法得到的结果主要集中在混淆矩阵的对角线上，非对角线上的值相对于对角线来说是很小的一部分。图3给出了所有的8 677 幅图像构建的加权直方图交核图像显示，该图显示出了明显的块效应，因此，在一定程度上表明基于OPA 的加权组合能够使得相同标签的图像具有更高的相似性。

3.2 Scene－15 数据集

Scene－15 数据集包含15 个自然场景图像，这些场景分别是CALsuburb，kitchen，living room，bedroom，store，industrial，MITcoast，MITforest，MIThighway，MITinsidecity，MITmountain，MITopencountry，MITstreet，MITtallbuilding 和PARoffice。每个场景包括200 到400 幅图像，图像的平均分辨率为300 pix×250 pix，整个数据集拥有图像4 485 幅。在该数据集上，我们在每个场景类别中随机选取100 幅图像作为训练集，剩余的图像作为测试集。

表2 给出了该数据集下的图像分类结果，由此表同样可以看到本文算法在图像分类准确度上的优势。图4 给出了本文方法在该数据集上的混淆矩阵，对角线上的数值表示对应类别上的分类结果。

表2 Scene－15 数据集图像分类准确度对比

图4 本文算法在Scene－15 上的混淆矩阵

表2 的分类准确度对比中，本文方法为82.10%略低于词袋模型在字典为4 000 时的82.55%，均高于其他对比方法。从图4 可以看到，对于CALsuburb 类别的平均分类准确度可以达到99.81%，最低的分类结果为类别industrial，其分类结果也达到了71.23%。

3.3 复杂度分析

词袋模型的计算复杂度是由图像特征提取、字典生成、特征编码和训练等部分组成。本文方法与传统的词袋模型相比，在字典生成过程需要更多的K均值聚类次数，而K均值聚类算法的计算复杂度为O(kNd)，其中k是聚类的类别个数，n为数据样本个数，d为数据样本的维度。因此，在字典生成过程中，字典越大，需要的计算资源就越多。在本文的实验中，词袋模型若采用字典大小4 000，则在字典生成过程相比于本文方法大约需要10 倍的计算时间。

在特征编码阶段，由于均采用硬编码策略，在查找最近邻过程，其计算复杂度为O(kNd)，其中，k是字典大小，N是图像特征个数，d为图像特征维度，本文采用SIFT 特征，故d＝128。同样，相比而言，字典越大，其需要的计算资源也越多。

表3 给出的是在Caltech－101 数据集上的计算时间比较，这些结果是运行在PC 机环境使用单线程获取的。PC 机的配置如下:Intel Core i5 四核CPU，主频为3.4 GHz，内存为8GB，Windows 7 64 位操作系统，MATLAB2012b 开发环境。

表3 Caltech－101 计算时间比对 单位:s

从运行时间来看，在字典生成阶段，本文由于需要3 次运行K均值算法，因而在计算时间上略高于字典大小为400 的词袋模型方法。另外，在特征编码方面也略高于字典大小为400 的词袋模型方法，这可能是本文方法在查找最近邻视觉词时，同样需要运行3 次查找算法的缘故。从该表看到:改进的OPA 算法的运行时间仅为13.58 s，相比于特征编码，其运行时间不足1%。

同理，存储代价同样与字典大小呈线性关系，字典越大，其所需的存储代价也越高。因此，在词袋模型中，组合多个小字典既可以减少计算复杂度又可以减少存储代价。

4 结束语

一般而言，基于词袋模型的图像分类算法，其用于特征编码的字典越大，图像分类准确度就越高，但同时也需要更高的计算资源和存储代价。本文的研究目标是通过在线组合多个在小规模的字典下的特征编码，以期其达到与大规模字典特征编码相同的图像分类准确度。

本文方法基于词袋模型，在字典生成阶段生成多个小字典而不是通常的大字典，并采用相应的特征编码方式。在组合多个字典特征编码时，以加权的方式对相应的特征编码进行融合。在特征融合阶段，本文改进了OPA(Online Passive-Aggressive)算法，得到了权值更新的闭式求解方式。实验结果表明，本文方法在分类准确度上与当前主流方法不相上下，但在计算时间和存储代价上更具优势，因此，验证了本文方法的有效性。