基于图结构的全景图自动识别与拼接方法

赵毅力，武仲科，张 雁，夏 炎

（1.西南林业大学 计算机与信息学院，云南 昆明650224；2.北京师范大学信息科学与技术学院，北京100875；3.西南林业大学 材料工程学院，云南 昆明650224）

0 引 言

图像匹配的方法一般分为两种类型，直接匹配或是基于特征的匹配。直接匹配的方法试图使用图像的像素值通过迭代的方法对图像进行配准［1，2］。基于特征的方法试图从图像中提取出不同类型的特征，例如线特征或点特征，并使用该特征的邻域信息来进行特征匹配［3，4］。

在基于特征的方法中，目前使用较多的是基于不变特征的方法。这类方法根据点特征的邻域信息计算出相应的特征描述符用以完成特征检索和匹配。这方面的工作最早是由Schmid和Mohr提出的，他们的方法通过对Harris角点进行高斯求导，形成旋转不变描述符。Lowe对这种方法进行了扩展，增加了特征的尺度不变性［5］。目前常用的特征点检测算子包括Harris角点检测算子、SIFT检测算子、BRIEF算子［6］和ORB算子［7］。并且在特征点的可重复性和描述符匹配性能评价方面也取得了不错的进展［8－10］。

基于不变特征的方法已经成功地应用到很多领域中，包括物体识别［11］、从运动获取结构［12］以及全景图像拼接［13］。虽然对图像匹配的研究已经取得了很多进展，仍然有值得研究的空间，特别是在现有的文献中缺乏对以下两个问题的详细讨论：①如何有效的判别输入的多幅无序图像之间是否有重叠部分以及重叠区域的大小；②如何自动对属于同一个场景的不同图像进行分类并合成相应的全景图像。

基于此，本文提出了一个基于图结构的全景图像自动识别和拼接的方法，能够对输入的多幅无序图像进行自动分类识别与拼接。该方法首先对输入图像进行MOPS特征检测，然后使用k－d树对特征点进行快速匹配，根据最近邻特征点距离与次近邻特征点距离之比得到初始匹配点对。根据图像特征点之间的对应关系使用RANSAC算法建立任意两幅图像之间的匹配模型，并用概率统计策略对其进行鲁棒校验。论文将多图像匹配问题建模为在不同图像节点之间建立无向连通图的问题，而多图像拼接的问题可以归结为对建立好的一个或多个无向连通图进行深度优先遍历。

1 MOPS特征检测与匹配

为了判别输入图像之间是否具有重叠区域以及图像之间的运动模型，首先对图像进行MOPS特征检测。MOPS（multi－scale oriented patches）算法［14］是 Matthew Brown针对全景图像拼接中尺度变化相对较小提出的一种特征检测算法，与 SIFT （scale－invariant feature transform）相 比 具有检测速度更快的优势。MOPS算法对Harris算法进行了扩展，为原本不具备旋转不变和尺度不变的Harris算法增加了一定的旋转不变性和尺度不变性。

对于每一幅输入图像I（x，y），首先使用子采样率参数s＝2，金字塔平滑尺度参数σp＝1.0构造高斯图像金字塔。然后在金字塔的每一层提取Harris特征点。在金字塔第L层图像PL（x，y）处的Harris矩阵计算公式为

式中： ——梯度算子，积分参数σd＝1.0，gσi——二维高斯卷积函数，σi＝1.5。为了在金字塔图像中的每一层检测特征点，首先需要计算Harris角点响应函数fHM

式中：det（HL）——矩阵 HL的行列式，tr（HL）——矩阵HL的迹矩阵，λ1和λ2——矩阵HL的特征值。如果金字塔图像PL（x，y）在 （x，y）处的角点响应函数值在其3x3的邻域中为最大值，并且大于阈值t，则将其作为候选特征点，在实验中取参数t＝10.0。

为了使Harris特征点具备旋转不变性，需要对每一个候选特征点赋予一个主方向θ。通过对局部梯度进行平滑可以计算得到方向向量uL

其中积分尺度参数σo＝4.5。

检测得到初始的候选特征点后，为了保证特征检测的稳定性，还需要对其进行筛选。由于Harris角点响应函数会在图像的边界处取得较大的响应值，而图像的边界对于噪声比较敏感，会对检测到的特征点的位置有比较多的影响，因此需要删除每一层金字塔图像边界上的候选特征点。首先对所有候选特征点进行顺序遍历，以当前特征点为中心构造一个40x40大小的采样窗口，将这个窗口旋转和特征点的主方向对齐。如果旋转后的窗口有任意部分超出当前特征点所在的金字塔图像的边界，就将当前特征点从候选特征点中删除。

一旦确定了特征点在金字塔图像中的位置，还需要为每一个特征点赋予一个描述符。这个描述符是对特征点所在局部区域的某种描述，并能够支持不同图像之间可靠的、有效的特征匹配。给定一个特征点fp（x，y，level，θ），对以特征点为中心的40x40大小的图像局部块进行采样，采样间隔s＝5。因此可以将特征点局部图像块划分为8x8的子块，特征向量的每一个分量是5x5子块的平均值，共64维。采样之后，为了使特征描述符向量对光亮度变化具有不变性，还需要对特征描述符向量进行归一化，使其均值为0，标准偏差为1。

如果拼接的是柱面全景图或球面全景图，首先需要使用反向映射将每一幅输入图像转换为柱面图像或球面图像，在转换过程中还需要使用双线性插值避免在图像变换中的走样。然后将每一幅图像中的特征点通过正向映射也转换到相应的柱面坐标系或球面坐标系中，再进行匹配。在对不同图像之间的特征点进行匹配时，需要对特征向量进行最近邻搜索。论文采用基于k－d树的最近邻搜索算法，可以将特征检索的时间复杂度O（N1N2D）降低到O（N1log2N2）。

算法1 基于k－d树的快速特征匹配

（1）为每一幅图像的特征点集构造一颗k－d树；

（2）依次对每一幅图像的每一个特征点进行遍历。初始时图像索引值i＝0，特征点索引值n＝0。对于第i幅图像的第n个特征点，对所有其他图像的k－d树进行检索，查找和当前特征点欧氏距离最近的前两个特征点nn1和nn2，其欧氏距离分别为d1和d2。当d1和d2的比值小于0.6时，认为nn1是最佳匹配点。

（3）当所有图像的所有特征点都遍历完成后，还需要对特征匹配的结果进行校验。假设第i幅图像中第ni个特征点的匹配图像索引值为j，匹配特征点索引值为nij。需要检查第j幅图像中第nij个特征点对应于图像i的匹配特征点索引值是否为ni，如果两者不相符就认为该匹配是错误的。

2 基于图结构的多图像匹配

根据图像特征点之间的对应关系就可以建立输入图像集合中任意两幅图像之间的匹配关系。可以用无向图结构来表示这个计算过程，每一幅输入图像是无向图中的一个节点，如果两幅图像之间满足给定的匹配关系，则在这两个节点之间存在一条连接线。多图像匹配问题就是要计算这个无向图结构中所有存在的无向连通图。

算法2 基于无向图结构的多图像匹配

（1）依次对输入的每一幅图像进行遍历，初始索引值i＝0；对除了第i幅图像以外的图像进行遍历，初始索引值j＝0。如果第i幅图像和第j幅图像之间有匹配的特征点对，就将该特征点对加入到第i幅图像的图像匹配集合中；

（2）如果第i幅图像和第j幅图像之间匹配的特征点数量大于给定的阈值，则认为两幅图像之间存在一个可以计算的模型，并将第j幅图像的索引值加入到第i幅图像的模型集合中；

（3）用 RANSAC （random sample consensus）算法［15］对第i幅图像和第j幅图像之间的匹配特征点对进行鲁棒校验，剔除外点，同时求出两幅图像之间的运动模型参数。

对于每一对潜在的匹配图像之间都存在两组不同类型的匹配特征点对，一组是符合运动模型几何一致性的特征点对，一组是几何不一致性的特征点对。论文使用基于统计的策略对图像匹配进行鲁棒校验。基本思想是比较这一组内点／外点是由一个正确的图像匹配或者错误的图像匹配产生的概率大小。对于一幅给定的图像，用nf表示这幅图像在重叠区域中的特征点数目，ni表示这幅图像在重叠区域中的内点数目。可以用服从0－1分布的随机变量m来表示随机事件 “这幅图像匹配正确或错误”。假设事件 “第i个匹配点对f（i）∈ ｛ 0，1｝是内点／外点”是n重伯努利实验，那么随机变量 “内点总的数目”服从二项分布

式中：p1——给定一个正确的图像匹配，一个特征点是内点的概率；p0——给定一个错误的图像匹配，一个特征点是内点的概率。因此内点的数目ni＝∑nfi＝1f（i）。论 文 在实验中选择参数p1＝0.7，p0＝0.01，可以通过贝叶斯公式计算一个图像匹配样本是正确的后验概率

如果p（m＝＞pmin，则认为该图像匹配是正确的。假设p（m＝1）＝p（m＝0），则

论文在实验中选择参数pmin＝0.97，则当条件ni＞5.9＋0.22nf成立时，认为该图像匹配是正确的。

3 全景图自动识别与拼接

一旦建立好图像两两之间的匹配关系，就可以根据匹配图像的连接集来查找全景图像序列，还可以对一组输入图像之间存在的一个或多个全景图像进行自动识别，同时拒绝那些不和其他图像匹配的 “噪声”图像。在第2部分的基础上面，论文把这个问题表示为对多个无向连通图的深度优先遍历。

算法3 全景图自动识别算法

（1）检查图像列表里面是否还有没有拼接过的图像，如果有，选择这幅图像记为Ifrom，作为新的拼接图像Iresult的起始图像，将其标记为 “已经拼接”；如果没有则算法退出；

（2）假设图像Ifrom的匹配列表中共有N幅图像，令索引值s＝0，从匹配列表中选取索引值为s的图像Ito，如果图像Ito还没有被拼接，则调用算法4对这两幅图像进行拼接；

（3）令索引值s＝s＋1，如果s＜N回到第 （2）步；否则输出Iresult，回到第 （1）步。

算法4 全景图自动拼接算法

（1）根据Ito和Iresult之间的映射关系动态调整包围盒的大小，如图1所示。在图1中，每一行表示一次拼接过程。假设从IMG1开始拼接，其中包围盒用虚线表示；

图1 多幅图像拼接过程中的包围盒动态调整

（2）根据包围盒的位置依次调整Iresult中已经拼接过的图像的位置参数，生成新的结果图像I′result，将旧的图像Iresult拷贝到Iresult中新的位置，并令I′result＝Iresult；

（3）使用多频带融合算法［16］将Ito与Iresult进行合成，并记录Ito在Iresult中的位置和索引号，将其标记为 “已经拼接”。依次从Ito的匹配列表中取出每一个元素，递归调用算法4。

4 实验结果

图2上半部分是使用佳能IXUS 980IS数码相机拍摄的8幅图像，下半部分是将这8幅图像输入系统后得到的4幅输出图像。系统能够自动识别出每一幅图像是否和其他图像有重叠，并能够将匹配的图像按组进行拼接输出。其中的一幅图像由于和其他图像都不匹配，因此作为一幅单独的 “拼接”图像输出。

图2 多幅图像的自动识别与拼接

5 结束语

本文提出了一种新的基于图结构的全景图像序列自动识别和拼接方法。这个方法使用MOPS进行特征检测，并用概率模型对图像匹配进行鲁棒校验，能够对无序图像集中的多个全景图像进行自动识别，在没有用户输入的情况下将它们自动进行拼接。即使图像之间存在由于光照变化带来的亮度差异，对多频带图像融合方案的采用也能够在图像重叠区域之间形成平滑过渡，同时保持高频细节。论文进一步的研究内容包括使用OpenCL或CUDA这样的并行计算框架将计算放到GPU中运行，以及探索其他图像融合方法。

：

［1］Bartoli A.Groupwise geometric and photometric direct image registration ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence.2008，30 （2）：2098－2108.

［2］GAY V.Direct estimation of nonrigid registrations with imagebased self－occlusion reasoning ［J］.IEEE Transactions on PatternA－nalysis and Machine Intelligence.2010，32 （1）：87－104.

［3］Sandip R，Satish K.A survey：Methods of feature based image registration ［J］.International Journal of Electronics Communication and Computer Engineering，2012，3 （4）：787－791.

［4］Jose S，Oscar C.GRASP and path relinking hybridizations for the point matching－based image registration problem ［J］.Journal of Heuristics，2012，18 （1）：169－192.

［5］Lowe D.Distinctive image features from scale－invariant keypoints ［J］.International Journal of Computer Vision，2004，60（2）：91－110.

［6］Calonder M，Lepetit V.Brief：Binary robust independent elementary features ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34 （7）：1281－1298.

［7］Ethan R，Vincent R，Kurt K，et al.ORB：An efficient alternative to SIFT or SURF ［C］／／Barcelona：13th International Conference on Computer Vision，2011：2564－2571.

［8］Pierre M，Pietro P.Evaluation of features detectors and descriptors based on 3Dobjects ［J］.International Journal of Computer Vision，2007，73 （3）：263－284.

［9］Steffen G，Tobias H，Mmtthew T.Evaluation of interest point detectors and feature descriptors for visual tracking ［J］.International Journal of Computer Vision.2011，94 （3）：335－360.

［10］Mikolajczyk K，Schmid C.A performance evaluation of local descriptors ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27 （10）：1615－1630.

［11］Noah S，Rahul G，Steven M，et al.Finding Paths through the worlds photos ［J］.ACM Transactions on Graphics，2008，27（3）：11－21.

［12］Furukawa Y，Snavely N，Curless B，et al.Reconstructing rome ［J］.IEEE Computer，2010，43 （6）：40－47.

［13］Byrod M，Brown M，Astrom A.Minimal solutions for panoramic stitching with radial distortion ［C］／／Procee－dings of the British Machine Vision Conference.London，2009：1－7.

［14］Brown M，Szeliski R，Wwnder S.Multi－image matching using multi－scale oriented patches ［C］／／International Conference on Computer Vision and Pattern Recognition.Anchorage：IEEE，2005：510－517.

［15］Jongmoo C，Medioni G.StaRSaC：Stable random sample consensus for parameter estimation ［C］／／IEEE Conference on Computer Vision and Pattern Recognition.Miami，2009：675－682.

［16］Allene C，Pons J，Keriven R.Seamless image－based texture atlases using multi－band blending ［C］／／19th International Conference on Pattern Recognition.Tampa，2008：1－4.