用于图像的立体匹配的系统和方法

摘要

提供了一种用于对至少两个图像例如立体图像对进行立体匹配的系统和方法，该系统和方法采用了全局优化函数，例如信任传播算法或函数，该函数利用动态编程作为预处理步骤。本公开的系统和方法包括从一场景获取第一图像和第二图像(402)，估计第一图像中的至少一个点与第二图像中的至少一个对应点的差异(404，406)，并且利用信任传播函数例如全局优化算法或函数来最小化所估计的差异(410)，其中利用被应用到第一和第二图像的确定性匹配函数例如动态编程的结果来初始化信任传播函数(408)，以加速信任传播函数。该系统和方法还根据所估计的差异生成差异图，并且将差异图转换成深度图。

权利要求

1.一种对至少两个图像进行立体匹配的方法，该方法包括：

从一场景获取第一图像和第二图像(402)；

估计所述第一图像中的至少一个点与所述第二图像中的至少一个对应点的差异(404，

406)；以及

利用信任传播函数来最小化所估计的差异(410)，其中，所述信任传播函数是利用被应用到所述第一图像和第二图像的确定性匹配函数的结果来初始化的(408)。

2.如权利要求1所述的方法，其中，所述确定性匹配函数是动态编程函数(408)。

3.如权利要求1所述的方法，其中，最小化步骤还包括将确定性结果转换为将被所述信任传播函数使用的消息函数。

4.如权利要求1所述的方法，还包括根据所述第一图像中的至少一个点中的每一个与所述第二图像中的至少一个对应点的所估计差异来生成差异图(210)。

5.如权利要求4所述的方法，还包括通过对所述差异图的至少一个点中的每一个的所估计差异取倒数来将所述差异图转换成深度图(212)。

6.如权利要求1所述的方法，其中，所述第一图像和第二图像包括一立体对的左眼视图和右眼视图。

7.如权利要求1所述的方法，其中，估计差异的步骤包括计算像素匹配成本函数(404)。

8.如权利要求1所述的方法，其中，估计差异的步骤包括计算平滑成本函数(406)。

9.如权利要求1所述的方法，还包括调整所述第一图像和第二图像中的至少一个以将所述第一图像和第二图像中每一个的外极线与所述第一图像和第二图像的水平扫描线对齐(204)。

10.一种用于对至少两个图像进行立体匹配的系统(100)，包括：用于从一场景获取第一图像和第二图像的装置；

差异估计器(118)，被配置用于估计所述第一图像中的至少一个点与所述第二图像中的至少一个对应点的差异，并且利用信任传播函数(136)来最小化所估计的差异，其中，所述信任传播函数(138)是利用被应用到所述第一图像和第二图像的确定性匹配函数的结果来初始化的。

11.如权利要求10所述的系统(100)，其中，所述确定性匹配函数是动态编程函数(138)。

12.如权利要求10所述的系统(100)，其中，所述差异估计器(118)还被配置用于将确定性结果转换为将被所述信任传播函数使用的消息函数。

13.如权利要求10所述的系统(100)，其中，所述差异估计器(118)还被配置用于根据所述第一图像中的至少一个点中的每一个与所述第二图像中的至少一个对应点的所估计差异来生成差异图。

14.如权利要求13所述的系统(100)，还包括深度图生成器(120)，用于通过对所述差异图的至少一个点中的每一个的所估计差异取倒数来将所述差异图转换成深度图。

15.如权利要求10所述的系统(100)，其中，所述第一图像和第二图像包括一立体对的左眼视图和右眼视图。

16.如权利要求10所述的系统(100)，其中，所述差异估计器包括像素匹配成本函数(132)。

17.如权利要求10所述的系统(100)，其中，所述差异估计器包括平滑成本函数(134)。

18.如权利要求10所述的系统(100)，还包括图像扭曲器(116)，被配置用于调整所述第一图像和第二图像中的至少一个以将所述第一图像和第二图像中每一个的外极线与所述第一图像和第二图像的水平扫描线对齐。

说明书

用于图像的立体匹配的系统和方法

技术领域

[0001] 本公开大体上涉及计算机图形处理和显示系统，更具体而言涉及用于至少两个图像的立体匹配(stereo matching)的系统和方法，该系统和方法采用了一种全局优化函数，该函数利用了动态编程作为预处理步骤。

背景技术

[0002] 立体成像是这样一个过程：在视觉上组合从略微不同的视点拍摄的一场景的至少两个图像，以产生三维深度的错觉。此技术依赖于这样一个事实，即，人眼之间间隔有某一距离，因此不会观看到完全相同的场景。通过向每只眼睛提供来自不同视角的图像，使观看者的眼睛误以为感觉到深度。通常，当提供两个不同的视角时，成分图像被称为“左”图像和“右”图像，分别也称为基准图像和补充图像。然而，本领域的技术人员将会认识到，可以组合多于两个视点来形成立体图像。

[0003] 在3D后期制作、视觉效应(VFX)工作流和三维(3D)显示应用中，一个重要的过程是从由左眼视图图像和右眼视图图像构成的立体图像推断出深度图。例如，最近面市的自动立体3D显示器要求图像加深度图的输入格式，以便显示器能够生成不同的3D视图来支持多个视角。

[0004] 从立体图像对推断出深度图的过程在计算机视觉研究领域中被称为立体匹配，因为像素或区块匹配被用于找出左眼视图图像和右眼视图图像中的对应点。根据图像中的与场景中的同一点相对应的两个像素之间的相对距离来推断出深度值。

[0005] 数字图像的立体匹配被广泛用于许多计算机视觉应用中(例如，用于计算机辅助绘图(CAD)的快速对象建模和原型制作、用于人机交互(HCI)的对象分割和检测、视频压缩、以及视觉监控)，以提供3D深度信息。立体匹配从定位在场景中的不同位置和方向处的两个或更多个相机获得场景的图像。这些数字图像是大致同时从每个相机获得的，并且与空间中的3D点相对应的每个图像中的点被匹配。一般地，通过搜索图像的一部分并且利用约束(例如外极约束)将一个图像中的一点与另一图像中的一点关联起来，从而来匹配来自不同图像的点。

[0006] 关于立体匹配已经有大量在先工作。立体匹配算法可被分类成两个类别：1)在局部优化的情况下匹配，以及2)在全局优化的情况下匹配。局部优化算法只考虑像素强度差别，而忽略深度值的空间平滑性。因此，深度值在平坦区域中经常是不精确的，并且诸如空洞之类的不连续伪影经常可见。全局优化算法基于像素强度差别和深度图的空间平滑性两者来找出最优深度图；从而，全局优化算法大大改善了精确性以及所得到的深度图的视觉外观。

[0007] 全局优化的主要局限在于计算速度低。在全局优化方法这一类中，动态编程与诸如信任传播和图切割之类的更精细算法相比是相对迅速的方法，因为只实施水平平滑。然而，动态编程经常导致所得到的深度图中的垂直不连续，从而产生扫描线伪影(参见图5B，其中扫描线伪影被圈了起来)。信任传播是更先进的优化技术，其在水平和垂直方向上都实施平滑，但是它消耗的计算力比动态编程方法多得多。

[0008] 因此，需要用于使不连续伪影达到最低限度的快速且高效的全局优化立体匹配方法的技术。

发明内容

[0009] 提供了一种用于对至少两个图像(例如，立体图像对)进行立体匹配的系统和方法，该系统和方法采用了全局优化函数，例如信任传播算法或函数，该函数利用动态编程作为预处理步骤。本公开的系统和方法包括从一场景获取第一图像和第二图像，估计第一图像中的至少一个点与第二图像中的至少一个对应点的差异(disparity)，并且利用信任传播函数(例如，全局优化算法或函数)来最小化所估计的差异，其中，利用被应用到第一和第二图像的确定性匹配函数的结果来初始化信任传播函数，以加速信任传播函数。该系统和方法还根据第一图像中的至少一个点中的每一个与第二图像中的至少一个对应点的估计差异生成差异图，并且通过对差异图的差异值取倒数来将差异图转换成深度图。深度图或差异图随后可结合立体图像对用于3D重放。

[0010] 根据本公开的一个方面，提供了一种对至少两个图像进行立体匹配的方法，包括：从一场景获取第一图像和第二图像，估计第一图像中的至少一个点与第二图像中的至少一个对应点的差异，并且利用信任传播函数来最小化所估计的差异，其中信任传播函数是利用被应用到第一图像和第二图像的确定性匹配函数的结果来初始化的。第一图像和第二图像包括一立体对的左眼视图和右眼视图。

[0011] 在一个方面中，确定性匹配函数是动态编程函数。

[0012] 在另一方面中，最小化步骤还包括将确定性结果转换为将被信任传播函数使用的消息函数。

[0013] 在另一方面中，该方法还包括根据第一图像中的至少一个点中的每一个与第二图像中的至少一个对应点的所估计差异来生成差异图。

[0014] 在另一方面中，该方法还包括通过对差异图的至少一个点中的每一个的所估计差异取倒数来将差异图转换成深度图。

[0015] 在另一方面中，估计差异的步骤包括计算像素匹配成本函数和平滑成本函数。

[0016] 在另一方面中，该方法还包括调整第一图像和第二图像中的至少一个以将第一图像和第二图像中每一个的外极线与第一图像和第二图像的水平扫描线对齐。

[0017] 根据本公开的另一方面，提供了一种用于对至少两个图像进行立体匹配的系统。该系统包括：用于从一场景获取第一图像和第二图像的装置；差异估计器，被配置用于估计第一图像中的至少一个点与第二图像中的至少一个对应点的差异，并且利用信任传播函数来最小化所估计的差异，其中，信任传播函数是利用被应用到第一图像和第二图像的确定性匹配函数的结果来初始化的。

[0018] 根据本发明的另一方面，提供了一种能够由机器读取的程序存储设备，其有形地包含着能够由该机器运行来执行用于对至少两个图像进行立体匹配的方法步骤的程序指令，该方法包括：从一场景获取第一图像和第二图像，估计第一图像中的至少一个点与第二图像中的至少一个对应点的差异，并且利用信任传播函数来最小化所估计的差异，其中，信任传播函数是利用被应用到第一图像和第二图像的确定性匹配函数的结果来初始化的。

附图说明

[0019] 在以下应当结合附图来理解的对优选实施例的详细描述中将会描述本公开的这些和其他方面、特征和优点，或者从这些详细描述中将会清楚本公开的这些和其他方面、特征和优点。

[0020] 在其中相似的标号始终表示类似的元件的附图中：

[0021] 图1是根据本公开一个方面的用于对至少两个图像进行立体匹配的系统的示例性图示；

[0022] 图2是根据本公开一个方面的用于对至少两个图像进行立体匹配的示例性方法的流程图；

[0023] 图3示出了为场景中的关注点拍摄的两个图像之间的外极几何；

[0024] 图4是根据本公开一个方面用于估计至少两个图像的差异的示例性方法的流程图；并且

[0025] 图5示出了根据本公开的方法处理的结果图像，其中图5A示出了左眼视图输入图像和右眼视图输入图像，图5B是通过传统动态编程处理的结果深度图，图5C是通过本公开的信任传播方法处理的结果深度，并且图5D示出了利用平凡初始化的传统信任传播方法与包括通过动态编程来初始化的信任传播的本公开方法之间的比较。

[0026] 应当理解，附图仅用于例示本公开思想的目的，而并不一定是用于例示本公开的唯一可能配置。

具体实施方式

[0027] 应当理解，图中所示的元件可以以硬件、软件或其组合的各种形式实现。优选地，这些元件是以硬件和软件的组合的形式在一个或多个适当编程的通用设备上实现的，这些通用设备可包括处理器、存储器和输入/输出接口。

[0028] 本说明书例示了本公开的原理。因此将会明白，本领域的技术人员将能够设计出各种布置，这些布置虽然在这里没有明确描述或示出，但却体现了本公开的原理并且包括在其精神和范围之内。

[0029] 这里记载的所有示例和条件语言都意图用于教学目的，以帮助读者理解本公开的原理和发明人对推进现有技术所贡献的思想，并且应当被解释为不限于这种具体记载的示例和条件。

[0030] 另外，这里的所有记载本公开的原理、方面和实施例及其具体示例的陈述，都意图包括其结构和功能等同物。此外，希望这种等同物既包括当前已知的等同物，也包括将来开发出的等同物，即所开发出的任何执行相同功能的元件，不论其结构如何。

[0031] 因此，例如，本领域的技术人员将会明白，这里给出的框图表示了实现本公开的原理的示例性电路的概念性视图。类似地，将会明白，任何流程图、状态转换图、伪代码等等都表示实质上可以表示在计算机可读介质中并可以由计算机或处理器来如此执行的各种过程，不论这种计算机或处理器是否被明确地示出。

[0032] 图中所示的各种元件的功能可通过使用专用硬件以及能够结合适当的软件来执行软件的硬件来提供。当由处理器提供时，这些功能可由单个专用处理器提供、由单个共享处理器提供、或者由多个独立的处理器(其中一些可能被共享)提供。另外，对术语“处理器”或“控制器”的明确使用不应当被解释为只指能够执行软件的硬件，而是可以隐含地包括(但不限于)数字信号处理器(“DSP”)硬件、用于存储软件的只读存储器(“ROM”)、随机存取存储器(“RAM”)和非易失性存储设备。

[0033] 还可以包括其他传统的和/或定制的硬件。类似地，图中所示的任何开关都只是概念性的。它们的功能可通过程序逻辑的操作来实现、通过专用逻辑来实现、通过程序控制和专用逻辑的交互来实现，或者甚至手工实现，具体的技术由实现者根据对上下文的更具体理解来选择。

[0034] 在其权利要求中，被表达为用于执行指定功能的装置的任何元件都意图涵盖执行该功能的任何方式，例如包括a)执行该功能的电路元件的组合或者b)任何形式的软件，因此包括固件、微代码等等，这种软件与用于执行该软件的适当电路相组合以执行该功能。这种权利要求所限定的公开存在于以下事实中：由所记载的各种装置所提供的功能以权利要求所要求的方式被组合到一起。因此，认为任何能够提供这些功能的装置都与这里示出的那些是等同的。

[0035] 立体匹配是用于从立体图像(例如左眼视图图像和右眼视图图像)推断出深度图的标准方法。传统自动立体显示器上的3D重放已经表明，深度图的平滑性严重影响所得到的3D重放的外观。不平滑的深度图经常导致3D重放中的Z字形边缘，这些边缘从视觉上来说比重放具有不那么精确的深度值的平滑深度图还更糟糕。因此，对3D显示和重放应用而言，深度图的平滑性比深度精确性更重要。另外，基于全局优化的方法对于3D显示应用中的深度估计是必要的。本公开给出一种用于图像的立体匹配的加速方案，这种立体匹配基于一种信任传播算法或函数，例如全局优化函数，这种算法或函数在水平方向和垂直方向上都实施平滑，其中该信任传播算法或函数除了其他低成功算法或函数外还使用动态编程来作为预处理步骤。

[0036] 提供了一种用于对至少两个图像(例如，立体图像对)进行立体匹配的系统和方法，该系统和方法采用了全局优化函数，例如信任传播算法或函数，该函数利用动态编程作为预处理步骤。本公开的系统和方法包括从一场景获取第一图像和第二图像，估计第一图像中的至少一个点与第二图像中的至少一个对应点的差异，并且利用信任传播函数(例如，全局优化函数)来最小化所估计的差异，其中，利用被应用到第一和第二图像的确定性匹配函数的结果来初始化信任传播函数，以加速信任传播函数。该系统和方法还根据第一图像中的至少一个点中的每一个与第二图像中的至少一个对应点的估计差异来生成差异图，并且通过对差异图的差异值取倒数来将差异图转换成深度图。深度图或差异图随后可结合立体图像对用于3D重放。

[0037] 现在参考附图，根据本公开实施例的示例性系统组件在图1中示出。扫描设备103可被提供来用于将胶片拷贝(film print)104(例如，相机原始负片)扫描成数字格式，例如，Cineon格式或者电影和电视工程师协会(SMPTE)数字图片交换(DPX)文件。扫描设备103可包括例如电视电影机(telecine)或任何将会从这种胶片生成视频输出的设备，例如TM
具有视频输出的Arri LocPro 。或者，可以直接使用来自后期制作过程或数字影院106的TM
文件(例如，已经是计算机可读形式的文件)。计算机可读文件的可能来源是AVID 编辑器、DPX文件、D5带，等等。

[0038] 所扫描的胶片拷贝被输入到后期处理设备102，例如计算机。该计算机实现在各种已知的计算机平台中的任何一种上，这些计算机平台具有诸如以下硬件：一个或多个中央处理单元(CPU)、存储器110(例如随机存取存储器(RAM)和/或只读存储器(ROM))、以及(一个或多个)输入/输出(I/O)用户接口112(例如键盘、光标控制设备(例如，鼠标或操纵杆)和显示设备)。该计算机平台还包括操作系统和微指令代码。这里描述的各种过程和功能可以是微指令代码的一部分或者经由操作系统运行的软件应用程序的一部分(或其组合)。在一个实施例中，软件应用程序被有形地包含在程序存储设备上，该软件应用程序可被上载到诸如后期处理设备102之类的任何适当的机器并被其执行。此外，各种其他外围设备可以通过诸如并行端口、串行端口或通用串行总线(USB)之类的各种接口和总线结构连接到该计算机平台。其他外围设备可包括另外的存储设备124和打印机128。打印机128可以用于打印胶片126的经修改版本，例如胶片的立体版本，其中，一个或多个场景可能已经由于以下描述的技术而被利用3D建模的对象来加以更改或替换。

[0039] 或者，已经是计算机可读形式的文件/胶片拷贝106(例如，数字影院，其例如可被存储在外部硬盘驱动器124上)可被直接输入到计算机102中。注意，这里使用的术语“胶片”可以指胶片拷贝或数字影院。

[0040] 软件程序包括存储在存储器110中的用于把第一图像中的至少一个点与第二图像中的至少一个对应点相匹配的立体匹配模块114。立体匹配模块114还包括图像扭曲器(image warper)116，图像扭曲器116被配置为调整立体匹配对的外极线，以使得外极线正好是图像的水平扫描线。

[0041] 立体匹配模块114还包括差异估计器118，差异估计器118被配置用于估计第一图像中的至少一个点与第二图像中的至少一个对应点的差异，并且用于根据所估计的第一图像中的至少一个点中的每一个与第二图像中的至少一个对应点的差异来生成差异图。差异估计器118包括被配置为匹配第一和第二图像中的像素的像素匹配成本函数132以及用于向差异估计应用平滑性约束的平滑成本函数134。差异估计器118还包括用于最小化所估计的差异的信任传播算法或函数136以及用于利用被应用到第一和第二图像的确定性匹配函数的结果来初始化信任传播函数136以加速信任传播函数136的动态编程算法或函数138。

[0042] 立体匹配模块114还包括深度图生成器120，用于通过对差异图的差异值取倒数来把差异图转换成深度图。

[0043] 图2是根据本公开一个方面用于对至少两个二维(2D)图像进行立体匹配的示例性方法的流程图。最初，后期处理设备102在步骤202获取至少两个2D图像，例如，具有左眼视图和右眼视图的立体图像对。后期处理设备102可通过获得计算机可读格式的数字主图像文件来获取至少两个2D图像。可以通过利用数字相机捕捉运动图像的时间序列来获取数字视频文件。或者，可以利用传统的胶片型相机来捕捉视频序列。在此情形下，经由扫描设备103扫描胶片。

[0044] 应当明白，不论胶片被扫描还是已经为数字格式，胶片的数字文件都将包括关于帧的位置的指示或信息，例如帧号码、从胶片开始起的时间，等等。数字图像文件的每个帧将包括一个图像，例如I1、I2、……、In。

[0045] 立体图像可以利用具有相同设定的两个相机来拍摄。或者相机被校准为具有相同的焦距、焦高和平行的焦平面；或者图像则必须在步骤204基于已知的相机参数而被扭曲，以便就好像它们是用具有平行的焦平面的相机拍摄的一样。这个扭曲过程包括步骤206的相机校准和步骤208的相机校正。校准和校正过程调整立体图像的外极线，使得外极线正好是图像的水平扫描线。参考图3，OL和OR表示两个相机的焦点，P表示两个相机中的关注点，并且pL和pR表示点P被投射到图像平面上之处。每个焦平面上的交点被称为外极点(由EL和ER表示)。右侧外极线，例如ER-pR，是连接光心和左侧图像上的点的光线在右侧图像上的投影，因此右侧图像上与左侧图像上的某个像素相对应的点应当位于右侧图像的外极线处，对于左侧外极线，例如EL-pL，也是类似的。由于对应点查找是沿着外极线发生的，所以校正过程将对应性搜索简化为只沿着扫描线搜索，这大大降低了计算成本。对应点是图像中与同一场景点相对应的像素。

[0046] 接下来，在步骤210中，为场景中的每一点估计差异图。每个场景点的差异是以左眼图像和右眼图像中的匹配点的相对距离的形式来计算的。例如，如果左眼图像中的点的水平坐标是x，并且右眼图像中其对应点的水平坐标为x’，则差异d＝x’-x。然后，在步骤212中，利用以下公式来将场景点的差异值转换为深度值z(即从场景点到相机的距离)：z＝Bf/d，其中B是两个相机之间的距离，也称为基线，并且f是相机的焦距，其细节将在下文中描述。

[0047] 参考图4，提供了根据本公开的用于估计差异图的方法，以上将其标识为步骤210。最初，在步骤402，获取立体的图像对。计算差异成本函数，包括在步骤404计算像素成本函数，以及在步骤406计算平滑成本函数。在步骤408，执行低成本立体匹配优化，例如动态编程，以获得对两个图像的立体匹配的初始确定性结果。在步骤410，低成本优化的结果随后用于初始化信任传播函数，以加速用于最小化差异成本函数的信任传播函数。

[0048] 现在将更详细描述图4所示的差异估计及其公式。差异估计是以上描述的工作流中的一个重要步骤。问题包括匹配左眼图像和右眼图像中的像素，即，找出右侧图像和左侧图像中对应于同一场景点的像素。通过考虑差异图是平滑的，立体匹配问题可以用如下数学公式来表述：

[0049] C(d(.))＝Cp(d(.))+λCs(d(.)) (1)

[0050] 其中d(.)是差异场，d(x，y)给出左眼图像中坐标为(x，y)的点的差异值，C是整体成本函数，Cp是像素匹配成本函数，并且Cs是平滑成本函数。平滑成本函数是用于实施差异图的平滑的函数。在优化过程期间，针对所有差异场最小化以上成本函数。对于局部优化，平滑项Cs被丢弃；因此，在优化过程期间不考虑平滑性。除了其他形式外，Cp可以被建模为像素强度的均方差：

[0051]

[0052] 取决于是否实施垂直平滑，平滑性约束的写法可以不同。如果水平和垂直平滑性约束都被实施，则平滑成本函数可被建模为以下均方误差函数：

[0053]

[0054] 在动态编程的情况下，只实施水平平滑，因此，平滑成本函数被建模如下：

[0055]

[0056] 由于此简化，动态编程只能用于一次一条扫描线地推断深度图，因为没有必要在整个图像平面上(尤其是在垂直方向上)优化深度图。

[0057] 以上成本函数公式可被转换为等价的概率公式，如下：

[0058]

[0059] 其中i和j是标识图像中的一点的单个索引。例如，如果图像的大小为320×240，则i＝0表示(0，0)处的像素，i＝321表示(1，1)处的像素，依此类推。比较式(1)(2)(3)，得到整体成本函数C＝logp(d(.))，像素匹配成本函数 平滑成本函数 以及

[0060] φi(di)＝exp((I(x，y)-I′(x-d(x，y))2)，

[0061] ψij(di，dj)＝exp([d(x，y)-d(x±1，y)]2+[d(x，y)-d(x，y±1)]2)[0062] 其中使用±是因为符号取决于像素的邻居；像素i和j是邻居像素；logZ相对于深度图而言是常数，其不影响式(5)和式(1)的等价。这样，最小化式(1)就等价于最大化式(5)。式(5)也被称为马尔可夫随机场公式，其中φi和ψij是马尔可夫随机场的势函数。求解式(5)可以通过最大化它或者通过计算差异的近似概率来实现。通过计算近似概率，计算出了近似概率b(di＝w)，该近似概率近似了真实概率p(di＝w)，即点i(坐标为x，y)的差异取值w的概率。w是从1到M的整数；其中M是最大差异值。像素i的差异值于是为实现最大b(di＝w)的w的值。

[0063] 信任传播(BP)通过使用被称为消息传递的迭代过程来计算近似概率b(di＝w)(即，b(di＝w)是像素i的差异等于w的概率)。在每次迭代时，通过以下式子来更新消息：

[0064]

[0065] 其中mij(dj)被称为从i传递到j的消息。消息一般被平凡地初始化为1。取决于不同的问题，消息传递可能要花1到数百次迭代才能收敛。在以上消息收敛后，通过以下式子来计算近似概率：

[0066]

[0067] 其中k是规格化常数。

[0068] 存在数种方式来加速信任传播算法或函数。一种方式是使用多标度方案来以从粗到细的方式细化消息，这是现有技术中已知的。本公开的用于加速信任传播算法的方法是减少信任传播算法的转换所需的迭代的次数。这是通过利用来自诸如动态编程或其他局部优化方法之类的低成本算法的立体匹配结果初始化信任传播消息来实现的。由于低成本算法只给出匹配过程中的确定性结果，而不是信任传播算法的消息函数，因此立体匹配结果被转换回消息函数。利用式(6)中的关系

[0069]

[0070] 并且因为图像是2D栅格，所以使用4邻居系统，于是任何像素的邻居像素数目为4。假定与每个节点相关联的消息是相同的，则后向转换如下：

[0071]

[0072] 低成本算法的结果是确定性的。由于需要计算近似概率b(xi)，因此需要将确定性匹配结果转换为近似差异概率bi(xi)。使用以下用于转换的近似：

[0073] bi(di＝w)＝0.9，如果di＝w

[0074] bi(di＝w)＝0.1，如果di≠w (10)

[0075] 其中w是范围从0到最大差异值M(例如，20)的整数，di是从动态编程算法输出的像素i的差异值。然后，di被用于计算式(10)，然后式(9)，然后所得到的消息被用于初始化式(6)。

[0076] 返回参考图2，在步骤212中，利用以下公式将每个场景点的差异值d转换为深度值z(从场景点到相机的距离)：z＝Bf/d，其中B是两个相机之间的距离，也称为基线，并且f是相机的焦距。每个至少一个图像(例如，左眼视图图像)的深度值被存储在深度图中。对应图像和相关联的深度图被存储在例如存储设备124中，并且可被取回以用于3D重放(步骤214)。另外，电影或视频剪辑的所有图像都可以与相关联的深度图一起被存储在表示该电影或剪辑的立体版本的单个数字文件130中。数字文件130可被存储在存储设备124以供以后取回，例如用于打印出原始胶片的立体版本。

[0077] 已利用如图5A所示的包括左眼视图图像和右眼视图图像在内的若干基准图像来测试了本公开的初始化方案。图5B和5C示出了传统的动态编程方法与包括通过动态编程来初始化的信任传播的本公开方法之间的比较。动态编程方法如图5B所示导致可见的扫描线伪影。为了实现类似于图5C所示图像的结果，传统的动态编程方法需要大约80-100次迭代。

[0078] 图5D示出了利用平凡初始化的传统信任传播方法与包括通过动态编程来初始化的信任传播的本公开方法之间的比较。图5D示出了通过20次迭代，本公开的方法产生了比传统信任传播方法好得多的差异图。

[0079] 虽然这里已经示出并详细描述了结合了本公开的教导的实施例，但是本领域的技术人员可以很容易设计出仍结合这些教导的许多其他改变的实施例。在已经描述了用于对至少两个图像进行立体匹配的系统和方法的优选实施例(它们意图为例示性的而非限制性的)后，注意本领域的技术人员在考虑以上教导后可以进行修改和改变。因此，应当理解，在所公开的公开内容的特定实施例中可以进行处于所附权利要求所限定的公开范围之内的变化。