ORB（Oriented FAST and Rotated BRIEF）是一种高效、鲁棒、广泛应用于实时计算机视觉系统的特征提取算法。它结合了 FAST 角点检测器与 BRIEF 描述子，并添加了方向信息与尺度不变性，是一个轻量级但功能强大的特征点提取与描述算法。

---

ORB 算法原理详解

ORB 是由 OpenCV 的 Ethan Rublee 等人在 2011 年提出。它分为两部分：

1. 特征点检测：基于 FAST + Harris 排序

• 使用 FAST (Features from Accelerated Segment Test) 算法检测角点。
• 为了解决 FAST 不具备强度排序的缺陷，ORB 使用 Harris 角点响应函数 进行排序，选择前 N 个最显著的角点。

2. 方向分配：基于灰度质心法（Intensity Centroid）

• 计算角点邻域内像素的灰度质心，用于估计主方向：

  $$m_{pq}=\sum _{x,y}{x}^p{y}^{q}I(x,y)$$

  主方向为：

  $$\theta =\arctan \left(\frac{m_{01}}{m_{10}}\right)$$

3. 描述子生成：Rotated BRIEF

• 使用 BRIEF 描述子进行关键点周围图像的二值比较：

  $${\text{descriptor}}_i=\{\begin{array}{ll}1& \text{if }I(p_i)<I(q_i)\\ 0& \text{otherwise}\end{array}$$

• 为实现旋转不变性，对采样点对应用旋转矩阵使其相对于主方向对齐。

---

ORB 特征提取整体流程

图像灰度化
   ↓
FAST 角点检测
   ↓
Harris 角点排序 & 非极大值抑制
   ↓
为每个角点分配方向（灰度质心法）
   ↓
对每个角点周围区域构造旋转后的 BRIEF 描述子
   ↓
生成关键点 + 描述子

---

C++ 实现示例（不依赖 OpenCV）

以下为核心模块示意（可独立编译，需使用如 stb_image.h 读图或手动导入图像灰度矩阵）：

数据结构定义

struct KeyPoint {
    int x, y;
    float angle;
    float response;
};

using Descriptor = std::bitset<256>;

FAST 检测器（简化版本）

bool isCorner(const uint8_t* img, int width, int height, int x, int y) {
    const int threshold = 20;
    const int circle[16][2] = {
        {0,-3},{1,-3},{2,-2},{3,-1},{3,0},{3,1},{2,2},{1,3},
        {0,3},{-1,3},{-2,2},{-3,1},{-3,0},{-3,-1},{-2,-2},{-1,-3}
    };
    int center = img[y * width + x];
    int count = 0;
    for (int i = 0; i < 16; ++i) {
        int xx = x + circle[i][0];
        int yy = y + circle[i][1];
        if (xx < 0 || yy < 0 || xx >= width || yy >= height) continue;
        int val = img[yy * width + xx];
        if (std::abs(val - center) > threshold) count++;
    }
    return count >= 12;
}

灰度质心主方向估计

float computeOrientation(const uint8_t* img, int width, int x, int y) {
    int m01 = 0, m10 = 0;
    for (int dy = -15; dy <= 15; ++dy) {
        for (int dx = -15; dx <= 15; ++dx) {
            int xx = x + dx, yy = y + dy;
            if (xx < 0 || yy < 0 || xx >= width || yy >= height) continue;
            int val = img[yy * width + xx];
            m10 += dx * val;
            m01 += dy * val;
        }
    }
    return std::atan2(m01, m10);
}

BRIEF 描述子生成

Descriptor computeDescriptor(const uint8_t* img, int width, int x, int y, float angle) {
    static const int pattern[256][2] = {/* 预定义随机采样对 p[i], q[i] */};
    Descriptor desc;
    float cosA = std::cos(angle), sinA = std::sin(angle);
    for (int i = 0; i < 256; ++i) {
        int dx1 = pattern[i][0], dy1 = pattern[i][1];
        int dx2 = pattern[i][0] + 1, dy2 = pattern[i][1] + 1;
        int u1 = x + dx1 * cosA - dy1 * sinA;
        int v1 = y + dx1 * sinA + dy1 * cosA;
        int u2 = x + dx2 * cosA - dy2 * sinA;
        int v2 = y + dx2 * sinA + dy2 * cosA;
        if (u1 < 0 || v1 < 0 || u2 < 0 || v2 < 0 || u1 >= width || v1 >= height || u2 >= width || v2 >= height) continue;
        desc[i] = img[v1 * width + u1] < img[v2 * width + u2];
    }
    return desc;
}

主提取函数

std::vector<std::pair<KeyPoint, Descriptor>> extractORB(const uint8_t* img, int width, int height) {
    std::vector<std::pair<KeyPoint, Descriptor>> results;
    for (int y = 16; y < height - 16; ++y) {
        for (int x = 16; x < width - 16; ++x) {
            if (!isCorner(img, width, height, x, y)) continue;
            float angle = computeOrientation(img, width, x, y);
            Descriptor d = computeDescriptor(img, width, x, y, angle);
            results.push_back({ {x, y, angle, 0}, d });
        }
    }
    return results;
}

---

扩展支持图像金字塔构造多尺度特征

为了让 ORB 算法具备尺度不变性（scale invariance），需要在多个不同分辨率的图像上提取特征点。这一技术称为 图像金字塔（Image Pyramid），用于模拟图像在不同缩放下的外观。

---

图像金字塔概述

图像金字塔是一组逐级缩小的图像集合：

Level 0: 原始图像（尺度 1.0）
Level 1: 缩小为 1/√2（尺度 ~0.707）
Level 2: 缩小为 1/2（尺度 0.5）
...
Level N: 最小图像（尺度 ≈ 0.25）

每一层都可以进行特征点检测，并将检测到的特征点坐标统一映射到原始图像坐标系中。

---

构造图像金字塔

以下是构造金字塔的 C++ 代码（不依赖 OpenCV）：

std::vector<std::vector<uint8_t>> buildImagePyramid(const std::vector<uint8_t>& image,
                                                    int width, int height,
                                                    int levels, float scaleFactor,
                                                    std::vector<std::pair<int, int>>& sizes) {
    std::vector<std::vector<uint8_t>> pyramid;
    pyramid.push_back(image); // level 0

    int currW = width, currH = height;
    sizes.push_back({width, height});

    for (int i = 1; i < levels; ++i) {
        int newW = static_cast<int>(currW / scaleFactor);
        int newH = static_cast<int>(currH / scaleFactor);
        std::vector<uint8_t> down(newW * newH);

        // 简单的 box filter 下采样
        for (int y = 0; y < newH; ++y) {
            for (int x = 0; x < newW; ++x) {
                int px = static_cast<int>(x * scaleFactor);
                int py = static_cast<int>(y * scaleFactor);
                if (px >= currW) px = currW - 1;
                if (py >= currH) py = currH - 1;
                down[y * newW + x] = pyramid[i - 1][py * currW + px];
            }
        }

        pyramid.push_back(down);
        sizes.push_back({newW, newH});
        currW = newW;
        currH = newH;
    }

    return pyramid;
}

---

多尺度 ORB 特征提取流程

可以对每一层金字塔图像应用原始的 ORB 提取器，并将特征点坐标乘以其对应的放大因子（scale）映射到原图：

std::vector<std::pair<KeyPoint, Descriptor>> extractORBMultiScale(
    const std::vector<uint8_t>& image, int width, int height,
    int levels = 4, float scaleFactor = 1.2f) {

    std::vector<std::pair<KeyPoint, Descriptor>> allKeypoints;
    std::vector<std::pair<int, int>> sizes;
    auto pyramid = buildImagePyramid(image, width, height, levels, scaleFactor, sizes);

    float currentScale = 1.0f;
    for (int i = 0; i < levels; ++i) {
        const auto& img = pyramid[i];
        int w = sizes[i].first;
        int h = sizes[i].second;

        auto keypoints = extractORB(img.data(), w, h);  // 单尺度 ORB 提取函数

        for (auto& kp : keypoints) {
            kp.first.x = static_cast<int>(kp.first.x * currentScale);
            kp.first.y = static_cast<int>(kp.first.y * currentScale);
            allKeypoints.push_back(kp);
        }

        currentScale *= scaleFactor;
    }

    return allKeypoints;
}

---

注意事项

事项	说明
特征数量	可控制每层特征数上限，防止低层“挤占资源”
尺度归一化	若后续匹配或聚类，建议对尺度进行记录
描述子旋转适配	每一层都使用其对应的角度计算描述子，确保旋转不变性

---

ORB 算法的创新点

特性	ORB 方法
检测器	FAST + Harris 响应排序
描述子	BRIEF（高效）
方向不变性	灰度质心法估计主方向
旋转不变性	旋转 BRIEF 描述子
尺度不变性（可选）	使用图像金字塔扩展
速度	极快，适合实时应用
匹配效率	Hamming 距离（支持二进制匹配）

---

总结

• ORB 是轻量、高效、旋转不变的特征提取方法。
• 上述代码完全不依赖 OpenCV，可用于嵌入式或定制平台。
• 可与 Hamming 距离 + 暴力搜索或 FLANN 结合完成特征匹配。

---