表示时变图形模型的数据流的编码方案

摘要

引入额外的预测级(14)，也就是运动矢量或第一预测级的预测误差(d(t))的预测，首先的确增加了编码或压缩的精力耗费，相应地也就增加了解码和解压缩的精力耗费，但是由于运动的一致性，这里提出的预测方法大大改进了大部分图形模型序列中关于精力耗费的压缩优势。

说明书

技术领域

本发明涉及对表示时变图形模型的数据流的编码和解码，并且具体的涉及该图形模型数据的压缩。

背景技术

现今，时变3D计算机图形模型在经典计算机图形领域中有广泛的应用。例如，3D计算机图形模型应用在游戏、虚拟世界、动画片制作等方面，而且还应用在最新的被称为自由视点视频(FVV)或者3D视频对象(3DVO)的系统中。

3D计算机图形模型在虚拟3D坐标系中描述了3D对象的表面。为此，定义了位于表面之上或者沿着表面排列的一定数量的控制点或者顶点的3D坐标(x，y，z)。通过不同的参数化方法来定义连续表面。例如在被称为多边形网格的参数化方法中，由多边形定义3D对象表面的形状，其中多边形的顶点形成控制点。为了完整的描述对象，还包括连接关系的指示，也即关于哪些控制点被分别概括成多边形的指示。然后通过联合色彩、纹理和其他特征例如反射等来显现完整的3D对象。取决于所使用的表面参数化，这些特征和连接关系或者直接和点表示相关。

于是3D几何图形的通常表示就是在具有或者不具有其连接关系指示的列表中的控制点的3D坐标的指示。例如，在上述用于三角形网格的多边形连接关系的情况下，分别为相应列表号的三个控制点形成三角形，并又被概括到一个列表中。3D坐标可以以浮点数值或者整数数值呈现。连接关系由整数值也就是列表号的指示组成，其中相应的控制点按照列表号在列表中排列。

为了在不同的系统和应用中交换和传送3D几何图形，理想的是要使用一种特定的文本格式，例如虚拟现实模型语言(VRML)，因为它能够在接收侧对3D数据进行解析。

此外，最重要的，还希望减少对3D几何图形编码的必要数据量，从而减少传输数据速率和必要存储空间。如果使用特殊的压缩方法能实现以上减少。由于以上原因，在MPEG-4标准中，对静止对象3D几何图形的编码方法进行了标准化，被称作3D网格编码(3DMC)。3DMC是一种二元格式，除了30-40倍的压缩之外，还提供了相对于可获得的文本格式有所改进的传输功能特性。

但是在多种应用中，产生了动态的即时变的3D模型。在经典的计算机图形中，通过动画来形成，操作者通常为每一时刻新建模型。在最近的FVV或者3DVO方法中，通过真实对象3D运动的重建来形成动态模型，真实对象被若干个摄像机所记录。基本上，可辨别两种动态3D模型的情况。在第一种情况下，拓扑保持相同，也就是控制点或顶点的数量以及连接关系随时间是不变的。仅仅是控制点的3D位置变化。第二种情况代表一般性。在这种情况下，拓扑的变化也是允许的。

在一些情况下，时间变化可由动画描述，也就是依靠基本的物理运动模型来描述变化。这种方法的例子有人的脸部和身体的动画，这也已经在MPEG-4中标准化了，也就是通过所谓的FBA(脸部和身体动画)方法。这种动画模型的缺点是它们无法转换到一般的情况，也就是说它们仅限于特殊的运动序列和/或特殊的对象，例如脸部等。如果没有动画模型存在，那么在每个时刻将不得不传递新的3D模型或者新的控制点网格，然后在每个时刻用MPEG-4 3DMC对其进行编码，但是因为在每一个时刻都是相同的对象在运动，因而该数据还含有许多时间冗余，这可以用于进一步的压缩。

在J.Zhang和C.B.Owen“Octree-based Animated GeometryCompression”，DCC’04，Data Compression Conference，Snowbird，Utah，USA，page 508-517，March 23-25，2004中描述了一种对时变3D模型进行编码的方法，其中通过对控制点的预测、预测误差或者运动矢量的量化以及将运动矢量概括成组，来描述随时间的变化。压缩，也就是比特率的降低按照差分脉冲编码调制的一般原理来实现。这样，相对于3DMC，可以获得动态模型更显著的压缩优势，也就是相同质量下比特率节省或者相同比特率下质量更好。

但是，随着在不同应用领域中3D模型的更多使用，对动态模型具有更好压缩的更有效编码方案的需求也在增加。

发明内容

因此，本发明的目的是提供一种用于对表示时变图形模型的数据流进行编码/解码的编码方案，这将能获得更高的压缩优势，也就是相同质量下的比特率节省或者相同比特率下的质量更好。

该目的通过权利要求1或者12中的设备以及权利要求19或20中的方法来实现。

根据本发明，数据流表示时变图形模型并且具有一系列的数据部分，这些数据部分由定义了不同时刻图形模型的坐标数据组成，对该数据流的编码包括基于当前待编码的第一数据部分之前的第二数据部分的坐标数据，预测当前待编码的第一数据部分的坐标数据，来获得第一数据部分的预测坐标数据，还包括第一数据部分的预测坐标数据和第一数据部分的坐标数据的比较，来获得当前待编码的第一数据部分的预测误差矢量。然后进行第二预测，也就是基于已经获得的预测误差矢量，预测第一数据部分的预测误差矢量，来获得第一数据部分的预测误差矢量，据此第一数据部分的预测的预测误差矢量和第一数据部分的预测误差矢量进行相互比较，来获得第一数据部分的预测误差矢量差。然后对这些预测误差矢量差进行处理，来获得编码数据流的一部分。

相应的，以相反的方式进行解码。编码数据流表示上述数据流的编码形式，并包含编码的预测误差矢量差，编码数据流首先通过处理编码数据流来获得解码的预测误差矢量差。基于已经解码的预测误差矢量差，预测当前待解码的第一数据部分的预测误差矢量，来获得第一数据部分的预测的预测误差矢量。这些预测的预测误差矢量和当前待解码的第一数据部分的预测误差矢量差合并，来获得第一数据部分的预测误差矢量。然后进行第二预测，也就是说基于第一数据部分之前的第二数据部分的坐标数据，预测第一数据部分的坐标数据，来获得第一数据部分的预测坐标数据，据此第一数据部分的预测坐标数据和第一数据部分的预测误差矢量合并，来获得当前待解码的第一数据部分的坐标数据。

本发明发现，引入额外的预测级，也就是运动矢量或第一预测级的预测误差的预测，首先的确增加了编码和/或压缩的精力耗费，相应地也就增加了解码和/或解压缩的精力耗费，但是由于运动的一致性，这种预测大大改进了大部分图形模型序列中关于精力耗费的压缩优势。

预测误差矢量的预测，也就是第二预测级，可以包括时间预测和/或空间预测。更具体的，为了预测当前待编码的数据部分的预测误差矢量，可以使用当前待编码的数据部分之前的数据部分的预测误差矢量和当前待编码的数据部分的预测误差矢量两者，当然后者只有在已经存在时才使用。

根据一个特殊的实施例，为了基于前一个数据部分的预测误差矢量对预测误差矢量进行时间预测，要使用该数据部分中表示了相同坐标信息和/或相同控制点的运动矢量的预测误差矢量。

在基于已经获得的相同数据部分的预测误差矢量来进行预测误差矢量的空间预测的情况下，为了预测，要使用和待预测的预测误差矢量相邻的预测误差矢量，它或是基于连接关系和/或数据流中的邻近信息确定，或是由几何分析确定。

如果对于待预测的预测误差矢量，有若干时间/空间预测或者预测的预测误差矢量可用，那么例如预测的预测误差矢量由所有的这些预测值的中间值确定。

根据本发明的一个特殊的实施例，预测误差矢量差仍然受到聚类并随之缩放/量化，来减少比特率。

根据本发明的一个特殊的实施例，预测误差矢量差最终被二进制算术编码。为此，首先它们被有利的二进制化，也就是形成一系列二元判定或二进制文件的形式或者比特系列。然后以逐个二进制文件或者比特的方式对比特系列进行二进制算术编码。二进制算术编码可基于自适应概率估计和/或静态概率估计进行。也可以使用上下文模型，也就是对二进制化的不同比特或者二进制文件以各自之间独立的方式执行概率估计的适配。

根据本发明的一个特殊的实施例，为了限制二进制算术编码的精力消耗以及仍然保持尽可能高的压缩率，根据两种不同的二进制化方案执行二进制化，其中第一二进制化方案只在待二进制化的数据小于预定阈值时使用，而当数据大于阈值时，则对阈值应用第一二进制化方案，来获得前缀，而第二二进制方案对待二进制化的数据的其余部分使用。换句话说，本例中首先提及的二进制化只由前缀组成，而本例中后来提及的二进制化由前缀和后缀组成。根据一个特殊的实施例，此后使用自适应概率模型对前缀的比特进行二进制自适应编码，如果必要时，使用上下文模型，也就是对各个比特使用不同的自适应概率估计，而使用静态概率估计对后缀的比特进行二进制算术编码。这样相当程度上减少了算术编码的计算精力消耗，并通过合适选择对预测误差矢量差的二进制方案，提供了很小的压缩率损失。

附图说明

下面将参考附图更具体地阐释本发明的优选实施例，附图中：

图1是根据本方明实施例的编码器的电路方框图；

图2是多边形网格的简化视图；

图3是图1的聚类形成装置的电路方框图；

图4是图1中的算术编码器的简化电路方框图；

图5是图示了图4的二进制化装置的运行的流程图；

图6是根据图5的二进制化结果示例性阐释的列表；

图7是图示了图4的二进制算术编码装置的运行的流程图；以及

图8是根据本发明实施例，适合于对由图1编码器产生的数据流解码的解码器的电路方框图。

具体实施方式

图1示出了根据本发明实施例的用于对表示时变图形模型的数据流进行编码的编码器。该编码器一般地由10表示，它包括用于接收将被编码的数据流的输入12和用于输出编码数据流的输出14。编码器10内部包括帧内编码(intra-encoding)装置16，它连接到在输入12和开关20的第一输入之间延伸的帧内编码路径18中。在与帧内编码路径18平行延伸的帧间编码(inter-encoding)路径22中，连接了编码器10的剩余部分24，它表示帧间编码部分，也就是编码器10中与数据流中称作先前时刻的先前部分相关地对图形模型相对于时刻的位置执行编码的部分，这一点在下面将会更清楚的看到，对比于帧内编码装置16，其与数据流中称作其他时刻的部分相独立地对某时刻的图形模型位置执行编码。

帧间编码部分24由两个相互交错的DPCM环组成，也就是外环26和内环28，其中外环26用于输入12处的数据流中顶点或控制点的预测，内环28负责外环26的偏移矢量和/或预测误差的预测。

内环28包括比较器即差值形成装置或差分器30，合并器即加法装置或加法器32，聚类形成装置34，缩放/量化装置36，作为缩放/量化装置36对应物的逆缩放装置38，作为聚类形成装置34对应物的逆聚类形成装置或聚类分解装置40，用于时间或空间预测的预测装置42，以及开关44。

外环26以组件30-40与内环28交迭，除此之外外环还包括比较器或比较装置即差分器46，合并器或合并装置即加法器48，还有存储器或网格存储器50以及开关52。

帧间编码部分24还包括被称为帧内/帧间开关的控制装置54，以及用于算术编码的编码装置56。

关于这些组件的内部连接，差分器46、差分器30、聚类形成装置34、缩放/量化装置36和编码装置56串联连接到输入12和开关20之间的帧间编码路径22。控制装置54可控制开关20，来控制连接帧内路径18或者帧间路径22到输出14。

在缩放/量化装置36的输出和编码装置56的输入之间，环26和28以逆缩放装置38、逆聚类形成装置40以及加法器32的串联形式分叉。具体的，加法器32的第一输入连接到逆聚类形成装置40的输出，而加法器32的输出连接到内环28的预测装置42的输入。开关44包括两个输入，即连接到预测装置42输出的一个输入和其呈现逻辑0作为偏移矢量的预测替代值的另一个输入。控制装置54控制开关44，并且能使得预测装置42的输出或者逻辑0施加到差分器30的反相输入。差分器46的输出通过非反相输入连接到差分器30。开关44的输出不仅连接到差分器30的反相输入，还连接到加法器32的另一输入。

加法器32的输出进一步连接到加法器48的输入，加法器48的输出又连接到存储器50的输入。开关52包括两个输入，其中一个输入连接到存储器50的输出，而另一输入连接到呈现逻辑0作为预测控制点的替代值的端子。控制装置54控制开关52，并且能使得逻辑0或者存储器50的内容施加到差分器46的反相输入和加法器48的另一输入。差分器46的非反相输入通过帧间路径22连接到输入12。

在先前描述了编码器10的结构之后，下面将描述它的功能。

输入12处进入的数据流表示时变图形模型。换句话说，进入的数据流由一系列数据部分组成，这些数据部分含有定义了不同时刻图形模型的控制点或坐标数据。模型表面最终如何由控制点定义其自身取决于底层的参数化。依赖于参数化，连接关系信息还要和控制点关联，其中连接关系信息确定了控制点之间的相邻关系并且对于模型的完整确定或参数化是需要的。

实际上存在不同的参数化方法。然而下面作为示例假设参数化是多边形网格参数化。根据多边形网格参数化，图形模型或者3D对象的表面形状由多边形定义，多边形的顶点形成控制点。表面多边形的最简单形状是平面三角区域。为了完整的描述对象，需要连接关系的指示，也即哪些控制点分别概括成多边形，其中如上所述的连接关系信息包含在进入的数据流中。控制点和连接关系共同描述对象的几何形状。

定义了某一时刻图形模型表面的控制点从数据部分获得。可以为每个数据部分和/或为每个时刻重新传输连接关系信息，但是在数据流12中作为优选的，只有在数据流中的拓扑和/或连接关系信息改变的那些数据部分中才存在连接关系信息。

一种特殊的多边形网格参数化方法为所谓的规则矩形网格、所谓的估计网格，网格关于空间中任意放置的平面来定义。这里，控制点三个坐标(x，y，z)中的两个表示控制点在网格中的空间位置，而剩下的第三坐标表示点与该平面的垂直偏差或者点关于该平面的深度。

为了能够更清晰的阐释下文关于图1中编码器10的功能的讨论，如前所述，下文中将假设多边形网格参数化成为输入12数据流的基础。图2示例性示出了空间图解中任意时刻的多边形网格参数图形模型60。进入的数据流中定义了该时刻的数据部分，以及由该数据部分定义的变化的图形模型的位置，在下文中根据由连接关系信息而用连接线相互连接的控制点生成的网格类推，有时也将被称为网格，如图2中所示。网格包括对象60表面上的控制点62。此外，或是在该数据部分本身之中或是在先前数据部分中的数据流12，包括连接关系信息，表示哪三个控制点62属于多边形64，这里是三角形。控制点62在图2中图形模型60的线交叉处可见，其中多边形或者三角形由三条线围成。

在下面的描述中，控制点将被指定为m_i(t)，下标i是和相应的控制点62唯一关联的列表号，t将表示该控制点处于位置m_i(t)时的时刻。换句话说，m_i(t)是关于以68为预定原点的坐标系66定义了控制点i的位置的矢量。下文中定义了时刻t的图形模型的所有控制点i的全部有时也将被称为m(t)。用m(t-1)指定定义了时刻t-1也就是紧处于时刻t之前的时刻的图形模型的全部控制点，用m(t-2)指定定义了时刻t-2处图形模型的全部控制点，等等。时刻t处的3D模型m(t)就是当前要被压缩的模型。

当数据流现在到达输入12，首先第一数据部分到达，其定义了第一时刻t＝0的图形模型。在这种情形下，编码器10未得到关于图形模型的在先信息。换句话说，该模型还没有被预处理，并且网格存储器50仍然是空的。在这种情形下，帧间编码路径24不能执行预测。因此在这种情况下，控制器54首先调节开关20，使得静态编码耦合到编码数据流14中，其中静态编码由时刻t＝0的数据部分和/或控制点m(t)以及可能的关联连接关系信息通过帧内编码装置16产生。静态编码例如可以是MPEG-4中的3DMC。数据部分的静态编码就应该意味着，是以独立的方式对该时间部分和/或该数据部分的控制点m(t＝0)进行编码，也就是没有和数据流中其它数据的相关性，于是也可以独立于其它数据部分的内容而得到该数据部分的解码结果。

在该时刻，因为控制器54控制开关20使帧内路径18传送到输出14，因此控制装置54控制开关44和52来分别施加预测替代值即逻辑0到差分器46和30的反相输入。于是当帧内编码装置16执行控制点m(t＝0)的静态编码时，控制点m(t＝0)保持不变到达聚类形成装置34的输入，这里它们将受到成组操作来减少矢量的数量，这将在下文具体讨论。如果必要，这些数量骤减的矢量然后在缩放/量化装置36中被按缩放以及量化，当然这带有信息的损失，然后在逆缩放装置38中缩放回来，并在组分解装置40中再被分离成控制点m^(t)，从这里它们到达网格存储器50的输入，来作为下一个时刻的预测控制点或者控制点的预测。

通过控制器54完成开关位置设置，即图1中开关20、44和52位于上开关位置，这不仅仅是针对待编码的第一网格即在时刻t＝0时的情况，还针对如下情况

-景象或对象内容有变化发生，其由例如控制器54从数据流12的侧面信息中导出；

-模型的拓扑有变化发生，其由控制器54根据数据流12中的侧面信息进一步导出，例如根据新传输的连接关系信息，从而编码器10和/或相应的编码方法对所有种类的模型通用，或者

-外环26的重建误差太大，即原始模型和解码模型之间的差异和/或当前待编码的控制点m(t)和存储器50中存有的控制点m^(t-1)之间的差异太大。

为了确定重建误差，控制器54也连接到差分器46的输出。

因此，开关20、44和52处于上开关位置时的开关位置被称为编码器10的帧内模式，因为没有进行预测。

相反，处于帧间模式的编码器10的功能将在下文描述。在这种模式中，控制器54控制开关20和52，使得开关20和52位于下开关位置，即帧间路径22连接到输出14，并且存储器50的输出连接到差分器46的反相输入。开关44的调节以逐个运动矢量的方式完成，正如下文将要描述的，使得可选地将或是预测装置42的输出或是预测替代值0连接到差分器30的反相输入。

在帧间模式中，通过首先以外环26的预测削减时间冗余以及接着以内环28的时间和/或空间预测削减时间和/或空间冗余，来完成进一步的压缩，下文将对此进行更具体的描述。

可以从前面对帧内模式的描述中看出，在对涉及时刻t的数据部分执行帧内模式后，在存储器50中存有该时刻t的网格拷贝，包括控制点m^(t)，它仅仅由于量化装置36中的量化而偏离了控制点m(t)的原始版本。如果处于时刻t+1的下一数据部分是具有相同拓扑的网格，即其由控制点m(t+1)组成，这些控制点具有和控制点m(t)相同的连接关系信息时，外环26中的预测成为可能。

现在考虑这样的情况，具有和处于时刻t-1的前一网格的拓扑相同的拓扑的控制点m(t)到达输入12。针对时刻t-1的相应重建网格以控制点m^(t-1)的形式存在存储器50中，并通过开关52施加到差分器46的反相输入，其中控制器54将开关52调节到下开关位置。差分器46于是形成控制点m(t)和重建控制点m^(t-1)的差，由此偏移矢量d(t)在差分器46的输出产生，表示外预测环26的预测误差。于是不是顶点本身而是偏移矢量d(t)从差分器46的输出传输到差分器30的输入。当处在帧间模式时，这些偏移矢量d(t)更明确的描述了各个单独的控制点i在当前待传输的时刻t的网格和先前重建的时刻t-1的网格之间在x，y，z(图2)中各坐标的差异，即对1和N之间所有的i，d_i(t)＝m_i(t)-m^_i(t-1)，其中N表示时刻t和t-1的网格中控制点的数量，这两个时刻的网格具有相同的拓扑，因此也就具有相同数量的顶点。

通过内预测环28，现在从先前传输的偏移矢量和/或从先前传输的控制点推出的偏移矢量中预测偏移矢量d(t)。这第二预测不是对所有的偏移矢量d_i(t)都是可能的。对特殊的偏移矢量d_i(t)，如果多于一个与当前网格具有相同拓扑的网格已被传输，时间预测是可能的。然后对于每个顶点i，在输入12已经至少接收了坐标信息m_i(t-2)和m_i(t-1)，正如将要描述的，可以从它们中推出预测偏移矢量d^(t-1)并将其施加到差分器30的反相输入，于是接下来用于预测。这样的时间预测应当是有利的，因为对象随时间的运动一般不会突然变化，因此从已知的运动来预测运动是可能的，和/或引起的运动矢量差较小并且因此可以较低速率来压缩。下文将更具体的描述时间预测，并通过预测装置42执行。

通过装置42也可以执行空间预测，即如果已经传输了刚被处理的网格t的至少一个控制点m_i(t)。对于该控制点i，信息m_i(t-1)已经到达，而偏移矢量d^_i(t)可在预测装置42中获得，这将在下文具体描述。该控制点i的所有空间相邻点j相关联的偏移矢量d_j(t)具有和d_i(t)大约相同数值的假设被证明是合理的，因为运动不会在整个对象上突然变化。因此，相邻顶点j的数值d^_j(t)可用作d_i(t)的空间预测值，相反，d^_i(t)可用作值d_j(t)的空间预测值。这里，当前顶点i的空间相邻点j和/或关联的运动矢量d_i(t)可以由预测装置42确定，例如通过空间连接到当前待编码的顶点i，即，例如根据表面参数化的类型在多边形网格中形成多边形，作为近似多边形函数的相邻控制点，或者沿图形模型的表面或几何形状以任何形式作为顶点i的空间相邻点。例如，该信息从3D模型的拓扑描述或者通过几何检查获得。甚至已经传送的当前网格的所有空间相邻点j的偏移矢量d_j(t)可以用于预测。

最后，当前顶点i的偏移矢量d_i(t)的预测值d^_i(t-1)由可获得的空间和时间预测矢量的整体来确定。为此，采用中值滤波器，即因为预测矢量根据其长度排序，装置42在排列的可获得预测矢量中进行选择，例如在奇数个预测矢量的情况下选择中间一个，以及在偶数个预测值的情况下选择两个中间预测矢量的中值，作为最终预测矢量。例如，如果与时间预测偏移矢量d^_i(t-1)相邻存在一组四个空间预测偏移矢量d^_j(t-1)，其中j∈{i的相邻点}，预测装置42从这组五个预测矢量中选择第三个，如果它们根据长度排列的话。

代替使用中值滤波，也可以使用平均等。

最后，差分器30形成预测值d^(t-1)和/或预测偏移矢量与由差分器46传送的偏移矢量d(t)之差，即当前网格的偏移矢量。结果是偏移矢量差e(t)，每一个顶点i形成一个偏移矢量差e_i(t)。要指出的是，没有预测值时，偏移矢量差e_i(t)对应于运动矢量d_i(t)。

先前描述的通过内环28的预测，即偏移矢量的预测，以及偏移矢量差e(t)的进一步处理，相对于本说明书背景技术部分中描述的方法表现出明显的区别和优点，在该方法中仅预测了顶点本身并且产生的偏移矢量将进一步处理。

前面大体描述了对于所有进入环28的偏移矢量d(t)的内环28预测的功能。但是随着更具体的对单独的顶点i考虑单独的偏移矢量d_i(t)，需要指出，对于每个偏移矢量d_i(t)并不都需要存在预测值。如从前面的描述显而易见，毕竟对于之前紧接着时刻t-1的帧内模式的时刻t的所有偏移矢量d(t)，没有用来形成预测偏移矢量d^(t-1)的必需信息，毕竟为此还不得不存在时刻t-2处顶点的控制点信息)。另外或可选地，也可能没有空间预测值，因为待预测的偏移矢量d_i(t)为了相邻点j而被指向为顶点i，其中对于相邻点j从输入12的数据流中还没有获得或者不能导出偏移矢量d_j(t)和/或控制点m_j(t)。在这种情况下，因为针对偏移矢量d_i(t)的时间和空间预测值都不能由预测装置42提供，所以控制装置54将开关44设置到上开关位置。否则的话，图1中的开关被设置到下开关位置。换句话说，控制装置54在帧内模式中依照预测值的存在情况，对每个偏移矢量d(t)单独控制开关44。

此外，在前面的描述中，忽略了在差分器30的输出和加法器32的输入之间的环28和26的部分。在下文中将描述这部分的意义，其中要指出的事实是在这部分更精确的描述中，假设预测装置42只执行时间预测，即基于前一个偏移矢量d_i(t-1)和/或前两个时刻的控制点m_i(t-1)和m_i(t-2)来预测进入的偏移矢量d_i(t)。

聚类形成装置34接收针对当前待编码的时刻t的网格的偏移矢量差e(t)。聚类形成装置34按照例如Octree算法，执行相似和相邻的偏移矢量差的概括(summary)，其中聚类形成装置34的功能将在下文中参照图3具体讨论。换句话说，聚类形成装置34用一组替代偏移矢量差o(t)取代偏移矢量差e(t)，其中替代偏移矢量差o(t)的数量小于偏移矢量差e(t)的数量。结果，减少了将要传输的数值的数量，即各矢量差的坐标。然后替代偏移矢量差o(t)在缩放/量化装置36中被缩放和量化，由此生成量化的矢量y(t)。这些又提供给编码装置56，编码装置56对其进行算术编码，这将在下文中更具体的描述。以此种方式编码和压缩的值y(t)被耦合到输出14的编码数据流中。

为了闭合两个DPCM环26和28，在解码器10中根据量化矢量y(t)重建输出信号m(t)，其中编码器前面所有的步骤，即差分器46和30中的差值形成、装置34中的聚类形成以及缩放/量化装置36中的缩放被撤销或者以相反的方式执行。相应的，逆缩放装置38用缩放装置36使用的缩放因子的倒数作为其缩放因子，对矢量y(t)进行缩放，于是产生重构的一组替代偏移矢量差o^(t)。在聚类分解装置40中通过撤销装置34的聚类分类，将这组重建的替代偏移矢量差转换成一组重建的或解码的偏移矢量差e^(t)。如果必要，为此最终聚类分解装置40使用侧面信息，该信息和替代偏移矢量差o(t)一起被聚类形成装置34输出，并且如果必要在输出14也被编码到编码比特流中作为侧面信息，这将参照图3进行阐述。

现在为了重建偏移矢量d(t)，特定的重建偏移矢量差e^i(t)出现在加法器32的输入，而同时相同的预测值d^(t-1)出现在另一输入，当从偏移矢量d_i(t)中产生偏移矢量差e_i(t)的时刻，该预测值出现在差分器30的反相输入。因此加法器输出的结果为重建的偏移矢量d^i(t)。它到达预测装置42和加法器48的输出，然后预测装置42使用它来预测输入12的数据流中下一个数据部分的偏移矢量d(t+1)，特别是预测偏移矢量d_i(t+1)。加法器48通过将重建的偏移矢量d^(t)加到存储于存储器50并已被差分器46从待重建的控制点m(t)中减去的预测控制点m^(t-1)上，来撤销差分器46的差值形成。因此加法器48的结果为重建的控制点m^(t)，其被存储到存储器50中来预测正被编码的数据部分之后的数据部分控制点m(t+1)。结果，存储器50含有刚被传输的网格的重建。由于缩放/量化装置36的量化，存储器50中的网格和原始的网格不相等，即m(t)≠m^(t)。

在帧间编码部分24中编码的目标是使得重建网格m^(t)用尽可能少的比特达到和原始网格m(t)尽可能的相似。由原始的网格和解码的时间上前一网格之间的差表示重建误差，即d(t)＝m(t)-m^(t-1)，并由控制装置54使用在太大的重建误差下切换到帧内模式，如前面所述。

参照前面对编码器10的功能描述，要指出的是如果在图1电路方框图中省略编码器10的聚类形成装置34和聚类分解装置40，那么很容易得到在预测装置42中带有空间预测的另一种编码器，因为预测装置可以使刚被重建的偏移矢量d^(t)在加法器32的输出马上可用于预测相同网格的随后偏移矢量d(t)以得到，即特别是相邻顶点的那些偏移矢量。

下面参照图3更具体的阐述聚类形成装置34的内部结构。如图所示，聚类形成装置34包括装置80，用于接收偏移矢量差e(t)，并将其分成组，如组{e₁(t)…e_n1(t)}，{e_n1+1(t)…e_n2(t)}…{e_n1-1+1(t)…e_N(t)}，其中1≤n₁≤n₂…≤n_g-1≤N，其中g表示组的数量，N表示顶点的数量。例如这种分类成组可以通过细分立方单元来在几何上完成，这里立方单元围绕所有的偏移矢量差e(t)并且尽可能的小，例如在特定的边界条件下细分成卦限(octant)，其中位于一个卦限中的所有偏移矢量差e(t)概括成一组。

接下来聚类形成装置34的另一装置82确定每组的替代偏移矢量差，例如通过对属于相应组的所有偏移矢量差进行平均。因此结果为替代偏移矢量差即每组一个。聚类形成装置34的另一装置84对每组检查替代偏移矢量差和关联组的偏移矢量差的匹配情况。对于太差的匹配，装置86再次使得相应的组提供给装置80和/或再次被细分。如果任意组中不再有太差的匹配，聚类形成装置34的装置88用替代偏移矢量差和分类信息代替偏移矢量差e(t)，其中分类信息给出哪些偏移矢量差被递归环80-86概括成组的指示。

要记住可能有这样的情况，当在装置42中使用混合空间/时间预测时，对于一些e(t)，无法确定预测值，相对于相同网格的其它e(t)而言，它们对应偏移矢量d。在这种情况下，有利的是不将偏移矢量合并到实际的偏移矢量差e的聚类中。

装置40通过联合相关联的替代矢量差和相应分组的所有顶点，使用分类信息，撤销了矢量的数量缩减。

前面的描述大体上局限于两个预测环26和28功能描述。下面将进入到更具体的编码装置56的功能中，其对量化矢量y(t)执行算术编码，更具体的是对这些3D矢量的各个分量x，y，z执行算术编码，其中这些3D矢量表示替代偏移矢量差的量化。

在算术编码中，即一般为特殊形式的熵编码中，待编码的源字母表的字符，这里即待编码的矢量y(t)的分量与不同的出现概率相关联。为了对当前待编码的字符进行编码，根据源字母表的所有字符的出现概率，细分当前的概率区间，然后通过将概率区间收缩到当前概率区间中与当前待编码的字符对应的子区域，来更新概率区间。这个过程针对一系列待编码的字符重复。最终为该系列字符输出的码字表示产生的概率区间。在解码器一侧，该过程用算术解码进行仿真，即例如根据源字母表的出现概率来细分0到1的初始概率区间，以便检查码字指向哪一个区域，于是更新概率区间到该子区域等等。在下面使用的二进制算术编码中，源字母表被固定为两种可能的二元状态或者数值，例如0和1，这是为什么之前y(t)的分量被二元化的原因，如下文所述。

在当前情况下，认识到在偏移矢量差的概率统计中，按照CABAC(基于上下文的自适应二进制算术编码)的算术编码导致较高的压缩率。例如在D.Marpe，H.Schwarz and T.Wiegand：Context-BasedAdaptive Binary Arithmetic Coding in the H.264/AVC VideoCompression Standard(invited paper)，IEEE Transactions on Circuits andSystems for Video Technology，Vol.13，No.7，p.620-636，July 2003中描述了CABAC。通过对聚类减少的矢量y(t)或者未聚类的运动矢量d(t)使用CABAC或者基于此的二进制算术编码，获得更高的数据压缩率。

下面将描述编码装置56的内部结构。图4首先示出了装置56的大致结构。如图所示，其由二进制化装置100和用于二进制算术编码的装置102的串行系列组成。二进制化装置接收待编码的值y(t)并对其进行二进制化，其中数值的二进制化表示将非二进制值转换成二进制表示。如下所述，根据本实施例的二进制化装置典型的使用两种二进制化方案的组合，即一元型二进制化或更严格的说截断一元(TU)二进制化和k阶指数Golomb二进制化。装置100进行的二进制化的结果是一系列表示相应待编码值的比特，待编码值例如替代偏移矢量差y(t)的分量x，y或z。

数值二进制化的结果也可以被称为二进制文件链或者一系列二元判决或二进制文件(bin)。如果认为二进制化是依靠二叉树将二进制化数值映射到二进制文件链，那么将产生以上这种指定结果，其中二叉树的叶子表示将被二进制化的值的可能数值，树的节点表示二进制判决，而从一个节点到下一层的两支独立的分枝则分别和可能的二进制数值0和1相关联。然后待二进制化的数值被映射到从二叉树的根到与待二进制化的数值对应的叶子的路径上产生的二进制文件链或二进制文件系列。

将参照图5更具体的阐述装置100所使用的TU二进制化和k阶指数Golomb二进制化的组合，其中图5图示了二进制化装置100的功能。如图所示，二进制化装置100首先根据第一二进制化方案这里即一元二进制化方案，对边界值s和待二进制化的值y(t)中的最小值进行二进制化，来获得主前缀。值x的一元二进制化产生长度为x的码字，它以x-1个1开头，以一个0结尾。严格说来，这里用于前缀二进制化的TU二进制化表示使用边界值w的一元二进制化，这里w等于s或者15。在等于或者大于s的值的TU二进制化中，相比于纯粹的一元二进制化，结束的0被省略。

在随后的步骤122中，二进制化装置100检查待二进制化的值y(t)是否大于边界值s，其中如果不是这种情况，那么二进制化装置100终止124对待二进制化的该值y(t)的二进制化处理。结果在这种情况下，二进制化结果只由前缀组成。否则，装置100在步骤126中根据第二二进制化方案这里即k阶指数Golomb方案，对待二进制化的值y(t)和边界值s的差值进行二进制化，来获得主后缀。

步骤128中将主后缀附在主前缀上来获得二进制化结果和/或二进制文件链。

图6典型的示出了根据图5对k＝0和s＝14的示例情况的二进制化结果，其中图6中的表格在左列140示出了待二进制化值的可能数值，并且二进制化结果和/或相应的比特或者二进制文件系列在其右侧的142示出。可以看到，对于1到14之间的待二进制化值，二进制文件系列142仅由前缀组成。

待二进制化并且大于s的值不仅包括TU前缀144，还包括后缀145，这里后缀表示对待二进制化的值b减去s后的0阶指数Golomb二进制化。虚线146表示主后缀145自身可以由次前缀即虚线146左侧部分和次后缀即虚线右侧部分组成。图6表格中的最后一行表示二进制文件号，它可能与各二进制文件和上下文模型的关联有关，这将在下面讨论。

为了完备性，下面的伪程序代码示出了根据k阶指数Golomb方案，如何将待二进制化的值b映射到比特系列，或者二进制文件系列是如何依赖b进行构建的：

while(1){

     if (b>=(1<<k)){

         set(1)        //设置一元次前缀的1

         b=b-(1<<k)

         k++

     }   else{

         set(0)        //设置一元次前缀的结尾0

         while(k--)    //在二元表示中用k个数字

               set((b>>k)&0x01)  //产生次后缀

         break

     }

}

其中k是指数Golomb方案的阶数，后面的加号“++”表示递增1而后面的减号“--”表示递减1，“x＜＜y”是对x的二补数表示移位y的二进制数位的算术移位运算，而“x＞＞y”类似的是对x的二补数表示向右移位y的二进制数位的算术移位运算，而“&”表示作用于二补数表示上的逐比特“与”运算。“set”命令是表示比特系列中的一个比特被设为括号中的数值。

换句话说，主后缀的次前缀是值l(b)＝[log₂(b/2^k+1)]的一元码，其中次后缀是数字b+2^k(1-2^l(b))使用k+l(b)个有效位的二进制表示。

根据图7，将描述用于对二进制化结果的二进制文件进行二进制算术编码的装置102的功能。在步骤160中连续检查二进制文件链的二进制文件是否该二进制文件是主前缀的一部分。如果是这种情况，装置102在步骤162中使用二进制文件的自适应二进制算术编码。这意味着对二进制文件或比特使用可变概率估计，以便初步细分当前概率区间，然后依赖二进制文件的值来更新概率区间为细分概率区间的两个半区间中的一个，其中根据当前二进制文件的值更新下一个二进制文件的概率估计。这里，也可在步骤162中执行上下文相关的自适应二进制算术编码，这也是带有CABAC的情况。在这种情况下，装置102没有对主前缀的所有二进制文件或者比特位置使用相同的概率估计，而是对各个二进制文件位置指派不同的上下文模型，其自适应概率估计又分别与所述上下文模型关联。

如果步骤160中的检查是否定的，在步骤162中检查二进制文件是否是主后缀的一部分。如果只将量化的替代偏移矢量差提供给编码器56，该步骤可以省略，然而由于侧面信息的传输也可能不是这样的情况。如果步骤164处的检查是肯定的，那么装置102在步骤166中使用静态概率估计来进行当前二进制文件的二进制算术编码，根据该概率估计二进制文件以固定的概率p具有值1，以固定的概率1-p具有值0。优选的，p＝0.5。对主后缀的二进制文件使用静态统计概率估计能大大减少精力消耗，因为不需要对自适应概率估计或者上下文模型的管理。

通过前面描述的用于自适应二进制算术编码和另外的待编码符号概率的上下文相关模型的方法组合，以上描述的算术编码方案实现了对待编码的信号统计的高度适应性，并表示了一种格外有效的熵编码方法。实现了压缩的显著进步。此外，根据上述方式的算术编码由于其低复杂度而适用于硬件和软件中的集成，特别是当使用CABAC来实现时，其中区间更新和概率估计的更新以基于表格的方式来运行而没有乘法运算。

特别地，前面描述的TU和k阶指数Golomb二进制化的组合能实现相互之间偏离相对较大的任意幅度的量化替代偏移矢量差的高效表示，因为它们是根据上述算法通过概括相似和相邻的偏移矢量差产生的。二进制表示的一元部分的最佳长度s以及使用的Golomb码的阶数k是根据待编码的全部数值来确定的。通过将数种上下文模型用于对二进制化的二进制文件序列进行二进制算术编码，产生对信号统计更好的适应。

下文指出关于算术编码的情况。当然，可以对每一个网格再次执行码字的产生和适配。但是，通过已经描述的对类似和相邻的偏移矢量差概括到聚类中，要传输的值y(t)的数量减少了。这里，数量可以变得很小，使得待编码的符号的分布关于其用于依据上述算术编码方案进行算术编码的能力不再是最优的，因为连续的两个3D网格之间没有出现适用于此编码的频率分布。于是为了高效率的算术编码，一列连续3D几何图形的预测偏移矢量可被概括为所谓的网格分组或者数据部分分组，然后为此确定公共码字，即用连续的区间细分和(上下文)适配。于是，相对于单独网格的独立帧到帧编码或者网格到网格编码，整个分组的偏移矢量差共同进行算术编码。通过这种概括，产生了更合适的符号频率或者分布函数。

为了完备性，下文将参照图8，描述适合于对根据图1的编码器产生的编码数据流进行解码的解码器结构。图8的解码器一般地以200表示。它的结构主要和编码器10结构中从输出14延伸到网格存储器50的部分相对应，不同点是算术编码理所当然被转换成算术解码。相应的，解码器200包含初始解码器或者帧内解码器202，其连接到帧内解码路径204，该路径在用于接收编码数据流的输入210和用于输出解码数据流或者重建数据流的输出212之间延伸，经过输入侧开关206和输出侧开关208。

除了帧内解码路径204，还存在有帧间解码路径214，其中用于执行和装置56的编码相逆的算术编码的算术解码装置216、逆缩放装置218、聚类分解装置220、合并器或者加法器222以及合并器或者加法器224串联，并且其从输入210延伸到开关208。组件218-224在功能性和必须的任务上对应于编码器10的组件38、40、32和48。相应的，解码器200包含时间/位置预测装置226，其输入连接到加法器222的输出和加法器224的输入之间，其输出通过开关228连接到加法器222的输入。开关228对应于图1的开关44，并将或者预测装置226的输出或者逻辑0切换到加法器222的输入作为替代预测值。加法器222的另一输入连接到聚类分解装置220的输出。类似的，解码器200包括网格存储器230，其输入连接到加法器224的输出，其输出通过对应于开关52的开关232连接到加法器224的输入。设置开关232来将预测替代值0或者网格存储器230的输出信号施加到加法器224的输入。图8中没有示出的控制装置控制开关206、208、228和232，来以和图1中已经描述的方式相对应的方式调节解码器中的帧内模式和帧间模式，其中开关206和208总是同步工作。

解码器200的功能从前面的图1描述中得出，并且因为该原因而在下文中再次简单略述。当待解码的数据流到达输入210，首先是帧内模式存在，于是帧内解码装置202接管第一数据部分或网格的解码。结果通过开关208在输出212输出，作为重建的/解码的数据流的一部分。解码结果通过串联连接被传送到逆缩放装置218的输入，为了清晰该连接没有在图8中示出，但是在帧内模式中对应于图1编码器的装置34和36的串联连接，由此在帧内模式中获得了网格重建，其进入到网格存储器230中。这里，开关228和232都切换到替代预测信号0。

下一个数据部分的解码已经通过帧间解码路径214进行。接收的、算术编码的、量化的替代偏移矢量差在解码装置216中经受算术解码。更具体的，解码器216为编码值y(t)一个二进制文件接一个二进制文件地确定二进制文件系列，这通过装置216根据由与主前缀或者主后缀的关系而将要使用的自适应或者静态概率估计分割当前的概率区间，并且检查接收的编码数据流中的码字是否位于产生的上半段或者下半段等等来进行。这样，装置216获得了待解码值y(t)的二进制化，然后它反向即从二进制化中确定非二进制化表示形式的值。结果是值y(t)，其在编码器10中已被提供给装置56。

此后，过程如图1中所述，即数值y(t)被逆缩放和分解来获得重建形式的偏移矢量差e^(t)。如果在预测装置226中没有对偏移矢量差的预测值，也就是说在编码中也没有预测值，那么特别的偏移矢量差e^_i(t)已经表示了偏移矢量d^(t)，并且因此通过加法器222与替代预测值0合并。否则，加法器222完成e^(t)和d^(t-1)之间的加和。类似的，加法器224完成d^(t)和m^(t-1)之间的加和，于是结果在输出212输出。

参照前面的描述，将指出如下内容。尽管前面已经以多边形网格参数化的背景描述了本发明，但是本发明还可以应用到其它的参数化。例如样条参数化通过将表面一块接一块的或者总体上参数化来定义一个3D图形模型为其中顶点作为控制点的函数。最著名的形式之一是以样条来描述，样条中使用低阶多项式，例如立方B样条。

另一可能的可应用本发明的参数化形式是由片状参数化或者片状表示组成。这是一种特别是在计算机断层摄影术中应用的表面描述形式。它通过一系列2D截面区域产生，这些区域在3D空间中的位置是已知的。然后这些截面区域的轮廓通过多边形或者参数化函数连接到3D对象。

另一种参数化的形式是所谓的点云。这里通过将控制点扩展到简单的3D几何体例如球体或者椭圆体来产生表面描述。通过接触和穿透这些几何体，产生图形模型的闭合表面。

Voxel模型参数化形成没有连接的特种3D描述。这里，使用立方体或者长方体作为几何体，它们依赖于实施例同等大小或者大小不同，其中几何体的位置由控制点确定。

骨架模型参数化使用控制点作为描述了3D模型骨架的多个一维参数化函数的支撑位置。模型的表面通过骨架函数的径向扩展来产生，例如作为圆柱体、椭圆体或者圆块。

最后，还有一种形式的参数化，其中使用了几何图元(geometricprimitive)。这里3D图形或者对象可以表示为简单的所谓几何图元或者若干图元的集合。图元可以是球体、圆锥体、棱锥体、截圆锥体、截棱锥体、圆柱体、棱柱、矩形块、椭圆体或者平行六面体，它们的位置由控制点表示。

如前所述，依赖于使用的参数化，在空间预测中确定当前待编码的顶点的空间相邻点的方式可能会改变。

在前面描述的确定了时间连续的网格的运动或者偏移矢量的外环中，以及用于时间或空间相邻的偏移矢量间差值形成的内环中，在装置36中进行缩放。也可以省略该缩放，因而块38和/或218可省略。对于研究本发明的技术人员来说进一步的普遍化是显然的，这就是为什么上述特殊实施例不应理解为限制性的原因。

因此上述实施例阐释了用于对时变3D计算机图形模型编码和解码的方法和布置，其中编码和解码包括运动补偿、量化和算术编码，以及相应的计算机和相应的计算机可读介质，计算机程序以可执行的方式存储在该介质上。

特别的，以上实施例描述了用于3D网格帧内-帧间编码的完整系统，其中以同样的方式处理静态和动态模型(有和没有拓扑变化)。也可以在固定或变化数目的编码网格后转变到帧内模式。在连续时刻的3D网格的顶点之间可进行偏移矢量预测。单独的对每个时刻，或者共同的对网格分组的多个连续时刻，使用用于3D网格的偏移矢量和偏移矢量差算术编码的CABAC自适应和最优化，使得进一步增加的压缩率成为可能。在编码器中带有中值预测或者公共分组预测以及在解码器中带有或者不带有侧面信息的情况下，进行一个或多个顶点的一个或多个偏移矢量的逐个分量预测。在之前空间和时间编码的顶点的偏移矢量的帮助下，提供了用于中值预测的相应侧面信息的形成和可选传输。同样地，一组待编码的偏移矢量或顶点的公共预测值的形成和传输是可能的。待编码的顶点的原始偏移矢量和相应预测偏移矢量之间的逐个分量的偏移矢量差的量化允许小的数值，其可以更容易被压缩。待编码的顶点的原始偏移矢量和相应的预测偏移矢量之间的量化或未量化的偏移矢量差的熵解码提供了进一步的压缩。通过将在解码器计算出的中值预测值或者分组预测值与解码的偏移矢量差加和，在解码器侧实现编码顶点的解码。如上所述，另外还设置了利用上下文自适应算术编码器的熵编码，就像相应的熵解码。如上所述，在之前空间和时间编码的顶点的偏移矢量以及这些顶点位置的帮助下，编码器和解码器处上下文计算成为可能。

最后要指出的是，根据环境，本发明的编码方案也可以以软件实现。实现方式可以是在数字存储介质上，特别是含有可被电方式读出的控制信号的软盘或者CD上，存储介质能够与可编程计算机系统协作，使得相应的方法得以执行。一般来说，该发明也可含在计算机程序产品中，程序代码存储于机器可读的载体上，当计算机程序产品在计算机上运行时，可执行根据本发明的方法。换句话说，该发明也可以实现为计算机程序，该程序含有在计算机上运行时来执行该方法的程序代码。

特别的，流程图的方框中的以上方法步骤或者装置方框可以单独的或者它们中的一些以子程序实现。可选地，当然这些方框也可能以ASIC的单独部分实现。