朴素方法

在深度学习流行之前， 目标检测算法大多依赖手工设计的视觉特征与浅层机器学习模型， 并基于滑窗（sliding window）算法，完成目标检测任务。

在本节中，我们先基于传统方法， 阐述一个简单的行人检测算法， 使读者对目标检测的基本思路有一个初步的认识。

一个简单的行人检测算法

传统的行人检测算法大致遵循这样一个流程。

对于待检测的图片 $x$ ，首先将其分割成大小相同的正方形格子。

记图片的长和宽分别为 $H$ 和 $W$ 个像素，格子的边长为 $C$ 个像素（通常取 $C=8$），格子的行数和列数分别为 $h$ 和 $w$ 。 如果 $H$ 和 $W$ 恰好为 $C$ 的整数倍，则有

$$h = \frac{H}{C}, \quad w = \frac{W}{C}$$

如果不能整除，我们可以在后续的算法中忽略不完整的格子。

接下来，对每个格子中的图片区域计算方向梯度直方图（Histogram of Oriented Gradient, HOG）。 HOG 是一种手工设计的视觉特征，可以在一定程度上描述物体的轮廓，非常适合行人检测任务。

在这里，我们不需要关注 HOG 的计算细节，只需要知道 HOG 的计算结果是一个维度为 $d$ （通常 $d=36$）特征向量。

记 $x_{i,j}$ 为格子中第 $i$ 行、第 $j$ 列的子图，大小为 $C\times C$ 像素，$f_{i,j}$ 为对应的特征向量，

则有

$$f_{i,j} := \text{HOG}(x_{i,j}) \in \mathbb{R}^d \quad \forall 1\le i\le h, 1\le j\le w$$

从数值计算的角度来看，我们可以将全部 $h\times w$ 个格子所对应的特征按照空间位置排列成一个 $h\times w\times d$ 的三维数组。 这样，通过形如 f[i,j] 的位置索引，我们就可以得到对应位置的格子的特征。

# Given
#   image: as a numpy array
#   cell size: C
#   grid shape: h and w
# Compute feature of all cell

all_feat = np.zeros(h, w, d)
for i in range(h):
    for j in range(w):
        patch = image[i*C:i*C+C, j*C:j*C+c]
        feat[i, j, :] = hog(patch)

接下来，设置一个固定大小的窗口，例如 $64\times128$ 像素， 我们暂且假定行人在图像上大约占据这么大的区域。

将这个窗口置于图像的左上角，并与图像边界对齐。 这个窗口恰好能包含 $h_\text{w}=16$ 行， $w_\text{w}=8$ 列的格子。

我们将窗口中所有格子所对应的特征向量按顺序拼接起来，就可以得到一个 $h_\text{w} \times w_\text{w} \times d = 1152$ 维度的特征向量。 我们将这个向量作为这个窗口的特征向量。

最后，我们将这个向量送入一个训练好的二类分类器，例如 SVM ，就可以判断这个窗口中是否存在行人。

下一步，我们在图像上，以格子为单位向右向下滑动窗口，重复上述特征拼接、分类的过程。 窗口每滑到一个位置，我们就可以知道这个位置是否存在行人。 窗口滑完整幅图片每滑到一个位置，我们就可以知道图像的每个位置上是否包含行人。

由于窗口的大小固定为 $64\times128$ 像素，算法只能检测这个尺度的行人。 为了能使算法检测更大或更小的行人，我们通常将图片方法或缩小，再在不同大小的图片上重复上述过程。

通常我们会设定一个缩放比率 $r > 1$，并将原图按照 $r$、$r^2$、$r^3$……等倍数方法，或按 $1/r$、$1/r^2$、$1/r^3$ ……等倍数缩小。 这样，使用固定大小的窗口和对应的分类器，我们就可以检测 $64r\times128r$ 、 $\frac{64}{r}\times\frac{128}{r}$ 等不同尺度的行人了。

由于这些等比例缩放的图像可以在空间上叠成一个金字塔的形状，我们通常称其为图像金字塔(image pyramid)。

这是一个十分简单的例子， 但已经包含了目标检测系统中最关键的几个组件：滑窗、图像金字塔、图像特征和分类器。 滑窗遍历图像上所有可能的位置，图像金字塔遍历所有可能的目标大小，特征和分类器组成模式识别系统，针对每个位置和每个尺度判断是否存在行人。

分类器的训练

最后，我们还遗留了一个问题，即分类器的训练。 回顾整个系统，不难发现，直到窗口特征，窗口特征是基于设计好的特征提取算法计算出来的，而分类器需要训练。

最后，我们还遗留了一个问题：在使用这个检测系统之前，我们还需要其中训练分类器。 我们的分类器根据一个 1152 维度的特征向量判断其中是否出现了行人，因此我们需要一个监督学习的数据集{x_i, y_i}i-1^N 去训练这个分类器，这里 x 是特征，y 是是否有行人的标记。

然而这个数据并不是现成的。 一个行人检测的数据集只会包含若干图片，以及在每个图片上以矩形框的形式标记出行人的位置。

我们需要根据行人检测数据集去生成用于训练分类器的特征数据集。 这个过程也并不困难，首先我们依照上述参数生成图像金字塔，并借助滑窗，在图像上的每个位置提取特征， 我们考虑金字塔中第 i 张图像，左上角上坐标为 i,j 的一个框，我们可以得到一个特征，x_{r,i,j} $i*C*r$ $(i+hw)*C*r$

将其按照缩放比例映射回原图，如果在原图对应的位置有行人标注，我们就将这个将这个窗口定义为一个正样本，同时将 x,1 加入数据集。如果原图对应的区域内没有行人标注，我们就将其定义为副样本 当然，由于原图的标注并不一定和格子 Cr 对齐，因此在定义正负样本的时候，我们必须允许一定的误差。

由于多尺度滑窗遍历了图像的所有位置和尺度，而物体中的样本通常只在个别特定位置，以特定大小出现。因此滑窗产生的区域大部分都会标记为副样本。 正负样本的不平衡性对与分类器的训练并不是件好事。 为了解决这个问题，我们通常会丢弃一部分负样本了，而且是丢弃那些对与分类器非常简单的样本，选择那些比较难的样本进行训练，这些样本通常也就是那些和标注框有所重叠，但重叠度不高的样本。 这个过程通常是和训练分类器并行进行的，称为难负样本发掘，hard negative mining。

加速检测器

滑动窗口和图像金字塔本质上给出了所有可能包含物体的框，是一种空间上非常密集采样。而在所有可能的框中，只有个别框真正包含物体。将所有如何提高效率就成了一个自然问题。

解决这个问题的思路大体有两个：一种是级联法，我们仍然保持密集的采样，但使用计算量极低的分类器去除大量负样本，再在剩余的小样本集上，用准确率（precision）高的计算较为复杂的分类器找出包含物体的框。

另一种方法是 region proposal 方法，即精细设计采样过程，使得这个过程只产生那些可能包含物体的框，拒绝显然没有物体的框。

图片出处

• https://www.mdpi.com/1424-8220/18/4/1174
• https://stackoverflow.com/questions/34985196/opencv-using-svm-and-hog-for-person-detection
• https://www.sciencedirect.com/science/article/abs/pii/S0165168410003476