编码网格模型的方法和装置、编码的网格模型、以及解码网格模型的方法和装置

技术领域

本发明涉及一种用于编码网格模型的方法和装置、编码的网格模型以及 用于解码网格模型的方法和装置。

背景技术

像建筑设计、化工厂和机械CAD(计算机辅助设计)设计的大型3D工 程模型被日益在各种虚拟世界应用中布置，诸如，Second Life^TM和Google  Earth^TM。在多数工程模型中，存在大量的小尺寸到中型尺寸的连接组件，平 均每一个组件都具有上至几百个多边形。如在[SBM01](D.Shikhare，S. Bhakar和S.P.Mudur.“Compression of Large 3D Engineering Models using  Automatic Discovery of Repeating Geometric Features”，2001年11月21-23日， 德国斯图加特)中定义的，如果在网格模型的一个子集中存在任何两个多边 形之间的路径，则该网格模型的子集是一连接组件。此外，这种类型的模型 具有在各种位置、比例和方位(orientation)上重复的许多几何特征。

自从90年代早期以来已经提出了高效地压缩3D网格的各种算法。然而 早期的工作大多集中在压缩具有平滑表面和小三角形的单个连接的3D模型。 对于诸如大型3D工程模型的多连接的3D模型(包含多个连接组件的3D模 型)，单独地压缩组件。这造成了相对低效的压缩。实际上，通过移除不同连 接组件之间的冗余可以大幅增加压缩性能。

[SBM01]提出了一种用于在大型3D工程模型中自动发现重复的几何特 征的方法。然而，对于更高效地压缩3D工程模型还有很大的空间，例如， 没有提供覆盖对于恢复原始模型必需的重复实例的变换信息的压缩解决方 案。考虑到3D工程模型通常所具有的大尺寸连接组件，这种类型的信息将 消耗大量存储。此外，如果使用组件的顶点位置的PCA(首要组件分析)，具 有相同几何和不同连接性的组件将具有相同的平均值和相同的方位轴。现有 技术不适于以各种比例检测和/或压缩重复的图案。两个仅在比例(即，大小) 上不同的组件将不能被识别为相同等效类别的重复特征。此外，期望实现比 [SBM01]中描述的更高的压缩率。

[OG00](O.Devillers和P.Gandoin，“Geometric compression for interactive  transmission”，IEEE Visualization，2000，pp.319-326)公开了一种基于KD树的 压缩算法，用于编码网格模型的所有连接组件的平均值。该算法在每次迭代 时将单元细分成两个子单元，并且编码两个子单元之一中的顶点的数目。如 果父单元包含p个顶点，可以利用算术编码器使用log₂(p+1)比特来编码子单 元之一中的顶点的数目。递归地应用该细分，直至每个非空子单元小到仅包 含1个顶点并且使得足够精确重构顶点位置成为可能。在[OG00]中提及了该 算法对于非均匀分布是最高效的，而正规分布是最坏情况。

发明内容

本发明基于对以下事实的认识：对于多数大型3D工程模型，连接组件 的重复实例的实例位置表明显著的多空间聚集(aggregation)，并且对于这种 情况可以改进[OG00]中描述的算法的效率。即，在大型3D网格模型内的重 复实例通常分布地使得若干实例在一个或很少的小区域内，而在其它相对较 大的区域内不存在实例。如果使用单个KD树来组织并且压缩这种类型的点 数据集(如在[OG00]中提出的)，KD树将是不合理地深，这将使得输出数据 流比所需的长。

本发明提供了对于这种情况的改进。根据本发明，使用若干KD树，每 一个用于被空间聚集的点的一个簇。这些KD树将生成相对短的数据流，并 且因此改进总压缩率。

在一个方面，本发明提供一种用于编码网格模型的点的方法。该方法包 括以下步骤：确定网格模型包括连接组件的重复实例，以及为每个重复实例 确定至少一个参考点，将所述重复实例的参考点分簇至一个或更多簇，以及 使用KD树编码来编码分簇后的参考点，其中，为每个簇生成单独的KD树。

根据本发明的另一方面，一种用于编码网格模型的点的装置，包括：分 析部件，用于确定网格模型包括连接组件的重复实例；确定部件，用于为每 个重复实例确定至少一个参考点；分簇部件，用于将所述重复实例的参考点 分簇至一个或更多簇；以及编码部件，用于使用KD树编码来编码分簇后的 参考点，其中，为每个簇生成单独的KD树。

根据本发明的另外一个方面，一种用于对编码的网格模型的点解码的方 法，包括以下步骤：提取重复的连接组件的实例的数据；使用所提取的数据 解码连接组件的实例；提取定义多个簇的第一数据、定义空间分辨率的第二 数据以及作为所述重复的连接组件的多个重复的位置的第三数据，其中，所 述第三数据被编码为KD树；提取定义所述网格模型内的一部分的第四数据； 以及根据所述第三数据和第四数据确定所述重复的连接组件的多个重复的位 置，其中，将第三数据应用于由第四数据定义的网格模型的所述部分。

根据本发明的又一方面，一种用于对编码的网格模型的点解码的装置， 包括：第一提取部件，用于从所述编码的网格模型中提取重复的连接组件的 实例的数据；解码部件，用于使用所提取的数据解码连接组件的实例；第二 提取部件，用于提取定义多个簇的第一数据、定义空间分辨率的第二数据以 及作为所述重复的连接组件的多个重复的位置的第三数据，其中，所述第三 数据被编码为KD树；以及第三提取部件，用于提取定义所述网格模型内的 一部分的第四数据；以及确定部件，用于根据所述第三数据和第四数据确定 所述重复的连接组件的多个重复的位置，其中，将第三数据应用于由第四数 据定义的网格模型的所述部分。

根据本发明的一个方面，一种编码的网格模型，包括：多个重复连接组 件，其中所述编码的网格模型包括至少以下内容的编码数据：每个重复的连 接组件的一个示例，所述重复的连接组件的多个重复的位置，所述位置被编 码为KD树，以及所述网格模型内的边界区域，其中，所述KD树参照所述 区域。

在从属权利要求、以下描述和附图中公开了本发明的有利实施例。

附图说明

参照附图描述本发明的示例性实施例，以下附图中示出了：

图1，2D示例中的KD树编码的原理；

图2a)，重复连接组件的多实例的位置；

图2b)，对重复连接组件的多实例的位置的传统KD树编码的结果；

图3，分簇(cluster)后的簇的位置；

图4，基于簇的编码的网格模型的数据结构；

图5，由5574个连接组件组成的会议室的示例性3D网格模型的2D表示；

图6，编码方法和解码方法的示例性流程图；以及

图7分簇方法的示例性流程图。

具体实施方式

图1示例性地示出了2D情况的传统KD树编码的原理。通过被称作父单 元的边界框10包围2D模型。7个顶点位于父单元中。KD树编码算法开始于 使用预定数目的比特编码顶点的总数，并且然后递归地细分单元。每次其将 父单元细分成两个子单元，编码两个子单元之一中的顶点的数目。按照惯例， 这可以是左侧子单元(在垂直分割后)或上单元(在水平分割后)。如果父单 元包含p个顶点，可以以算术编码器使用log₂(p+1)比特来编码子单元之一中 的顶点的数目。递归地应用这个细分，直至每个非空子单元小到仅包含1个 顶点并且使得足够精确重构顶点位置成为可能。为了压缩所有重复实例的位 置，最初将所有位置的整个边界框10视作父单元。在图1的示例中，使用 32比特编码顶点的总数(7个)。然后应用垂直分割，使得获得左侧子单元 V1和右侧子单元V2。在下一编码步骤中，编码左侧子单元V1的顶点数(4 个)。通过父单元内的顶点的数目确定用于编码的比特数：其是log₂(7+1)＝3 比特。根据父单元中的顶点数和左侧子单元V1中的顶点数，可以推算出右 侧子单元内的顶点数，并且因此不需要编码。

在下一步骤中，应用水平分割。现在作为父单元V1的左侧子单元V1被 分割成上侧子单元V1H1和下侧子单元V1H2。现在作为父单元V2的右侧子 单元V2被分割成上侧子单元V2H1和下侧子单元V2H2。编码在具有两个顶 点的左上侧子单元V1H1继续。因此，接下来编码数目2，其中在算术编码器 中使用log₂(4+1)＝2.3比特。如以上描述的，在左下侧子单元V1H2中的顶点 数不必编码，这是因为其可以根据左侧单元V1和左上侧子单元V1H1中的顶 点数推算。然后，将相同的例程应用于右侧单元V2，这造成使用2比特编码 零。如图1所示，还需要两个分割步骤，直至每个顶点在单独的单元内，并 且甚至更多的步骤是必需的，直至每个顶点足以位于其单元内。每个步骤都 需要编码增加数目的1和0，取决于所需精度，附加步骤的数目可能高。

以上提及的现有技术文献[OG00]暗示单个KD树提供优化的压缩。但是， 已经发现，在空间聚集的点的情况下存在额外冗余，本发明可以减少该额外 冗余。点的空间聚集意味着对于多个后续分割操作，总有一个子单元是空的。 因此，如果点是空间聚集的，任何等级(k+1)将消耗与其父等级k相同数目 的比特。原理上，KD树的传统使用通过将KD树的每个等级变窄来改善压缩 率。本发明通过使用多个KD树并且使每个KD数具有更少的等级来改善压 缩率。

本发明应用KD树编码算法不仅用于编码顶点位置，而且用于编码重复 连接组件的位置。图2a)示出了多个重复连接组件21-24位于3D网格模型的 边界框20内的示例。如同在许多大型3D网格模型中，位置在边界框内非常 不均匀地分布。如果仅仅将KD树编码算法应用于对位置进行编码，在图2b) 中示出了示例性结果。可以看出，在定位簇之前需要5个初始分割步骤。即， 在图2的示例中，编码将如下：12(总数)-6(左侧子单元第一生成)-6-3 (上侧子单元第二生成)-2-3-0(左侧子单元，第三生成)-2-0-0-0(上侧子 单元，第四生成)-2-4-0-3(左侧子单元，第五生成)-2-0-3-0(上侧子单元， 第六生成)，结果是12-6-6-3-2-3-0-2-0-0-0-2-4-0-3-2-0-3-0。以上描述了比特 数目的分配。对于更精确的位置可能需要其它数据。因此，代码包含先前值 或者零的许多重复。

对于本发明，例程和结果代码二者实质上是简略的。根据本发明的一个 方面，将点分簇，即，创建簇并且如果可能将点分配到簇。可以以如图3所 示的方式有利地将图2中所示的点分簇。在这个示例中，在边界框30内有4 个簇31-34。一般地，分簇包括：选择尚未被分簇的并且包括一个或更多点的 第一单元，以及定义包括第一单元或第一单元内的一个或更多点的簇。

在一个实施例中，如图6a)所示，一种用于编码网格模型的点的方法包 括以下步骤：确定E1网格模型包括连接组件的重复实例，以及为每个重复实 例确定E2至少一个参考点，将重复实例的参考点分簇E3到一个或更多的簇 中，以及使用KD树编码来编码E4分簇后的参考点，其中，为每个簇生成单 独的KD树。

在一个实施例中，分簇包括以下步骤：定义围绕网格模型的边界框；将 边界框划分成单元，其中，单元是最小的空间分辨率单位；选择尚未被分簇 的并且包括重复实例的一个或更多参考点的第一单元；以及定义包括所述第 一单元或所述第一单元内的一个或更多参考点的簇。一般地，第一单元是创 建新簇的候选项。在一个实施例中，一个单元足以创建一簇。在另一实施例 中，需要其中每个包括一个或更多点的至少2个相邻单元，用于创建簇。在 另一个实施例中，需要任何数目的相邻单元内的预定最小数目的点，用于创 建簇。

在一个实施例中，仅仅选择第一单元，如果其尚未被分簇并且其包括至 少M个点(例如，M个重复实例的参考点)。在一个实施例中，M是用户可 定义的参数。对应的编码方法包括以下步骤：定义参数M，其中M是单元内 的点的最小数目，以便选择该单元作为用于创建新簇的源。

在一个实施例中，分簇还可包括以下步骤：确定一个或更多其它单元， 其中其它单元是选择的第一单元的邻近单元或者递归的邻近单元(即，邻域 的邻域等)，并且其中每个确定的其它单元包括重复实例的至少一个参考点， 以及将确定的一个或者多个邻近单元添加到所述簇。

在一个实施例中，分簇还包括以下步骤：以每个单元中参考点的数目的 升序或降序排列所有单元，并且根据所述顺序选择第一单元(用于创建新簇 的候选项)。

对于许多大型3D工程模型(诸如图5中所示的示例性会议室)，实例位 置显著示出了多空间聚集。如果使用一个单个KD树来组织和压缩这种类型 的点数据集，KD数将深得不合理。另一方面，如果使用若干KD树，每个用 于空间聚集的点的一个簇，KD树将生成相对较短的数据流并且因此改善总压 缩率。例如，在如图5所示的由5574个连接组件组成的会议室的3D模型中， 多个重复连接组件是椅子RCC1、地毯RCC2的重复纹理元素或大型吊灯的 重复结构元素RCC3。为了使大型3D工程模型的紧凑存储和快速传输成为可 能，本发明提供了对于编码所有重复实例的位置尤其有利的高效压缩策略。 在一个方面，本发明提供一种对离散点、尤其对显著示出多空间聚集的那些 点的高效压缩方法。大型3D工程模型中的重复实例的位置通常具有这种特 征。

本发明提供一种基于分簇的KD树的压缩算法，用于高效压缩具有显著 多空间聚集的离散点数据集。根据输入点的空间位置首先将它们分簇。每个 簇包含被空间分簇的一组点。然后通过由一个KD树组织属于每个簇的所有 点来压缩每个簇。

以下将描述用于编码的示例性分簇方法。设C_Point表示所有的点的簇。 开始，C_Point是空的。

步骤1：将要压缩的所有点的整个边界框细分成N*N*N个单元。

步骤2：根据落入每个单元的点的数目以升序将所有单元排列成队列 Q_Cell。

步骤3：如果(Q_Cell不是空的)

从Q_Cell中弹出单元P。跳过空单元。去步骤4。

否则去步骤6。

步骤4：如果(P不属于C_Point中的任何簇)

生成新的簇C，仅包括P，并且将C添加到C_Point。

去步骤5。

否则去步骤3。

步骤5：检验C中的所有单元的所有邻近单元。

设P1表示C中的任何单元的任何邻近单元。

如果((落入P1的点的数目＞B)

&&(P1不属于C_Point中的任何簇))

将P1添加到C。

(B是用户指定的阈值。)

在完成所有邻近单元的检验后，去步骤3。

步骤6：独立地压缩落入属于C_Point中的相同簇的单元中的点。通过使 用单独KD树组织对应的点，并且基于例如[OG00]将它们压缩来压 缩每个簇。

用户定义的参数B指定一个单元中必须有多少个点以便将其作为邻域添 加到簇。虽然在一个实施例中B＝1，但是其他实施例可能要求更高值的B。 图7中示出了分簇方法的流程图。

表1示出了可以作为结果的比特流的语法。ae(v)意思是算术编码，有点 类似于H.264/AVC中的算术编码。

表1：实例位置的比特流语法

示例性比特流的语义为如下：

BoundaryBox_Of_All_Instance_Positions指示所有实例位置的边界框。

Num_Of_Clusters指示簇的数目。

N指示单元的分辨率，即，在以上描述的编码例程的步骤1中的N。

Indices_of_Two_Boundary_Cells_of_cluster[i]指示定义cluster[i]的边界框 的两个单元的索引。其具有2*Log₂(n*n*n)个比特。

KD-tree_of_current_cluster表示用于记录当前簇的KD树的比特。

在一个实施例中，在编码期间，在实际分簇之后存在确定每个簇的边界， 和对应的两个边界单元的步骤。通过两个边界单元的索引可以表示边界。当 前簇的边界单元是具有每个维度的最小索引和最大索引的单元。例如，如果 在2D情况下，属于簇的点在{x_min，x_max}和{y_min，y_max}的范围内，则边界单元 处于x_min，x_max和y_min，y_max，即使这些单元实际上不在该簇内。然而，使用它 们的索引来定义当前簇的局部边界框。在局部边界框内，可以使用局部坐标， 这减少比特量。

在一个实施例中，计算当前簇的KD树具有以下步骤：计算落入当前 cluster[i]的实例的相对位置，以及计算边界框以外的全局坐标系统中的对应的 实例位置。

在一个实施例中，所述编码方法还包括定义网格模型的空间分辨率(例 如，表1中的N)的步骤。在这种情况下，单元是根据定义的空间分辨率的 最小的空间分辨率单元。空间分辨率对重构的精确度有影响，这是因为在编 码期间处于特定单元内某处的位置可能在解码后仅在该单元内的预定位置被 再现，例如在单一的中心。为了更加精确的位置，需要更高的空间分辨率。 在一个实施例中，N是预定的。在另一实施例中，可以根据质量需求来选择 N，例如，可以将其降低来再现低分辨率显示。

如以上描述的，现有技术方法在点非常不均一地分布时效率低。在一个 实施例中，编码方法还包括以下步骤：确定点的空间均一性(homogeneity) 量度(其中，如果点均匀地分布则空间均一性的量度高，而如果分布更加不 均匀则空间均一性量度低)，将空间均一性与阈值比较，以及仅当空间均一性 低于阈值时执行分簇。例如，编码方法可以包括以下步骤：确定重复实例的 参考点的空间均一性的量度，将空间均一性与阈值相比较，以及仅当空间均 一性低于阈值时(即，如果点的分布非常不均一)执行分簇。

在一个实施例中，编码方法还包括以下步骤：如果空间均一性低于阈值， 则修改空间分辨率，测量空间均一性以及重复这些步骤直至空间均一性不低 于阈值。

图4示出了基于簇的编码的网格模型的数据结构。指代特定类型的连接 组件和完整3D网格模型的根包括至少一个簇，至少一个簇指代重复的连接 组件并且被表示为KD树KD-T1，...，KD-T3。在图4的示例中，连接组件根 CCr代表特定连接组件。例如连接组件可以是3D工程网格模型中的特定类型 的螺旋(screw)。在本示例中，在3D模型内存在其中经常使用这种类型的螺 旋的3个区域。将每个区域表示为簇，其通过单独的KD树KD-T1，...，KD-T3 表示。连接组件的少数或单个实例还可能在其它区域中出现。在一个实施例 中，没有将这些实例分簇，而是在单独的结构T4(例如，特殊KD树或仅仅 是坐标列表)中描述它们的位置。三个簇KD树KD-T1，...，KD-T3的每一个 指代连接组件的多个实例的一个簇并且包括位置信息，例如簇的边界单元的 索引。

以下将描述本发明的其它实施例。

在一个实施例中，一种用于编码网格模型的点的装置，包括：用于确定 该网格模型包括连接组件的重复实例的确定部件；以及用于为每个重复实例 确定至少一个参考点的确定部件；分簇部件，用于将所述重复实例的参考点 分簇至一个或更多簇；以及编码部件，用于使用KD树编码来编码所分簇的 参考点，其中，为每个簇生成单独的KD树。

在一个实施例中，用于分簇的部件包括：定义部件，用于围绕网格模型 定义边界框；划分部件，将边界框划分成单元，其中，单元是最小的空间分 辨率单位；选择部件，用于选择尚未被分簇的并且包括重复实例的一个或更 多参考点的第一单元；以及定义部件，用于定义包括所述第一单元或所述第 一单元内的一个或更多参考点的簇。

在一个实施例中，装置还包括：确定部件，用于确定一个或更多其它单 元，其中其它单元是选择的第一单元的邻近单元或者递归的邻近单元，并且 其中每个确定的其它单元包括重复实例的至少一个参考点；以及添加部件， 将所述确定的一个或多个邻近单元添加到所述簇。

在一个实施例中，分簇部件还包括：组织部件，用于以每个单元中参考 点的数目的升序或降序排列所有单元，其中根据所述顺序选择第一单元(即， 簇的初始单元)。

在一个实施例中，分簇部件包括：用于确定当前簇的边界单元(具有每 个维度的最小索引和最大索引的单元)的部件。

在一个实施例中，编码装置还包括：用于定义空间分辨率的部件，其中 单元是根据所定义的空间分辨率的最小的空间分辨率单位。

在一个实施例中，编码装置还包括：分析部件，用于确定重复实例的参 考点的空间均一性的量度，其中，如果参考点均匀地分布则空间均一性的量 度高，而如果分布更加不均匀则空间均一性的量度低；比较部件，用于将空 间均一性与阈值比较；以及控制部件，用于仅当空间均一性低于阈值时执行 分簇。

在一个实施例中，一种编码的网格模型包括多个重复连接组件，其中， 编码的网格模型包括至少以下内容的编码数据：每个重复连接组件的一个实 例、所述重复连接组件的多个重复的位置，所述位置被编码为KD树，以及 在所述网格模型内的边界区域，其中所述KD树指代所述区域。

在一个实施例中，编码的网格模型的边界区域的数据包括边界单元的索 引。

在图6b)示出的一个实施例中，一种用于对编码的网格模型的点解码的方 法包括以下步骤：提取D1重复连接组件的实例的数据；使用所提取的数据 解码D2连接组件的实例；提取D3定义多个簇的第一数据(Num_Of_Cluster)、 定义空间分辨率的第二数据(N)以及作为所述重复连接组件的多个重复的 位置的第三数据(KD-T1，...KT-T3)，其中，所述第三数据被编码为KD树；提 取D4定义所述网格模型内的一部分的第四数据(Index_Boundary_Cluster)， 以及根据所述第三数据和第四数据确定D5所述重复连接组件的多个重复的 位置，其中，将第三数据应用于由第四数据定义的网格模型的所述部分。

在解码方法的一个实施例中，第四数据(Index_Boundary_Cluster)包括 网格模型内的两个单元的索引，其中单元是根据由所述第二数据定义的空间 分辨率的最小的空间分辨率单位。

实验显示，对于图案位置数据，根据本发明的基于簇的KD树压缩相比 较于基于传统KD树的压缩，可以节约50％的存储空间 (Clus_Comp/Coor_Comp)。

表2中，#C是连接组件的数目，#P是重复组件的数目，Coor.(K)是以K 字节形式的原始的实例位置的大小，Coor_Comp(K)是使用一个KD树压缩的 实例位置的大小，#Clu是簇的数目以及Clu_Coor_Comp(K)是通过基于分簇 的KD树的压缩方法的压缩的实例位置的大小。

表2对于2个示例模型的示例性压缩效率。

虽然已经作为应用于本发明优选实施例而示出、描述、并且指出本发明 的基本的新颖的特点，但应该理解，本领域技术人员在不背离本发明的精神 的情况下，在所描述的装置和方法中、在所公开的设备的形式和细节、以及 以在它们的操作中，可以做出各种省略和替换以及改变。虽然关于重复连接 组件的实例位置公开了本发明，本领域技术人员将认识到在此描述的方法和 设备在原理上可以应用于关于压缩一组离散点的任何场景。在此明确地意欲 以实质上相同方式执行实质相同功能以达到相同效果的那些元件的所有组合 在本发明的范围以内。从描述的一个实施例到另一个实施例的元件的替换完 全是可设计并且可想到的。

应该理解仅仅以示例方式描述了本发明，可以在不背离本发明的范围的 情况下进行细节的修改。说明书和(在适当时)权利要求和附图中公开的每 个特点都可以单独提供或者以适当的结合来提供。可以将所述特点在适当时 实施于硬件、软件、或者二者的结合。权利要求中出现的参考数字仅用于例 示而不对权利要求的范围具有限定效果。