基于最大化可视信息的三维场景最佳视角自动获取方法

摘要

本发明提出了一种基于最大化可视信息的三维场景最佳视角自动获取方法。利用三维场景各顶点的曲率表征该场景的表面几何特征，并利用自适应的聚类方法求出该三维场景的特征区域。对于每个采样视点，评估其可视特征总量以及其对各特征区域的视觉显示效果，最终基于聚类算法和统计方法找出该观察该三维场景的最佳视角。该方法充分利用给定三维场景表面的几何特征信息，在获得最大可视信息量的同时兼顾每个特征区域的可视化质量，求出的最佳视角，充分满足人们观察三维场景的视觉需求。

说明书

技术领域

本发明涉及一种计算机三维模型处理方法，具体涉及一种基于最 大化可视信息的三维场景最佳视角自动获取方法。

背景技术

近年来，随着计算机技术和网络技术的飞速发展，越来越多的三 维场景模型用于环境导航、虚拟现实、数字城市等领域中。

给定一个三维模型，从不同的角度对其进行观察时，由于不同视 角承载了该三维模型的不同方向的视觉信息，可能会展现出完全不同 的表现形式。寻找最佳视角的本质是找出一个承载最大信息量的视 点，该视点有利于人们更加深入地去观察和了解给定的三维模型。近 年来，最佳视角问题得到了学术界的广泛研究，并应用到很多实际问 题中，如形状识别和分类、三维模型视图编辑、基于图像的渲染、三 维模型搜索等。

对于什么样的视角是最佳视角这一问题，现在还没有一个权威的 定义。在研究最佳视角问题时，人们通常根据自己所面对的实际应用 去进行定义。通过研究计算机图形心理学，Blanz等人提出了决定最 佳视角的四个属性：利于识别、熟悉度、能用函数表示以及审美标准， 并且最佳视角在很大程度上受三维模型的几何特性影响(Blanz，V，et al.，What object attributes determine canonical views？PERCEPTION -LONDON-，1999.28：p.575-600.)。结合这些研究成果，最佳视角常 被定义为能为人们提供该模型最多可视化信息的视角。其中，可视化 信息可以进一步表现为曲率、拓扑或者轮廓熵等描述符，且最佳视角 就是尽可能多地使这些描述符在给定视角范围内可见。

传统的求解三维模型最佳视角的方法主要有：基于传统的审美标 准如黄金分割等(G.D.Birkhoff，Mathematics of aesthetics，The world  of mathematics(1956)，pp.2185--2195.)、定义一个信息描述符，然后 定义最大化该信息描述符的视点为最佳视点(Page，D.L.and Koschan， A.F.and Sukumar，S.R.and Roui-Abidi，B.and Abidi，M.A，Shape  analysis algorithm based on information theory，in Proc.of Proceedings  of International Conference on Image Processing(2003)，pp.229--232. 等)、基于语义的最佳视角获取方法(Denton，T.and Demirci，M.F.and  Abrahamson，J.and Shokoufandeh，A.and Dickinson，S，Selecting  Canonical Views for View-Based 3-D Object Recognition，in Proc.of  International Conference on Pattern Recognition(2004)，pp.273--276. 等)。

然而，三维模型通常只包含单一的物体，而三维场景通常包含有 大量的物体，而且呈现出不同的形状和材质，这就使得传统的针对三 维模型的最佳视角的方法并不能很好地移植到三维场景的最佳视角 中来。对于三维场景，其最佳视角应该满足以下两个条件：能够尽可 能多地看到场景中的物体；尽量使可见的物体视觉效果达到最佳。

发明内容

本发明的目的在于提供一种基于最大化可视信息的三维场景最 佳视角自动获取方法。

为达到上述目的，本发明采用的技术方案是：

1)对给定的三维场景，确定其向上的方向即正方向，并就确定 的正方向对该三维场景进行归一化；

2)根据归一化后的三维场景，在单位球的上半球面对视点进行 均匀采样；

3)求出三维场景表面各顶点的曲率，用以表征三维场景表面的 几何特征；

4)基于三维场景表面顶点曲率聚类的方法求取三维场景表面的 特征区域，并采用各特征区域聚类中心的曲率值作为该区域的特征 值，用以表征该区域的重要程度；

5)基于主成分分析(PCA)方法对求出的三维场景各特征区域内部 位置关系进行分析，求出各特征区域的主方向，用以衡量步骤2)各 采样视点对该特征区域的可视化质量；

6)以看到最多的特征区域和获得最优的可视化质量为核心，提 出基于特征区域特征值和特征区域可视化质量的能量函数，并基于统 计的方法求取优化能量函数的最佳视角。

其具体的执行步骤如下：

步骤一：对于给定的三维场景S，确定其向上的方向，并就确定 的正方向对该三维场景进行归一化，得到归一化后的三维场景M；

步骤二：对归一化后的三维场景M，在单位球的上半球面上进行 均匀采样，得到采样视点集V；

步骤三：对归一化后的三维场景M的每个顶点求平均曲率，得到 场景M的曲率图M_c；

步骤四：对曲率图M_c中每个顶点p_i∈M_c，定义一个7维特征向 量e(p_i)去描述其几何特征：

[式一]

$e\left(p_i\right)=(x_i,y_i,z_i,n_i^x,n_i^y,n_i^z,{\kappa }_i)$

其中，(x_i，y_i，z_i)表示顶点p_i的坐标，表示顶点p_i的法向量， k_i表示顶点p_i处的曲率值；

用均值漂移的聚类算法对特征向量e(p_i)做聚类，将曲率图M_c划 分为一系列特征区域M_c＝{C₁，C₂，...，C_N}，对特征区域集合M_c中的每个 特征区域C_i用其聚类中心c_i表示该区域的几何特征；

步骤五：对每个特征区域C_i，用主成分分析法(PCA)求出该区域 内部所有顶点p_j∈C_i的坐标{x_j，y_j，z_j}的三个特征向量{t_j，s_j，r_j}；

步骤六：对于步骤二中得到的采样视点v_i∈V，利用步骤四中求 得的特征区域M_c＝{C₁，C₂，...，C_N}和对应的聚类中心{c₁，c₂，...，c_N}∈C，求出 可视化特征信息能量函数VN(v_i)：

[式二]

$\mathrm{VN}\left(v_i\right)=\left|\right|\underset{c_j\in C}{\Sigma }({\kappa }_j·{\delta }_j)\left|\right|/N$

其中，k_j表示聚类中心c_j的曲率值，N为总的特征区域个数，指 标函数δ_j定义如下：

[式三]

步骤七：对于步骤二中得到的采样视点v_i∈V，利用步骤五对每 个特征区域C_i求得的特征向量{t_j，s_j，r_j}，求出三维场景M的可视化质 量能量函数VF(v_i)：

[式四]

$\mathrm{VF}\left(v_i\right)=\underset{c_j\in C}{\Sigma }\left|\right|t_j·(v_i-c_j)\left|\right|/\left(\right|\left|t_j\right||·||v_i-c_j|\left|\right)$

其中，{c₁，c₂，...，c_N}∈C为各个特征区域的聚类中心；

步骤八：利用步骤六和步骤七的结果，得到每个采样视点v_i∈V的 能量函数f_i：

[式五]

f_i＝(VN(v_i)-ω·VF(v_i)

其中VN(v_i)和VF(v_i)分别是步骤六和步骤七中求得的可视化特征 信息能量函数和可视化质量能量函数，ω为可视化质量能量函数的权 值；

步骤九：结合各采样视点v_i∈V的坐标和其对应的能量函数，定 义一个4维特征向量用以描述该视点的可视信息：

[式六]

其中，(x_i，y_i，z_i)是采样视点v_i的坐标，f_i为步骤八求得的采样视点 v_i对应能量函数；

用均值漂移的聚类算法对特征向量做聚类，得到一系列聚类 中心VC＝{VC₁，VC₂，...，VC_K}；

步骤十：遍历步骤九求得的聚类中心VC＝{VC₁，VC₂，...，VC_K}，比较 它们的能量函数项，定义最佳视角为：

[式七]

其中，f_i表示聚类中心VC_i∈VC的能量函数项；

步骤十一：根据步骤十求得的最佳视角利用其坐标信息对三 维场景做平行投影，得到最佳视角的投影图。

本发明首先，给定一个三维场景模型，需要确定其向上的方向(Fu， Hongbo and Cohen-Or，Daniel and Dror，Gideon and Sheffer，Alla， Upright orientation of man-made objects，ACM Transactions on Graphics (2008)，pp.42：1--42：7.)。根据确定的正方向，对输入场景进行归一化。 然后，在单位球上半球对视点进行均匀采样(Polonsky，O.and Patané， G and Biasotti，S.and Gotsman，C.and Spagnuolo，M，What′s in an  Image？The Visual Computer(2005)，PP.840--847.)。

本发明判定最佳视点的核心规则是得到最大的可视信息。在实际 研究中，研究人员通常会人为规定三维模型的可视化信息描述符，如 曲率、拓扑或者轮廓熵等，用以表征模型表面的几何特性。本发明采 取的三维模型特征描述符为模型各顶点的平均曲率值。有别于三维模 型的单一物体、单一材料的简单结构，三维场景通常含有超过一个物 体和一种材质。因此，三维场景的复杂度远大于单纯的三维模型，而 常规的基于最大化三维模型的可视信息方法应用在三维场景上时容 易陷入局部最优困境，已不能很好满足三维场景最佳视角问题。因此， 本发明中应用到均值漂移聚类方法(Comaniciu，D.and Meer，P，Mean  shift：A robust approach toward feature space analysis，IEEE Transactions  on Pattern Analysis and Machine Intelligence(2002)，pp.603--619.)。通过 聚类，可以将整个三维场景划分为一系列的特征区域。基于特征区域 的最大化可视信息方法求解得到的最佳视角，可以充分考虑到整个三 维场景中每个人们感兴趣的部位，权衡整个三维场景各区域对视觉信 息的贡献，而不用将重点局限于某个特别突出的部位，从而顺利跳出 局部最优的困境。

同时，本发明不光考虑了最多的视觉信息，还在获取最大可视信 息的基础上，最优化每个特征区域的视觉质量。对于划分出的每个特 征区域，利用主成分分析方法(PCA)对区域内所有顶点进行分析， 并得到它的三个主方向。对于每个特征区域，我们以与其主方向垂直 的方向为最佳视线方向。因此，只需计算视线与主方向的内积，便可 评估出某视点对该特征区域的视觉效果好坏。

综合考虑最大可视信息和最佳视觉效果两个因素，合理安排二者 的权值，构建出评价各采样视点优劣的能量函数。然后，再次利用均 值漂移聚类算法对各采样视点进行聚类，得到一系列视点的聚类中 心。最后，利用统计的方法对各视点聚类中心的能量函数进行排序， 选取所得能量函数最大的聚类中心作为最佳视点所在位置，并利用平 行投影获取最佳视角的投影图。

附图说明

图1是本发明基于最大化可视信息的三维场景最佳视角自动获 取方法的流程图；

图2是本发明示意图；

图3展示不同视角体现三维场景不同的信息，同时给出传统的针 对三维模型的最佳视角求解方法在三维场景问题上的缺陷；

图4展示各个特征区域的聚类中心和各个特征区域主成分分析 (PCA)求得的三个主方向；

图5展示采样视点的聚类中心和最佳视角的选取，同时分析最佳 视角随采样视点数目的增多的收敛趋势；

图6展示本发明方法求得的部分三维场景最佳视角投影图(第1 列)，同时给出在该视角下该三维模型的特征区域聚类中心(第2列) 和两种传统的针对三维模型的最佳视角方法的对比结果(第3、4列)。

具体实施方式

下面将根据附图对本发明进行详细说明。

图1是本发明的流程图。本发明主要分为十一个步骤：

参见图1、2：

步骤一：对于给定的三维场景S，确定其向上的方向，规定为正 方向。并就确定的正方向对该三维场景进行归一化，得到归一化后的 三维场景M；

步骤二：对归一化后的三维场景M，在包围M的单位球的上半 球上进行均匀采样，得到采样视点集V。对于不同的采样视点，由于 其承载了三维场景M的不同方向的几何特征信息，其视觉效果可能会 呈现出截然不同的表现形式(图3)。

步骤三：对于一个给定的三维模型，其表面的几何特征信息主要 体现为表面各顶点之间的曲率特征。因此，对归一化后的三维场景M， 求出每个顶点的平均曲率，得到场景M的曲率图M_c；

步骤四：得到场景M的曲率图M_c后，需要对曲率图中每个顶点 给出一个量化的数学描述子。对于曲率图中每个顶点p_i∈M_c，定义一 个7维向量e(p_i)去描述其几何特征：

[式一]

$e\left(p_i\right)=(x_i,y_i,z_i,n_i^x,n_i^y,n_i^z,{\kappa }_i)$

其中，(x_i，y_i，z_i)表示顶点p_i的坐标，表示顶点p_i的法向量， k_i表示顶点p_i处的曲率值。向量e(p_i)同时包含了当前顶点的几何位置 信息和表面特征信息。

传统的针对三维模型的最佳视角算法如(Vázquez，P.P.and Feixas， M.and Sbert，M.and Llobet，A，Viewpoint entropy：a new tool for  obtaining good views of molecules，in Proc.of Proceedings of the  Symposium on Data Visualisation 2002(2002)，pp.183--188.)等容易陷 入局部最优困境(如图3)，因此不适于解决三维场景最佳问题。本 发明用均值漂移聚类算法对特征向量e(p_i)做聚类，聚类结果将曲率图 M_c划分为一系列特征区域M_c＝{C₁，C₂，...，C_N}。对每个特征区域C_i，用 其聚类中心c_i表示该区域的几何特征，点c_i的向量表达式为：

[式二]

$\beta \left(c_i\right)=(x_i,y_i,z_i,n_i^x,n_i^y,n_i^z,{\kappa }_i)$

其中，(x_i，y_i，z_i)表示算出的聚类中心c_i的坐标，表示算出 的聚类中心c_i的法向量，k_i表示算出的聚类中心c_i处的曲率值。

步骤五：对每个特征区域C_i，用主成分分析法(PCA)对该区域内 部所有顶点p_j∈C_i的坐标{x_j，y_j，z_j}进行分析，并求出它的三个特征向 量{t_j，s_j，r_j}(图4)。其中，对该区域顶点分布起决定性作用的是向量t_j(假定它的三个特征值排列为λ₁≥λ₂≥λ₃)。

步骤六：对于步骤二中得到的采样视点v_i∈V，利用步骤四中求 得的特征区域M_c＝{C₁，C₂，...，C_N}和对应的聚类中心{c₁，c₂，...，c_N}∈C，利用 式二中定义的点c_i的向量表达式e(c_i)，求出可视化特征信息能量函数 VN(v_i)：

[式三]

$\mathrm{VN}\left(v_i\right)=\left|\right|\underset{c_j\in C}{\Sigma }({\kappa }_j·{\delta }_j)\left|\right|/N$

其中，k_j表示聚类中心c_j的曲率值，N为总的特征区域个数，指 标函数δ_j定义如下：

[式四]

其中，当前视点v_i能否看到聚类中心c_j由判定式D(v_i，c_j)决定：

[式五]

其中，判定式D(v_i，c_j)定义为：

[式六]

D(v_i，c_j)＝(p(v_i)-p(c_j)).(n(c_j))

式中，p(.)表示点的坐标，n(.)表示该点的法向量。

步骤七：对于步骤二中得到的采样视点v_i∈V，利用步骤五对每 个特征区域C_i求得的特征向量{t_j，s_j，r_j}，求出三维场景M的可视化质 量能量函数VF(v_i)：

[式七]

$\mathrm{VF}\left(v_i\right)=\underset{c_j\in C}{\Sigma }\left|\right|t_j·(v_i-c_j)\left|\right|/\left(\right|\left|t_j\right||·||v_i-c_j|\left|\right)$

其中，{c₁，c₂，...，c_N}∈C为各个特征区域的聚类中心。由步骤五可知， 由于t_j为对该区域顶点分布起决定性作用的向量，在计算采样视点对 该区域的视觉质量时，只需满足视线与向量t_j垂直便可得到很好的效 果(参见图5)。

步骤八：利用步骤六和步骤七的结果，得到每个采样视点v_i∈V的 能量函数f_i：

[式八]

f_i＝(VN(v_i)-ω·VF(v_i)

其中VN(v_i)和VF(v_i)分别是步骤六和步骤七中求得的可视化特征 信息能量函数和可视化质量能量函数，ω为可视化质量能量函数的权 值。能量函数f_i越大，便代表该视点越符合人们的视觉需求。

步骤九：结合各采样视点v_i∈V的坐标和其对应的能量函数，定 义一个4维向量用以描述该视点的可视信息：

[式九]

其中，(x_i，y_i，z_i)是采样视点v_i的坐标，f_i为步骤八求得的采样视点 v_i对应能量函数。

参照步骤四，用均值漂移聚类算法对特征向量做聚类，得到 一系列聚类中心VC＝{VC₁，VC₂，...，VC_K}。对于每个聚类中心VC_i，可以定 义一个4维向量α(VC_i)：

[式十]

α(VC_i)＝(x_i，y_i，z_i，f_i)

式中，(x_i，y_i，z_i)为采样视点聚类中心的坐标，f_i为求得的采样视 点聚类中心的能量函数值。

步骤十：遍历步骤九求得的聚类中心VC＝{VC₁，VC₂，...，VC_K}，利用 描述每个聚类中心视觉特性的向量α(VC_i)，比较它们的能量函数项f_i， 定义最佳视角为：

[式十一]

其中，f_i表示聚类中心特征向量α(VC_i)的能量函数项。

步骤十一：根据步骤十求得的最佳视角利用其坐标信息对三 维场景做平行投影，得到最佳视角的投影图。(图6)

如上所述，本发明提出了一种基于最大化可视信息的三维场景最 佳视角自动获取方法。利用三维场景各顶点的曲率用以表征该场景的 表面几何特征，并利用聚类方法求出该三维场景的特征区域。对于每 个采样视点，评估其可视特征总量以及其对各特征区域的视觉效果， 最终基于聚类算法和统计方法找出该三维场景的最佳视角。该方法充 分利用给定三维场景表面的几何特征信息，在获得最大可视信息量的 同时兼顾每个特征区域的可视化质量，求出的最佳视角充分迎合人们 的视觉需求。

尽管已经参考附图对本发明进行了解释和描述，专业技术人员应 该理解，在不脱离本发明精神和范围的情况下，可以在其中或对其进 行各种其他改变，增删。