基于空间特征的多平面支持向量机地形分类∗

薛琮琳 郭剑辉 马玲玲

（南京理工大学计算机科学与工程学院 南京 210094）

1 引言

对于地形识别来说，一般可分为结构化环境或者复杂非结构化环境下的地形识别。结构化环境主要为高速公路与城市化道路等，一般可通过对车道标识和边界等来进行识别，与结构化环境相比，非结构化环境下因为背景和道路没有明显的差别而难利用上述的边界特征进行识别，而且室外非几何地形存在有很大的潜在危险性，例如美国在2005年，2006年研发的机遇号、勇气号火星探测器就因为陷入了松软的沙土不能移动。所以对野外环境下各类地形的识别研究具有重要意义。

目前对于野外地形环境的分类主要分为两种:一种是被称作基于本体感受的分类方法（proprioceptive methods），另一种是基于图像外形特征的分类方法（appearance—based methods）［1］。基于本体感受的方法，主要是利用触觉传感器获得机器人在行驶的时候与地面相互作用的振动信号来进行分类，基于振动的优点是受光照变化较小，对被遮挡的目标物体也有较好的效果，缺点是需要事先实验触觉获得振动与地形的关系，对未知地形不适用，对于危险地形探测比较危险。基于地形外形的特征的分类方法是利用图像视觉信息来进行地形识别，图像包含的信息是最丰富的，相较来说有着巨大的优势。而基于图像的视觉分类的好坏，在不同的问题和环境下图像特征的选取对图像的表现力有着相当大的影响。

尺度不变换特征转换（Scale invariant feature transform，SIFT）［14］是 David Lowe在 1999 年提出的，于2004年时完善总结。SIFT是一种利用局部性特征来表达图像的，它构建出一系列的空间尺度，在相邻的尺度空间上寻找出极值点，并提取出其位置、尺度、旋转不变量。对于目标的旋转遮挡以及光照等问题，SIFT特征都可以取得比较好的效果。而对于地形识别中纹理比较复杂的情况，需要在SIFT特征的基础上进一步抽象。词袋模型BOW（bag of words）［2，5］最初是运用在自然语言处理以及信息检索等领域，BOW忽略了语义上的关系，而是通过构建词典，利用词汇的集合的方式来表达文档。而在2012年，加利福尼亚州圣塔芭芭拉分校（UCSB）机器人研究所的Filichkin与Byl利用BOW，在图像的SIFT或者SUFR特征的基础上生成图像中层特征，结果表明中层特征有着更大的图像表达能力。其研究成果也实地应用于美军军用机器人——小狗（Little—Dog）。受BOW的启发与基础上，出现了基层特征的高层语义特征的提取方法，典型的是空间金字塔模型的匹配（spatial pyramid matching，SPM）算法，在局部特征的基础上，以不同的粒度来划分金字塔从底层特征上来抽象出高层语义特征。SPM算法的Spatial代表分别统计每一个子区域的特征，最后把所有块的特征串联起来形成新的中层特征。在分块的方式上，采取的类似于层次金字塔的方式，在每一个维度上以不同的尺度上进行统计特征，这是Pyramid部分，最后的Matching部分则是对特征进行匹配。以SIFT作为底层特征，以SPM来提取高级语义能更好地表达图像。

SSPM算法进一步加强了图像的表现能力，但是最后的特征向量有可能会发生维数灾难，所以需要较快速度的分类器。基于结构风险最小化原则的SVM的分类性能已经获得了很好的效果，但是由于求解的是一个二次规划的问题会导致比较慢。LSTSVM［7］算法是利用PSVM的思想，在TWSVM［6，10］的基础上提出的。将二次规划问题转化为一个最小正则问题，与SVM相比具有更高的分类精度和计算速度。

综上所述，本文以基于SIFT特征的空间金字塔模型特征提取方法SSPM和相关支持向量多平面支持向量机LSTSVM分类来对地形进行有效的分类。

2 SSPM算法

SPM模型出现的背景是BOW模型被大量地用在了图像表示中。BOW模型对于图像的表达有很大的提高，但是丢失了特征的位置信息。SPM模型的主要思想:在获得图像的底层特征的基础上，将图像在每个维度上划分不同的尺度，以不同的粒度大小来建立空间金字塔模型。

图1 空间金字塔的构造

假定有点集X与点集Y处在D维的特征空间。以尺度分别为0，1…L来对特征空间进行划分，对于每一维上，我们可以划分为2l个相等的间隔。这样总的特征空间可以产生M=2dl个特征的特征空间块bin。对于X与Y中的点x1，y1，如果x1和y1在尺度为l形成的bin中，就称x1与y1是匹配的。定义HlX()i为点集X在尺度l下在第i个bin中的点数，那尺度l下每一个bin中的匹配数定义为

对于尺度l，X与Y的匹配程度定义为

以尺度来分析，直观地看粒度大的会包含有更复杂的信息，所以大尺度的权重分配小于小尺度的。第l层的权重定义为

综上，X与Y的匹配程度可以定义为

利用dense sift特征作为底层特征，利用k-mean算法形成d个聚类作为字典D，按照BOW模型的方法把所有图片的dense sift特征归属到相应类别，利用金字塔模型再次进行特征组合。

字典 D=(d1，d2，…，dn)，图像 I1，I2，对于字典的每一个码字di有相应的金字塔模型有kL( )Xi，Yi表示图像I1，I2在di上的匹配关系。对于整个字典来说，图像I1，I2的匹配程度定义如下:

3 LSTSVM算法

传统支持向量机在分类性能已经有很好的表现，多平面向量机［12～13，15］是为了解 SVM 过高的计算代价和异或等问题而提出的。而最小二乘相关支持向量机是在孪生支持向量机的基础上提出的。因为金字塔模型的向量维数会随着层数增大，为了更好的分类性能和训练时间采取比较快速的LSTSVM来进行分类。LSTSVM是采用了和PSVM相同的思路来求解两个平面，具有较快的分类速度和精度。

假定特征空间为n维，定义为Rn，样本数量为m=m1+m2，m1为正类样本数，m2为负类样本数。设两个超平行平面分别为

其中，w1，w2是超平面权重向量，e1，e1为全为1的列向量，b1，b2是偏差。

令矩阵 A=m1×n代表正类样本集，矩阵B=m2×n代表负类样本集。

目标函数为最小化以下问题:

最小二乘相关支持向量机使用松弛变量的二范数形式代替孪生支持向量机中的ℓ1范数形式，这样使得原本约束条件中的 y≥0可以被省略［9］。将约束条件转换为目标函数，第一个优化问题变为

以第一个平面为例，式（8）对w和b求偏导可得:

把 w1，w2，b1和 b2带入式（5）即可以得到分类平面。

4 结合算法

因为是应用于图像识别，所以使用dense SIFT为底层特征［8］，经金字塔模型组合抽象得到高层特征，以该特征作为样本输入。需要考虑的是组合后的特征维数可能会很大。对于金字塔模型来说，我们假定设置M个码字的字典和L层金字塔，那最后所得的金字塔特征维数为。相比于SVM来说，LSTSVM可以取得较好的分类效果和时间优势，采用LSTSVM验证再对底层特征抽象后的特征对地形的识别率影响。

算法具体步骤:

1）对图片提取dense SIFT特征；

2）利用k-mean算法将dense SIFT特征聚类，形成字典D；

3）利用字典D将每张图片的SIFT特征对应到相应的字典项当中；

4）对图像进行金字塔模型划分，并提取出高级语义的特征；

5）利用网格搜索法计算LSTSVM的最优参数δ；

6）利用最优参数δ与训练集训练分类器LSTSVM；

7）利用训练得到的分类器进行算法验证，分析性能。

5 实验结果

关于地形分类的专用数据库比较少，实验数据库采用的是军事医学科学院卫生装备研究所提供的DSI数据库，数据库总共包含有8种不同典型的地形路面:沥青路面、泥地、草地、瓷砖、碎石、大碎石、沙地和落叶覆盖。每类有300幅图像样本，每个样本分辨率为256×256，图片在不同光照和天气条件下获取。

实验在Matlab R2014a上，每类图片随机选取200幅作为训练数据，其余为测试数据。底层特征采取的是4×4网格结构，统计了8个方向的梯度sift描述子，每个样本可以提取出961个dense sift特征，实验结果如表1～3所示。

图2 分别为沥青路面、泥地、草地、瓷砖、碎石、大碎石、沙地和落叶覆盖

表1 Sift特征与SVM分类结果 /Acc±Std（%）

表2 16码字1层金字塔与LSTSVM分类结果 /Acc±Std（%）

表3 16码字3层金字塔与LSTSVM分类结果 /Acc±Std（%）

实验结果显示，直接通过SVM分类时，会出现某些类别分类严重错误。比如Asphalt和floor（0.5327），Asphalt和 Grass（0.3600），Floor和 Sand（0.3764）和 Wood chips（0.4690）等，其他较低的分类精度有 Asphalt和 Dirt（0.7650），Gravel和 Wood chips（0.7254），说明特征的图像表达能力有待提高；表2可以看出经过金字塔模型形一层形成的特征与LSTSVM结合的分类，上述出现严重分类错误的几类已经得到了极大的改善，而其他类的分类效果也得到了提高，标准差小于表1，说明经过进一步的提高底层特征形成的语义能很好地改善对地形的识别；表3是形成三层金字塔的特征与LSTSVM相结合的结果，可以的看出经过进一步的特征组合再次提高识别率，虽然提升相对较小但是总体识别率都达到了较好的效果，且标准差小于表1和表2，结果稳定。

从表4中可以看出，通过对特征的进行SPM模型化之后，总体识别率得到了提高，而且其中每一类的分类精度都得到了保证，不会出现个别类出现很多偏差的情况。而且可看出使用LSTSVM可以降低训练时间，对地形识别的工程应用方面有着很大的帮助。

表4 时间比较

6 结语

本文针对地形类型分类中，提出了一种结合了金字塔模型和LSTSVM的地形分类算法。实验证明，使用的SSPM算法相比于直接使用底层特征提高了分类精度，而且避免了个别类上分类精度的上的偏差，相比于传统的SIFT特征识别有着明显优势，总体上提高准确率，而且标准差减小，结果比较稳定。LSTSVM相比于SVM有更高的分类精度，有效地降低了对于分类层数增加带来的计算成本，对于工程实践应用有着一定意义。综上，对于野外非结构环境下的地形识别，SSPM算法与LSTSVM相结合的方法是有着极高的实践价值。