图像融合技术外文翻译-中英对照

***大学毕业设计〔英文翻译〕原文题目：AutomaticPanoramicImageStitchingusingInvariantFeatures译文题目：使用不变特征的全景图像自动拼接学院：电子与信息工程学院专业：********姓名：******学号：**********使用不变特征的全景图像自动拼接马修·布朗和戴维•洛计算机科学系英国哥伦比亚大学加拿大温哥华摘要本文研究全自动全景图像的拼接问题，尽管一维问题〔单一旋转轴〕很好研究，但二维或多行拼接却比拟困难。以前的方法使用人工输入或限制图像序列，以建立匹配的图像，在这篇文章中，我们假定拼接是一个多图像匹配问题，并使用不变的局部特征来找到所有图像的匹配特征。由于以上这些，该方法对输入图像的顺序、方向、尺度和亮度变化都不敏感；它也对不属于全景图一局部的噪声图像不敏感，并可以在一个无序的图像数据集中识别多个全景图。此外，为了提供更多有关的细节，本文通过引入增益补偿和自动校直步骤延伸了我们以前在该领域的工作。1.简介全景图像拼接已经有了大量的研究文献和一些商业应用。这个问题的根本几何学很好理解，对于每个图像由一个估计的3×3的摄像机矩阵或对应矩阵组成。估计处理通常由用户输入近似的校直图像或者一个固定的图像序列来初始化，例如，佳能数码相机内的图像拼接软件需要水平或垂直扫描，或图像的方阵。在自动定位进行前，第4版的REALVIZ拼接软件有一个用户界面，用鼠标在图像大致定位，而我们的研究是有新意的，因为不需要提供这样的初始化。根据研究文献，图像自动对齐和拼接的方法大致可分为两类——直接的和基于特征的。直接的方法有这样的优点，它们使用所有可利用的图像数据，因此可以提供非常准确的定位，但是需要一个只有细微差异的初始化处理。基于特征的配准不需要初始化，但是缺少不变性的传统的特征匹配方法〔例如，Harris角点图像修补的相关性〕需要实现任意全景图像序列的可靠匹配。在本文中，我们描述了一个基于不变特征的方法实现全自动全景图像的拼接，相比以前的方法有以下几个优点。第一，不变特征的使用实现全景图像序列的可靠匹配，尽管在输入图像中有旋转、缩放和光照变化。第二，通过假定图像拼接是一个多图像匹配问题，我们可以自动发现这些图像间的匹配关系，并且在无序的数据集中识别出全景图。第三，通过使用多波段融合呈现无缝输出的全景图，可以产生高质量的结果。本文通过引入增益补偿和自动校直步骤延伸了我们以前在该领域的工作，我们还描述了一个高效的捆绑调整实现并展示对任意数量波段的多个重叠图像如何进行多波段融合。本文其余局部的结构如下。第二局部说明所研究问题的几何学和我们选择不变特征的原因。第三局部介绍了图像匹配方法〔RANSAC〕和验证图像匹配的概率模型。第四局部中，我们描述了图像对准算法〔捆绑调整〕，即共同优化每个摄像头的参数。五到七局部描述了处理过程，包括自动校直、增益补偿和多波段融合。第九局部中，我们给出了结论和对未来工作的展望。2.特征匹配全景识别算法的第一步是在所有图像之间提取和匹配SIFT特征检测点。SIFT特征检测子位于不同尺度空间高斯插值函数的极值点处，对每一个特征点，特征尺度和方向被确定，这为测量提供了一个相似不变的结构。尽管在这个结构中简单的采样强度值是相似不变的，但是不变描述子实际上是通过对方向直方图的局部梯度值进行累积计算得到的，这样就允许边缘有轻微的移动而不会改变描述子的矢量，对仿射变换提供了一定的鲁棒性。空间累积计算对平移不变性同样重要，因为感兴趣点位置通常仅在0~3个像素的范围内是精确的。为了实现亮度不变性可以使用梯度〔消除偏差〕和对描述子矢量归一化〔消除增益〕。由于SIFT特征在旋转和尺度变化时是不变的，我们可以处理具有变化的方向和大小的图像〔见图8〕。值得注意的是，这是传统的特征匹配技术不能实现的，例如Harris角点图像修补的相关性。传统的相关性在图像旋转时是变化的，Harris角点在改变图像尺度时也是变化的。假设相机绕光学中心旋转，图像的变换群是一个对应矩阵的特殊群。由一个旋转矢量和焦距将每个摄像头参数化，就给出了成对的对应矩阵，其中〔1〕并且是均匀的图像坐标〔，其中是二维的图像坐标〕。4参数的相机模型定义为：〔2〕对旋转使用指数表示：〔3〕在这个变换群中，理想条件下将会使用不变的图像特征。可是，在图像坐标中对于小的变换表示如下：〔4〕或者等价于，其中，〔5〕是通过一个关于的对应线性化得到的仿射变换。这意味着每个小的图像修补经过一次仿射变换，并且合理利用了在仿射变换下局部不变的SIFT特征。一旦从所有n个图像中提取特征点后〔线性时间内〕，需对特征点进行匹配。由于多个图像可能重叠在一个单一的光线上，在特征空间内每个特征点需和它最近的k个领域点匹配〔k=4〕，通过使用k-d树算法找到近似最近的领域点，时间复杂度为O〔〕。k-d树是一种轴对齐的二进制空间划分，它在平均最高方差维递归划分特征空间。图像匹配图像匹配的目标是找到所有匹配〔例如重叠〕图像，稍后图像匹配连通集会成为全景图。由于每个图像可能和任意其他一个匹配，这个问题一开始就呈现是出图像数的二次方。为了得到一个好的拼接结果，对于图像几何而言，每个图像只需要和少数重叠的图像来匹配。从特征匹配这个步骤中，我们已找出图像间有大量匹配点的图像。对于当前图像，我们将m幅图像作为可能的匹配图像〔m=6〕，这m幅图像与当前图像有最大数量的特征匹配点。首先，使用RANSAC算法选择一系列和图像间对应矩阵兼容的内点，然后应用概率模型做进一步的验证。3.1使用RANSAC算法的鲁棒对应矩阵估计RANSAC〔随机抽样一致性算法〕算法是使用最少的一组随机采样匹配点的一种鲁棒估计过程，用来估计图像变换参数，并找到与数据具有最好一致性的解决方案。在全景图的情况下，我们选择r=4对匹配特征点，使用直接线性变换〔DLT)方法计算图像间的对应矩阵H。重复500次试验，选择内点数最大的解决方案〔在像素误差范围内，其预测和H是一致的〕。假设一对匹配图像间的特征匹配点是正确的概率〔内点概率〕为，n次试验后找到正确变换的概率为：〕〔6〕经过大量试验后，找到正确对应矩阵的概率非常大。例如，对于内点概率，在500次试验后，未找到正确对应矩阵的概率为。RANSAC算法本质上是一种估计H的采样方法，如果用对数似然和的最大化代替内点数量的最大化，结果是最大似然估计〔MLE〕。此外，如果变换参数的先验值是有效的，可以计算出最大后验概率〔MAP〕。这些算法被分别称为MLESAC和MAPSAC。3.2图像匹配关系验证的概率模型对两两图像间是否存在匹配关系，我们使用一系列几何一致的特征匹配点〔RANSAC内点〕和一系列在重叠区域内，但不一致的特征点〔RANSAC外点〕来验证。验证模型通过比拟这些正确匹配产生的一系列内点和错误匹配产生的一系列外点的概率来进行验证。对于一幅给定的图像，重叠区域内总的匹配特征点数为，内点数为。图像是否有效匹配通过二进制变量表示。第个匹配特征点是否为内点被假定为独立的贝努力分布，以便于内点总数服从贝努力分布：〔7〕〔8〕其中，是可以正确匹配图像时特征点为内点的概率，是不能实现图像匹配时特征点为内点的概率；表示特征匹配点变量的集合，内点数，B(.)是贝努力分布，表示如下：〔9〕我们选择，，那么可以使用贝叶斯规那么〔式10、11〕计算正确图像匹配的先验概率。〔10〕〔11〕如果满足〔12〕我们可以实现图像匹配。假定，，进一步得出正确图像匹配的判定条件：〔13〕其中，。尽管在这我们选择了，，，和的值，但在原理上可以从数据中进一步确定这些值。例如，可以通过在大的数据集中计算一局部匹配点和正确的对应矩阵相一致来估计。一旦图像间的匹配点对确定，我们可以找到全景序列作为连接匹配图像集，它可以识别图像集中的多个全景，拒绝不匹配的噪声图像〔见图2〕。〔a〕图一〔b〕图二〔c〕SIFT匹配点1〔d〕SIFT匹配点2〔e〕RANSAC内点1〔f〕RANSAC内点2〔g〕依据对应矩阵的图像对准图1，从所有图像中提取SIFT特征点。使用k-d树匹配所有特征点后，对于一个给定图像，用有最多特征匹配点的m幅图像进行图像匹配。首先执行RANSAC算法计算出对应矩阵，然后调用概率模型验证基于内点数的图像匹配，在这个例子中，输入图像是517×374像素，有247个正确特征匹配点。〔a〕图像匹配点〔b〕图像匹配点的连接分量〔c〕输出全景图图2，可识别全景图。考虑一个特征匹配点的噪声集，我们使用RANSAC算法和概率验证过程找到一致的图像匹配〔a〕，每个图像对间的箭头表示在图像对间找到一致的特征匹配点集，图像匹配连接分量被找到〔b〕，拼接成全景图〔c〕；注意到该算法对不属于全景图的噪声图像不敏感。4.捆绑调整考虑到图像间的几何一致性匹配集，使用捆绑调整解决所有相机参数的问题，这是重要的一个步骤，由于成对对应矩阵拼接将会造成累计误差，忽略图像间的多重约束，如全景图两端应联合起来。图像一个接一个被添加到捆绑调节器，最正确匹配图像〔一致匹配数目最大〕在每一步被添加，新图像用与最正确匹配图像具有相同的旋转和焦距长度初始化，然后相机参数使用L-M算法被更新。我们使用的目标函数是一种抗差总和平方预测误差。也就是说，每个特征点被投影到所有与它匹配的图像中，并且平方图像距离的总和依据相机参数最小化。考虑到对应关系〔表示在图像中第k个特征点的位置〕，残差表示为〔14〕其中对应到的点是对应于点从图像到图像的投影〔15〕误差函数是所有图像抗差剩余误差的和，表示如下:〔16〕其中n是总的图像数,I()是和图像匹配的图像集,是图像和图像的特征匹配集。我们使用Huber鲁棒误差函数,如下所示:〔17〕这个误差函数结合将范数的快速收敛性作为内点的优化方案〔距离小于〕，和将范数的鲁棒性作为外点的方案〔距离大于〕。作为初始化过程中使用的外点距离，个像素点作为最终结果。这是一个我们使用L-M算法解决的非线性最小二乘问题。每次迭代的形式如下：〔18〕其中是所有参数，是残差，。在〔对角线〕协方差矩阵中，我们先前编码的有关参数改变了，如下所示：〔19〕这个矩阵中，角度标准偏差是，焦距长度〔是目前为止焦距长度估计的平均值〕。这有助于选择适宜的步长，从而加快收敛，例如，如果用一个球形的协方差矩阵，一弧度的旋转变化将被焦距长度参数中一像素的变化所补偿。最后，在每一次迭代中，改变参数以确保等式〔16〕的目标函数确实在减小。通过链式法那么导数被分析计算，例如:〔20〕其中〔21〕〔22〕〔23〕4.1通过直接计算线性系统的快速解决方案由于矩阵是稀疏的,乘以它的转置是没有用的，事实上，这是捆绑调整中最有价值的步骤，对的矩阵〔是测量个数的两倍，是参数的个数〕所需的时间复杂度为O〔〕。由于每个图像通常只匹配其它图像的一小局部，出现了稀疏性，这意味着在实际中矩阵中每个元素的计算比M次乘法少的多，如下所示：〔24〕例如，相机和间的反向协方差只依赖于和间的特征匹配残差值。相似的,不需要直接计算，可通过下式得到：〔25〕在两种情况下，如果每个特征点匹配每个单独的图像，每一个和将需要次乘法，但在实际中，对于给定的图像，特征匹配点的个数要比这个少的多。因此，每个捆绑调整迭代的时间复杂度为O，这是解决线性系统的代价。参数的数量是图像数量的4倍，典型的值大概是的100倍。自动全景校直使用第2-4局部步骤的图像配准提供了摄像机间的相对旋转，但是对于选定的世界坐标系而言仍有一个未知的3D旋转。对于每一幅图像如果我们简单的假设R=I，我们通常会发现在输出的全景图中有波状效应，这是因为真正的相机不会是完全水平且没有倾斜的。我们可以修正这种波形的输出，并且可以通过利用人们通常拍摄全景图方式的启发式算法自动校直全景图。人们很少相对于视距扭转相机，所以相机的参数向量〔水平轴〕通常位于一个平面〔见图4〕。通过找到相机参数向量的协方差矩阵的零向量，我们可以找到“向上的向量〞〔对包含了相机的中心和视距〕，如下：〔26〕对一个垂直向上向量〔在呈现的结构中〕进行整体旋转，非常有效的从输出全景图中消除了波状效应，如图4。图3，寻找向上向量u。由于一个好的用于对准波浪形全景图的启发式算法，人们很少相对于视距转动相机，因此，尽管倾斜〔如图b〕和旋转(如图c)，相机参数X向量通常位于一个平面，向上向量〔与重力方向相反〕是这个平面的法线。〔a〕没有使用自动校直图像〔b〕使用自动校直图像图4，自动全景校直。利用人们很少相对于视距转动相机的启发式算法允许我们通过计算向上向量〔垂直于包含相机中心和视距的平面〕校直波浪形全景图。,6.增益补偿在前面的局部中，我们描述了计算相机几何参数〔方向和焦距〕的方法。在这一局部中，我们描述了如何解决光度测量参数，即图像间的总增益。通过相似的方式建立模型，对所有图像定义一个误差函数，误差函数是所有重叠像素的增益归一化强度误差的和，表示如下:〔27〕其中，是增益，是图像和图像的重叠区域。在实际中，我们通过每个重叠区域的平均值来近似，如下所示：〔28〕这简化了计算并给外点提供鲁棒性，这可能是由图像间小的位置不正引起的。此外，是这个问题的最正确解决方案，我们添加了一个预先条件来保持增益一致。因此误差函数可表示如下：〔29〕其中与图像和图像间重叠局部的像素数量相等，参数和分别是归一化强度误差和增益的标准偏差，我们选择，。这是一个增益参数的二次目标函数，可以通过在封闭的形式中设置导数趋于0来解决〔见图5〕。〔a〕完成一半的图像配准〔b〕没有增益补偿的图像〔c〕有增益补偿的图像〔d〕使用增益补偿和多波段混合拼接图像图5，增益补偿。如果没有应用增益补偿，如〔a〕〔b〕，图像间大的亮度变化是可见的；增益补偿后，由于未建模的影响，一些图像边缘仍然可见，例如晕映〔图c〕。这些都可以使用多波段混合有效的平滑掉〔图d〕。7.多波段融合理想情况下，每个图像中沿一条射线的每个样值〔像素〕会有相同的强度，它们会相交，但现实并非如此。由于一些未建模的影响，即使在增益补偿后，图像边缘仍然可见，如图像边缘暗淡〔朝图像边缘方向强度降低〕，由于光中心不必要的移动引起的视差效果，摄像头的错误建模、径向畸变等引起的微小的定位误差等。由于这些，一个好的融合策略是很重要的。从前面的步骤中，考虑到的匹配，有n幅图像可以被表示在一个共同的〔球形〕坐标系中。为了从多个图像中合并信息，我们为每个图像分配一个加权函数，其中从中心1到边缘0线性变化。加权函数在球形坐标系内重新采样，拼接的一种简单方法是计算沿着每条射线，使用这些加权函数的图像强度的加权总和。如下所示：〔30〕其中，是使用线性融合形成的复合球面图像，可是如果有小的匹配错误，这种方法会引起高频细节模糊〔见图7〕。为了防止这种情况，我们使用Burt和Adelson的多波段融合算法。多波段融合的想法是在一个很大的空间范围内融合低频率，在一个小的范围内融合高频频率。我们通过找到图像最有用的点集来初始化每个图像的混合权重，表示如下：〔31〕例如对于，为1表示图像有最大权值，0表示其它一些图像有较高的权值。这些最大权值的映射连续混合形成了每个波段的混合权值。所呈现图像的高通版本形式如下：〔32〕〔33〕其中，是的高斯标准偏差，操作符表示卷积，表示在波长为范围内的空间频率。我们通过模糊这幅图像的最大权值映射，形成融合权值以融合图像间的该波段，如下：〔34〕其中，为波长为的波段内的融合权值，后续的频段使用低频带通图像和进一步模糊融合权值来融合，例如，对于，〔35〕〔36〕〔37〕其中设置高斯模糊内核的标准偏差为，如后续波段有相同波长的范围。对每一个波段，使用对应的融合权值线性合并重叠的图像，如下所示：〔38〕这会引起高频段〔小于〕在小范围内融合，而低频段〔大于〕在较大的范围内融合〔见图6〕。注意到我们选择呈现的全景图在参数为，的球面坐标内呈现全景图，原那么上从呈现的角度来看，我们可以选择一个外表的任何二维参数。一个好的选择将会呈现一个三角形球面，在图像平面构造融合权值，这样会有统一处理所有图像的优势，同时易于其它外表〔在图形硬件〕的重采样。，参数设置受极点的奇异性影响。算法：自动全景拼接输入：n个无序图像从n幅图像中提取SIFT特征。使用k-d算法为每个特征点找到k个最邻近的匹配特征点。对于每一幅图像：选择m个候选匹配图像，它们与要匹配的图像有最多的特征匹配点；使用RANSAC算法找到几何一致的特征匹配来得到图像对间的对应矩阵；使用概率模型验证图像匹配。找到图像匹配的连接分量。对于每个连接分量：〔1〕执行捆绑调整解决所有相机的旋转角，，和焦距；〔2〕呈现使用多波段融合拼接的全景图。输出：全景图像〔a〕原始图像和拼接结果〔b〕波段1(从0到)〔c〕波段2(从到)〔d〕波段3(小于)图6，多波段融合。左边显示的为k=1，2，3的带通图像B(θ,φ)，右边为对应的融合权值W(θ,φ)。最初的融合权值指定为1是每个图像的最大权值。为了获得每一个融合函数，在空间频率中，权值是模糊的，并形成相同空间频率的带通图像。使用基于融合权值的加权和将带通图像融合在一起〔a〕线性融合拼接图像〔b〕多波段融合拼接图像图7，线性和多波段融合拼接的比拟。右边的图像使用多波段融合，其中使用了5个波段，,=5个像素。左边的图像是线性融合拼接。关于运动中的人的图像匹配会引起图像间小的错误配准，线性融合拼接的结果会导致图像模糊，而多波段融合拼接图像是清晰的。〔a〕〔b〕图8，具有旋转和缩放的图像拼接。尽管在输入图像中有旋转、缩放和亮度变化，使用不变特征点可以实现图像拼接。塔顶和塔底的插像是其它图像尺寸的4倍。特征匹配点数随(b)k=0.5时，两幅图(c)先前数据显示未k的变化关系像拼接的例子配准的细节图像图9，存在径向畸变的图像拼接。图像显示了一阶径向畸变对图像拼接的影响〔图像的高度归一化为单位长度〕，其中。注意到径向畸变没有在我们的算法中建模，我们使用了44幅图像序列测试并应用于20个不同k值的径向畸变图像，畸变图像的例子示于图〔d〕-〔h〕中。为了评估拼接的性能，我们计算了RANSAC算法后一致匹配点的个数，结果示于图〔a〕。虽然在最坏的情况下，每个特征的匹配点数量下降了约三分之一，正确特征匹配点的数量仍然非常高〔大约每个图像500个〕，因此图像仍可正确匹配。尽管径向畸变在呈现的图像中会引起明显的重影，见图〔b〕-〔c〕，但会在捆绑调整和成像阶段修正，这对于高质量全景图拼接非常重要。8.结果图2显示了典型的全景识别算法操作，输入4个全景图像和4个噪声图像。该算法检测匹配图像和未匹配图像的连接分量，输出4个混合全景图。图5显示了一个较大的例子，使用相机的自动模式摄取这个图像序列，这将容许改变孔径和曝光时间，并对一些图片使用闪光灯。尽管亮度改变了，SIFT特征稳健地匹配和多波段融合策略可以产生一个无缝的全景图。输出是度，并在球形坐标系中呈现。57个图像完全自动匹配而无用户介入，对于最后的匹配，个参数最优化问题被解决。像素的输入图像在60秒内匹配和配准，15分钟后呈现了一个〔23万像素〕的全景图，57秒内，呈现一个像素的预览，该测试在1.6GHz的奔腾M上进行。9.结论本文为全自动全景图像拼接提供了一种新的系统。不变的局部特征的使用和验证图像匹配的概率模型允许我们在无序图像集中识别多个全景图，并实现全自动图像拼接而无用户介入。这个方法在相机变焦，输入图像的方向，由于闪光灯和曝光／光圈设置引起的亮度改变方面是稳健的。尽管图像间有亮度差异，多波段融合方案确保图像间的平滑过渡，同时保存了高频细节。以后的工作：今后工作的领域可能包括相机和场景中的运动补偿，摄像机几何和光学性能更先进的建模。摄像机运动：全景图经常受到光中心微小运动引起的视过失误，这些可通过从一个中心位置重新呈现前，调节相机成像和场景深度来消除。使用一个好的表示形式可能是一个无穷大的视差平面。拍摄期间小的运动会导致运动模糊，同时大的相机运动会引起视差。使用附近聚焦的图像可以改善运动模糊图像，类似的技术也可以用于产生超分辨率图像。场景运动：虽然多波段融合策略在很多情况下非常有效，当多个图像间融合时，场景中大动作的对象会引起明显的重叠〔见图10〕。另一种方法基于图像间的差异局部自动寻找最正确接缝线。先进的相机模型：不包括在投影相机模型〔保持直线〕中的大多数相机有一个重要的特征，即径向畸变，虽然没有明确的算法建模，在适度的径向畸变下我们已经测试了其性能〔见图9〕。在我们的实验中，虽然全景识别和近似校准非常有效，在显示的结果中仍有明显的重叠，因此，高质量的图像拼接应用中需要有径向畸变参数，至少在捆绑调整和成像阶段。理想的图像拼接应该也支持多个运动模式，例如，关于一点的旋转〔如全景图〕，观察平面〔如白板〕和欧式变换〔如调整扫描图像〕；也可以呈现多外表类型，如球形，圆柱形，平面。光度建模：理论上应尽可能多的估计相机测光参数，暗角〔沿图像边缘强度下降〕是每个镜头都不可防止的，特别是在色泽均匀区域，如天空；从重叠图像区域也可以获得高动态范围信息，并呈现色调映射或合成曝光图像。我们已经开发了一个C++实现本文中描述的算法，称为自动缝合，这个方案的演示可以从网站下载，网址为。图10，一个困难的拼接问题。这个例子〔纽约时代广场〕包含许多移动的物体和图像间亮度的巨大变化。尽管存在这些挑战，我们的方法仍可以找到一致的不变特征集，正确的配准图像。未来的自动图像拼接器可以检测到移动的物体，并计算出高动态范围场景的辐射地图。这将使用户重新摄取选择不同曝光设定和移动物体的场景。AutomaticPanoramicImageStitchingusingInvariantFeaturesMatthewBrownandDavidG.LoweDepartmentofComputerScience,UniversityofVancouver,AbstractThispaperconcernstheproblemoffullyautomatedpanoramicimagestitching.Thoughthe1Dproblem(singleaxisofrotation)iswellstudied,2Dormulti-rowstitchingismoredifficult.Previousapproacheshaveusedhumaninputorrestrictionsontheimagesequenceinordertoestablishmatchingimages.Inthiswork,weformulatestitchingasamulti-imagematchingproblem,anduseinvariantlocalfeaturestofindmatchesbetweenalloftheimages.Becauseofthisourmethodisinsensitivetotheordering,orientation,scaleandilluminationoftheinputimages.Itisalsoinsensitivetonoiseimagesthatarenotpartofapanorama,andcanrecognisemultiplepanoramasinanunorderedimagedataset.Inadditiontoprovidingmoredetail,thispaperextendsourpreviousworkintheareabyintroducinggaincompensationandautomaticstraighteningsteps.1.IntroductionPanoramicimagestitchinghasanextensiveresearchliteratureandseveralcommercialapplications.Thebasicgeometryoftheproblemiswellunderstood,andconsistsofestimatinga3×3cameramatrixorhomographyforeachimage.Thisestimationprocessneedsaninitialisation,whichistypicallyprovidedbyuserinputtoapproximatelyaligntheimages,orafixedimageordering.Forexample,thePhotoStitchsoftwarebundledwithCanondigitalcamerasrequiresahorizontalorverticalsweep,orasquarematrixofimages.REALVIZStitcherversion4hasauserinterfacetoroughlypositiontheimageswithamouse,beforeautomaticregistrationproceeds.Ourworkisnovelinthatwerequirenosuchinitialisationtobeprovided.Intheresearchliteraturemethodsforautomaticimagealignmentandstitchingfallbroadlyintotwocategories—directandfeaturebased.Directmethodshavetheadvantagethattheyusealloftheavailableimagedataandhencecanprovideveryaccurateregistration,buttheyrequireacloseinitialisation.Featurebasedregistrationdoesnotrequireinitialisation,buttraditionalfeaturematchingmethods(e.g.,correlationofimagepatchesaroundHarriscorners)lacktheinvariancepropertiesneededtoenablereliablematchingofarbitrarypanoramicimagesequences.Inthispaperwedescribeaninvariantfeaturebasedapproachtofullyautomaticpanoramicimagestitching.Thishasseveraladvantagesoverpreviousapproaches.Firstly,ouruseofinvariantfeaturesenablesreliablematchingofpanoramicimagesequencesdespiterotation,zoomandilluminationchangeintheinputimages.Secondly,byviewingimagestitchingasamulti-imagematchingproblem,wecanautomaticallydiscoverthematchingrelationshipsbetweentheimages,andrecognisepanoramasinunordereddatasets.Thirdly,wegeneratehigh-qualityresultsusingmulti-bandblendingtorenderseamlessoutputpanoramas.Thispaperextendsourearlierworkintheareabyintroducinggaincompensationandautomaticstraighteningsteps.Wealsodescribeanefficientbundleadjustmentimplementationandshowhowtoperformmulti-bandblendingformultipleoverlappingimageswithanynumberofbands.Theremainderofthepaperisstructuredasfollows.Section2developsthegeometryoftheproblemandmotivatesourchoiceofinvariantfeatures.Section3describesourimagematchingmethodology(RANSAC)andaprobabilisticmodelforimagematchverification.Insection4wedescribeourimagealignmentalgorithm(bundleadjustment)whichjointlyoptimisestheparametersofeachcamera.Sections5-7describetherenderingpipelineincludingautomaticstraightening,gaincompensationandmulti-bandblending.Insection9wepresentconclusionsandideasforfuturework.2.FeatureMatchingThefirststepinthepanoramicrecognitionalgorithmistoextractandmatchSIFTfeaturesbetweenalloftheimages.SIFTfeaturesarelocatedatscale-spacemaxima/minimaofadifferenceofGaussianfunction.Ateachfeaturelocation,acharacteristicscaleandorientationisestablished.Thisgivesasimilarity-invariantframeinwhichtomakemeasurements.Althoughsimplysamplingintensityvaluesinthisframewouldbesimilarityinvariant,theinvariantdescriptorisactuallycomputedbyaccumulatinglocalgradientsinorientationhistograms.Thisallowsedgestoshiftslightlywithoutalteringthedescriptorvector,givingsomerobustnesstoaffinechange.Thisspatialaccumulationisalsoimportantforshiftinvariance,sincetheinterestpointlocationsaretypicallyonlyaccurateinthe0-3pixelrange.Illuminationinvarianceisachievedbyusinggradients(whicheliminatesbias)andnormalisingthedescriptorvector(whicheliminatesgain).SinceSIFTfeaturesareinvariantunderrotationandscalechanges,oursystemcanhandleimageswithvaryingorientationandzoom(seefigure8).NotethatthiswouldnotbepossibleusingtraditionalfeaturematchingtechniquessuchascorrelationofimagepatchesaroundHarriscorners.Ordinary(translational)correlationisnotinvariantunderrotation,andHarriscornersarenotinvarianttochangesinscale.Assumingthatthecamerarotatesaboutitsopticalcentre,thegroupoftransformationstheimagesmayundergoisaspecialgroupofhomographies.Weparameteriseeachcamerabyarotationvectorandfocallength.Thisgivespairwisehomographieswhere(1)andarethehomogeneousimagepositions(，whereisthe2-dimensionalimageposition).The4parametercameramodelisdefinedby(2)and(usingtheexponentialrepresentationforrotations)(3)Ideallyonewoulduseimagefeaturesthatareinvariantunderthisgroupoftransformations.However,forsmallchangesinimageposition(4)orequivalently,where(5)isanaffinetransformationobtainedbylinearisingthehomographyabout.Thisimpliesthateachsmallimagepatchundergoesanaffinetransformation,andjustifiestheuseofSIFTfeatureswhicharepartiallyinvariantunderaffinechange.Oncefeatureshavebeenextractedfromallnimages(lineartime),theymustbematched.Sincemultipleimagesmayoverlapasingleray,eachfeatureismatchedtoitsknearestneighboursinfeaturespace(weusek=4).ThiscanbedoneinO〔〕timebyusingak-dtreetofindapproximatenearestneighbours.Ak-dtreeisanaxisalignedbinaryspacepartition,whichrecursivelypartitionsthefeaturespaceatthemeaninthedimensionwithhighestvariance.3.ImageMatchingAtthisstagetheobjectiveistofindallmatching(i.e.overlapping)images.Connectedsetsofimagematcheswilllaterbecomepanoramas.Sinceeachimagecouldpotentiallymatcheveryotherone,thisproblemappearsatfirsttobequadraticinthenumberofimages.However,itisonlynecessarytomatcheachimagetoasmallnumberofoverlappingimagesinordertogetagoodsolutionfortheimagegeometry.Fromthefeaturematchingstep,wehaveidentifiedimagesthathavealargenumberofmatchesbetweenthem.Weconsideraconstantnumbermimages,thathavethegreatestnumberoffeaturematchestothecurrentimage,aspotentialimagematches(weusem=6).First,weuseRANSACtoselectasetofinliersthatarecompatiblewithahomographybetweentheimages.Nextweapplyaprobabilisticmodeltoverifythematch.3.1RobustHomographyEstimationusingRANSACRANSAC(randomsampleconsensus)isarobustestimationprocedurethatusesaminimalsetofrandomlysampledcorrespondencestoestimateimagetransformationparameters,andfindsasolutionthathasthebestconsensuswiththedata.Inthecaseofpanoramasweselectsetsofr=4featurecorrespondencesandcomputethehomographyHbetweenthemusingthedirectlineartransformation(DLT)method.Werepeatthiswithn=500trialsandselectthesolutionthathasthemaximumnumberofinliers(whoseprojectionsareconsistentwithHwithinatolerancepixels).Giventheprobabilitythatafeaturematchiscorrectbetweenapairofmatchingimages(theinlierprobability)is,theprobabilityoffindingthecorrecttransformationafterntrialsis〕(6)Afteralargenumberoftrialstheprobabilityoffindingthecorrecthomographyisveryhigh.Forexample,foraninlierprobability=0.5,theprobabilitythatthecorrecthomographyisnotfoundafter500trialsisapproximately.RANSACisessentiallyasamplingapproachtoestimatingH.Ifinsteadofmaximisingthenumberofinliersonemaximisesthesumoftheloglikelihoods,theresultismaximumlikelihoodestimation(MLE).Furthermore,ifpriorsonthetransformationparametersareavailable,onecancomputeamaximumaposterioriestimate(MAP).ThesealgorithmsareknownasMLESACandMAPSACrespectively.3.2ProbabilisticModelforImageMatchVerificationForeachpairofpotentiallymatchingimageswehaveasetoffeaturematchesthataregeometricallyconsistent(RANSACinliers)andasetoffeaturesthatareinsidetheareaofoverlapbutnotconsistent(RANSACoutliers).Theideaofourverificationmodelistocomparetheprobabilitiesthatthissetofinliers/outlierswasgeneratedbyacorrectimagematchorbyafalseimagematch.Foragivenimagewedenotethetotalnumberoffeaturesintheareaofoverlapandthenumberofinliers.Theeventthatthisimagematchescorrectly/incorrectlyisrepresentedbythebinaryvariable.Theeventthatthefeaturematchisaninlier/outlierisassumedtobeindependentBernoulli,sothatthetotalnumberofinliersisBinomial(7)(8)whereistheprobabilityafeatureisaninliergivenacorrectimagematch,andistheprobabilityafeatureisaninliergivenafalseimagematch.Thesetoffeaturematchvariablesisdenoted.ThenumberofinliersandB(.)istheBinomialdistribution(9)Wechoosevaluesand.WecannowevaluatetheposteriorprobabilitythatanimagematchiscorrectusingBayes’Rule(10)(11)Weacceptanimagematchif(12)Choosingvaluesandgivesthecondition(13)foracorrectimageandβ=0.3.Thoughinpracticewehavechosenvaluesfor,,,,and,theycouldinprinciplebelearntfromthedata.Forexample,couldbeestimatedbycomputingthefractionofmatchesconsistentwithcorrecthomographiesoveralargedataset.Oncepairwisematcheshavebeenestablishedbetweenimages,wecanfindpanoramicsequencesasconnectedsetsofmatchingimages.Thisallowsustorecognisemultiplepanoramasinasetofimages,andrejectnoiseimageswhichmatchtonootherimages(seefigure(2)).(a)Image1(b)Image2(c)SIFTmatches1(d)SIFTmatches2(e)RANSACinliers1(f)RANSACinliers2(g)ImagesalignedaccordingtoahomographyFigure1.SIFTfeaturesareextractedfromalloftheimages.Aftermatchingallofthefeaturesusingak-dtree,themimageswiththegreatestnumberoffeaturematchestoagivenimagearecheckedforanimagematch.FirstRANSACisperformedtocomputethehomography,thenaprobabilisticmodelisinvokedtoverifytheimagematchbasedonthenumberofinliers.Inthisexampletheinputimagesare517×374pixelsandthereare247correctfeaturematches.(a)Imagematches(b)Connectedcomponentsofimagematches(c)OutputpanoramasFigure2.Recognisingpanoramas.Givenanoisysetoffeaturematches,weuseRANSACandaprobabilisticverificationproceduretofindconsistentimagematches(a).Eacharrowbetweenapairofimagesindicatesthataconsistentsetoffeaturematcheswasfoundbetweenthatpair.Connectedcomponentsofimagematchesaredetected(b)andstitchedintopanoramas(c).Notethatthealgorithmisinsensitivetonoiseimagesthatdonotbelongtoapanorama(connectedcomponentsofsize1image).4.BundleAdjustmentGivenasetofgeometricallyconsistentmatchesbetweentheimages,weusebundleadjustmenttosolveforallofthecameraparametersjointly.Thisisanessentialstepasconcatenationofpairwisehomographieswouldcauseaccumulatederrorsanddisregardmultipleconstraintsbetweenimages,e.g.,thattheendsofapanoramashouldjoinup.Imagesareaddedtothebundleadjusteronebyone,withthebestmatchingimage(maximumnumberofconsistentmatches)beingaddedateachstep.Thenewimageisinitialisedwiththesamerotationandfocallengthastheimagetowhichitbestmatches.ThentheparametersareupdatedusingLevenberg-Marquardt.Theobjectivefunctionweuseisarobustifiedsumsquaredprojectionerror.Thatis,eachfeatureisprojectedintoalltheimagesinwhichitmatches,andthesumofsquaredimagedistancesisminimisedwithrespecttothecameraparameters.Givenacorrespondence(denotesthepositionofthefeatureinimage),theresidualis(14)whereistheprojectionfromimagetoimageofthepointcorrespondingto(15)Theerrorfunctionisthesumoverallimagesoftherobustifiedresidualerrors(16)Wherenisthenumberofimages,I()isthesetofimagesmatchingtoimage,isthesetoffeaturematchesbetweenimagesand.WeuseaHuberrobusterrorfunction(17)Thiserrorfunctioncombinesthefastconvergencepropertiesofannormoptimisationschemeforinliers(distancelessthan),withtherobustnessofannormschemeforoutliers(distancegreaterthanσ).Weuseanoutlierdistanceduringinitialisationandpixelsforthefinalsolution.Thisisanon-linearleastsquaresproblemwhichwesolveusingtheLevenberg-Marquardtalgorithm.Eachiterationstepisoftheform(18)WhereΦarealltheparameters,rtheresidualsand.Weencodeourpriorbeliefabouttheparameterchangesinthe(diagonal)covariancematrix(19)Thisissetsuchthatthestandarddeviationofanglesisandfocallengths(whereisthemeanofthefocallengthsestimatedsofar).Thishelpsinchoosingsuitablestepsizes,andhencespeedingupconvergence.Forexample,ifasphericalcovariancematrixwereused,achangeof1radianinrotationwouldbeequallypenalisedasachangeof1pixelinthefocallengthparameter.Finally,theparameterisvariedateachiterationtoensurethattheobjectivefunctionofequation16doesinfactdecrease.Thederivativesarecomputedanalyticallyviathechainrule,forexample(20)where(21)and(22)(23)FastSolutionbyDirectComputationoftheLinearSystemSincethematrixissparse,formingbyexplicitlymultiplyingbyitstransposeisinefficient.Infact,thiswouldbethemostexpensivestepinbundleadjustment,costingO()foranmatrix(MistwicethenumberofmeasurementsandNisthenumberofparameters).Thesparsenessarisesbecauseeachimagetypicallyonlymatchestoasmallsubsetoftheotherimages.ThismeansthatinpracticeeachelementofcanbecomputedinmuchfewerthanMmultiplications(24)i.e.,theinversecovariancebetweencamerasanddependsonlyontheresidualsoffeaturematchesbetweenand.Similarly,neednotbecomputedexplicitly,butcanbecomputedvia(25)Inbothcaseseachsummationwouldrequiremultiplicationsifeachfeaturematchedtoeverysingleimage,butinpracticethenumberoffeaturematchesforagivenimageismuchlessthanthis.HenceeachiterationofbundleadjustmentisO,whichisthecostofsolvingthelinearsystem.Thenumberofparametersis4timesthenumberofimages,andtypicallyisaround100timeslargerthan.5.AutomaticPanoramaStraighteningImageregistrationusingthestepsofsections2-4givestherelativerotationsbetweenthecameras,butthereremainsanunknown3Drotationtoachosenworldcoordinateframe.IfwesimplyassumethatR=Iforoneoftheimages,wetypicallyfindawavyeffectintheoutputpanorama.Thisisbecausetherealcamerawasunlikelytobeperfectlylevelandun-tilted.Wecancorrectthiswavyoutputandautomaticallystraightenthepanoramabymakinguseofaheuristicaboutthewaypeopletypicallyshootpanoramicimages.Theideaisthatitisrareforpeopletotwistthecamerarelativetothehorizon,sothecameraXvectors(horizontalaxis)typicallylieinaplane(seefigure4).ByfindingthenullvectorofthecovariancematrixofthecameraXvectors,wecanfindthe“up-vector〞u(normaltotheplanecontainingthecameracentreandthehorizon)(26)Applyingaglobalrotationsuchthatup-vectorisvertical(intherenderingframe)effectivelyremovesthewavyeffectfromoutputpanoramasasshowninfigure4.Figure3.Findingtheup-vectoru.Agoodheuristictoalignwavypanoramasistonotethatpeoplerarelytwistthecamerarelativetothehorizon.Hencedespitetilt(b)androtation(c),thecameraXvectorstypicallylieinaplane.Theup-vectoru(oppositetothedirectionofgravity)isthevectornormaltothisplane.(a)Withoutautomaticstraightening(b)WithautomaticstraighteningFigure4.Automaticpanoramastraightening.Usingtheheuristicthatusersrarelytwistthecamerarelativetothehorizonallowsustostraightenwavypanoramasbycomputingtheup-vector(perpendiculartotheplanecontainingthehorizonandthecameracentre).6.GainCompensationInprevioussections,wedescribedamethodforcomputingthegeometricparameters(orientationandfocallength)ofeachcamera.Inthissection,weshowhowtosolveforaphotometricparameter,namelytheoverallgainbetweenimages.Thisissetupinasimilarmanner,withanerrorfunctiondefinedoverallimages.Theerrorfunctionisthesumofgainnormalisedintensityerrorsforalloverlappingpixels(27)where,arethegains,andistheregionofoverlapbetweenimagesand.Inpracticeweapproximatebythemeanineachoverlappingregion(28)Thissimplifiesthecomputationandgivessomerobustnesstooutliers,whichmightariseduetosmallmisregistrationsbetweentheimages.Also,sinceisanoptimalsolutiontotheproblem,weaddapriortermtokeepthegainsclosetounity.Hencetheerrorfunctionbecomes(29)whereequalsthenumberofpixelsinimagethatoverlapinimage.Theparameter