用于使用可平行化架构中的图像来初始化及解算面元的局部几何形状或表面法线的方法

摘要

本文中描述用于解算视频流中所观测的场景中的对象的表面法线的系统及方法。所述系统及方法可包含：对所述视频流进行取样以产生关键帧的集合；产生所述关键帧中的每一者中的地图点的集合的假设表面法线；通过从所述假设表面法线中的每一者计算的扭曲矩阵使第一关键帧中的对应地图点的贴片扭曲到第二关键帧的视点；计分所述两个关键帧中的每一假设表面法线之间的扭曲误差；及舍弃在所述第一与第二关键帧之间具有高扭曲误差的假设表面法线。

说明书

技术领域

本文中所揭示的标的物通常涉及用于例如计算机视觉及扩增实境(AR)应用程序等 用于映射及跟踪技术的应用程序中的系统、方法及设备。具体来说，系统及过程用于通 过比较可平行化架构中的关键帧的集合中的假设法线来计算表面法线。

背景技术

相关背景

例如游戏、计算机视觉及扩增实境系统等应用程序依赖于对象的准确及有效检测及 跟踪。在未知环境中跟踪相机，或跟踪在相机前方移动的未知对象涉及首先建造环境或 对象的外观及结构表示。随后可通过匹配来自传入图像的图像特征与可存储为关键帧的 特征贴片的所存储外观表示来继续进行跟踪。

为了将来自过去关键帧(第一帧)的特征匹配到当前帧(第二帧)上，针对相似度，比较 环绕过去关键帧(第一帧)中的特征点位置的局部外观或像素强度与其中预期特征所位于 的当前帧(第二帧)中的候选区中的局部外观或像素强度。量化或测量相似度的一个常用 方法为经由使用过去关键帧中的像素的窗口与当前关键帧中的像素的窗口之间的归一 化交叉相关(NCC)得分。在两个帧/图像中的特征的校正位置处，来自两个帧/图像的像素 的窗口之间的NCC得分很高，从而指示良好相似性。然而，在两个图像的相机姿态相 当不同且存在两个图像中的特征的外观的改变时，无法直接比较特征窗口，且NCC得 分很低。在此情况下，环绕第一帧中的特征位置的图像区域必须扭曲到第二帧的图像区 域的视点，从而看起来类似于如从第二视点在第二帧中所见的特征的外观。环境的局部 几何形状或局部表面法线对于此匹配来说是重要的，从而使外观从一个视图扭曲到另一 视图，以用于从两个不同视角的宽基线匹配。场景的几何形状通常近似为中心定在3D 特征点位置处且具有3D的任意平面法线向量的小平坦贴片。通过局部几何形状的此表 示，需要中心定在每一3D特征点位置处的平坦贴片的法向量以便使围绕图像中的特征 位置的窗口的外观从一个视点扭曲到另一视点。另外，对于以动态方式与环境交互的扩 增，需要估计表面法线或贴片法线。举例来说，如果从其弹开的表面的法线为已知的， 那么可使弹力球扩增为真实的；及在扩增实境的应用程序中，这些是中心定在3D特征 点处的贴片的表面法线。传统地，使用最小化经扭曲贴片之间的平方差和的迭代梯度下 降算法来估计这些法线。举例来说，Nicholas Moltom、Andrew Davison及Ian Reid在其 标题为“来自运动的实时结构的局部平坦贴片特征(Locally Planar Patch Features for  Real-Time Structure from Motion)”的论文中描述此估计，所述论文呈现于2004英国机 器视觉会议。此方法为本身迭代算法，所述算法难以平行化。另外，此过程需要相对准 确的初始解来收敛到全局最佳值。此需要计算梯度，这需要较高表示精度。归因于计算 限制，对照明改变的最传统解也不是恒定的。

发明内容

本发明的实施例是针对通过解算所俘获视频流中的对象的局部几何形状或表面法 线来执行相机及目标跟踪。在一个实施例中，产生在视频流中可见的场景中的3D特征 点的假设法线。假设法线表示相对于由移动相机所看见的对象的表面法线的近似。因为 视频流从第一关键帧摇动到第二关键帧中所表示的对象的不同视图，所以针对特定3D 特征点假设的所有法线当中的校正表面法线为具有以下特性的法线：在校正法线用于使 中心定在第一关键帧中的图像特征位置周围的像素的窗口/贴片扭曲到第二关键帧的相 机视图中时，来自第一帧的像素的经扭曲窗口具有与第二关键帧中的像素的对应窗口的 高相关性。用于使像素从第一关键帧扭曲到第二关键帧的不正确地假设的法线将产生第 一帧中的像素的经扭曲窗口与第二关键帧中的像素的窗口之间的低相关性得分。在一个 实施例中，像素的窗口/贴片可为中心定在预定位置处的正方形或矩形像素网格或贴片 (例如，8x8或10x12像素网格)。在一个实施例中，如果存在两个以上关键帧，那么校 正法线可在此扭曲程序之后产生任何两个关键帧之间的高相关性得分。在准确表面法线 的计算/估计之后，可正好匹配及跟踪视频流中的关键帧之间的对应对象或点。

在一个实施例中，在可平行化架构中分析用于关键帧的集合的假设法线以确定其准 确性，其中并行评估法线的集合以用于确定在扭曲之后在若干对关键帧之间的高相关性 得分。假设可能表面法线及使用多对关键帧确定其准确性提供与使用梯度下降或类似迭 代方法的替代方案相比较对图像噪声稳健的解。另外，能够以并行方式实施计算导致与 迭代或类似方法相比较更快速的解。

另一实施例是针对用于解算视频流中的对象的表面法线的方法，其包括：取样视频 流以产生关键帧的集合；选择关键帧的集合中的对应图像点；使用两个或两个以上关键 帧中的对应图像点产生由关键帧的集合成像的场景中的3D特征点；产生3D特征点的 假设表面法线；通过从假设表面法线中的每一者计算的扭曲矩阵使对应于第一关键帧中 的3D特征点的图像像素贴片扭曲到第二关键帧的视点；计分第一及第二关键帧之间的 由每一假设表面法线产生的扭曲误差；及舍弃产生第一及第二关键帧之间的高扭曲误差 的假设表面法线。

另一实施例是针对包括指令的非暂时性机器可读媒体，所述指令在由机器执行时致 使所述机器执行用于解算视频流中的对象的表面法线的操作，所述指令包括：取样视频 流以产生关键帧的集合；选择关键帧的集合中的对应图像点；使用两个或两个以上关键 帧中的对应图像点产生由关键帧的集合成像的场景中的3D特征点；产生3D特征点的 集合的假设表面法线；通过从假设表面法线中的每一者计算的扭曲矩阵使对应于第一关 键帧中的3D特征点的图像像素贴片扭曲到第二关键帧的视点；计分第一及第二关键帧 之间的由每一假设表面法线产生的扭曲误差；及舍弃产生第一及第二关键帧之间的高扭 曲误差的假设表面法线。

另一实施例是针对用于解算视频流中的对象的表面法线的计算装置，其包括：用于 取样视频流以产生关键帧的集合的取样装置；用于选择关键帧的集合中的对应图像点、 使用两个或两个以上关键帧中的对应图像点产生由关键帧的集合成像的场景中的3D特 征点及产生3D特征点的假设表面法线的假设装置；用于通过从假设表面法线中的每一 者计算的扭曲矩阵使对应于第一关键帧中的3D特征点的像素图像贴片扭曲到第二关键 帧的视点的扭曲装置；用于计分第一及第二关键帧之间的由每一假设表面法线产生的扭 曲误差的计分装置；及用于舍弃产生第一及第二关键帧之间的高扭曲误差的假设表面法 线的消除装置。

另一实施例是针对具有用于解算视频流中的对象的表面法线的处理器的计算装置， 其包括：用于俘获视频流的相机；表面法线解算器，其包括：用于取样视频流以产生关 键帧的集合的取样单元；用于选择关键帧的集合中的对应图像点、使用两个或两个以上 关键帧中的对应图像点产生由关键帧的集合成像的场景中的3D特征点及产生3D特征 点的假设表面法线的假设单元；用于通过从假设表面法线中的每一者计算的扭曲矩阵使 对应于第一关键帧中的3D特征点的图像像素贴片扭曲到第二关键帧的视点的扭曲单 元；用于计分第一及第二关键帧之间的由每一假设表面法线产生的扭曲误差的计分单 元；及用于舍弃产生第一及第二关键帧之间的高扭曲误差的假设表面法线的消除单元。

上文概述不包含本发明的所有方面的详尽列表。预期本发明包含可从上文概括的各 种方面的所有合适组合以及在下文详细描述中所揭示及尤其在本申请案申请的权利要 求书中所指出的那些方面实践的所有系统及方法。此些组合具有上文概述中并未特定叙 述的特定优势。

附图说明

本发明的特征、性质和优点在结合附图阅读时将从下文陈述的详细描述变得更清 楚，在附图中相同参考字符始终对应地进行识别，且其中：

图1展示可在未知环境中跟踪相机及/或可使用经估计表面法线跟踪在相机前方移 动的未知对象的计算装置的组成图；

图2展示视频流的第一关键帧中的书上的地图点的表面法线；

图3展示检视平坦贴片的两个相机；

图4展示用于解算可平行化架构中的对象的表面法线的基于假设的过程；

图5展示书4的具有假设法线的集合的实例关键帧；

图6展示用于通过解算所俘获视频流中的对象的局部几何形状或表面法线来执行相 机及目标跟踪的表面法线解算器；及

图7展示针对图中的3D特征点产生的假设法线方向。

具体实施方式

图1展示可在未知环境中跟踪相机及/或可使用经估计表面法线跟踪在相机前方移 动的未知对象的计算装置100的组成图；计算装置100可为桌上型计算机、膝上型计 算机、移动电话、蜂窝式电话、蜂窝式或其它无线通信装置、个人通信系统(PCS)装置、 个人导航装置(PND)、个人信息管理器(PIM)、个人数字助理(PDA)、平板或其它类似装 置。

计算装置100可包含存储器单元102及用于执行所俘获视频流中的相机及/或目标跟 踪的操作的处理器104。在一个实施例中，计算装置100可包含集成到装置100中或经 由有线或无线外围设备连接而连接到装置100的一或多个视频相机106a、b。视频相机 106a、b可俘获将用以执行相机及/或目标跟踪的视频流，如下文将更完整地描述。相机 106a、b可使用能够俘获视频流的任何类型的图像传感器，包含电荷耦合装置(CCD)有 源像素传感器及互补金属氧化物半导体(CMOS)有源像素传感器。

在一个实施例中，计算装置100可包含用于与一或多个有线或无线网络通信的网络 接口单元110。网络接口单元110可提供计算装置100内的存取存储于远程装置/服务器 上的数据的组件。举例来说，网络接口单元110可提供存取存储于远程服务器上的视频 流的处理器104，所述视频流可经由因特网存取。网络接口单元110可能能够使用各种 协议与远程装置/服务器通信。举例来说，网络接口单元110可经编程以与码分多址 (CDMA)协议、时分多址(TDMA)协议、频分多址(FDMA)协议、3GPP长期演进(LTE)协 议、传输控制协议及因特网协议(TCP/IP)、IEEE 802.X等中的一或多者一起操作。举例 来说，网络接口单元110可使用无线网络信道存取及检索远程服务器上的视频流。

在一个实施例中，计算装置100中的表面法线解算器108有助于通过解算所俘获视 频流中的对象的局部几何形状或表面法线来执行相机及目标跟踪。表面法线解算器108 可处理视频流，且结合处理器104、存储器单元102、集成式数字信号处理器112及计 算装置100的其它组件解算表面法线。在准确表面法线的计算/估计之后，可精确地匹配 及跟踪视频流中的帧之间的对应对象或点。

图2展示视频流的第一关键帧中的书204上的地图点(例如，3D特征点)的表面法线 202。如本文中所使用，表面法线为正交于关键帧中的对象上的指定地图点的向量或平 面。在一个实施例中，关键帧中的地图点的精确法线最初是未知的。然而，可产生地图 点的假设法线。假设法线表示相对于关键帧中所见的对象的表面法线的近似。因为视频 流摇动到第二关键帧中的对象(例如，书204)的不同视图，所以可通过使用假设表面法 线的集合中的每一法线使图像/特征贴片从第一关键帧扭曲到第二关键帧中的图像/特征 贴片及接着计算第二关键帧中的对应图像/特征贴片的相关性得分或扭曲误差(相关性得 分及扭曲误差具有反比关系)来计分针对地图点产生的假设表面法线。如果作为使用特定 假设表面法线的此扭曲程序(上文也描述)结果的两个帧的特征贴片之间的相关性得分低 于设定的阈值(例如0.9或0.8)，那么可舍弃所述特定假设法线。此不准确性可由多个关 键帧中的相同地图点的贴片之间的在扭曲程序期间的高经检测误差得分(即低归一化交 叉相关性(NCC)得分)展示。准确表面法线对于扩增来说是重要的，从而以物理上合理的 方式与表面交互。具体来说，对于一些扩增实境应用程序，应在大约5°到10°以内估计 每一法线。然而，对于其它应用程序，准确性要求可能不同(更小或更大)。因此，舍弃 不准确的假设表面法线会消除较晚处理程序中的潜在误差。

NCC匹配解决了找到两个图像之间的相似性的问题。经由使用NCC得分，对于均 差及标准差，匹配是恒定的(线性效果)。对于图像数据，这表示对于亮度偏移及对比度 改变，NCC是恒定的。在比较用不同相机或在当天的不同时间拍摄的图像时，NCC得 分的这些特性会有更合乎需要的效果。

在经由搜索窗口计算NCC得分时，考虑参考贴片以找到搜索窗口内的图像/特征贴 片最佳匹配的位置。下式描述此操作：

$\gamma (u,v)=\frac{{\Sigma }_{x,y}[f(x,y)-{\bar{f}}_{u,v}][t(x-u,y-v)-\bar{t}]}{{\left\{{\Sigma }_{x,y}{[f(x,y)-{\bar{f}}_{u,v}]}^2{\Sigma }_{x,y}{[t(x-u,y-v)-\bar{t}]}^2\right\}}^{0.5}}$

其中

·x、y为贴片内的像素位置

·u、v为搜索窗口内的像素位置

·f()存取贴片数据

·t()存取搜索窗口内的图像数据

·(也被写成f_avg)为贴片中的所有像素的平均值

·(也被写成t_avg)为当前与贴片进行比较的区域的所有像素的平均值

·为贴片的方差(平方标准差)

·为当前进行比较的区域的方差(标准差)。

在上文等式中，一对最优像素位置<u,v>寻求获得最佳匹配。

Nicholas Molton、Andrew Davison及Ian Reid的标题为“来自运动的实时结构的局 部平坦贴片特征(Locally Planar Patch Features for Real-Time Structure from Motion)”的 论文中的章节2.1(其呈现于2004英国机器视觉会议)描述用于执行贴片扭曲的方法。方 法通过如图3中所示分析检视平坦贴片的两个相机的几何形状而开始。确切地说，图3 展示含有在具有零旋转的起点处的第一相机(相机0)、在从相机0旋转R的位置t处的第 二相机(相机1)及在位置x_p(其在具有法线n的局部平坦表面上)处的点的场景。相机0的 图像平面中的在位置(u₀,v₀)处的点向后投影到光线ρu₀，其中u₀＝(u₀,v₀,1)^T。在平面p上 的点x满足等式n^Tx＝n^Tx_p。在光线与平面的相交处，x＝ρu₀，因此ρn^Tu₀＝n^Tx_p，且 相交具有齐次坐标(ρv₀,1)^T＝(n^Tx_pu₀,n^Tu₀)^T。将此投影到第二图像中给出如下 等式：

$u_1=R\left[I\right|-t]\begin{array}{}\end{array}\left(\begin{array}{c}{n}^T{x}_p{u}_0\\ n^T{u}_0\end{array}\right)=R[n^T{x}_{p}I-{\mathrm{tn}}^T]u_0$

其中I为3x3单位矩阵。因此，两个相机图像中的理想化图像位置由单应性相关：

H_I＝R[n^Tx_pI-tn^T]

如果相机具有内部矩阵C₀及C₁，那么像素坐标中的单应性为：

$H=C_{1}R[n^T{x}_{p}I-{\mathrm{tn}}^T]C_0^{-1}$

此等式可用以预测其模板图像与当前相机图像之间的特征的视觉外观的变换。找到 此预测与特征的实际外观之间的差异，且使用图像配准方法进行表面法线估计的相关联 校正。此方法提供反向组合调整(即，用调整H_i更新原始图像变换H_n-1)，从而得到变换 H_n的新估计，以使得：

$H_n=H_{n-1}{H}_i^{-1}$

可在表面法线n的改变方面参数化H_i。通过添加向量d来调整法线n，其中 向量可经选择为垂直于彼此及x_p的任何单位向量，且α及β参数 化调整的量。相加调整d足以使表面法线在平面将在相机0中可见的定向的范围内变化。 使用上文等式，调整变换H_i(即，扭曲矩阵)变为：

$H_i=H_n^{-1}{H}_{n-1}$

$\left(\begin{array}{c}{H}_i={\left[C_{1}R\right[{(n+d)}^T{x}_{p}I-t{(n+d)}^T\left]C_0^{-1}\right]}^{-1}\left[C_{1}R\right[n^T{x}_{p}I-{\mathrm{tn}}^T\left]C_0^{-1}\right]\\ H_i=C_0{[n^T{x}_{p}I-{\mathrm{tn}}^T+{\mathrm{td}}^T]}^{-1}[n^T{x}_{p}I-{\mathrm{tn}}^T]C_0^{-1}\\ H_i=C_0{[n^T{x}_{p}I-{\mathrm{tn}}^T+t{(\alpha {\bar{x}}_p^1+\beta {\bar{x}}_p^2)}^T]}^{-1}[n^T{x}_{p}I-{\mathrm{tn}}^T]C_0^{-1}\end{array}\right)$

在一个实施例中，在可平行化架构中分析关键帧的集合的假设法线以确定其准确 性，其中并行评估法线的集合以用于确定若干对关键帧之间的在扭曲之后的高相关性得 分或低扭曲误差。假设可能表面法线及使用多对关键帧确定其准确性提供与使用梯度下 降或类似迭代方法的替代方案相比较对图像噪声稳健的解。举例来说，此假设驱动系统 及过程不会遭受取决于初始化而陷于局部最小值的问题。此外，梯度下降方法取决于图 像梯度的准确估计，但在存在图像噪声的情况下，图像梯度估计变得不准确。因此，在 存在图像像素噪声的情况下，假设表面法线计算更稳健。

图4展示用于解算可平行化架构中的对象的表面法线的基于假设的过程300。过程 300可由图2中所示的计算装置100的组件中的一或多者执行。举例来说，法线解算器 108可结合处理器104、存储器单元102及计算装置100的其它组件执行下文描述的操 作。

过程300开始于操作302，其中接收或检索视频流。视频流可从相机106a、b中的 一者获得，或从局部或远程存储器源获得。举例来说，视频流可存储于存储器单元102 中及可由表面法线解算器108及处理器104存取。在另一情况下，视频流存储于远程服 务器上且可经由使用网络接口单元110由表面法线解算器108存取。视频流可使用任何 译码格式或技术编码。举例来说，视频流可使用高级视频编解码器高清晰度(AVCHD)、 音频视频交错(AVI)、Adobe Flash视频格式(FLY)、Google视频文件格式(GVI)、H.264 及移动图片专家组(MPEG)系列标准编码。

在操作302处进行接收或检索后，即刻在操作304处取样视频流以产生一系列关键 帧。从视频流获得的关键帧的数目可取决于视频流的长度及指定的取样速率。举例来说， 三十秒视频流可以5Hz的速率进行取样以输出150个关键帧。在其它实施例中，可使 用不同取样速率。在操作304处通过取样产生的每一关键帧为在特定时刻在视频流中的 场景的完整表示(例如，场景的静态图像)。选择取样速率以输出关键帧，所述关键帧显 示视频流内的对象的显著差异或移动，且提供有用的基线。在一个实施例中，集成到计 算装置100中的专用视频取样单元对视频流进行取样以产生关键帧的集合。

在操作305处，在关键帧的集合中选择图像点，且图像点用以产生由关键帧的集合 观测的场景中的地图点(例如，3D特征点)。图像点为对应于由关键帧观测的场景中的三 维元素(即，3D特征点)的关键帧中的二维位置。

在操作306处，针对地图点的集合产生假设法线。在一个实施例中，假设法线对应 于每一关键帧中所表示的场景的单位球面中的不同离散方向。举例来说，可相对于x轴 以45度引导在第一地图点处的第一假设法线，而可相对于x轴以90度引导在第二地图 点处的第二假设法线。这些假设法线中的每一者表示由关键帧成像的对象的表面法线的 估计。在一个实施例中，针对每一地图点产生假设法线的集合。举例来说，可产生60 个单独地图点的60个假设表面法线。在其它情况下，可产生20到100个假设表面法线。 举例来说，在一个实施例中，可产生30个单独地图点的30个假设表面法线，而在另一 实施例中，可产生50个单独地图点的50个假设表面法线。尽管这些假设表面法线为粗 略的估计，但将经由比较及计分来确定其准确性，如下文所更详细描述。对于使具有大 基线的视图之间的关键帧中的贴片的外观扭曲，估计及确定准确表面法线是重要的。因 此，舍弃不准确的假设表面法线消除较晚处理程序中的潜在误差。

在操作308处，选择两个关键帧以用于比较相应假设法线。选定关键帧可为视频流 中的顺序/邻近帧或视频流中的非顺序/非邻近帧。在一个实施例中，选定关键帧经选择 为时间上充分分离以确保由关键帧表示的场景中的对象的移动。举例来说，可设定下分 离界限以指示关键帧之间的必要分离度。关键帧的分离提供可充分区分的足够宽基线以 用于计分/比较假设/经估计法线。尽管关键帧经选择为相对分离，但在一个实施例中， 分离不应超出上分离界限，以使得关键帧实质上并不相异。举例来说，在50个关键帧 的连续集合中，下分离界限可为3个关键帧，而上分离界限可为5个关键帧。在此实例 中，在操作308处选择的关键帧可为帧5及9(即，分开4个关键帧)。在其它实施例中， 下分离界限可在1到5个关键帧的范围内，而上分离界限可在5到10个关键帧的范围 内。尽管在关键帧方面表示上及下分离界限，但在其它实施例中，可在原始视频流中的 关键帧之间的时间差方面表示分离界限。通过选择具有相对相似性及良好基线的关键 帧，可较精确地执行扭曲及比较操作。

在选择两个关键帧之后，操作310使用对应于图像像素贴片的地图点的假设表面法 线中的每一者使所述贴片的外观从一个选定关键帧扭曲到另一选定关键帧。在一个实施 例中，像素的窗口/贴片可为中心定在关键帧中所表示的图像中的预定位置处的正方形或 矩形像素网格或贴片(例如，8x8或10x12像素网格)。可使用经由上文所描述的过程计 算的扭曲矩阵执行扭曲。计分每一假设表面法线以确定准确性(即，误差度)。在一个实 施例中，得分是基于来自第一关键帧的经扭曲贴片与第二关键帧中的目标贴片之间的 NCC(归一化交叉相关性)得分，其中假设法线用以计算扭曲。产生高于预定义相关性得 分水平的得分的假设法线经确定为准确假设，而低于预定义相关性得分水平的得分经确 定为不准确的且被舍弃。舍弃低相关性得分假设会消除不太可能的解，同时保留更大可 能的估计。在一个实施例中，可对用于多个关键帧及扭曲程序的扭曲误差求和来改进跨 越多个关键帧的误差估计的稳健性。

图5展示书404的具有假设法线402的集合的实例关键帧。经着色法线402a、b表 示不准确的法线，其在操作310处计算的得分低于预定义的相关性得分水平，而未着色 法线402c、d、e表示其得分高于预定义的相关性得分水平的准确法线。如上所指出， 舍弃不准确的法线402a、b(例如，经着色表面法线)，而保留准确法线402c、d、e以供 相机及目标跟踪操作使用。

在一个实施例中，对于多对关键帧重复操作308及310。举例来说，在关键帧5及 9已进行比较及扭曲从而展现两个帧中的准确及不准确的法线之后，可以类似方式处理 关键帧5以及关键帧2。因为重复比较帧，所以计算的数目归因于假设修剪随时间的流 逝而减少(即，早点消除不太可能的假设而不用使用所有若干对帧对其进行测试)。

通过使用多对关键帧，增加估计及表面法线解的稳健性。在足够数目的关键帧对已 进行比较/扭曲且在操作312处确定呈现为准确的一或多个表面法线的清洁集合之后，操 作308及310因法线估计已收敛而终止。其后，经修剪表面法线的最终集合可用以在操 作314处执行相机跟踪、目标跟踪或其它视频处理程序。在一个实施例中，操作312可 确定具有最高相关性得分水平(即，最低扭曲误差)的表面法线。具有最高相关性得分的 此经确定表面法线其后可在操作314处用以执行相机跟踪、目标跟踪或其它视频处理程 序。

上文所描述的用于解算表面法线的过程可并行化，因为表面假设法线为独立的，且 可单独地执行对应比较/扭曲操作。可平行化及可独立地操作的此能力提供采用高速缓存 位置的潜在硬件加速的可用性。

在一个实施例中，使用定向直方图以用于初始化及优化每一关键帧中的假设法线。 举例来说，对于关键帧中的每一地图点，针对每一关键帧计算观测此地图点的从地图点 到相机的中心的方向。地图点的近似法线估计为每一地图点的这些向量的平均值。

图6展示根据一个实施例的表面法线解算器108的功能单元框图及一些构成硬件组 件。图6中所示的组件表示包含于表面法线解算器108中的元件，且不应解释为排除其 它组件。表面法线解算器108的组件可用以执行用于解算上文所描述的对象的表面法线 的基于假设的过程300的操作中的一或多者。

在一个实施例中，表面法线解算器108包含取样装置/单元502。取样装置502对视 频流进行取样以产生一系列关键帧。从视频流获得的关键帧的数目可取决于视频流的长 度及指定的取样速率。选择取样速率以输出显示视频流内的对象的显著差异或移动及提 供有用基线的关键帧。在一个实施例中，取样装置502可为DSP、通用硬件处理器、滤 波器的集合及/或任何类似装置。

在一个实施例中，表面法线解算器108包含假设装置/单元504。假设装置504产生 由取样装置502产生的关键帧中的每一者中的地图点的集合。在一个实施例中，假设法 线对应于相对于每一关键帧中所表示的场景的单元球面的不同离散方向。举例来说，图 7展示针对图中的3D特征点而产生的由从球面突出的线701表示的假设法线方向。假 设装置504可为DSP、通用硬件处理器、滤波器的集合及/或任何类似装置。在一个实施 例中，假设装置504可选择关键帧中的图像点。两个或两个以上关键帧中的对应图像点 可用以使用多视图几何形状中的熟知技术产生由关键帧成像的场景中的地图点(例如， 3D特征点)。举例来说，Richard Hartley和Andrew Zisserman的计算机视觉中书多视图 几何形状描述可用以产生地图点(例如，3D特征点)的技术。图像点为对应于由关键帧成 像的场景中的三维元素(即，3D特征点)的关键帧中的二维位置。

在一个实施例中，表面法线解算器108包含选择装置/单元506。选择装置506从由 取样装置502产生的关键帧的集合选择两个关键帧。在一个实施例中，选定关键帧经选 择为时间上充分分离的，从而确保由关键帧表示的场景中的对象的移动。选择装置506 可为DSP、通用硬件处理器、滤波器的集合及/或任何类似装置。

在一个实施例中，表面法线解算器108包含扭曲装置/单元508。扭曲装置508使用 对应于图像贴片的地图点的假设表面法线中的每一者使所述贴片的外观从一个选定关 键帧扭曲到另一选定关键帧。扭曲装置508可为DSP、通用硬件处理器、滤波器的集合 及/或任何类似装置。

在一个实施例中，表面法线解算器108包含计分装置/单元510。计分装置510计分 每一表面法线以确定准确性(即，误差度)。在一个实施例中，得分为来自第一关键帧的 经扭曲贴片与第二关键帧中的目标贴片之间的NCC(归一化交叉相关性)得分，其中假设 法线用以计算扭曲。在一个实施例中，计分装置510对多个关键帧的扭曲误差求和来改 进跨越多个关键帧的误差估计。计分装置510可为DSP、通用硬件处理器、滤波器的集 合及/或任何类似装置。

在一个实施例中，表面法线解算器108包含消除装置/单元512及标记装置/单元514。 消除装置512舍弃/消除得分低于预定义相关性得分水平的假设法线，而标记装置514 标记得分高于预定义相关性得分水平的假设法线。得分高于预定义相关性得分水平的假 设法线经确定为准确假设，而低于预定义相关性得分水平的得分经确定为不准确的且被 舍弃。舍弃低相关性得分假设消除不太可能的解，同时保留更大可能的估计。消除装置 512及标记装置514可各自为DSP、通用硬件处理器、滤波器的集合及/或任何类似装置。

在一个实施例中，表面法线解算器108包含确定装置/单元516。确定装置516确定 经标记表面法线的集合是否大于或等于表面法线的预定义数目。在经标记表面法线的数 目低于预定义数目时，确定装置516致使扭曲装置、计分装置及消除装置处理一对新关 键帧。确定装置516可为DSP、通用硬件处理器、滤波器的集合及/或任何类似装置。在 一个实施例中，确定装置516可确定具有最高相关性得分水平(即，最低扭曲误差)的表 面法线。具有最高相关性得分的此经确定表面法线其后可用以执行相机跟踪、目标跟踪 或其它视频处理程序。

取决于应用，可由各种装置来实施本文中所描述的方法。举例来说，这些方法可以 硬件、固件、软件或其任何组合来实施。对于涉及硬件的实施方案，处理单元可实施于 一或多个专用集成电路(ASIC)、数字信号处理器(DSP)、数字信号处理装置(DSPD)、可 编程逻辑装置(PLD)、现场可编程门阵列(FPGA)、处理器、控制器、微控制器、微处理 器、电子装置、经设计以执行本文所描述的功能的其它电子单元，或其组合内。

对于涉及固件及/或软件的实施方案，可用执行本文中所描述的功能的模块(例如， 程序、功能等等)来实施方法。在实施本文所述的方法时，可以使用任何有形地体现指令 的机器可读媒体。举例来说，软件代码可以存储在存储器中并且通过处理单元执行。存 储器可以实施在处理单元内或处理单元外部。在本文中使用时，术语“存储器”是指任 何类型的长期、短期、易失性、非易失性或其它存储器，并且不应限于任何特定类型的 存储器或任何特定类型数目的存储器或存储存储器的媒体的类型。

如果以固件及/或软件来实施，那么可将功能作为一或多个指令或代码存储在计算机 可读媒体上。实例包含编码有数据结构的计算机可读媒体和编码有计算机程序的计算机 可读媒体。计算机可读媒体包含物理计算机存储媒体。存储媒体可为可由计算机存取的 任何可用媒体。借助于实例而非限制，此类计算机可读媒体可包含RAM、ROM、 EEPROM、CD-ROM或其它光盘存储装置，磁盘存储装置、半导体存储装置或其它存储 装置，或任何其它可用于存储指令或数据结构的形式的所要程序代码并且可由计算机存 取的媒体；在本文中使用时，磁盘和光盘包含压缩光盘(CD)、激光光盘、光学光盘、数 字多功能光盘(DVD)，软性磁盘和蓝光光盘，其中磁盘通常以磁性方式再现数据，而光 盘用激光以光学方式再现数据。上述各项的组合也应包含在计算机可读媒体的范围内。

除了存储在计算机可读媒体上之外，还可将指令和/或数据提供为通信设备中包含的 传输媒体上的信号。举例来说，通信设备可包含具有指示指令及数据的信号的收发器。 所述指令和数据经配置以致使一或多个处理单元实施权利要求书中概述的功能。即，通 信设备包含具有指示执行所揭示的功能的信息的信号的传输媒体。在第一时间，通信设 备中包含的传输媒体可包含用以执行所揭示功能的信息的第一部分，而在第二时间，通 信设备中包含的传输媒体可包含用以执行所揭示功能的信息的第二部分。