Bag of Visual Words

**视觉词袋（Bag of Visual Words, BoVW）**将文本检索的思想应用于图像（Sivic与Zisserman，2003）：将局部特征描述子量化为一个由离散”视觉词”组成的词汇表，将一张图像描述为词出现次数的直方图，并通过比较直方图来比较图像。它是SLAM中回环检测和重定位背后的经典引擎（例如ORB-SLAM中使用的DBoW2）。

流程

词汇表构建（离线）。 从训练语料库中收集大量局部描述子（例如ORB、SIFT），并用k-means将其聚类为 $K$ 个聚类中心——即视觉词。对于二值描述子，聚类中心是在Hamming空间中用中位数而非欧氏均值来计算的。
图像表示。 对每张新图像，提取描述子并将每个描述子分配给其最近的视觉词。该图像变成一个 $K$ 维直方图 $\mathbf{v}$ ，其中第 $k$ 个bin统计被分配给第 $k$ 个词的特征点数量。所有空间布局信息都被丢弃——这正是”词袋（bag）“这个名字的由来。
TF-IDF加权。 并非所有词的信息量都相同。每个bin按词频乘以逆文档频率进行加权：

$v_k = \frac{n_{k,d}}{n_d} \cdot \log\frac{N}{n_k}$

其中 $n_{k,d}$ 是词 $k$ 在图像 $d$ 中出现的次数， $n_d$ 是该图像中的词总数， $N$ 是数据库图像的数量， $n_k$ 是包含词 $k$ 的数据库图像数量。到处出现的词（地板纹理、树叶）会被降权；稀有且有区分度的词则在得分中占主导地位。

检索。 对加权后的直方图归一化并计算相似度得分——DBoW2使用一种基于L1的评分方式

$s(\mathbf{v}_1, \mathbf{v}_2) = 1 - \frac{1}{2}\left\lVert \frac{\mathbf{v}_1}{\lVert \mathbf{v}_1 \rVert} - \frac{\mathbf{v}_2}{\lVert \mathbf{v}_2 \rVert} \right\rVert_1$

——并返回得分最高的数据库图像作为回环检测候选。

层次化词汇树

一个扁平词汇表需要 $O(K)$ 次距离计算才能为每个描述子分配词，而具有区分度的检索通常需要 $K \sim 10^5$ – $10^6$ 个词，这种代价太高了。DBoW2/DBoW3将这些词组织成一棵词汇树（vocabulary tree），通过层次化k-means构建：每个节点分出 $k$ 个分支，共 $L$ 层，得到 $K = k^L$ 个叶子词。为一个描述子分配词，只需沿树逐层与 $k$ 个子节点比较——复杂度为 $O(kL)$ ，即相对于 $K$ 呈对数级。

两种索引结构使检索和验证变得快速：

倒排索引（Inverted index）：对每个词，记录包含该词的数据库图像列表（及其权重）。为查询打分时只需触及那些至少共享一个词的图像。
正向索引（Direct index）：对每张图像，按某个中间层级将特征按树节点分组。当检索到一个候选时，用于几何验证的对应关系只需在落在同一节点内的特征之间匹配即可找到——比暴力描述子匹配快得多。

实践要点

词汇表大小很关键：过小的词汇表会让不相似的特征碰撞到同一个词中（区分度低）；过大的词汇表会把匹配的特征分散到不同的词中（可重复性低）。检索系统之所以使用大词汇表，正是因为层次树能让分配过程的开销保持低廉。
回环检测的归一化：原始得分依赖于场景纹理的丰富程度，因此像ORB-SLAM这样的系统会用查询帧的共视关键帧中的最高得分来归一化候选帧的得分，把绝对阈值变成相对阈值，从而能够在不同环境之间迁移。
处处使用同一词汇表：一个预先训练好、与环境无关的词汇表（例如ORB-SLAM自带的ORB词汇表）在实践中表现出人意料地好，避免了每次部署都要重新训练。

局限性与验证步骤

BoVW丢弃了几何信息，因此两张纹理统计相似但描绘的并非同一地点的图像也可能得到很高的分数（感知混淆（perceptual aliasing）——走廊、砖墙等）。因此，实际的回环检测流程会将BoVW的输出仅视为候选项，并通过几何验证来确认：匹配特征，用RANSAC估计本质/基础矩阵或PnP姿态，只有当足够多的内点支持一致的几何关系时才接受这个回环。时序一致性检查（要求连续多帧匹配）进一步抑制误报。在一个视觉域上训练的词汇表迁移到差异很大的环境中时效果也会打折扣。

对SLAM的意义

里程计会产生漂移；回环检测正是让SLAM超越单纯航位推算的关键，而BoVW是一种能在与地图规模无关的常数时间内找到回环的经典方法。它同样为跟踪丢失后的重定位以及多会话地图对齐提供支持。即便在较新的系统中学习型全局描述子（NetVLAD及其后继者）取代了检索阶段，BoVW的架构——量化、加权、倒排索引、验证——仍然是参考设计，而且DBoW2式的词汇表由于速度快、体积小、只需CPU即可运行，仍在许多已部署的系统中运行。

动手实践

Global feature detection