|Table of Contents|

Rapidly calculating approximate geodesic distance based on metric multidimensional scaling

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

Issue:
2016年02期
Page:
190-
Research Field:
Publishing date:

Info

Title:
Rapidly calculating approximate geodesic distance based on metric multidimensional scaling
Author(s):
Chen HonghuaPang Mingyong
Department of Educational Technology,Nanjing Normal University,Nanjing 210097,China
Keywords:
digital geometry processing triangular meshes high-dimensional embedding geodesic distances metric multidimensional scaling
PACS:
TP391
DOI:
10.14177/j.cnki.32-1397n.2016.40.02.010
Abstract:
A novel algorithm is proposed for rapidly calculating approximate geodesic distance between any vertex pair on a triangular mesh based on the metric multidimensional scaling(MMDS)technique.The geodesic calculating on the surface of a given mesh in the low-dimensional space is transformed into the Euclidean distance computing in a high-dimensional Euclidean space.The given mesh is decimated to its simplified version,then all geodesic distances are calculated on the original mesh only for the vertex pairs of the simplified mesh,and subsequently the simplified mesh is embeded into a high-dimensional space according to the computed distances by employing the MMDS.Regarding the vertices of the simplified mesh as control points,the remaining vertices of the original mesh is embeded into the high-dimensional space by using the least square method.Finally the Euclidean distances are calculated in the high-dimensional Euclidean space to express the approximate geodesic distances between any two points in the originat mesh.Experiments show that the method is robust and can deal with different models with various complexities of topology and geometry,and it has ability to quickly calculate the approximate geodesic distance between any two points with a pre-defined precision on 3D mesh models.

References:

[1] Liang L,Szymczak A,Wei M.Geodesic spin contour for partial near-isometric matching[J].Computers & Graphics,2015,46:156-171.
[2]Taimouri V,Hua J.Deformation similarity measurement in quasi-conformal shape space[J].Graphical Models,2014,76(2):57-69.
[3]Tung T,Matsuyama T.Geodesic mapping for dynamic surface alignment[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2014,36(5):901-913.
[4]Lian Z,Godil A,Sun X,et al.CM-BOF:visual similarity-based 3D shape retrieval using clock matching and bag-of-features[J].Machine Vision & Applications,2013,24(8):1685-1704.
[5]周艳,刘圣军,金小刚,等.基于测地距离的多边形网格模型约束变形[J].软件学报,2007,18(6):1543-1552.
Zhou Yan,Liu Shengjun,Jin Xiaogang,et al.Geodesic-based constrained deformations for polygonal mesh models[J].Journal of Software,2007,18(6):1543-1552.
[6]Liu Y J,Chen Z,Tang K.Construction of iso-contours,bisectors and Voronoi diagrams on triangulated surfaces[J].IEEE Transactions on Software Engineering,2010,33(8):1502-1517.
[7]Chen J,Han Y.Shortest path on the polyhedron,Part I[J].International Journal of Computational Geometry & Application,1996,6(2):360-369.
[8]Kaneva B,O'Rourke J,Kaneva B.An implementation of Chen & Han's shortest paths algorithm[C]//Proceedings of 21st Canadian Conference on Computational Geometry.Fredericton,Canada:University of New Brunswick,2000:139-146.
[9]Ying X,Xin S Q,He Y.Parallel Chen-Han(PCH)algorithm for discrete geodesics[J].ACM Transactions on Graphics,2013,33(1):57-76.
[10]Mitchell J S,Mount D M,Papadimitriou C H.The discrete geodesic problem[J].SIAM Journal on Computing,1987,16(4):647-668.
[11]Surazhsky V,Surazhsky T.Fast exact and approximate geodesics on meshes[J].ACM Transactions on Graphics,2005,24(3):553-560.
[12]Liu Y J,Zhou Q Y,Hu S M.Handling degenerate cases in exact geodesic computation on triangle meshes[J].Visual Computer,2007,23(9-11):661-668.
[13]Liu Y J.Exact geodesic metric in 2-manifold triangle meshes using edge-based data structures[J].Computer-Aided Design,2013,45(3):695-704.
[14]Xu C X,Wang T,Liu Y J,et al.Fast wavefront propagation for computing exact discrete geodesics on meshes[J].IEEE Transactions on Visualization & Computer Graphics,2015,21(7):822-834.
[15]Kanai T,Suzuki H.Approximate shortest path on a polyhedral surface and its applications[J].Computer-Aided Design,2001,33(11):801-811.
[16]Ying X,Wang X,He Y.Saddle vertex graph:a novel solution to the discrete geodesic problem[J].ACM Transactions on Graphics,2013,32(6):2504-2507.
[17]Kimmel R,Sethian J A.Computing geodesic paths on manifolds[J].Proceedings of the National Academy of Sciences of the United States of Amercia,1998:8431-8435.
[18]Novotni M,Klein R.Computing geodesic distances on triangular meshes[C]//Proceedings of WSCG.Plzen,Czech:University of West Bohernia,2002:341-347.
[19]Crane K,Weischedel C,Wardetzky M.Geodesics in heat:a new approach to computing distance based on heat flow[J].ACM Transactions on Graphics,2013,32(5):13-15.
[20]Buja A,Swayne D F,Littman M L,et al.Data visualization with multidimensional scaling[J].Journal of Computational and Graphical Statistics,2008,17(2):444-472.
[21]Tenenbaum J B,De Silva V,Langford J C.A global geometric framework for nonlinear dimensional reduction[J].Science,2000,290(12):2319-2323.
[22]Roweis S T,Saul L K.Nonlinear dimensionality analysis by locally linear embedding[J].Science,2000,290(12):2323-2326.
[23]王晓侃,毛峡.基于非线性流形学习的人脸面部运动估计[J].电子与信息学报,2011,33(10):2531-2535.
Wang Xiaokan,Mao Xia.Human face analysis with nonlinear manifold learning[J].Journal of Electronics & Information Technology,2011,33(10):2531-2535.
[24]曹明明,干宗良,崔子冠,等.基于2D-PCA特征描述的非负权重邻域嵌入人脸超分辨率重建算法[J].电子与信息学报,2015,37(4):777-783.
Cao Mingming,Gan Zongliang,Cui Ziguan,et al.Novel neighbor embedding face hallucination based on non-negative weights and 2D-PCA feature[J].Journal of Electronics & Information Technology,2015,37(4):777-783.
[25]Sorkin O,Cohen-Or D.Least-squares meshes[C]//Proceedings of Shape Modeling International.Genova,Italy:IEEE,2004:191-199.
[26]潘志庚,庞明勇.几何网格简化研究与进展[J].江苏大学学报(自然科学版),2005,26(1):67-71.
Pan Zhigeng,Pang Mingyong.Survey for decimation of geometric meshes[J].Journal of Jiangsu University(Natural Science),2005,26(1):67-71.
[27]Schroeder W J,Zarge J A,Lorensen W E.Decimation of triangle meshes[J].Computer Graphics,1992,26(2):65-70.
[28]周昆,潘志庚,石教英.基于三角形折叠的网格简化算法[J].计算机学报,1998,21(6):506-513.
Zhou Kun,Pan Zhigeng,Shi Jiaoying.Mesh simplification algorithm based on triangle collapse[J].Chinese Journal of Computers,1998,21(6):506-513.
[29]Hoppe H,Derose T,Duchamp T,et al.Mesh optimization[C]//Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques.New York,US:ACM,1993:19-26.
[30]Garland M,Heckbert P.Surface simplification using quadric error metrics[J].Computer Graphics,1997,31(3):209-216.
[31]Varadhan S R S.On the behavior of the fundamental solution of the heat equation with variable coefficients[J].Communications on Pure and Applied Mathematics,1967,20(2):431-455.
[32]Botsch M.On linear nariational surface deformation methods[J].IEEE Transactions on Visualization & Computer Graphics,2008,14(1):213-230.

Memo

Memo:
-
Last Update: 2016-04-30