面向初学者的目标检测 第一部分：梯度向量、HOG 与选择性搜索

中文精读

原文约 3,019 词 · 14 节

1. 面向初学者的目标检测（第一部分）：梯度向量、HOG 与选择性搜索

   • 这一篇是全系列的第一部分，从图像处理最基础的概念和几种图像分割方法讲起，暂不涉及深度神经网络。
   • 用于目标检测与识别的深度学习模型安排在第二、第三部分讨论（Part 4 仅出现在系列链接列表中）。
   • 文中说明作者起初把“目标识别”和“目标检测”混用，但二者并不等同：前者侧重判断图像中是否存在某物体，后者还需指出物体位置；两者高度相关，许多识别算法是检测的基础。

2. 图像梯度向量

   • 先区分导数（标量）、方向导数（沿单位向量方向的瞬时变化率）与梯度（向量，指向函数增长最快的方向，含全部偏导数信息）。
   • 图像处理关心颜色从一个极端到另一个极端（如灰度图的黑到白）的变化方向，因此要在像素上度量梯度；由于像素独立且不可再分，图像梯度是离散的。
   • 对像素 (x, y)，梯度向量为 [f(x+1,y)-f(x-1,y), f(x,y+1)-f(x,y-1)]，即左右、上下相邻像素的颜色差。
   • 梯度有两个属性：幅值（L2 范数 sqrt(gx²+gy²)）与方向（arctan(gy/gx)）。文中示例为 [-50, 50]，得到幅值 70.7107、方向 -45°。
   • 逐像素计算太慢，可把整幅图像矩阵看作 A，用卷积核一次完成：x 方向用核 [-1,0,1]，y 方向用 [+1,0,-1]ᵀ，示例结果分别为 -50 和 50。
   • 节末给出可运行的 Python 代码，用 sig.convolve2d 在 3×3 示例数据上以 mode='valid' 计算 G_x 与 G_y；因 numpy 数组表示中 40 排在 90 前面，y 方向核中 -1 相应列在 1 之前。
   python

   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')

3. 常用图像处理卷积核

   • Prewitt 算子不只用上下左右四个相邻像素，而是利用周围八个像素，结果更平滑；x、y 方向各对应一个 3×3 核。
   • Sobel 算子在 Prewitt 基础上给直接相邻像素更高权重，以强化其影响，同样是两个 3×3 核。
   • 不同卷积核服务于不同目标，如边缘检测、模糊、锐化等，文中给出维基页面作为更多示例与参考。

4. 示例：2004 年的 Manu

   • 用 2004 年 Manu Ginobili 的照片做实验，为简化先把照片转成灰度；彩色图像只需在每个颜色通道上分别重复同样过程。
   • 代码以 mode="L" 读图直接得到灰度图，故无需事先转换颜色；再定义 Sobel 的 x、y 两个核，用 mode='same' 做二维卷积得到 G_x 与 G_y。
   • 随后用 fig 的两个子图 ax1、ax2 分别 imshow((G_x+255)/2) 与 imshow((G_y+255)/2)（cmap='gray'）并标注 Gx、Gy，并排显示两幅梯度图。
   • 生成图多数区域呈灰色：像素差在 -255 到 255 之间，为显示需映射回 [0,255]，简单线性变换 (G+255)/2 会把梯度为 0（颜色恒定的背景）显示成 125 的灰色。
   python

   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)
   
   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()

5. 方向梯度直方图（HOG）

   • HOG（Histogram of Oriented Gradients）是从像素颜色中提取特征、用于构建物体识别分类器的一种高效方式。
   • 文中指出，掌握了图像梯度向量的知识，就不难理解 HOG 的工作方式。

6. HOG 如何工作

   • 第一步预处理图像，包括缩放与颜色归一化；第二步计算每个像素的梯度向量及其幅值和方向。
   • 第三步把图像划分成许多 8×8 像素的单元（cell），每个单元内 64 个像素的幅值按 9 个无符号方向区间（0–180° 而非 0–360°）分桶累加；这是基于经验的实用选择。
   • 若某像素梯度方向落在两个桶之间，其幅值按比例拆分到两个桶而非全给较近者；例如幅值 8、方向 15° 的向量，给 0° 桶 2、给 20° 桶 6。
   • 这种设计使直方图在图像出现轻微形变时更稳定。
   • 最后以 2×2 单元（16×16 像素）的块（block）在图像上滑动，每个块内 4 个单元的直方图拼成 36 维向量并归一化为单位权重，所有块向量拼接成最终 HOG 特征向量，可送入 SVM 等分类器学习识别任务。

7. 图像分割（Felzenszwalb 算法）

   • 一张图里出现多个物体（现实照片几乎都如此）时，需要先找出可能包含目标物体的区域，使分类更高效。
   • Felzenszwalb 与 Huttenlocher（2004）提出基于图的方法，把图像分割成相似的区域；它也是后文讨论的常用区域建议算法 Selective Search 的初始化方法。
   • 用无向图 G=(V,E) 表示输入图像：顶点 vi 表示像素，边 (vi,vj) 连接两个顶点，边权 w 衡量两者的不相似度（可用颜色、位置、强度等维度量化），权重越高越不相似。
   • 分割解 S 是把 V 划分成若干连通分量 {C}；直观上相似像素应属同一分量，不相似的应分到不同分量。

8. 图的构建方式

   • 网格图（Grid Graph）：每个像素只与周围 8 个邻居相连，边权为两像素强度值之差的绝对值。
   • 最近邻图（Nearest Neighbor Graph）：每个像素是特征空间 (x, y, r, g, b) 中的一个点，边权为两个像素特征向量之间的欧氏距离。

9. 关键概念

   • 内部差异 Int(C) 取分量最小生成树（MST）中最大边权：即使去掉所有权重小于该值的边，分量仍保持连通。
   • 两个分量之间的差异 Dif(C1,C2) 取跨越两个分量、连接二者的所有边中的最小权重；若两者之间没有边，则 Dif 为无穷大。
   • 最小内部差异 MInt(C1,C2) 取 Int(C1)+τ(C1) 与 Int(C2)+τ(C2) 中的较小者，其中 τ(C)=k/|C| 用于给出有意义的差异阈值；k 越大，越容易得到更大的分量。
   • 用成对区域比较谓词评估分割质量：当且仅当 Dif(C1,C2) > MInt(C1,C2) 时判为 True，才视为两个独立分量；否则说明分割过细，两者应合并。

10. 图像分割如何工作

    • 整体是自底向上的过程。给定 G=(V,E)，|V|=n、|E|=m，先把所有边按权重升序排列为 e1,…,em。
    • 初始时每个像素各自成一个分量，共 n 个分量；把第 k 步的分割快照记为 Sᵏ。
    • 依次对 k=1,…,m 取第 k 条边 ek=(vi,vj)：若 vi、vj 已在同一分量，则不做处理，Sᵏ = Sᵏ⁻¹。
    • 若二者属于 Sᵏ⁻¹ 中的两个不同分量 Ciᵏ⁻¹、Cjᵏ⁻¹，则当 w(vi,vj) ≤ MInt(Ciᵏ⁻¹, Cjᵏ⁻¹) 时合并，否则不做处理。
    • 文中给出用网格图构建、k=300 时对一张室内场景的分割效果图，并指出对分割性质及其存在性证明感兴趣的读者可参阅原论文。

11. 示例：2013 年的马努

    • 以 2013 年马努·吉诺比利（Manu Ginobili）的照片作为示例图，此时他的秃斑已相当明显；为简单起见，仍使用灰度图片。
    • 不从头实现算法，而是直接调用 skimage.segmentation.felzenszwalb 对图像做分割；代码先用 scipy.misc.imread 以 mode="L" 读入图片。
    • 分别用 scale=100 和 scale=1000 运行两次 Felzenszwalb 算法，并用 matplotlib 以 121/122 两个子图并排展示两个分割掩码，子图横轴标签分别为 k=100 与 k=1000。
    • k=100 得到更细粒度的分割，产生较多小区域，马努的秃斑被识别为独立区域；k=1000 得到更粗粒度分割，区域倾向于更大。
    python

    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()

12. 选择性搜索（Selective Search）

    • 选择性搜索是一种常用算法，用于产生可能包含物体的候选区域（region proposal）。
    • 它建立在图像分割结果之上，利用基于区域的特征（而不只是单个像素的属性）做自底向上的层次化合并。

13. 选择性搜索的工作方式

    • 初始化阶段：先运行 Felzenszwalb 与 Huttenlocher 的基于图的图像分割算法，得到初始区域。
    • 随后用贪心算法迭代合并区域：先计算所有相邻区域之间的相似度，再把最相似的两个区域合并。
    • 合并出新区域后，重新计算该区域与其邻居的相似度。
    • 不断重复“合并最相似区域”这一步，直到整幅图像合并成单一区域为止。

14. 配置变体与参考文献

    • 对任意两个区域 (r_i, r_j)，选择性搜索提出四种互补的相似度度量：颜色相似度、纹理相似度、尺寸相似度和形状相似度。
    • 纹理相似度采用适合材质识别的算法，例如 SIFT；尺寸相似度鼓励小区域尽早合并；形状相似度希望一个区域能填补另一个区域的空隙。
    • 通过调整 Felzenszwalb 与 Huttenlocher 算法中的阈值 k、更换颜色空间、以及挑选不同的相似度指标组合，可以生成多样化的选择性搜索策略。
    • 质量最好的配置同时混合多种初始分割方案、融合多种颜色空间、并组合全部相似度度量；质量（模型复杂度）与速度之间需要权衡。
    • 参考文献列出 Dalal 与 Triggs 的 HOG 行人检测论文、Felzenszwalb 与 Huttenlocher 的基于图的高效图像分割论文，以及 Satya Mallick、Chris McCormick 的 HOG 与梯度向量教程。