【特征匹配】BRIEF特征描述⼦原理及源码解析
相关：
传统的特征点描述⼦如SIFT,SURF描述⼦，每个特征点采⽤128维(SIFT)或者64维(SURF)向量去描述，每个维度上占⽤4字节，SIFT需要128×4=512字节内存，SURF则需要256字节。如果对于内存资源有限的情况下，这种描述⼦⽅法显然不适应。同时，在形成描述⼦的过程中，也⽐较耗时。后来有⼈提出采⽤PCA降维的⽅法，但没有解决计算描述⼦耗时的问题。
鉴于上述的缺点Michael Calonder等⼈在论⽂提出BRIEF描述特征点的⽅法(BRIEF:Binary Robust Independent Elementary Features)。BRIEF描述⼦采⽤⼆进制码串(每⼀位⾮1即0)作为描述⼦向量，论⽂中考虑长度有128,256,512⼏种，同时形成描述⼦算法的过程简单，由于采⽤⼆进制码串，匹配上采⽤汉明距离，（⼀个串变成另⼀个串所需要的最⼩替换次数）。但由于BRIEF描述⼦不具有⽅向性，⼤⾓度旋转会对匹配上有很⼤的影响。
BRIRF只提出了描述特征点的⽅法，所以特征点的检测部分必须结合其他的⽅法，如SIFT,SURF等，但论⽂中建议与Fast结合，因为会更能体现出Brirf速度快等优点。
--------------------------------------------------------------------------------------------------
BRIEF描述⼦原理简要为三个步骤，长度为N的⼆进制码串作为描述⼦(占⽤内存N/8)：
1.以特征点P为中⼼，取⼀个S×S⼤⼩的Patch邻域；
2.在这个邻域内随机取N对点，然后对这2×N点分别做⾼斯平滑。定义τ测试，⽐较N对像素点的灰度值的⼤⼩；
3.最后把步骤2得到的N个⼆进制码串组成⼀个N维向量即可；
-----------------------------------------------------------------------------------------------------
原理解析：
__1.关于做τ测试前，需要对随机点做⾼斯平滑，由于采⽤单个的像素灰度值做⽐较，会对噪声很敏感；采⽤⾼斯平滑图像，会降低噪声的影响，使得描述⼦更加稳定。论⽂中建议采⽤9×9的kernal。
__2.论⽂中对随机取N对点采⽤了5中不同的⽅法做测试，论⽂中建议采⽤G II的⽅法：
G I :（X,Y）~（-S/2,S/2）分布，X,Y即均匀分布；
G II: ，X,Y均服从⾼斯分布；
G III: ，先随机取X点，再以X点为中⼼，取Y点；
G IV: 在空间量化极坐标系下，随机取2N个点；
G V: X固定在中⼼，在Patch内，Y在极坐标系中尽可能取所有可能的值；
__3.最后汉明距离的计算，直接⽐较两⼆进制码串的距离，距离定义为：其中⼀个串变成另⼀个串所需要的最少操作。因⽽⽐欧⽒距离运算速度快.
如果取N=128，即每个特征点需要128/8=16个字节内存⼤⼩作为其描述⼦。
OPENCV源码解析：
#include <stdio.h>
#include <iostream>
#include "cv.h"
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/core/core.hpp"
#include "opencv2/features2d/features2d.hpp"
#include "opencv2/nonfree/nonfree.hpp"
using namespace std;
using namespace cv;
int main( int argc, char** argv )
{
Mat img_1 = imread( "F:\\Picture\\book.jpg", CV_LOAD_IMAGE_GRAYSCALE );
Mat img_2 = imread( "F:\\Picture\\book_2.jpg", CV_LOAD_IMAGE_GRAYSCALE );
if( !img_1.data || !img_2.data )
{
return -1; }
//-- Step 1: Detect the keypoints using SURF Detector
int minHessian = 400;
SurfFeatureDetector detector( minHessian); //采⽤Surf特征点检测
std::vector<KeyPoint> keypoints_1, keypoints_2;
detector.detect( img_1, keypoints_1 );
detector.detect( img_2, keypoints_2 );
//-- Step 2: Calculate descriptors (feature vectors)
BriefDescriptorExtractor extractor(64); //参数表⽰字节数，采⽤长度为64×8=512的向量表⽰，见下⽅分析 Mat descriptors_1, descriptors_2;
//-- Step 3: Matching descriptor vectors with a brute force matcher
BFMatcher matcher(NORM_HAMMING); //汉明距离匹配特征点
std::vector< DMatch > matches;
matcher.match( descriptors_1, descriptors_2, matches );
//-- Draw matches
Mat img_matches;
drawMatches( img_1, keypoints_1, img_2, keypoints_2, matches, img_matches );
-- Show detected matches
imshow("Matches", img_matches );
waitKey(0);
return 0;
}
Brief描述⼦的类定义：
注意bytes参数表⽰的是描述⼦占⽤的字节数不是描述⼦长度，如默认采⽤32字节对应描述⼦长度为32×8=256；
/*
* BRIEF Descriptor
*/
class CV_EXPORTS BriefDescriptorExtractor : public DescriptorExtractor
{
public:
static const int PATCH_SIZE = 48; //邻域范围
static const int KERNEL_SIZE = 9;//平滑积分核⼤⼩
// bytes is a length of descriptor in bytes. It can be equal 16, 32 or 64 bytes.
BriefDescriptorExtractor( int bytes = 32 ); //占⽤字节数32，对应描述⼦长度为32×8=256;
virtual void read( const FileNode& );
virtual void write( FileStorage& ) const;
virtual int descriptorSize() const;
virtual int descriptorType() const;
/
// @todo read and write for brief
AlgorithmInfo* info() const;
protected:
virtual void computeImpl(const Mat& image, vector<KeyPoint>& keypoints, Mat& descriptors) const; //计算特征描述⼦函数 typedef void(*PixelTestFn)(const Mat&, const vector<KeyPoint>&, Mat&); //不同长度的描述⼦调⽤不同的函数
int bytes_;//占⽤字节数
PixelTestFn test_fn_;
};
计算特征描述⼦函数：
void BriefDescriptorExtractor::computeImpl(const Mat& image, std::vector<KeyPoint>& keypoints, Mat& descriptors) const {
/
/ Construct integral image for fast smoothing (box filter)
Mat sum;
Mat grayImage = image;
if( pe() != CV_8U ) cvtColor( image, grayImage, CV_BGR2GRAY );
///TODO allow the ur to pass in a precomputed integral image
//pe() == CV_32S)
// sum = image;
//el
integral( grayImage, sum, CV_32S); //计算积分图像
//Remove keypoints very clo to the border
KeyPointsFilter::runByImageBorder(keypoints, image.size(), PATCH_SIZE/2 + KERNEL_SIZE/2);//剔除落在边界外的⾓点
descriptors = Mat::zeros((int)keypoints.size(), bytes_, CV_8U);
test_fn_(sum, keypoints, descriptors); //计算特征点描述⼦
}
关于对随机点平滑，不采⽤论⽂中⾼斯平滑，⽽是采⽤随机点邻域内积分和代替，同样可以降低噪声的影响：
inline int smoothedSum(const Mat& sum, const KeyPoint& pt, int y, int x)
{
static const int HALF_KERNEL = BriefDescriptorExtractor::KERNEL_SIZE / 2;
int img_y = (int)(pt.pt.y + 0.5) + y;
int img_x = (int)(pt.pt.x + 0.5) + x;
return sum.at<int>(img_y + HALF_KERNEL + 1, img_x + HALF_KERNEL + 1)
- sum.at<int>(img_y + HALF_KERNEL + 1, img_x - HALF_KERNEL)
- sum.at<int>(img_y - HALF_KERNEL, img_x + HALF_KERNEL + 1)
+ sum.at<int>(img_y - HALF_KERNEL, img_x - HALF_KERNEL);
}
描述⼦向量的形成（以长度为16字节×8=128为例）：
数组des每⼀个元素占⽤⼀个字节，源码位置：...\modules\features2d\src\generated_16.i
// Code generated with '$ scripts/generate_code.py src/ 16'
#define SMOOTHED(y,x) smoothedSum(sum, pt, y, x)
desc[0] = (uchar)(((SMOOTHED(-2, -1) < SMOOTHED(7, -1)) << 7) + ((SMOOTHED(-14, -1) < SMOOTHED(-3, 3)) << 6) + ((SMOOTHED(1, -2) < SMOOTHED desc[1] = (uchar)(((SMOOTHED(-6, -23) < SMOOTHED(8, -9)) << 7) + ((SMOOTHED(-12, 6) < SMOOTHED(-10, 8)) << 6) + ((SMOOTHED(-3, -1) < SMOOTH desc[2] = (uchar)(((SMOOTHED(-14, 9) < SMOOTHED(2, 0)) << 7) + ((SMOOTHED(7, -3) < SMOOTHED(22, 6)) << 6) + ((SMOOTHED(-6, 6) < SMOOTHED(- desc[3] = (uchar)(((SMOOTHED(0, 12) < SMOOTHED(-3, 19)) << 7) + ((SMOOT
HED(1, 15) < SMOOTHED(-11, -5)) << 6) + ((SMOOTHED(14, -1) < SMOOTH desc[4] = (uchar)(((SMOOTHED(-13, 13) < SMOOTHED(3, -1)) << 7) + ((SMOOTHED(-16, 17) < SMOOTHED(6, 10)) << 6) + ((SMOOTHED(7, 15) < SMOOTH desc[5] = (uchar)(((SMOOTHED(6, 12) < SMOOTHED(21, 3)) << 7) + ((SMOOTHED(-3, 2) < SMOOTHED(14, 1)) << 6) + ((SMOOTHED(5, 1) < SMOOTHED(- desc[6] = (uchar)(((SMOOTHED(22, 0) < SMOOTHED(7, -18)) << 7) + ((SMOOTHED(-1, -3) < SMOOTHED(0, 18)) << 6) + ((SMOOTHED(-4, 22) < SMOOTHE desc[7] = (uchar)(((SMOOTHED(4, 12) < SMOOTHED(0, -19)) << 7) + ((SMOOTHED(20, 13) < SMOOTHED(3, 5)) << 6) + ((SMOOTHED(-8, -12) < SMOOTHE desc[8] = (uchar)(((SMOOTHED(3, 6) < SMOOTHED(22, -2)) << 7) + ((SMOOTHED(-13, 14) < SMOOTHED(4, -4)) << 6) + ((SMOOTHED(-13, 8) < SMOOTHE desc[9] = (uchar)(((SMOOTHED(4, -7) < SMOOTHED(0, 16)) << 7) + ((SMOOTHED(-6, -5) < SMOOTHED(-12, -1)) << 6) + ((SMOOTHED(1, -1) < SMOOTHED desc[10] = (uchar)(((SMOOTHED(-20, 17) < SMOOTHED(-18, 7)) << 7) + ((SMOOTHED(2, 15) < SMOOTHED(19, -11)) << 6) + ((SMOOTHED(-18, 6) < SMOO desc[11] = (uchar)(((SMOOTHED(-2, 4) < SMOOTHED(-1, 6)) << 7) + ((SMOOTHED(-2, 7) < SMOOTHED(6, 8)) << 6) + ((SMOOTHED(-8, -1) < SMOOTHED( desc[12] = (uchar)(((SMOOTHED(5, -7) < SMOOTHED(7, 7)) << 7) + ((SMOOTHED(-5, 13) < SMOOTHED(-8, 11)) << 6) + ((SMOOTHED(11, -4) < SMOOTHE desc[13] = (uchar)(((SMOOTHED(11, 0) < SMOOTHED(-3, 2)) << 7) + ((SMOOT
HED(7, -12) < SMOOTHED(14, 5)) << 6) + ((SMOOTHED(0, -7) < SMOOTHED desc[14] = (uchar)(((SMOOTHED(-11, 6) < SMOOTHED(-10, 13)) << 7) + ((SMOOTHED(1, -7) < SMOOTHED(14, 0)) << 6) + ((SMOOTHED(-12, 1) < SMOOT desc[15] = (uchar)(((SMOOTHED(1, -1) < SMOOTHED(13, -10)) << 7) + ((SMOOTHED(-19, 14) < SMOOTHED(8, -14)) << 6) + ((SMOOTHED(-4, -13) < SMOO #undef SMOOTHED
参考⽂章：
Michael Calonder et.BRIEF:Binary Robust Independent Elementary Features
