基于压缩感知的SIFT图像匹配算法的研究

谢 昕，徐 殷，熊焕东，李 波，胡锋平

（华东交通大学1.信息工程学院；2.土木建筑学院，江西 南昌330013）

基于压缩感知的SIFT图像匹配算法的研究

谢 昕1，徐 殷1，熊焕东1，李 波1，胡锋平2

（华东交通大学1.信息工程学院；2.土木建筑学院，江西 南昌330013）

针对尺度不变特征变换（SIFT）算法的计算量大、速度慢等缺点，提出了一种融合压缩感知的图像匹配算法。首先对目标图像和待匹配图像进行预处理，利用压缩感知技术进行图像压缩，结合SIFT算法提取图像的特征点，通过自适应阈值序贯相似性检测（SSDA）匹配算法进行图像快速匹配搜索，从而找到最佳匹配位置。

尺度不变特征变换；压缩感知；序贯相似性检测算法；自适应阈值

随着计算机技术的快速发展，图像匹配[1]逐渐成为计算机机器视觉的一个重要研究方向，目前广泛应用在数字图像安全、空间探测、医学图像分析、虚拟现实技术、遥感图像处理、无线传感器网络和机器视觉等领域。

近年来，国内外许多研究学者相继提出了多种图像匹配算法。1988年Harris C提出了Harris角点图像匹配算法[2]，该算法图像配准精度较高且计算量小，并且对图像的旋转没有限制，但对于图像边缘信息少的匹配效果不太理想。2004年Lowe David G提出了SIFT（scale invariant feature transform）特征点匹配算法[3]，该算法具有旋转、缩放以及仿射不变性等特点，虽然能够保持一定程度上的稳定性，但存在误匹配现象。上述两种方法只能完成一些特定条件下的图像匹配且匹配的效率不高，对于在复杂环境下的图像匹配还有待进一步提高。

2003年俞辉等人提出了基于轮廓特征的图像匹配算法，利用轮廓特征有效解决了图像旋转的问题[4]，同时也改善了光照的影响，但该算法中轮廓特征的提取易受噪声的干扰，不适于有噪声影响和轮廓不明显的图像。2005年王立新等人设计了一种快速高效的图像匹配算法[5]，使用序贯相似性检测（sequential similarity detection algorithm，SSDA）算法设置阈值进行图像匹配，该算法的匹配效率较高且易于实现，但该算法阈值的适当选取存在较大困难，且对图像的明暗度、尺度旋转等变化较为敏感。2011年曾峦等人采用了改进的SIFT特征提取和匹配算法[6]，通过采用SIFT描述向量之间的欧式距离最小值与次小值的比值作为阈值，对图像先进行粗匹配，再利用匹配结果对主方向角度差直方图去除伪匹配，有效解决了图像匹配阈值的选择问题且算法稳定、可靠，但该匹配算法耗时太长，对大图像的处理效果也不太理想。

针对上述问题，本文引入压缩感知[7]进行空间变换信号描述，在保证信号足够重构的前提下，对数据进行压缩，利用SIFT算法提取图像的特征点，结合自适应阈值序贯相似性检测[8－9]匹配算法进行图像快速匹配，从而找到最佳匹配位置。

1 压缩感知概述

文献[10-11]指出，设X是RN空间（RN空间的任何信号都可以用N×1维的基向量的线性组合表示）一维的可压缩信号。信号X∈RN通过正交基所描述的变化系数向量可以表示为

其中：Ψ为正交变换基组成的N×N变换域矩阵；Θ是Ψ的等价或逼近的稀疏表示。

设计一个平稳的、与变换基不相关的观测矩阵Φ，其大小为M×N（M≪N）维，对Θ进行观测得到观测向量Y=ΦΘ或Y=ΦΨTΘ。该过程也可以描述为信号X通过矩阵ACS（ACS＝ΦΨT）进行自适应观测

其中：ACS称为传感因子；Y是一个M×1维的观测集合，由于Y中包含了每个信号的特有信息，因此不同的信号所对应的Y值也不同，对于信号是图像的情况，可以将压缩后的数据Y做为图像的特征表示。

2 自适应阈值序贯相似性检测（SSDA）算法

SSDA算法是1972年由Bamea D I和Silverman H F等人提出的一种著名的图像匹配算法。该算法能对不匹配的点进行快速丢弃，大大减少了匹配的计算量，从而使匹配速度得到很大提高，该算法容易实现且匹配速度快。

自适应阈值SSDA算法是对传统SSDA匹配算法的一种改进，其实现原理及步骤如下：

设目标图像S的大小为N×N，待匹配图像T的大小为M×M，待匹配图像叠放在目标图像上平移，待匹配图像覆盖下的那块目标图像设为子图Si,j，（i，j）为这块子图的左上角点在目标图像S中的坐标，（m，n）为待匹配图像上每个像素点的坐标，则有：1≤i，j≤N-M+1，且0≤m，n≤M。

1）定义绝对误差值ε

2）把目标图像S的左上角点作为起始点，开始计算待匹配图像T与待匹配图像覆盖下的那块目标子图像Si,j之间匹配的累计误差，并将其值作为自适应阈值的初始值t0，然后按照行列顺序依次选择进行匹配检测。

3）从第二点开始，在目标图像区域内每次以随机不重复的顺序选取像素点进行匹配，计算待匹配图像与该位置子图像中的对应像素点的累积误差，记为t。将t与t0进行比较，若t≥t0，则立即停止对该目标模块的计算，并将子图像移动到下一个位置并进行计算t；若t＜t0，则用t更新阈值t0，并记录下该目标子图像左上角像素点的坐标位置，即

4）按照上述步骤依次搜索整个目标图像，得到误差累加和最小的值，即为最小阈值。

3 SIFT算法流程[12-14]

SIFT算法利用金字塔和高斯核滤波差分在尺度空间中寻找极值点，并提取图像的特征点进行局部特征匹配，主要流程如下：

3.1 特征点的检测

根据Tony Lindeberg理论可知，高斯函数作为唯一的尺度空间内核函数，通过一个尺度可变的高斯函数G（x，y,σ）与原始图像I（x，y）来构造一个图像的尺度空间函数L（x，y,σ）

其中：*表示卷积运算；σ是图像的尺度空间因子，其值越小表示图像被平滑的越少，相应的尺度越小。

为了在尺度空间中更有效地检测出稳定的特征点，可使用高斯函数D（x，y,σ）来进行尺度近似归一化处理

其中：k为阈值。在高斯尺度空间中，通过高斯平滑和降采样处理，每个像素点和同一层的8个相邻点及上下相邻层的各9个相邻点共26个像素点进行比较，得到尺度空间和图像空间的局部极值点，并记为局部特征点。

3.2 特征点的精确定位

可以通过Hessian矩阵来精确定位特征点的位置和尺度，Hessian矩阵为：，则该点的稳定性E为

其中：r为控制特征值大小的参数。

3.3 特征点的方向

通过特征点邻域像素的梯度方向分布来确定特征点的方向，特征点的梯度幅值m（x，y）和方向θ（x，y）计算公式如下

其中：L表示检测的特征点的尺度，上述方法可以使SIFT特征点具有旋转不变形。

3.4 特征点的描述

每个特征点都具有位置、方向、尺度3个信息，以特征点为中心均匀分成4×4个邻域子块，每个子块形成一个像素点，每个像素点含有8个方向的信息向量，即每个特征点可以得到128个方向特征描述。因此这128个特征向量可以准确地描述所有特征点。

4 SIFT算法的改进

首先对待匹配图像和目标图像进行预处理，利用压缩感知技术快速的得到两幅图像的局部特征，然后利用SIFT算法进行特征点提取，结合自适应阈值SSDA算法进行图像匹配,从而找到最佳匹配位置。改进后的算法流程如图1所示。

图1 改进后的图像匹配算法流程图Fig.1 The improved image matching algorithm flow

算法描述：

1）预处理操作。由于在获取图像过程中可能会受到噪声等因素干扰，为了避免这些因素对本算法的影响，本文对读入的目标图像T和待匹配图像S进行预处理操作，比如去噪、二值化处理等。

2）压缩感知获取图像局部特征。通过对预处理后的图像进行小波变换，得到稀疏的小波变换系数矩阵，通过设计合适的稀疏随机观测矩阵对P其进行观测，从而可以得到数据量远小于原信号或图像维数N的M个观测值（M≪N）。根据文献[15]采用的稀疏随机观测矩阵P定义如下

其中：s通过随机概率在2～4之间[16]。因此，利用压缩感知可以快速准确获取图像特征并对图像进行压缩。

3）SIFT算法提取特征点。利用SIFT算法分别对2幅图像进行特征点描述，然后进行特征点提取及匹配。特征点匹配以2个特征点描述符之间的欧式距离作为相似度准则。假设特征点对和的特征描述符分别为da和db，则其欧式距离定义为

采用K-D树（二叉树的一种，K维数据结构）进行优先搜索，查找出目标子图像与待匹配图像中特征点p欧式距离最近和次近的2个相连特征点p'和p",然后计算p和p'，p和p"两组描述符之间欧式距离的比值r。

4）确定最小阈值。通过自适应阈值SSDA匹配算法确定最小阈值t，其实现如图2所示。

图2 确定最小阈值流程图Fig.2 The flow of minimum threshold

5）图像匹配。将r与阈值t进行比较,如果r≤t，则匹配成功，即找到最佳匹配位置；否则让待匹配图像在目标图像上进行行列平移一个位置，直到搜索完目标图像为止。

5 算法仿真及结果分析

为了验证算法的可行性时，本文选取了经典的lena图像作为目标图像，lena图像中的一小部分图像作为待匹配图像，如图3所示，2幅图像的大小分别为512×512和64×64。图4为2幅匹配图像通过本文算法所提取的匹配点图像，图5为特征点匹配图像，图6为最后的匹配效果图像。

图3 目标图像和待匹配图像Fig.3 Original image

图4 提取的匹配点图像Fig.4 Extraction of image matching point

图5 特征点匹配图像Fig.5 Feature points matching images

图6 匹配效果图Fig.6 Effect image after matching

本文还对目标图像进行逆时针旋转30°与待匹配图像进行匹配，图7为特征点匹配图像，图8为匹配效果图。

图7 特征点匹配图像Fig.7 Feature points matching images

图8 匹配效果图Fig.8.Effect image after matching

本文与以下几种经典的匹配算法从特征点检测数量、匹配点数量、算法时间和准确率上来衡量这几种算法的优越性，如表1所示。

表1 几种匹配算法的比较Tab.1 The comparison of several kinds of matching algorithm

从表1发现，本文算法从特征点的数量和匹配点的数量上都少于传统的SIFT算法，耗时与准确度上也优于其他几种经典的匹配算法，这说明本文算法的匹配精度更高、匹配速度更快。

6 结论和展望

本文在传统的SIFT算法的基础上，提出了一种新的基于压缩感知图像匹配算法。不仅大大减少了与图像匹配无关的特征点，使特征点匹配更精确，又能让图像匹配速度更快。通过仿真实验结果表明，本文算法在匹配准度与匹配时间上都得到比较满意的效果，能够满足机器视觉系统的实时处理要求。但是对于彩色图像的匹配不太稳定，还需要进一步的研究。

[1]王军，张明柱.图像匹配算法的研究进展[J].大气与环境光学学报，2007，2(1)：11-15.

[2]HARRIS C，STEPHENS M.A combined corner and edge detector[C]//Proc of Alvey Conf Vision.England:Manchester University Press，1988：189-192.

[3]LOWE D G.Distinctive image features from scale invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[4]俞辉，侯在克，何旭莉.一种基于轮廓特征的图像拼接算法设计与实验[J].石油大学学报：自然科学版，2003，27（2）：114-118.

[5]王立新，刘彤宇，李阳.SSDA匹配算法的研究及实现[J].光电技术应用，2005，20（3）：53-55.

[6]曾峦，王元钦，谭久彬.改进的SIFT特征提取和匹配算法[J].光学精密工程，2011，19（6）：391-1396.

[7]DONOHO D L.Compressed sensing[J].Information Theory，2006，52（4）：1289-1306.

[8]王丽丹，华顺刚，刘红卫.自适应阈值SSDA图像匹配拼接算法的研究[J].光学技术应用，2006，21（3）：54-58.

[9]张维琪，樊斐.自适应SSDA图像处理匹配并行算法设计与实现[J].计算机工程与用，2014，50（20）：64-68.

[10]石光明，刘丹华，高大化.压缩感知理论及研究进展[J].电子学报，2009，37（5）：1070-1081.

[11]郭厚焜，吴峰，黄萍.基于压缩感知和字典学习的背景差分法[J].华东交通大学学报，2012，29（1）：43-47.

[12]白廷柱，侯喜报.基于SIFT算子的图像匹配算法研究[J].北京理工大学报，2013，33（6）：622-628.

[13]郝勇，戴芳，黎莹.位平面和SIFT相结合的图像匹配方法[J].计算机工程与应用，2013，49（8）：191-194.

[14]QIU WENTAO，ZHAO JIAN，LIU JIE.Image matching combine SIFT with regional SSDA[J].International Conference on Control Engineering and Communication Technology,2012,78：177-179.

[15]ZHANG K H，ZHANG L，YANG M H.Real-time compressive tracking[C]//European Conference on Computer Vision，2012：89-99.

[16]王松林，项欣光.基于压缩感知的多特征加权目标跟踪算法[J].计算机应用研究，2014，3(3)：929-932.

Research on SIFT Image Matching Algorithm Based on Compressed Sensing

Xie Xin1，Xu Yin1，Xiong Huandong1，Li Bo1，Hu Fengping2
(1.School of Information Engineering，East China Jiaotong University，Nanchang 330013，China；2.School of Civil Engineering and Architecture East China Jiaotong University，Nanchang 330013，China)

Aiming at the disadvantages of massive calculation and slow speed of traditional scale invariant feature transform(SIFT)algorithm,this paper proposes an improved image matching method which combines compressed sensing(CS)algorithm.Firstly,target images and images to be matched are preprocessed and compressed by using compressed sensing technology.Then,image feature points are extracted in combination with SIFT algorithm. Finally,sequential similarity detection algorithm (SSDA)with adaptive threshold is used for fast search of image matching to find an optimal matching position,and a matching image is obtained.Experimental results demonstrate that the method realizes fast image matching,efficiently overcomes the shortcomings of heavy computation and low efficiency in the process of extracting image features,and guarantees the matching accuracy and efficiency,which meets the real-time requirements in machine vision system.

scale invariant feature transform;compressed sensing;sequential similarity detection algorithm; adaptive threshold value

TP391.9

A

1005-0523（2015）06-0115-07

(责任编辑 姜红贵)

2015-05-04

国家自然科学基金项目（61272197）；江西省自然科学基金（20132BAB201027,20142BAB207007）；江西省科技厅工业支撑计划（20151BBE50055）；赣鄱英才555工程领军人才培养计划（S2013-57）；江西省研究生创新专项基金项目（YC2015S254）

谢昕（1969—），男，教授，研究方向为机器视觉和网络与信息安全。