快速特征提取与感知哈希结合的图像配准算法

宋　博，姜万里，孙　涛，熊正强，芮华建

SONG Bo1,JIANG Wanli2,SUN Tao1,XIONG Zhengqiang1,RUI Huajian1

1.武汉大学 电子信息学院，武汉 430072

2.陆军军官学院，合肥 230031

1.School of Electronics and Information,Wuhan University,Wuhan 430072,China

2.Army OfficerAcademy of PLA,Hefei 230031,China

1　引言

图像特征点配准广泛应用于三维重建、医学制导、图像拼接等领域中，是计算机视觉领域中基础而又重要的课题[1-3]。图像特征点是指能够有效表达图像本质的点，而图像特征点匹配是指在图像中找出有效的匹配点对，进而实现图像配准。图像配准是图像处理领域中的一项关键技术，一直以来很多学者在此方面做了大量的工作，研究的焦点多集中在匹配的准确率和实时性等方面。

基于特征的图像配准方法是利用图像的特征信息实现配准。例如Harris算法，分别在模板图像和待配准图像上，提取Harris角点信息，然后利用相关系数关系，在待匹配图像中搜索出相关性最大的位置，但是这种方法不具有尺度和旋转不变性[4]。2004年，Lowe提出的SIFT（Scale Invariant Feature Transform）算法，通过引入高斯拉普拉斯算子实现了特征点的尺度旋转不变性，进一步实现了图像的自动配准，但是因为算法要遍历整幅图像求解，相应地也增加了运算工作量，不能达到实时性的要求[5]。2006年，Bay等[6]在SIFT算法基础上，提出了SURF（Speeded Up Robust Features）算法，该方法利用Haar小波，计算特征点的主方向，提高了图像配准的速度，但是仍然不能达到实时性的要求。对于纹理信息丰富的图像，Rosten等[7-8]研究了实时性更强的FAST特征检测算法，但是该算法不具备缩放旋转不变性。文献[9]对具有代表性的特征准点算法进行了分析，证明了SURF算法是综合性能最好的算法。2015年，Yang等[10]利用限制SURF算法提高了图像的匹配速度。Lin等[11]在2015年提出利用全局相似变换进行图像配准，提高了图像配准精度，但是在前期特征提取部分仍采用SIFT算法全局处理，没有针对性地改善特征提取过程中计算量较大的问题，实时性不足。雒培磊等[12]基于深度学习的方法对遥感影像进行拼接，虽然通过十字点集的方法提前剔除误匹配点，降低了图像拼接总时间，但是配准过程的时间消耗相比SIFT却略有增加。此外，文献[13-14]采用GPU、多核并行计算等硬件加速的方法实现配准，但是该类方法对硬件要求较高，存在一定的经济成本。

针对特征点匹配中在耗时和精度方面的缺陷，本文对算法进行改进，提出了一种快速图像配准方法。先采用高斯拉普拉斯算子构建边缘稀疏矩阵，之后采用耗时较少的改进后的FAST算法进行特征点的提取，为了提高算法性能，对图像进行高斯拉普拉斯加权从而结合梯度信息求解。此外，采用感知哈希算法对匹配对提纯，在此基础上通过RANSAC算法得到单应性矩阵最优参数后，又依据仿射不变性建立约束条件对单应形矩阵进行校验。实验表明，本文提出的配准方法具有良好的性能。

2　图像快速配准算法

2.1　特征点快速检测提取

2.1.1构建边缘稀疏矩阵

传统的特征检测是对整幅图像进行遍历计算，计算量是m×n（m是图像的高度，n是图像的宽度），会产生大量的特征信息，从而影响图像/视频帧的匹配时间。图像的边缘包含了图像的大部分信息，通过高斯拉普拉斯算子（Laplacian of Gaussian，LoG）检测出图像的边缘区域，然后在边缘区域上进行特征点检测能够极大程度上增加检测特征点的稳定性，同时可以大大降低计算量。另一方面，图像特征的质量，影响着图像的匹配准确率，好的特征点应该具有好的鲁棒性。特征点一般位于一阶导数极大值点，转换为二阶导数，也就是位于二阶导数为零的点。一般直接求一阶导数的极大值比较复杂，而通过求解二阶导数为零的点，可以减少计算量，节省耗时。

本文采用LoG算子来计算局部特征，它是一种二阶导数算子，具有各向同性的边缘检测算子，能对任何方向的线条进行锐化，且不具有方向性，这是高斯拉普拉斯算子最大的优点。对于函数 f(x,y)，在点(x,y)处的拉普拉斯算子如公式（1）所示：

在实际图像边缘检测中，采用如式（2）所示高斯拉普拉斯算子模板M计算梯度值，模板的中心系数为正数，其余的系数为负，所有模板的系数之和为零。

通过高斯拉普拉斯算子求得图像的梯度信息之后，边缘图像中仍然存在着一些梯度值较小的像素点以及因噪声等因素存在的梯度值较大的像素点。这些信息对于特征点的提取会造成干扰，同时导致提取到的特征点数量过多，影响效率。因此，实际中需要设置适当的梯度阈值进行过滤，提取边缘稀疏矩阵。

如图1显示了实际过程梯度阈值的设置流程。首先，根据潜在边缘点的梯度分布直方图得到梯度幅值的递增排列，初始值选取递增方向达到总数80%的边缘点对应的梯度值为高阈值TGmax，低阈值TGmin为高阈值的一半。然后，根据边缘点像素个数占总像素比例对稀疏度进行判断，本文中设置判断参考范围为3%～10%。若未满足要求，则根据浮动阈值ΔT进行微调。实验中，大多数情况下使用初始阈值便可达到稀疏度要求，甚至有些情况直接得到的边缘矩阵已经满足稀疏度条件。

图1　梯度阈值设置示意图

通过边缘稀疏矩阵提取对应的像素信息，剔除了部分弱边缘的像素点，减少了噪声的干扰，同时保留了大部分边缘信息。对于纹理较平坦的图像，因稀疏度判断并不会丢失主要信息；对于纹理丰富的图像，剔除了部分边缘，从而减少计算量，尽管存在部分特征点的丢失，但图像配准过程中理论上只需要四对准确的匹配点对，就可以获得准确的单应性矩阵，在实验过程中，保留的边缘信息中存在足够的准确的匹配点对。

2.1.2优化的FAST特征点检测

FAST是一种角点检测方法，该方法最早是由Edward Rosten和Tom Drummond提出的，该方法最明显的优点是它高效的计算速度。

如图2所示，FAST特征点检测的方法是在以P像素为中心的圆周上按顺时针方向从1到16的顺序对圆周像素点进行编号。根据式（3）所示，如果在圆周上有N个连续的像素的亮度都比圆心像素的亮度lp加上阈值th还要亮，或者比圆心像素的亮度lp减去阈值th还要暗，则圆心像素被称为候选特征点[15]。

图2　FAST特征点检测示意图

目前使用FAST算法可以通过先检测非特征点的像素点来提高检测速度，但是FAST特征点检测算法只考虑了中心像素与圆周上的像素的关系，这导致该方法仅对圆周边缘区域进行特征点检测，并没有结合圆周内部像素点的信息，导致检测的特征点较少以及误检测现象发生。在已通过LoG算子求得梯度信息之后，如式（4）所示，考虑将需要检测的圆心像素I0(x,y)的邻域（圆周内部像素）的梯度信息加权融合至圆心像素以在保持FAST算法稳定性的基础上增加检测特征点的数目。

在式（5）的基础上，使用FAST特征点检测算法对特征点进行提取，当α∗LoG∗I(x,y)＞0时，则说明该待检测点是较亮点，通过梯度加权值变小，则增加了该点比圆周上N个连续的像素点都亮的可能性；当α∗LoG∗I(x,y)＜0时，说明该待检测点是较暗点，通过梯度的加权，值变小，则增加了该点比圆周上N个连续的像素点都暗的可能性。通过在检测过程中加入梯度信息，从而调节了FAST特征点判断的阈值范围，相当于利用梯度信息对候选特征点进一步筛选，使得对图像中存在的阴影、噪声、亮度变化等具有更强的适应能力，可以增加特征点检测数目，使特征点提取更加稳定。

2.2　误匹配对剔除

2.2.1感知哈希算法优化匹配对

特征点匹配的好坏直接影响图像配准的结果，而特征点匹配因阈值、噪声等原因总会存在误匹配点。在计算变换参数之前移除误匹配点，能够提高配准精度，同时降低计算复杂度。本文提出使用均值感知哈希方法[16]提纯匹配点对，该方法以匹配点对为中心，以特征点的主方向为水平方向，提取一定大小的图像块计算得到该特征点的哈希指纹，通过匹配点对哈希指纹的对比验证来判断该匹配点对是否正确匹配。

均值感知哈希利用图像的低频信息计算哈希指纹，相比其他感知哈希算法[17]具有较快的运行速度，通过比较两幅图的哈希指纹就可以判断两幅图像是否相似[18]。哈希指纹一般是在8×8图像大小尺寸下获得的0、1哈希值组合，通过计算比较相同位置哈希值不同的个数，如果不同的个数为0，则这两张图片非常相似，如果这两张图片的哈希距离的不同个数小于5，则这两幅图像相似，否则认为这两幅图像差别很大，不相似。

在获得匹配对之后，对于准确的匹配点对，其所处图像区域也是相似的；对于错误的匹配点对，其所处图像区域是有差异的[19]。根据这一特性，结合感知哈希算法对匹配对进行校验，剔除错误的匹配对，具体的算法流程如下。

步骤1选取特征点邻域尺寸：以特征点的主方向为垂直方向，然后以通过FAST提取的特征点为中心，因为特征点距圆周边缘的最小尺寸为3，为了更好地保留边缘特征点，所以选取7×7的正方形作为感知哈希校验区域。

步骤2简化色彩：将步骤1中获得7×7图像转换为7×7灰度图像。

步骤3计算像素灰度平均值：计算步骤2中得到的7×7灰度图像的49个像素的灰度平均值。

步骤4比较像素灰度值：将步骤2得到的7×7灰度图像的每个像素与步骤3中得到的7×7灰度图像的灰度平均值进行比较，大于平均值的记为1，小于平均值的记为0。

步骤5计算哈希值：将步骤4中得到的49个0、1按固定的顺序组合起来，这样就得到了该以特征点为中心的哈希指纹。

步骤6匹配点提纯：通过比较步骤5中获得的哈希指纹，统计49个相同位置的值的不同的个数，如果不同的个数小于5，则认为这对匹配点对是正确匹配的，否则不是正确的匹配点对。

如图3（a）所示，在SURF描述符下使用FAST算法得到的匹配点对，此时未使用感知哈希验证，可以看到图中存在数对误匹配对。图3（b）为按照上述误匹配剔除算法对图3（a）中匹配点对进行提纯，可以看到图3（a）中原来存在的误匹配对已全部被剔除。

图3　图像匹配点对感知哈希算法验证前后对比

在对匹配对进行提纯之后，使用RANSAC算法来进行迭代寻找最佳的单应性矩阵。因为经过一次提纯，剔除了错误的匹配对，减少了样本数据集中的无效数据，使得在匹配点数据集中迭代寻找最优参数矩阵更加高效。

2.2.2单应性矩阵准确性校验

在视频图像匹配中，经过前述步骤并不能判断图像是否正确匹配。Lin等[20]曾在2016年利用改进的Seamdriven并且加入了曲线和直线结构保持约束，进一步提高了图像配准精度。本文根据图像的仿射变换的特性，提出了相应的约束条件进行校验，进而去除干扰图像。

平面图像的仿射变换应具有以下特性：共线线段单比不变性、直线的平行性[21]。已知四点 Pi(xi,yi)(i=1,2,3,4)，且其中直线P1P2与直线P3P4平行，那么经过仿射变换后

由直线的平行性可得：

因直线P1P2与直线P3P4平行，故经过仿射变换后理论上也是平行的，但是在实际中总会存在一定误差，式（6）中β是变换后两平行线斜率差的阈值。

由共线线段单比不变性可得：

通过式（6）、（7）所示约束条件，对所得单应性矩阵准确性进行校验，不满足阈值约束条件的结果被判定为错误的配准结果。

3　实验分析

实验平台硬件环境：Intel®Core™ i5 2.50 GHz CPU，4 GB RAM；软件环境：Windows 7旗舰版系统，Microsoft Visual Studio 2010，Visual C++，Open_CV_VERSION 2.4.8。默认采用的梯度阈值TGmin=20，TGmax=40，FAST特征点选取阈值th=30，仿射不变性阈值β=γ=0.2，拉普拉斯加权系数α=0.075，汉明阈值为2倍的最小距离。在实际不同的场景中，提取的特征点数量存在差异，实验中特征点的提取数量范围设定为80～120。

（1）仿射不变性校验

为验证本文所提仿射不变性约束条件在匹配过程中的有效性，对不同算法在匹配图像中存在和不存在目标物体（课本）情况下的匹配结果进行对比分析。

如图4所示，第一行是SIFT算法处理结果，第二行是SURF算法处理结果，第三行是ORB算法处理结果，第四行是本文算法处理结果。第一列是SIFT、SURF、ORB和本文算法分别对含有目标物体（课本）图像匹配的结果，可以看出都能很好地匹配到目标，SIFT和SURF算法匹配到的特征点较多，但存在的误匹配对也较多，ORB和本文算法匹配对较少；第二列匹配图像中不存在目标物体情况下四种算法的匹配结果，可以看到SIFT、SURF、ORB方法均匹配到了大量的匹配点对，本文算法也存在少量的匹配对，但是实际并不存在目标。第三列图像为四种方法在第二列图像匹配基础上标记出的匹配结果，可以看到只有本文算法最终未标记出目标物体匹配结果，这是因为本文算法利用图像变换的仿射不变性，对匹配结果进行判断处理后的结果，可以看出，算法能够在不存在目标时，很好地纠正误匹配结果。

图4　匹配图像中存在和不存在目标物状态下SIFT、SURF、ORB及本文算法的特征点匹配结果

（2）缩放、旋转和噪声匹配性能分析

为检验本文算法的缩放、旋转和噪声匹配性能，选择标准Lena图像（512×512）为参考图像，以存在缩放旋转的高斯噪声Lena图像为待匹配图像，其获取方法为：对标准Lena图像，加高斯白噪声，然后对图像进行横向4/5，纵向6/5的缩放，然后顺时针旋转35°。将本文算法与SIFT、SURF、ORB算法进行匹配性能比较。实际实验过程中，避免匹配过程特征点数过多，对图像进行一次下采样处理，以便后续计算。另外，SIFT、SURF、ORB算法匹配对提取最优匹配点时采用的汉明距离阈值是2.5倍的最小距离。

图5为在前述缩放、旋转和噪声情况下，几种算法的特征点匹配结果对比。图5（a）为SIFT算法匹配结果，41个匹配对中有3对误匹配，误匹配率约为7.32%；图5（b）为SURF算法匹配结果，32个匹配对中，有16对误匹配，误匹配率为50%；图5（c）为ORB算法匹配结果，31个匹配对中，有1个误匹配对，误匹配率约为3.23%；图5（d）为本文算法匹配结果，在32个匹配对中，有4对误匹配，误匹配率约为12.5%。从仿真实验结果来看，在图像存在噪声、缩放和旋转的情况下，ORB、SIFT和本文算法都表现出很强的鲁棒性，SURF性能最差。

如图6所示，使用所提算法对不同场景下实际拍摄图像进行实验验证结果，图像中方框标记出为匹配出的目标物体（课本）。第一行为待匹配图像由大到小情况下的缩放匹配结果；第二行为待匹配图像在不同旋转角度情况下的匹配结果；第三行是待匹配图像不同投影变换下的匹配结果；第四行为待匹配图像在被部分遮挡情况下的匹配结果；第五行为待匹配图像在光照条件从暗至亮发生变化情况下的匹配结果。从实验结果中可以看出本文算法在图像存在一定缩放、旋转、投影变换、遮挡和光照变化的情况下，都能够很好地实现图像的匹配，具有很好的鲁棒性，而且在经过感知哈希与仿射不变性的进一步校验之后，具有很少的误判断。

图5　本文算法与经典算法Lena图像特征点匹配结果对比

图6　不同场景下实拍图像本文算法特征点匹配结果

（3）运行效率分析

为检验算法的运行效率，选择标准Lena图像（512×512）进行特征描述仿真实验，将本文算法结果与SIFT、SURF、ORB算法结果进行对比分析。得到四种算法的特征点提取具体耗时如表1所示，表中时间均为连续处理10次之后的平均值。

由表1中对单个特征点描述所用时间的平均值可知，本文算法速度最快，约是SIFT算法耗时的1/160，约是SURF算法耗时的1/75，约是ORB算法的1/14。从总耗时来看ORB算法耗时最短，主要原因是本文算法为解决FAST算法下某些特征点难以提取的问题，利用高斯拉普拉斯算子加权从而增加了FAST算法检测的特征点数。

表1　本文算法与经典算法性能比较

如图7为一段视频序列图像中没有目标、出现目标、目标消失过程中本文方法连续运行耗时曲线。两条垂直标记线分别表示目标49帧开始出现及97帧目标消失，标记线之间表示在目标出现在视频期间利用本文算法对目标进行匹配的耗时，其他区间为无目标时处理耗时。在49～97帧出现目标时，单帧处理最大耗时为50 ms，而整个区间变化稳定在30～40 ms，在无目标匹配过程中，单帧处理耗时基本稳定在20～30 ms。在曲线中出现峰值，产生的原因可能有两个：（1）视频中出现噪声，造成图像稀疏矩阵中非零个数增加，增加了计算量；（2）可能是算法中梯度阈值、FAST特征阈值的更新或高斯拉普拉斯算子的加权系数的更新，增加了计算量。但是总体上看，本文算法的处理速度整体小于50 ms/帧，具有良好的实时性以及鲁棒性。

图7　视频序列图像匹配耗时变化曲线

（4）图像配准结果分析

为验证本文算法整体性能，对无人机航拍得到的实际序列图像进行了实验验证，其中，无人机航拍序列图像第60帧和96帧配准结果如图8所示。在图8中，暗度较低的部分是第60帧图像经过降低亮度显示的结果，亮度较高的是第96帧图像，这样处理是为了方便对图像的配准结果进行分析比较，图中箭头标记序号为配准结果比对位置。图8（a）是利用SIFT算法进行配准的结果，可以看出利用SIFT算法进行配准的结果在1和2处的线性区域具有一定的错位，在3处房子明显出现了错位。图8（b）是利用SURF算法进行配准的结果，可以看出SURF算法在1处具有较好的配准效果，在2处公路的行车线则出现错位，在3处出现了明显的错位，4处甚至都出现明显的误配准。图8（c）是利用本文算法进行配准的结果，可以看出本文算法最终在3处配准比对位置的配准结果都具有较好的直观效果，没有出现因误匹配导致的变形和错位现象。实验结果表明，本文提出的算法在配准精度上要优于SIFT和SURF算法。

图8　本文算法与SIFT、SURF算法图像配准结果对比

4　结束语

针对经典的特征点算法是从整个图像进行遍历来确定特征点的问题，本文提出了一种先建立图像边缘稀疏矩阵，在其基础上利用改进的FAST算法快速提取特征点，再通过SURF描述符为特征点构建描述向量。获得匹配点对后，利用均值感知哈希算法对匹配点对提纯，之后再使用RANSAC算法寻找最优参数矩阵，并结合仿射不变性对单应性矩阵进行校验，提高图像配准准确度。实验结果表明，本文算法具有很好的配准精确性、时效性以及鲁棒性。

参考文献：

[1]Burger W，Burge M J.Digital image processing：An algorithmic introduction using Java[M].Berlin：Springer，2016.

[2]Oliveira F P M，Tavares J M R S.Medical image regis-tration：A review[J].Computer Methods in Biomechanics and Biomedical Engineering，2014，17（2）：73-93.

[3]Adel E，Elmogy M，Elbakry H.Image stitching based on feature extraction techniques：A survey[J].International Journal of Computer Applications，2014，99（6）：1-8.

[4]Harris C.A combined corner and edge detector[C]//Proc of Alvey Vision Conf，1988：147-151.

[5]Lowe D G.Distinctive image features from scale-invariant keypoints[C]//International Journal of Computer Vision，2004，60（2）：91-110.

[6]Bay H，Tuytelaars T，Van Gool L.Surf：Speeded up robust features[C]/Proceedings of European Conference on Computer Vision（ECCV 2006），2006：404-417.

[7]Rosten E，Drummond T.Machine Learning for High-Speed Corner Detection[C]//Proceedings of European Conference on Computer Vision，2006：430-443.

[8]Rosten E，Porter R，Drummond T.Faster and better：A machine learning approach to corner detection[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2010，32：105-119.

[9]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors[J].IEEE Trans on Pattern Aralysis&Machine Intelligence，2005，27（10）：1615-1630.

[10]Yang K.Missile placement analysis based on improved SURF feature matching algorithm[C]//Proceedings of International Conference on Graphic and Image Processing，2015.

[11]Lin C C，Pankanti S U，Ramamurthy K N，et al.Adaptive as-natural-as-possible image stitching[C]//Proceedings of International Conference on Computer Vision and Pattern Recognition，2015：1155-1163.

[12]雒培磊，李国庆，曾怡.一种改进的基于深度学习的遥感影像拼接方法[J].计算机工程与应用，2017，53（20）：180-186.

[13]Daga P，Chadebecq F，Shakir D C S，et al.Real-time mosaicing of fetoscopic videos using SIFT[C]//Proceedings of SPIE Medical Imaging，2016.

[14]曹国刚，张晴，张培君，等.基于多核并行化差异进化算法的图像配准方法[J].计算机工程与应用，2017，53（20）：166-172.

[15]安维胜，余让明，伍玉铃.基于FAST和SURF的图像配准算法[J].计算机工程，2015，41（10）：232-235.

[16]Haviana S F C，Kurniadi D.Average hashing for perceptual image similarity in mobile phone application[J].Journal of Telematics and Informatics，2016，4（1）：12-18.

[17]Niu X M，Jiao Y H.Overview of perceptual hashing[J].Acta Electronica Sinica，2008，36（7）：1405-1411.

[18]丁凯孟，朱长青，卢付强.基于自适应格网划分的遥感影像感知哈希认证算法[J].武汉大学学报：信息科学版，2015，40（6）：716-720.

[19]Jaewook J，Gunho S，Bang K，et al.Matching aerial images to 3D building models using context-based geometric hashing[J].Sensors，2016，16（6）：932.

[20]Lin K，Jiang N，Cheong L F，et al.SEAGULL：Seamguidedlocalalignmentforparallax-tolerantimage stitching[C]//ProceedingsofEuropeanConferenceon Computer Vision（ECCV 2016），2016.

[21]Demir B，Bruzzone L.Hashing-based scalable remote sensing image search and retrieval in large archives[J].IEEE Transactions on Geoscience&Remote Sensing，2016，54（2）：892-904.