一种鲁棒的二进制图像特征点描述子

王 颖 王爱民

(东南大学仪器科学与工程学院，南京 210096)

一种鲁棒的二进制图像特征点描述子

王 颖 王爱民

(东南大学仪器科学与工程学院，南京 210096)

为了提高特征点匹配的速度，采用二进制方法生成特征点描述，并对描述子进行了尺度和旋转适应性改进.使用特征点邻域小块中随机点的强度对比生成描述，描述子的相似度以Hamming距离度量，以二进制运算提高算法的时间性能.为了检验算法在视角、旋转及尺度变化时的性能，采用Wall和Graffiti图像集及相应的旋转和尺度变换图像集对算法进行测试，得到该算法在各图像集上的匹配准确率，并与SURF算法得到的结果进行比较.结果表明，在2幅图像间进行特征点匹配时，该算法的特征点描述生成时间和匹配时间分别为1 043.67和4 313.36 ms，而使用SURF算法时的相应时间分别为3 950.34和9 951.03 ms，说明该算法的时间特性明显优于SURF算法.此外，在绝大多数测试集上，该算法的匹配准确率明显高于SURF算法.

特征点;特征匹配;SURF算法

随着算法精度的不断提高，特征点提取与匹配技术越来越多地应用于图像拼接、三维场景重建以及物体的检测、识别、跟踪等领域.部分应用场景(如机器人即时定位与地图构建、增强现实的配准和跟踪等)对实时处理的要求较高，因此需要在保证准确性的情况下，尽可能提高特征点提取与匹配算法的运行速度.目前，应用范围较广的此类算法包括尺度不变特征变换SIFT(scale-invariant fea-ture transform)算法［1-2］和使用近似 Hessian提取算子的 SURF(speeded up robust feature)算法［3］等.

SIFT算法使用差分高斯(difference of Gauss，DoG)近似拉普拉斯高斯(Laplace of Gauss，LoG)提取特征点，采用梯度直方图形式的特征点描述子.该算法匹配精度高、鲁棒性好，能处理2幅图像大视角变化时的匹配问题，其缺点在于特征点提取与匹配时间过长、难以实现实时处理.Mikolajczyk等［4］将SIFT算法中的特征点描述变换到极坐标下，从而提高了算法的性能.Ke等［5］对SIFT算法的特征点描述子进行主成分分析，提出了PCA-SIFT算法.Bay等［3］基于简化思想提出了SURF算法，以Haar小波近似Hessian算子，并使用积分图像(integral image)缩短了计算时间.SURF算法能较好地平衡算法速度和精度，应用较为广泛，但仍无法满足实时处理的要求.以上各种特征描述算法都需要生成高维的特征描述子，描述的生成和特征点的匹配较为费时，成为提高算法速度的瓶颈.

本文提出了一种能够快速生成描述、实现匹配的二进制特征点描述子，并对算子进行改进，使其适应尺度和旋转变换.

1 二进制特征点描述子

1.1 相关原理

用二进制数据描述图像特征点的思想来源于Lepetit等［6-7］的相关研究.其基本思想是将特征点的匹配看作分类问题，构建随机分类树，通过学习来实现特征点的识别.图1为随机分类树及其改进结构的示意图.随机分类树由根节点及其下的各个节点组成，每个节点包含1个分类测试ti，叶节点用于存储训练得到的后验概率.Ozuysal等［8］对随机分类树的结构进行了调整，在分类树的每一层中采用相同的测试，并去掉层级结构.在此基础上，Calonder等［9］进一步去除了分类器和训练过程，仅保留测试结果作为二进制特征点描述子.

图1 随机树结构的改进

1.2 定义

二进制特征点描述子是一种二进制向量，可通过比较特征点邻域小块中随机点的强度得到，每1个二进制位记录1个比较结果.

式中，I(u)为经过平滑的图像在点u=(x，y)T处的强度.选择n组不同位置的点对(u，v)，比较每一组点的像素强度I(u)和I(v)，将结果保存为n位二进制数据.由此可将二进制特征点描述子定义为如下的n维二进制数据串:

在式(2)中，测试点ui和vi的坐标服从二维高斯分布;n的选择取决于实际应用的要求，为了平衡精度和时间，通常取128，256或512.

在二进制特征点描述中，由于仅对像素强度进行比较，得到的结果受噪声影响较为严重.需要先对图像进行平滑处理，提高特征点描述的稳定性与可重复性.

二进制特征点描述子的匹配使用Hamming距离度量.具体做法如下:将2个二进制数据按位异或，根据结果中1数量的多寡判定特征点描述子是否匹配.

2 适应性改进

2.1 尺度不变性

Lindeberg［10］于1998年提出了尺度空间理论，并在多尺度中对图像进行处理，其方法类似于生物视觉中由粗到精(coarse to fine)的处理方式.尺度空间理论解决了尺度变化时图像特征点的提取问题.将若干幅经过不同程度高斯平滑的图像构成尺度空间，在尺度空间中筛选符合条件的特征点，并定义该特征点所在尺度为特征尺度.其具体过程如下:首先将图像I(x，y)与高斯函数卷积，即

式中，L(x，y，t)为得到的平滑图像;G(x，y，t)为二维高斯函数，其表达式为

式中，t和σ分别为高斯函数的标准差和方差.将图像与方差为σi的高斯函数卷积，并用结果图像建立尺度空间.

然后，在多尺度下进行图像特征点判别，其判别法则如下:

对坡脚进行垂直切坡处理后，斜马道宽度拓展为4.85 m，即上坝道路初期坝下游坝面段实际宽度达到4.85 m，增强了道路的安全通行条件。

式中，F为判别函数;Th和Tl分别为响应上、下限;MW为特征点M在尺度空间上邻域W中的一点.

在二进制特征点描述中引入尺度s，s与σ成正比.根据s调整测试点的分布，从而解决图像尺度变化下的特征点描述问题.

2.2 旋转不变性

向特征点赋予特征方向是实现旋转不变性的一种途径［3］.本文通过在局部区域计算Haar小波响应得到特征点的特征方向(见图2).该方法的具体计算过程如下:首先，在图像中建立一个以特征点为中心，半径为6s的圆形区域，在该区域内计算边长为4s的Haar小波响应，并赋予其参数为2s的高斯权值;然后，建立一个圆心角为π/3的扇形滑动窗，并统计x，y方向上Haar小波响应的矢量和;最后，选择矢量长度最大的方向为特征方向，其表达式为

式中，weight(x，y)表示权值;wh(x，y)表示方向为h时的窗函数;dx，dy分别表示x，y方向上的Haar小波响应.

图2 特征方向示意图

得到特征方向后，对生成测试点的坐标进行插值，即可使图像发生旋转时得到的特征点描述子固定不变.

3 测试数据及算法评价

为了对算法的性能做出准确评估，采用标准图像库进行测试.这里选取文献［4］中的2组视角变化的测试图像集Wall和Graffiti图像集(见图3).每组测试图像集中包含6幅图像，以第1幅为基准，其余每幅图像的视角在20°～60°之间变化.这2组测试图像集代表2种不同的场景类型.其中，Graffiti图像集为平面绘图，含有明显的线条界限;Wall图像集为粗糙砖砌墙面照片，包含了重复的纹理.已知每幅图像到基准图像的单应性矩阵，通过点的坐标换算即可验证特征点的匹配是否正确.

图3 测试图像集中的基准图像

为了分别研究算法在旋转和尺度变换下的工作特性，对基准图像(即Wall，Graffiti图像集中的第1幅图像)进行旋转和缩放，生成Wall和Graffiti的旋转、缩放测试图像集.

在算法评价方面，主要分析算法的匹配准确率，其表达式为

式中，N为返回的匹配点总数;R为正确匹配点数量.

4 实验与结果

4.1 实验设置

在Wall图像集和Graffiti图像集上分别对本文算法和SURF算法进行测试.特征点提取采用快速Hessian算子.特征点提取及SURF算法的特征描述部分使用了计算机视觉类库 OpenCV［11］(open source computer vision)中的相关函数.实验中，快速Hessian算子的参数设置如下:Hessian阈值为200，阶数为3，每阶为4层.在尺度图像集上进行测试时，由于图像较大，将Hessian阈值设定为1 000.SURF算法的特征描述子为64维.二进制描述子为256位，采用的特征点邻域小块为48×48像素.编程语言为C++.

特征点匹配采取最近邻策略:若2个特征点描述子的距离互为最短，则判定为匹配点.

4.2 实验结果与分析

为检验算法运行效率，考察了2种算法在2幅图像间进行特征点匹配的处理时间.实验中，基准图像为Wall图像集中的第1幅图像，其大小为1 000×700像素，提取的特征点数量为7 366.匹配对象为Wall图像集中的第2幅图像，特征点数量为5 993.采用双核处理器 PC，CPU主频为2.20 GHz.实验结果表明:本文算法和SURF算法的描述生成时间分别为1 043.67和3 950.34 ms，特征点匹配时间分别为4 313.36和9 951.03 ms.

图4为2种算法在Wall和Graffiti视角变换图像集上的匹配准确率.由图可知，在2组视角变换图像集上，采用改进二进制描述子时匹配准确率高于SURF算法.此外，利用同一算法时Wall图像集上的匹配准确率高于Graffiti图像集上的匹配准确率，说明这2种算法更适用于纹理丰富的图像集.

图4 不同视角时的测试结果

图5和图6分别为2种算法在Wall和Graffiti尺度变换和旋转变换图像集上的匹配准确率.由图5可知，尺度不变性测试在2个图像集上的结果几乎没有差别，表明单纯尺度变化下图像的类型对实验结果没有影响，本文算法的特征点匹配准确率仍然高于SURF算法.在旋转测试的结果中，2种算法得到的结果无明显差别(见图6).

综上所述，在大多数情况下本文算法的匹配准确率明显高于SURF算法.从算法的运行时间来看，本文算法的特征点描述子生成时间约为SURF算法的1/4，匹配时间约为SURF算法的1/2，说明本文算法具有明显的速度优势.

图5 不同尺度时的测试结果

图6 不同旋转角度时的测试结果

5 结语

本文提出了一种鲁棒的二进制图像特征点描述子.实验结果表明，在各类图像上使用该特征点描述子进行特征点匹配时的匹配准确率精度均高于SURF算法.与梯度直方图类的特征点描述子相比，二进制特征点描述子占用内存少，SURF算法的64维特征点描述子需要256 byte的存储空间，而256位的二进制描述子仅占用32 byte的存储空间.此外，二进制特征点描述子的生成与匹配速度较快.因此，本文算法适用于手机等存储空间较小、计算能力受限制的硬件平台以及增强现实等一些实时性要求较高的应用场合.与随机树等机器学习类的算法相比，本文算法不需要学习训练阶段，适于需要添加新特征点的SLAM等应用场景.下一步的工作重点在于结合快速特征点提取，进一步扩大算法的速度优势.

［1］ Lowe D G.Object recognition from local scale-invariant features［C］//Proceedings of the7th IEEE International Conference on Computer Vision.Los Alamitos，USA，1999:1150-1157.

［2］ Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91-110.

［3］ Bay Herbert，Tuytelaars Tinne，Van Gool Lue.SURF:speeded up robust features［C］//Proceedings of the9th European Conference on Computer Vision.Graz，Austria，2006:404-417.

［4］Mikolajczyk K，Schmid C.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10):1615-1630.

［5］ Ke Y，Sukthankar R.PCA-SIFT:a more distinctive representation for local image descriptors［C］//Proceedings of the2004IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington DC，USA，2004:506-513.

［6］ Lepetit V，Pilet J，Fua P.Point matching as a classification problem for fast and robust object pose estimation［C］//Proceedings of the2004IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington DC，USA，2004:244-250.

［7］ Lepetit V，Fua P.Keypoint recognition using randomized trees［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(9):1465-1479.

［8］Ozuysal M，Calonder M，Lepetit V，et al.Fast keypoint recognition using random ferns［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(3):448-461.

［9］ Calonder M，Lepetit V，Strecha C，et al.BRIEF:binary robust independent elementary features［C］//Proceedings of the11th European Conference on Computer Vision.Berlin，Germany，2010:778-792.

［10］ Lindeberg T.Feature detection with automatic scale selection［J］.International Journal of Computer Vision，1998，30(2):79-116.

［11］ Willow Garage.OpenCV［EB/OL］.(2010-04-10)［2010-06-03］.http://opencv.willowgarage.com.

Robust binary feature point descriptor

Wang Ying Wang Aimin
(School of Instrument Science and Engineering，Southeast University，Nanjing 210096，China)

In order to improve the speed of feature point matching，a binary method is used to generate feature point description，and the descriptor’s adaptability to different scales and rotations is improved.The descriptor is computed using intensity difference tests.The descriptor similarity is evaluated by using Hamming distance，and the time performance of the algorithm is improved by binary operation.The Wall and Graffiti image sets as well as their transformed image sets are used to test the performance of the proposed algorithm for the different perspectives，rotations and scales.The matching accuracies on each image set are obtained.The comparison results of the proposed algorithm and the speeded up robust feature(SURF)algorithm show that during the feature point matching between the two images，the construction time and the matching time of the descriptors of the proposed algorithm are 1 043.67 and 4 313.36 ms，respectively，while the corresponding data of the SURF algorithm are 3 950.34 and 9 951.03 ms，indicating that the time characteristics of the proposed algorithm are better than those of the SURF algorithm.In addition，on most image sets，the matching accuracy of the proposed algorithm is higher than that of the SURF algorithm.

feature point;feature matching;speeded up robust feature(SURF)algorithm

TP391.4

A

1001－0505(2012)02-0265-05

10.3969/j.issn.1001 －0505.2012.02.014

2011-08-20.

王颖(1985—)，女，博士生;王爱民(联系人)，男，博士，教授，博士生导师，wangam@seu.edu.cn.

国家高技术研究发展计划(863计划)资助项目(2009AA01Z311).

王颖，王爱民.一种鲁棒的二进制图像特征点描述子［J］.东南大学学报:自然科学版，2012，42(2):265-269.［doi:10.3969/j.issn.1001 －0505.2012.02.014］