0. 前言

本节中，我们将介绍机器学习方法支持向量机 (Support Vector Machine, SVM)，它可以根据训练数据得到准确的二分类分类器，它已被广泛用于解决许多计算机视觉问题。该分类器可以通过使用数学公式表达，该公式可以用于在高维空间中查看数据集的几何结构。此外，我们还将介绍一种新的图像表示，该表示通常与 SVM 结合使用以获取鲁棒性目标检测器。

1. HOG 图像特征

物体图像主要以其形状和内容为特征，通常可以由定向梯度直方图 (Histogram of Oriented Gradients, HOG) 表示，这种表示方法基于图像梯度构建的直方图。因为我们对物体形状和纹理感兴趣，所以需要分析梯度方向的分布。此外，为了考虑这些梯度的空间分布，在将图像划分为多个区域计算多个直方图。
因此，构建 HOG 表示的第一步是计算图像的梯度。然后将图像细分为小单元格(例如，8×8 像素)，并为这些单元格构建梯度方向直方图。因此，必须将可能的方向范围划分为多个区间。大多数情况下，只考虑梯度方向而不考虑它们的符号(称为无符号梯度)，在这种情况下，可能的方向范围是 0 到 180 度，此时，一个 9-bin 直方图会将可能的方向划分为 9 个 20 度的区间。单元格中的每个梯度向量都累积在对应于该梯度大小的 bin。
然后将单元格分组为块，由一定数量的单元格组成一个块，这些块可以相互重叠(即它们可以共享单元格)。例如，块由 2×2 个单元格组成，如果块步长为 1 个单元格，每个单元格(除了最后一个单元格)将被 2 个块共享。相反，如果块步长为 2 个单元格，则块不会发生重叠现象。
一个块包含一定数量的单元格直方图(例如，块由 2×2 个单元格组成时，包含 4 个单元格直方图)。将直方图连接在一起可以形成一个长向量(例如，当单元格数为 4、直方图 bin 数为 9 时，将生成一个长度为 36 的向量）。为了这种图像表示具有鲁棒性，对该向量进行归一化(例如，每个元素除以向量的大小)。最后，将与图像的所有块相关联的向量(按行顺序)连接在一起得到一个更长的向量(例如，在 64×64 图像中，当块中单元格大小为 8x8，步长为 1 时，可以得到 7x7=49 个块，因此最终向量为 49×36=1764 维)，这个长向量就是图像的 HOG 表示。
图像的 HOG 表示是一个高维向量，可以使用该向量表征图像，用于执行图像分类任务，为了实现这一目标，我们需要使用可以处理高维向量的机器学习方法。

2. 交通标志分类

在本节中，我们构建交通标志标志分类器，用于说明图像的 HOG 表示，并利用这种表示方法进行图像分类。

2.1 SVM 模型

(1) 首先，获取用于训练的样本，使用的正样本如下所示：

(2) 负样本集如下所示：

(3) 接下来，使用 SVM 区分这两个类别，在 OpenCV 中可以借助 cv::svm 类实现。为了构建鲁棒性分类器，使用 HOG 来表示图像实例。更准确地说，我们使用由 2×2 单元组成的 8×8 块，块步长为 1 单元：

    cv::HOGDescriptor hog(cv::Size((image.cols / 16) * 16, (image.rows / 16) * 16), // 窗口大小
                    cv::Size(16, 16),    // 块尺寸
                    cv::Size(16, 16),    // 块步长
                    cv::Size(4, 4),      // 单元格尺寸
                    9);                  // bins 数量

(4) 使用 9-bin 直方图和尺寸为 64×64 样本，将得到大小为 8100 的 HOG 向量(由 225 个块组成)。为每个样本计算 HOG 描述符，然后将它们组合为一个矩阵，矩阵中的每一行都表示一个 HOG：

    // 计算第一个描述符
    std::vector<float> desc;
    hogDesc.compute(positives[0], desc);
    std::cout << "Positive sample size: " << positives[0].rows << "x" << positives[0].cols << std::endl;
    std::cout << "HOG descriptor size: " << desc.size() << std::endl;
    // 样本描述符矩阵 
    int featureSize = desc.size();
    int numberOfSamples = positives.size() + negatives.size();
    // 创建包含样本HOG的矩阵 
    cv::Mat samples(numberOfSamples, featureSize, CV_32FC1);
    // 用第一个描述符填充第一行
    for (int i = 0; i < featureSize; i++)
        samples.ptr<float>(0)[i] = desc[i];
    // 正样本的计算描述符
    for (int j = 1; j < positives.size(); j++) {
        hogDesc.compute(positives[j], desc);
        // 用当前描述符填充下一行
        for (int i = 0; i < featureSize; i++)
            samples.ptr<float>(j)[i] = desc[i];
    }
    // 计算负样本的描述符
    for (int j = 0; j < negatives.size(); j++) {
        hogDesc.compute(negatives[j], desc);
        // 用当前描述符填充下一行
        for (int i = 0; i < featureSize; i++)
            samples.ptr<float>(j + positives.size())[i] = desc[i];
    }

(5) 在以上代码中，我们创建了描述符矩阵，接下来，我们继续创建第二个矩阵以表示与每个样本相关联的标签，为正样本分配标签 1，而负样本分配标签 -1：

    // 创建标签
    cv::Mat labels(numberOfSamples, 1, CV_32SC1);
    // 正样本标签
    labels.rowRange(0, positives.size()) = 1.0;   
    // 负样本标签
    labels.rowRange(positives.size(), numberOfSamples) = -1.0; 

(6) 构建用于训练的 SVM 分类器，设定 SVM 的类型和要使用的核：

    // 创建 SVM 分类器
    cv::Ptr<cv::ml::SVM> svm = cv::ml::SVM::create();
    svm->setType(cv::ml::SVM::C_SVC);
    svm->setKernel(cv::ml::SVM::LINEAR);

(7) 将标记样本输入到分类器中，并调用 train 方法训练模型：

    // 准备训练数据
    cv::Ptr<cv::ml::TrainData> trainingData =
        cv::ml::TrainData::create(samples, cv::ml::SampleTypes::ROW_SAMPLE, labels);
    // 训练 SVM
    svm->train(trainingData);

(8) 训练完成后，可以将分类器用于预测新图像所属的类别：

    cv::Mat queries(4, featureSize, CV_32FC1);
    // 用查询描述符填充行
    hogDesc.compute(cv::imread("11.png", cv::IMREAD_GRAYSCALE), desc);
    for (int i = 0; i < featureSize; i++)
        queries.ptr<float>(0)[i] = desc[i];
    hogDesc.compute(cv::imread("12.png", cv::IMREAD_GRAYSCALE), desc);
    for (int i = 0; i < featureSize; i++)
        queries.ptr<float>(1)[i] = desc[i];
    hogDesc.compute(cv::imread("n12.jpg", cv::IMREAD_GRAYSCALE), desc);
    for (int i = 0; i < featureSize; i++)
        queries.ptr<float>(2)[i] = desc[i];
    hogDesc.compute(cv::imread("n13.jpg", cv::IMREAD_GRAYSCALE), desc);
    for (int i = 0; i < featureSize; i++)
        queries.ptr<float>(3)[i] = desc[i];
    cv::Mat predictions;
    // 测试SVM分类器
    svm->predict(queries, predictions);

    for (int i = 0; i < 4; i++)
        std::cout << "query: " << i << ": " << ((predictions.at<float>(i) < 0.0)? "Negative" : "Positive") << std::endl;

2.2 SVM 原理

在交通标志识别中，每个图像实例都由 8100 维 HOG 空间中的一个点表示。显然我们不可能可视化如此高维的空间，但 SVM 的思想是在高维空间中确定边界，利用边界可以区分属于不同类别的样本。更具体地说，这个边界实际上只是一个简单的超平面，可以在 2D 空间中解释这种思想，2D 空间中每个样本都可以表示为一个 2D 点。在这种情况下，超平面是一条简单的线：

这是十分简单的例子，但从概念上讲，在 2 维空间或 8100 维空间中 SVM 的工作方式都是一样的。上图演示了如何使用一条简单的线将属于两个不同类别的点分开，可以看出，空间中还存在许多不同的线可以将不同类别分开。因此，我们需要确定究竟选择哪条线？在这个问题之前，我们必须考虑到，用来构建分类器的样本只是所有可能样本的极小的一部分，而我们希望分类器不仅能够正确分离提供的样本集，而且还能够对没有见过的其他样本做出最佳决策，这通常称为分类器的泛化能力。理想情况下，分类超平面应该无偏的位于两个类之间。更正式地说，SVM 应当将超平面设置在使边界周围的边距最大化的位置，边距定义为分离超平面和正样本集中最近点之间的最小距离加上超平面和最近的负样本之间的距离，最近的点(定义边界点)称为支持向量 (support vectors)。SVM 定义了一个优化函数，用于识别这些支持向量。但是并不总可以仅使用直线分割不同类别，如果样本点的分布如下：

在这种情况下，简单的直线超平面无法实现合适的类别分离。 SVM 通过引入人工变量来解决这个问题，这些变量通过一些非线性变换将问题引入更高维空间。例如，在以上示例中，我们可以添加样本点到原点的距离作为附加变量，即计算每个点的 $r=\sqrt{(x^2+y^2)}$，可以得到一个三维空间，为简单起见，我们在 $(r,x)$ 平面上绘制点：

此时，样本点集可以被一个简单的超平面分隔开，我们需要在这个新空间中找到支持向量。事实上，在 SVM 公式中，不必将所有点都引入新空间，只需要定义一种方法来测量该更高维空间中的点到超平面距离。因此，SVM 定义了核函数，用于在更高维空间中测量此距离，而无需显式计算该空间中的点坐标。这只是从数学上解释了为什么可以在高维空间中有效计算产生最大边距的支持向量。这也解释了为什么在使用 SVM 时，需要指定要使用的核。正是通过应用这些核，可以实现非线性分隔，以便在核空间中更好的分隔不同类别。
然而，由于使用 SVM，我们经常使用非常高维的特征(例如，本节使用的 HOG 有 8100 维)，因此样本可能可以使用简单的超平面进行分离，这就是我们不使用非线性核，而使用线性核 (cv::ml::SVM::LINEAR) 的原因，生成的分类器在计算上更简单，但是对于更具挑战性的分类问题，核仍然是一个非常有效的工具。OpenCV 提供了许多标准核(例如，径向基函数和 sigmoid 函数)，用于将样本引入更高维的非线性空间，使不同类别可以通过超平面分离。SVM 有许多变体，最常见的变体是 C-SVM，它会对每个离群样本施加一个惩罚。
因为 SVM 具有严谨的数学基础，可以很好地处理非常高维的特征。事实上，当特征空间的维数大于样本数时，运行效果最好。与需要将所有样本点保存在内存中的最近邻居等方法相比，SVM 也是一种内存高效的算法，因为它们只需要存储支持向量。
定向梯度直方图和 SVM 组成了性能优异的分类器，这是由于 HOG 可以被视为一种强大的高维描述符，它捕获了对象样本的基本特征，HOG-SVM 分类器已成功应用于许多实际场景中，例如人物检测。

3. HOG 可视化

HOG 由组合在重叠块中的单元格构建而成，因此，很难可视化该描述符。然而，通常可以通过显示与每个单元格关联的直方图来表示。在这种情况下，与在常规条形图中对齐方向bin不同，可以使用星形绘制直方图，其中每条线都具有与其代表的 bin 相关联的方向，并且线的长度是与 bin 计数成正比，可以在图像上显示这些 HOG 表示，如下所示：

每个单元格 HOG 表示可以由一个简单的函数生成，该函数接受一个指向直方图的迭代器。然后为每个 bin 绘制正确方向和长度的线：

// 在每个单元格上绘制一个HOG 
void drawHOG(std::vector<float>::const_iterator hog,    // HOG迭代器 
            int numberOfBins,                           // HOG中的bin数
            cv::Mat &image,                             // 单元格图像
            float scale=1.0) {                          // 长度乘数
    const float PI = 3.1415927;
    float binStep = PI / numberOfBins;
    float maxLength = image.rows;
    float cx = image.cols / 2.;
    float cy = image.rows / 2.;

    // 迭代每个bin
    for (int bin = 0; bin < numberOfBins; bin++) {
        // bin 方向
        float angle = bin*binStep;
        float dirX = cos(angle);
        float dirY = sin(angle);
        // 线长度与bin尺寸的比例
        float length = 0.5*maxLength* *(hog+bin);
        // 绘制线
        float x1 = cx - dirX * length * scale;
        float y1 = cy - dirY * length * scale;
        float x2 = cx + dirX * length * scale;
        float y2 = cy + dirY * length * scale;
        cv::line(image, cv::Point(x1, y1), cv::Point(x2, y2), CV_RGB(255, 255, 255), 1);
    }
}

然后，HOG 可视化函数为每个单元格调用以上函数：

// 在图像上绘制HOG
void drawHOGDescriptors(const cv::Mat &image,   // 输入图像
                        cv::Mat &hogImage,      // 生成的HOG图像
                        cv::Size cellSize,      // 每个单元格的大小
                        int nBins) {            // bins 数量

    // 块大小是图像大小
    cv::HOGDescriptor hog(cv::Size((image.cols / cellSize.width) * cellSize.width, 
                            (image.rows / cellSize.height) * cellSize.height),
        cv::Size((image.cols / cellSize.width) * cellSize.width,
                    (image.rows / cellSize.height) * cellSize.height),	
        cellSize,       // 块步长
        cellSize,       // 单元格大小
        nBins);         // bins 数量
    // 计算 HOG
    std::vector<float> descriptors;
    hog.compute(image, descriptors);
    float scale= 2.0 / *std::max_element(descriptors.begin(), descriptors.end());
    hogImage.create(image.rows, image.cols, CV_8U);
    std::vector<float>::const_iterator itDesc= descriptors.begin();
    for (int i = 0; i < image.rows / cellSize.height; i++) {
        for (int j = 0; j < image.cols / cellSize.width; j++) {
            // 绘制每个单元格
            hogImage(cv::Rect(j*cellSize.width, i*cellSize.height, cellSize.width, cellSize.height));
            cv::Mat roi= hogImage(cv::Rect(j*cellSize.width, i*cellSize.height,
                                    cellSize.width, cellSize.height));
            drawHOG(itDesc, nBins, roi, scale);
            itDesc += nBins;
        }
    }
}

此函数计算具有指定单元大小组成的 HOG 描述符，因此，这种表示忽略了在每个块上进行的归一化影响。

4. 人物检测

OpenCV 提供了一个基于 HOG 和 SVM 的预训练人物检测器，SVM 分类器可用于通过在多个尺度上扫描图像上的窗口来检测完整图像中的实例，然后，构建分类器对图像执行检测：

    // 创建描述符
    std::vector<cv::Rect> peoples;
    cv::HOGDescriptor peopleHog;
    peopleHog.setSVMDetector(cv::HOGDescriptor::getDefaultPeopleDetector());
    // 检测人物
    peopleHog.detectMultiScale(myImage, // 输入图像
                peoples,                // 输出边界框列表
                0,                      // 阈值
                cv::Size(5, 5),         // 窗口步长
                cv::Size(40, 40),       // 填充图像
                1.1,                    // 缩放因子
                2);                     // 分组阈值，0表示不分组

以上代码中，窗口步幅用于定义单元格大小为 128×64 的模板如何在图像上移动(示例中，水平和垂直方向每次移动 4 个像素)。由于评估的窗口较少，较长的步幅可以使检测速度更快，但可能会错过一些人物实例。图像填充参数用于在图像的边界上添加像素，以便可以检测到图像边缘中的人物。SVM 分类器的标准阈值为 0 (正实例的标签值为 1，负实例的标签值为 -1)。如果想确定检测到的对象的确是一个人，那么可以提高这个阈值(这意味着我们需要高精度，但代价是会遗漏图像中的一些人)，反之，如果想确定检测到所有人(即需要高召回率)，那么可以降低阈值，但在这种情况下会出现更多的错误检测。获得的检测结果的示例如下所示：

需要注意的是，当分类器应用于完整图像时，在连续位置应用的多个窗口通常会导致一个正样本进行多次检测。当两个或多个边界框在同一位置重叠时，最好的办法是只保留其中一个。使用函数 cv::groupRectangles 能够将相似位置的相似大小的矩形组合在一起(该函数由 detectMultiScale 自动调用)。事实上，在特定位置获得一组检测甚至可以被视为一个指标，以确认在该位置确实有一个正实例，因此 cv::groupRectangles 函数允许指定检测集群的最小大小，以接受为正样本，并丢弃孤立检测，这是 detectMultiScale 方法的最后一个参数。将该参数设置为 0 可以保留所有检测，得到的结果如下图所示：

5. 完整代码

主函数文件 (trainSVM.cpp) 完整代码可以在 gitcode 中获取。

小结

定向梯度直方图 (Histogram of Oriented Gradients, HOG) 是基于图像梯度构建的直方图，是一种表示图像的有效方式。而支持向量机 (Support Vector Machine, SVM) 可以根据训练数据得到准确的二分类分类器，被广泛用于解决许多计算机视觉问题。HOG 和 SVM 组成了性能优异的分类器，本节中我们利用 SVM-HOG 构建目标检测模型。

系列链接

OpenCV实战（1）——OpenCV与图像处理基础
OpenCV实战（2）——OpenCV核心数据结构
OpenCV实战（3）——图像感兴趣区域
OpenCV实战（4）——像素操作
OpenCV实战（5）——图像运算详解
OpenCV实战（6）——OpenCV策略设计模式
OpenCV实战（7）——OpenCV色彩空间转换
OpenCV实战（8）——直方图详解
OpenCV实战（9）——基于反向投影直方图检测图像内容
OpenCV实战（10）——积分图像详解
OpenCV实战（11）——形态学变换详解
OpenCV实战（12）——图像滤波详解
OpenCV实战（13）——高通滤波器及其应用
OpenCV实战（14）——图像线条提取
OpenCV实战（15）——轮廓检测详解
OpenCV实战（16）——角点检测详解
OpenCV实战（17）——FAST特征点检测
OpenCV实战（18）——特征匹配
OpenCV实战（19）——特征描述符
OpenCV实战（20）——图像投影关系
OpenCV实战（21）——基于随机样本一致匹配图像
OpenCV实战（22）——单应性及其应用
OpenCV实战（23）——相机标定
OpenCV实战（24）——相机姿态估计
OpenCV实战（25）——3D场景重建
OpenCV实战（26）——视频序列处理
OpenCV实战（27）——追踪视频中的特征点
OpenCV实战（28）——光流估计
OpenCV实战（29）——视频对象追踪
OpenCV实战（30）——OpenCV与机器学习的碰撞
OpenCV实战（31）——基于级联Haar特征的目标检测