方向感知的网格模型特征识别

郭艺辉　黄承慧　钟雪灵　陆寄远

摘 要：针对网格模型平滑区域提取特征困难，以及现有特征识别方法无法检测仅沿某一特定方向分布的特征点的问题，提出一种方向感知的网格模型特征識别方法。首先，分别从x、y、z三个方向探测网格顶点邻接面法向量沿不同方向变化的情况。设定合适的阈值，只要检测到在任何一个方向上顶点邻接面法向量的变化超过阈值，该顶点即被识别为特征点。然后，针对现有网格模型特征识别算法无法检测三维医学模型普遍存在的一种仅沿z轴方向分布的梯田型结构的问题，单独探测医学模型网格顶点邻接面法向量沿z轴方向变化的情况，将变化超出阈值的顶点识别为梯田型结构顶点，正确地将非正常梯田型结构从人体模型正常结构特征中分离出来。与二面角法的对比实验的结果显示：在相同阈值设置下，所提方法能更好地识别出网格模型特征，解决了二面角法在没有明显折线的平滑区域上无法有效识别特征点的问题;同时，也解决了现有网格模型特征检测算法因不具备方向探测能力而无法将医学模型非正常梯田型结构与正常人体结构区分开来的问题，为医学模型后续数字几何处理工作提供了条件。

关键词：网格特征识别;平滑特征区域;方向属性;医学三维重建;梯田型结构

中图分类号： TP391.72文献标志码：A

Direction-perception feature recognition on mesh model

GUO Yihui*， HUANG Chenghui， ZHONG Xueling， LU Jiyuan

（School of Internet Finance and Information Engineering， Guangdong University of Finance， Guangzhou Guangdong 510020， China）

Abstract： In order to solve the problems of the difficulty to extract features on the smooth regions of mesh models and the impossibility to recognize the feature vertices distributed only along one specific direction by the existing feature detection methods， a direction-perception method of feature recognition on mesh models was proposed. Firstly， the changes of the normal vectors of the mesh vertex adjacent surfaces were detected in x， y and z directions separately. With a suitable threshold set， if the change of a normal vector of the mesh vertex adjacent surfaces exceeded the threshold in any direction， the vertex would be recognized as a feature vertex. Then， concerning the problem that the existing mesh model feature detection algorithms cannot recognize the terraced field structure only distributed along the z-axis of three-dimensional medical model， the algorithm detected the change of normal vectors of the mesh vertex adjacent surfaces just along the z-axis direction， and recognized the vertex as a terraced field structure vertex once the change of the vertex exceeds the threshold. The abnormal terraced field structures were separated from the normal structures of the human body successfully. The experimental results show that， compared with the dihedral angle method， the proposed method can identify the features of the mesh model better under the same conditions. The proposed method solves the problem that the dihedral angle method cannot effectively identify the feature vertices on the smooth regions without obvious broken lines， and also solves the problem that the existing mesh model feature detection algorithms cannot distinguish the abnormal terraced field structures from the normal human body structures due to the lack of the direction detection ability， and establishes a base for the following digital geometry processing of the medical model.

Key words： mesh feature recognition; smooth feature region; directionality property; three-dimensional medical reconstruction; terraced field structure

0 引言

三维网格模型特征识别是网格简化、网格分割、网格光顺以及模型重建等诸多数字几何处理工作的关键步骤。众多网格模型特征识别方法被提出。Guskov等[1]提出二面角法。Lee等[2]提出以感知为基础的（Perception inspired）视觉显著度模型“Mesh saliency”。Kim等[3]将网格显著性测度模型与人类视觉注意模型作对比分析，将对模型显著域的处理转化为曲率域的处理以实现基于视觉显著性的模型显著区域形状调控。Sipiran等[4]提出3D-Harris方法，将用于二维图像特征点检测的Harris算子扩展到三维空间，用于提取三维模型特征点。Laga等[5]提出有同样显著特征的模型属于同一语义类，而属于同一语义类的模型有着相似的最佳视点，将模型最佳视点选择的问题转变为模型特征选择和分类的问题。Dutagaci等[6]提出一个基于人手工标定标准语义特征点数据集的公开测试平台，用于评价各种三维模型语义特征点检测算法的有效性。Song等[7]首先在谱图域计算网格显著性，接着将显著信息传递回网格空间域，提取出三维模型语义特征点。Wu等[8]提出符合人类视觉感知的基于局部反差与全局稀疏理论的网格模型显著性检测算法。朱帆等[9]提出一种基于局部平均形心距离差的顶点显著性度量方法。王海玲等[10]提出融合几何特征信息和视觉特征信息的多特征融合度量方法。Gupta等[11]提出了一种计算机辅助设计（Computer Aided Design， CAD）模型零件变形特征分类、表示和提取方法。孙挺等[12]提出了基于局部特征概率密度估计的三维模型特征提取体系框架。Levallois等[13]提出了一种基于积分不变量的鲁棒的离散特征估计方法，可以对边缘、光滑区域和平坦区域的特征进行准确分类。Liu等[14]提出了一种从噪声三角网格中提取特征曲线的鲁棒算法。Kong等[15]提出了一种基于拓扑变换的自由曲面特征识别方法。Muraleedharan等 [16]提出了一种CAD网格模型孔、槽、穴特征识别方法。Torrente等[17]将霍夫变换 （Hough Transform， HT）技术扩展到三维图形领域，识别和定位网格模型语义特征。Soltanpour等[18]对三维人脸局部特征提取方法进行了综述。Song等[19]提出了一种从局部到全局的网格显著特征计算方法，有效地检测出符合人类感知的显著特征。Chen等[20]提出了通过线性组合部件突出程度、部件相对大小以及部件边缘强度的网格特征测量方法。刘斌 [21]针对三角网格曲面上复杂特征阵列式设计重用困难问题，提出一种两步法特征阵列重用策略，该方法可用于复杂特征的阵列式实时交互设计。杨贤康等[22]提出了基于L0优化的网格曲面特征线提取算法。胡俊等[23]提出一种流形网格曲面上自由形状特征可参数驱动的阵列重用设计方法。

然而，对于网格模型平滑区域特征检测，上述众多特征识别算法要么虽然能准确识别，但是算法实施过程较为复杂;要么虽然计算简单直观，但是当模型表面没有锐利的折线存在时，对网格平滑区域的特征检测会失效，例如二面角法[1]即是如此。本文提出了一个既简单直观又能很好地识别网格平滑区域特征的方法。对于每一个顶点，分别从三维空间的三个方向探测其邻接面法向量方向变化的情况，只要有任何一个方向的变化超过阈值，即便是该顶点位于网格平滑特征区域，也会被准确地识别出来。

同时，由于本文方法的方向特性，该方法还能解决现有特征检测方法无法有效识别医学模型梯田型结构的问题。通过一组二维計算机断层扫描（Computed Tomography， CT）数据重建的三维医学模型目前已广泛地应用于解剖三维重建、立体仿真手术与导航、放射治疗规划、计算机辅助诊断以及个性化假肢再造等领域。然而由于机器设备扫描分辨率以及环境噪声的影响，重建的三维医学模型普遍含有一种特殊的梯田型结构，如图1所示。

这种梯田型结构不仅会使组织器官呈现出非正常外观，同时还会干扰医生对疾病的诊断，对后续的临床治疗也会产生极其不利的影响。然而，尽管已有上述众多三维模型特征识别方法被提出，这些算法均无法有效标识医学模型梯田型结构，其原因是：医学模型梯田型结构仅沿z轴方向分布，而目前还没有一种特征检测方法能有效区分方向，将仅沿一个方向分布的特征点标识出来。

本文提出的方向感知的特征检测方法可以准确识别出模型中仅沿z轴方向分布的梯田型结构，将梯田型结构与人体骨骼模型固有特征结构区分开来，为后续有效进行数字几何处理有针对性去除这些非正常人体结构提供了可能。

1 方向感知的网格模型特征识别方法

首先，构建笛卡尔坐标系，如图2所示。

接着，定义网格模型特征检测函数，计算式如下：

δx，i=max（θx，nfk）-min（θx，nfk）（1）

其中：k为网格顶点i一邻域邻接三角形，nfk为一邻域邻接三角形面法向量;计算顶点i一邻域邻接三角形面法向量nfk与x轴之间的角度差，记为θx，nfk;找出网格顶点i一邻域三角形沿x轴方向的最大偏离max（θx，nfk）以及最小偏离min（θx，nfk）;计算沿x轴方向的最大偏离max（θx，nfk）以及最小偏离min（θx，nfk）之间的差，记为δx，i。同理，在y轴以及z轴方向也执行上述相同的操作，得到δy，i 与 δz，i，计算式如下：

δy，i=max（θy，nfk）-min（θy，nfk）（2）

δz，i=max（θz，nfk）-min（θz，nfk）（3）

设置一个合理的阈值τ，若顶点i的δx，i> τ或者 δy，i> τ或者 δz，i>τ，则顶点i为网格模型的特征顶点，如图3（a）所示;若顶点i的δx，i>τ，则顶点i为网格模型的x轴方向特征顶点，如图3（b）所示;若顶点i的δy，i>τ，则顶点i为网格模型的y轴方向特征顶点，如图3（c）所示;若顶点i的δz，i>τ，则顶点i为网格模型的z轴方向特征顶点。由于三维医学模型的梯田型结构仅沿z轴方向分布，因此，若三维医学模型网格顶点i的δz，i>τ，则顶点i为梯田型结构顶点，如图3（d）所示。

2 实验与结果分析

本文实验环境的配置为Intel Pentium i5 2.60GHz、RAM 2GB的PC，操作系统是Windows 10，使用Visual C++ 2010编程实现。

2.1 网格模型平滑特征识别结果

实验中，采用Princeton大学公开测试平台[24]提供的Fish模型、Teddy模型、Chair模型、Casting模型、Girl模型以及Torso模型（图4）进行网格模型特征识别，同时与二面角方法进行对比，以验证本文方法的有效性。算法运算时间以及参数设置如表1所示。

对于Fish网格模型、Teddy模型以及Chair模型，图4（a）为原始网格模型。分别采用二面角法以及本文方法识别模型特征，两种方法阈值设置均完全相同，分别为29°、18.5°以及25°。图4（b）为采用二面角法识别的模型特征点，观察到：Fish网格模型鱼背部位、鱼鳍与身体连接处光滑弯曲部位因没有明显的折线，这些部位特征点没有被二面角法有效识别到;Teddy模型耳朵与头部连接处、左臂与身体连接处光滑弯曲部位的特征点没有被二面角法有效识别到;Chair模型椅腿与椅面光滑连接的弯曲部位特征点没有被二面角法识别到，同时椅脚远端也有漏检的特征点。图4（c）为采用本文方法识别出的模型特征，观察到：对于Fish、Teddy模型，尽管平滑特征区域没有尖锐的折线，但是本文方法依然准确识别出这些部位特征点;对于Chair模型尽管椅腿与椅面光滑连接部位没有明显的折线，但是在相同阈值设置下，本文方法准确识别出该部位所有特征点，同时相较于二面角法，本文方法在椅脚远端也识别到更多特征点。

对于有更多细节表现的Casting模型、Girl模型以及Torso模型（图4），本文方法依然有良好的特征检测能力。对于每一个模型，在二面角法以及本文方法均采用相同阈值的情况下（分别为22°、28°以及24.5°），观察到：对于Casting模型，本文方法识别出了更多模型光滑弯曲部位的特征点;对于Girl模型以及Torso模型，相较于二面角法，本文方法识别出了更多眼睛、嘴唇、鼻以及Girl发饰等部位的特征点。

使用本文方法进行模型特征检测运算时间以及参数设置如表1所示。实验结果表明，由于本文方法可以从三维空间三个方向分别探测模型顶点邻接面法向量沿x轴、y轴以及z轴方向偏离的情况，并且规定：三个方向中只要有任何一个方向偏离值大于阈值（执行逻辑或的运算），该顶点就被标识为特征点。因此，使用本文方法能准确捕捉到顶点邻接面弯曲的状况，相较于二面角法，在表1中所示相同阈值设置下，本文方法能更加灵敏地识别出网格模型特征点，即使该特征点位于没有明显折线的平滑特征区域也能被准确检测出来。

2.2 特定方向感知特征识别结果

本文提出的方向感知特征检测方法可以利用自身能够区分顶点方向属性的特性，准确标识出三维医学模型仅沿z轴方向分布的梯田型结构。本实验所用到的三维医学模型是由二维医学CT切片数据通过移动立方体（Marching Cubes， MC）算法三维重建而成。

分别采用二面角法以及本文方法识别股骨髁模型（如图5所示）、股骨头模型（如图6所示）以及胫骨模型（如图7所示）的梯田型结构。两种方法阈值设置相同，对于股骨髁模型均為47°，股骨头模型均为70°，胫骨模型均为32°。对于每一个模型，图（a）均为原始医学网格模型及局部放大图;对于每一个模型，图（b）为采用二面角法识别的模型梯田型结构及局部放大图;对于每一个模型，图（c）为采用本文方向感知的特征提取方法提取的梯田型结构及局部放大图。

由图5～7中图（b）可以看出：图5（b）中二面角法提取的结果既包含非正常梯田型结构，又包含股骨髁的髁间窝以及外侧髁突出部位的正常人体特征。图6（b）中二面角法提取的结果既包含非正常梯田型结构，又包含正常人体胫骨边缘突起的胫骨粗线结构特征。图7（b）中二面角法提取的结果既包含非正常梯田型结构，又包含正常的人体股骨粗隆结构特征。由此可知，二面角法因无法探知特征点的方向属性，因而无法将梯田型结构与正常人体特征结构区分开来。

由图5～7中图（c）可以看出：图5（c）中本文方法准确提取到梯田型结构，提取的结果没有包含人体正常股骨髁的髁间窝凹陷特征以及外侧髁突出部位的特征。图6（c）中本文方法准确提取到非正常梯田型结构，而没有包含正常人体胫骨边缘突起的胫骨粗线特征。同样，图7（c）中本文方法也是准确提取到非正常梯田型结构，而没有包含正常人体股骨粗隆特征。本文方法有效地将非正常梯田型结构从正常人体模型结构特征中分离出来，在后续的数字几何处理过程中，就可以有针对性地将这些非正常的梯田型结构去除，得到最大限度逼近于正常人体特征的医学网格模型，最终更好地适用于数字医学诊疗的需求。

本文方法进行医学模型梯田型结构检测运算时间以及参数设置如表2所示。

实验结果表明，由于本文方法可以独立探测医学模型网格顶点邻接面法向量仅沿z轴方向的变化情况，因此，相较于二面角法，在表2中相同阈值设置下，本文方法能忽略掉骨骼模型人体正常特征，而仅将梯田型结构准确识别出来。本文方法解决了二面角法等模型特征检测方法因不能识别仅沿某一特定方向分布的特征点，而无法将医学模型非正常梯田型结构与正常人体结构区分开来的问题。

[11]GUPTA R K， GURUMOORTHY B. Classification， representation， and automatic extraction of deformation features in sheet metal parts [J]. Computer-Aided Design， 2013， 45（11）： 1469-1484.

[12]孙挺，张锦华，耿国华.基于局部特征概率密度估计的三维模型特征提取方法[J].计算机科学，2015，42（6）：293-295，312.（SUN T， ZHANG J H， GENG G H. New architecture for extraction of 3D model features based on probabilistic density estimation of local surface features [J]. Computer Science， 2015， 42（6）： 293-295， 312.）

[13]LEVALLOIS J， COEURJOLLY D， LACHAUD J. Scale-space feature extraction on digital surfaces [J]. Computers and Graphics， 2015， 51： 177-189.

[14]LIU H， DAI N， ZHONG B， et al. Extract feature curves on noisy triangular meshes [J]. Graphical Models， 2017， 93： 1-13.

[15]KONG T， ZHANG Y， FU X B. The model of feature extraction for free-form surface based on topological transformation [J]. Applied Mathematical Modelling， 2018， 64： 386-397.

[16]MURALEEDHARAN L P， KANNAN S S， KARVE A， et al. Random cutting plane approach for identifying volumetric features in a CAD mesh model [J]. Computers and Graphics， 2018， 70： 51-61.

[17]TORRENTE M， BIASOTTI S， FALCIDIENO B. Recognition of feature curves on 3D shapes using an algebraic approach to Hough transforms [J]. Pattern Recognition， 2018， 73： 111-130.

[18]SOLTANPOUR S， BOUFAMA B， WU Q M J. A survey of local feature methods for 3D face recognition [J]. Pattern Recognition， 2017， 72： 391-406.

[19]SONG R， LIU Y， MARTIN R R. Local-to-global mesh saliency [J]. The Visual Computer， 2018， 34（3）： 323-336.

[20]CHEN H， LI M. A novel mesh saliency approximation for polygonal mesh segmentation [J]. Multimedia Tools and Applications， 2018， 77（13）： 17223-17246.

[21]刘斌.三角网格曲面上的特征阵列[J].机械工程学报，2019，55（3）：120-129.（LIU B. Pattern design of freeform features on triangular meshes [J]. Journal of Mechanical Engineering， 2019， 55（3）： 120-129.）

[22]杨贤康，潘茂东，童伟华，等.基于L0优化的网格曲面特征线提取算法[J].计算机工程，2019，45（7）：251-257，263.（YANF X K， PAN M D， TONG W H， et al. Feature lines extraction on meshes using L0 minimization [J]. Computer Engineering， 2019， 45（7）： 251-257， 263.）

[23]胡俊，劉斌，黄常标，等.网格曲面上自由形状特征交互式阵列设计[J].计算机集成制造系统，2019，25（1）：61-70.（HU J， LIU B， HUANG C B， et al. Interactive pattern design of freeform features on mesh surface [J]. Computer Integrated Manufacturing Systems， 2019， 25（1）： 61-70.）

[24]CHEN X， GOLOVINSKIY A， FUNKHOUSER T. A benchmark for 3D mesh segmentation [J]. ACM Transactions on Graphics， 2009， 28（3）： Article No. 73.

[25]严严，陈日伟，王菡子，等.基于深度学习的人脸分析研究进展[J].厦门大学学报（自然科学版），2017，56（1）：13-24.（YAN Y， CHEN R W， WANG H Z， et al. Recent advances on deep-learning-based face analysis [J]. Journal of Xianmen University （Natural Science）， 2017， 56（1）： 13-24.）

[26]刘栋，李素，曹志冬.深度学习及其在图像物体分类与检测中的应用综述[J].计算机科学，2016，43（12）：13-23.（LIU D， LI S， CAO Z D. State-of-the-art on deep learning and its application in image object classification and detection [J]. Computer Science， 2016， 43（12）： 13-23.）

[27]李鑫，陈雷霆，蔡洪斌.基于结构感知深度神经网络的显著性对象检测算法[J].计算机应用研究，2019，36（7）：2195-2199.（LI X， CHEN L T， CAI H B. Salient object detection algorithm based on structure-sensitive deep neural network [J]. Application Research of Computers， 2019， 36（7）： 2195-2199.）

[28]杨军，王顺，周鹏.基于深度体素卷积神经网络的三维模型识别分类[J].光学学报，2019，39（4）：314-324.（YANG J， WANG S， ZHOU P. Recognition and classification for three-dimensional model based on deep voxel convolution neural network [J]. Acta Optica Sinica， 2019， 39（4）： 314-324.）

[29]CHARLES R Q， SU H， MO K. PointNet： deep learning on point sets for 3D classification and segmentation [C]// Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2017： 77-85.

[30]LUCIANO L， HAMZA A B. Deep learning with geodesic moments for 3D shape classification [J]. Pattern Recognition Letters， 2018， 105： 182-190.

[31]FEY M， LENSSEN J E， WEICHERT F， et al. SplineCNN： fast geometric deep learning with continuous B-spline kernels [C]// Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2018： 869-877.

This work is partially supported by the National Natural Science Foundation of China （71501051）， the National Natural Science Foundation of China International （Regional） Cooperation and Exchange Project  （61320106008）， the Natural Science Foundation of Guangdong Province （2017A050501042）， the Key Project of the Humanities and Social Sciences Research in Universities of Guangdong Province （2018WZDXM032）.

GUO Yihui， born in 1976， Ph. D.， lecturer. Her research interests include computer graphics， digital geometry processing.

HUANG Chenghui， born in 1976， Ph. D.， associate professor. His research interests include machine learning.

ZHONG Xueling， born in 1980， Ph. D.， professor. His research interests include financial technology， big data.

LU Jiyuan， born in 1976， Ph. D.， professor. His research interests include multimedia data processing.

收稿日期：2019-05-13;修回日期：2019-07-19;錄用日期：2019-07-22。

基金项目：国家自然科学基金资助项目（71501051）;国家自然科学基金国际（地区）合作与交流项目（61320106008）;广东省自然科学基金资助项目（2017A050501042）;广东省普通高校人文社会科学研究重点项目（2018WZDXM032）。

作者简介：郭艺辉（1976—），女，山东济南人，讲师，博士，主要研究方向：计算机图形学、数字几何处理; 黄承慧（1976—），男，湖南郴州人，副教授，博士，主要研究方向：机器学习; 钟雪灵（1980—），男，广东河源人，教授，博士，主要研究方向：金融科技、大数据;陆寄远（1976—），男，广东南海人，教授，博士，主要研究方向：多媒体数据处理。

文章编号：1001-9081（2019）12-3673-05DOI：10.11772/j.issn.1001-9081.2019050799