3.6　基于支持向量机算法的新蒙文字母识别系统的研究

3.6.1　支持向量机模型和工作原理

支持向量机(Support Vector Machines，SVM)是一种二分类模型，它的目标是寻找一个超平面来对样本进行分割，分割的原则是间隔最大化，最终转化为一个凸二次规划问题来求解，所以，总体来说，SVM算法就是一个可以用线性分类器对原始空间中并非线性可分隔的数据进行分类的算法。

由简单至复杂的模型包括：当训练样本线性可分时，通过硬间隔最大化，学习一个线性可分支持向量机；当训练样本近似线性可分时，通过软间隔最大化，学习一个线性支持向量机；当训练样本线性不可分时，通过核技巧和软间隔最大化，学习一个非线性支持向量机。

3.6.2　线性可分支持向量机

1.间隔最大化和支持向量

如果一个线性函数能够将样本分开，则称这些数据样本是线性可分的。在二维空间中它是一条直线，在三维空间中它是一个平面，以此类推，如果不考虑空间维数，这样的线性函数统称为超平面。

二维平面的超平面如图3-16所示。

图3-16中○代表正类，●代表负类，样本是线性可分的，但是很显然不只有一条直线可以将样本分开，而是有无数条，而线性可分支持向量机的超平面就是对应着能将数据正确划分并且间隔最大的直线，而图中距离超平面最近的一组○和●就称为这个超平面的支持向量。

说明

决定分离超平面时，只有支持向量起作用，因为它们决定了函数间隔和几何间隔，其他点不起作用。

设这个超平面为W，正类支持向量○为向量X+，负类支持向量●为向量X-，两个支持向量之间的间隔为γ，则γ等于他们的差在超平面W上面的投影，即

(3-39)

其中X+和X-满足yi(WΤXi+b)=1，即

(3-40)

推出

(3-41)

将式(3-41)代入式(3-39)得

(3-42)

即间隔γ最大的条件就是使最大化，为了计算方便，通常将式(3-42)变形成式(3-43)的样子。

(3-43)

式(3-43)就是支持向量机的基本型。

2.对偶问题

式(3-43)本身是一个凸二次规划问题，可以使用现有的优化计算工具来计算，但是它的约束条件是一个不等式，不便于数学分析，为了把它变为等式，就要选取它的对偶形式，这样还可以引出原问题不能反映而对偶可以反映的特征。

对式(3-43)使用拉格朗日法得到式(3-44)。

(3-44)

因为要求L(W,b,α)的极值，分别对式(3-44)的W和b求偏导，得

(3-45)

令其分别等于零，得

(3-46)

将式(3-46)代入式(3-44)，可得

(3-47)

这里，式(3-44)加号后面的部分就是将约束条件加入后的转化式，而这时候的约束条件变成了可见经拉格朗日变换后，它由原来的不等式变成了等式。

在KKT条件下进一步整理之后，得到它的模型为

(3-48)

这就是SVM的线性模型，对于任意样本(Xi,yi)，若αi=0，则其不会出现，也就是说，它不影响模型的训练；若αi>0，则yi f(xi)-1=0，也就是yi f(xi)=1，即该样本一定在边界上，是一个支持向量。即当训练完成后，大部分样本都不需要保留，最终模型与支持向量有关。

3.6.3　非线性可分支持向量机

对于非线性问题，要使用非线性模型，才能很好地分类。非线性情况下支持向量机超平面示意图如图3-17所示。

图3-17的问题很明显，如果在二维平面内，则需要用一个椭圆才能将其分类。对于这样的问题，可以将训练样本从原始空间映射到一个更高维的空间，使得样本在这个空间中线性可分。令φ(X)表示将X映射到高维空间后的特征向量，于是超平面的模型可表示为

f(x)=WΤφ(X)+b

(3-49)

于是有最小化函数

(3-50)

它的约束条件是yi(WΤφ(Xi)+b)≥1(i=1,2,…,m)。

其对偶问题为

(3-51)

它的约束条件是

若要对式(3-51)求解，会计算φ(Xi)Τφ(Xj)，这是样本Xi和Xj映射到特征空间之后的内积，由于特征空间维数是提高之后的，它可能会很高，甚至是无穷维的，因此直接计算φ(Xi)Τφ(Xj)通常是困难的，于是可以构造一个函数

k(Xi,Xj)=〈φ(Xi),φ(Xj)〉=φ(Xi)Τφ(xj)

(3-52)

即Xi和Xj在特征空间中的内积等于它们在原始样本空间中通过函数k(Xi,Xj)计算的函数值，于是式(3-49)就变成

(3-53)

它的约束条件是

求解后得到

(3-54)

这里的函数k(Xi,Xj)就是核函数，在实际应用中，人们通常会从一些常用的核函数里面选择使用，根据样本数据的不同，选择不同的参数，核函数也因此不同，常用的核函数有：

线性核函数

(3-55)

多项式核函数

(3-56)

高斯核函数(σ>0)

(3-57)

拉普拉斯核函数(σ>0)

(3-58)

可见，线性核函数其实就是当d=1时多项式和函数的特殊形式。

3.6.4　L1软间隔支持向量机

在前面的讨论中，我们假设训练样本在样本空间或者特征空间中是线性可分的，但在现实任务中往往很难确定合适的核函数使训练集在特征空间中线性可分，退一步说，即使找到了这样的核函数使得样本在特征空间中线性可分，也很难判断是不是由于过拟合造成的。

线性不可分意味着某些样本点(Xi,Xj)不能满足间隔大于或等于1的条件，样本点落在超平面与边界之间。为解决这一个问题，可以对每个样本点引入一个误差因子(ξi≥0)，使得约束条件变为

yi(WΤφ(Xi)+b)≥1-ξi

(3-59)

同时，对于每一个误差因子ξi≥0，支付一个代价ξi≥0，使目标函数变为

(3-60)

其中，C为惩罚函数，C值越大对误差分类的惩罚越大，C值越小对误差分类的惩罚越小，式(3-60)包含两个含义：

 使尽量小，即间隔尽量大。

 使误分类点的个数尽量少，C是调和两者的因数。

有了式(3-60)，L1软间隔支持向量机可以和线性可分支持向量机一样考虑线性支持向量机的学习过程，此时，线性支持向量机的学习问题变成对凸二次规划问题的求解(原始问题)。

(3-61)

与线性可分支持向量机的对偶问题解法一致，式(3-61)的拉格朗日函数为

(3-62)

其中αi≥0,μi≥0，它们都是拉格朗日乘子。

令L(W,b,α,ξ,μ)对W,b,α求偏导，得

(3-63)

将式(3-63)代入式(3-61)得到对偶问题

(3-64)

它的约束条件是

可以得到模型

(3-65)

上述过程的KKT条件是

(3-66)

对于任意训练样本(Xi,yi)，总有αi=0或者yi f(Xi)-1+ξi=0。

若αi=0，则该样本不出现在式(3-65)中，不影响模型。

若αi>0，则必有yi f(Xi)-1+ξi=0，即yi f(Xi)=1+ξi，此时该样本为支持向量。

由于C=αi+μi：

若αi<C，则必有μi>0，根据KKT公式知ξi=0，即该样本恰好落在最大间隔的边界上。

若αi=C，则μi>0，此时若ξi≤1，则该样本在最大间隔内部。

若ξi>1，则样本分类错误。

3.6.5　支持向量机的构建、初始化、仿真

1.支持向量机的分类步骤

应用SVM进行分类的步骤如下：首先收集各个类的训练集和测试集，接着选择合适的用来分类的图像特征，从训练集中提取特征，然后用SVM分类器训练，从而得到分类模板，最后通过模板对待分类图像进行分类。支持向量机的分类步骤如图3-18所示。

2.支持向量机的训练集与测试集

在进行图像分类前，从待处理的数据中取出相当数量的具有代表性的数据作为训练样本。另外，取出一定数量的样本作为测试样本。这个工作很重要，当算法没有改进空间时，通常通过建立好的训练集来提高分类效果。训练集要满足以下的条件：

 训练集要有代表性。

 训练集中不能有错误的样本。

 训练集要尽量完备。

本实验的样本图像采集处理工作为先建立35个新蒙文字母的数据文件夹，每个文件夹内放入手写的蒙文图片字体包括粗、中、细字体，共计100张，图片的大小为72px×72px，其中70张作为训练集，30张作为测试集，将训练集与测试集分别放入两个不同的新蒙文数据文件夹，分别命名为pictures与testPictures。采集图片数据信息时调用imageset函数即可。

样本采集处理代码为trainingset=imageset(dir,'recursive');。

imageset是图像集整理函数，dir代表输入图片集的地址，recursive代表现在函数选取的是标准模式，最后输出的trainingset包含三种信息。

依据本课题设置的训练集，它是一个1×35的矩阵，取其中之一imagetset(1,1),它包含Description属性，即本实验的标签“36”；Imagelocation，即“36”文件夹内70张图片的位置；Count,即“36”文件夹内图片的数量是70张。本示例的35种字母被分别命名为36～70。图像采集结果如图3-19所示。

测试集的图片处理工作与训练集一样。

3.特征选择与提取

特征的选择过程分为目测和实验两个步骤。

(1)目测：对两类图像的颜色、纹理、形状进行分析，选择可能分开两类的特征。

(2)实验：提取特征，用SVM进行训练，由测试效果来决定是否进行优化(如分块)或更换其他特征。

在本实验中，选择了2个特征，即方向梯度直方图、灰度共生矩阵。

(1)方向梯度直方图：HOG特征描述子，它通过计算和统计图像局部区域的梯度方向直方图来构成特征，广泛应用于图像处理的物体检测中。

① 归一化图像。首先把输入的彩色图像转为灰度图像，然后对图像进行平方根Gamma压缩，从而达到归一化效果。这种压缩处理能够有效地减少图像局部阴影和光照变化，从而提高HOG特征对于光照变化的鲁棒性。

② 计算图像梯度。首先用一维离散微分模版[-1,0,1]及其转置分别对归一化后的图像进行卷积运算，得到水平方向的梯度分量及垂直方向的梯度分量。然后根据当前像素点的水平梯度和垂直梯度，得到当前像素点的梯度幅值和梯度方向。

③ 为每个细胞单元构建梯度方向直方图。首先把尺寸为64px×64px的图像分为8×16个Cell，即每个Cell为8px×8px。然后把梯度方向限定在[1，0,-1]，并将梯度方向平均分为9个区间(Bin)，每个区间20°。最后对Cell内每个像素用梯度方向在直方图中进行加权投影，也就是说Cell中的每个像素点都根据该像素点的梯度幅值为某个方向的Bin进行投票，这样就可以得到这个Cell的梯度方向直方图，也就是该Cell对应的9维特征向量。

④ 把细胞单元组合成大的块(Block)，块内归一化梯度直方图。把相邻的2×2个Bell形成一个Block，这样每个Block就对应着36维的特征向量。由于局部光照的变化及前景和背景对比度的变化，使得梯度强度的变化范围非常大。为了进一步消除光照的影响，最后对Block内的36维特征向量进行归一化。

⑤ 采用滑动窗口法通过Block对样本进行扫描，收集HOG特征。

实现它的MATLAB程序是：[hog_feature,vis_hog]=extractHOGFeatures(img,'CellSize',cellSize);。

输入图片信息img，并规定一个细胞的大小CellSize为4px×4px，在MATLAB中运行就可得到hog_feature。

(2)灰度共生矩阵：一幅图像的灰度共生矩阵能反映出图像灰度关于方向、相邻间隔、变化幅度的综合信息，它是分析图像的局部模式和它们排列规则的基础。1973年Haralick从纯数学的角度，研究了图像纹理中灰度级的空间依赖关系，提出灰度共生矩阵的纹理描述方法，其实质是从图像中灰度为i的像素点[其位置为(x，y)]出发，统计与其距离为d、灰度为J的像素点(x+dx,y+dy)同时出现的次数p(i,j,d,θ)，数学表达式为

p(i,j,d,θ)=[(x,y),(x+dx,y+dy)|f(x,y)=i,f(x+dx,y,dy)=j]

(3-67)

式中：x,y=0,1,2,…,N-1，是图像中的像素坐标；dx，dy是位置偏移量；d为生成灰度共生矩阵的步长；i,j=0,1,2,…,L-1是灰度级；θ是生成方向，可以取0°、45°、90°、135°这4个方向，从而生成不同方向的共生矩阵。

要使特征值不受区域范围的影响，还需对此灰度共生矩阵进行归一化处理

(3-68)

由灰度共生矩阵能够导出许多纹理特征，可以计算出14种灰度共生矩阵特征统计量。对图像上的每一像元求出某种邻域的灰度共生矩阵，再由该灰度共生矩阵求出各统计量，就得到对应纹理图像的统计量。若干统计量可以组成图像分类的特征向量。

这4个特征之间不相关，可以有效地描述光学或遥感图像的纹理特征，便于计算又具有较好的鉴别能力。由于要处理的原始图像灰度级比较大，需要从计算时间和纹理可分性上将其灰度级压缩至9级；考虑到参数的旋转不变性，选取4个方向上的均值作为纹理特征参数，步长d为1。利用灰度共生矩阵的定义求出原始图像的灰度共生矩阵，并依据公式进行归一化处理，计算出灰度共生矩阵下的4个纹理特征，作为分类器的输入。

MATLAB中灰度共生矩阵的提取可以调用graycomatrix函数。本实验为了取不同方向(0、45°、90°、135°)的灰度共生矩阵，通过循环计算各个方向的灰度共生矩阵并进行归一化处理(计算对比度、逆差距、熵、自相关)，然后取平均值和方差作为最终提取的特征。

其中，通过glcm = graycomatrix(image,'Offset',[i,i])从图像image中创建一个灰度共生矩阵，设置Offset表明这是一个p行2列的整型矩阵，说明感兴趣的是像素与其相邻像素之间的距离。通过stats = graycoprops(glcm)从灰度共生矩阵glcm来计算静态属性。

本实验一共设置4个角度的灰度共生矩阵，最终通过一个矩阵计算将所有特征值整合到一个矩阵中去。

具体的特征提取及合并程序如图3-20和图3-21所示。

最后通过features(i,:) = [hog_feature glcm_feature]函数将两个特征整合到一起。

4.用SVM进行图像分类

在支持向量机中，采用不同的内积函数将导致使用不同的支持向量机算法，因此内积函数的选择对支持向量机的构建有重要作用，本文采用MATLAB自带的fitcecoc函数，默认情况下，fitcecoc函数使用线性SVM二进制学习器。

5.图像仿真

本实验提取特征值的时候会先利用img=imresize(img,[i i])调整图片的像素大小,i为像素值的大小，下面分别将待处理图片的大小改为256px×256px、64px×64px、32px×32px,分别运行程序，择优选取最好的像素大小。

(1)默认线性多BSVM分类(处理图像256px×256px,见图3-22)。

其中，默认线性多分类的代码为：classifier =fitcecoc(trainingFeatures,trainingLabels);。程序经过了过了两个小时还在运行，所以不采用这个像素设置。

(2)默认线性多BSVM分类(处理图像64px×64px，见图3-23)。

其中，默认线性多分类的代码为classifier =fitcecoc(trainingFeatures,trainingLabels);。程序运行了11分50秒，正确率是96.95%，oosLoss值是0.0143，说明分类结果比较理想。

(3)默认线性多BSVM分类(处理图像32px×32px，见图3-24)。

其中，默认线性多分类的代码为classifier =fitcecoc(trainingFeatures,trainingLabels);。程序运行了5分06秒，正确率是97.33%，oosLoss值是0.0155。

(4)默认线性多BSVM分类(处理图像8px×8px，见图3-25)。

其中，默认线性多分类的代码为classifier =fitcecoc(trainingFeatures,trainingLabels);。程序运行了5分06秒，正确率是79.33%，oosLoss值是0.1910。

各类分辨率比较汇总情况如表3-2所示。

由表3-2可见，默认线性多BSVM分类(处理图像32px×32px)的分类结果是这4个分辨率里效果最理想的，所以采用32px×32px方式来提取图片。

由于MATLAB自带的fitcecoc函数默认使用线性SVM二进制学习器，下面分别换成其他核函数进行分类测试。

(1)线性核函数如图3-26所示。

其中，线性核函数的代码为t =templateSVM('Standardize',1);classifier = fitcecoc(trainingFeatures,trainingLabels,'Learners',t);。程序运行了6分43秒，正确率是96.57%，oosLoss值是0.0188。

(2)高斯核函数如图3-27所示。

其中，高斯核函数的代码为t =templateSVM('KernelFunction','gaussian');classifier =fitcecoc(trainingFeatures,trainingLabels,'Learners',t);。程序运行了7分39秒，正确率是38.38%，oosLoss值是0.7029，说明这个核函数不适合当作蒙文识别的SVM分类器。

(3) 多项式核函数如图3-28所示。

其中，多项式核函数的代码为t =templateSVM('KernelFunction','polynomial');classifier =fitcecoc(trainingFeatures,trainingLabels,'Learners',t);。程序运行超过了100分钟，相较其他的分类器，这个核函数不适合当作蒙文识别的SVM分类器。

(4)序列最小优化算法(SMO)核函数如图3-29所示。

其中，序列最小优化算法核函数的代码为t =templateSVM('KernelOffset',0);classifier =fitcecoc(trainingFeatures,trainingLabels,'Learners',t);。程序运行了5分14秒，正确率是97.73%，oosLoss值是0.0147，说明这个方法适合当作蒙文识别的SVM分类器。

综合比较上述4种分类器，最终选择序列最小优化算法核函数来作为蒙文识别的SVM分类器。各种核函数分类方法的比较汇总如表3-3所示。

最后使用核函数predictedLabels = predict(classifier,testFeatures)进行预测，classifier是训练出来的SVM分类器，testFeatures是测试集的特征值矩阵。

本实验最终采用序列最小优化算法核函数进行分类，使用自定义的代码Predict('D:\testPictures\test\38\38.60.png')来调出测试图片的分类结果。本次用来测试图片的标签是38。

最终的识别分类结果如图3-30所示。

3.6.6　支持向量机各层及各层间传输函数的设计选择

支持向量机的传输示意图如图3-31所示。

输入层是提取的各个特征值，将它们传递给隐含层，隐含层是核函数K(xi,x)，通过选取不同的隐含层函数，会得到不同的分类效果。本文通过实验采用序列最小优化算法线性核函数进行分类，之后将它加权，使用坐标上升法，同时改变参数αi与αj，使得超平面W最优。同时满足约束条件，αi每一次改变，会使W(α)变得更好，αi也会逐渐接近某一个特定值，当它确定时再保持这个αi去确定αi+2，当所有的α都确定的时候代入公式计算b的值，最后代入线性核函数的公式，输出层即可输出分类结果。

支持向量机的二分类过程前面已经介绍过了，但是现实中遇到的往往是多分类的情况。

支持向量机应对多分类情况主要有两种方式。

(1)一对一的支持向量机分类(One Against One SVMs)：一对一方式就是对每两个类样本之间构建出一个分类超平面，所有k类样本共能构造出k(k-1)/2个分类超平面。具体分类操作如下：

取出所有满足条件yi=s,yi=t，通过二分类法构造最优分类函数

(3-69)

新样本的预测方式就是将它输入k(k-1)/2个分类器内，最后通过投票的方式将获得票数最多的类别作为它的预测值。把多分类的问题变成二分类的问题。

这种方式的优点是：对于每一个子SVM，由于训练样本少，因此其训练速度显著快于一对多SVM方式，同时其精度也较高。这种方式的缺点：随着类数k的增多，SVM的个数也越来越多，随着k个数的增多，其训练速度也会越来越慢，这是需要改进的地方。

(2)一对多的支持向量机分类(One Against Rest SVMs)：一对多方式与一对一方式的区别就是一对多方式为每一个独立样本与其余样本之间构建出一个分类超平面，所有k类样本共能构造出k个分类超平面。