一种改进Harris-SIFT算子的图像匹配算法*

李 兰 谢勤岚

(中南民族大学生物医学工程学院 武汉 430074)

一种改进Harris-SIFT算子的图像匹配算法*

李 兰 谢勤岚

(中南民族大学生物医学工程学院 武汉 430074)

SIFT特征是一种性能良好的检测局部的特征,被广泛应用于图像匹配。针对SIFT算法的数据处理量大、运行速度慢、时间复杂度高等问题,提出了一种基于角点精确定位、降低特征维度、增强近似最近邻匹配法的改进算法。实验的结果证明,改进后的算法提高了算法的运行速度和匹配精确度。

SIFT; Harris; 图像匹配

Class Number TP391

1 引言

图像匹配是利用图像处理方法将两幅图像相同的区域进行匹配[1],它是图像处理领域的一个重要应用技术,在计算机视觉、医学图像分析、模式识别等多方面都有着广泛的应用价值。在实际应用中,由于处在不同条件下,匹配的图像之间往往存在着尺度、噪声、亮暗、旋转等差异,这给图像匹配算法带来了不少难题。而基于局部特征的算法只考虑特征信息,具有较强的抗噪声、形变能力和计算量小、鲁棒性高的优点[2],因此被广泛应用于各个行业中。到目前为止,已经有大量的局部特征算法被提出。文献[3～4]对几种有代表性的局部特征进行了性能评估,通过实验表明SIFT是性能最为鲁棒的局部特征算法。

SIFT算法由D.G.Lowe[5～7]于1999年提出,SIFT特征[5～7]是一种性能良好的局部特征,被广泛应用于图像匹配中,但SIFT特征点有128维描述符,所以存在数据处理量大、运行速度慢、时间复杂度高的问题[6]。

本文结合Harris角点检测[7]和SIFT特征描述算子的优点,利用Forsnter算子思想对角点进行精确定位,然后改进SIFT算法描述子,用36维特征描述符代替128维特征描述符,进行特征描述。最后利用增强型近似最近邻匹配方法对描述子进行匹配,达到图像匹配的目的。

2 改进的Harris角点检测算法

Forsnter算子[8]是摄影测量中经典的兴趣点定位算子,具有精度高、速度快等特点,其基本思想是：通过获得角点,以该点为中心建立最佳窗口,对最佳窗口内的每个像素的边缘直线(垂直于梯度方向)进行加权中心化,得到角点的精确坐标。

利用Harris算子[9～10]提出的角点作为Forsnter算子的最佳窗口中心点,在窗口内进行加权中心化,精确定位角点坐标的具体计算原理如下：

最佳窗口内任一像素(x,y)的边缘直线l的方程可以表示为

p=x·cosθ+y·sinθ

(1)

式(1)中,p为原点(最佳窗口的左上角像素)到直线l的距离,θ为梯度角,tanθ=gy/gx,gx、gy为该点的robert梯度。设角点坐标为(x0,y0),式(2)中,v是点(x,y)到直线l的垂直距离,则可列出如下关系式：

p+v=x0·cosθ+y0·sinθ

(2)

(3)

式(3)中,将原点到边缘的直线的距离视为观测值,而边缘直线的方向保持不变,权w(x,y)是梯度模的平方,因此,权的实质即是该边缘尺度。对式(3)进行法化,得到法方程：

(4)

对式(4)求解,即可得到精确角点坐标(x0,y0)。

3 改进的SIFT算法

3.1 用36维特征描述子代替原128维特征描述子

将关键点周围16×16区域改为15×15区域[11],在该区域上采样计算方向,将每个5×5的区域方向投影到8个方向,如图1所示

对于每个种子的8个方向的梯度方向直方图的累加值s1、s2、…、s8[4～6],如图2(a)所示,可以用4个方向v1,v2,v3,v4来表示为图2(b)所示。它们之间的关系是：

(5)

改进后的特征描述子维数为

相比原来的特征描述子128维,维数降低不少。将描述每个种子的累加值的数量由8个降为4个,由于4个累加值仍然包含了8个累加值中所有信息,故并不影响对特征点信息的描述。基于此这种改进大大的节约了计算时间,提高算法的实时性。

3.2 用增强型近似最近邻匹配方法进行匹配

由于最近邻匹配法[2]是一种单向的操作,可能会产生错误的匹配点。增强型最近邻匹配双向法流程图如图3所示。

将最近邻匹配法单向判定改为增强型最近邻匹配法双向判定后,对可能存在的匹配点对进行反向的确认,实现正反双向判定,提高了匹配的正确率。

4 实验和结果

为了验证本文改进的算法的图像配准速度和效果,本文设计了几个实验来与原始Harris-sift算法来进行比较。实验平台为Pentium(R) Dual-Core E6700 处理器, 3.20GHz,内存为4G的PC机,Window 7 64位操作系统,编程环境为VS2012+OpenCv2.4.8。实验结果从特征点个数、匹配点对、特征点对、特征点匹配时间、算法运行总时间以及正确匹配率5个方面对改进算法与原算法进行对比。

图4和图5是图像的匹配实验结果,对比可以看出,SIFT算法提取出来的点不是角点,不能反映图像的视觉角点,而本文算法结合改进的Harris-sift算法提取的特征描述点都是角点,并降低了特征提取的复杂度,大大提高了原SIFT算法的匹配率和速度。

表1 图像匹配比较数据

表1是实验得到的数据,通过分析表1中的实验数据和匹配结果可以发现,改进的算法用Forsnter算子思想对Harris角点进行精定位,提高了图像特征点提取的精确度。然后用36维的特征描述符对特征点进行描述,大大节约了匹配时间,用增强型近似最近邻匹配方法进行匹配,提高了算法的匹配率。

5 结语

本文针对SIFT算法存在数据处理量大、运行速度慢、时间复杂度高的问题,提出改进的Harris-sift的图像匹配算法。该算法采用Forsnter算子获取Harris角点精确定位,然后改进SIFT算子,对其描述符进行降维,并在匹配过程中采用双向匹配法,提高了特征点的匹配率和匹配速度。实验表明,本文的改进算法准确率更高,运算速度更快。但本文改进算法也有不足之处,在将sift算子由128维改为36维后,会降低算法的正确匹配率,虽然改进的算法整体上提高了特征点正确匹配率,因此对该算法还需要进行进一步研究,如何在降维的同时提高正确匹配率,这是下一步工作的重点。

[1] 冈萨雷斯.数字图像处理[M].北京：电子工业出版社,2003.

[2] 王永明,王贵锦. 图像局部不变性特征与描述[M].北京：国防工业出版社,2010.

[3] 曾凡永,顾爱辉,等.几种特征点提取算子的分析和比较[J].现代测绘,2015(3):15-18.

[4] Mikolajczyk K, Tuytelaars T, Schmid C.仿射区域描述子的比较[J].国际计算机视觉杂志,2005,65(1/2):43-72.

[5] D.Lowe.尺度不变特征点中独特的图像特征点[J].国际计算机视觉杂志,2004,60,(2):91-110.

[6] D.Lowe. 局部尺度不变特征点的物体识别[J].国际计算机视觉杂志,1999:1150-1157.

[7] Lowe D.开源SIFT库.Lowe D. OpenSIFT-An open-source SIFT library[EB/OL].

[8] 李鹏程,曾毓敏,张琴.基于改进Harris的图像拼接算法[J].南京师范大学学报(工程技术版). 2014(09): 43-48.

[9] 张艳,张志成.混合Forstner算法和SIFT灰度图像特征点提取[J].科技通报.2012(10):64-70.

[10] 毛雁明,兰美辉.角点检测方法研究.[J].现代计算机：下半月版,2008(10):86-88.

[11] 杨松,邵龙潭,宋维波,等.一种基于SIFT特征的快速图像匹配算法[J].计算机应用与软件,2016,33(7):186-189.

An Improved Image Matching Algorithm Based on Harris-SIFT

LI Lan XIE Qinlan

(College of Biomedical Engineering, South-Central University for Nationalities, Wuhan 430074)

SIFT features are a kind of local features with high performance, which are applied widely in the image matching field. However, there are some disadvantages about SIFT algorithm, such as, a large volume of data processing, low running speed, high time complexity and so on. Based on these disadvantages, the paper proposes an improved image matching algorithm based on Harris and SIFT. Experimental results prove that the improved algorithm has higher matching accuracy and less matching time.

SIFT, Harris, image matching

2016年10月25日,

2016年11月28日

李兰,女,硕士研究生,研究方向：医学图像处理。谢勤岚,男,博士,教授,研究方向：智能信号与图处理,电子系统集成技术,生物医学系统辨识,建模与仿真,生物信息学,智能控制理论等。

TP391

10.3969/j.issn.1672-9730.2017.04.009