基于最优最小生成树的三维模型形状优化方法

doi:10.11772/j.issn.1001-9081.2018081710

计算机应用 ›› 2019, Vol. 39 ›› Issue (3): 858-863.DOI: 10.11772/j.issn.1001-9081.2018081710

• 虚拟现实与多媒体计算 • 上一篇下一篇

基于最优最小生成树的三维模型形状优化方法

韩丽, 刘书宁, 于冰, 徐圣斯, 唐棣

辽宁师范大学计算机与信息技术学院, 辽宁大连 116081

收稿日期:2018-08-17 修回日期:2018-10-26 出版日期:2019-03-10 发布日期:2019-03-11
通讯作者: 刘书宁
作者简介:韩丽(1973-),女,辽宁大连人,教授,博士,主要研究方向:计算机图形学、计算机视觉;刘书宁(1992-),男,河北衡水人,硕士研究生,主要研究方向:计算机图形学;于冰(1988-),男,辽宁沈阳人,硕士研究生,主要研究方向:计算机图形学;徐圣斯(1993-),男,辽宁大连人,硕士研究生,主要研究方向:计算机图形学;唐棣(1960-),女,内蒙古通辽人,教授,主要研究方向:计算机图形学。
基金资助:
国家自然科学基金资助项目（61702246）；辽宁省社会科学基金资助项目（2018lslktyb-084）。

3D model shape optimization method based on optimal minimum spanning tree

HAN Li, LIU Shuning, YU Bing, XU Shengsi, TANG Di

School of Computer and Information Technology, Liaoning Normal University, Dalian Liaoning 116081, China

Received:2018-08-17 Revised:2018-10-26 Online:2019-03-10 Published:2019-03-11
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61702246), the Social Science Foundation of Liaoning Province (2018lslktyb-084).

摘要/Abstract

摘要：

针对海量、异构、复杂的三维模型高效形状分析需求，提出基于最优最小生成树的三维模型形状优化方法。首先基于三维模型最小生成树（3D-MST）构造模型的结构描述；其次通过拓扑结构与几何形状检测并结合双边滤波与熵权值分布进行局部优化，获得模型的优化MST表示；最终基于优化的Laplacian谱特征，结合薄板样条函数（TPS），实现模型的形状分析与相似性检测。实验结果表明，所提方法不仅有效地保留了模型的形状特征，而且可高效地实现复杂模型的稀疏优化表示，能进一步提高几何处理与形状检索的高效性和增强鲁棒性。

关键词: 最小生成树, 体积, 双边滤波, 熵权值, 谱嵌入

Abstract:

For the efficient shape analysis of massive, heterogeneous and complex 3D models, an optimization method for 3D model shape based on optimal minimum spanning tree was proposed. Firstly, a model description based on 3D model Minimum Spanning Tree (3D-MST) was constructed. Secondly, local optimization was realized by topology and geometry detection and combination of bilateral filtering and entropy weight distribution, obtaining optimized MST representation of the model. Finally, the shape analysis and similarity detection of the model were realized by optimized Laplacian spectral characteristics and Thin Plate Spline (TPS). The experimental results show that the proposed method not only effectively preserves shape features of the model, but also effectively realizes sparse optimization representation of the complex model, improving the efficiency and robustness of geometric processing and shape retrieval.

Key words: Minimum Spanning Tree (MST), volume, bilateral filtering, entropy weight, spectral embedding

中图分类号:

TP391.41

韩丽, 刘书宁, 于冰, 徐圣斯, 唐棣. 基于最优最小生成树的三维模型形状优化方法[J]. 计算机应用, 2019, 39(3): 858-863.

HAN Li, LIU Shuning, YU Bing, XU Shengsi, TANG Di. 3D model shape optimization method based on optimal minimum spanning tree[J]. Journal of Computer Applications, 2019, 39(3): 858-863.

参考文献

[1] OSADA R, FUNKHOUSER T, CHAZELLE B, et al. Shape distributions[J]. ACM Transactions on Graphics, 2002, 21(4):807-832.
[2] PICKUP D, SUN X, ROSIN P L, et al. Shape retrieval of non-rigid 3D human models[C]//Proceedings of the 7th Eurographics Workshop on 3D Object Retrieval. Aire-la-Ville, Switzerland:Eurographics Association, 2014:101-110.
[3] 李海生,孙莉,吴晓群,等.基于模型内二面角分布直方图的非刚性三维模型检索[J].计算机辅助设计与图形学学报,2017,29(6):1128-1134.(LI H S, SUN L, WU X Q, et al. Non-rigid 3D shape retrieval based on inner dihedral angle histogram[J]. Journal of Computer-Aided Design and Computer Graphics, 2017, 29(6):1128-1134.)
[4] HILAGA M, SHINAGAWA Y, KOHMURA T, et al. Topology matching for fully automatic similarity estimation of 3D shapes[C]//Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. New York:ACM, 2001:203-212.
[5] DU H, QIN H. Medial axis extraction and shape manipulation of solid objects using parabolic PDEs[C]//Proceedings of the 9th ACM Symposium on Solid Modeling and Applications. Aire-la-Ville, Switzerland:Eurographics Association, 2004:25-35.
[6] 王飞,张树生,白晓亮,等.拓扑和形状特征相结合的三维模型检索[J].计算机辅助设计与图形学学报, 2008, 20(1):99-103.(WANG F, ZHANG S S, BAI X L, et al. 3D model retrieval based on both the topology and shape features[J]. Journal of Computer-Aided Design and Computer Graphics, 2008, 20(1):99-103.)
[7] LI F, DAI Q, XU W, et al. Statistical modeling and many-to-many matching for view-based 3D object retrieval[J]. Signal Processing Image Communication, 2010, 25(1):18-27.
[8] GAO Y, DAI Q, WANG M, et al. 3D model retrieval using weighted bipartite graph matching[J]. Signal Processing:Image Communication, 2011, 26(1):39-47.
[9] LIPMAN Y, CHEN X, DAUBECHIES I, et al. Symmetry factored embedding and distance[J]. ACM Transactions on Graphics, 2010, 29(4):Article No. 103.
[10] SAHILLIOGLU Y, YEMEZ Y. Minimum-distortion isometric shape correspondence using EM algorithm[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(11):2203-2215.
[11] SUN J, OVSJANIKOV M, GUIBAS L. A concise and provably informative multi-scale signature based on heat diffusion[J]. Computer Graphics Forum, 2009, 28(5):1383-1392.
[12] AUBRY M, SCHLICKEWEI U, CREMERS D. The wave kernel signature:a quantum mechanical approach to shape analysis[C]//Proceedings of the 2011 IEEE International Conference on Computer Vision Workshops. Washington, DC:IEEE Computer Society, 2011:1626-1633.
[13] 姜巍,徐凯,程志全,等.一种通用的局部内蕴对称检测算法[J].计算机辅助设计与图形学学报,2013,25(7):974-979.(JIANG W, XU K, CHENG Z Q. et al. A generalized algorithm for partial intrinsic symmetry detection[J]. Journal of Computer-Aided Design and Computer Graphics, 2013, 25(7):974-979.)
[14] 匡振中,李宗民,田伟伟,等.热模态特征与非刚体模型检索[J].计算机辅助设计与图形学学报,2015,27(8):1426-1433.(KUANG Z Z, LI Z M, TIAN W W, et al. Modal feat feature and non-rigid 3D model retrieval[J]. Journal of Computer-Aided Design and Computer Graphics, 2015, 27(8):1426-1433.)
[15] LAU L C, NAOR J S, SALAVATIPOUR M R, et al. Survivable network design with degree or order constraints[J]. SIAM Journal on Computing, 2017, 39(3):1062-1087.
[16] 朱利,邱媛媛,于帅,等.一种基于快速k-近邻的最小生成树离群检测方法[J].计算机学报,2017,40(12):2856-2870.(ZHU L, QIU Y Y, YU S, et al. A fast kNN-based MST outlier detection method[J]. Chinese Journal of Computers, 2017, 40(12):2856-2870.)
[17] GAL R, COHEN-OR D. Salient geometric features for partial shape matching and similarity[J]. ACM Transactions on Graphics, 2006, 25(1):130-150.
[18] 韩丽, 胡江月. 体积分布的三维模型形状分析方法[J]. 计算机工程与应用, 2015, 51(23):195-198.(HAN L, HU J Y. Shape analysis method of 3D models based on volumetric distribution[J]. Computer Engineering and Applications, 2015, 51(23):195-198.)
[19] SHAPIRA L, SHAMIR A, COHEN-OR D. Consistent mesh partitioning and skeletonisation using the shape diameter function[J]. Visual Computer, 2008, 24(4):249-459.
[20] SHAPIRA L, SHALOM S, SHAMIR A, et al. Contextual part analogies in 3D objects[J]. International Journal of Computer Vision, 2010, 89(2/3):309-326.
[21] SHILANE P, MIN P, KAZHDAN M, et al. The Princeton shape benchmark[C]//Proceedings of the 2004 Shape Modeling Applications. Washington, DC:IEEE Computer Society, 2004:167-178.
[22] YANG Q. A non-local cost aggregation method for stereo matching[C]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Washington, DC:IEEE Computer Society, 2012:1402-1409.
[23] AFSAL S, RAFEEQ A K, JOTHYKUMAR J, et al. A novel approach for palm print recognition using entropy information features[EB/OL].[2018-07-12]. https://ieeexplore.ieee.org/document/7566374/.
[24] 王年,周梅菊,张江,等.基于最小生成树的LAPLACE谱图像匹配算法[J].系统仿真学报,2009,21(17):5481-5485.(WANG N, ZHOU M J, ZHANG J, et al. Laplacian spectrum image matching algorithm based on minimum spanning tree[J]. Journal of System Simulation, 2009,21(17):5481-5485.)
[25] 韩丽,颜震,徐建国,等.基于显著特征谱嵌入的三维模型相似性分析[J].模式识别与人工智能,2015,28(12):1119-1126.(HAN L, YAN Z, XU J G, et al. Three-dimensional model similarity analysis based on salient features spectral embedding[J]. Pattern Recognition and Artificial Intelligence, 2015, 28(12):1119-1126.)
[26] CHUI H, RANGARAJAN A. A new point matching algorithm for non-rigid registration[J]. Computer Vision and Image Understanding, 2003, 89(2):114-141.
[27] MYRONENKO A, SONG X. Point set registration:coherent point drift[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(12):2262-2275.

基于最优最小生成树的三维模型形状优化方法

3D model shape optimization method based on optimal minimum spanning tree

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	佘玉龙, 张晓龙, 程若勤, 邓春华. 基于边缘关注模型的语义分割方法[J]. 计算机应用, 2021, 41(2): 343-349.
[2]	张钊, 吉建民, 陈小平. 用于知识表示学习的对抗式负样本生成[J]. 计算机应用, 2019, 39(9): 2489-2493.
[3]	汤慧, 周明全, 耿国华. 基于区域分割的低覆盖点云配准算法[J]. 计算机应用, 2019, 39(11): 3355-3360.
[4]	王辉, 王悦, 刘畅祖, 庄珊娜, 曹俊杰. 自适应尺度的双边纹理滤波方法[J]. 计算机应用, 2018, 38(5): 1415-1419.
[5]	田华, 刘俣男, 顾家莹, 陈俏. 基于特征矩阵相似性度量的形状对应性分析[J]. 计算机应用, 2017, 37(6): 1763-1767.
[6]	郭浩, 刘磊, 陈俊杰. 基于高阶最小生成树的脑网络分析及对阿兹海默氏症患者的分类[J]. 计算机应用, 2017, 37(11): 3339-3344.
[7]	张鹏程, 张权, 张芳, 陈燕, 韩建宁, 郝慧艳, 桂志国. 结合改进扩散和双边滤波的低剂量CT重建[J]. 计算机应用, 2016, 36(4): 1100-1105.
[8]	袁华, 庞建铿, 莫建文. 基于噪声分类的双边滤波点云去噪算法[J]. 计算机应用, 2015, 35(8): 2305-2310.
[9]	杜明本, 陈立潮, 潘理虎. 基于暗原色理论和自适应双边滤波的煤矿尘雾图像增强算法[J]. 计算机应用, 2015, 35(5): 1435-1438.
[10]	王伟东, 刘兵, 管红杰, 周勇, 夏士雄. 基于核函数的谱嵌入聚类算法[J]. 计算机应用, 2015, 35(3): 761-765.
[11]	王妍, 章婷婷, 宋知润, 王俊陆, 郭敬玉. 基于区域分簇的大规模无线传感器网络生命周期优化策略[J]. 计算机应用, 2015, 35(11): 3031-3037.
[12]	相艳, 贺建峰, 易三莉, 刑正伟. 基于交叉累计剩余熵的多谱磁共振图像配准[J]. 计算机应用, 2015, 35(1): 231-234.
[13]	刘洪滨杜玲姬红利. 面向网关版权保护的抗几何攻击视频水印方法[J]. 计算机应用, 2013, 33(12): 3531-3535.
[14]	张官亮邹焕新卢春燕赵键. 基于拟Laplacian谱和点对拓扑特征的点模式匹配算法[J]. 计算机应用, 2013, 33(06): 1686-1690.
[15]	白雪任晓玲刘希玉. 基于粘贴和2-臂DNA模型的层次聚类算法[J]. 计算机应用, 2013, 33(02): 308-315.