目标检测入门 Part 1：梯度向量，HOG 和 SS

在 "目标检测入门"系列文章中，将介绍一些用于图像处理和对象检测的基本概念，算法和流行的深度学习模型。第1部分介绍了梯度向量的概念，HOG（Histogram of Oriented Gradients）算法以及图像分割的选择性搜索。

转载声明: 本文参考 Lil’Log 的相关内容，并进行翻译和编辑

1 图像梯度方向

首先，我想确保我们可以区分以下术语。它们非常相似，密切相关，但不完全相同。

在图像处理中，我们想知道颜色从一种极端变化到另一种极端的方向（例如，在灰度图像上从黑色变为白色）。因此，我们要测量颜色像素上的“梯度”。图像上的梯度是离散的，因为每个像素都是独立的，无法进一步拆分。

图像梯度矢量被定义为度量每个单独的像素，在x轴和y轴的像素的颜色的变化。该定义与连续多变量函数的梯度一致，该函数是所有变量的偏导数的向量。假设 $f(x, y)$ 记录着像素 $(x, y)$ 的颜色，则像素 $（x，y）$ 的梯度矢量定义如下：

$\nabla f(x, y) = \begin{bmatrix} g_x \\ g_y \end{bmatrix} = \begin{bmatrix} \frac{\partial f}{\partial x} \\[6pt] \frac{\partial f}{\partial y} \end{bmatrix} = \begin{bmatrix} f(x+1, y) - f(x-1, y)\\ f(x, y+1) - f(x, y-1) \end{bmatrix}$

其中 $\frac{\partial f}{\partial x}$ 是 $x$ 方向上的偏导数，是用来计算目标左右两侧的相邻像素之间的色差，用 $f(x+1, y) - f(x-1, y)$ 来计算。类似的，$\frac{\partial f}{\partial y}$ 是 $y$ 方向上的偏导数，是用来计算目标上下两侧的相邻像素之间的色差，用 $f(x, y+1) - f(x, y-1)$

图像梯度有两个重要属性：

• 大小 是向量的L2范数, $g = \sqrt{ g_x^2 + g_y^2 }$.
• 方向 是两个方向上偏导数之比的反正切, $\theta = \arctan{(g_y / g_x)}$.

Fig. 1. 为了计算目标像素在位置（x，y）的梯度向量，我们需要知道其四个相邻像素（或八个周围像素，取决于内核）的颜色。

Fig. 1.中示例的梯度向量为:

$\nabla f = \begin{bmatrix} f(x+1, y) - f(x-1, y)\\ f(x, y+1) - f(x, y-1) \end{bmatrix} = \begin{bmatrix} 55-105\\ 90-40 \end{bmatrix} = \begin{bmatrix} -50\\ 50 \end{bmatrix}$

因此，

• 大小是 $\sqrt{50^2 + (-50)^2} = 70.7107$，
• 方向是 $\arctan{(-50/50)} = -45^{\circ}$。

反复对每个像素重复进行梯度计算过程太慢。但是，它可以很好地转换为在整个图像矩阵上用 $\mathbf{A}$ 进行卷积运算，其中 $\mathbf{A}$ 是专门设计的卷积核之一。

让我们从 Fig 1 中示例的 x 方向开始。$[-1,0,1]$ 在 x 轴上滑动；$\ast$ 是卷积运算符：

$\mathbf{G}_x = [-1, 0, 1] \ast [105, 255, 55] = -105 + 0 + 55 = -50$

同样，在y方向上，我们采用卷积核 $[+1, 0, -1]^\top$：

$\mathbf{G}_y = [+1, 0, -1]^\top \ast \begin{bmatrix} 90\\ 255\\ 40 \end{bmatrix} = 90 + 0 - 40 = 50$

在 python 中尝试一下：

1
2
3
4
5

import numpy as np
import scipy.signal as sig
data = np.array([[0, 105, 0], [40, 255, 90], [0, 55, 0]])
G_x = sig.convolve2d(data, np.array([[-1, 0, 1]]), mode='valid') 
G_y = sig.convolve2d(data, np.array([[-1], [0], [1]]), mode='valid')

这两个函数分别返回array([[0], [-50], [0]]) 和 array([[0, 50, 0]]) （请注意，在 numpy 数组表示中，40显示在90的前面，因此-1在内核中的1之前相应地列出。）

通用图像处理内核

Prewitt 算子: 不仅依赖四个直接相邻的相邻像素，还利用八个周围的像素获得更平滑的结果。

$\mathbf{G}_x = \begin{bmatrix} -1 & 0 & +1 \\ -1 & 0 & +1 \\ -1 & 0 & +1 \end{bmatrix} \ast \mathbf{A} \text{ and } \mathbf{G}_y = \begin{bmatrix} +1 & +1 & +1 \\ 0 & 0 & 0 \\ -1 & -1 & -1 \end{bmatrix} \ast \mathbf{A}$

Sobel 算子: 为了更加强调直接相邻像素的影响，它们被赋予更高的权重。

$\mathbf{G}_x = \begin{bmatrix} -1 & 0 & +1 \\ -2 & 0 & +2 \\ -1 & 0 & +1 \end{bmatrix} \ast \mathbf{A} \text{ and } \mathbf{G}_y = \begin{bmatrix} +1 & +2 & +1 \\ 0 & 0 & 0 \\ -1 & -2 & -1 \end{bmatrix} \ast \mathbf{A}$

为不同的目标创建了不同的内核，例如边缘检测，模糊，锐化等等。查看此维基页面以获取更多示例和参考。

范例：2004 年的 Manu

让我们用 2004 年吉诺比利的照片进行一个简单的实验[下载照片],那时他仍然有很多的头发。为简单起见，首先将照片转换为灰度。对于彩色图像，我们只需要分别在每个彩色通道中重复相同的过程即可。

Fig. 2. 在2014年还有头发的 Manu Ginobili. (图片来源: Manu Ginobili’s bald spot through the years)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import numpy as np
import scipy
import scipy.signal as sig
# With mode="L", we force the image to be parsed in the grayscale, so it is
# actually unnecessary to convert the photo color beforehand.
img = scipy.misc.imread("manu-2004.jpg", mode="L")

# Define the Sobel operator kernels.
kernel_x = np.array([[-1, 0, 1],[-2, 0, 2],[-1, 0, 1]])
kernel_y = np.array([[1, 2, 1], [0, 0, 0], [-1, -2, -1]])

G_x = sig.convolve2d(img, kernel_x, mode='same') 
G_y = sig.convolve2d(img, kernel_y, mode='same') 

# Plot them!
fig = plt.figure()
ax1 = fig.add_subplot(121)
ax2 = fig.add_subplot(122)

# Actually plt.imshow() can handle the value scale well even if I don't do 
# the transformation (G_x + 255) / 2.
ax1.imshow((G_x + 255) / 2, cmap='gray'); ax1.set_xlabel("Gx")
ax2.imshow((G_y + 255) / 2, cmap='gray'); ax2.set_xlabel("Gy")
plt.show()

Fig. 3. 在示例图像上应用Sobel算子核.

您可能会注意到大多数区域都是灰色的。由于两个像素之间的差在 -255 和 255 之间，因此出于显示目的，我们需要将它们转换回 [0，255]。一个简单的线性变换 $(\mathbf{G}+ 255)/2$ 会将所有零（即，不变色的背景的梯度没有变化）变为 125（显示为灰色）。

2 方向梯度直方图（HOG）

方向梯度直方图（HOG）是从像素颜色中提取特征以构建对象识别分类器的有效方法。有了图像梯度矢量的知识，不难理解HOG的工作原理。开始吧！

HOG 的工作原理

1. 预处理图像，包括调整大小和颜色归一化。

2. 计算每个像素的梯度矢量及其大小和方向。

3. 将图像分成许多 $8\times8$ 像素单元。在每个像元中，将这64个像元的大小值进行合并，并累加到9个无符号方向的 bin 中（无符号，所以 0-180 度而不是 0-360 度；这是基于经验实验的切实可行的选择）。

为了获得更好的鲁棒性，如果像素的梯度矢量的方向位于两个bin之间，则其幅度不会全部进入更近的 bin 中，而是成比例地分配在两个 bin 中。例如，如果像素的梯度向量的大小为8，且度为15，则它在度0和20的两个存储 bin 之间，我们将2分配给 bin 0，将6分配给 bin 20。

这种有趣的配置使直方图在小失真应用于图像时更加稳定。

Fig. 4. 如果一个梯度矢量的降级在两个 bin 之间，如何分割它的大小。 (Image source: https://www.learnopencv.com/histogram-of-oriented-gradients/)

4. 然后，在图像上滑动 2x2 单元（即 16x16 像素）的块。在每个块区域中，将4个单元格的4个直方图连接到具有36个值的一维向量中，然后进行归一化以具有单位权重。最终的HOG特征向量是所有块向量的串联。可以将其输入到SVM等分类器中，以学习对象识别任务。

范例：2004年的 Manu

让我们重用上一节中的相同示例图像。记住我们已经对于整个图像计算了 $\mathbf{G}_x$ 和 $\mathbf{G}_y$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

N_BUCKETS = 9
CELL_SIZE = 8  # Each cell is 8x8 pixels
BLOCK_SIZE = 2  # Each block is 2x2 cells

def assign_bucket_vals(m, d, bucket_vals):
    left_bin = int(d / 20.)
    # Handle the case when the direction is between [160, 180)
    right_bin = (int(d / 20.) + 1) % N_BUCKETS
    assert 0 <= left_bin < right_bin < N_BUCKETS

    left_val= m * (right_bin * 20 - d) / 20
    right_val = m * (d - left_bin * 20) / 20
    bucket_vals[left_bin] += left_val
    bucket_vals[right_bin] += right_val

def get_magnitude_hist_cell(loc_x, loc_y):
    # (loc_x, loc_y) defines the top left corner of the target cell.
    cell_x = G_x[loc_x:loc_x + CELL_SIZE, loc_y:loc_y + CELL_SIZE]
    cell_y = G_y[loc_x:loc_x + CELL_SIZE, loc_y:loc_y + CELL_SIZE]
    magnitudes = np.sqrt(cell_x * cell_x + cell_y * cell_y)
    directions = np.abs(np.arctan(cell_y / cell_x) * 180 / np.pi)

    buckets = np.linspace(0, 180, N_BUCKETS + 1)
    bucket_vals = np.zeros(N_BUCKETS)
    map(
        lambda (m, d): assign_bucket_vals(m, d, bucket_vals), 
        zip(magnitudes.flatten(), directions.flatten())
    )
    return bucket_vals

def get_magnitude_hist_block(loc_x, loc_y):
    # (loc_x, loc_y) defines the top left corner of the target block.
    return reduce(
        lambda arr1, arr2: np.concatenate((arr1, arr2)),
        [get_magnitude_hist_cell(x, y) for x, y in zip(
            [loc_x, loc_x + CELL_SIZE, loc_x, loc_x + CELL_SIZE],
            [loc_y, loc_y, loc_y + CELL_SIZE, loc_y + CELL_SIZE],
        )]
    )

以下代码简单地调用函数来构造直方图并将其绘制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Random location [200, 200] as an example.
loc_x = loc_y = 200

ydata = get_magnitude_hist_block(loc_x, loc_y)
ydata = ydata / np.linalg.norm(ydata)

xdata = range(len(ydata))
bucket_names = np.tile(np.arange(N_BUCKETS), BLOCK_SIZE * BLOCK_SIZE)

assert len(ydata) == N_BUCKETS * (BLOCK_SIZE * BLOCK_SIZE)
assert len(bucket_names) == len(ydata)

plt.figure(figsize=(10, 3))
plt.bar(xdata, ydata, align='center', alpha=0.8, width=0.9)
plt.xticks(xdata, bucket_names * 20, rotation=90)
plt.xlabel('Direction buckets')
plt.ylabel('Magnitude')
plt.grid(ls='--', color='k', alpha=0.1)
plt.title("HOG of block at [%d, %d]" % (loc_x, loc_y))
plt.tight_layout()

在上面的代码中，我以左上角位于 [200，200] 的块为例，这是该块的最终归一化直方图。您可以使用代码来更改要通过滑动窗口标识的块位置。

Fig. 5. 一个块的HOG直方图演示

该代码主要用于演示计算过程。有许多已实现HOG算法的现成库，例如 OpenCV，SimpleCV 和 scikit-image。

3 图像分割（Felzenszwalb算法）

当一幅图像中存在多个对象时（几乎每张真实照片都存在），我们需要确定一个可能包含目标对象的区域，以便可以更有效地执行分类。

Felzenszwalb 和 Huttenlocher (2004) 提出了一种使用基于图的方法将图像分割成相似区域的算法。这也是选择性搜索（一种流行的区域提议算法）的初始化方法，我们将在后面讨论。

假设，我们使用无向图 $G=(V, E)$ 代表输入图像。一个交点 $v_i \in V$ 代表一个像素。一条边 $e = (v_i, v_j) \in E$ 连接两个顶点 $v_i$ 和 $v_j$。相关权重 $w(v_i, v_j)$ 衡量之间的差异 $v_i$ 和 $v_j$。可以在颜色，位置，强度等维度上量化差异性。权重越高，两个像素的相似性越小。分割解决方案 $S$ 是将 $V$ 划分为多个连接的组件。直观上，相似的像素应属于相同的组件，而相异的像素应分配给不同的组件。

图形构造

有两种方法可以根据图像构造图形。

• 网格图: 每个像素仅与周围的邻居连接（总共8个其他单元）。边缘权重是像素强度值之间的绝对差。
• 最近邻图: 每个像素都是特征空间（x，y，r，g，b）中的一个点，其中（x，y）是像素位置，（r，g，b）是RGB中的颜色值。权重是两个像素特征向量之间的欧几里得距离。

关键概念

在为良好的图分区（也称为图像分割）制定标准之前，让我们定义几个关键概念：

• 内部差异: $Int(C) = \max_{e\in MST(C, E)} w(e)$, 其中 $MST$ 是组件的最小生成树。组件 $C$ 仍然可以保持连接，即使我们移除了所有权重小于 $Int(C)$ 的边。
• 两个组件之间的区别: $Dif(C_1, C_2) = \min_{v_i \in C_1, v_j \in C_2, (v_i, v_j) \in E} w(v_i, v_j)$。如果它们之间没有边缘 $Dif(C_1, C_2) = \infty$。
• 最小内部差异: $MInt(C_1, C_2) = min(Int(C_1) + \tau(C_1), Int(C_2) + \tau(C_2))$, 其中 $\tau(C) = k / \vert C \vert$ 帮助确保我们对组件之间的差异有一个有意义的阈值。随着更高 $k$，则很有可能导致组件更大。

通过对给定的两个区域 $C_1$ 和 $C_2$ 定义一个成对区域比较预测来评估分割的质量:

$D(C_1, C_2) = \begin{cases} \text{True} & \text{ if } Dif(C_1, C_2) > MInt(C_1, C_2) \\ \text{False} & \text{ otherwise} \end{cases}$

只有当预测为 True 时，我们才将它们视为两个独立的组件。否则，分割太精细，可能应该合并它们。

图像分割的工作原理

该算法遵循自下而上的过程。给定 $G=(V, E)$ and $|V|=n, |E|=m$：

1. 边缘按重量升序排列，标记为 $e_1, e_2, \dots, e_m$。
2. 最初，每个像素都保留在自己的组件中，因此我们从 $n$ 个组件开始。
3. 重复 $k=1, \dots, m$:
   • 步骤 $k$ 的分割快定义为 $S^k$。
   • 第 k 个边缘定义为 $e_k = (v_i, v_j)$。
   • 如果 $v_i$ 和 $v_j$ 属于同一个组件, 什么也不做，此时 $S^k = S^{k-1}$.
   • 如果 $v_i$ 和 $v_j$ 在分割快 $S^{k-1}$ 中属于不同组件 $C_i^{k-1}$ 和 $C_j^{k-1}$，如果 $w(v_i, v_j) \leq MInt(C_i^{k-1}, C_j^{k-1})$，我们希望将它们合并为一个; 否则什么也不做.

如果您对分割属性的证明以及分割属性为何始终存在感兴趣，请参阅原文

Fig. 6. 在Felzenszwalb基于图的分割算法（k = 300）中通过网格图构造检测到的带有分割的室内场景。

示例：2013年的 Manu

这一次，我会用老吉诺比利在2013年[照片]作为示例图像时，他的秃斑已经长大了强烈。为了简单起见，我们使用灰度图片。

Fig. 7. 2013年秃头的Manu Ginobili。 (Image source: Manu Ginobili’s bald spot through the years)

与其从头开始编码，不如让我们将 skimage.segmentation.felzenszwalb 应用于图像。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

import skimage.segmentation
from matplotlib import pyplot as plt

img2 = scipy.misc.imread("manu-2013.jpg", mode="L")
segment_mask1 = skimage.segmentation.felzenszwalb(img2, scale=100)
segment_mask2 = skimage.segmentation.felzenszwalb(img2, scale=1000)

fig = plt.figure(figsize=(12, 5))
ax1 = fig.add_subplot(121)
ax2 = fig.add_subplot(122)
ax1.imshow(segment_mask1); ax1.set_xlabel("k=100")
ax2.imshow(segment_mask2); ax2.set_xlabel("k=1000")
fig.suptitle("Felsenszwalb's efficient graph based image segmentation")
plt.tight_layout()
plt.show()

该代码运行了 Felzenszwalb 算法的两个版本，如图8所示。左边的 $k=100$ 会生成细粒度的分割，该分割具有识别 Manu 秃点的小区域。右边的 $k=1000$ 输出区域趋于更大的粗粒度分割。

Fig. 8. Felsenszwalb 基于图的高效图像分割应用于2013年 Manu 的照片。

4 选择性搜索

选择性搜索是提供可能包含对象的区域提议的常用算法。它建立在图像分割输出的基础之上，并使用基于区域的特征（注意：不仅是单个像素的属性）来进行自下而上的层次分组。

选择性搜索的工作原理

1. 在初始化阶段，应用 Felzenszwalb 和 Huttenlocher 的基于图的图像分割算法来创建要开始的区域。
2. 使用贪婪算法将区域迭代地组合在一起：
   • 首先，计算所有相邻区域之间的相似度。
   • 将两个最相似的区域分组在一起，并在结果区域及其邻居之间计算新的相似度。
3. 重复对最相似区域进行分组的过程（步骤2），直到整个图像变为单个区域为止。

Fig. 9. 选择性搜索的详细算法。

配置变化

给定两个地区 $(r_i, r_j)$，选择性搜索提出了四个互补的相似性度量：

• 颜色：相似
• 纹理：使用对材料识别效果很好的算法，例如 SIFT.
• 大小：鼓励小区域尽早合并。
• 形状：理想情况下，一个区域可以填补另一个区域的空白。

通过（i）调整阈值 k在 Felzenszwalb 和 Huttenlocher 的算法中，（ii）更改色彩空间和（iii）选择相似性指标的不同组合，我们可以产生一组多样化的“选择性搜索”策略。生成具有最高质量的区域建议的版本配置有（i）各种初始分割建议的混合，（ii）多种颜色空间的混合，以及（iii）所有相似性度量的组合。毫不奇怪，我们需要在质量（模型复杂性）和速度之间取得平衡。

References

[1] Dalal, Navneet, and Bill Triggs. “Histograms of oriented gradients for human detection.” Computer Vision and Pattern Recognition (CVPR), 2005.

[2] Pedro F. Felzenszwalb, and Daniel P. Huttenlocher. “Efficient graph-based image segmentation.” Intl. journal of computer vision 59.2 (2004): 167-181.

[3] Histogram of Oriented Gradients by Satya Mallick

[4] Gradient Vectors by Chris McCormick

[5] HOG Person Detector Tutorial by Chris McCormick