支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM 还包括核技巧，这使它成为实质上的非线性分类器。SVM 的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM 的的学习算法就是求解凸二次规划的最优化算法。

SVM原理

SVM 是一种在特征空间中寻找最大间隔超平面的判别式、线性、二分类器。之所以去寻找最大间隔的超平面就是为了追求模型的最大鲁棒性，对未知数据有最强的泛化能力。例如我们对样本施加一些噪声，间隔越大，就越不容易被错误分到另一类，如图9.17所示 ，a 图为所有的数据点，b 图为支持向量机最终的最大间隔超平面，可以看到它对噪声有着很强的鲁棒性。但是 c 图的分类效果的鲁棒性很差。

图 9.17 SVM原理

SVM学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。  即为分离超平面，对于线性可分的数据集来说，这样的超平面有无穷多个（即感知机），但是几何间隔最大的分离超平面却是唯一的。在推导之前，先给出一些定义。假设给定一个特征空间上的训练数据集:

其中， ， ， ， 为第 个特征向量， 为类标记，当它等于+1时为正例；为-1时为负例。再假设训练数据集是线性可分的。对于给定的数据集T和超平面 ，定义超平面关于样本点  的几何间隔为：

超平面关于所有样本点的几何间隔的最小值为：

实际上这个距离就是我们所谓的支持向量到超平面的距离。根据以上定义，SVM模型的求解最大分割超平面问题可以表示为以下约束最优化问题：

将约束条件两边同时除以   ，得到：

因为  是标量，所以为了表达式简洁起见，令 ， ，又因为最大化   ，等价于最大化   ，也就等价于最小化 （  是为了后面求导以后形式简洁，不影响结果），因此SVM模型的求解最大分割超平面问题又可以表示为以下约束最优化问题：

这是一个含有不等式约束的凸二次规划问题，可以对其使用拉格朗日乘子法得到其对偶问题，首先将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数：

其中 为拉格朗日乘子，且   。现在令 ，当样本点不满足约束条件时，即在可行解区域外： ，此时，将 设置为无穷大，则  也为无穷大。当满足本点满足约束条件时，即在可行解区域内： ，此时，   为原函数本身。于是，将两种情况合并起来就可以得到新的目标函数：

 

于是原约束问题就等价于：

新的目标函数先求最大值，再求最小值。这样的话，首先就要面对带有需要求解的参数 和 的方程，而  又是不等式约束，这个求解过程不好做。所以需要使用拉格朗日函数对偶性，将最小和最大的位置交换一下，这样就变成了：

要有 = ，需要满足两个条件：

1. 优化问题是凸优化问题
2. 满足KKT条件

首先，本优化问题显然是一个凸优化问题，所以条件一满足，而要满足条件二，即要求：

为了得到求解对偶问题的具体形式，令   对 和 的偏导为0，用 将拉格朗日目标函数变为 一个未知数的方式，对其求解 后求对 的极大，再把目标式子加一个负号，将求解极大转换为求解极小，这就是对偶问题。最后得到的问题形式如下：

 _，_ 

 

现在的优化问题变成了如上的形式。对于这个问题有更高效的优化算法，即序列最小优化（SMO）算法。正如上面提到的，既然知道了如果所有的拉格朗日乘子 都满足KKT条件和对偶问题中的约束条件，那么这样的拉格朗日乘子 一定是极值点。那就可以不停地试错，判断拉格朗日乘子 是不是满足约束条件，如果都满足就可以找到极值点 ，如果不满足，那我就优化选择到的乘子，重复此过程，直到得到优化结果。这就是SMO算法的大致思想。通过这个优化算法能得到 ，再根据 就可以通过下式求解出 和 ，进而求得最初的目的：找到超平面，即”决策平面”。

 

对于任意训练样本 ，总有 或者 。若  ，则该样本不会在最后求解模型参数的式子中出现。若 ，则必有 ，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。

 SVM模型训练过程

上面都是基于训练集数据线性可分的假设下进行的，但是实际情况下几乎不存在完全线性可分的数据，为了解决这个问题，引入了“软间隔”的概念，即允许某些点不满足约束，然后我们采用hinge损失，将原优化问题改写为：

其中 为“松弛变量”， ，即为hinge损失函数。每一个样本都有一个对应的松弛变量，表征该样本不满足约束的程度。 称为惩罚参数， 值越大，对分类的惩罚越大。跟线性可分求解的思路一致，同样这里先用拉格朗日乘子法得到拉格朗日函数，再求其对偶问题可以得到线性支持向量机的训练算法如下：

1. 选择惩罚参数 ，构造并求解凸二次规划问题：

 _c,  _ 

最后求解出最优解 

1. 计算 ， 

选择  的一个分量  满足条件   ，计算 

1. 求最大间隔超平面

最后得到分类决策函数：

对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。由于在线性支持向量机学习的对偶问题里，目标函数和分类决策函数都只涉及实例和实例之间的内积，所以不需要显式地指定非线性变换，而是用核函数替换当中的内积。核函数表示为 ，可以实现实例通过一个非线性转换后的内积。在线性支持向量机学习的对偶问题中，用核函数 替代内积，求解得到的就是非线性支持向量机的分类决策函数：

最后介绍一个常用的核函数——高斯核函数，其对应的SVM是高斯径向基函数分类器。

 基于SVM的行人检测实战

上一节已经介绍了目标检测中图像特征提取方式Haar特征，HOG特征以及DMP特征。HOG特征更倾向于轮廓的检测，比如行人的检测；而Haar特征则能更好的描述敏感的变化，更适于检测人脸。下面介绍如何通过opencv实现行人检测，Opencv利用HOG特征实现行人检测，包括了HOG的特征提取和SVM识别两部分。本节将提到两种方式：

1. 利用Opencv自带的已训练好的行人检测模型直接进行检测。
2. 通过设置训练的正负样本得到HOG特征，并训练SVM，得到模型，最后进行行人的检测。

（1）OpenCV自带行人检测器实现行人检测

利用OpenCV自带的行人检测其实现行人检测主要有三步：

1. 初始化HOG描述子；
2. 设置HOG中的SVM为已训练好的SVM模型；
3. 读取图像，检测，并在图像中显示出检测结果；

下面是使用opencv自带的hog目标检测模型结合其训练好的SVM实现行人检测。

1. import cv2
2. #待检测图像的文件路径
3. base_path = ‘image/people.jpg’
4. img=cv2.imread(base_path)
5. #初始化HOG描述子
6. hog = cv2.HOGDescriptor()
7. # 设置支持向量机，其为一个预先训练好的行人检测器
8. hog.setSVMDetector(cv2.HOGDescriptor_getDefaultPeopleDetector())
9. #检测行人
10. rects, wei = hog.detectMultiScale(img, winStride=(4, 4), padding=(8, 8),
11. scale=1.05)
12. for (x, y, w, h) in rects:
13. #将检测结果在图像中圈出来
14. cv2.rectangle(img, (x, y), (x + w, y + h), (0, 0, 255), 2)
15. #显示图像
16. cv2.imshow(“people detect”, img)
17. cv2.waitKey(0)

图 9.18 行人检测

如图9.18所示使用opencv自带模型很好的实现了图像中行人的检测，下面对我们用到的检测器进行简单的介绍。

cv2.HOGDescriptor()：OpenCV中的HOG特征提取功能使用了HOGDescriptor这个类来进行封装。其中包含了许多函数，下面列举了常用的一些函数：

1. getDetectorSize(self)：获得设置的hog描述子的维数；
2. compute(self,,img,,winStride=None,padding=None, locations=None)：计算输入的检测窗口的hog描述子；
3. computeGradient(self,,img,grad,angleOfs,paddingTL=None,paddingBR=None)：计算输入图像的梯度幅度图像；
4. setSVMDetector(cv2.HOGDescriptor_getDefaultPeopleDetector())：设置训练好的支持向量机检测器；
5. detectMultiScale(self,img,hitThreshold=None,winStride=None,padding=None,scale=None, finalThreshold=None, useMeanshiftGrouping=None)：对输入图像进行检测，并且返回目标位置与目标的权重。

 （2）利用opencv实现HOG检测器的自定义数据训练

上面使用了自带的模型，较为简单。下面的代码可以通过设置正负样本，自己提取HOG特征，然后训练出SVM模型，进而进行检测得到结果。基本步骤如下：

训练模型

1. 准备正样本和负样本；
2. 计算样本的HOG特征；
3. 训练SVM模型；
4. 将训练好的SVM模型设置为opencv 中的SVM模型，得到训练好的行人检测器；
5. 利用自己训练的检测器进行检测

下面是实现训练模型的代码，主要包括加载正样本行人标签信息的函数load_imgelable( )，加载正样本图片，并且进行尺度归一化的函数load_imge1( )，加载负样本所有原图片的函数load_imge2( )，从负样本原图片截取64*128的图像作为训练负样例的函数sample_neg( )，计算图像的HOG特征的函数compute_hog( )，初始化要训练的svm参数的函数svm_init( )，获取svm的支持向量的函数get_svm_detector(svm)

load_imgelable( )的核心代码如下：

1. def <span class=”hljs-title function_“>load_imgelable(dirname, imageNum=500):
2. ‘’’
3. 通过pascal格式的文件加载图像的中的行人数量，行人的位置信息的标签
4. :param dirname: 存储图像标签pascal格式文件的路径的文件，如annotations.lst
5. :param imageNum: 要读取的图像数目
6. :return: 返回存储图像方框数量与位置信息的list
7. ‘’’
8. people_num=[]#每张照片里的行人数量
9. people_coordinate=[]#每张照片里的行人标注框坐标
10. cnt = imageNum
11. file = open(dirname)
12. imglab = file.readline()
13. while imglab != ‘’:
14. #文件末尾
15. imglab_name = dirname.rsplit(r’/‘,1)[0] + r’/‘+ imglab.split(‘/‘, 1)[1].strip(‘\n’)
16. #图像路径
17. f = open(imglab_name, encoding=‘gbk’)
18. line_list = f.readlines()
19. for line in line_list:
20. if str(line).__contains__(‘Objects with ground truth’):
21. nums = re.findall(r’\d+’, str(line))
22. people_num.append(nums[0])
23. break
24. for index in range(1, int(nums[0]) + 1):
25. for line in line_list:
26. if str(line).__contains__(“Bounding box for object “ + str(index)):
27. coordinate = re.findall(r’\d+’, str(line))
28. people_coordinate.append([coordinate[1],coordinate[2],
29. coordinate[3],coordinate[4]])
30. break
31. f.close()
32. cnt = cnt-1
33. if cnt == 0:
34. break
35. imglab = file.readline()
36. return [people_num,people_coordinate] #返回所有图像的标注内容

 load_imge1( )函数的核心代码如下：

1. def <span class=”hljs-title function_“>load_imge1(dirname,people_num,people_coordinate,imageNum=500, showImage = False):
2. ‘’’
3. 加载正样本图像，并进行尺度归一化
4. :param dirname: 存储图像名称的文件，如pos.lst
5. :param imageNum: 要读取的图像数目
6. :param showImage: 是否显示图像
7. :return: 返回存储图像内容的list
8. ‘’’
9. img_list = []
10. cnt = imageNum
11. file = open(dirname)
12. img = file.readline()
13. flag0=0
14. while img != ‘’: #文件末尾
15. flag1=imageNum-cnt
16. for i in range(0,int(people_num[flag1])):
17. [Xmin,Ymin,Xmax,Ymax]=people_coordinate[flag0]
18. imgid=img.rsplit(‘/‘, 1)[1].strip(‘\n’)
19. img_name = dirname.rsplit(r’/‘,1)[0] + r’/‘+ img.split(‘/‘, 1)[1].strip(‘\n’) #图像路径
20. img_all = cv2.imread(img_name,0) #将图像读取，并转为灰度图像
21. w=(int(Ymax)-int(Ymin))/2-int(Xmax)+int(Xmin)
22. if (int(Xmin)-int(w/2))>0:
23. img_cut=img_all[int(Ymin):int(Ymax),(int(Xmin)-int(w/2)):(int(Xmax)+int(w/2))]
24. else:
25. img_cut=img_all[int(Ymin):int(Ymax),int(Xmin):int(Xmax)]
26. img_content=cv2.resize(img_cut,dsize=(64,128))
27. img_list.append(img_content)
28. flag0=flag0+1
29. if showImage: #是否显示图像，默认否
30. cv2.imshow(img_name+str(i), img_content)
31. cv2.waitKey(10)
32. cnt = cnt-1
33. if cnt == 0:
34. break
35. img = file.readline()
36. return img_list #返回所有图像的内容

 load_imge2( )函数的核心代码如下：

1. def <span class=”hljs-title function_“>load_imge2(dirname, imageNum = 500, showImage = False):
2. ‘’’
3. 加载负样本的图像
4. :param dirname: 存储图像名称的文件，如pos.lst
5. :param imageNum: 要读取的图像数目
6. :param showImage: 是否显示图像
7. :return: 返回存储图像内容的list
8. ‘’’
9. img_list = []
10. cnt = imageNum
11. file = open(dirname) #
12. img = file.readline()
13. while img != ‘’: #文件末尾
14. img_name = dirname.rsplit(r’/‘,1)[0] + r’/‘+ img.split(‘/‘, 1)[1].strip(‘\n’) #图像路径
15. img_content = cv2.imread(img_name,0) #将图像读取，并转为灰度图像
16. img_list.append(img_content)
17. if showImage: #是否显示图像，默认否
18. cv2.imshow(img_name, img_content)
19. cv2.waitKey(10)
20. cnt = cnt-1
21. if cnt == 0:
22. break
23. img = file.readline()
24. return img_list #返回所有图像的内容

sample_neg( )函数的核心代码如下：

1. def <span class=”hljs-title function_“>sample_neg(neg_sample_all, imageNum=500, size=(64,128)):
2. “””
3. 获取负样例，从没有行人的图片中截取64_128的图像作为训练负样例
4. :param neg_sample_all: 所有没有行人的图像
5. :param imageNum: 负样本的数目
6. :param size: 截取的图像的大小
7. :return: 返回负样本图像的内容
8. “””
9. neg_sample_list = []
10. cnt = imageNum
11. width, height = size[0], size[1] #图像的宽度和高度
12. for i in range(len(neg_sample_all)):
13. row, col = neg_sample_all[i].shape
14. for j in range(2):
15. y = int(random.random()_(row - height)) #随机选择图像截取的起点，也就是说从图像中随机截取的图像
16. x = int(random.random()*(col - width))
17. neg_sample_list.append(neg_sample_all[i][y:y+height, x:x+width])
18. cnt = cnt-1
19. if cnt == 0:
20. break
21. return neg_sample_list

 compute_hog( )函数的核心代码如下：

1. def <span class=”hljs-title function_“>compute_hog(img_list, wsize = (64, 128)):
2. “””
3. 计算图像的HOG特征
4. :param img_list:
5. :param wsize: #图像的大小
6. :return:
7. “””
8. gradient_list = []
9. hog = cv2.HOGDescriptor() #初始化HOG描述子
10. for i in range(len(img_list)):
11. if img_list[i].shape[1] >= wsize[0] and img_list[i].shape[0] >= wsize[1]:
12. #图像要大于需要的图像的大小
13. roi = img_list[i][(img_list[i].shape[0] - wsize[1]) // 2:
14. (img_list[i].shape[0] - wsize[1]) // 2 + wsize[1],
15. (img_list[i].shape[1] - wsize[0])//2 :
16. (img_list[i].shape[1] - wsize[0])//2 + wsize[0]]
17. hog_data = hog.compute(roi) #计算截取的图像的 HOG特征
18. gradient_list.append(hog_data)
19. return gradient_list #返回图像的HOG特征

svm_init( )函数的核心代码如下：

1. def <span class=”hljs-title function_“>svm_init(): #初始化svm
2. svm = cv2.ml.SVM_create() #
3. svm.setCoef0(0)
4. svm.setDegree(3) #多项式核时，变量的阶数
5. criteria = (cv2.TERM_CRITERIA_MAX_ITER + cv2.TERM_CRITERIA_EPS, 1000, 1e-3)
6. svm.setTermCriteria(criteria)
7. svm.setGamma(0) #
8. svm.setKernel(cv2.ml.SVM_LINEAR) #SVM的核函数
9. svm.setNu(0.5)
10. svm.setP(0.1)
11. svm.setC(0.01)
12. svm.setType(cv2.ml.SVM_EPS_SVR) #SVM的类型
13. return svm

get_svm_detector( )函数核心代码如下：

1. def <span class=”hljs-title function_“>get_svm_detector(svm): #获取SVM特征向量
2. sv = svm.getSupportVectors() #获取支持向量
3. rho, _, _ = svm.getDecisionFunction(0)
4. sv = np.transpose(sv)
5. return np.append(sv, [[-rho]], 0)

最后是我们调用这些函数进行训练的主程序代码，训练完成后我们会把训练好的SVM分类器保存成一个myHogDector.bin的文件，以供我们检测阶段时，加载使用。核心代码如下：

1. import cv2
2. import numpy as np
3. import random
4. import re
5. if name == “main“:
6. print(“加载训练样本”)
7. base_path = ‘INRIAPerson//‘
8. [people_num,people_coordinate]=load_imgelable(base_path+“Train//annotations.lst”, imageNum=614)
9. # 加载正例图像，大小均为（64*128）
10. pos_list = load_imge1(base_path+“Train//pos.lst”,people_num,
11. people_coordinate,imageNum=614, showImage=False) #正样本
12. # 负例图像，大小不定，需要裁剪
13. neg_list_all = load_imge2(base_path+“Train//neg.lst”,
14. imageNum=1218, showImage=False)
15. neg_list = sample_neg(neg_list_all, imageNum=1218, size=[64, 128]) #行人，一般是站立的，负例图像
16. print(“加载训练样本完成”)
17. ylabels = []
18. gradient_list = []
19. print(“计算HOG特征”)
20. pos_gradient_list = compute_hog(pos_list, wsize=(64, 128)) #计算HOG特征
21. [ylabels.append(1) for _ in range(len(pos_list))] #正例标签
22. neg_gradient_list = compute_hog(neg_list, wsize=(64, 128)) #计算HOG特征
23. [ylabels.append(-1) for _ in range(len(neg_list))] #负例标签
24. gradient_list.extend(pos_gradient_list)
25. gradient_list.extend(neg_gradient_list)
26. print(“计算HOG特征完成”)
27. print(“训练SVM模型”)
28. svm = svm_init() #初始化svm
29. svm.train(np.array(gradient_list),
30. cv2.ml.ROW_SAMPLE, np.array(ylabels)) #训练SVM模型
31. hog = cv2.HOGDescriptor() #hog描述子
32. hard_neg_list = []
33. hog.setSVMDetector(get_svm_detector(svm)) #setSVMDetector用于加载svm模型，对hog特征分类的svm的系数赋值
34. #加入错误分类的标签，重新对svm进行训练
35. for i in range(len(neg_list_all)):
36. rects, wei = hog.detectMultiScale(neg_list_all[i], winStride=(2,2), padding=(8,8), scale=1.01)
37. for (x,y, w,h ) in rects:
38. merge=int(h/2)
39. hardExample = neg_list_all[i][y:y+h, x:x+merge]
40. hard_neg_list.append(cv2.resize(hardExample,(64,128)))
41. hard_gradient_list = compute_hog(hard_neg_list)
42. [ylabels.append(-1) for _ in range(len(hard_neg_list))]
43. gradient_list.extend(hard_gradient_list)
44. #训练svm
45. svm.train(np.array(gradient_list), cv2.ml.ROW_SAMPLE, np.array(ylabels))
46. #保存hog
47. hog.setSVMDetector(get_svm_detector(svm))
48. hog.save(‘myHogDector.bin’)
49. print(“训练SVM模型完成”)

测试模型

通过上面的学习，已经训练了一个自己的SVM分类器，下面就可以用自己的分类器对任意一张图片进行行人检测，检测的步骤其实跟OpenCV自带行人检测器实现行人检测的方式，只需要把其中的检测器换成自己的分类。主要步骤如下：

1. 初始化HOG描述子；
2. 加载已训练好的检测器；
3. 读取图片并进行检测；打印显示检测结果；

下面是实现检测功能的核心代码：

1. import cv2
2. base_path = ‘image/people.jpg’#待检测图像的文件路径
3. img=cv2.imread(base_path)
4. hog = cv2.HOGDescriptor()  #初始化HOG描述子
5. # 设置支持向量机，其为一个预先训练好的行人检测器
6. hog.load(‘myHogDector.bin’)
7. rects, wei = hog.detectMultiScale(img, winStride=(2, 2), padding=(8, 8), scale=1.05) #检测行人
8. for (x, y, w, h) in rects:
9.     cv2.rectangle(img, (x, y), (x + w, y + h), (0, 0, 255), 2) #将检测结果在图像中圈出来
10. cv2.imshow(“people detect”, img) #显示图像
11. cv2.waitKey(0)

如图9.19为自己训练的检测器的结果，明显可以看到，在图9.19中的训练结果几乎与opencv自带的行人检测器效果差不多。当然也还可以通过增大训练样本集，改善样本的质量等方法继续提高自己训练的模型。

图 9.19 输出结果