特征检测与匹配

10 Apr 2019

Reading time ~3 minutes

1 特征提取概述

1.1 图像特征

图像特征主要包括三种类型：角点、边缘、区域。其中，在表达图像特征时角点的应用最为广泛，因为角点在任意方向的一个微小变动都会引起图像灰度的很大变化，因此角点也称为兴趣点（interest point）、关键点（key point）或特征点（feature）等。

1.2 特征检测与匹配

特征点由关键点和描述子组成。其中，描述子通常是一个向量，描述了该关键点周围的像素信息。只要两个特征点的描述子在向量空间上的距离相近，就可以认为它们是相同的特征点。

特征检测的主要方法有：SIFT、SURF、ORB。

1.2.1 SIFT特征

SIFT方法（Scale-Invariant Feature Transform，尺度不变特征变换）由David Lowe于1999年发表于计算机视觉国际会议。该方法有四个主要步骤：

尺度空间的极值检测。搜索所有尺度空间上的图像，通过高斯微分函数来识别潜在的对尺度和选择不变的兴趣点；
特征点定位。在每个候选的位置上，通过一个拟合精细模型来确定位置尺度，关键点的选取依据其稳定程度；
特征方向赋值。基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向，后续的所有操作都是对于关键点的方向、尺度和位置进行变换，从而提供这些特征的不变性；
特征点描述。在每个特征点周围的邻域内，在选定的尺度上测量图像的局部梯度，然后将其变换到允许较大的局部变形和光照的表示方法

该方法对于旋转、尺度缩放、亮度变化保持不变，对于视角变化、仿射变换、噪声也保持一定程度的稳定性。

1.2.2 SURF特征

SURF方法（Speeded Up Robust Features，加速稳健特征）由Herbert Bay发表于2006年发表于欧洲计算机视觉会议。SURF是对SIFT算法的改进，提升了算法的执行效率，为算法在实时计算机系统中应用提供了可能。

1.2.3 ORB特征

ORB方法（Oriented FAST and Rotated BRIEF）是一种快速特征点提取和描述的算法，由Ethan Rublee、Vincent Rabaud、Kurt Konolige和Gary R.Bradski于2011年在文章“ORB：An Efficient Alternative to SIFT or SURF”中提出。该算法分为两部分，分别是特征点提取和特征点描述。特征提取由FAST（Features from Accelerated Segment Test）算法发展而来，特征点描述根据BRIEF（Binary Robust Independent Elementary Features）描述算法改进。ORB将FAST特征点的检测方法与BRIEF特征描述子结合起来，并在它们原来的基础上做了改进与优化，其速度是SIFT的100倍，SURF的10倍。

2 ORB特征检测与匹配

2.1 oFAST: FAST Keypoint Orientation

ORB采用FAST算法检测特征点，并为其添加了一个方向，称作oFAST。

2.1.1 FAST特征点检测

检测候选特征点周围一圈的像素值，如果候选点周围领域内有足够多的像素点与该候选点的灰度值差别够大，则认为该候选点为一个特征点。

\[N=\sum_x\left|I(x)-I(p)\right|>\varepsilon_d\]

其中，\(I(x)\)为圆周上任意一点的灰度；\(I(p)\)为圆心的灰度；\(\varepsilon_d\)为灰度差的阈值，如果N大于给定阈值，一般为周围圆圈点的四分之三，则认为p是一个特征点。

为了获得更快的结果，如果测试了候选点周围每隔90度的点，应该至少有三个和候选点的灰度值差足够大，否则不用再计算其它点，直接认为该候选点不是特征点。假如采用圆的半径为3，则需要比较16个周边像素点，如下图所示：

2.1.2 基于灰度质心的角度方向

首先定义一个图像的矩为

\[m_{pq}=\sum_{xy}x^py^qI(x,y)\]

根据图像的矩可以找到质心为

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

由此可以构造一个由特征点p指向灰度质心C的向量，其角度为

\[\theta=tan^{-1}(m_{01},m_{10})\]

当灰度质心C与特征点p很接近时，测量结果变得很不稳定，但这种情况很少见。与其它方法相比，质心法受图像噪声的影响最小。

2.2 rBRIEF: Rotation-Aware Brief

ORB采用BRIEF算法来计算一个特征点的描述子，其核心思想是在关键点p的周围以一定模式选取N个点对，把这N个点对的比较结果组合起来作为描述子。

2.2.1 BRIEF描述子的计算过程

BRIEF是由EPFL的Calonder在ECCV2010上提出的。主要思路就是在特征点附近随机选取若干点对，将这些点对的灰度值做二进制比较，组合成一个二进制串，并将这个二进制串作为该特征点的特征描述子。

计算步骤如下

（1）以关键点p为圆心，以d为半径作圆O。

（2）在圆O内某一模式选取n个点对，\(\{x_1,y_1\}, \{x_2,y_2\}, \{x_3,y_3\},..., \{x_n,y_n\}\)。

（3）定义操作\(\tau\)

\[\tau(p;x,y)= \left\{ \begin{array}{rcl} &1 &p(x)<p(y)\\ &0 &p(x)\ge p(y) \end{array} \right.\]

（4）分别对已选取的点进行\(\tau\)操作，将得到的结果进行组合

\[f_n(p)=\sum_{1\le i\le n}2^{i-1}\tau(p;x_i,y_i)\]

例如，取n=4，得4个点对\(\{x_1,y_1\}, \{x_2,y_2\}, \{x_3,y_3\}, \{x_4,y_4 \}\)

对这4个点对进行\(\tau\)操作，得到

\[\tau(p;x_1,y_1)=1\\ \tau(p;x_2,y_2)=0\\ \tau(p;x_3,y_3)=1\\ \tau(p;x_4,y_4)=1\]

最终得描述子为1011。

在选取点对时，以当前关键点为原点，以水平方向为x轴，以垂直方向为y轴建立坐标系。当图片发生旋转时，坐标系不变，同样的取点模式取出来的点却不一样，计算得到的描述子也不一样，由此可以看出BRIEF描述子不具备旋转不变性。并且BRIEF描述子对噪声非常敏感，需要对图像进行高斯平滑处理。

总结得到BRIEF算法的缺点如下：

不具备旋转不变性
对噪声敏感
不具备尺度不变性

2.2.2 Steered BRIEF

将n个点对\((x_i,y_i)\)表示成如下\(2\times n\)矩阵

\[S= \left( \begin{array}{rcl} x_1,&..., &x_n\\ y_1,&..., &y_n \end{array} \right)\]

利用图像得角度\(\theta\)和其旋转矩阵可以得出S矩阵的可旋转形式

\[S_\theta=R_\theta S\]

于是新的二进制串可以表示为

\[g_n(p,\theta):=f_n(p)|(x_i,y_i)\in S_\theta\]

2.2.3 rBRIEF

三种特征描述子的分布如下

其中，x轴表示距离均值0.5的距离，y轴表示特征点数量统计。

比较BRIEF和steered BRIEF两种算法，可以看到BRIEF算法落在0上的特征点数较多，说明其均值在0.5左右，方差较大，可区分性较强。均值落在0.5时，方差有最大值0.25。而steered BRIEF失去了这个特性，容易引起误匹配。

为了解决方差较小的问题，减少描述子之间的相关性，论文中使用了统计学习的方法重新选择点对集合。首先建立300k个特征点测试集。列举特征点\(31\times31\)邻域所有可能的binary test，每个binary test由邻域中一对\(5\times5\)子窗口组成，用子窗口的灰度平均值来代替原先某个点的值。若将邻域的宽度记作\(w_p=31\)，将子窗口的宽度记作\(w_t=5\)，于是所有可能的子窗口数量为\(N=(w_p-w_t)^2=729\)。如果想要从中选取两个窗口，那么有\(\left(\begin{array}{rcl}N \\ 2 \end{array}\right)\)种选取方法，消除其中重叠的部分，最终得到了M=205590种可能的选取方法，从这M种方法种选取256种，算法如下：

对300k测试集中每个特征点\(31\times31\)邻域的按M种方法取\(5\times5\)子窗口对，比较大小，形成二进制串。
将这些二进制串按其均值距0.5的距离排序，并组成一个向量T。
贪婪搜索：
1. 将T中第一列放入结果向量R，并将其从T中移除。
2. 取T中的下一列和R中所有列向量计算相关性，如果结果小于设定的阈值，就将该列放入R中，否则丢弃。
3. 重复上一步直至R中有256列，如果R中列数小于256，则提高阈值继续搜索。

这就是rBRIEF算法。相比于steered BRIEF，该方法对于方差和相关性有显著提高。

2.3 总结

相比于先前的SURF、SIFT特征提取算法，ORB的运行效率都更快，且具备旋转不变性。

由于rBRIEF用\(5\times5\)子窗口的灰度平均值来代替原先某个点的灰度值，其抗噪声性能有了一定的提升。将SIFT和rBRIEF比较，测试其在不同噪声强度下的匹配性能，得到结果如下

可以看出SIFT匹配性能随信噪比降低而急剧下降，但Rbrief算法相对影响不是很大。

ORB本身不具备尺度不变性，但OpenCV里通过图像金字塔使ORB算法仍能检测出发生了一定程度尺度变换的目标，并通过透视变换等方法校正目标。

3 实例

3.1 SURF

%% Read Images
Temp = rgb2gray(imread('temp.jpg'));
I = rgb2gray(imread(image.jpg'));
TPoints = detectSURFFeatures(Temp);
IPoints = detectSURFFeatures(I);
%% Detect Feature Points
figure;
imshow(Temp);
title('Feature Points from Template');
hold on;
plot(TPoints);
figure;
imshow(I);
title('1000 Strongest Feature Points from Image');
hold on;
plot(selectStrongest(IPoints, 1000));
%% Extract Feature Descriptors
[TFeatures, TPoints] = extractFeatures(Temp, TPoints);
[IFeatures, IPoints] = extractFeatures(I, IPoints);
%% Find Putative Point Matches
Pairs = matchFeatures(TFeatures, IFeatures);
matchedTPoints = TPoints(Pairs(:, 1), :);
matchedIPoints = IPoints(Pairs(:, 2), :);
figure;
showMatchedFeatures(Temp, I, matchedTPoints, ...
    matchedIPoints, 'montage');
title('Putatively Matched Points (Including Outliers)');
%% Locate the Object in the Scene Using Putative Matches
[tform, inlierTPoints, inlierIPoints] = ...
    estimateGeometricTransform(matchedTPoints, matchedIPoints, 'affine');
figure;
showMatchedFeatures(Temp, I, inlierTPoints, ...
    inlierIPoints, 'montage');
title('Matched Points (Inliers Only)');
%%
TPolygon = [1, 1;...                           % top-left
        size(Temp, 2), 1;...                 % top-right
        size(Temp, 2), size(Temp, 1);... % bottom-right
        1, size(Temp, 1);...                 % bottom-left
        1, 1];                   % top-left again to close the polygon
newTPolygon = transformPointsForward(tform, TPolygon);
figure;
imshow(I);
hold on;
line(newTPolygon(:, 1), newTPolygon(:, 2), 'Color', 'y');
title('Detected Point');

3.2 ORB

#include <iostream>
#include <opencv2/core/core.hpp>
#include <opencv2/features2d/features2d.hpp>
#include <opencv2/highgui/highgui.hpp>
using namespace std;
using namespace cv;
int main(int argc, char** argv)
{
    int pairN = 1;
    char buf[100];
    sprintf(buf, "F:\\OpenCV\\ORB\\img\\pair%04d_frm1.jpg", pairN);
    Mat I = imread(buf);
    sprintf(buf, "F:\\OpenCV\\ORB\\img\\pair%04d_frm2.jpg", pairN);
    Mat T = imread(buf);
    std::vector<KeyPoint> keypoints_I, keypoints_T;
    Mat descriptors_I, descriptors_T;
    Ptr<FeatureDetector> detector = ORB::create();
    Ptr<DescriptorExtractor> descriptor = ORB::create();
    Ptr<DescriptorMatcher> matcher = DescriptorMatcher::create("BruteForce-Hamming");
    detector->detect(I, keypoints_I);
    detector->detect(T, keypoints_T);
    descriptor->compute(I, keypoints_I, descriptors_I);
    descriptor->compute(T, keypoints_T, descriptors_T);
    Mat ShowKeypointsI, ShowKeypointsT;
    drawKeypoints(I, keypoints_I, ShowKeypointsI, Scalar::all(-1), DrawMatchesFlags::DEFAULT);
    drawKeypoints(T, keypoints_T, ShowKeypointsT, Scalar::all(-1), DrawMatchesFlags::DEFAULT);
    imshow("KeypointsI", ShowKeypointsI);
    imshow("KeypointsT", ShowKeypointsT);
    imwrite("F:\\OpenCV\\ORB\\img\\KeypointsI.jpg", ShowKeypointsI);
    imwrite("F:\\OpenCV\\ORB\\img\\KeypointsT.jpg", ShowKeypointsT);
    vector<DMatch> matches;
    matcher->match(descriptors_I, descriptors_T, matches);
    double min_dist = 10000, max_dist = 0;
    for (int i = 0; i < descriptors_I.rows; i++)
    {
        double dist = matches[i].distance;
        if (dist < min_dist) min_dist = dist;
        if (dist > max_dist) max_dist = dist;
    }
    cout << "max dist: " << max_dist << endl;
    cout << "min dist: " << min_dist << endl;
    std::vector<DMatch> good_matches;
    for (int i = 0; i < descriptors_I.rows; i++)
    {
        if (matches[i].distance <= max(1.5* min_dist, 30.0))
        {
            good_matches.push_back(matches[i]);
        }
    }
    Mat img_goodmatch;
    drawMatches(I, keypoints_I, T, keypoints_T, good_matches, img_goodmatch);
    imshow("goodmatch ", img_goodmatch);
    imwrite("F:\\OpenCV\\ORB\\img\\goodmatch.jpg", img_goodmatch);
    waitKey(0);
    return 0;
}