一种新的图像关键点描述子

王　强，成　虹

(1．成都工业学院　a.机械工程学院；b.材料工程学院，成都　611730；2.西南交通大学　机械工程学院，成都　610031)

一种新的图像关键点描述子

王强1a,2*，成虹1b

(1．成都工业学院a.机械工程学院；b.材料工程学院，成都611730；2.西南交通大学机械工程学院，成都610031)

摘要：目前图像特征匹配的主流方法是检测图像中的关键点，通过对关键点的唯一表述来生成关键点描述算子。通过对图像进行分析，提出了一种新的图像关键点描述算子，对图像关键点邻域像素进行编码，得到二进制编码标签，同时根据幅值大小，生成8维的关键点方向描述算子，通过比较不同图像的关键点描述算子，实现图像的匹配。实验证明：该方法能获得很好的匹配效果。

关键词：图像处理；描述子；关键点；特征匹配

图像匹配是很多计算机视觉问题的基础，比如图像拼接、目标识别、3D重构、人脸识别等。在选择匹配的方法上，主要是通过寻找图像中有代表性的关键点，然后通过对关键点描述，得到关键点的唯一表述。匹配时通过对比不同图像中的关键点以及描述算子，确定图像中的唯一匹配点。关键点以及描述算子的生成方法已有很多：Moravec[1]提出了视频图像匹配的角点检测算法；Harris[2]根据图像的一阶导数提出了Harris角点检测算法；Lowe[3-4]提出的SIFT算法，通过生成不同尺度的高斯模糊图像，在不同的尺度上进行关键点检测，通过极值抑制、去除不稳定关键点以及插值拟合等方法得到亚像素精度上的关键点，然后再生成128维的关键点幅值和方向描述算子，得到关键点的唯一描述子；Calonder等[5-6]提出了BRIEF方法，该方法取特征点的n×n的邻域中的任意一堆点比较大小(可以取到256对)，根据比较的大小形成二进制串，在进行图像匹配时，比较2图中的这些二进制串中相同的数量，其特征配对采用汉明距离方法；Rosten等[7]提出了一种FAST关键点检测方法；Rublee等[8]结合BRIEF方法和FAST方法，提出了一种ORB算法，用于关键点的检测和描述。但角点检测方法适应性不强，SIFT算法能够满足图像的光照、尺度以及旋转不变性，但是其时间复杂度太大，不适合实时性的要求。BRIEF方法对噪声敏感，而且不具有旋转不变性和尺度不变性。ORB方法是在BRIEF和FAST方法的基础上进行的改进，通过加上描述子的方向，实现了旋转不变性，但是同样对噪声敏感。因此，有必要继续研究更好的图像关键点描述方法。本文根据图像纹理特征方法，结合图像局部二值模式，提出一种新的关键点描述方法。

1结合图像纹理特征的局部二值模式

通过对图像纹理的分析，Ojala[9]提出了一种局部二值模式编码方法(LBP)。LBP算法通过对图像局部邻域与中心像素的差分，得到中心像素的二进制表示，通过对每个像素点进行LBP编码，统计图像的直方图，实现图像识别。LBP编码已经成功应用在人脸识别上，并取得了不错的效果[10]。LBP原始编码方法如下：

设一个3×3的邻域内中心像素为gc，邻域内像素依次记为g0～g7，如图1所示。设图像在局部邻域的联合分布为：

T=t(gc,g0,g1,…，g7)

(1)

在不失掉信息的前提下，让邻域像素值依次减去中心像素值，则式(1)可以表示为：

T=t(gc,g0-gc,g1-gc,…，g7-gc)

(2)

由于中心像素与邻域像素和中心像素的差分分布独立，该联合分布可以近视表示为：

T≈t(gc)t(g0-gc,g1-gc,…，g7-gc)

(3)

其中t(gc)是图像中某个局部邻域的中心像素值分布，从分析局部邻域纹理模式来看，它是无用的信息。而t(g0-gc,g1-gc,…，g7-gc)则代表了局部纹理模型。设置阈值函数

(4)

其中：z=g1-gc(i=0,1,…，7)。

所以，只需要考虑差分

t(s(g0-gc),s(g1-gc),…，s(g7-gc))。

(5)

图1　LBP编码示例

LBP算子来自于邻域像素的联合分布，基本的LBP算子是在3×3的邻域内通过式(5)得到邻域像素和中心像素的幅值差分信号，然后根据式(4)组合成一个8位的二进制串，将这个二进制串按照权重转换成十进制的数值，代替原来中心像素的值。因此，LBP算法可以表示为：

(6)

其中：P为邻域像素的数量；R为邻域半径，如3×3邻域，则R=1。原始的LBP编码算法有很多缺陷，比如没有旋转不变性、对邻域大小的限制、不能够很好地表现图像的纹理特征等。所以又出现了很多改进算法。比如将3×3的邻域改为圆形邻域，通过插值得到邻域像素的值，还有通过将编码后的值按照二进制位进行移位操作，取移位操作后的最小值作为中心像素的替代之。此外，还有均匀LBP编码方式等[11]。图2是几种不同的LBP编码后的结果。图2(a)是一张铁路扣件的图像，图2(b)、(c)和(d)是分别采用3种不同的LBP编码方式得到的结果。

2本文提出的关键点描述方法

本文不做关键点的检测，主要是提出一种关键点的描述算子。关键点的检测可以采用SIFT算法、FAST算法、Harris角点检测算法等。针对检测出的关键点，采用LBP编码的方式，提取关键点的LBP值。同时，考虑到对关键点描述的唯一性，将邻域像素与关键点像素的差分幅值进行比较，设置中心像素与邻域像素差分幅值最大的方向为0°方向，然后依次计算邻域像素与关键点的连线到0°方向的角度，得到一个关于关键点与邻域像素之间的维与角度相关的向量。结合关键点的LBP编码值共同实现对关键点的描述。邻域像素点与关键点的幅值差分可能相同，这时采用与主方向夹角最小的排在前，大的排在后，如果主方向有多个相同的值，则采用最接近主方向幅值与各个最大幅值夹角逆时针方向最小的作为主方向，依次类推，如图3所示。

图3　生成关键点的方向向量

设关键点为gk，其邻域像素为gi(i=0,1,…,P)，共P个邻域点。定义为gmax=max(gi)邻域像素点与关键点差分幅值最大的点。确定主方向之后，按照逆时针方向，计算与关键点差分幅值依次减小的每个邻域点与关键点的连线到主方向的夹角，由此得到关键点邻域角度向量V。根据邻域点的数量，最大幅值方向定义为0，所以该向量为一个P维向量。根据LBP的编码规则，其邻域像素数量一般可取8个或16个，本文取8个邻域点，由此得到的是一个8维的向量，其中每一维的值可以通过式(7)计算：

(7)

其中：i=0,1,…,7；αi为每个夹角大小。通过计算得到αi的值，生成向量V=(α0,α1,…,α7)。由此得到关键点的角度向量描述。

从图像的LBP编码值可以看出，一张图像的LBP编码有重复的值，比如一张128×128大小的图像，对于普通灰度图像而言，其颜色灰阶是256色，进行LBP编码后不可避免有重复的LBP值。但是，考虑到一张图像能检测出来的关键点的数量是有限的，因此，对于关键点的LBP编码后的重复率是有限的；同时，加上与邻域像素之间的角度向量，除了主方向为0°外，其他7个方向的分布可以有7！=5 040种变化，可以实现对关键点的唯一描述，从而用于基于关键点的图像匹配。

本文的算法描述如下：

1)采用SIFT算法检测图像中的关键点；

2)遍历图像中的关键点，对每个关键点进行LBP编码并保存；

3)针对每个关键点，找到LBP编码邻域中与关键点之间差分按照大小排序；

4)根据式(7)分别计算每个邻域像素点与关键点的连线与主方向的角度，以逆时针为正，得到关键点与邻域像素点之间的角度向量并保存，由此得到关键点的描述向量。

在进行图像匹配时，首先检测2幅图像中的关键点，然后依次循环关键点，对点进行LBP编码得到每个关键点的LBP值并进行比较。如果LBP值相同并且唯一，则找到匹配的点；如果LBP值不唯一，则根据生成的角度向量进行搜索，找到角度向量相似的即为匹配点。判断角度向量相似的方法采用欧式距离进行判断，当2个向量的欧式距离在一定的阈值内，则认为2个向量相似，可以进行匹配；反之，则没有找到匹配点。根据实验结果，阈值设置在0.4～0.8之间，可以得到比较好的匹配效果，具体阈值大小可以根据匹配的准确性要求进行调整。

3实验验证

图4是来自牛津大学图像库中的2幅图像，图像大小为850×860，从2个不同的角度、尺度进行拍摄。对2幅图采用SIFT算法分别检测出1 458个关键点(如图4(a)所示)和1 340个关键点(如图4(b)所示)。图4(c)和图4(d)是分别采用通过SIFT算法匹配和本文的算法进行匹配的结果。与SIFT算法进行比较，可以发现：采用本文算法得到的匹配结果与SIFT算法相当，但运行效率要比SIFT算法高很多。在Windows7系统上处理器配置为i5-2520M，SIFT算法配对50对特征点的时间为3 920 ms，而本文算法只需要366 ms。这是因为SIFT的描述子是128维的向量，而且这128维向量首先需要在16×16的邻域内对图像进行分块，每一小块为4×4的图像块，然后计算其梯度方向直方图，每个块都分为8个方向，由此得到4×4×8=128维向量，其时间复杂度非常高。而LBP编码只需比较中心像素与邻域像素的大小，然后将比较大小得到的二值串转换成十进制代替原来的像素值，其速度非常快。同时，在计算角度向量的时候，由于只需要8个方向的值，大大降低了向量的维度，故其运行效率非常高，可以用于实时图像匹配。图4(a)和图4(b)表示检测出来的关键点，图4(c)中的连线表示采用SIFT算法匹配时2点之间的连线，图4(d)中的连线表示采用本文算法匹配时2点之间的连线。

(a)第1幅图的关键点检测结果

(b)第2幅图的关键点检测结果

(c) SIFT匹配结果

(d) 本文算法匹配结果

由于LBP算法计算的是图像的差分，有效地克服了光照的影响。在旋转不变性方面，由于采用的是关键点主方向，其他方向与主方向的相对角度，所以实现了旋转不变性。在尺度不变性方面，主要是通过关键点的检测算法实现，由于SIFT算法本身是多尺度进行关键点检测的，所以本文的描述算子同样继承了SIFT的尺度不变性。当然，由于SIFT算法本身在关键点检测方面的效率也比较低下，所以，采用本文的关键点描述子时，其前期的关键点检测算法也可以采用其他的算法，比如FAST算法，BRISK算法[12]等。由于SIFT算法在检测关键点方面的稳定性有很大的优势，而其他的检测算法主要是实时性方面有优势，在实际使用过程中，可以根据自己的需要选择相应的关键点检测方法。

4结语

图像的关键点是表征图像信息的关键，对于描述图像内容起到重要的作用。对于关键点的检测和描述历来是图像处理研究的重点。计算机视觉相关的很多问题都需要通过关键点的检测和描述来实现，比如图像匹配、图像拼接、3D重构等等。对于关键点的准确检测和唯一性描述是实现上述问题的关键。本文提出的关键点描述算法在很大程度上能够解决关键点的描述唯一性，实验证明：这种方法是切实可行的。

参考文献：

[1] MORAVEC H P. Rover visual obstacle avoidance[C]// International Joint Conference on Artificial Intelligence,1981:785-790.

[2] YARON O, SIDI M. A combined corner and edge detector[C]// Alvey Vision Conference. 1988:147-151.

[3] LOWE D G.Object recognition from local scale-invariant features[C]// Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on. IEEE, 1999:1150-1157.

[4] LOWE D G.Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(60):91-110.

[5] CALONDER M, LEPETIT V, STRECHA C, et al. BRIEF: binary robust Independent elementary features[C]// European Conference on Computer Vision. Springer-Verlag, 2010:778-792.

[6] CALONDER M, LEPETIT V, OZUYSAL M, et al. BRIEF: computing a local binary descriptor very fast[J]. Pattern Analysis & Machine Intelligence IEEE Transactions on, 2012, 34(7):1281-1298.

[7] ROSTEN E, PORTER R, DRUMMOND T. Faster and better: a machine learning approach to corner detection[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2008, 32(32):105-119.

[8] RUBLEE E, RABAUD V, KONOLIGE K, et al. ORB: an efficient alternative to SIFT or SURF[J]. Proceedings, 2011, 58(11):2564-2571.

[9] OJALA T, HARWOOD I. A Comparative study of texture measures with classification based on feature distributions[J]. Pattern Recognition, 1996, 29(1):51-59.

[11] OJALA T, PIETIKINEN M, MENPT. Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2002, 24(7):971-987.

[12] LEUTENEGGER S, CHLI M, SIEGWART R Y. BRISK: binary robust invariant scalable keypoints[C]// International Conference on Computer Vision. IEEE Computer Society, 2011:2548-2555.

A New Descriptor for Image Keypoints

WANGQiang1a,2*，CHENGHong1b

(1.a.School of Mechanical Engineering；b.School of Materials Engineering,Chengdu Technological University,Chengdu 611730,China;2. School of Mechanical Engineering,Southwest Jiaotong University,Chengdu 610031,China)

Abstract:Image feature matching plays a basic role in many compute vision issues , such as the objects rebuilding, objects recognition, moving objects tracking and so on. Currently, detecting the keypoints of an image is the main method of image feature matching, which uses the unique description of keypoints to generate the corresponding description operators. A new descriptor for image keypoints is proposed through analyzing the image. The neighboring pixels are coded to create the binary coding label. Meanwhile, a eight dimensional description operator for keypoints directions is generated according to the amplitude magnitude. Image matching is realized through comparing the keypoints description operators of each image. Experiment results show that the proposed method reaches the great matching performance.

Key words:image process；descriptor；keypoint；feature matching

DOI:10.13542/j.cnki.51-1747/tn.2016.02.006

收稿日期：2016-04-05

基金项目：四川省教育厅项目“智能救援机器人视觉及传感系统设计”(16ZB0330)；四川省创新创业项目“计算机视觉在工业检测中的应用”(201511116019)

作者简介：王强(1979— )，男(汉族)，四川广安人，讲师，在读博士研究生，研究方向：计算机视觉、模式识别，通信作者邮箱: wangqiang_sky@163.com。

中图分类号：TP391.4

文献标志码：A

文章编号：2095-5383(2016)02-0020-04

成虹(1955— )，男(汉族)，山西晋城人，教授，研究方向：金属材料成型。