CN101379513A

CN101379513A - 视频对准和图像序列缝合

Info

Publication number: CN101379513A
Application number: CNA2006800286445A
Authority: CN
Inventors: C·保尔; D·斯蒂里; R·泽里斯基
Original assignee: Microsoft Corp
Current assignee: Microsoft Technology Licensing LLC
Priority date: 2005-08-04
Filing date: 2006-08-03
Publication date: 2009-03-04
Anticipated expiration: 2026-08-03
Also published as: EP1920385A2; EP1920385B1; WO2007019409A9; WO2007019409A2; WO2007019409A3; US7460730B2; CN101379513B; US20070031062A1; EP1920385A4

Abstract

“关键帧缝合器”提供了一种通过对准或排列视频帧来构造镶嵌全景表示来构建镶嵌全景图像的有效技术。通过从每个图像帧提取特征点以及匹配图像对之间的这些特征点，进行图像对之间的匹配。此外，关键帧缝合器通过利用视频中固有的排序信息，在匹配图像对时保留了图像缝合的精确性。通过根据计算出的图像－图像重叠标识关键帧来降低搜索图像帧之间的匹配的成本。关键帧然后被匹配到所有其它关键帧，但中间图像帧仅匹配到时间上相邻的关键帧和相邻的中间帧，以构造“匹配结构”。然后从该匹配结构估计图像定向，并用于构造镶嵌。通过用代表性测量替代特征点的组可压缩图像对之间的匹配以降低计算开销。

Description

视频对准和图像序列缝合

背景

技术领域

本发明涉及镶嵌式全景图像的构造，尤其涉及用于构建图像对应关系的“匹配”结构的技术，该结构被优化以排列图像，用于将大量图像“对准”到具有静态和/或动态组成部分的基础全景表示。

相关技术

一般来说，镶嵌全景图像是通过组合多个重叠的图像帧以生成全景而在一个或多个维度中被扩展的图像。结果，全景图像的尺寸一般比常规的图像捕获设备(如数字照相机或摄像机)能够在单个图像帧中所捕获的尺寸大。

已经开发了若干常规技术用于生成这种全景图像。例如，基本方法是仅仅拍摄多幅常规的摄影或视频图像以便覆盖所希望的取景空间的全部。然后使用若干常规的图像“镶嵌”或“缝合”算法，将这些图像排列并合成为完整的全景图像。

例如，一个传统的镶嵌方案展示了如何能够自动地识别和缝合包含在一组无序图像中的全景。这些技术允许用户用照相机拍摄若干图像，识别来自同一全景的图像群集，然后将各群集缝合成全景。例如，一种此类方案首先比较图像对中的“点特征”，以生成匹配网格。使用连通分量方法来识别独立的全景。通过使得测量误差最小化来排列每个群集中的图像。最后，每个群集中的图像被扭曲到一合成表面并被混合，以生成输出全景。

当运用于相对较小的数据集时，例如由数字照相机所捕获的图像群集，许多常规的镶嵌方案能够迅速地缝合相关的图像帧以生成镶嵌图像。然而，当数据集变得非常大时，镶嵌图的生成变为更为复杂的处理。例如，利用照相机，用户一般仅仅拍摄几幅或几十幅图像来创建全景。然而，利用摄像机，就容易在很短的时间段内生成成百上千幅图像。例如，以每秒仅30帧的典型视频速度，仅一分钟内就会生成总共1800个图像帧。

不幸的是，许多镶嵌方案所执行的匹配技术对于匹配如此大量的图像来生成这些图像的单个镶嵌全景来说常常是不切实际的。因此，已经作了努力来提供缝合或镶嵌诸如视频记录之类的更大数据集的有效技术。虽然从视频中缝合全景的概念并非是新的，但是构造这些镶嵌的方法、所采用的基础照相机运动模型、以及算法的细节显著不同。

例如，用于从视频序列生成镶嵌图像的一种常规方法对图像分辨率增强应用使用随接收到的视频帧而变的仿射运动模型。另一种常规的视频镶嵌方案使用八参数透视变换模型。又一种常规的视频镶嵌方案使用“流形投影”(manifold projection)方法与简单的仅平移(translation only)照相机运动模型的组合。该方法导致了用于视频缝合的快速算法，其中使用来自基础场景的像素窄带来形成合成的全景图像。此外，对仅平移照相机模型的使用避免了对计算更为复杂的3D照相机运动的必要性，而这正是许多常规镶嵌方案所做的。

其它常规的视频缝合方案通过一开始仅把视频序列的相邻帧缝合在一起来操作，从而使得匹配问题在图像数量上线性化。然而，此类技术忽略由于照相机在其路径上交叉返回而造成的匹配。通过不包含这些匹配，全景的组成部分可能由于误差累积而漂移。然而，一些常规的镶嵌方案通过将匹配处理和排列处理交错来部分地补偿该问题。具体来说，在每个新的图像被排列到其时间邻居后，空间邻居被识别并用于改进该新图像的定向估计。

另一种从运动分析中生成图像结构的常规的镶嵌方案采用类似的交错的匹配策略。在其它常规的“从运动中构造”(structure from motion)研究中，为从手持视频序列中提取结构和运动而提出了帧“抽选(decimation)”策略。该策略通过使用锐度测量按照全局运动模型来排序帧以考虑去除，来识别“不必要的”帧避免后续计算。然后使用基于运动相关系数的阈值。在用于“从运动中构造”的使用三焦点张量树的更大的系统中，该策略被作为预处理步骤使用。然而，这些方案的一个问题是只要丢弃“不必要的”图像帧就会丢失数据。

另一种常规的视频镶嵌方案通常是通过在假设时间相邻的图像是空间相邻的条件下将图像匹配和定向估计交错来操作的。该方案还假设照相机路径中的任何环路足够小，使得累积的误差或漂移可被忽略。然而，这些假设可能被认为过于严格，因为它们约束了用户捕获视频记录的能力。此外，该方案不直接处理匹配中的间断，而这会随着同一全景的多个视频而发生。此外，这种匹配和排列的交错要求图像以与视频相同顺序地被排列。

将自动高质量缝合应用于视频序列的另一个问题是与缝合大量图像相关联的相当高的计算成本，以及所造成的使得这些算法以合理的时间运行所需的运动模型的简化或限制性的假设。用于从静态图像以“批量”方式构造大型全景的现有方法可能是相当健壮的。然而，它们对于以合理的时间量排列和缝合高质量视频序列的全部帧来说通常不十分有效。虽然确实存在缝合视频的快速技术，但是这些方法通常使用更为受限的运动模型，且产生的最终全景表示没有基于静态图像的批处理方法精确。

至少一种常规的视频镶嵌方案部分地解决了这些问题中的一些问题。例如，称为“VideoBrush^TM”的一种常规方案提供了从摄像机捕获的图像构造的全景图像的近实时的预览。一般来说，VideoBrush^TM系统提供了使用参数排列的1D和2D视频镶嵌，这包括用近似固定的照相机位置或捕获近似平面场景的任意移动的照相机所捕获的视频。结果，用户在如何捕获视频以便由该常规技术使用方面受到约束。

许多常规镶嵌方案的另一个问题是它们在捕获了整个图像集之后使用记录的图像的前后必然(post-hoc)处理来操作。结果，一个问题是直到在某一将来的时间全景已经被实际生成为止，用户从不实际上毫无疑问地知道已经实现了场景的足够覆盖以确保可从该组捕获的图像帧构造所希望的全景。因而，用户难于看到“正片”(big picture)。

尤其是，使用常规的图像缝合方案，直到图像从照相机上传到计算设备(如PC型计算机等)为止，用户不会发现产生的全景是有缺陷的。例如，如果用户错过了一个或多个地点，全景中会出现间隙。如果缝合程序不能将一个或多个捕获的图像插入到全景中，例如由于图片之间太少的重叠、由于缺少纹理、由于图像聚焦问题(图像太模糊)等等，也会出现间隙。此外，虽然可以通过修剪全景来去除全景边缘处的间隙，但是这会造成修剪边界外的其它想要的图像元素的丢失。最差情况下，希望成为一张全景的图像最终可能成为全部图像的多个不连接的(畸形的)片段。

常规后处理方法的又一个问题涉及“重影”问题，其中在拍摄用于全景的图像时对象已从一个帧移动到下一个帧。虽然用户可能能够使用取景器来识别图片中的缺陷(例如散焦)并重新拍摄，但是在摄影时诸如重影或照明中的差异之类的照片间的缺陷可能不能被发现。不幸的是，当用户注意到这些缺陷时，一般来说重新拍摄错过的或有缺陷的图像帧就太晚了。

通过使用图像间更大的重叠以及通过拍摄被认为受到重影干扰的区域的多个副本，用户能够降低诸如间隙和重影之类的缺陷的风险。然而这种基于冗余的方法在时间上代价高，尤其在存储空间上代价高(因为拍摄了更多的图片)，并且它仍然不能确保成功地生成最终的全景图像。

概述

提供本概述是为了以简化的形式介绍在下面的详细描述中将进一步描述的一部分概念。本概述不意图标识所请求保护的主题的关键特征或必要特征，也不意图被用作为确定所请求保护的主题的范围。

一种“关键帧缝合器”提供了一种通过将图像帧序列对准或排列到基础全景表示来构建镶嵌全景图像的有效技术。由该关键帧缝合器所提供的技术是可缩放的，使得通过对准大量的顺序图像帧(例如由照相机或摄像机或其它图像源捕获的图像序列)能够容易地构造大型全景。此外，在各实施例中，该关键帧缝合器被充分地优化以允许实时地或近实时地缝合图像。因此，用户能够用照相机“掠过”(brush)一场景以便在捕获图像时实时地创建该场景的镶嵌图像。因此，用户还能够通过简单地掠过镶嵌中表现出问题的任何区域来纠正最终全景中的误差或间隙。

一般来说，在一个实施例中，该关键帧缝合器通过从每个新的图像帧中提取“特征”或“兴趣点”来操作，其中第一个图像帧被标识为“关键帧”。每个后续帧然后(通过所述特征)被匹配到前一个帧以及前一个关键帧。每当一估计的帧重叠落在最小重叠阈值之下时，从输入的图像帧标识新的关键帧。可选地，如果已经超过了预定最大数量的帧而没有按照图像帧重叠标识出新的关键帧，则当前帧被标识为新的关键帧。

然后，每个帧还被匹配到下一个或“前向”关键帧。每个关键帧然后被匹配到所有其它关键帧，以构造关键帧“网格”。然后使用图像帧之间、图像帧与关键帧之间以及关键帧之间的所有匹配测量来构造图像“匹配结构：。该匹配结构然后被用于估计图像帧的最优图像定向，然后图像定向被用于从图像帧序列构造图像镶嵌。

换言之，通过构建图像对应关系的“匹配结构”，该匹配结构随后被优化来排列图像，关键帧缝合器允许实时或近实时地排列非常大量的图像帧。注意，在一个实施例中，图像对应关系的优化是使用束调节结束来实现的。此外，在一个实施例中，假设存在有限数量的关键帧，则通过对对应于关键帧对的图像“块”执行增量优化，在捕获图像的同时提供镶嵌图像的“实时”构造。

如上所述，这里所述的关键帧缝合器提供了一种构建静态镶嵌全景图像的有效技术。此外，该关键帧缝合器还能够输出中间“扭曲的”视频帧，这些帧作为“覆盖图”被映射到静态全景。因此，该关键帧缝合器能够对发生在场景内的动作序列构造“动画全景”。在该情况下，用户能够通过全景拍摄一场景来构造“背景全景”。然后，发生在整个镶嵌场景的一特定部分内的任何动作都可被拍摄，并且产生的扭曲的图像可作为覆盖图被插入到静态全景中，从而产生“动画全景”。该选项的一个优点是允许通过创建视频序列的静态部分并且仅仅对发生动作的较小部分生成动画来实现视频图像的大压缩。

根据上述概述，显然这里所述的关键帧缝合器提供了一种用于生成场景的静止和/或动画全景镶嵌图像的独特系统和方法。除了刚才描述的好处之外，通过结合附图阅读下面的详细描述，该关键帧缝合器的其它优点将变得显而易见。

附图说明

本专利或申请文件包含至少一幅彩色图。通过请求和支付必要费用，专利局会提供带有彩色附图的本专利或专利申请公开文件的副本。

参考下面的描述、所附的权利要求以及附图，将更好地理解本发明的具体特点、特征和优点，附图中：

图1是描述构成用于实现这里所述的关键帧缝合器的示例性系统的通用计算设备的总系统图。

图2是描述具有简化的计算和I/O能力的通用计算设备的总系统图，该计算设备与数字照相机或其它图像输入源一起使用来实现这里所述的关键帧缝合器。

图3是描述具有集成的计算和I/O能力以及整合的显示屏的数字照相机的总系统图，用来实现这里所述的关键帧缝合器。

图4例示出表示用于实现这里所述的关键帧缝合器的示例性程序模块的示例性架构系统图。

图5A提供了图像序列，用线条示出了由关键帧缝合器所执行的初始图像匹配序列，其中图像帧被匹配到它们的顺序邻居以及直接前一个关键帧(每个关键帧在此被标识为“KEY”)。

图5B提供了图像序列，除了图5A所例示的匹配之外，还用线条示出了从每个中间帧(非关键帧)对后续的其它关键帧的前向匹配(每个关键帧在此被标识为“KEY”)。

图5C提供了图5B的图像序列，除了图5B所例示的匹配之外，还用线条示出了关键帧之间的匹配(每个关键帧在此被标识为“KEY”)。

图6例示出一示例性的流程图，示出如这里所述的关键帧缝合器的一个实施例的示例性操作流程。

图7例示出使用关键帧缝合器生成的一静态镶嵌全景，其中一动态视频帧的覆盖图被扭曲并映射到静态镶嵌全景以创建动态镶嵌全景。

图8至图13例示出由关键帧缝合器从独特的视频序列中生成的镶嵌全景的各种实例。

图14A例示出在每个图像的一小的角形窗口中具有匹配特征点的一对图像。

图14B例示出图14A的该对图像，示出通过将匹配特征点测量组用相应的代表性测量替代而产生的匹配特征点的压缩。

图15提供了一张图表，例示出对于仅在全部图像对的一小子集之间存在连接的镶嵌图，海赛矩阵(Hessian)H的稀疏图案由具有类似于图15的图表的图案的稀疏矩阵来表示。

图16提供了一张图表，例示出如图15所例示的用于一特定视频序列的Hessian稀疏性可被调整，以便通过将关键帧的参数置换到最后，从而限制在优化操作期间对Hessian进行因子分解时的非零项或填补项的个数，来减少优化图像定向的计算复杂性。

详细描述

在对本发明的较佳实施例的下列描述中，参考附图，附图形成了本文的一部分，并且附图中例示出可实践本发明的具体实施例。要理解，可以使用其它实施例并且可以作出结构上的改变，而不背离本发明的范围。

1.0 示例性操作环境：

图1、图2和图3例示出可实现这里所述的“关键帧缝合器”的各种实施例的合适的计算环境的各种例子。

例如，图1例示出通用计算系统环境100的示例。计算系统环境100仅为合适的计算环境的一个示例，并非对本发明的使用范围或功能提出任何局限。也不应将计算环境100解释为对示例性计算环境100中例示出的任一组件或其组合具有任何依赖性或要求。

本发明可以使用许多其它通用或专用计算系统环境或配置来操作。可适用于本发明的众所周知的计算系统、环境和/或配置的示例包括但不限于，个人计算机、服务器计算机、诸如蜂窝电话和PDA之类的手持式、膝上型或移动式计算机或通信设备、多处理器系统、基于微处理器的系统、机顶盒、可编程消费电子设备、网络PC、小型机、大型计算机、包括任一上述系统或设备的分布式计算环境等等。

可在诸如程序模块等由计算机执行的计算机可执行指令的一般上下文中结合包括麦克风阵列198的组件的硬件模块一起描述本发明。一般而言，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等等。还可在分布式计算环境中实践本发明，在分布式计算环境中，任务由通过通信网络链接的远程处理设备来执行。在分布式计算环境中，程序模块可以位于包括存储器存储设备的本地和远程计算机存储介质中。参考图1，用于实现本发明的示例性系统包括采用计算机110形式的通用计算设备。

计算机110的组件可包括但不限于，处理单元120、系统存储器130以及将包括系统存储器130的各种系统组件耦合至处理单元120的系统总线121。系统总线121可以是若干种类型的总线结构中的任一种，包括存储器总线或存储器控制器、外围总线以及使用各种总线架构的任一种的局部总线。作为示例而非限制，这类架构包括工业标准架构(ISA)总线、微通道架构(MCA)总线、增强型ISA(EISA)总线、视频电子技术标准协会(VESA)局部总线、以及外围部件互连(PCI)总线(也称为夹层(Mezzanine)总线)。

计算机110通常包括各种计算机可读介质。计算机可读介质可以是可由计算机110访问的任一可用介质，包括易失性和非易失性介质、可移动和不可移动介质。作为示例而非限制，计算机可读介质可包括计算机存储介质和通信介质。计算机存储介质包括以用于储存诸如计算机可读指令、数据结构、程序模块或其它数据等信息的任何方法或技术实现的易失性和非易失性、可移动和不可移动介质。

计算机存储介质包括但不限于：RAM、ROM、PROM、EPROM、EEPROM、闪存或其它存储器技术；CD-ROM、数字通用盘(DVD)或其它光盘存储；磁盒、磁带、磁盘存储或其它磁存储设备；或可以用来储存所希望的信息并可由计算机110访问的任何其它介质。通信介质通常将计算机可读指令、数据结构、程序模块或其它数据体现在诸如载波或其它传输机制等的已调数据信号中，并包括任何信息传送介质。术语“已调数据信号”指以对信号中的信息进行编码的方式设置或改变其一个或多个特征的信号。作为示例而非限制，通信介质包括如有线网络或直接连线连接之类的有线介质，以及如声、RF、红外和其它无线介质之类的无线介质。

系统存储器130包括易失性和/或非易失性存储器形式的计算机存储介质，如只读存储器(ROM)131和随机存取存储器(RAM)132。包含如在启动期间帮助在计算机110内的元件之间传输信息的基本例程的基本输入/输出系统133(BIOS)通常储存在ROM 131中。RAM 132通常包含处理单元120立即可访问和/或当前正在操作的数据和/或程序模块。作为示例而非限制，图1例示出了操作系统134、应用程序135、其它程序模块136和程序数据137。

计算机110也可包括其它可移动/不可移动，易失性/非易失性计算机存储介质。仅作为示例，图1例示出对不可移动、非易失性磁介质进行读写的硬盘驱动器141，对可移动、非易失性磁盘152进行读写的磁盘驱动器151，以及对如CD ROM或其它光介质之类的可移动、非易失性光盘156进行读写的光盘驱动器155。可以在示例性的操作环境中使用的其它可移动/不可移动，易失性/非易失性计算机存储介质包括但不限于：磁带盒、闪存卡、数字通用盘、数字视频带、固态RAM、固态ROM等等。硬盘驱动器141通常通过如接口140之类的不可移动存储器接口连接到系统总线121，磁盘驱动器151和光盘驱动器155通常通过诸如接口150之类的可移动存储器接口连接到系统总线121。

上文讨论并在图1中例示出的驱动器及其相关联的计算机存储介质为计算机110提供了计算机可读指令、数据结构、程序模块和其它数据的存储。例如，在图1中，例示出硬盘驱动器141储存操作系统144、应用程序145、其它程序模块146和程序数据147。注意，这些组件可以与操作系统134、应用程序135、其它程序模块136和程序数据137相同或不同。这里对操作系统144、应用程序145、其它程序模块146和程序数据147给予不同的标号是为了说明至少它们是不同的副本。用户可以通过如键盘162和定点设备161(通常指鼠标、轨迹球或触摸垫)之类的输入设备向计算机110输入命令和信息。

其它输入设备(未示出)可包括操纵杆、游戏垫、圆盘式卫星天线、扫描仪、无线电接收机、电视机或广播视频接收机等等。这些和其它输入设备通常通过耦合至系统总线121的有线或无线用户输入接口160连接至处理单元120，但是也可以通过如并行端口、游戏端口、通用串行总线(USB)或IEEE 1394接口、蓝牙(Bluethooth^TM)无线接口、IEEE 802.11无线接口之类的常规接口和总线结构连接。此外，计算机110还可包括如麦克风或麦克风阵列198之类的语音或音频输入设备，以及通过音频接口199连接的扬声器197或其它声音输出设备，音频接口199同样包括如并行、串行、USB、IEEE 1394、蓝牙之类的常规有线或无线接口。

监视器191或其它类型的显示设备也通过如视频接口190之类的接口连接至系统总线121。除了监视器191之外，计算机还可包括其它外围输出设备，如打印机196，它们可通过输出外围接口195连接。

此外，计算机110还可包括能够捕获图像序列193的照相机(如数字/电子照相机或摄像机、胶片/照片扫描仪)作为输入设备。此外，虽然仅描绘了一个照相机192，但是可包括多个各种类型的照相机作为计算机110的输入设备。对多个照相机的使用提供了同时或顺序地捕获图像的多幅视图的能力，以捕获三维或深度图，或捕获场景的全景图。来自一个或多个照相机192的图像193通过使用包括例如USB、IEEE 1394、蓝牙、IEEE 802.11等的常规有线或无线接口而输入到计算机110。该接口连接到系统总线121，从而允许图像193被发送到并存储于RAM132或与计算机110相关联的任何上述其它数据存储设备中。然而，注意也可从任何上述计算机可读介质将先前存储的图像数据输入到计算机110，而不直接要求使用照相机192。

计算机110可以使用到如远程计算机180的一个或多个远程计算机的逻辑连接而在网络化环境中操作。远程计算机180可以是个人计算机、服务器、路由器、网络PC、对等设备或其它常见的网络节点，并通常包括上述相对于计算机110所描述的许多或所有元件，尽管在图1中仅示出了存储器存储设备181。图1中描绘的逻辑连接包括局域网(LAN)171和广域网(WAN)173，但也可包括其它网络。这类联网环境常见于办公室、企业范围计算机网络、内联网以及因特网。

当在LAN网络环境中使用时，计算机110通过网络接口或适配器170连接到LAN 171。当在WAN网络环境中使用时，计算机110通常包括调制解调器172或用于在如因特网之类的WAN 173上建立通信的其它手段。调制解调器172可以是内置或外置的，它通过用户输入接口160或其它适当的机制连接至系统总线121。在网络化环境中，相对于计算机110所描述的程序模块或其部分可储存在远程存储器存储设备中。作为示例而非限制，图1例示出远程应用程序185驻留在存储器设备181上。可以理解，示出的网络连接是示例性的，也可以使用在计算机之间建立通信链路的其它手段。

参考图2，该图示出了表示与数字照相机或摄像机耦合的简化计算设备的总系统图。此类计算设备通常在具有至少某些最小计算能力以及通信接口的设备中。可适用于本发明的已知的简化计算设备、环境和/或配置的示例包括但不限于：手持式、膝上型或移动式计算机，诸如蜂窝电话和PDA之类的通信设备等等。

应注意到，图2中以虚线或短划线表示的任何框表示这里所描述的简化计算设备的替换实施例，并且如下所述的这些替换实施例中的任何或全部都可与贯穿整个文本所描述的其它替换实施例一起结合使用。

至少，为了使得计算设备能够实现“关键帧缝合器”(Keyframe Stitcher)(下文详细描述)，计算设备200必需具有某种最小计算能力以及用于连接数字照相机290或其它图像输入源的有线或无线接口240。

特别是，如图2所示，计算设备200的计算能力一般由处理单元210(大致类似于上文参考图1所描述的处理单元120)和系统存储器220例示出。注意，与图1的通用计算设备的处理单元120形成对比，图2所例示的处理单元210可以是诸如DSP、VLIW处理器或其它微控制器之类的专用(或廉价)微处理器，而不是上述PC型计算机等之类的通用处理器单元。

此外，图2的简化的计算设备200还可包括其它组件，例如用于一个或多个输入设备240(类似于参考图1所述的输入设备)的连接。图2的简化的计算设备还可包括其它可选的组件，例如一个或多个输出设备250(类似于参考图1所述的输出设备)，例如外部显示设备280。最后，图2的简化的计算设备还可分别包括可移动和/或不可移动存储设备260和270(类似于参考图1所述的存储设备)。

最后，参考图3，该图是描绘具有集成的计算340和I/O能力345以及诸如LCD屏幕之类的显示设备310的数字照相机300的总系统图，用于实现这里所述的关键帧缝合器。

一般来说，如本领域技术人员所已知的那样，常规的数字照相机除了可移动325或不可移动330的照相机存储器320之外，还包括诸如上述描述的那些组件(如I/O、计算、以及显示器)。这些照相机还包括镜头305和一组一个或多个控制器315。此外，如同参考图2所描述的简化的计算设备一样，数字照相机的计算能力340可使用诸如DSP、VLIW处理器或其它微控制器之类的低成本专用处理器，而不是上述参考图1所述的PC型计算机等之类的通用处理器单元。如下文中进一步详细描述的那样，这些组件组合使用以允许在独立的数字照相机中实现关键帧缝合器的实时功能。

已经描述了示例性的操作环境，本说明书的剩余部分将致力于具体实施“关键帧缝合器”的程序模块和处理的讨论。

2.0 引言：

“关键帧缝合器”提供了一种用于通过将图像帧序列对准或排列到基础全景表示来构建镶嵌全景图像的有效技术。该关键帧缝合器所提供的技术是可缩放的，使得通过对准大量的顺序图像帧(例如由照相机或摄像机或其它图像源捕获的图像序列)能够容易地构造大型全景。此外，在各种实施例中，该关键帧缝合器被充分地优化以允许实时地或近实时地缝合图像。因此，用户能够用照相机“掠过”(brush)一场景以在捕获图像时实时地创建该场景的镶嵌图像。

应注意，该关键帧缝合器的这些实时实施例可在具有用于在创建时呈现镶嵌全景图像的整合显示器的独立摄像机内实现。类似地，该关键帧缝合器可在直接耦合至数字照相机或通过单独的计算设备耦合至数字照相机的外部显示设备上实现。然而，在这些情况中的每一种情况中，这里所述的关键帧缝合器实质上以相同的方式工作。

因此，虽然此处将该关键帧缝合器一般地描述为在诸如捕获图像序列之后执行图像序列的后处理的PC型计算机之类的计算设备内实现，但是应理解这里所提供的关键帧缝合器的详细描述同样适用于涉及外部显示设备和/或外部计算设备、或其中直接实现关键帧缝合器的照相机的其它实施例，以便提供镶嵌全景的实时生成。

2.1 系统综述：

如上所述，这里所述的关键帧缝合器提供了一种有效的图像镶嵌技术，它允许从场景的一组图像中进行图像序列的实时或离线缝合以生成镶嵌全景，并允许动画镶嵌全景的生成。

一般来说，在一个实施例中，该关键帧缝合器执行用于对准和排列图像以生成镶嵌的下列步骤：

1.首先，该关键帧缝合器从每个新的图像帧提取“特征”或“兴趣点”，其中第一个图像帧和最后一个图像帧被标识为“关键帧”。

2.每个后续帧(通过所述特征)被匹配到前一个帧以及直接前一个关键帧。

3.每当一估计的帧重叠落在最小重叠阈值之下时，从输入的图像帧标识新的关键帧。

a.可选地，如果已经超过了预定最大数量的帧而没有按照图像帧重叠标识出新的关键帧，则当前帧被标识为新的关键帧。

4.每个帧还被匹配到下一个或“前向”关键帧。

5.每个关键帧然后被匹配到所有其它关键帧，以构造关键帧“网格”。

6.然后使用图像帧之间、图像帧与关键帧之间以及关键帧之间的所有匹配测量(即“匹配结构”)来估计图像帧的最优图像定向(包括缩放、扭曲、旋转等)，然后图像定向被用于从图像帧序列构造图像镶嵌。

注意，在从图像帧的估计的最优定向构造图像镶嵌的过程中，使用常规的图像缝合技术来组合重叠的图像段，常规技术包括例如常规的混合、羽化(feathering)、对比度和亮度调整、去重影操作等。

如上所述，在一个实施例中，该关键帧缝合器用于生成“动画镶嵌”，其中生成静态镶嵌背景，并且在对应于整个镶嵌的子区域的其它帧序列内发生的动态照片(action shot)被扭曲及映射到整个镶嵌上，以生成静态和动态组成部分都混合到整个镶嵌全景中的“动画全景”。

在该实施例中，照相机一般对场景进行全景拍摄，以构造“背景”镶嵌，接着是来自整个镶嵌的子部分内的一个或多个“动态照片”。然而，在该情况下，对动态照片的额外帧的处理稍微不同于上述用于构造静态镶嵌全景的一般方法。

特别是，动画镶嵌全景的静态背景是以与上述完全相同的方式构造的。然而，“活的”帧(即“动态照片”)序列然后作为动态覆盖图被添加到静态镶嵌上，以便通过将每个动态照片仅仅对准到镶嵌全景的“关键帧网格”而不是对准到整个“匹配结构”来创建动画镶嵌。使用对关键帧网格的对准而不是对整个匹配结构的对准的一个原因是由于发生在表示动态照片的帧序列内的“动作”，很可能动态照片的帧不会很好地匹配关键帧之间的中间帧。

注意，在“对准”动态照片的帧时，这些帧被按需扭曲、缩放、旋转等，以适合于整个镶嵌。此外，如同上述静态镶嵌的生成一样，在将动态照片的帧对准到整个镶嵌之后，使用常规的图像缝合技术来组合重叠的图像段，这些常规技术包括例如常规的混合、羽化、对比度和亮度调整、去重影操作等。

最后，在又一实施例中，如上所述，该关键帧缝合器被用于提供实时或近实时图像缝合，以便在用户在一场景上移动照相机时生成镶嵌全景。在该情况下，为了在构造镶嵌全景之前生成完整的匹配结构，不是处理整个视频流，而是对对应于相邻关键帧对的图像“块”估计最优图像定向，以提供镶嵌图像的近实时的递增构造。

该实施例的一个优点是它允许在图像被捕获时向用户显示镶嵌全景的近实时显示。例如，当用户在场景上用摄像机或照相机全景拍摄，并捕获该场景的图像时，可以在该数字照相机或摄像机的LCD型显示屏或取景器上实时显示相应的镶嵌全景。显然，该实时实施例也可在耦合到照相机的外部显示设备上实现，该外部显示设备可直接耦合到照相机或通过耦合照相机的外部计算设备来耦合。

然而，就镶嵌全景的生成而言，该关键帧缝合器的这些实施例中的每一个都以相同的方式工作，唯一不同在于用于该目的的硬件和硬件连接。因此，出于解释的目的，对关键帧缝合器的下述讨论将假设在具有来自活的或记录的照相机输入的视频流输入源的PC型计算机中实现关键帧缝合器。然而，应理解这里所述的关键帧缝合器意图涵盖上述实施例和实现方式中的每一个。

2.2 系统架构综述：

图4的总系统图例示出上面概括的处理。特别是，图4的系统图例示出用于实现这里所述的关键帧缝合器的程序模块之间的相互关系。

应注意，图4中以虚线或短划线表示的框以及框之间的互连表示这里所述的关键帧缝合器的替换实施例，如下所述，这些替换实施例的任何或全部都可可与贯穿整个文本所描述的其它替换实施例一起结合使用。此外，还应注意出于解释清楚的目的，图5中所例示的关键帧缝合器示出照相机或图像源400在关键帧缝合器的整个系统的外部。然而，如上所述，在各种实施例中，图4中所例示的某些或全部组件和程序模块可整合到照相机400中。

一般来说，如图4所例示的那样，该关键帧缝合器一般通过将直接来自照相机或摄像机或其它图像输入源的图像提供给图像帧输入模块405来开始操作，图像帧输入模块405保存图像文件410供关键帧缝合器使用。可选地，关键帧缝合器可对一组预先记录的图像文件410(诸如视频记录或其它图像序列)操作。

一旦图像文件410可用于关键帧缝合器，特征点提取模块415就分析每个图像帧并从每个图像帧提取一组图像特征。这些提取的特征然后被提供给匹配结构构造模块420，后者的作用是标识图像410中的关键帧并构建“匹配结构”425，匹配结构一般表示：1)关键帧之间的对应关系(即“关键帧网格”)、2)相邻关键帧之间的中间帧之间的对应关系、以及3)中间帧与这些中间帧任一侧上的相邻关键帧之间的对应关系。

一般来说，上述特征点提取模块415通常会从每个图像提取几百个特征，产生具有大的重叠的匹配图像对之间的数百个匹配(因此为实质上更大的“匹配结构”)。如果匹配的特征良好地分布在图像上，这就强有力地约束了图像的相对定向。然而，大量的测量对于许多图像序列来说是计算瓶颈。因此，在一个实施例中，如在第3.5节中进一步详细描述的那样，匹配结构构造模块用少得多的数量的“代表性测量”来替代图像对之间的测量，以减少生成图像镶嵌所需的计算开销。

在任一种情况中，一旦完成了匹配结构425，它就被提供给定向优化模块430，后者分析匹配结构以确定每个图像的最优“定向”433。一般来说，这些最优定向433表示“照相机定向”的估计，例如焦距、照相机旋转等。

这些定向433然后被转换回图像，供镶嵌构造模块435使用，后者使用定向433通过按需旋转、缩放、扭曲图像以适合于镶嵌来“对准”图像410。具体来说，给定最优图像定向433，镶嵌构造模块435按照最优图像定向从图像帧410构建镶嵌全景440。注意，在一个实施例中，镶嵌构造模块对镶嵌440的构造还包括使用常规图像混合技术，包括例如羽化、对比度和亮度调节、去重影操作等。

一旦镶嵌构造模块435完成了镶嵌440，在各个实施例中，镶嵌440仅被存储用于稍后使用、显示在常规显示设备445上、或供回给用于捕获图像的数字照相机或摄像机400的显示器，供镶嵌的实时预览使用。

如上所述，在一相关实施例中，关键帧缝合器提供镶嵌全景的实时生成，使得用户能够在耦合到他们的照相机或与他们的照相机集成的显示设备上正确地看到完成的全景将会是什么样。在该实施例中，镶嵌的构造如上所述地进行。然而，不是一次处理整组图像帧410，而是当图像帧被接收时(诸如从实时照相机400输入)，通过处理以两个直接相邻的关键帧为界的中间图像帧的“块”来处理图像帧。因此，实时镶嵌图像的生成的最大延迟大约为从一个关键帧到下一个关键帧的时间段。

在另一个实施例中，同样如上所述，关键帧缝合器构建既具有静态组成部分又具有动态组成部分的动画全景。一般来说，一旦已经通过镶嵌构造模块435构造了基础镶嵌，则通过帧扭曲/映射模块450将表示“动态照片”的额外的顺序图像帧对准到匹配结构425的关键帧网格部分。

具体来说，如同基础镶嵌的生成一样，通过定向优化模块430计算表示动态照片的图像帧410的最优定向433。然而，这些动态照片定向433仅是相对于匹配结构425的关键帧网格部分而不是相对于整个匹配结构被计算的。这些动态照片定向433然后由帧扭曲/映射模块450使用，以便通过按需旋转、缩放、扭曲图像以适合于镶嵌来对准表示动态照片的图像410。

最后，动画镶嵌生成模块455使用常规图像缝合技术，通过运用常规的混合、羽化、对比度和亮度调节、去重影操作等，以逐帧的方式，将动态照片的对准的图像帧覆盖到基础镶嵌上。所得的动画镶嵌然后被储存440以供稍后需要时使用，或提供以便经由显示设备445来回放。

此外，应注意到不同于表示用于构造镶嵌440的全部帧的单个合成的基础镶嵌，由动画镶嵌模块455生成的动画镶嵌将按照帧的顺序映射产生按顺序示出动态照片的每个帧的动画。换言之，动画镶嵌在基础镶嵌上顺序地示出动态照片的每个帧，同时在基础镶嵌上示出动态照片的下一个顺序帧之前从基础镶嵌中去除动态照片的每个帧。

注意，用于生成动画镶嵌的该相同的技术可用于提供视频序列的压缩，即构造视频序列的不活动的或静态部分的单个静态镶嵌，然后以上述相同的方式将视频序列的活动或动态部分提取并映射到基础静态镶嵌。在此情况下，用于构造基础镶嵌的帧中的冗余信息被简单地丢弃了，并且仅表示所提取的动态照片的动态元素与基础镶嵌一起被保存。结果，相对于原始视频序列，产生的动画镶嵌可提供相当大的压缩率，这取决于原始视频序列的内容。注意，视频序列的动态区域的标识和提取是本领域技术人员熟知的概念，这里将不详述。

3.0 操作综述：

上述程序模块被用来实现这里所述的关键帧缝合器。如上所概括的那样，该关键帧缝合器提供一种有效的图像镶嵌技术，它允许从一场景的一组图像中进行图像序列的实时缝合以生成镶嵌全景，并允许动画镶嵌全景的生成。下面的小节提供了关键帧缝合器的操作以及用于实现第2节中描述的程序模块的示例性方法的详细讨论。

特别是，下面的小节提出了一种将可能数千个视频帧对准和缝合到大型全景镶嵌的自动且有效的方法。由关键帧缝合器所提供的这些技术保留了图像缝合器的稳健性和精确性，它匹配全部的图像对，同时利用视频记录中固有的排序信息。在一个实施例中，通过根据图像—图像重叠的量自适应地标识关键帧来降低搜索视频帧之间的匹配的计算成本。关键帧被匹配到所有其它关键帧，但是关键帧之间的中间视频帧仅匹配到时间上相邻的关键帧和其它相邻的中间帧。然后从该稀疏的匹配集中估计图像定向。此外，在另一实施例中，通过用单个代表性测量来替代图像中的小窗口内的测量来压缩图像对之间的匹配，从而以最小的精确性损失在相当程度上减少了估计图像定向所需的时间。

3.1 全景取景器的操作细节：

下面的段落详细描述了这里所述的关键帧缝合器的具体操作实施例。特别是，下面的段落描述了与关键帧缝合器一起使用的照相机和输入图像；操作考虑因素；特征提取和图像匹配；有效的匹配结构；匹配结构压缩；以及计算开销。

3.2 照相机和图像或视频流：

如上所述，在一个实施例中，关键帧缝合器被实现在具有足够集成的计算能力来生成实时镶嵌预览的数字照相机或摄像机内。然而，除了在数字照相机或摄像机内实现全景取景器之外，众多常规的照相机类型或视频馈送源中的任一种都可与全景取景器组合使用。

实际上，可使用能够与外部计算设备对接并扩展到关键帧缝合器的任何数字照相机或视频流馈送源。此外，许多较新的照相机或摄像机可直接连接到计算机的现有端口(USB接口、IEEE 1394接口、蓝牙无线接口、IEEE 802.11无线接口等)。任何此类照相机可由关键帧缝合器使用。

此外，如果关键帧缝合器的功能没有整合到照相机，则可在具有足够计算能力的任何计算设备上将关键帧缝合器实例化，与如同关键帧缝合器实现在用于镶嵌全景的实时生成的数字照相机内一样。例如，用户可以使用连接到台式、笔记本或手持式计算设备的常规的“网络摄像头”(web cam)等(不具有整合的计算能力)，以如同用具有集成的关键帧缝合器能力的专用数字照相机进行捕获一样来生成镶嵌全景图像。

然而，如上所述，不是描述连接到用于启用关键帧缝合器的单独的计算设备的外部照相机或图象源的每个可能的组合，而是将在这里将关键帧缝合器一般地描述为实现在用于处理图像序列来生成镶嵌图像的常规计算设备内。然而，应理解，这里给出的关键帧缝合器的详细描述同样适用于涉及集成在数字照相机中、以及耦合到可包括或不包括整合的显示设备或计算能力的照相机的外部计算设备的其它实施例中。

3.3 操作考虑因素：

与许多常规镶嵌技术形成对比，该关键帧缝合器并不从计算考虑因素中排除帧。相反，该关键帧缝合器将中间帧匹配到自适应地选择的关键帧。此外，与要求受限的或受约束的照相机运动的常规视频镶嵌技术形成对比，该关键帧缝合器提供一种有效的镶嵌方法，它一般适用于大量的照相机运动模型，例如2D相似性、3D旋转、仿射扭曲以及完全单应性(full homography)，仅列举了一些此类运动模型。因此，该关键帧缝合器所提供的镶嵌方法可用于获得来自视频序列的数千帧的稳固的、全局一致的排列。

此外，为了允许关键帧缝合器的实时或近实时性能，必须假设在关键帧的总数上存在一有限的界限。一个合理的方式是假设整个镶嵌将适合于本地存储器(即关键帧缝合器不是镶嵌无限的平面，而是镶嵌一旋转的全景或有限范围的平面)。这意味着整个全景可被有限数量的关键帧所覆盖。

在一个实施例中，如上所述，仅当当前帧不按照某一最小阈值量重叠直接前一个关键帧时，才创建新的关键帧。然而，为了确保对于旋转的全景或有限范围的平面总是有有限数量的关键帧，在一密切相关的实施例中，仅当当前帧不按照某一阈值重叠任一先前的关键帧(而非仅仅前一关键帧)时，才创建新的关键帧。

例如，如果用户可以在场景的同一部分上多次来回全景拍摄，就可能有若干关键帧覆盖所产生的镶嵌的相同部分。对于无限数量的图像帧，这意味着关键帧的数量可能无界。然而，为了处理无限数量的图像帧，需要用一常数来对关键帧的数量定界(因为计算成本是关键帧的个数的三次方，如在第3.7节中详细描述的)。

如上所述，对于旋转的全景或对于从有限范围的平面构造的全景来说，对于任何选择的重叠阈值，有限数量的关键帧可以覆盖整个合成表面。因此，可以通过仅在关键帧不按照某一阈值重叠任一其它关键帧(而非仅仅直接前一关键帧)时创建新的关键帧，来给关键帧的数量定界。做此判决的一个简单的方式是简单地检查当前帧和全部关键帧之间的特征点匹配的数量。

此外，在其它实施例中，可通过判断特征点之间的匹配是否在几何上看似可信来使得关键帧缝合器更为健壮。这可以通过在每次添加新的关键帧时重新估计关键帧定向来进行。这还允许实时全景预览的产生。例如，关键帧可被扭曲到合成表面、被混合和被显示。

3.4 特征提取和图像匹配：

在关键帧缝合器的一个测试实施例中，从每个帧提取常规的多尺度定向片(Multiscale Oriented Patches：MOPS)，以便为后续图像匹配提供特征。如本领域技术人员所知，MOPS提供了一种类型的不变特征，它位于离散尺度空间中的哈里斯角(Harris corner)，并使用模糊的局部梯度来定向。通过定义旋转不变帧从图像中提取MOPS，在旋转不变帧中，由偏置/增益归一化强度值的8×8的片组成的特征描述符被采样。使用自适应非最大抑制算法来控制图像中的特征的密度。在一测试实施例中，使用快速最近邻居算法来实现基于MOPS的图像匹配，该算法基于特征的低频哈尔(Haar)小波系数来索引特征。在一个实施例中，使用离群值滤除过程(outlier rejection procedure)根据不正确的特征匹配的背景分布来验证成对的特征匹配。然后使用RANSAC来改进特征匹配。

然而，应注意，存在大量常规特征提取技术用于图像匹配。这里所述的关键帧缝合器适用于大多数这些常规的特征提取技术，并不限于上述对MOPS技术的使用。然而，出于解释的目的，下面的讨论将一般地涉及使用上述MOPS技术从图像中提取特征。

3.5 有效的匹配结构

如上所述，视频序列中的帧的数量可在非常短的时间段内迅速增加到数千图像帧。因此，为了避免匹配全部这些帧对，必须作出关于时间和空间相邻性之间的相关性的假设。然而，任何这些相关性假设应当受到限制，以避免过度约束用户捕获图像序列。此外，关键帧缝合器的一个优点是这里描述的镶嵌框架将排列图像推迟到完成匹配之后，从而允许关键帧缝合器在具有较少的匹配的图像之前用更多的匹配来排列图像，从而提高最终镶嵌的整体质量。

为了保持健壮的镶嵌技术，关键帧缝合器作出的基本假设是大多数时间上相邻的帧同样是空间上相邻的。因此，关键帧缝合器首先寻找全部时间上相邻的图像对之间的匹配。这些对之间的局部匹配随后被用于根据重叠的量(或者在一个实施例中每当帧总数超过预定阈值而没有标识出新的关键帧时)来选择关键帧。为此，关键帧缝合器通过将第一个帧和最后一个帧定义为关键帧来开始。关键帧缝合器然后单步通过视频(或其它图像序列)，将不按某一阈值(或在一测试实施例中为大约50％)重叠最近标记的关键帧的那些帧标记为关键帧。不被标记为关键帧的中间帧被匹配到它们的时间上相邻的关键帧和中间帧。然后通过匹配全部关键帧对来创建“关键帧网格”。

作为该方法的基础的假设是这些相邻的关键帧几乎完全覆盖全景。虽然，一般来说会有全景的某些部分没有被任何关键帧所覆盖且因此会不被匹配。然而，随着重叠阈值被设置得更为严格，这些可能不匹配的区域变得更小。另一方面，如果照相机路径多次越过全景，则若干关键帧可与全景的同一部分相关联。与照相机一次全景拍摄所述全景相比，这会引起在生成关键帧网格时要尝试更多的匹配。因此，用户付出了计算代价来不止一次地覆盖全景。虽然有可能精减那些由于不止一次穿过场景的相同部分而重叠其它关键帧的关键帧，但是关键帧缝合器改为处理所有的帧来增加整个镶嵌处理的精确性。

如上所述，图像的匹配用于构造包括“关键帧网格”的“匹配结构”。一般来说，构造该网格的第一个步骤是标识图像帧序列中的关键帧。在标识这些关键帧时，该序列的第一个帧和最后一个帧被设置为关键帧。整个图像序列然后被评估以标识第一个帧和最后一个帧之间的其余的关键帧(按照帧重叠或者按照中间帧的个数)。一旦标识了关键帧，整个图像序列被评估，如下所详述的那样，以便相对于所标识的关键帧来构造匹配结构。

例如，如图5A所给出的图像帧序列所例示的那样，序列的第一个帧和最后一个帧被标识为关键帧，满足关键帧的任何中间帧也被标识为关键帧(图5A中表示为“KEY”)。如图5A的上部的曲线连线所例示的那样，每个图像帧(包括关键帧)然后被匹配到直接前一个关键帧。此外，如图5A的下部的曲线连线所示，每个图像帧还被匹配到其直接相邻的图像帧。如上所述，匹配是按照从每个图像帧提取的“兴趣点”或“特征”来进行的。

接着，关键帧缝合器通过对图像帧执行“前向匹配”来继续匹配处理。特别是，如图5B的下部曲线连线所例示的那样，在前向匹配期间，每个图像帧(包括关键帧)被匹配到直接前一个关键帧(图5B中表示为“KEY”)。

最后，在构造匹配结构的最后一个步骤中，关键帧缝合器通过将全部关键帧匹配到每一个其它关键帧来生成“关键帧网格”。例如，如图5C的下部曲线连线所例示的那样，在关键帧网格的构造期间，每个关键帧(图5C中表示为“KEY”)被匹配到图像序列中的每个其它关键帧。注意，某些关键帧—关键帧匹配已经按照上述关于图5A和图5B所述的前两个匹配步骤执行了。没有必要重复那些已经计算过的匹配。然而，在明确的关键帧—关键帧匹配步骤之前计算的任何关键帧匹配仍然被包含在单独的关键帧网格中，用于若干目的，包括用于动画全景的动态照片的映射。

上述的匹配结构构造处理可以概括为下述步骤：

1.将第一个和最后一个图像帧标记为关键帧

2.对于每个图像帧：

a.提取特征点

b.匹配到前一个帧

c.匹配到前一个关键帧

d.估计与前一个关键帧的重叠

i.如果重叠太小则标记为关键帧

e.如果太多的图像帧而没有基于重叠的新的关键帧，则任选地标记为关键帧

3.对于每个帧：

a.匹配到下一个或“前向”关键帧

4.对于每个关键帧：

a.匹配到全部其它关键帧

5.任选地压缩构成该匹配结构的匹配测量(下文详述)

6.从匹配结构(或压缩的匹配测量)估计图像定向

该处理总体上例示于图6，图6给出了如这里所描述的关键帧缝合器的一个实施例的示例性操作流程。应注意到图6中以虚线或短划线表示的任何框表示关键帧缝合器的替换实施例，并且如下所述的这些替换实施例中的任何或全部都可与贯穿整个文本所描述的其它替换实施例一起结合使用。

一般来说，如图6所例示的那样，这里所述的关键帧缝合器通过检索预记录的或作为实况输入从摄像机600或其它图像输入源提供的一组图像帧605而开始操作。特别是，关键帧缝合器开始从照相机600或预记录的图像帧605获取下一个图像帧610。

如果图像序列605的当前图像帧是第一个图像帧615，它就被标识620为关键帧625。如果当前帧不是关键帧625，它就被匹配630到前一个图像帧605(可以是也可以不是关键帧)。该匹配信息然后被存储为整个匹配结构635的一部分。接着，当前图像帧被匹配640到前一个关键帧625。同样，该匹配信息然后被存储为整个匹配结构635的一部分。

然后作出关于当前帧和该前一个关键帧之间的计算出的重叠是否在预定阈值645之下的判断。如果重叠位于该阈值645之下，则当前帧被标识650为关键帧625。可选地，如果已经处理了太多的帧而没有根据重叠将新的帧标识为关键帧，则在一个实施例中当前帧被标识650为关键帧625。

一般来说，该匹配过程(630和640)和关键帧标识过程(645、650和655)继续，直到处理了整个图像序列且没有更多的图像帧660为止(最后一个帧也被标识为关键帧650)。然而，在实时处理的情况下，每当当前帧被标识650为关键帧时，该帧就被临时作为“最后一个帧”660来对待，对图像序列的处理继续以完成整个匹配结构635。

特别是，不管整个图像序列605是否已被处理(直到框660)、或者不管是否使用以关键帧对定界的图像帧块的实时处理，通过将每个帧605匹配665到下一个或“前向”关键帧625，匹配结构的构造继续进行。该匹配信息665然后被存储为整个匹配结构635的一部分。注意，从框665到匹配结构635的连接由符号(A)示出以便提供更为清晰的附图。类似地，到图像帧605和关键帧625的连接分别由符号(B)和(C)示出，以便提供更为清晰的附图。

接着，所有关键帧625都被匹配670。在实时处理的情况下，该匹配包括将当前关键帧对相互匹配以及匹配到先前的关键帧或关键帧对(如果有的话)。该匹配信息670然后被存储为整个匹配结构635的一部分。然而，应注意，该特定的匹配信息670还表示用于生成动画镶嵌的上述“关键帧网格”，如下文详述的。注意，从框670到匹配结构635的连接也由符号(A)示出，以便提供更为清晰的附图。

接着，在一个实施例中，整个匹配结构635被压缩(第3.6节详细描述)，以便在从匹配结构635估计680最优图像定向时降低计算开销。

最后，给出估计680的最优图像定向，执行图像605对准和排列(通过缩放、扭曲、旋转等)，以及可选的常规混合、羽化、对比度和亮度调节、去重影操作等，用于构造685镶嵌690，镶嵌690然后被保存供以后使用。此外，在实时镶嵌生成的情况下，在用户捕获图像的同时，镶嵌690以近实时方式被供回照相机600显示器供用户查看。

如下所示，图7至图13提供了各种动画和静态全景的示例。

特别是，图7例示出使用关键帧缝合器生成的静态镶嵌全景700，其中动态视频帧710的覆盖图被扭曲并被映射到静态镶嵌全景以创建动态镶嵌全景。注意，在图7中，动态视频帧710的覆盖图被放大并偏移，其中大的白色箭头指向它要被映射到整个静态镶嵌中的位置。在操作中，该放大和偏移并非是动画镶嵌如何被构造。具体来说，提供该放大和偏移作为动态照片被映射到的位置的例子，因为否则在诸如图7所示的单个图像中将很难清楚地区分作为覆盖图而被扭曲和映射到整个静态镶嵌的帧。

图8和图9例示出从具有大约1000个帧、在大约720×1280像素分辨率下的连续视频序列生成的未修剪的镶嵌全景的示例。类似地，图10(568个镶嵌帧)和图11(568个镶嵌帧)也提供了从单扫描带(swath)(照相机连续扫掠)中捕获的连续视频序列创建的镶嵌的示例。

最后，图12和13例示出从多个单独的扫描带(每种情况中是三个)中捕获的视频序列生成的全景的示例。在每种情况下，多于1000幅的图像被组合以生成每个镶嵌。应注意，在多扫描带的情况下，通过将用于关键帧检测的重叠阈值设置得比时间和空间重叠自然地更为一致的连续扫描带的情况中的低，观察到更佳的结果。

3.6 匹配结构压缩：

一旦在图像对之间已经建立了特征匹配，它们就可用于估计照相机定向。每个特征匹配定义了取决于该对图像的相对定向的测量误差。通过在(健壮的)最小二乘法框架中最小化测量误差来估计相对照相机定向。传统的兴趣点检测器通常会从每个图像提取数百个特征，导致具有大的重叠的匹配的图像对之间的数百个匹配。如果匹配的特征良好地分布在图像中，这强有力地约束了图像的相对定向。然而，大量的测量对于许多图像序列来说是计算瓶颈。

因此，在一个实施例中，关键帧缝合器通过用少得多的“代表性测量”来自动代替一对图像之间的测量来解决该计算瓶颈问题。

例如，如图14A所例示的那样，一对图像1400和1410可具有一组匹配特征点1420和1430，它们分别跨越每幅图像中的小的窗口。注意，图像1400和图像1410之间的特定特征点之间的对应关系通过使用从第一图像中的特征点1420到第二图像中的匹配特征点1430的实连线1440来示出。接着，如图14B所示，根据前面的讨论，图像1400中的该组特征点1420被分析以创建单个代表性测量1450。类似地，同样如图14B所示，图1410中的该组特征点1430被分析以创建单个代表性测量1460。该对代表性测量1450和1460然后用于分别替代相应的一组特征点1420和1430，从而压缩了特征点的总数。注意，虚线1470示出图像1400和1410中代表性特征点1450和1460之间的对应关系。

特别是，在一个实施例中，原始的新的测量都由图像点对和2×2协方差矩阵来表示。新的测量被设置到原始点的质心，并且通过对逆协方差矩阵求和来调整协方差。

通过用更少数量的代表性测量来替代原始测量，关键帧缝合器改变了误差表面的形状，同时显著地降低了计算开销。然而，对于降低的计算成本来说存在精确性的损失。为了最小化精确性损失，仅跨越小部分图像的测量被合并。跨越小的角形窗口的测量拙劣地约束了除平移分量之外的单应性参数。用一组点的质心来表示该组点丢弃了它们在排列图像所需的扭曲的非平移分量上设置的约束。因此，如果一些点具有小的范围(即通过使用小的角形窗口)，仅仅允许这些点合并减少了被丢弃的信息量，并因此使得丢弃此数据所导致的误差最小化。

一般来说，要被合并的测量是通过在任一图像中它们所跨越的窗口大小上设置预定界限来选择的。以一组中的全部测量为开始，关键帧缝合器递归地沿最大轴对齐维度(在任一图像中)分割，直到在两个图像中对全部组都满足所述界限为止。对于每个组，然后在位于该组的质心处的每个图像中创建单个测量。在替换实施例中可以使用更为复杂的技术(k-均值聚集(k-meansclustering))，因为这类技术可能用更少的聚类来满足边界约束。然而，上述的过程执行良好，且一般要求相对少量的计算开销来进行计算。

在一测试实施例中，对于通过用某一范围的边界框尺寸压缩测量来合并测量以及将它们近似为单个点的精确性进行评估。特别是，观察扫描从0％(无压缩)至50％(直到在图像的每个象限中的一个点)的最大边界框尺寸的结果。对三个独特的图像序列运行该扫描。该分析的结果示出相对于计算开销和精确性两者来说，大约20％的窗口尺寸似乎提供了良好的性能结果。注意，利用测试的图像序列，大约20％的窗口尺寸对应于完全重叠的图像之间的大约25个匹配和50％重叠的图像之间的12个匹配。由于仅需要2个测量来估计两个图像之间的旋转和缩放，因此大约20％的窗口尺寸似乎是开始的较佳数字。然而，对于诸如单应性之类的扭曲来说，窗口尺寸可能需要更小，其中要求的匹配的最小数量更多。

显然，存在其它方法来减少每次图像匹配迭代中考虑的测量的数量。例如，在一个实施例中，每个匹配的图像对可被排列，并且对于误差的线性近似然后可被用于创建连接两个图像的单个线性测量。然而，使用若干代表性的2D点(即上述的“代表性测量”)是有好处的。首先，可能保留误差表面的某些非线性性，而不需要在简化表示(使用上述的压缩技术)之前排列图像。其次，已经设计了许多常规技术来加速稀疏非线性最小化代码来估计最优照相机定向。这些用于加速最优照相机定向估计的技术可容易地适用于上述的压缩技术。特别是，这仅仅是在压缩和排列步骤之间匹配测量的问题。

3.7 计算开销

使用上述的匹配结构和压缩的测量，使用二阶非线性技术(例如传统的牛顿-拉夫逊(Newton Raphson)技术)估计将测量误差或目标函数最小化的照相机定向。对于P个图像对且对i之间有M_i个测量，被最小化的目标函数是：

公式1

此处，e_ij是由于对i中的匹配j造成的2D测量误差，

是2×2的测量协方差。e_ij取决于测量ij以及对i中的图像的相对定向。在一个实施例中，关键帧缝合器使用下面的对称扭曲函数：

公式2

其中，w()是扭曲函数，x_ij和

是被扭曲的每个图像中的点，p_i表示扭曲参数的矢量。注意，p_i表示对i中的图像之间的“半途”(halfway)扭曲。此外，在具有单个未知焦距的旋转全景的情况下，这意味着误差是对两个图像之间半途旋转的图像平面计算的，扭曲函数由公式3给出：

w (x_{ij}, {[ω^{T}, f]}^{T}) = π (K (f) R (ω) K^{- 1} (f) [\begin{matrix} x_{ij} \\ 1 \end{matrix}])

公式3

其中，π([x，y，z])^T＝[x/z，y/z]^T，R(ω)是半途旋转矩阵，K(f)是校准矩阵：

K (f) = [\begin{matrix} f & 0 & p_{x} \\ 0 & f & p_{y} \\ 0 & 0 & 1 \end{matrix}]

公式4

注意，单应性、2D相似性、以及仅旋转运动模型导致不同形式的w()。

在目标函数的最小化(即定向优化)的每次迭代中，目标函数的梯度和海赛矩阵(Hessian)g和H分别被计算并用于求解更新步长。对e_ij使用线性近似，g和H由下式给出：

公式5

更新步长d是通过求解下式得出的：

Hd＝-g 公式6

海赛矩阵H是Nd×Nd的稀疏矩阵，其中N是照相机数，d是用于表示每个照相机的参数数量(例如对于旋转照相机来说d＝3)。计算g和H的计算成本对测量数量呈线性，因为公式1中的每个测量项仅依赖于单对图像。

对于全部图像对之间存在测量的全景来说，求解公式6是N的三次方。然而，当全部图像对中的仅一小子集之间存在连接时，H的稀疏图案由具有类似于图15所例示的图表的图案的稀疏矩阵来表示。如本领域技术人员所公知的那样，常规的“束调节”(bundle adjustment)技术可用于利用该H的稀疏性，通过使用LU分解来把求解公式6的计算复杂性降低到仅仅关键帧数的三次方或更小，且对中间帧的数量线性。通过将关键帧的参数改序到最后，能够在对H进行因子分解时限制非零项或填补项的个数。来自用于构造图8的镶嵌的图像序列的经因子分解的Hessian矩阵的稀疏图案的例子示于图16。

换言之，图15示出了来自用于生成图8的镶嵌的图像序列的匹配帧，即相当于Hessian矩阵的稀疏图案。如果在图像i和j之间发现匹配，则点(i，j)被填充。时间邻居匹配显示为沿对角线向下的线。对关键帧的前向和后向匹配显示为对角线上的框，较长的照相机停顿产生较大的框(即更多的特征点匹配，假设照相机以恒定速率记录图像帧)。关键帧对关键帧匹配显示为对角线外的稀疏点。由于照相机缓慢地在图像序列的一个方向中全景拍摄，时间上远离的帧之间的关键帧对关键帧匹配是离群值(outliers)，它们在健壮优化期间被滤除。图16中所示的图表示出了在将关键帧改序到最后之后，经因子分解的Hessian矩阵的稀疏图案。关键帧造成了右下角和右侧上方中的填补项。

匹配的图像对的数量最多是关键帧数量的二次方(如果它们全部彼此重叠)，但是更为通常的是线性的；它对中间帧数量也是线性的。每个图像对的特征匹配的数量在该部分计算成本上是一标量乘数。在许多情况下，对测量的贡献值进行求和的成本超过求解运动参数中的稀疏线性系统的成本。在这些情况下，已经观察到使用特征匹配压缩来减少每图像测量的数量仅以很小的精确性代价换来了相当程度的计算效率。

已经出于说明和描述的目的提出了关于关键帧缝合器的上述描述。这并非是穷举性的，也不是要把本发明限制到所公开的精确形式。根据上述的教导可以作出许多修改和变型。此外，应注意，为了形成关键帧缝合器的其它混合实施例，可以任何组合的方式来使用上述的替换实施例中的任何或全部。本发明的范围不限于本详细说明，而是由所附权利要求书来限定。

Claims

1.一种具有用于自动生成镶嵌图像的计算机可执行指令的计算机可读介质，所述计算机可执行指令包括：

对一场景的一组顺序图像中的每一个图像，标识一组特征点；

从对每个图像所标识的所述一组特征点构造图像对应关系的匹配结构；

通过用代表性测量自动替代所述一组特征点的一个或多个子集来压缩所述匹配结构；

从所述压缩的匹配结构估计最优图像对准；以及

按照所估计的最优图像对准从所述一组图像中构造静态镶嵌图像。

2.如权利要求1所述的计算机可读介质，其特征在于，构造所述图像对应关系的匹配结构还包括：

将所述一组顺序图像的第一个图像帧和最后一个图像帧标识为关键帧；

对于每个图像帧，标识对直接前一图像的特征点匹配；

对于每个图像帧，标识对直接前一关键帧的特征点匹配；

对于每个图像帧，估计与直接前一关键帧的重叠量，并且如果所估计的重叠量位于一预定阈值之下，则将该图像帧设置为新的关键帧；

对于每个帧，标识对直接后一关键帧的特征点匹配；以及

对于每个关键帧，标识对每个其它关键帧的特征点匹配。

3.如权利要求2所述的计算机可读介质，其特征在于，构造所述图像对应关系的匹配结构还包括：对于每个图像帧，估计与全部先前的关键帧的重叠量，并且如果所估计的与全部关键帧的重叠量位于一预定阈值之下，则将该图像帧设置为新的关键帧。

4.如权利要求2所述的计算机可读介质，其特征在于，构造所述图像对应关系的匹配结构还包括：如果已经超过了预定最大数量的图像帧而没有按照所估计的重叠量标识出新的关键帧，则将一图像帧设置为新的关键帧。

5.如权利要求2所述的计算机可读介质，其特征在于，每个所述关键帧之间的特征点匹配构成一“关键帧网格”。

6.如权利要求4所述的计算机可读介质，其特征在于，还包括通过以下步骤生成动画镶嵌图像：

按照所述关键帧网格，将图像帧子序列对准到所述静态镶嵌；

在所述动画镶嵌图像的回放期间，顺序地将所述对准的图像子序列作为动态覆盖图映射到所述静态镶嵌。

7.一种从场景的至少一组顺序图像中生成镶嵌图像的系统，包括使用计算设备执行以下步骤：

接收一场景的至少一组顺序图像帧；

将每组顺序图像帧的第一个图像帧和最后一个图像帧标识为关键帧；

从每个图像提取一组特征点；

对于每个图像帧，标识对直接前一个图像的特征点匹配；

对于每个图像帧，标识对直接前一个关键帧的特征点匹配；

对于每个图像帧，估计与直接前一关键帧的重叠量，并且如果所估计的重叠量位于一预定阈值之下，则将该帧设置为新的关键帧；

对于每个帧，标识对直接后一关键帧的特征点匹配；以及

对于每个关键帧，标识对每个其它关键帧的特征点匹配；

从全部特征点匹配生成一匹配结构；

从所述匹配结构估计最优图像对准；以及

从所述估计的最优图像对准构造静态镶嵌图像。

8.如权利要求7所述的系统，其特征在于，还包括以下步骤：通过自动地选择性地用代表性测量来替代一对或多对图像之间的一组或多组特征点匹配，来压缩所述匹配结构的特征点匹配，其中所述代表性测量对应于所述被替代的一组特征点匹配。

9.如权利要求7所述的系统，其特征在于，每个所述关键帧之间的特征点匹配构成一“关键帧网格”。

10.如权利要求9所述的系统，其特征在于，还包括生成动画镶嵌图像的步骤，包括：

按照所述关键帧网格，将一图像帧子序列对准到所述静态镶嵌；

将所述对准的图像子序列作为动态覆盖图映射到所述静态镶嵌。

11.如权利要求7所述的系统，其特征在于，还包括以下步骤：通过对由直接相邻的关键帧所定界的多组图像帧中的每一组顺序地执行如权利要求1所述的系统的步骤，实时地生成所述静态镶嵌。

12.如权利要求7所述的系统，其特征在于，还包括以下步骤：如果已经超过了预定最大数量的图像帧而没有按照所估计的重叠量标识出新的关键帧，则将一图像帧设置为新的关键帧。

13.如权利要求11所述的系统，其特征在于，如权利要求11所述的步骤是在具有用于实时显示所述静态镶嵌的整合式显示设备的设备齐全的摄像机内执行的。

14.一种具有用于实现如权利要求7所述的系统的步骤的计算机可执行指令的计算机可读介质。

15.一种从场景的一组顺序图像中自动生成镶嵌图像的方法，包括：

接收一场景的图像组；

在接收每个图像时评估该图像，以标识该图像的一组特征点；

按照对每个图像所标识的特征点构建图像对应关系的匹配结构，所述匹配结构包括被标识为关键帧的图像帧之间的匹配、相邻的非关键帧图像帧的组之间的匹配、以及每个非关键帧图像帧与直接前一个关键帧和后续的每个非关键帧图像帧之间的匹配；

从所述匹配结构估计最优图像对准；以及

按照所述估计的最优图像对准从所述图像组构造静态镶嵌图像。

16.如权利要求15所述的方法，其特征在于，还包括在估计所述最优图像对准之前，通过自动地选择性地用代表性测量来替代一对或多对图像之间的一组或多组特征点匹配来压缩所述匹配结构，其中所述代表性测量对应于被替代的一组特征点匹配。

17.如权利要求15所述的方法，其特征在于，被标识为关键帧的图像帧之间的匹配构成一“关键帧网格”，并且通过以下步骤构造动画镶嵌图像：

在所述动画镶嵌图像的回放期间，顺序地将所述对准的图像子序列作为顺序动态覆盖图映射到所述静态镶嵌。

18.如权利要求15所述的方法，其特征在于，将图像帧标识为关键帧包括以下至少一个：

将所述场景的顺序图像组的第一个帧和最后一个帧标识为关键帧；

对于每个图像帧，估计与直接前一关键帧的重叠量，并且如果所估计的与直接前一关键帧的重叠量位于一预定阈值之下，则将该帧设置为新的关键帧；

对于每个图像帧，估计与全部先前的关键帧的重叠量，并且如果所估计的与全部关键帧的重叠量位于一预定阈值之下，则将该图像帧设置为新的关键帧；以及

如果已经超过了预定最大数量的顺序图像帧而没有标识出新的关键帧，则将一图像帧设置为新的关键帧。

19.如权利要求15所述的方法，其特征在于，还包括在所述图像组的每个图像被摄像机捕获时实时构造所述静态镶嵌图像的预览，以及在集成到所述摄像机的显示设备上实时显示所述静态镶嵌图像的预览。

20.如权利要求15所述的方法，其特征在于，从所述图像组构造所述静态镶嵌图像包括通过运用以下至少之一来优化所述静态镶嵌图像：

重叠的图像帧的羽化；

图像帧对比度调节；

图像帧亮度调节；以及

对重叠的图像帧去重影。