引用本文
刘洪豪, 刘贤喜, 张开兴, 卢山, Lee Heow Pueh, 宋正河. 基于光传播Monte Carlo模拟的三维模型特征提取方法[J]. 光谱学与光谱分析, 2020, 40(2): 385-390.
LIU Hong-hao, LIU Xian-xi, ZHANG Kai-xing, LU Shan, Lee Heow Pueh, SONG Zheng-he. 3D Model Feature Extraction Based on Light Propagation Simulation with Monte Carlo Method[J]. Spectroscopy and Spectral Analysis, 2020, 40(2): 385-390.  
Permissions
Copyright©2020, 光谱学与光谱分析
光谱学与光谱分析 所有
基于光传播Monte Carlo模拟的三维模型特征提取方法
刘洪豪1, 刘贤喜1, 张开兴1,2,*, 卢山1, Lee Heow Pueh3, 宋正河4
1. 山东农业大学机械与电子工程学院, 山东 泰安 271018
2. 山东省农业装备智能化工程实验室, 山东 泰安 271018
3. Department of Mechanical Engineering, National University of Singapore, Singapore 117575, Singapore
4. 中国农业大学工学院, 北京 100083
*通讯联系人 e-mail: kaixingzhang@139.com

作者简介: 刘洪豪, 1992年生, 山东农业大学机械与电子工程学院博士研究生 e-mail: mobeikehan@126.com

收稿日期:2019-01-15 接受日期:2019-05-22 网络出版日期:2020-02-12
基金项目:国家重点研发计划项目(2017YFD0700102)资助
摘要

在现代工业设计、 人工智能、 软件设计等领域, 三维模型正展现强劲需求与活力, 传统三维模型特征提取方法仅能提取模型表面特征, 难以满足复杂模型特征提取需求, 为提高三维模型的特征提取精度, 基于光谱分析以及可见光传播特性, 提出一种具有高区分度的三维模型特征提取方法。 首先利用光散射系数、 吸收系数、 各向异性等光学特性参数, 量化分析光在不同介质中透射、 散射、 反射概率, 并确定最佳光谱模拟波段; 其次采用Monte-Carlo法模拟光子束在三维模型中的传播历程, 获得光子束传播轨迹的角度、 距离、 能量等多种统计量, 计算不同统计量权重, 经过统计分析后完成特征提取; 然后在ESB国际通用三维模型库中, 测试不同光子束数量、 约束空间形状对特征提取效果影响, 从而确定最佳模拟参数; 最后使用多种特征提取方法与光传播模拟法进行特征提取效果比较, 并采用查准率、 查全率以及E测度评价指标对特征提取效果进行定量测试。 实验结果表明, 三维模型特征提取准确度对光传播约束空间形态较为敏感, 光子传播的最佳约束空间为球体; 三维特征提取效率随着光子束数量升高而降低, 在保证特征提取精度的前提下, 10 000~25 000区间是光子束模拟数量的最佳取值范围; 基于光传播模拟的特征提取准确度高于小波变换、 距离夹角以及D2分布方法, 能够满足三维模型检索需求, 更适合复杂三维模型的离线特征提取与应用。 结合光谱分析与可见光传播特性的模型特征提取法拓宽了光谱分析的应用范围, 能够提取出融合三维模型表面特性与内部形态的有效特征, 为高精度特征提取技术研究注入新动力。

关键词: 光传播模拟; 特征提取; 蒙特卡罗法; 三维模型
中图分类号:O439 文献标志码:A
3D Model Feature Extraction Based on Light Propagation Simulation with Monte Carlo Method
LIU Hong-hao1, LIU Xian-xi1, ZHANG Kai-xing1,2,*, LU Shan1, Lee Heow Pueh3, SONG Zheng-he4
1. College of Mechanical and Electronic Engineering, Shandong Agricultural University, Tai’an 271018, China
2. Shandong Provincial Engineering Laboratory of Agricultural Equipment Intelligence, Tai’an 271018, China
3. Department of Mechanical Engineering, National University of Singapore, Singapore 117575, Singapore
4. College of Engineering, China Agricultural University, Beijing 100083, China
*Corresponding author
Abstract

Three-dimensional model has been showing extensive demand and vitality in modern industrial design, artificial intelligence and software design fields. Traditional feature extraction methods merely depend on model surface feature, which could not sufficiently satisfy complex model feature extraction needs. In order to improve the accuracy of model feature extraction, a 3D model feature extraction method with high discrimination was proposed based on spectral analysis and light propagation attributes. Firstly, the probability of light transmission, scattering and reflection when light propagation in different medium was quantitatively analyzed with scattering coefficient, absorption coefficient and anisotropy parameters. Secondly, the Monte-Carlo method was used to simulate light propagation in complex 3D model, where different feature statistics including angle, distance and energy were obtained to complete feature extraction. Then, the influence factors of photon beam number and constrained space shape were tested for optimal parameters determination. Finally, the feature extraction effectiveness was evaluated on retrieval precision, recall and E-measure. The results showed that the feature extraction accuracy sensitively varied with constrained space shape and the optimal constrained space for photon propagation was sphere; The feature extraction efficiency decreased with more photon beams, and within basic accuracy requirement, 10 000 to 25 000 photon beams were the optimal simulation number; The feature extraction accuracy of proposed method was higher than the wavelet transform, distance-angle and D2 distribution methods, which is more suitable for offline feature extraction of complex 3D models. The proposed simulation method of feature extraction broadens spectral analysis application, which could extract the integrated feature between model surface and internal structure, promoting model feature extraction research.

Keyword: Light propagation simulation; Feature extraction; Monte-Carlo method; 3D model
引言

三维模型特征提取是三维模型分类筛选的关键环节[1], 高精度特征提取方法可为三维重构、 3D打印以及虚拟现实技术提供技术参考。 特征提取的核心是利用不同维度方法分析并挖掘模型的形状或拓扑结构, 建立与模型唯一对应且具有高区分度的代表特征。 传统的三维特征提取方法主要有数学统计法[2]、 模型投影法[3]和拓扑分析法[4], 三种方法均不同程度提高了特征提取准确度, 但该三种方法的特征分析只停留在模型表面, 无法综合反映模型内部结构属性。

如何深入模型内部, 并提取能够反映三维模型表面属性和内部结构的综合特征信息已成为特征提取技术的研究焦点, 相关研究表明光具有较强的穿透特性, 光在不同介质中传播时, 不同光谱波段的光会与介质发生不同作用, 产生包括散射、 反射、 透射、 吸收等在内的多种物理现象[5], 而这些现象反映了物体材料属性及物理形状。 因此, 在一定空间内模拟光与三维模型相互作用, 统计并分析能量吸收、 透射反射次数以及光传播路径等多种信息因子, 进而可获得一种代表性强、 区分度高的三维模型特征。

鉴于可见光独特的传播特性以及三维模型复杂多样性, 本文使用蒙特卡罗法[6]模拟光在三维模型中传播全过程, 将光谱分析理论与可见光传播特性分析拓展到三维模型特征提取技术中, 提出一种新的三维模型特征提取方法。

1 原理与方法

光在介质中传播时会发生多种物理现象, 图1显示了光在三维模型中产生各种光学现象的原理示意图, 不同波段可见光在不同形态的介质中产生光散射、 反射以及透射的概率具有随机性, 蒙特卡罗法能够较好解决随机性问题[7, 8]。 使用蒙特卡罗法模拟光在三维模型中的传播并实现特征提取主要包括: 设置光子束的初始化状态, 根据光的波长特征和传播介质的光学属性确定光子移动步长, 分析并确定光散射、 界面反射概率, 实现光子传播全过程跟踪模拟, 统计分析光子信息, 从而完成三维模型特征提取。

图1 光传播过程示意图Fig.1 The illustration of light propagation

1.1 模拟初始化

初始化即确定模拟的起始状态, 包括模型初始化与光子初始化两部分, 对于三维模型的初始化, 首先对三维模型进行尺度归一化、 旋转归一化处理[9], 从而保证三维模型相对大小一致, 然后确定三维模型重心, 并以重心为原点建立三维空间坐标系, 将三维模型包围在标准约束空间中, 并使用方位角α 以及偏转角β 表示模型的轮廓, 图2给出了坐标系中方位角、 偏转角示意图。

图2 三维空间坐标系示意图Fig.2 The illustration of three-dimensional coordinate

以光子束为最小模拟单位, 模拟光在约束空间中的传播历程, 光子初始化时光子束的入射位置(x, y, z)均匀分布在约束空间表面, 入射方向指向坐标原点, 并使用位置坐标点与(x, y, z)坐标轴的余弦值(Ux, Uy, Uz)表示入射方向。 此外, 为了实现光子束的能量信息统计, 初始化后的光子束均被设置w0能量。

1.2 计算移动步长

定义光子在传播方向未改变时的直线传播距离为移动步长, 移动步长受到包括各向异性、 折射率、 吸收系数、 反射率、 散射系数在内多种因素影响, 但主要由介质的散射系数、 吸收系数决定[10], 式(1)表示了光子平均移动步长与散射系数、 吸收系数反比例关系, 式中Δ s表示平均步长, σ s和σ a分别代表光散射系数、 吸收系数。

Δs≪1σs+σa(1)

移动步长的大小具有随机性, 其概率密度函数遵守Beer定律[9], 见式(2)

p(s)=(σa+σs)e-(σa+σs)s(2)

s=-lnεσa+σs(3)

结合概率密度以及式(1)反比例关系, 计算得出移动步长, 见式(3), 式中随机变量ε ∈ [0, 1]。 此外, 光子移动单个步长的同时伴随着光子的能量转移, 体现光子束的能量损失, 单次移动后的光子束能量为

w'=σsσa+σsw(4)

式中, w'表示移动后的光子束能量, w为移动前光子束能量。

1.3 确定散射方向

光子束在传播过程中因光散射而改变传播方向, 三维模型的形状越复杂, 结构变异连接处的光学性质差异越大, 光散射效果越明显, 因此在模拟过程中增加光散射过程有助于提高三维模型特征提取精度。 相函数是一种描述入射光单次散射偏转角度的概率分布函数, 其中Henyey-Greenstein相函数(H-G函数)计算方便[11], 在蒙特卡罗法模拟中最为常用, H-G相函数表达式为

cosβ=12g1+g2-1-g21-g+2gεg≠02ε-1g=0(5)

式中, β 为偏转角; g∈ [-1, 1]表示各向异性系数; 随机数ε ∈ [0, 1]。

各项向性系数g=-1时, 入射光全部背向散射; 反之g=1时, 入射光完全前向散射。 散射偏转角确定后, 在散射方位角取值范围内取随机数, 完成散射方向的改变。

1.4 模拟终止化

光子束出射后在被包围的约束空间中传播, 与模型表面、 空间约束界面碰撞, 产生折射、 反射等现象, 但光子束不可能无限传播, 为保证模拟随机性与模拟效率, 定义2种光子束终止化方式: (1)光子束能量低于临界阈值w″时终止; (2)光子束在约束空间表面和模型表面透射时终止。

光子束传播到三维模型和约束空间表面时, 可能发生透射或内反射现象, 取随机数值ε ∈ [0, 1]与Fresnel反射系数[12]R(ai)比较, 判断是否发生内反射, 若ε > R(ai), 光子束透射界面, 反之光子束发生内反射。

αi=cos-1(|uz|)nisinαi=ntsinαtR(αi)=12sin2(αi-αt)sin2(αi+αt)+tan2(αi-αt)tan2(αi+αt)(6)

式中, ni表示传播介质折射率; nt表示出射介质折射率。

1.5 分析并提取特征

光子束从初始化到终止化为止, 光子束全部传播信息均可被跟踪记录, 光子束特有的传播信息体现三维模型不同形态与内部结构。 单个光子束传播信息构成随机事件, 根据概率统计理论对大量随机事件统计分析, 即可完成有效信息的提取, 表1显示了三维模型特征提取过程中光子束传播信息统计量。

表1 光子束传播信息统计量 Table 1 The statistics of light propagation information

将不同统计特征组成特征矩阵, 对特征矩阵、 角度分布、 距离分布、 能量分布特征进行加权平均, 完成三维模型特征提取。

2 实验部分

选用美国普渡大学开发的ESB国际通用模型库作为三维模型实验数据集, ESB数据集[13]包括薄壁、 棱柱、 回转体3大类共计867个模型, 具有种类齐全、 覆盖范围广、 易于使用的特点, 部分三维模型如图3所示。

图3 ESB三维模型节选Fig.3 The part of ESB model database

实验中三维模型的光学特性参数为: 各向异性系数g=0.12, 光学参数σ s=12 mm-1, σ a=0.03 mm-1, 在Matlab2016中按照图4所示的流程对光子束传播过程进行模拟。

为实现三维模型特征提取效果的定性和定量评价, 实验以查准率、 查全率、 模型检索效率[14]等作为三维模型特征提取的评价标准。

图4 实验模拟流程图Fig.4 Light propagation simulation process

3 结果与讨论
3.1 光子数量分析

光子数量是决定特征提取效果的关键影响因素, 模拟光子数量不足导致提取特征信息量少, 无法反应模型基本特征, 数量过多则特征提取时间长, 特征提取效率低。 图5显示了光子束数量对特征提取准确度、 提取效率的影响, 其中横坐标表示不同梯度光子束数量, 纵坐标以查准率表征提取效果, 以所需时间表征提取效率。

图5 模拟数量分析图Fig.5 The curve of simulation numbers analysis

由图5可知, 特征提取时间随着光子束数量提高而增加, 同等变化幅度内呈现线性变化趋势, 表明光子模拟算法无记忆性; 查准率曲线先升高, 在光子束数量为5万左右时达到顶峰后呈现下降趋势, 这是因为随着光子束数量增加, 光子在模型内部传播密度增大, 表征模型特征点的统计量更加充分, 从而导致查准率升高, 但随着光子束数量逐步增加, 各统计量数据逐渐饱和且趋于正态分布, 模型特征的区分度减小, 查准率降低。 综合特征提取效果和提取效率两方面, 确定光子束数量范围为10 000~25 000之间, 此时, 特征提取时间需要30 s左右, 表明光子特征提取方法更适合离线三维模型检索与应用。

3.2 约束空间分析

约束空间是影响特征提取的重要因素, 一方面约束空间决定了光子束的发射位置, 另一方面约束空间内表面形状影响光子反射角度。 图6显示了不同形状约束空间下部分光子三维传播轨迹, 图6(a)为ESB模型库中三维模型, 图6(b, c, d)分别为圆球体、 正方体、 椭球体中光子传播轨迹, 其中红色代表被约束空间表面内反射的光子, 绿色表示被吸收的光子, 蓝色为透射出三维模型表面的光子。

图6 不同约束空间中光子分布示意图
(a): 原模型; (b): 圆球体约束空间; (c): 正方体约束空间; (d): 椭球体形约束空间Fig.6 Photon distribution in different constrained space
(a): Original model; (b): Sphere space; (c): Cube space; (d): Spheroid space

由图6光子分布图可知, 在不同约束空间中, 光子传播轨迹有较大差异, 为量化约束空间对特征提取的影响效果, 选取结构差异较大的10种三维模型在不同约束空间中进行特征提取, 由表2统计结果可知, 在特征提取效果方面, 圆球体和正方体优于椭球体特征提取; 在稳定性方面, 圆球体性能最优。 此外, 使用圆球体约束空间, 三维模型旋转变化后与约束空间保持相对位置不变, 因此在初始化阶段三维模型不需要旋转归一化处理, 算法复杂度降低, 综合特征提取效果与流程两方面, 确定圆球体为最佳模拟约束空间。

表2 不同约束空间特征提取效果 Table 2 The results of feature extraction
3.3 算法比较

为验证光子模拟方法的特征提取效果, 使用不同特征提取方法进行对比实验, 3种比较算法分别为使用频率较高的D2分布算法、 距离-夹角算法以及频率域小波变换方法[15]。 使用球体约束空间并将光子模拟次数设置为1.2万次, 在ESB模型库中选取10种不同类别三维模型, 每种三维模型进行5次特征提取, 以5次模型检索的查准率-查全率平均值作为最终统计数据, 比较结果如图7所示。

图7 查全率查准率曲线Fig.7 The recall-precision curve

由图7可知, 整体上本文特征提取效果与小波变换算法近似, 检索准确度高于D2分布与距离夹角算法, 这是因为基于形态的D2算法与距离-夹角算法只以模型表面信息点作为特征提取源, 小波变换和光子传播模拟方法能够深入模型内部, 体现表面与内部融合的双重特征; 为进一步比较本文算法与小波变换算法的精度, 图8显示了以内部形状复杂多腔体三维模型作为检索对象的对比效果, 此时小波算法检索准确度明显低于光子模拟算法, 这是由于在使用小波变换进行特征提取前三维模型必须要进过旋转归一化处理, 复杂三维模型在旋转归一化处理时会发生空间坐标系不重合现象, 而小波变换对模型位置信息变化较为敏感, 从而一定程度上降低了特征提取区分度。 以上两方面对比分析表明, 光子传播模拟算法的特征提取准确度较高, 能够满足三维模型特征提取与检索要求, 尤其适用于内部复杂三维模型特征提取。

图8 复杂三维模型E测度分析结果Fig.8 The E-measure results for complex model

4 结 论

(1)蒙特卡罗法可实现光在不同介质中散射、 折射、 反射等现象的模拟, 将该方法应用到三维模型特征提取方面, 能够提取出融合模型表面特性与内部形态的有效特征, 是一种新的三维模型特征提取方法。

(2)采用蒙特卡罗光子模拟法并在ESB模型库中进行三维特征提取时, 最佳约束空间为球体, 10 000~25 000之间是光子束模拟数量的最佳取值范围。

(3)在球体约束空间且光子束数量为1.2万次的条件下, 光子模拟法的特征提取准确度高于小波变换、 距离夹角以及D2分布算法, 但特征提取效率有待提高, 该方法更适合复杂三维模型的离线特征提取与应用。

参考文献
[1] Biasotti S, Cerri A, Aono M, et al. Visual Computer, 2016, 32(2): 217. [本文引用:1]
[2] Li P J, Ma H D, Ming A L. Multimedia Tools and Applications, 2017, 76(7): 10207. [本文引用:1]
[3] Ji M M, Feng Y F, Xiao J, et al. Neurocomputing, 2015, 169: 23. [本文引用:1]
[4] Hong Y, Kim J. Ksii Transactions on Internet and Information Systems, 2017, 11(8): 3950. [本文引用:1]
[5] Wang Q, Yu Y M, Wang T M, et al. Optik, 2016, 127(22): 10539. [本文引用:1]
[6] YANG Xue, LI Gang, LIU Yan, et al(杨雪, 李刚, 刘妍, 等). Spectroscopy and Spectral Analysis(光谱学与光谱分析), 2016, 36(11): 3476. [本文引用:1]
[7] Watte R, Aernouts B, Van Beers R, et al. Optics Express, 2015, 23(13): 17467. [本文引用:1]
[8] Funamizu H, Maeda T, Sasaki S, et al. Opt. Rev. , 2014, 21(3): 359. [本文引用:1]
[9] Lin S F, Wu C C, Hsu C Y, et al. International Journal of Pattern Recognition and Artificial Intelligence, 2011, 25(4): 583. [本文引用:2]
[10] Modric D, Maretic K P, Hladnik A. Appl. Optics, 2014, 53(33): 7854. [本文引用:1]
[11] Hajdek K, Miljkovic P, Modric D. Teh. Vjesn. , 2014, 21(4): 779. [本文引用:1]
[12] Periyasamy V, Pramanik M. J. Biomed. Opt. , 2014, 19(4): 045003. [本文引用:1]
[13] Liu Y J, Zheng Y F, Lv L, et al. Visual Computer, 2012, 28(1): 75. [本文引用:1]
[14] Lian Z H, Godil A, Bustos B, et al. Pattern Recognition, 2013, 46(1): 449. [本文引用:1]
[15] LIU Hong-hao, ZHAO Xiu-yan, ZHANG Kai-xing, et al(刘洪豪, 赵秀艳, 张开兴, 等). Transactions of the Chinese Society for Agricultural Machinery(农业机械学报), 2018, 49(S1): 338. [本文引用:1]