面向单视频超分辨率重建的改进的SIFT配准算法

孙 文 华

(南昌工程学院信息工程学院，江西 南昌，330099)



面向单视频超分辨率重建的改进的SIFT配准算法

孙 文 华

(南昌工程学院信息工程学院，江西 南昌，330099)

针对单视频超分辨率重建传统的基于SIFT特征点检测的配准，在特征匹配上占用时间很大，难于满足实时性的要求，而用于计算128维特征描述子的时间最长这一缺点，提出了一种改进的SIFT配准算法，该算法的原理为通过放弃对128维特征描述子的计算，采用特征点之间的灰度相关系数来进行初始匹配，以期大大减少计算时间，提高特征匹配速度。实验结果证明，该算法在配准结果、时间消耗上明显优于传统配置算法。

特征点检测;特征匹配;SIFT配准算法;超分辨率重建

单视频超分辨率重建中，只涉及到空间分辨率的增强。由于单视频超分辨率重建的特殊性，传统的基于SIFT特征点检测的配准只是一种通用解决方案，但传统SIFT算法在实时性方面较差，主要原因就是需要对128维特征描述子进行计算，从而需要耗费大量时间在特征匹配上。此外，利用特征描述子的欧式距离的消除法在多对一的歧义消除中还会有错误选择的出现。故如果想要在实时性上有所提高，就必须对算法进行优化，对特征描述子进行改进。在此笔者提出一种改进的SIFT配准算法，该算法的原理为通过放弃对128维特征描述子的计算，采用特征点之间的灰度相关系数代替特征描述子进行视频帧间配准，从而大大减少计算时间，提高特征匹配速度。

1 传统SIFT特征匹配算法

David.Lowe在1999年在对现有的基于不变量技术的特征检测方法[1]研究和总结的基础上，提出了尺度不变特征变换(Scale Invariant Feature Transform)，简称SIFT算法。该算法是基于尺度空间的，通过对图像平移、旋转、缩放、甚至仿射变换保持不变性的图像局部特征。并于2004年得以改善，现被广泛应用于物体识别、导航、医学图像处理、图片拼接[2]、影像跟踪配准和手势识别等多个领域。

1.1 传统SIFT特征匹配算法特点

近年来，SIFT特征匹配算法在计算机视觉 (Computer Vision) 领域中的研究和应用都相当广泛，该算法既可以对影像图片[3]中局部具有明显的特征进行检测与描述，又可以对多幅图像中检测到的特征向量进行配对。SIFT特征匹配算法的特征归纳起来主要有：(1)关键点检测速度快；(2)关键点定位精确；(3)独特性好，信息量丰富，对特征描述子的计算过程中还包含了区域统计特性；(4)稳定性较好，不但对常见的线性光照模型表现出不变性，而且对复杂的光照变化模型同样具有较强的适应性。

1.2 变换参数矩阵的计算

SIFT特征匹配算法采用六参数仿射变换模型[4]，即两帧之间的变换矩阵共有6个未知参数。而每一对匹配可以建立2个匹配方程，如式(1)所示。(u,v)是原图中点(x,y)在目标图中的匹配特征点。

u=Ax+By+C

v=Dx+Ey+F

(1)

式(1)又可转化为：

(2)

其中的3×3矩阵就是六参数配准中的变换参数矩阵，只要求出它，就可以进行图像的配准。6个未知数需要6个方程，即3对特征点。可转化为式(3)：

(3)

根据线性代数的知识，可知变换参数矩阵有解，但是事实上图像中存在很多组这样的特征点匹配，但由于匹配误差[5]导致的解各不相同，故只能求出一组解，以尽量逼近结果，即超定方程组的最小二乘解。最终n对匹配特征点可以转化为：

(4)

目前常用的解决这个问题的方法有最小二乘法，退火算法和遗传算法[6]，现对其做一个简单比较。

最小二乘法只能解决一阶的超定方程问题，但是速度非常快，且解几乎是最优解。模拟退火算法和遗传算法是启发式搜索算法，前者模仿固体冷却时内部粒子的不稳态，采用随机干扰来搜索最优解，但后者则是模仿自然界的生物种群进化行为，利用选择，交叉和变异3种行为和一个评估函数来进行最优解的搜索。由于这2种算法并非专为一阶超定方程组准备，所以在实验中发现用这2种算法来解变换参数矩阵，只能逼近最优解，并且收敛速度慢。因此最终采用最小二乘法来计算变换参数矩阵[7]。

假设：

H×X1=X2

(5)

X1是一个3×N的矩阵，其中N为特征点匹配的对数。由于N往往不为3，X1并非方阵，因此不能直接求其逆矩阵而得解H。现对等式两边同时乘以X1的转置矩阵，则等式左边变成H和一个3×3方阵之积，于是可得解：

H=(X2*X1T)×(X1*X1T)-1

(6)

2 改进的SIFT特征点匹配

图像的特征点匹配主要分为以下步骤：第一步，进行SIFT特征点检测；第二步，进行特征点的初始匹配；第三步，进行变换参数矩阵的计算和误匹配与歧义方面的消除。在这几步当中，除了变换参数矩阵的计算，都需要用到128维特征描述子。特征描述子包含了特征点周围16个4×4邻域内的8个方向的梯度变化信息，是一个128维的归一化向量，使其能够表达丰富的图像梯度信息[8]。

在单视频超分辨率重建过程中，每秒大约有30帧的图像信息，故相邻的帧之间的图像信息都不会有太大的变化，也就是说图像中特征点的位置都不会出现太大的偏移，故完全可以利用X与Y坐标的信息消除歧义匹配或者误匹配。改进SIFT配准算法通过放弃对128维特征描述子的计算，而采用特征点之间的灰度相关系数来进行单视频帧与帧之间的配准[8]。

2.1 改进的初始匹配

根据特征点匹配的原理，在进行SIFT特征点检测之后，就是对特征点进行初始匹配。传统算法中认为128维特征描述子的欧氏距离优劣直接影响到特征点的初始匹配的成功与否。

假设m是图1(a)中的特征点，坐标为(u,v)，n是图1(b)中与之对应的特征点，坐标为(j,k)，分别以m和n为中心，R1为半边长作2个正方形邻域，则这2个邻域的相关系数定义为：

(7)

由于现在放弃对128维特征描述子的计算，且特征点之间的灰度相关系数是可以用来甄别特征点的匹配，故选取了特征点之间的灰度相关系数来作为初始匹配的依据。通过实验发现，当特征点之间的灰度相关系数阈值达到0.95的时候就能较好的剔除误匹配[10]。假设现在需要在目标图中找一个特征点与原图中的特征点Pi进行初始匹配。可以通过以下步骤进行：

Step 1：根据式(7)，分别计算Pi与目标图中所有特征点的灰度相关系数。

Step 2：选取目标图特征点中，找出和Pi相关性最强的一点Pj。

Step 3：假设Cij>0.95，则认为Pi和Pj是一对初始匹配。

在实际应用中，一个320×200像素的图像往往能找到大约400个特征点。因而如果对每一对特征点都进行灰度相关系数的计算，那么就要计算大约16 000次灰度相关系数，如果灰度相关系数的计算邻域再大一点，这与性能优化的初衷背道而驰。实验证明，其计算时间甚至大于用128维特征描述符来进行运动配准。

考虑到应用环境为基于单视频超分辨率的重建，相邻几帧之间的差异在非高速摄影中变化往往不大，每个特征点的仿射变换位移很小，所以可以将目标图中候选特征点集限定在和原图特征点平面坐标欧氏距离小于r的子集上。之前的步骤就可以修改为：

Step 1：选择候选特征点，将目标图中与Pi的平面坐标欧氏距离比r小的作为候选特征点。

Step 2：计算候选特征点与Pi的灰度相关系数。

Step 3：找出与Pi之间灰度相关系数最高的一点Pj。

Step 4：假设Cij>0.95，则认为Pi和Pj是一对初始匹配。

在实际的应用当中，r的取值需要根据图像的长宽像素尺寸来决定。通常，r取50或者长宽像素较大者的1/6。

2.2 改进的匹配关联度

在能效消除多对一歧义匹配或者误匹配的常用方法当中，通常认为，匹配关联度是唯一一种既能有效消除多对一歧义匹配又能同时消除误匹配的方法。

基于128维SIFT特征描述符子的匹配关联度定义为：

(8)

其中，cAB，cCD分别为匹配点对(A,B)和(C,D)的灰度相关系数，这里的d(p1,p2)为点p1和点p2基于128维特征描述符的欧几里德距离。

(9)

(10)

其中，dr代表相对距离差，ε为相对距离偏差的一个阈值，在此取ε=0.3。当dr=0时，即(A,C)和(B,D)相对距离差为零时，δ(A,B,C,D)=1，这时在其它因素相同的情况下，匹配点对(C,D)与(A,B)的关联性最强，随着dr的增大，δ(A,B,C,D)单调递减。分母上，若(d(A,C)+d(B,D))×0.5值越小，即是(A,C)和(B,D)之间距离的平均值越小，S(A,B)越大，也就是说(C,D)离(A,B)越近，相同条件下与待验证匹配的关联性越强。

根据式(8)和式(9)，发现在一对匹配点的匹配关联度计算过程中，对两点之间的距离进行了多次的计算，而之前这个距离用的是128维特征描述子的欧氏距离来进行表示[11]。由于现在放弃对128维特征描述子的计算，故这个距离必须用平面坐标系的欧氏距离替换。

在匹配关联度中，这个距离主要是为了计算多个匹配之间的相互关系，也就是多组匹配在原图中的特征点关系和在目标图中的特征点关系是否相似。在单视频超分辨率重建的配准过程中，由于相邻帧与帧之间的特征点位移不是很大，故它们之间的相似性可以通过几何上的位置关系来表示。故在此采用平面坐标系的欧氏距离来替代128维特征描述子向量空间中的欧氏距离。

2.3 改进配准算法传统配准算法的对比

改进的配准算法与传统配准算法原理上基本一样，主要也是下面几个步骤：(1)特征点的提取；(2)进行初始的匹配；(3)歧义以及误匹配的剔除；(4)计算变换矩阵。其中，改进的配准法主要是在前面3个步骤对传统配准算法进行了改进，而在步骤(4)和传统配置算法一样，都是采用最小二乘法。改进的配准算法与传统配准算法的比较见表1。

表1 改进配准算法和传统配准算法比较

3 实验结果

实验中提取了临近的两帧彩色视频的图像，分别为第70帧和第90帧，并对第90帧的图像进行了一定程度的仿射变换(图1(a)，图1(b))。下面分别采用传统SIFT配准算法与改进SIFT配准方法进行配准实验。检验配准的准确程度采用配准后的灰度图与目标灰度图的图像像素值相减，如果相减后结果的绝对值越小，则配准越准确，当相减结果为0时，也就是说配准前后两幅图像完全一样。

另外，对改进SIFT配准算法和传统SIFT配准算法性能进行了比较。结果证明，改进的配准算法得到的配准结果明显优于传统配准算法，在初始匹配、歧义和误匹配剔除方面都明显占优势，特别是在时间消耗上(表2)。

表2 改进SIFT配准算法和传统SIFT配准算法性能对比

图1 传统SIFT配准和改进SIFT配准实验

4 结论与讨论

传统的基于SIFT特征点检测的配准只是一种通用解决方案，而在单视频的应用场景下，完全可以放弃对128维特征描述子的计算。该算法通过采用特征点之间的灰度相关系数来进行初始匹配，并用平面坐标欧氏距离配合本次研究提出的匹配关联度算法来取代特征描述子进行误匹配的剔除，大大节省了计算时间。通过实验证明，该算法的准确性和效率高等特点弥补了传统算法在单视频超分辨率重建视频的质量方面和实时性方面的不足。

[1] 刘彬，叶丽娜.一种基于SIFT特征的序列图像拼接算法[J].兵工自动化，2009，28(6):76-78.

[2] 周正，雷梦龙，唐少先.基于计算机视觉技术的番茄叶部病害识别研究[J].安徽农业科学，2013，41(5):2 288-2 289.

[3] Beritelli F，Grasso R.A pattern recognition system for environmental sound classification based on MFCCs and neural networks[C]//2nd International Conference on Signal Processing and Communication Systems，ICSPCS 2008，2008：1-4.

[4] 尹洪武，张步英，王静.一类非线性抛物方程的高精度有限元分析[J].河北科技师范学院学报，2013，27(2): 53-56.

[5] K Yan,Sukthankar R.PCA-SIFT:a more distinctive representation for local image descriptors[C]//Proceedings of the 2004 IEEE.Computer Society Conference on Computer Vision and Pattern Recognition,2004:506-513.

[6] 曾文锋，李树山，王江安.基于仿射变换模型的图像配准中的平移、旋转和缩放[J].红外与激光工程，2001，30(1): 18-20，17.

[7] 许录平，姚静.一种图像快速超分辨率复原方法[J].西安电子科技大学学报：自然科学版，2007，34(3): 382-385,408.

[8] 程光权，成礼智.基于小波的方向自适应图像插值[J].电子与信息学报，2009，31(2): 265-269.

[9] 陈建辉，王博亮，徐中佑，等.一种自适应最大相关性数字图像插值算法[J].厦门大学学报：自然科学版，2005，44(3): 355-358.

[10] 林虹.基于小波和插值的超分辨率图像重建算法研究[D].西安：西安电子科技大学，2005.

[11] 申玉发，张晓昱，赵立强.密度K均值聚类算法及在复杂网络分析中的应用[J].河北科技师范学院学报，2013，27(4): 32-36.

The SIFT Registration Algorithm of Super Resolution Reconstruction of Single Video

SUN Wen-hua
(School of Information Engineering,Nanchang Institute of Technology,Nanchang Jiangxi,330099,China)

In view of the traditional single video super-resolution reconstruction based on SIFT feature point detecting registration, we found that holding time on the feature matching is too long to meet the requirements of real-time, and the time calculating 128 d features is the longest, thus, we proposed an improved SIFT registration algorithm, which adapted the gray correlation coefficient between the feature points to do the initial matching instead of using the calculation of 128 d feature descriptor, in order to greatly reduce the computing time and increase the speed of feature matching. The experimental results showed that the algorithm is superior to the traditional configuration algorithm on the registration results and time consumption.

feature point detection;feature matching;SIFT algorithm;super resolution reconstruction

南昌工程学院青年基金项目(项目编号：2012KJ020)；江西省科技厅科技计划项目(项目编号：20141BBE50034)。

2015-06-18

10.3969/J.ISSN.1672-7983.2015.03.014

TP391

A

1672-7983(2015)03-0074-06

孙文华(1981-)，男，硕士，工程师。主要研究方向：计算机网络管理、视频跟踪和图像处理等。

(责任编辑：朱宝昌，杨静)