BRIEF算法

BRIEF算法,第1张

BRIEF算法 本文结构

为了看懂ORB特征提取算法,来看了BRIEF算法的原文,并查看了OpenCV中BRIEF的相关实现,来验证论文的解读正确与否。


BRIEF论文解读 摘要

用二进制串描述局部特征,好处有二:一是很少的bit就能描述独特的性质;二是可以用汉明距离计算两个二进制串之间的特征,计算速度快。


在实际应用中的好处是:算的准;算的快;省内存


BRIEF特征的建立和用于匹配,都很快。


性能测试表明,BRIEF比SURF和U-SURF快,准确度差不多。


Introduction

经验表明,用256甚至128个bit表示一个BRIEF特征就够用了。


算的快,省内存,适合实时计算的应用,比如SLAM(省计算)或者三维重建(省存储)。




先前一些算法,先计算浮点型特征描述向量,再转化为二进制表示。


这样的算法,匹配很快,但是前期还是慢。




BRIEF是在keypoint周边随机取点对进行灰度计算,直接得到二进制特征描述向量。


Method

图像patch先做平滑 *** 作,再根据检验结果(response of test,比如t检验,即t-test)生成二进制描述符。




创建这样的特征向量,需要考虑的是高斯模糊的模糊核kernel(即\(\sigma\))值的选取,以及点对\((\vecx_1, \vecx_2)\)的选取,其中\(\vec x_1=(u,v)^T\)_

模糊的作用是消噪。


识别率的实验表明,sigma取2的效果最好,对应的高斯窗口为9x9规格。




论文提出了5种选择[x,y]的方式,并根据识别率进行实验,发现第二种性能最好:(X, Y) ∼ i.i.d. Gaussian(0, (1/25)S^2)

注意:这里的高斯分布容易引起混淆,详细讲是:每次t-检验中,要选取的两个点为(X,Y),其中X=(u1,v1)T,Y=(u2,v2)T,(X,Y)~N(0, (1/25)S^2)

实际测试发现sigma2=(1/25)S2能有最高的识别率。


我还是不明白,空域中到底要怎么选点?

看了OpenCV中的实现发现,所谓随机选点,只是最开始的一个patch是随机选点,并且这个选出来的点的顺序要记录下来给后面所有的patch使用。


并且,这些选出的点并不是真正的、纯粹的随机,而是服从上述高斯分布的。


为什么patch在t-检验前要做平滑?

因为论文原文提出的t-检验,每次检查的是两个像素点。


单个像素点是噪声敏感的。


因此要做平滑 *** 作。


(而平滑 *** 作比较耗时,这也为后来的优化做了伏笔。


Calonder等人又于2011年提出采用盒状滤波器的处理方法来代替高斯平滑处理方法)

实验和结果

在6种图片上,分别使用SURF、U-SURF、BRIEF-16、BRIEF-32、BRIEF-64进行测试,发现BRIEF-32除了在涂鸦(Graffitti)上表现不如SURF和U-SURF好之外,其他图片序列上基本都是最好的。


而且显然BRIEF-32也和BRIEF-64差不了太多,并且也基本胜过SURF和U-SURF。


上述比较过程中,keypoint是用的SURF的keypoint。


实际上SURF的keypoint会吃掉BRIEF带来的速度提升,一般用其他更快的keypoint检测子,比如CenSurE(Center Surround Extremas Realtime Feature Detector and Matching这篇论文提出。


也可以考虑FAST等算法,FAST:Rosten, E., Drummond, T.: Machine Learning for High-Speed Corner Detection. In: European Conference on Computer Vision)。


但是,换用了更快的检测子,能保证识别率吗?

同样的测试图片,对比分别用SURF和CenSurE检测的keypoint然后接上BREIF描述符,测量匹配的准确度,CenSurE在大多数情况下比SURF准确率还高;个别情况稍低于SURF。


旋转角的讨论

BRIEF没有专门考虑旋转的问题。


那么就从0°~360°进行旋转测试吧。




发现小范围(0-15°)内,BRIEF识别率最高,其次是U-SURF,然后是SURF和o-BRIEF;

角度再大一点(15°~30°),BRIEF和U-SURF准确率迅速下降到0,角度再大,则这两个算法的识别率保持为0.而SURF和o-BRIEF这两个考虑旋转方向的算法,始终能保持大于60%的准确率,而且在90°的倍数角度处,识别率有极大值。


这里的o-BRIEF是:用SURF算出旋转角度,然后用BRIEF按照这个角度旋转再进行描述的一个算法。




这里的BRIEF都是BRIEF-32。




o-BRIEF和SURF的识别率,在旋转角度从0到180度变化时,几乎是重合的。


实验中还测量了SURF和BRIEF在description和matching两个阶段的对比,发现特征描述的计算时间上相差35-40倍,精确邻近匹配的计算时间上相差3~10倍。




通常U-SURF比SURF快上3倍左右。


当前BRIEF的大多数时间消耗在高斯模糊 *** 作上。


基于积分图像的近似平滑 *** 作,能加速。


结论

BRIEF算的快(二进制描述,汉明距离匹配),算的准(这很重要),省内存(远少于SIFT和SURF的描述符位数)。




下一步考虑方向和尺度。


使用快速的方向估测子(fast orientation estimators),没理由不相信速度不快!

OpenCV中的实现

对一个keypoint(及其所在区域,称为patch),在生成其描述符之前,BRIEF要先对patch做高斯平滑,这会消耗时间。




OpenCV在具体的实现上,结合了平滑和积分图像的思想,将t-检验中原本的两个点p1、p2,替换成p1、p2各自一个模板区域内的像素之和,这个模板区域以p1或p2为左上角定点。


也就是,从原来的单独两个点的像素值比较,换成了两个模板区域内的像素和的比较,参与比较的点多了,降低了噪声的影响。


但是计算效率呢?没关系,因为使用了积分图像,因此计算时间是O(4)=O(1)的:

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);
}

这里的积分图像的使用,其实也就是盒状滤波器:指定区域内的像素和,或者像素和的归一化结果;也就是一个元素全为1,再乘以一个系数的矩阵。




当然,盒状滤波器在实现的过程中可以有更快的实现方式,即分别指定一维的行内滤波器和列内滤波器,每个滤波器都是计算整个行或列的元素和:先逐列扫描,每列计算元素和,并存储到临时数组中;再对临时数组使用行滤波器进行求和,这样就得到一个区域的盒状滤波结果了。


参考:

Opencv2.4.9源码分析——BRIEF

极限优化:Haar特征的另一种的快速计算方法—boxfilter

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/587879.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-12
下一篇 2022-04-12

发表评论

登录后才能评论

评论列表(0条)

保存