本发明提出一种自适应的三角形多分辨率网格顶点位置预测方法，包括以下步骤：对原始网格进行初始化以生成所述原始网格的平滑近似估计网格；根据所述原始网格的平滑近似估计网格生成基本层；根据所述基本层生成增强层；根据所述增强层分别依据两种预测类型计算第一预测值和第二预测值；根据所述第一预测值和第二预测值以及最优决策准则选择所述第一预测值或第二预测值作为最终的网格顶点位置预测值。本发明提出了一种自适应的三角形多分辨率网格顶点位置预测方法和装置，能够高效地解决三角形多分辨率网格顶点位置的预测问题。
1.一种自适应的三角形多分辨率网格顶点位置预测方法，其特征在于，包括以下步骤：对原始网格进行初始化以生成所述原始网格的平滑近似估计网格；
根据所述增强层分别依据两种预测类型计算第一预测值和第二预测值；以及根据所述第一预测值和第二预测值以及最优决策准则选择所述第一预测值或第二预测值作为最终的网格顶点位置预测值，其中，所述对原始网格进行初始化以生成所述原始网格的平滑近似估计网格进一步包括：读取所述原始网格的连接信息和控制信息，根据所述原始网格的连接信息得到对应的Laplacian矩阵；和根据所述Laplacian矩阵构建超定方程，并采用最小二乘的方法求解所述超定方程以得到所述原始网格的平滑近似估计网格，其中，所述根据增强层分别依据两种预测类型计算第一预测值和第二预测值包括：采用平滑近似估计网格中对应顶点的几何位置作为当前顶点的第一预测值υκ*，其中，k为顶点号；和利用当前重构得到的增强层中与顶点υ相邻的顶点的位置信息获得当前顶点的第二预测值其中，所述的根据所述第一预测值和第二预测值以及最优决策准则选择所述第一预测值或第二预测值作为最终的网格顶点位置预测值进一步包括：根 据 如 下 准则 确 定 所 述 顶 点 的 多个 相 邻 顶 点 的 最 优 决 策值 Pκ：其中，υκ为υ的相邻顶点；和
根据所述多个相邻顶点的最优决策值Pκ确定最终的网格顶点位置预测值，如果所述多个相邻顶点中的最优决策值Pκ为0的相邻顶点个数多于Pκ为1的相邻顶点个数，则选择第一预测值υκ*作为最终的网格顶点位置预测值，否则选择第二预测值 作为最终的网格顶点位置预测值。
2.一种自适应的三角形多分辨率网格顶点位置预测装置，其特征在于，包括：平滑近似估计网格生成模块，用于对原始网格进行初始化以生成所述原始网格的平滑近似估计网格；
基本层生成模块，用于根据所述平滑近似估计网格生成模块生成的原始网格的平滑近似估计网格生成基本层；
增强层生成模块，用于根据所述基本层生成模块生成的所述基本层生成增强层；
计算模块，用于根据所述增强层分别依据两种预测类型计算第一预测值和第二预测值；以及选择模块，用于根据所述第一预测值和第二预测值以及最优决策准则选择所述第一预测值或第二预测值作为最终的网格顶点位置预测值，其中，所述的自适应的三角形多分辨率网格顶点位置预测装置，其特征在于，所述平滑近似估计网格生成模块包括：矩阵生成子模块，用于读取所述原始网格的连接信息和控制信息，并根据所述原始网格的连接信息得到对应的Laplacian矩阵；和平滑近似估计网格生成子模块，用于根据所述Laplacian矩阵构建超定方程，并采用最小二乘的方法求解所述超定方程以得到所述原始网格的平滑近似估计网格，其中，所述的自适应的三角形多分辨率网格顶点位置预测装置，其特征在于，所述计算模块采用平滑近似估计网格中对应顶点的几何位置作为当前顶点的第一预测值υκ*，其中，k为顶点号，及利用当前重构得到的增强层中与顶点υ相邻的顶点的位置信息获得当前顶点的第二预测值 ，其中，所述的自适应的三角形多分辨率网格顶点位置预测装置，其特征在于，所述选择模块根据如下准则确定所述顶点的多个相邻顶点的最优决策值Pκ：其中，υκ为υ的相邻顶点，并根据所述多个相邻
顶点的最优决策值Pκ确定最终的网格顶点位置预测值，如果所述多个相邻顶点中的最优决策值Pκ为0的相邻顶点个数多于Pκ为1的相邻顶点个数，则选择第一预测值υκ*作为最终的网格顶点位置预测值，否则选择第二预测值 作为最终的网格顶点位置预测值。
自适应的三角形多分辨率网格顶点位置预测方法和装置
技术领域
[0001] 本发明涉及通信技术领域，特别涉及一种自适应的三角形多分辨率网格顶点位置预测方法和装置。
背景技术
[0002] 图形数据越来越广泛的应用在各种不同的领域，包括视频游戏、工程设计、建筑漫游、虚拟现实、电子商务和科学可视化。在各种表示的工具中，三角形网格提供了一种非常有效的3D网格模型表示方法。一般来说，连接数据描述了顶点之间的邻接关系；几何结构数据确定了顶点的位置；属性数据确定了一些属性，比如法向量、材质反射率和纹理坐标。在大多数情况下，几何结构和属性数据是和顶点对应的，因此，它们经常被称为顶点数据。
[0003] 大多数的3D三角形网格压缩算法都可用相同的算法来处理几何结构和属性数据。
[0004] 现有的编码方案仅仅需要平均每个像素很少的比特来对连接数据进行编码，并且它们的性能被认为已经非常接近于最优。而几何结构数据占据压缩的网格数据的主要部分，因此现在更多的关注于几何结构的编码。大多数的几何编码方法包含三个过程：顶点位置的量化、量化后的顶点位置的预测以及预测残差的熵编码。预测过程充分利用相邻顶点坐标之间的空间相关性，它是减少几何结构数据的关键。
[0005] 现有的网格顶点位置预测方法有差分预测，线性预测，平行四边形预测，蝶形预测以及二阶预测。所有这些预测方法都可以看成是具有特定选择系数的线性预测的一种特殊情形。目前网格顶点位置预测主要是针对单分辨率的网格，对于多分辨率的网格，需要为特定的多分辨率网格生成方法设计不同的预测方法，并没有一种通用的预测方法。
发明内容
[0006] 本发明的目的旨在至少解决上述技术缺陷，特别是解决三角形多分辨率网格顶点位置的预测问题。
[0007] 为达到上述目的，本发明一方面提出一种自适应的三角形多分辨率网格顶点位置预测方法，包括以下步骤：对原始网格进行初始化以生成所述原始网格的平滑近似估计网格；根据所述原始网格的平滑近似估计网格生成基本层；根据所述基本层生成增强层；根据所述增强层分别依据两种预测类型计算第一预测值和第二预测值；根据所述第一预测值和第二预测值以及最优决策准则选择所述第一预测值或第二预测值作为最终的网格顶点位置预测值。
[0008] 本发明再一方面还提出了一种自适应的三角形多分辨率网格顶点位置预测装置，包括：平滑近似估计网格生成模块，用于对原始网格进行初始化以生成所述原始网格的平滑近似估计网格；基本层生成模块，用于根据所述平滑近似估计网格生成模块生成的原始网格的平滑近似估计网格生成基本层；增强层生成模块，用于根据所述基本层生成模块生成的所述基本层生成增强层；计算模块，用于根据所述增强层分别依据两种预测类型计算第一预测值和第二预测值；和选择模块，用于根据所述第一预测值和第二预测值以及最优决策准则选择所述第一预测值或第二预测值作为最终的网格顶点位置预测值。
[0009] 本发明提出了一种自适应的三角形多分辨率网格顶点位置预测方法和装置，能够高效地解决三角形多分辨率网格顶点位置的预测问题。
[0010] 本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
[0011] 本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明显和容易理解，其中：
[0012] 图1为本发明实施例的自适应的三角形多分辨率网格顶点位置预测方法流程图；
[0013] 图2为本发明实施例的原始网格的平滑近似估计网格示意图；
[0014] 图3为本发明实施例的原始网格的边收缩和顶点分裂过程示意图；
[0015] 图4为本发明实施例的增强层示意图；和
[0016] 图5为本发明实施例的自适应的三角形多分辨率网格顶点位置预测装置结构图。
具体实施方式
[0017] 下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。
[0018] 本发明主要在于，在具有原始网格的平滑近似网格和当前增强层网格的条件下，对于通过顶点分裂产生的新顶点的位置可以选择当前增强层网格中相邻的点的加权平均值作为新顶点位置的预测值，也可以选择平滑近似网格中的对应点作为预测值。在这个过程中，采用自适应的方法进行决策如何选择二者之一。自适应的方法为该顶点在当前增强层网格中的相邻点的最优决策类型的投票。如果邻近点大部分选择前者，则新产生的顶点也选择前者；如果邻近点大部分选择后者，则新产生的顶点也选择后者。
[0019] 如图1所示，为本发明实施例的自适应的三角形多分辨率网格顶点位置预测方法流程图，包括以下步骤：
[0020] 步骤S101，对原始网格进行初始化以生成原始网格的平滑近似估计网格。具体地包括：
[0021] 首先，读取所述原始网格的连接信息和控制信息，根据所述原始网格的连接信息得到对应的Laplacian矩阵。具体方法为：以下记原始网格为M，若di是顶点i的度数，那么网格的Laplacian矩阵定义为：
[0022]
[0023] 若控制点集合C中的顶点的几何位置为：
[0024]
[0025] 其中，C＝{s1，s2，…，sm}是控制点在原始网格M中的下标索引，则重构的平滑近似估计网格的顶点位置的坐标x可以由以下超定方程得到：
[0026] Ax＝b，
[0027] 其中，
[0028] 接着，采用最小二乘的方法求解上述超定方程就可以得到原始网格M的平滑近似估计网格M*，如图2所示。其中，M*和M具有相同的连接信息，但是几何结构信息存在一定的差别。
[0029] 步骤S102，根据原始网格的平滑近似估计网格生成基本层。可采用现有的边收缩的方法，如图3所示。在每次收缩过程中，将网格中的一条边收缩，同时边上的一个顶点合并到另一个顶点上，收缩的点对应的边合并到未收缩的顶点上。多次操作，直到得到基本层。在这个过程中，需要记录相应的收缩信息。
[0030] 步骤S103，根据基本层生成增强层。从基本层开始，进行收缩过程的逆过程。每次对一个顶点进行分裂，产生一个新的顶点，如图3所示。根据收缩过程的记录信息可以恢复出新产生的顶点的连接信息。从而可以得到一个新的增强层。同时，还需要确定新产生的顶点的几何位置。如图4所示，为本发明实施例的增强层示意图。
[0031] 步骤S104，根据增强层分别依据两种预测类型计算第一预测值υκ*和第二预测值 k为顶点号。如图3所示，由υ1分裂产生了一个新的顶点υ，并恢复了顶点υ相应的连接信息，得到了一个新的增强层Mκ。在重构的过程中，本发明还需要确定υ的几何位置。对于υ的几何位置，有两种有效的预测方法，以下分别进行说明：
[0032] 第一种预测方式是：采用平滑近似网格中对应顶点的几何位置作为当前分裂顶点的预测值，在图3中，对应顶点的几何位置为υ*。
[0033] 第二种预测方式是：充分利用当前重构得到的增强层Mκ中和顶点υ相邻的顶点的位置信息。在图3中，对应顶点的几何位置为 假设在Mκ中和顶点υ相邻的点有υ1，υ2，υ3，s。同时，本发明会剔除在原始网格中和υ并不相邻的顶点s。这样顶点υ的预测值可以表示为满足要求的相邻点集合的加权平均。
[0034]
[0035] 其中 一般来说，选择λκ相等。
[0036] 步骤S105，根据第一预测值υκ*和第二预测值 以及最优决策准则选择第一预测值υκ*或第二预测值 作为最终的网格顶点位置预测值。对于上述提到的对当前顶点的几何位置的预测值，需要进行自适应的决策。决策方式如下：在图3中分别对满足要求的相邻点集合{υ1，υ2，υ3}判断最优的决策类型，每个顶点υκ的最优决策值Pκ由如下准则得到：
[0037] 其中，υκ为υ的相邻顶点。
[0038] 接着，对决策类型的数量进行投票。若大部分相邻顶点的Pκ选择0，那么当前顶点的位置选择υκ*作为预测值，否则，选择 作为预测值。
[0039] 如图5所示，为本发明实施例的自适应的三角形多分辨率网格顶点位置预测装置结构图。该装置包括平滑近似估计网格生成模块110、基本层生成模块120、增强层生成模块130、计算模块140和选择模块150。平滑近似估计网格生成模块110用于对原始网格进行初始化以生成所述原始网格的平滑近似估计网格。基本层生成模块120用于根据平滑近似估计网格生成模块110生成的原始网格的平滑近似估计网格生成基本层。增强层生成模块130用于根据基本层生成模块120生成的所述基本层生成增强层。计算模块140用于根据增强层分别依据两种预测类型计算第一预测值和第二预测值。选择模块150用于根据第一预测值和第二预测值以及最优决策准则选择第一预测值或第二预测值作为最终的网格顶点位置预测值。
[0040] 在本发明的一个实施例中，平滑近似估计网格生成模块110包括矩阵生成子模块111和平滑近似估计网格生成子模块112。矩阵生成子模块111用于读取原始网格的连接信息和控制信息，并根据所述原始网格的连接信息得到对应的Laplacian矩阵。平滑近似估计网格生成子模块112用于根据所述Laplacian矩阵构建超定方程，并采用最小二乘的方法求解所述超定方程以得到所述原始网格的平滑近似估计网格。
[0041] 本发明提出了一种自适应的三角形多分辨率网格顶点位置预测方法和装置，能够高效地解决三角形多分辨率网格顶点位置的预测问题。
[0042] 尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同限定。
