近年来, 科学技术的迅猛发展带来了图像数据的爆炸性增长。如何在庞大的图像数据库中, 快速而准确地对图像信息进行分类识别至关重要, 这也是近几年科研人员研究的热点^[1-14]。

Joachims^[2]为了解决文本分类问题, 于1998年提出词袋(bag of words)模型, 跨入21世纪以来, 国外的研究者开始着手在场景识别领域使用词袋模型。2004年Csurk^[3]等首次将词袋模型应用在场景识别中, 相比于以前的场景识别算法, 该算法具有更好的准确率, 但是忽略了特征的空间信息。2007年Svetlana Lazebnik等^[4]将空间金字塔的词袋模型引入到了场景分类的应用中, 该算法模型克服了传统的词袋模型忽略特征的空间信息的缺点, 准确率得到了进一步提升; 缺点是不适用于高维特征, 且其没有充分利用局部特征在特征区间的结构特性。2010年陈海林等^[5]提出了基于双空间金字塔匹配核的图像分类算法, 他们首次利用了局部特征在特征空间和图像空间建立金字塔模型, 相对于单空间金字塔的图像分类其准确度有所提高, 但是分类的时间效率较低。2016年, 华南农业大学的薛昆南等^[6]提出了基于卷积词袋网络的视觉识别算法, 该算法首次运用了深度学习的思想, 其结合了卷积神经网络强大的特征学习能力, 提高了分类的准确度。但是其对于运算的平台有相当高的要求, 并且需要进行大量的线下训练以得到一个匹配的卷积模型, 另外时间效率较低。已有的图像分类算法精确度还无法满足实际的图像分类需要, 为此提出了一种基于改进的空间金字塔词袋模型的图像分类算法。首先针对原K-means算法的易陷于局部最优化的缺陷^[7], 在正式开始K-means算法之前先随机从所有数据指定一个初始聚类中心, 然后再运用轮盘法依次获取剩下的K-1个中心点, 最后将获得的K个聚类中心点投入到标准的K-means算法中继续聚类; 其次把支持向量机将可能产生非常严重的过拟合结果径向基核函数替换成新的核函数, 即直方图交叉核函数^[8]。通过仿真验证比较分析, 改进算法的准确率明显高于原基于空间金字塔词袋模型的图像分类算法。

1 词袋模型

传统的词袋模型主要分为3个步骤:特征提取与描述、K-means聚类、支持向量机^[9]。基于词袋模型的场景分类流程如图 1所示。

1.1 特征提取与描述

特征提取分为特征检测与特征描述两部分。特征检测用于确定特征在图像中的位置, 特征描述一般采用特征向量对该特征所在的局部区域进行描述。SIFT特征检测算法由D.G.Lowe^[10]在1999年提出, 该算法对平移、旋转、光照和噪声均具有不错的鲁棒性。SIFT特征提取过程如图 2所示。

本文采用的Dense SIFT跳过了经典的SIFT前3步, 即直接指定关键点位置和描述子采样区域, 计算SIFT特征。

1.2 空间金字塔

空间金字塔出现的背景是词袋模型被大量地用在了图像分类中, 但是传统的词袋模型完全缺失了图像特征点的空间位置信息。空间金字塔意将图像分成若干块, 分别统计每一子块的特征, 最后将所有块的特征拼接起来, 形成完整的特征。在分块的细节上, 采用了一种多尺度的分块方法, 即分块的粒度越大越细, 呈现出一种层次金字塔的结构。按照词袋模型相同的方法构建包含M个字的词典, 利用图像金字塔把图像划分为多个尺度的块, 然后计算落入每个块中属于不同类别的词的个数, 把所有尺度下的直方图特征连接起来组成一个作为分类的特征向量, 放入支持向量机中进行训练和预测。

2 K-means算法

K-means算法是一种无监督聚类算法, 在20世纪60年代被提出^[11]。该算法的基本思想是在m维欧几里得空间依据提前设定的阈值将n个数据划分到K个类中, 并且同一类别的数据之间的相似度较高, 而不同类别的数据相似度较低^[12]。假设需要聚类的数据集S=(x₁, x₂, ..., x_n); K个聚类中心为(c₁, c₂, ..., c_k)。默认计算两个样本之间距离采用的是欧氏距离, 具体如式(1)所示。

$ d\left( {{x_i},{x_j}} \right) = \sqrt {{{\left( {{x_{{i_1}}},{x_{{j_1}}}} \right)}^2} + {{\left( {{x_{{i_2}}},{x_{{j_2}}}} \right)}^2} + \cdots + {{\left( {{x_{{i_m}}},{x_{{j_m}}}} \right)}^2}} $

(1)

计算所有样本点的平均值的计算方法为

$ {\rm{Meandist}}\left( S \right) = \frac{2}{{n\left( {n - 1} \right)}} \times \sum\limits_{i \ne j,i,j = 1}^n {d\left( {{x_i},{x_j}} \right)} $

最常用的目标函数为平方误差准则函数, 其定义为

$ E = \sum\limits_{i = 1}^K {\sum\limits_{j \in {N_i}} {{{\left\| {{x_j} - {c_i}} \right\|}^2}} } $

式中:N_i表示第i个簇集合, C_i表示第i个簇的中心, E表示所有数据样本对象与它所属的聚类中心的欧氏距离的平方和。

K-means聚类的具体步骤如下:

1) 首先预给定聚类数目K, 然后从所有的数据中随机选择K个数据, 将其作为初始的聚类中心。

2) 计算剩余的所有数据到K个聚类中心点的距离, 根据相似度最小原则, 将其划归到相应的类别中。

3) 对于每一个类, 计算该类内所有数据的平均值, 并将其作为新的聚类中心。

4) 判断是否达到迭代结束的条件, 如果达到则迭代结束。否则返回到步骤2), 继续迭代。

K-means算法迭代结束的条件:

1) 簇不发生变化。

2) 前后两次迭代的目标函数值小于设定的某个阈值。

3) 迭代超过一定的次数。

满足上述3个条件中任意一个即可以结束迭代, 满足条件1)或者2), 则表明簇收敛。

K-means算法对于大数据的处理来说算法的速度很快, 但缺点也很明显。其一, K值需要预先给定, 而通常实际并不知道数据分为多少个类比较合适, 只能凭借经验设定, 因而算法的结果存在不确定性。其二, 算法对初始选取的聚类中心点是敏感的, 不同的初始随机种子点其聚类结果可能相差甚远。

针对缺点二, 本文提出一个基于轮盘法的改进的K-means算法。具体步骤如下:

1) 在所有数据中随机选取一个点作为第一个聚类中心点。

2) 计算每个样本与当前所有聚类中心点的最近距离, 用D(x)表示, 接着计算每个样本被选为下一个聚类中心点$\frac{{D\left( x \right)}}{{\sum\limits_{x \in X} D {{\left( x \right)}^2}}}$的概率。最后按照轮盘法规则选取下一个聚类中心点。

3) 重复步骤2)直至找出K个聚类中心点。

4) 代入经典的K-means聚类算法的第2)~4)步骤。

轮盘法又称为比例选择算子, 其基本思想是个体被选中的概率与其适应度函数成正比。整个原盘代表是概率和1, 每个小部分代表的是不同的数据点被选为聚类中心点的概率, 距最近中心点距离越远, 被选为下一个中心点的概率也就越大, 这克服了聚类容易陷于局部最优化的问题。设群体大小为n, 个体i的适应度为F_i, 则个体i被选中的概率为

$ {P_i} = {F_i}/\sum\limits_{i = 1}^n {{F_i}} \left( {\sum\limits_{i = 1}^n {{F_i}} = 1} \right) $

3 结合直方图交叉核的SVM分类器

支持向量机(support vector machines, SVM)由Vapnik^[13]在20世纪末提出, 是在机器学习中运用统计学习的方法。该算法的核心在于利用结构风险最小化的原则, 旨在寻找一种超平面, 能将所有不同的数据分割开来, 使分类的精度达到最高^[14]。SVM最优分类面示意如图 3。

假定需要训练的样本集合为D, 包含n个特征, 且将分类超平面记为式(2)所示:

$ \begin{array}{*{20}{c}} {D = \left\{ {\left( {{x_i},{y_j}} \right){{\left| {{x_i} \in R} \right.}^p},{y_i} \in \left\{ { - 1,1} \right\}} \right\}_{i = 1}^n}\\ {wx + b = 0} \end{array} $

(2)

对于分类的数据, 通常情况下将其分为线性和非线性数据。对于线性可分的情况, 分类的间隔通常设为2/‖w‖, 并且存在下述的约束条件:

$ {y_i}\left( {w{x_i} + b} \right) \ge 1,1 \le i \le n $

在上述约束条件下, 构建最优化的超平面的问题就被转化为求解式(3):

$ \min \varphi \left( w \right) = \frac{{{{\left\| w \right\|}^2}}}{2} $

(3)

引入拉格朗日算子, 转而可转为研究其对偶问题, 即

$ \begin{array}{*{20}{c}} {\max \left( \alpha \right) = \sum\limits_{i = 1}^n {{\alpha _i}} - \frac{1}{2}\sum\limits_{i = 1,j = 1}^n {{\alpha _i}{\alpha _j}{y_i}{y_j}{x_i}{x_j}} }\\ {{\rm{s}}.{\rm{t}}.{\alpha _i} \ge 0,\sum\limits_{i = 1}^n {{\alpha _i}{y_i}} = 0,1 \le i \le n,1 \le j \le n} \end{array} $

综上, 可获得超平面的最优解:

$ w = \sum\limits_{i = 1}^n {{\alpha _i}{y_i}{x_i}} $

$ b = y - w{x_i} $

求解可以得到最优分类函数:

$ f\left( x \right) = \sum\limits_{i = 1,j = 1}^n {{\alpha _i}{\alpha _j}{x_i}{x_j}} + b $

针对绝大多数样本数据为线性不可分的情况, 学者们对SVM进行了改进, 即引入了核函数。上述的f(x)就变成了如式(4)所示:

$ \max \left( \alpha \right) = \sum\limits_{i = 1}^n {{\alpha _i}} - \frac{1}{2}\sum\limits_{i = 1,j = 1}^n {{\alpha _i}{\alpha _j}{y_i}{y_j}K\left( {{x_i},{x_j}} \right)} $

(4)

式中K(x_i, x_j)是引入的核函数。

高斯径向基函数是一种局部性强的核函数, 其可以将一个样本映射到一个更高维的空间内, 该核函数是SVM中应用最广的核函数, 原算法的核函数采用的正是高斯径向基函数。具体的表达式为

$ K\left( {{x_i},{y_i}} \right) = {{\rm{e}}^{\frac{{ - {{\left| {{x_i} - {y_j}} \right|}^2}}}{{2{\delta ^2}}}}} $

参数δ的选择决定径向基函数的宽度, 它的选择对于最终的结果具有很大的影响力。具体来说SVM通过内积核函数将原始特征空间映射到高维特征空间, 最后在高维特征空间中完成最优分类超平面的确定。对于每一个特征来说其映射在每一维的空间都有一个权值称之为特征权值。参数δ较大时在高维空间的权值较小, 所以数值上近似相当于一个低维的子空间; 所谓可分性, 就是引入的核函数将原样本数据在所隐式定义的映射后的新特征空间中进行线性划分的能力。有定理表明, 当rank(K)=n时, 则训练样本在特征空间中线性可分, 其中K=(K(x_i, y_j))_n×n。这里着重讨论δ→0的情况, 此时易知Gram矩阵将K=(K(x_i, y_j))_n×n变成对角阵, 因此满秩, 即rank(K)=n, 由相关性定理易证样本在特征空间中线性可分。这就很容易解释为什么把任意的核函数K(x, y))与高斯核函数$K\left( {x, y} \right) = {\rm{exp}}(-\frac{{{{\left| {x-y} \right|}^2}}}{{2{\delta ^2}}})$ (δ>0)进行凸组合时, 都能组成任何一个对任意训练样本都线性可分的新的核函数, 且核函数具体为$\mathit{\boldsymbol{\bar K}}\left( {x, y} \right) = \left( {1-c} \right)K\left( {x, y} \right) + c \times {\rm{exp}}(-\frac{{{{\left| {x-y} \right|}^2}}}{{2{\delta ^2}}})$, 其中0 < c < 1。不过在实际应用中仍需避免过学习的问题。单纯地对$K\left( {x, y} \right) = {\rm{exp}}(-\frac{{{{\left| {x-y} \right|}^2}}}{{2{\delta ^2}}})$进行观察分析, 可看出它只对样本距离与δ相当的小领域内的样本产生影响, 当样本之间的距离远大于δ时, 它的值逐渐趋近于0, 因此高斯核函数的插入值能力较强, 比较善于提取局部特征, 这也从一定程度上解释了为什么高斯径向基核函数拟合数据能力强但也会出现过拟合的问题。

由于基于空间金字塔的特征被一一分布成了直方图, 因此SVM中的核函数可以采用直方图交叉核。这是一种基于隐式对应关系的内核函数, 解决了无序、可变长度的矢量集合的判别分类的问题。这个内核可以证明是正定的, 并且还有诸多优势。

本文选取直方图交叉函数作为SVM核函数。这个内核的基本思想是将特征集映射到多分辨率超平面中去, 然后对这些超平面进行比较。比较时采用一种加权的超平面交集的比较方法, 从而粗略地估计出特征集之间最好的局部匹配的相似度。直方图交叉核函数为

$ K\left( {{x_i},{y_i}} \right) = \min \left( {{x_i},{y_i}} \right) $

直方图交叉核函数的计算过程如下:

1) 不同间隔得到不同层次的直方图, 为计算每个层次间的重叠程度, 引入了交集函数:

$ I\left( {H\left( X \right),H\left( Y \right)} \right) = \sum\limits_{j = 1}^r {\min \left( {H{{\left( X \right)}_j},H{{\left( Y \right)}_j}} \right)} $

其中X、Y为2个直方图, H(X)_j为X直方图j方形中重叠的数目。H(Y)_j为Y直方图j方形中重叠的数目, 第j方形重叠的数目为二者的最小值, 所有方形的重叠数目之和为该层次的交集函数值。随着层次的增加, 间隔亦随之增大, 交集函数的取值也有所增加。

2) 连续2个层次的交集函数值差为N_i如式(5)所示, 2个直方图的相似函数定义如式(6)所示。

$ {N_i} = I\left( {{H_i}\left( X \right),{H_i}\left( Y \right)} \right) - I\left( {{H_{i - 1}}\left( X \right),{H_{i - 1}}\left( Y \right)} \right) $

(5)

$ K\left( {\psi \left( X \right),\psi \left( Y \right)} \right) = \sum\limits_{i = 0}^L {\frac{1}{{{2^i}}}{N_i}} $

(6)

本文的实验过程如下:

1) 用Dense SIFT进行特征检测。

2) 按照词袋相同的方法(即改进的K-means算法)构建包含M个字的词典。

3) 利用图像金字塔把图像划分为多个尺度的网格块, 然后计算落入每个网格中属于不同类别的字的个数, 则图像X、Y最终的匹配度为

$ {K^L}\left( {X,Y} \right) = \sum\limits_{m = 1}^M {{k^L}\left( {{X_m},{Y_m}} \right)} $

4) 把所有尺度下的直方图特征连接起来组成一个大的特征。这个特征, 就是用来分类的特征向量, 其维度为

$ M\sum\limits_{i = 0}^L {{4^l}} = M \times \frac{1}{3}\left( {{4^{L + 1}} - 1} \right) $

4 仿真实验及分析

本仿真实验是在Win10系统、Intel(R) Pentium(R) CPU、主频为2 GB、内存为6 GB的计算机上运行的, 使用MATLAB R2014a进行编程仿真实验。本文的数据集中有6种不同类别的数据, 每组60幅图像, 一共采用了360幅图像, 其中每组采用40幅图像训练, 20幅图像拿来测试。部分数据集图像如图 4所示, 第1行为Phoning类, 第2行为PlayingGuitar类。

仿真实验中的聚类数目k值根据经验选为300。为了实验的准确性, 每一组分别进行3次实验, 最后取其平均值。对比的实验算法包括原基于词典模型、基于空间金字塔的词袋模型、基于卷积词袋网络、只改进的K-means算法的基于金字塔的词袋模型、本文提出的改进的基于空间金字塔词典模型。

评价的指标为准确度$e = \frac{{{c_t}}}{{{c_t} + {c_f}}}$, 其中c_t为该类所有图像识别类别正确的图像数目, c_f为图像类别识别错误的图像数目。基于空间金字塔词袋模型的图像分类结果的混淆矩阵如图 5所示, 本文基于改进的空间金字塔词袋模型的图像分类结果的混淆矩阵如图 6所示。

混淆矩阵的第i行第j列元素(i≠j)表示第i个类别被错认为j类的比率, 对角线元素表示该类的正确分类率, 每一行的元素之和为概率1。从图 5和图 6可以看出, Shooting和Running类识别的准确度比较好, 能够达到90%甚至更高, 已经达到较高的分类标准。RidingBike和PlayingGuitar这2个类分类相对容易被混淆易出现分类识别错误, 其错误率甚至能达到20%, 其准确率未能达到高标准的图像分类要求。所有类别图像的分类结果如表 1所示。所有类别图像分类算法的运行时间如表 2所示。

通过表 1的数据可知, 基于空间金字塔词袋模型的图像分类算法相对于经典的词袋模型的精确度有了大约5%的提升, 图像分类的准确率能达到80%以上。改进的K-means聚类算法与原基于空间金字塔词袋模型图像分类算法相比也有了大约3%的提升, 另相对于最近的基于卷积神经网络的分类算法的准确度相比提高了近2%。还可知, 本文基于改进的空间金字塔词袋模型的图像分类算法分别有效地优化改善了K-means聚类算法的易陷于局部最优化的缺陷和支持向量机采用径向基核函数可能产生非常严重的过拟合问题。本文的改进算法的图像分类的准确率相对于原基于空间金字塔模型的图像分类算法有了大约9%的提升, 另外相对于最近的基于卷积神经网络的算法的准确度相比提高了近乎8%, 由此验证了改进算法的图像分类的性能更优。

通过表 2数据可知, 只改进的K-means算法的金字塔词袋模型与基于卷积神经网络的算法运行时间相差无几。总体上来说本文的改进金字塔模型的图像分类算法的运行时间是最长的, 相对于经典的词袋模型算法运行时间来说接近其两倍, 与基于卷积神经网络的算法相比慢了接近16%, 但是总体上时间相差不是很大。

5 结论

1) 使用轮盘法的改进的K-means聚类方法改善了原K-means算法易陷于局部最优化的问题。2)支持向量机采用直方图交叉核函数改善优化了原高斯径向基核函数可能产生非常严重的过拟合问题。经过仿真实验对比分析, 文中提出基于改进的空间金字塔词袋模型的图像分类的算法在准确度上优于原经典的金字塔词袋模型算法, 更适用于图像分类。