8月23日计算机视觉理论学习笔记——图像检索

---

前言

本文为8月23日计算机视觉理论学习笔记——图像检索，分为两个章节：

• 相似图像检索；
• 在高维空间检索。

---

一、相似图像检索

1、颜色

将一张图像描述成一个256 维度的特征向量。

• 自编码器： 通过神经网络进行特征提取出针对学习样本的通用特征降维方法。

• 颜色特征提取：
  • 目标：统计图片的颜色成分 ⇒ 颜色聚类直方图；
  • 方法：使用 K-means 对图片 Lab 像素值进行聚类。

• 颜色特征相似度计算：
  1. 颜色直方图距离：EMD（Earth Mover Distance，推土机距离）；
  2. 色差距离：CIEDE2000——Lab 空间中两个颜色之间的视觉相似度；
     • 色差容忍度（Tolerance）：无法感知的色差。
  3. EMD 距离直观解释：
     • 三个土堆：每个土堆有5个单位的土量；
     • 三个土坑：每个土坑能容纳的土量分别为 3、7、5；
     • 不同土堆和土坑之间的距离不同，分别是 1、2、4；
     • 一趟只能搬运1单位的土；
     • 目标：以最小的行走距离（EMD），将所有土堆运输到土坑。
     • 解决方案：E1⇒ H1: 3⇒ H2: 2, E2⇒ H2: 5⇒ H3: 5，距离=3×1+2×2+5×1+5×1=17。

2、纹理（texture）

重复模式：元素或基元按一定规则排列。

• 纹理特征：

  • 反映同质现象；
  • 包含物体表面结构组织排列的重要信息。

• Gabor 滤波器组： 类似于人类的生物视觉系统：

  • 频域：属于加窗傅里叶变换；
  • 空域：一个高斯核函数和正弦平面波的乘积；
  • 尺度：6频率：
    • 频率：1、2、3、4、5、6；
    • 尺寸：25、35、49、69、97、137.
  • 8方向：
    • 0、22.5、45、67.5、90、112.5、135、157.5.

• Gabor 纹理特征提取：
  1. 彩色图片灰度化；
  2. 提取灰度图的 Gabor 滤波器特征；
  3. 使用 K-means++ 聚类所有像素的 Gabor 特征。

3、局部特征

(1)、局部特征点特征提取

• 局部特征点；
• 特征描述子。

(2)、图之间的相似度匹配

• 两个图 SIFT 点集之间的匹配对数；
• 双向匹配。

4、Bag of Visual Word 视觉词汇的字典

由图片集的所有视觉词汇构成，不是现成的，需要构建：

• 特征检测：特征点——SIFT、SURF等；
• 特征表示：SIFT 描述子、颜色、纹理等；
• 字典生成：K-means 等聚类。

---

二、在高维空间检索

为解决从海量且具有高维度的数据集合中找到最相似的数据，需采用近邻查找技术（Nearest Neighbor）加快查找过程。

1、KD-Tree

用于多维度检索的二叉平衡树。

• 构建过程：
  1. 输入：N个D维空间的数据点；
  2. 确定 split 值——方差最大的维度；
  3. 确定分割点——split 维度上的中值点，首次为根节点；
  4. 确定分割面——垂直 split 维度的超平面；
  5. 确定左右子树：
     • 左子树：split 维度上小于分割点；
     • 右子树：split 维度上大于分割点。
  6. 迭代以上步骤，直到空间只包含一个数据点。

示例：

1. 输入：(2, 3), (5, 4), (4, 7), (9, 6), (7, 2), (8, 1)；
2. 确定 （7, 2）是根节点；
3. 左子树：(2, 3), (5, 4), (4, 7)；
4. 右子树：(8, 1), (9, 6)。

• 最近邻查询： 从根节点开始，根据每个维度的 split 维进行左右子树的查询，直到叶子节点。

示例：查询点 (2, 4.5)：

• 路径：(7, 2) ⇒ (5, 4) ⇒ (4, 7)；
• 回溯：(5, 4) ⇒ (2, 3)。

2、局部敏感哈希 LSH

使 2个相似度很高的数据以较高的概率映射成同一个 hash 值，而令2个相似度很低的数据以极低的概率映射成同一个 hash 值。

• 构建 LSH 索引：
  1. 重构 LSH 函数 $g$：串接 k个具有 $(r1,r2,P_1,P_2)$ 局部敏感性的哈希原子函数；
  2. 独立、随机选取 L个 LSH 函数；
  3. 构建 L个 LSH 索引表；
  4. 计算查询的 L个 LSH 值。

3、原子哈希函数 P-stable LSH

$$h_{a,b}(\upsilon )=[\frac{a\cdot \upsilon +b}{r}]:{\mathcal{R}}^d\to \mathcal{N}$$

• 把d维向量 $\upsilon$ 映射为一条直线上的一个整数值；
• 随即投射 $a$：在 P-stable 分布上独立、随机选取的d维向量；
• 桶宽 $r$：映射直线上的分段长度；
• 随机偏移 $b$：在 $[0,r]$ 上均匀随机选取的偏移值。

---