基于最优最小生成树的三维模型形状优化方法
|
摘要
针对海量、异构、复杂的三维模型高效形状分析需求,提出基于最优最小生成树的三维模型形状优化方法。首先基于三维模型最小生成树(3D-MST)构造模型的结构描述;其次通过拓扑结构与几何形状检测并结合双边滤波与熵权值分布进行局部优化,获得模型的优化MST表示;最终基于优化的Laplacian谱特征,结合薄板样条函数(TPS),实现模型的形状分析与相似性检测。实验结果表明,所提方法不仅有效地保留了模型的形状特征,而且可高效地实现复杂模型的稀疏优化表示,能进一步提高几何处理与形状检索的高效性和增强鲁棒性。
For the efficient shape analysis of massive, heterogeneous and complex 3 D models, an optimization method for 3 D model shape based on optimal minimum spanning tree was proposed. Firstly, a model description based on 3 D model Minimum Spanning Tree(3 D-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.
For the efficient shape analysis of massive, heterogeneous and complex 3 D models, an optimization method for 3 D model shape based on optimal minimum spanning tree was proposed. Firstly, a model description based on 3 D model Minimum Spanning Tree(3 D-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.
引文
[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-rigid3D 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 3Dshape 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 ComputerAided 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 ComputerAided 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 YY,YU S,et al.A fast k NN-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.
[2]PICKUP D,SUN X,ROSIN P L,et al.Shape retrieval of non-rigid3D 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 3Dshape 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 ComputerAided 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 ComputerAided 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 YY,YU S,et al.A fast k NN-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.