改进ORB特征点检测的图像拼接方法

秦绪佳，陈国富，王洋洋，张美玉

(浙江工业大学 计算机科学与技术学院，杭州 310032)

1 引 言

图像拼接是通过配准、变换和融合等方式把多张有重叠部分的图像处理后成一张广角清晰的图像[1].遥感图像拼接技术有多的应用，在自然保护、灾害勘察、军事勘察等方面遥感图像都有应用.图像配准方法一般分为两种类型，基于频域方法和基于时域方法.基于频域的方法是1975年Hines和Kuglin提出的相位相关法，此方法大多应用于遥感图像拼接方面.在图像拼接过程中，先进行快速傅立叶变换，将两张图像变换至频域，然后根据两张图像间的互功率谱获得平移矢量，最后根据平移矢量实现图像配准[2].基于时域的方法又可以进一步分成两种类型，基于特征的方法和基于区域的方法.基于区域的方法由于计算量非常大，所以算法较少.当前图像拼接算法大部分都是基于特征的方法，该类方法先提取图像中特征点.分析图像特征点，计算两张图像特征点的匹配关系，通过特征点的位置关系来计算两张图像的变换关系[3]，最后根据变换关系实现图像的拼接.基于特征的方法在计算中不需要用到图像的颜色信息，因此对于图像光线的变换有较好的鲁棒性，并且还有计算量小，拼接速度快的优点.

常见的提取图像特征点方法有：Harris、FAST，SIFT，SURF和ORB等.Ethan[4]等人在2011年提出的ORB算法，ORB算法的运算速度是SIFT算法的100倍，是SURF算法的10倍[5].ORB(Oriented FAST and Rotated BRIEF)是一种特征点提取和描述的算法.由Edward等人在2006年提出FAST角点检测方法，算法计算速度快，精确度也高.Michael等人[6]在2010提出一种特征描述子BRIEF.BRIEF特征描述子是一种二进制编码描述子，可以更快建立特征描述子，减少特征匹配时间.Yi等人[7]提出了一种量子特征点提取方法.Wang等人[8]提出了一种基于基于SIFT的匹配算法GeoMatch，能够进行快速的特征匹配.FAN等人[9]提出了一种改进ORB算法，在特征点检测过程中设置了自适应阈值，提高了匹配质量，降低了计算成本.

本文提出了一种改进FAST特征点检测的方法，优化检测过程，减少周围像素点比较次数，更快速的选择特征点，还可以减少选择噪点的数量.本文还改进了RANSAC算法，在计算变换矩阵的过程中，添加了合适的样本，提高了内点占比.提高了计算效率，降低了迭代次数.最后通过泊松融合可以实现高效，实时，准确的图像拼接.

2 改进的ORB特征点检测方法

ORB(Oriented FAST and Rotated BRIEF)是一种特征点提取和描述的算法.ORB算法是通过对每个像素点附近的16个像素进行比较判断，效率较差.而且提取的点中常常会包含很多边缘点与噪点，为了除去这些无效的噪点，本文提出了通过提取周边点的方法来减少无效噪点的干扰.

2.1 ORB特征点检测与描述

ORB算法由两部分Oriented FAST 和 Rotated BRIEF构成.Oriented FAST即特征提取是由FAST算法发展而来，Rotated BRIEF即特征点描述是由BRIEF特征描述算法改进得到.FAST角点检测方法[10]是比较像素点与周围像素点的像素差，当像素差大于阈值就判定该像素点为角点(特征点).FAST检测角点仅仅只是对比像素值，因此角点并不具备方向性和旋转不变性.ORB算法提出了一种利用灰度质心法来确定角点方向，解决了角点不具备方向性的问题.角点的灰度值与质心的灰度值不一致时，角点坐标到质心构成一个向量作为该角点的主方向.矩的元素表达为：

(1)

其中的p，q确定灰度的阶数，I(x，y)是像素点(x，y)的像素值.

图像块的质心C为：

(2)

图像块角点中心到质心的方向就是特征点的方向，计算公式为：

θ=arctan(m01，m10)

(3)

BRIEF算法是利用二进制串的特征描述符描述特征点.二值判断方法为：

(4)

p(x)是指图像块p在点x处的像素值.

BRIEF算法对噪声较为敏感，ORB算法通过像素平均值来替代某点的像素值来增强抗噪性.二进制串的计算公式如下：

(5)

BRIEF算法得到的描述子是不具有旋转不变性，ORB算法把公式(3)FAST中求出的特征点方向当作BRIEF的主方向.对每个特征点处，产生的n对随机，即2*n的矩阵M：

(6)

并用旋转矩阵R(特征点方向θ)进行旋转变换，使其变为有向形式：

(7)

旋转变换公式为：Sθ=RθM.BRIEF特征描述子的最终结果为：

gn(P，θ)=fn(P)|(xi，yi)∈Sθ

(8)

2.2 提取周边像素点的方式

针对ORB算法判断特征点的方式会产生较多的边缘点与噪点[11]的问题提出一种改进，在比较某点的周边像素时，重新选边缘点进行二次比较，用多次比较的方法大大减少噪点的干扰.

对图像进行预处理得到二进制信息.特征点中心灰度值设作1，低于中心灰度值设作0.点p的灰度值与附近点x灰度值的比较关系有3种情况，如公式(9)所示.

(9)

ORB提取特征点的方法如图1所示，以点P的3个像素半径做圆，选择圆边缘上的16个像素点.

图1 选择周围像素点Fig.1 Select surrounding pixels

ORB算法判断特征点的方法：对圆上的灰度值进行分类.如设点P的灰度值为1，图1中圈右侧像素点6的灰度值比点P低，则点6灰度值为0.图1中圈左侧像素点14灰度值比P相近.则点14灰度值为1.在对灰度值进行分类后，如果圈上有9个以上连续像素暗于或亮于P，则判断P为特征点.

2.3 快速判断特征点的方式

ORB算法提取特征点，每次都要将中心点对比周边16个像素点的灰度值，才能确定该点是否是特征点，效率十分低下.针对该问题，本文提出了一种快速判断图像特征点的改进方法.

图2 选取4个固定周边点Fig.2 Select 4 fixed perimeter points

根据ORB算法判断特征点的特点，有9个以上连续像素暗于或亮于P，则判断P为特征点.即测试了候选点周围每隔90度角的4个点，应该至少有3个和候选点的灰度值差足够大.为了计算方便，选取为P点中心十字线上的4个点ABCD.比如AC高于P点，而BD又低于P点，那么P点一定是噪点.

从比较16个点到比较4个点效率是大大提高了，但是得到噪点的几率就大了很多.提出了新的一种采样法减少噪声.以点P的5个像素半径做圆，PA，PB，PC，PD做延长线落在外圆上，得到相应的WXYZ 4个点.

图3 选取8个周边点Fig.3 Select 8 fixed perimeter points

假设点P是特征点，那么点P与周边像素点的灰度值就一定会存在差值，并且周边像素点在灰度值上会保持对应的延展性.即当内圈像素点A的灰度值比中心点P低时，则外圈对应像素点W的灰度值也要比P低，这样保持了连贯性.若W的灰度值也要比P高，则P点便是噪点.

本文提出了一种新的判断特征点方法，不需要每次对16个像素点进行比较，仅需要比较8次，大大减少了比较次数，提高了特征点提取效率.还利用特征点延展性，更准确地分类噪点或是特征点.

3 改进的RANSAC算法

采用基于K最近邻近算法[12]快速对特征点进行匹配，结果会有大量的错误.基于欧式距离对特征点进行粗匹配，也会存在许多误匹配.就需要通过RANSAC算法进行提纯，并求得变换矩阵.RANSAC算法的迭代总次数是根据内点比例动态变化的.内点占比例越高，就能越快计算出参数模型估计，迭代次数也就越少.

3.1 RANSAC算法

RANSAC算法的主要过程如下：

1)P表示算法产生有用结果的概率即在一些迭代过程中从数据集中随机选中的点均为内点的概率.用w来表示每次从数据集中选取一个局内点的概率.最小数据量为n.迭代次数为k.((1-w)n)k表示不会选择到n个点都是内点的概率，结果与1-P相同.因此：

((1-w)n)k=1-P

(10)

2)在初始样本中随机选取4对匹配点(要求四点不得共线)，并计算得到变换矩阵T.

3)通过变换矩阵T来计算剩余特征点对间的欧式距离d.

4)判断欧式距离d是否小于设定阈值，若小于即为内点，大于为外点.记录内点的数目count.

5)重复步骤2-步骤4，当重复到设定迭代次数或内点数目count达到最大值且数值稳定不变时，即得到最佳的变换矩阵T.

RANSAC算法根据置信概率P、匹配总数、当前内点个数及当前迭代次数动态的改变迭代总次数[13].当内点占比w高时，便可迅速找到正确估计，迭代次数可以大幅减少，还是以指数级减少的时，最终的迭代次数几十次即可.

3.2 改进RANSAC算法

本文对RANSAC算法提出一种改进，在迭代结束前，在样本中重新添加新的特征点.添加新的特征点步骤如下：

Step 1.得到一个相对准确的变换矩阵T.在计算变换矩阵过程中，迭代次数达到10次后或者内点数目趋于稳定，就认为该变换矩阵T相对准确.

Step 2.添加新特征点.在一次迭代过程中从内点集合中随机选择两对匹配点，从基准图像中这两点的延长线上随机选取一点a.通过变换矩阵T计算出点a在待匹配图像中的位置b.

Step 3.验证新特征点.若位置b在待匹配图像中两点的延长线，或者偏移非常小，就把点a点b作为新特征点对并放在内点集合中，否则就重新选择特征点.

Step 4.在每次迭代过程中，只添加3对特征点，添加太多会反而会导致总迭代次数过大.重复第2步、第3步，直到内点数目稳定或达到迭代次数，就停止添加特征点.

增加的新特征点，是用内点做延长线得到，保证每次都在重叠区域选择点，而且通过验证保证了新特征点是准确性.通过这种方式提高内点占比，提高RANSAC效率，减少迭代次数.

本文提出了一种改进RANSAC算法，通过不断增加内点的方式，不仅提升了效率，还可以计算得到更合适的变换矩阵.

3.3 泊松融合

由于图像拍摄的角度、特征点匹配的精度、仿射变换误差等问题，都会造成拼接出现痕迹.这就需要图像融合技术去除拼接过程中产生的重影和间隙.图像融合常用的方法：加权求和、小波融合、平均图像融合等.本文则采用泊松融合[14]，泊松融合的核心是通过插值重构融合区域的像素，同时能保证梯度域上的连续.融合步骤如下：

Step 1.通过变换矩阵找到两张图像的交界处，若有拼接痕迹，一定发生于交界处.依据交界处坐标从待匹配图像中选择一块图像c，将图像c融合到有拼接痕迹的地方.利用差分运算计算出图像c的梯度场.

Step 2.计算拼接图像的梯度场，拼接痕迹的区域可以不用计算梯度场.因为融合的时候，拼接痕迹区域的梯度场就是图像c的梯度场，这样可以减少一部分计算量.

Step 3.计算融合图像的梯度场.步骤2得到的是拼接图像的梯度场，把待融合图像c的梯度场赋值于拼接图像对应区域梯度场.得到一个待重建的完整梯度场.

Step 4.计算融合图像的散度.对步骤3得到的待重建梯度场，对梯度求偏导，计算得到融合图像的散度.

Step 5.计算系数矩阵.泊松重建方程Ax=b，b为图像散度，x是融合图像的像素值.只要构建系数矩阵A就能进行融合图像.

图4 图像泊松融合结果对比Fig.4 Comparison of image Poisson blend results

泊松融合的关键就在于重建方程Ax=b.利用方程计算得到图像的每一个像素值，进而融合图像.图4中左图是有拼接痕迹的图像(矩形标出拼接痕迹)，右图是泊松融合后的结果.对比左右两图矩形区域，可以明显发现右图更加自然.

4 实验与结果分析

实验硬件环境为：Windows10操作系统，Intel Corei5-7600 CPU @ 3.5GHz处理器.实验数据为遥感图像.本文实验对比本文算法与其他角点检测算法，再通过比较特征点提取时间及准确度，验证本文算法的优越性.用改进的RANSAC算法对比原RANSAC算法，验证本文改进的算法计算效率是否提高.最后展示本文算法的图像拼接结果.

4.1 特征点匹配实验对比

用4种图像特征点提取算法，各提取1000对、5000对特征点，实验结果求平均值后如表1所示.把图像边缘5像素之内的点定义为边缘点，边缘点大概率是噪点.提取特征点所消耗的时间与提取特征点的数量呈正相关.从表1中可以发现，ORB算法提取特征点的速度最快，但提取的边缘点最多.使用本文改进的ORB算法在5000对特征点时速度反超原ORB算法，速度最快而且还大大减少了边缘点的数量.

表1 不同算法提取特征点
Table 1 Extracting feature points with different algorithms

算法名称1000对特征点耗时边缘点5000对特征点耗时边缘点SIFT算法3562ms4.11%16895ms4.21%SURF算法1549ms6.14%8323ms5.67%ORB算法169ms7.68%924ms6.92%本文算法183ms2.41%870ms2.38%

用ORB算法与本文改进的ORB算法进行实验对比.对3组遥感图像进行特征点的匹配，绘制后结果如图5所示.其中图5(a)、图5(c)、图5(e)为ORB算法得到的匹配结果，图5(b)、图5(d)、图5(f)为本文改进的ORB算法得到的匹配结果.

图5 ORB算法与改进后的ORB算法特征点匹配结果对比Fig.5 ORB algorithm is compared with the improved ORB algorithm feature point matching results

从图5中我们可以明显发现，图5(a)、图5(c)、图5(e)画框标注部分的线段交叉，多于对应的图5(b)、图5(d)、图5(f).通过实验我们可以得出改进后的ORB不仅提升了算法效率，也提高了匹配的正确率.

4.2 拼接结果对比

对比RANSAC算法与改进的RANSAC算法，在不同特征点对数和特征点匹配对数下的效率情况.从表2中可以发现，本文提出的改进RANSAC算法中内点占比高于原RANSAC算法，所以耗时也更少.可以说明本文改进RANSAC算法提高了效率，能更快得计算出变换矩阵.

表2 与RANSAC的对比实验结果
Table 2 Comparison of experimental results with RANSAC

特征点对数特征点匹配RANSAC算法内点占比耗时本文算法内点占比耗时500对100对85.6%21.6ms92.1%19ms1000对200对87.8%23.5ms91.6%22ms5000对1000对86.7%30.7ms91.2%24ms10000对1500对87.3%35.8ms89.8%23.4ms

为验证改进算法计算变换矩阵的准确性，用RANSAC算法与本文算法进行对比，对比结果如图6所示.左侧是原RANSAC算法拼接得到的效果图，右侧是本文改进算法得到的效果图.

图6 拼接结果的对比Fig.6 Comparison of splicing results

对比图6画框部分，可以发现图6(a)中右侧变换后拼接效果好于左侧.可能图6(a)的感官没有那么明显，对比图6(b)中画框停车位拼接部分，就能明显看出右侧明显好于左侧.由此说明改进的RANSAC算法可以得到更好的变换矩阵，能实现更好的拼接效果.

图7 图像融合效果对比Fig.7 Image fusion effect comparison

从图6中可以发现，由于拍摄角度不同及亮度也不同，即便变换矩阵多精确，都会有拼接痕迹存在.通过泊松融合对图像进行融合，主要是对图像重叠的边界进行融合，消除图像拼接的痕迹，效果如图7所示.可以明显发现左图画框部分还有拼接痕迹，而右图经过泊松融合后，基本看不出拼接痕迹，图片拼接更加自然.

图8 序列图像拼接效果Fig.8 Sequence image mosaic effect

通过本文提出的改进算法对多张序列遥感图像进行拼接，拼接后效果如图8所示.总共是8张序列图像，从图8中可以发现还是存在累计误差的，但误差较小，不影响观感.通过泊松融合消除了拼接痕迹，让最后结果更加自然.

5 总 结

本文提出了一种改进的ORB角点检测方法，在提取周边点的方式和判断特征点条件上进行改进.改进后的算法能更快更准地提取图像特征点，减少噪点的数目，提升了特征点检测效率.还提出了一种改进的RANSAC算法，在迭代过程中添加合适的特征点，提高内点占比，减少迭代次数.不仅提升了效率，还得到了更合适的变换矩阵，实现更好的拼接效果.最后采用泊松融合消除图像拼接产生的拼接痕迹，使图像拼接更加自然.通过实验可以证明，本文提出方法能够实现实时、高效、准确的图像拼接.