基于SIFT-BP的图像配准算法

高 华，曹 锋，陈明星

(重庆交通大学，重庆 400074)

图像配准技术是图像处理的重要分支，其目的是对不同时间、不同传感器或者不同视角的2张或2张以上的图像进行匹配。该技术广泛应用于机器视觉、遥感图像、医学影像、三维重构等。图像的配准一般采用基于区域或基于特征［1－3］。基于区域的配准方法要先比较区域内的各个像素点，然后建立图像之间的变换模型参数，因此其计算量大，配准时间长。如果图像存在缩放旋转或扭曲，就会影响图像配准的精确性，进而影响到后续工作的处理。基于特征的图像配准方法因其配准速度快、精度高、鲁棒性好而成为研究热点。

基于特征的配准算法主要有角点匹配算法、SIFT特征［4］提取算法、SURF特征提取算法等。角点提取虽具有旋转不变性，但是对于尺度变化较大的图像无法保持特征的不变性;SIFT特征是图像的局部特征，不仅对旋转、尺度缩放、亮度变化可以保持不变性，而且对视角变化、仿射变换、噪声也具有一定程度的稳定性［5］。

但是，传统的SIFT算法仅考虑了特征点的描述子信息，完全忽略了特征点描述符之间的几何信息。本文对参考图像和映射图像中离散的关键点应用BP算法，将关键点的相似度融入到消息传递过程中，以迭代算法计算对应关键点，不但利用了关键点的局部信息，而且保持了映射图像中关键点间的空间约束。

1 SIFT特征检测与匹配

1.1 特征检测

SIFT算法特征点的检测基于尺度空间理论。二维图像的尺度空间定义为

其中:G(x，y，δ)是二维高斯函数;δ为尺度空间因子;(x，y)表示图像的像素位置。

为了在尺度空间检测到有效的关键点，提出用不同的高斯差分核分别与图像进行卷积生成高斯差分尺度空间:

DoG算子计算简单，是归一化LoG算子的近似。

利用SIFT算法构造DOG金字塔时通过相邻尺度空间函数相减即可。在形成的尺度空间中的3×3×3的空域和尺度域结合的邻域里进行非最大值抑制。一个点如果在尺度空间本层以及上下26个邻域中值是最大或最小时，才可认为是特征点。通过拟合3维2次函数精确确定特征点的位置和尺度，同时去除对比度低的特征点和不稳定的边缘响应点。

1.2 特征点描述

1.2.1 确定特征点主方向

为了使关键点具备旋转不变性，利用关键点邻域像素的梯度方向的分布特性为每个关键点指定方向参数:以特征点为中心，在邻域窗口内采样，用梯度方向直方图统计邻域像素的梯度方向，峰值代表特征点处邻域梯度的主方向，即为特征点的主方向，如果存在相当于主峰值80%能量的峰值时，则作为特征点的辅方向。因此，一个特征点可能会有1个主方向和1个以上的辅方向，这可以增强匹配的鲁棒性。

1.2.2 构建描述子

首先将坐标轴旋转为关键点的方向，以确保旋转不变性，然后将以关键点为中心的8×8的窗口分成16个2×2的小块，并计算各小块内8个方向的梯度方向直方图再进行累加，形成一个种子点，。每个种子点对应8个方向的向量信息，则每个关键点就对应16×8=128维的向量。

1.2.3 SIFT 特征向量的匹配

Lowe提出的SIFT算法采用欧式距离作为两幅图像间的相似性度量，即如果最近的距离除以次近的距离少于某个比例阈值，则认可该匹配点是对的。

其中:D1(i)、D2(j)分别为参考图和映射图中的第i个和第j个特征向量;T为不依赖于图像的常量。

1.3 改进的SIFT匹配算法

尽管SIFT算法可以提取图像独特的特征，但是最近欧氏距离决定了它只是一种局部优化的方法，完全忽略了不同的特征描述符之间的几何信息。这造成的后果就是本应映射在参考图描述符附近的映射图描述符距离可能很远。为此本研究作一个全局优化匹配并且定义一个补偿函数φ(m)，表示参考从一个关键点到另一个关键点的距离和映射图对应关键点之间的距离的差异总和，如式(4)所示。

其中:ID1是原始图像的描述符集;m(·)是映射图中相应于参考图的映射描述符指数。因此，可按式(6)～(8)解决全局优化问题:

但是，式(6)不是凸函数并且带有复杂的指数，这样，经过式(3)计算后会丢弃一些关键点，但剩下的关键点的数量通常仍然会超过100。因此，一次彻底的搜索将需要100!步，显然是难以计算的。此外，在这么早的阶段应用式(6)也可能会不必要地丢弃有用的信息，并且式(6)有可能在存在不满足这个条件下的匹配的情况下出现错误。

为此，本文提出使用信任度扩散算法(belief propagation)［7］解决式(6)出现的问题。BP算法广泛地应用于信号处理应用中［8－9］，它的优点就是目标函数的凹凸性不受限制，其主要思想是消息的迭代传输。首先，将整个优化问题分解成若干较简单的局部问题。在每次迭代过程中，每个局部问题尝试估计下一个将要进行的优化问题的最优解。相邻的2个局部优化问题将交换信任度。每一个局部优化问题的信任度将会纳入下一次迭代计算信任度的过程中。当进行到一个固定的预定义的迭代数量或者所有的局部优化问题在收敛在一个最有可能的解时，算法停止。

由于即使提出的目标函数呈指数增长，优化问题也不会发生改变，因此式(6)可改为

并且 CDes/CDist= ε。bDesi(mi)和 bDisti，j(mi，mj)可以分别近似看作映射图中给定的第mi个关键点的描述符信息所匹配的参考图中第i个关键点的信任度和第mj个关键点相匹配的第j个关键点的信息。

此时本文的优化问题转化为式(10)，但是，它并没有使优化问题变得更易于处理。因此，把优化问题简化一点，对于相互接近的关键点，使优化函数只包含 bDisti，j，在邻域(假设 j∈N(i) ⊂ID1，并且，优化问题可以近似使用最大积BP 算法［10］解决。此时，

如果网络图是一棵树，最大积BP算法收敛到全局最优。在一般情况下，该算法不是最理想的，但是在许多应用中却依然工作良好［9］。定义为关键点i的信任度，关键点j在第n次迭代的正确匹配为mj。在每次迭代过程中，消息从关键点i传输到关键点j。改进算法描述如下:

2)当 i∈ID1时，利用式(14)迭代更新消息

3)计算每个节点的信任度:

4)令n=n+1，转至步骤2)。当n达到最大迭代次数时，算法结束。

1.4 求解图像间的投影变换关系

假设2幅图像满足以下投影变换关系

表示成向量形式为kXi=HX'i，单应性矩阵H的自由度为8，因此需要4对匹配点就可计算出H。

2 实验分析

本文实验操作系统为Window XP，内存为2G，编程环境是Visual 2008，OpenCV2.1。选取图1作为待配准的原始图像，分别用Lowe的传统SIFT配准算法和本文的改进算法对图1进行配准，配准结果如图2所示。观察可知，在传统配准算法中有一些匹配的错误，特别是原始图像的关键点都相当接近，然而原SIFT匹配算法基本上忽略了这些信息并且去匹配了远离该关键点的其他关键点中的一个，本文提出的BP算法却试图保持关键点的距离不变。在传统算法中，上下图像分别包含了306279个特征点，有效匹配点对数为65。使用改进的匹配算法后，上下图像分别提取了284252个特征点，有效匹配点对数为78。可见与传统算法相比，改进的算法提高了提取特征点位置的精确度与匹配的准确性。本文CDes被设置成40000，CDist设置为 550。

图3 改进算法配准效果

3 结束语

本文实现了基于BP的SIFT特征点的改进的图像配准算法。在图像配准的过程中，对于传统SIFT算法忽略特征点的位置信息等，提出了利用信任度扩散算法求解关键点之间的匹配关系，将关键点的相似度融入到消息传递过程中，以迭代的方法计算对应点，最后利用投影变换矩阵对之进行匹配。在配准的过程中，改进算法比传统的方法有了显著的改善，不但减少了误匹配点，降低了误匹配率，而且与原始算法相比，能够找出更多的匹配点，增强了定位的鲁棒性。

［1］赵向阳，杜利民.一种全自动稳健的图像拼接融合算法［J］.中国图象图形学报，2004，9(4):417 －422.

［2］关晓菊，周激流，何坤.基于方向能量的灰度图像边缘检测［J］.激光杂志，2010，31(2):14 －16.

［3］范永辉，王刚，曲文娟.基于小波域分类隐马尔可夫树模型的图像融合算法研究［J］.激光杂志，2009，30(5):32－34.

［4］Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91 －110.

［5］YANG HENG，WANG QING.A novel local feature descriptor for image matching［Z］//IEEE International Conference on Multimedia and Expo.［S.l.］:［s.n.］，2008:1405－1408.

［6］Fischler M A，Bolles R C.Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image A-nalysis and Automated Cartography［J］.Communications of ACM，1981，24(6):381 －395.

［7］Pearl J.Probabilistic reasoning in intelligent systems:networks of plausible inference［M］.San Francisco:Morgan Kau Fmann Publishers Inc，1988.

［8］Kschischang F，Frey B，Loeliger H.Factor graphs and the sum-product algorithm［J］.IEEE Trans Inform Theory，2001，47:498 －519.

［9］Sun J，Zheng N N，Shum H Y.Stereo matching using belief propagation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(7):787 －800.

［10］MacKay D.Information Theory，Inference，and Learning Algorithms［M］.Cambridge:［s.n.］，2003.