ORB-SLAM3代码详解 - 第 03 篇 · ORB 特征提取：金字塔、FAST 与四叉树均匀化

ORB-SLAM3代码详解 – 第 03 篇 · ORB 特征提取：金字塔、FAST 与四叉树均匀化

核心源码：src/ORBextractor.cc（约 1197 行）。特征提取是每一帧、每一个关键帧的首个处理环节，
负责把图像转换为"特征点 + 描述子"。特征点的质量与空间分布直接影响后续的匹配、三角化与
光束法平差（BA）。本篇分析其四个核心环节：图像金字塔构建、FAST 角点提取、四叉树均匀化、
ORB 描述子计算。

行号、常量均基于仓库 commit 4452a3c。相关函数可在 ORBextractor::operator() 处设断点验证。

1. 为什么是 ORB，而不是 SIFT/SURF

SLAM 是实时系统：每秒二三十帧，每帧几百个点都要提特征、算描述子、做匹配。SIFT/SURF 精度高，但太慢、且描述子是浮点向量（128 维），匹配要算欧氏距离。

ORB（Oriented FAST and Rotated BRIEF）的选择是工程权衡的典范：

一句话：ORB 用"够好 + 极快"换掉了 SIFT 的"最好但慢"。SLAM 要的是每帧都按时算完，而不是单帧最优。

2. 三个尺寸常量

ORBextractor.cc 顶部定义了三个贯穿全文件的常量（71-73 行）：

const int PATCH_SIZE = 31; // 计算描述子/方向的图像块边长
const int HALF_PATCH_SIZE = 15; // 半径（质心法的圆形邻域半径）
const int EDGE_THRESHOLD = 19; // 图像四周预留的边界宽度

为什么需要 EDGE_THRESHOLD？因为算描述子要在特征点周围取 31×31 的块、算方向要取半径 15 的圆。太靠边的点会越界，所以提点时四周留出安全边界。后面金字塔的 copyMakeBorder 和提点的 minBorderX 都和它有关。

3. 图像金字塔：尺度不变性的来源

同一个物体，离相机近时占的像素多、远时占的像素少。要在不同距离都能匹配，就得在多个尺度上找特征——这就是图像金字塔。

3.1 尺度系数预计算（构造函数）

构造函数里把每一层的尺度因子提前算好（约 420-430 行）：

mvScaleFactor[i] = mvScaleFactor[i–1] * scaleFactor; // 1, 1.2, 1.44, …
mvLevelSigma2[i] = mvScaleFactor[i] * mvScaleFactor[i]; // 尺度的平方
mvInvScaleFactor[i] = 1.0f / mvScaleFactor[i];
mvInvLevelSigma2[i] = 1.0f / mvLevelSigma2[i];

默认 scaleFactor=1.2、nLevels=8，于是 8 层的缩放比是 1, 1.2, 1.44, …, 约 3.58。

mvLevelSigma2 这个量后面到处都是。第 09/14 篇讲 BA 时，信息矩阵 = mvInvLevelSigma2[octave] · I——意思是"在高层（模糊层）提到的点，定位不确定性大，权重要小"。所以这里的预计算不是炫技，是为优化埋的伏笔。

3.2 每层该提多少点？等比数列分配

总特征数 nFeatures（默认 1000）不是均分到 8 层，而是按尺度等比递减分配（约 434-446 行）：

float factor = 1.0f / scaleFactor; // ≈0.833
float nDesiredFeaturesPerScale =
nfeatures * (1 – factor) / (1 – pow(factor, nlevels));
for (int level = 0; level < nlevels–1; level++) {
mnFeaturesPerLevel[level] = cvRound(nDesiredFeaturesPerScale);
nDesiredFeaturesPerScale *= factor; // 每层乘 factor 递减
}
mnFeaturesPerLevel[nlevels–1] = max(nfeatures – sumFeatures, 0); // 最后一层兜底

直觉：底层（原图）面积大、信息多，多分点；越往上图越小，少分点。这是个公比 factor 的等比数列，保证各层加起来正好 ≈ nFeatures。

3.3 ComputePyramid：逐层缩小 + 加边

void ORBextractor::ComputePyramid(cv::Mat image) {
for (int level = 0; level < nlevels; ++level) {
float scale = mvInvScaleFactor[level];
Size sz(cvRound(image.cols*scale), cvRound(image.rows*scale));
// … 申请带 EDGE_THRESHOLD 边界的大图 temp …
if (level != 0) {
resize(mvImagePyramid[level–1], mvImagePyramid[level], sz, 0,0, INTER_LINEAR);
copyMakeBorder(..., EDGE_THRESHOLD, ..., BORDER_REFLECT_101+BORDER_ISOLATED);
} else {
copyMakeBorder(image, temp, EDGE_THRESHOLD, ..., BORDER_REFLECT_101);
}
}
}

两个细节：

• 逐层缩：第 level 层是从 level-1 层 resize 来的（而非每次从原图），误差累积小、也更快。
• **copyMakeBorder 用 BORDER_REFLECT_101（镜像反射）**填边界，而不是补 0。补 0 会在边界制造假的强梯度，污染 FAST 检测和描述子。

4. FAST 提取与四叉树均匀化

这是 ORB-SLAM 系列相对原始 ORB 最重要的改进。朴素 FAST 的致命问题：特征点扎堆——纹理强的区域（如一棵树、一块招牌）冒出一大片点，纹理弱的区域（白墙）一个都没有。点扎堆意味着几何约束都集中在局部，BA 会"偏科"，定位不稳。

ORB-SLAM3 的解法分两步：先密集提点，再用四叉树筛成均匀分布。

4.1 第一步：网格化密集提 FAST（ComputeKeyPointsOctTree）

把每层图像切成 35×35 像素的小格子，在每个格子里独立提 FAST（约 781-846 行）：

const float W = 35; // 格子边长
// … 算出 nCols, nRows, wCell, hCell …
for (int i = 0; i < nRows; i++)
for (int j = 0; j < nCols; j++) {
// 先用高阈值 iniThFAST 提
FAST(cell, vKeysCell, iniThFAST, true);
if (vKeysCell.empty()) // ← 关键：提不到就降级
FAST(cell, vKeysCell, minThFAST, true); // 用低阈值 minThFAST 再提
// 把格子内坐标还原成层坐标
for (auto &kp : vKeysCell) { kp.pt.x += j*wCell; kp.pt.y += i*hCell; ... }
}

“高阈值提不到就降级到低阈值”（iniThFAST=20 → minThFAST=7）是个朴素而有效的设计：保证连白墙、暗角这种弱纹理格子也尽量挤出几个点，让全图都有候选。第 02 篇 yaml 里那两个参数（iniThFAST/minThFAST）就是控制这里——图像偏暗时调小 minThFAST 能多提点。

注意格子提取时相邻格有 6 像素重叠（maxY = iniY+hCell+6），避免落在格子边界上的角点被切掉漏检。

这一步提取的候选点数量很大（vToDistributeKeys 预留了 nfeatures*10），且分布仍不均匀，随后由四叉树进行筛选。

4.2 第二步：四叉树均匀化（DistributeOctTree）

这是 ORB-SLAM 特征均匀化的核心算法。其基本思想为：

不断把图像区域四等分，每个最终的小区域只保留响应最强的 1 个点。 区域多了，点自然就铺匀了。

算法分三阶段（约 555-779 行）：

阶段 ① 初始化根节点。按图像宽高比算出初始节点数 nIni（通常宽图分成几个并排的方块根节点），把所有候选点按 x 坐标分配进去：

const int nIni = round((maxX–minX) / (maxY–minY)); // 宽高比，决定初始几个根节点
// 每个 ExtractorNode 是一个矩形区域，持有落在其中的 vKeys
vpIniNodes[kp.pt.x/hX]->vKeys.push_back(kp); // 按 x 把点扔进对应根节点

每个 ExtractorNode 就是一个矩形（四个角 UL/UR/BL/BR）+ 它框住的一批关键点。

阶段 ② 反复分裂。遍历所有节点，调 DivideNode 把一个矩形切成田字形四块，点按位置落入四个子块：

// DivideNode：把当前矩形从中点切成 n1(左上) n2(右上) n3(左下) n4(右下)
const int halfX = ceil((UR.x–UL.x)/2.0f);
const int halfY = ceil((BR.y–UL.y)/2.0f);
// 按 kp 落在哪个象限分到 n1/n2/n3/n4

分裂的终止与剪枝规则（这是精华）：

• 节点里只剩 1 个点 → 标记 bNoMore=true，不再分（叶子）；
• 节点里没有点 → 直接删掉（空区域不浪费）；
• 当节点总数 ≥ 目标点数 N，或再分也无法增加节点数（size==prevSize）→ 停。

阶段 ③ 精细分裂（接近目标时的优先策略）。当一轮分裂后节点数快要超过 N 时（size + nToExpand*3 > N），不再无脑全分，而是优先分裂"点最多"的节点——因为点最多的节点最"挤"，分裂它对均匀化收益最大：

sort(vPrevSizeAndPointerToNode.begin(), ..., compareNodes); // 按节点内点数排序
for (从点最多的节点开始分裂) {
DivideNode(...);
if (lNodes.size() >= N) break; // 一旦凑够 N 个节点立即收手
}

阶段 ④ 每节点留最强点。最后，每个节点（区域）里只保留 FAST 响应 response 最大的那个点：

for (每个 node) {
cv::KeyPoint* pKP = &vNodeKeys[0];
for (k=1..) if (vNodeKeys[k].response > maxResponse) pKP = &vNodeKeys[k];
vResultKeys.push_back(*pKP); // 一个区域 → 一个代表点
}

整个过程图示：

初始: 候选点严重扎堆 四叉树分裂后: 密集区被切得更细
┌───────────────┐ ┌───┬───┬───────┐
│ ····· · │ │· │ · │ │ 每个小格最终
│ ······ · │ ───────▶ ├─┬─┼─┬─┤ · │ 只留 1 个最强点
│ ····· │ │·│·│·│·│ │ → 点数受控且分布均匀
│ · · │ ├─┴─┼─┴─┤ · │
└───────────────┘ └───┴───┴───────┘

最终效果：特征点数量被控制在每层目标值 mnFeaturesPerLevel 附近，且空间分布均匀。均匀分布的特征带来分布更广的几何约束，是 ORB-SLAM 系列建图与定位稳定性的重要来源。

4.3 收尾：还原坐标与尺度信息

均匀化后，把点的坐标加上边界偏移、记录所在层（octave）和块尺寸（约 880-895 行）：

keypoints[i].pt.x += minBorderX;
keypoints[i].pt.y += minBorderY;
keypoints[i].octave = level; // 记录所在金字塔层 → 后续 BA 信息矩阵据此定权重
keypoints[i].size = PATCH_SIZE * mvScaleFactor[level];

octave 字段很重要：它告诉后续模块"这个点是在哪个尺度提的"，匹配时的搜索半径、BA 时的权重都依赖它。

5. 灰度质心法：给每个点算方向

旋转不变的来源。BRIEF 本身不抗旋转，所以先给每个点算一个"主方向"，描述子按这个方向旋转后再算，旋转就被抵消了。

ORB 用灰度质心法（IC_Angle，约 76-103 行）：在点周围的圆形邻域里，把"质量"看作灰度值，求质心相对中心的方向。

static float IC_Angle(const Mat& image, Point2f pt, const vector<int>& u_max) {
int m_01 = 0, m_10 = 0;
const uchar* center = &image.at<uchar>(cvRound(pt.y), cvRound(pt.x));
// 中心行 v=0
for (int u = –HALF_PATCH_SIZE; u <= HALF_PATCH_SIZE; ++u)
m_10 += u * center[u];
// 上下对称地逐行累加圆形邻域内的矩
for (int v = 1; v <= HALF_PATCH_SIZE; ++v) {
int d = u_max[v]; // 该行的圆形边界（预计算）
for (int u = –d; u <= d; ++u) {
int val_plus = center[u + v*step], val_minus = center[u – v*step];
v_sum += (val_plus – val_minus);
m_10 += u * (val_plus + val_minus);
}
m_01 += v * v_sum;
}
return fastAtan2((float)m_01, (float)m_10); // θ = atan2(m01, m10)
}

• $m_{10}={\sum }_{u,v}u\cdot I(u,v)$，$m_{01}={\sum }_{u,v}v\cdot I(u,v)$ 是图像矩；
• 质心方向 $\theta =\arctan 2(m_{01},m_{10})$ 就是该点的主方向。

u_max（即 umax）是什么？ 圆形邻域每一行的半宽。直接遍历 31×31 方块会把角上的像素也算进去，破坏旋转不变性。构造函数里预计算了每行的圆边界（约 453-470 行），用 sqrt(HALF_PATCH²-v²) 并做对称化处理，保证邻域是个圆而非方块。

6. Rotated BRIEF：算出 256 位二进制描述子

有了方向，就能算描述子了（computeOrbDescriptor，约 107-145 行）。BRIEF 的本质：在点周围按预定义的 256 对采样点，比较每对像素的灰度大小，大于得 0、小于得 1，拼成 256 位。

static void computeOrbDescriptor(const KeyPoint& kpt, const Mat& img,
const Point* pattern, uchar* desc) {
float angle = kpt.angle * factorPI;
float a = cos(angle), b = sin(angle); // 旋转矩阵
const uchar* center = &img.at<uchar>(cvRound(kpt.pt.y), cvRound(kpt.pt.x));

// 关键宏：取采样点时先按方向旋转坐标
#define GET_VALUE(idx) \\
center[ cvRound(pattern[idx].x*b + pattern[idx].y*a)*step + \\
cvRound(pattern[idx].x*a – pattern[idx].y*b) ]

for (int i = 0; i < 32; ++i, pattern += 16) { // 32 字节 × 8 位 = 256 位
int t0, t1, val;
t0 = GET_VALUE(0); t1 = GET_VALUE(1); val = t0 < t1;
t0 = GET_VALUE(2); t1 = GET_VALUE(3); val |= (t0 < t1) << 1;
// … 一个字节比较 8 对点 …
desc[i] = (uchar)val;
}
}

三个要点：

算描述子前先高斯模糊：见下一节 operator() 里的 GaussianBlur(…, Size(7,7), 2, 2)。BRIEF 只比单个像素，对噪声极敏感；先模糊一下，描述子才稳定、可重复。

7. 主流程串联：operator()

所有零件在仿函数 operator()（约 1086 行）里串起来。Frame 构造时就是调用它：

int ORBextractor::operator()(InputArray _image, ..., vector<KeyPoint>& _keypoints,
OutputArray _descriptors, std::vector<int>& vLappingArea) {
ComputePyramid(image); // ① 建金字塔（§3）
vector<vector<KeyPoint>> allKeypoints;
ComputeKeyPointsOctTree(allKeypoints); // ② 提点 + 四叉树均匀化 + 算方向（§4,§5）

for (int level = 0; level < nlevels; ++level) {
Mat workingMat = mvImagePyramid[level].clone();
GaussianBlur(workingMat, workingMat, Size(7,7), 2, 2, BORDER_REFLECT_101); // ③ 模糊
computeDescriptors(workingMat, keypoints, desc, pattern); // ④ 算描述子（§6）

for (auto& keypoint : keypoints) {
if (level != 0) keypoint->pt *= scale; // ⑤ 各层坐标统一缩放回原图尺度
// ⑥ 按是否落在双目重叠区，分流到 mono / stereo 索引段
if (落在 vLappingArea 内) { _keypoints[stereoIndex—] = ...; }
else { _keypoints[monoIndex++] = ...; }
}
}
return monoIndex;
}

最后两个工程细节：

• 坐标统一回原图尺度：keypoint->pt *= scale。无论在哪层提的，输出坐标都换算到原始图像分辨率，下游不用关心金字塔。
• vLappingArea 双目重叠区分流：这是 ORB-SLAM3 为双目鱼眼加的优化。落在左右目重叠区的点被放到数组尾部（stereoIndex 倒着填），便于后续左右匹配。普通单目场景这段不影响。

8. 工程提示（本篇踩坑）

• nFeatures：默认 1000（EuRoC）。室内低纹理或易丢失场景可提高至 1500~2000；嵌入式等算力受限场景可降至 600~800。该值并非越大越好：弱纹理区域强行提取的点响应低、噪声大，会污染匹配与 BA。
• iniThFAST/minThFAST：图像偏暗、对比度低时调小 minThFAST（如 5）以提取更多点；图像噪点较多时适当调大，以过滤伪角点。
• 四叉树与非均匀化对比：将 ComputeKeyPointsOctTree 替换为被注释的 ComputeKeyPointsOld（网格保留法），可观察到地图点云结块、定位抖动加剧，直观反映均匀化的作用。
• 金字塔层数 nLevels：层数越多对大尺度变化越鲁棒，但提取耗时增加，通常 8 层即可。
• 大畸变／鱼眼：边缘畸变较大时，特征分布与描述子可重复性下降。ORB-SLAM3 通过相机模型（第 05 篇）与双目重叠区分流予以缓解。
• 性能：特征提取通常是 Tracking 的主要耗时之一。加速可先降低 nFeatures 与 nLevels，再结合 -march=native（第 02 篇）。Debug 构建下该环节无法满足实时性，不宜据此测量帧率。

9. 本篇小结 & 下一篇

本篇要点：

第 04 篇分析 ORBmatcher：描述子距离的计算、旋转直方图去外点，以及投影匹配、词袋匹配、极线匹配、Sim3 匹配等策略各自适用的场景。