图像分析之ORB特征

Last updated on May 7, 2023 pm

[TOC]

Overview

  • Oriented FAST + Rotated BRIEF

Feature/Corner Detector

  • FAST方法 -- 定位特征点坐标
  • 矩方法 -- 特征点方向
  • 非极大值抑制 -- 特征点响应值（分数）
  • 图像金字塔 -- 特征点具有 尺度不变性

Descriptor

  • BRIEF -- 特征点描述子
  • 特征点方向 -- 描述子具有 旋转不变性

oFAST: FAST Keypoint Orientation

Multiscale Image Pyramid

  • level: 8
  • scale: 1.2
  • down sample: bilinear interpolation
  • produce FAST features (filtered by Harris ???) at each level in the pyramid

FAST (Features from Accelerated and Segments Test)

  • FAST-9: ≥ 9 contiguous pixels brighter than p+threshold

Procedure:

  1. Select a pixel p whose intensity is \(I_p\) and Select appropriate threshold value \(t\)
  2. the pixel p is a corner if there exists a set of \(n\) contiguous pixels in the circle (of 16 pixels) which are all brighter than \(I_p+t\), or all darker than \(I_p−t\)
    • Rapid rejection by testing 1, 9, 5 then 13: First 1 and 9 are tested if they are too brighter or darker. If so, then checks 5 and 13
    • If p is a corner, then at least three of these must all be brighter than \(I_p+t\) or darker than \(I_p−t\)

NMS (Non-Maximal Suppression)

非极大值抑制主要是为了避免图像上得到的“角点”过于密集，主要过程是，每个特征点会计算得到相应的响应得分，然后以当前像素点p为中心，取其邻域（如3x3 的邻域），判断当前像素p的响应值是否为该邻域内最大的，如果是，则保留，否则，则抑制。

Uniform Distribution (特征均匀化)

均匀化的方式一般有如下两种：

  • Grid网格化
  • K叉树

对于天空这种环境，Grid的方式提取的特征较少，不如K叉树的方式。

ORB-SLAM中使用 四叉树 DistributeOctTree() 来快速筛选特征点，筛选的目的是非极大值抑制，取局部特征点邻域中FAST角点相应值最大的点，而如何搜索到这些扎堆的的点，则采用的是四叉树的分快思想，递归找到成群的点，并从中找到相应值最大的点。

Orientation by Intensity Centroid (IC)

  • Rosin defines the moments of a patch as:

    \[ m_{p q}=\sum_{x, y} x^{p} y^{q} I(x, y) \]

    the first order moment of a patch \(I\) (patch size = 31)

    \[ \begin{aligned} m_{10} &= \sum_{x=-15}^{15} \sum_{y=-15}^{15} x I(x, y) = \sum_{y=0}^{15} {\color{blue} \sum_{x=-15}^{15} x \left[ I(x,y) - I(x, -y) \right] } \\ m_{01} &= \sum_{x=-15}^{15} \sum_{y=-15}^{15} y I(x, y) = \sum_{y=1}^{15} {\color{blue} \sum_{x=-15}^{15} y \left[ I(x,y) - I(x, -y) \right] } \end{aligned} \]

  • the intensity centroid

    \[ C=\left(\frac{m_{10}}{m_{00}}, \frac{m_{01}}{m_{00}}\right) \]

  • the orientation (the vector from the corner’s center to the centroid)

    \[ \theta=\operatorname{atan} 2\left(m_{01}, m_{10}\right) \]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    const int PATCH_SIZE = 31;
    const int HALF_PATCH_SIZE = 15;

    int m01 = 0;
    int m10 = 0;
    for(int y=-half_patch_size; y<half_patch_size; ++y){
        for(int x=-half_patch_size; x<half_patch_size; ++x){
            m01 += y * image.at<uchar>(kp.pt.y+y, kp.pt.x+x);
            m10 += x * image.at<uchar>(kp.pt.y+y, kp.pt.x+x);
        }
    }
    kp.angle = std::atan2(m01, m10)/CV_PI*180.0;

Gaussian Filter

  • ref: 图像分析之高斯滤波

  • start by smoothing image using a Gaussian kernel at each level in the pyramid in order to prevent the descriptor from being sensitive to high-frequency noise

  • Gaussian Kernel size: 7x7, Sigma: 2

  • 利用高斯滤波的可分离性，实现水平和垂直分开滤波，降低计算量，并进行定点化

rBRIEF: Rotation-Aware Brief

Brief of BRIEF (Binary robust independent elementary feature)

<img src="/img/post/image_features/brief.png"/>

  • In brief, each keypoint is described by a feature vector which is 128–512 bits string.

  • vector dim = 256 bits (32 bytes)

  • each vector \(\longleftrightarrow\) each keypoint

  • for each bit, select a pair of points in a patch \(I\) which centered a corner \(\mathbf{p}\) and compare their intensity

    \[ \mathbf{S}= \left(\begin{array}{l} \mathbf{p}_{1}, \ldots, \mathbf{p}_{n} \\ \mathbf{q}_{1}, \dots, \mathbf{q}_{n} \end{array}\right) \in \mathbb{R}^{(2 \times 2) \times 256} \]

    \[ \tau(\mathbf{I} ; \mathbf{p}_i, \mathbf{q}_i):= \left\{\begin{array}{ll} 1 & : \mathbf{I}(\mathbf{p}_i) < \mathbf{I}(\mathbf{q}_i) \\ 0 & : \mathbf{I}(\mathbf{p}_i) \geq \mathbf{I}(\mathbf{q}_i) \end{array}\right. \]

  • the descriptor (each bit \(\longleftrightarrow\) each pair of points \((\mathbf{p}_i, \mathbf{q}_i)\)):

    \[ f(n) = \sum_{i=1}^n 2^{i-1} \tau(\mathbf{I} ; \mathbf{p}_i, \mathbf{q}_i), \quad (n = 256) \]

steered BRIEF

  • 为了具有旋转不变性，引入该算法，但方差很小、相关性高

    \[ \mathbf{R}_{\theta} = \begin{bmatrix} \cos{\theta} & -\sin{\theta} \\ \sin{\theta} & \cos{\theta} \end{bmatrix} \]

    \[ \mathbf{S}_{\theta}=\mathbf{R}_{\theta} \mathbf{S}= \left(\begin{array}{l} \mathbf{p}_{1}', \ldots, \mathbf{p}_{n}' \\ \mathbf{q}_{1}', \dots, \mathbf{q}_{n}' \end{array}\right) \]

rBRIEF

  • rBRIEF shows significant improvement in the variance and correlation over steered BRIEF

  • 为了把steered BRIEF方差增大，相关性降低

  • 基于统计规律，利用了贪心算法进行筛选

  • construct a lookup table of precomputed BRIEF patterns 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // construct a lookup table of precomputed BRIEF patterns

    // 训练好的31*31邻域256对像素点坐标
    static int ORB_pattern[256*4] = {
          8, -3,  9,  5 /*mean (0), correlation (0)*/,
          4,  2,  7,-12 /*mean (1.12461e-05), correlation (0.0437584)*/,
        -11,  9, -8,  2 /*mean (3.37382e-05), correlation (0.0617409)*/,
          7,-12, 12,-13 /*mean (5.62303e-05), correlation (0.0636977)*/
          //                       .
          //                       .
          //                       .
    }

  • steered BRIEF

  • for each bit of the descriptors

    \[ \mathbf{p}_i' = \mathbf{R}_{\theta} (\mathbf{p}_i-\mathbf{p}) + \mathbf{p} \\ \mathbf{q}_i' = \mathbf{R}_{\theta} (\mathbf{q}_i-\mathbf{p}) + \mathbf{p} \]

    \[ \tau(\mathbf{I} ; \mathbf{p}_i', \mathbf{q}_i'):= \left\{\begin{array}{ll} 1 & : \mathbf{I}(\mathbf{p}_i') < \mathbf{I}(\mathbf{q}_i') \\ 0 & : \mathbf{I}(\mathbf{p}_i') \geq \mathbf{I}(\mathbf{q}_i') \end{array}\right. \]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    double degRad = kp.angle/180.0*CV_PI;
    double dcos = std::cos(degRad);
    double dsin = std::sin(degRad);

    vector<bool> d(256, false);
    for (int i = 0; i < 256; i++) {
        d[i] = 0;

        int p_offset_x = ORB_pattern[4*i+0];
        int p_offset_y = ORB_pattern[4*i+1];
        int q_offset_x = ORB_pattern[4*i+2];
        int q_offset_y = ORB_pattern[4*i+3];

        double pu = kp.pt.x + (dcos*p_offset_x - dsin*p_offset_y);
        double pv = kp.pt.y + (dsin*p_offset_x + dcos*p_offset_y);
        double qu = kp.pt.x + (dcos*q_offset_x - dsin*q_offset_y);
        double qv = kp.pt.y + (dsin*q_offset_x + dcos*q_offset_y);

        int pI = image.at<uchar>((int)pv, (int)pu);
        int qI = image.at<uchar>((int)qv, (int)qu);

        d[i] = (pI>=qI) ? 0 : 1;
    }

ORB Features in ORB-SLAM2

ORB特征点：

  • 二维坐标（2自由度）
  • 方向（灰度质心法，矩特征）
  • 金字塔层级
  • 不确定度（跟金字塔层级有关）
  • 描述子

ORB描述子匹配：

  • BoW
  • 暴力匹配
  • FLANN

ORB描述子匹配验证：

  • 通过 描述子间的距离阈值（通过最小、最大距离设置） 筛选
  • 特征点方向（图像块矩特征）一致性检查（直方图统计）
  • 到极线的距离（给定 基础矩阵）
  • 三维点
    • SLAM中已关联三维点的有效性
    • 视差检查（余弦距离）
    • 三角化后三维点的有效性
      • Z朝前
      • 重投影误差（考虑 卡方分布，受自由度影响）
Computer Vision
#Computer Vision #DIP #Image Features
图像分析之ORB特征
https://cgabc.xyz/posts/7cfdb1/
Author
Gavin Gao
Posted on
July 13, 2020
Licensed under