基于Harris-Hist的特征匹配及目标定位算法

张 震,张照崎,苗志滨,朱留存,李修明,麦 冬,张坤伦,周瑞凯

(1. 北部湾大学 先端科学技术研究院,广西 钦州 535001； 2. 大连理工大学-立命馆大学国际信息与软件学院,辽宁 大连 116085； 3. 广西机械工业研究院有限责任公司,南宁 530007)

0 引 言

图像特征提取及特征匹配是计算机视觉、图像处理和计算机图形学的研究热点[1],广泛应用于目标定位、目标跟踪[2]、图像配准[3]、图像拼接、图像融合[4-5]和同步定位与地图绘制(SLAM)[6]等领域. 这类方法首先对图像中显著特征进行提取,然后利用提取特征的描述子完成两幅图像间特征的匹配,再通过特征匹配关系建立图像间的几何变换模型[6-7].

特征点检测算法多基于灰度的一阶或二阶导数寻找极值点. Moravec算法[8]是最早的基于梯度算法,其将每个像素点与其邻域像素点进行相关性计算,具有较低相关性的点认定为特征点,该算法对噪声较敏感. Harris等[9]对Moravec算法进行改进,提出了经典的Harris特征点检测算法,但其对图像旋转、光线变化、噪声和视点变换不敏感. Rosten等[10]提出了一种FAST(features from accelerated segment test)特征点检测算法,若一个像素点圆形邻域内有足够多点的灰度值与其差别较大,则认为该点为特征点. FAST算法速度快,但易受噪声影响. 上述特征点检测算法都是基于单一尺度的,之后出现了一些能适应尺度变化的特征检测算法,如尺度不变特征转换(SIFT)算法[11]和SURF(speed-up robust features)算法[12]等. SURF是SIFT的改进算法,其利用Haar小波近似SIFT方法中的梯度操作,同时利用积分图技术进行快速计算,使计算速度得到显著提高. 这类算法需要用Laplace算子或Gauss差分算子构建尺度空间,增加了计算复杂度和匹配识别的难度,实时性较差.

文献[8-10]主要考虑了特征点检测,未给出描述子定义算法和匹配算法. SIFT算法在特征点周围取16×16的邻域,并将邻域化分为4×4个小区域,每个小区域统计8个方向梯度,得到128维的向量作为该点的描述子. SURF算法在特征点周围取一个带方向的正方形邻域,再将邻域划分为16个子区域,每个子区域统计4个Haar小波特征,得到64维的向量作为该点的描述子. 上述两种特征描述子信息丰富,但运算代价较高,内存较大. Calonder等[13]提出了BRIEF描述子,该算法思想是在特征点邻域内随机挑选若干像素点对,对比各像素点对灰度值大小生成二进制序列作为描述子,极大节省了内存空间. Rublee等[14]对BRIEF描述子进行改造,提出了ORB(oriented FAST and rotated BRIEF)算法,根据角度参数提取BRIEF描述子,使其具有旋转不变性. 目前，已有许多改进融合算法[15-21],如文献[15-16]将Harris与SIFT算法相结合对原算法进行了改进,文献[17]提出基于Harris-SURF特征匹配算法对原算法进行了改进,均取得了较好的实验结果.

本文应用背景源于机器人视觉伺服定位、抓取,对定位精度和实时性要求较高. 经典的SIFT和SURF算法适应范围广、鲁棒性好,但运行速度慢. ORB算法运行速度快,但定位精度不高. 本文在特征检测及匹配定位过程中,同时满足定位精度和实时性要求. 本文选择Harris算法[9]提取特征点. 在特征匹配环节,计算特征点圆形邻域内像素点灰度直方图(Hist)作为特征描述子,通过计算两幅图像中各特征点描述子间的距离实现特征匹配. 最后,根据匹配结果,定位目标在场景图像中的位置,模型总体流程如图1所示.

图1 模型流程Fig.1 Flow chart of model

1 Harris图像特征点提取算法

1.1 算法原理

Harris算法思想：以待检测点为中心加窗,获取窗口内像素强度. 移动窗口后,获取新窗口内像素强度,并计算移动窗口移动前后的强度差值. 若沿任意方向移动窗口,强度差值均较大,则认为待检测点为特征点；若沿任意方向移动窗口,强度差值均较小,则认为待检测点位于图像平坦区域；若沿某特定方向移动窗口,强度差值很小,而沿其他方向移动窗口,强度插值很大,则认为待检测点位于图像边缘. 根据该思想可得

(1)

其中：W(x,y)为窗口,一般取高斯窗口；u,v是以待测点为中心的偏移量；I为图像像素值. 将

由Tayloy公式展开并截取,可近似为

(2)

则

(3)

R=detM-k(trM)2,

(4)

根据经验k=0.04～0.06.

1.2 Harris算法

Harris算法实现步骤如下.

1) 计算图像每个点的x,y方向梯度Ix,Iy:Ix=Gx⊗I,Iy=Gy⊗I;

5) 计算图像每个点的特征响应强度R=detM-k(trM)2;

6) 根据阈值τ判定是否为特征点.

特征检测效果如图2所示,其中：(A)为原始图像；(B)为原始图像检出的特征点；(C),(D)分别为(A)旋转10°和-10°后检出的特征点. 实验中,最大特征响应强度的0.1倍作为阈值,可见Harris特征点具有旋转不变性.

图2 特征点检测结果Fig.2 Detection results of feature points

2 基于灰度直方图的特征匹配与定位算法

2.1 特征描述子定义

特征描述子应具可区分性,且当图像发生平移、旋转等变化时,应保持其不变性. 本文旨在满足伺服定位、抓取中的定位精度和实时性要求,力求简化描述子定义,减小匹配代价. 以特征点为中心,计算邻域内点的灰度直方图,作为该特征点的描述子. 本文用圆形邻域取点,以保证描述子具有旋转不变性,步骤如下.

1) 以特征点为中心取样.

考虑到数字图像的离散特性,圆形邻域取样公式定义为

(5)

其中: grayx和grayy分别为灰度图像横、纵坐标；cornerx和cornery分别为特征点横、纵坐标；rwindow为取样窗口半径. 图3(A)为按式(5)设计的取样窗口,窗口大小为21×21,取到圆形邻域内349个点,取样窗口大小可根据实际需要进行调整.

2) 根据取样结果计算灰度直方图,并做归一化处理.

以图2(B)中右上角特殊标记特征点为例,采样结果如图3(B)右上角小图所示. 灰度直方图计算中,设置Bins数为16,得到16维向量

H=(0,0,0,0,1,5,22,43,11,157,46,8,17,34,5,0),

对该特征向量做归一化处理,归一化公式为

(6)

归一化后向量为

G=(0,0,0,0,0.006,0.042,0.113 8,0.245 5,0.047 9,1,0.221 6,0.095 8,0.101 8,0.179 6,0.036,0),

即为特征点的描述子,归一化直方图如图3(B)所示,图3(C),(D)分别为图2(C),(D)中对应特殊标记特征点的归一化直方图. 由图3可见,3个对应角特征点的描述子相似度很高,保持了旋转不变性.

图3 特征点的描述子Fig.3 Descriptors of feature points

2.2 特征匹配与目标定位算法

特征匹配的依据是特征点描述子间的相似度,本文采用巴氏距离作为度量标准,巴氏距离定义为

(7)

特征匹配步骤如下：

1) 选择标准图像中的任意描述子G[m]；

2) 在场景描述子中寻找G′[n],使得d(G[m],G′[n])最小；

3) 若d(G[m],G′[n])<τ,则认为标准图像特征点m与场景图像特征点n匹配.

特征匹配结果如图4所示,其中每条连线对应的两点为匹配的特征点.

目标定位过程如下：

1) 根据匹配结果,寻找描述两组特征点间的变换关系,即估计归一化单应性矩阵为

(8)

满足

(9)

2) 根据标准图像4个顶点坐标,利用式(9)计算对应场景图像4个顶点坐标,从而定位目标.

目标定位结果如图4所示,红色框即为定位的标准图像在场景图像中位置,利用式(9)可计算标准图像每个像素点在目标图像中的位置.

图4 旋转10°(A)和-10°(B)的特征匹配及目标定位结果Fig.4 Results of feature matching and target location for 10° (A) and -10° (B) rotation

3 实验结果对比分析

图5和图6分别为本文算法与SIFT[11],SURF[12],Harris-SIFT[16],Harris-SURF[17],ORB[14]算法的匹配及定位效果对比. 图5和图6分别采用peppers图像、barche图像作为标准图像,各自旋转10°后作为场景图像. 通过调整算法参数,4种算法特征匹配数量基本相同. 对于特征点分布,本文算法、Harris-SIFT算法、Harris-SURF算法更合理,SIFT算法、SURF算法次之,ORB算法较差. SIFT,SURF,Harris-SIFT,Harris-SURF算法及本文算法定位精度均表现较好,视觉观察差别较小,明显优于ORB算法. 下面对图6中barche图像做更深入的实验数据对比,考察4种算法的运行速度和定位精度.

实验环境：电脑主频3.6 GHz,内存16 GB,操作系统Windows10 64位,开发平台VSC++,SIFT,SURF,ORB算法实现调用了OPENCV库函数. 由于SIFT,SURF算法为非免费资源,无法在RELEASE模式下运行,为具可比性,实验中统一采用DEBUG模式运行,时间单位为ms. 在RELEASE模式下,运行速度约可提升10倍. 表1为图6中barche图像各角度下定位过程运行时间对比. 由表1可见,ORB算法耗时最少；本文算法、Harris-SURF算法、Harris-SIFT算法次之；SURF算法和SIFT算法实时性较差.

平移误差定义为：定位中估计的4个边界顶点坐标与场景中对应的4个实际边界顶点坐标之间距离的最大值. 表2为不同算法在各角度下定位过程平移误差的对比. 由表2可见,平移定位误差均值排序为：SIFT算法(0.23)<本文算法(1.20)

表1 不同算法的运行时间(ms)对比

表2 不同算法定位过程平移误差(像素)的对比

旋转误差定义为：定位中估计的4条边界线与场景对应的4条实际边界线角度偏差绝对值的最大值. 表3为不同算法在各角度下定位过程旋转误差的对比. 由表3可见,旋转定位误差均值排序为：SIFT算法(0.04)<本文算法(0.21)

表3 不同算法定位过程旋转误差(°)对比

鉴于机器人视觉伺服定位、抓取过程中,相机位置固定、拍摄角度不变、光线稳定,每次触发拍照时,工件图像只发生平移和旋转,不存在尺度变化和仿射变换,故在定位精度实验中,重点对比了平移和旋转误差. SIFT算法定位精度最高,本文算法次之,Harris-SIFT算法和Harris-SURF算法效果较好,SURF算法一般,ORB算法不能满足精度要求. 在运行速度上,ORB算法实时性最好,本文算法次之,Harris-SIFT算法、Harris-SURF算法实时性较好,SURF算法、SIFT算法难以满足实时性要求. 因此,本文算法综合效果最好.

综上可见,本文算法在特征提取环节继承了Harris算子定位精度高、具有旋转不变性的优点,同时也保留了其对尺度变化敏感的不足；在特征匹配环节,提出的描述子定义简单、易实现,匹配代价小,实时性较好,但对光线变化较敏感.