乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T05:24:19Z","timestamp":1733376259726,"version":"3.30.1"},"reference-count":78,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2023,12,5]]},"abstract":"We present GEGNN, a learning-based method for computing the approximate geodesic distance between two arbitrary points on discrete polyhedra surfaces with constant time complexity after fast precomputation. Previous relevant methods either focus on computing the geodesic distance between a single source and all destinations, which has linear complexity at least or require a long precomputation time. Our key idea is to train a graph neural network to embed an input mesh into a high-dimensional embedding space and compute the geodesic distance between a pair of points using the corresponding embedding vectors and a lightweight decoding function. To facilitate the learning of the embedding, we propose novel graph convolution and graph pooling modules that incorporate local geodesic information and are verified to be much more effective than previous designs. After training, our method requires only one forward pass of the network per mesh as precomputation. Then, we can compute the geodesic distance between a pair of points using our decoding function, which requires only several matrix multiplications and can be massively parallelized on GPUs. We verify the efficiency and effectiveness of our method on ShapeNet and demonstrate that our method is faster than existing methods by orders of magnitude while achieving comparable or better accuracy. Additionally, our method exhibits robustness on noisy and incomplete meshes and strong generalization ability on out-of-distribution meshes. The code and pretrained model can be found on https:\/\/github.com\/IntelligentGeometry\/GeGnn.<\/jats:p>","DOI":"10.1145\/3618317","type":"journal-article","created":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T15:20:48Z","timestamp":1701789648000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Learning the Geodesic Embedding with Graph Neural Networks"],"prefix":"10.1145","volume":"42","author":[{"given":"Bo","family":"Pang","sequence":"first","affiliation":[{"name":"Peking University, China"}]},{"given":"Zhongtian","family":"Zheng","sequence":"additional","affiliation":[{"name":"Peking University, China"}]},{"given":"Guoping","family":"Wang","sequence":"additional","affiliation":[{"name":"Peking University, China"}]},{"given":"Peng-Shuai","family":"Wang","sequence":"additional","affiliation":[{"name":"Peking University, China"}]}],"member":"320","published-online":{"date-parts":[[2023,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3144567"},{"key":"e_1_2_1_2_1","volume-title":"Mesh Forging: Editing of 3D-Meshes Using Implicitly Defined Occluders. In SGP.","author":"Bendels G. H.","year":"2003","unstructured":"G. H. Bendels and R. Klein. 2003. Mesh Forging: Editing of 3D-Meshes Using Implicitly Defined Occluders. In SGP."},{"key":"e_1_2_1_3_1","volume-title":"Proc.","author":"Bhat Pravin","year":"2004","unstructured":"Pravin Bhat, Stephen Ingram, and Greg Turk. 2004. Geometric texture synthesis by example. In Symp. Geom. Proc."},{"key":"e_1_2_1_4_1","unstructured":"Shaked Brody Uri Alon and Eran Yahav. 2022. How Attentive are Graph Attention Networks?. In ICLR."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012099975-0.50005-1"},{"key":"e_1_2_1_6_1","volume-title":"ShapeNet: An information-rich 3D model repository. arXiv preprint arXiv:1512.03012","author":"Chang Angel X.","year":"2015","unstructured":"Angel X. Chang, Thomas Funkhouser, Leonidas J. Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, Jianxiong Xiao, Li Yi, and Fisher Yu. 2015. ShapeNet: An information-rich 3D model repository. arXiv preprint arXiv:1512.03012 (2015)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98601"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0500334102"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2504435.2504442"},{"key":"e_1_2_1_10_1","volume-title":"A survey of algorithms for geodesic paths and distances. arXiv preprint arXiv:2007.10430","author":"Crane Keenan","year":"2020","unstructured":"Keenan Crane, Marco Livesu, Enrico Puppo, and Yipeng Qin. 2020. A survey of algorithms for geodesic paths and distances. arXiv preprint arXiv:2007.10430 (2020)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2516971.2516977"},{"key":"e_1_2_1_12_1","volume-title":"The Heat Method for Distance Computation. Commun. ACM 60, 11","author":"Crane Keenan","year":"2017","unstructured":"Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2017. The Heat Method for Distance Computation. Commun. ACM 60, 11 (2017)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Congyue Deng Or Litany Yueqi Duan Adrien Poulenard Andrea Tagliasacchi and Leonidas J Guibas. 2021. Vector neurons: A general framework for so (3)-equivariant networks. In CVPR.","DOI":"10.1109\/ICCV48922.2021.01198"},{"key":"e_1_2_1_14_1","volume-title":"Fast Graph Representation Learning with PyTorch Geometric. In ICLR Workshop.","author":"Fey Matthias","year":"2019","unstructured":"Matthias Fey and Jan Eric Lenssen. 2019. Fast Graph Representation Learning with PyTorch Geometric. In ICLR Workshop."},{"key":"e_1_2_1_15_1","volume-title":"Frank Weichert, and Heinrich M\u00fcller.","author":"Fey Matthias","year":"2018","unstructured":"Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich M\u00fcller. 2018. SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels. In CVPR."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.46"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Michael Garland and Paul S Heckbert. 1997. Surface simplification using quadric error metrics. In SIGGRAPH.","DOI":"10.1145\/258734.258849"},{"key":"e_1_2_1_18_1","unstructured":"Justin Gilmer Samuel S Schoenholz Patrick F Riley Oriol Vinyals and George E Dahl. 2017. Neural message passing for quantum chemistry. In ICML."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Craig Gotsman and Kai Hormann. 2022. Compressing Geodesic Information for Fast Point-to-Point Geodesic Distance Queries. In SIGGRAPH Asia.","DOI":"10.1145\/3550469.3555412"},{"key":"e_1_2_1_20_1","unstructured":"Will Hamilton Zhitao Ying and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In NeurIPS."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322959"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392415"},{"key":"e_1_2_1_23_1","unstructured":"Kaiming He Xiangyu Zhang Shaoqing Ren and Jian Sun. 2016. Deep residual learning for image recognition. In CVPR."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Hugues Hoppe Tony DeRose Tom Duchamp John McDonald and Werner Stuetzle. 1993. Mesh optimization. In SIGGRAPH.","DOI":"10.1145\/166117.166119"},{"key":"e_1_2_1_25_1","unstructured":"Qingyong Hu Bo Yang Linhai Xie Stefano Rosa Yulan Guo Zhihua Wang Niki Trigoni and Andrew Markham. 2020. RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Clouds. CVPR."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3506694"},{"key":"e_1_2_1_27_1","volume-title":"Sethian","author":"Kimmel Ron","year":"1998","unstructured":"Ron Kimmel and James A. Sethian. 1998. Computing geodesic paths on manifolds. Proceedings of the National Academy of Science 95, 15 (1998)."},{"key":"e_1_2_1_28_1","unstructured":"Thomas N Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. In ICLR."},{"key":"e_1_2_1_29_1","unstructured":"Yangyan Li Rui Bu Mingchao Sun Wei Wu Xinhan Di and Baoquan Chen. 2018. PointCNN: Convolution on X-transformed points. In NeurIPS."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1805964.1805971"},{"key":"e_1_2_1_31_1","article-title":"Neural Subdivision","volume":"39","author":"Derek Liu Hsueh-Ti","year":"2020","unstructured":"Hsueh-Ti Derek Liu, Vladimir G. Kim, Siddhartha Chaudhuri, Noam Aigerman, and Alec Jacobson. 2020. Neural Subdivision. ACM Trans. Graph. (SIGGRAPH) 39, 4 (2020).","journal-title":"ACM Trans. Graph. (SIGGRAPH)"},{"volume-title":"Smooth subdivision surfaces based on triangles. Thesis","author":"Loop Charles","key":"e_1_2_1_32_1","unstructured":"Charles Loop. 1987. Smooth subdivision surfaces based on triangles. Thesis, University of Utah (1987)."},{"key":"e_1_2_1_33_1","unstructured":"Ilya Loshchilov and Frank Hutter. 2019. Decoupled weight decay regularization. In ICLR."},{"key":"e_1_2_1_34_1","volume-title":"Euclidean embeddings of finite metric spaces. Discrete Mathematics 313, 23","author":"Maehara Hiroshi","year":"2013","unstructured":"Hiroshi Maehara. 2013. Euclidean embeddings of finite metric spaces. Discrete Mathematics 313, 23 (2013)."},{"key":"e_1_2_1_35_1","unstructured":"Michael Martinek Matthias Ferstl and Roberto Grosso. 2012. 3D Shape Matching based on Geodesic Distance Distributions. In Vision Modeling and Visualization."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2001.6910"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003613990342877X"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/571647.571648"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461935"},{"volume-title":"PyTorch: An Imperative Style","author":"Paszke Adam","key":"e_1_2_1_41_1","unstructured":"Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In NeurIPS."},{"key":"e_1_2_1_42_1","unstructured":"Tobias Pfaff Meire Fortunato Alvaro Sanchez-Gonzalez and Peter Battaglia. 2020. Learning Mesh-Based Simulation with Graph Networks. In ICLR."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84882-891-9"},{"key":"e_1_2_1_44_1","volume-title":"Guibas","author":"Qi Charles R.","year":"2017","unstructured":"Charles R. Qi, Li Yi, Hao Su, and Leonidas J. Guibas. 2017. PointNet++: Deep hierarchical feature learning on point sets in a metric space. In NeurIPS."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925930"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-010-0320-3"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24574-4_28"},{"key":"e_1_2_1_48_1","volume-title":"Interior distance using barycentric coordinates. Comput. Graph. Forum (SGP) 28, 5","author":"Rustamov Raif M","year":"2009","unstructured":"Raif M Rustamov, Yaron Lipman, and Thomas Funkhouser. 2009. Interior distance using barycentric coordinates. Comput. Graph. Forum (SGP) 28, 5 (2009)."},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Ryan Schmidt Cindy Grimm and Brian Wyvill. 2006. Interactive Decal Compositing with Discrete Exponential Maps. In SIGGRAPH.","DOI":"10.1145\/1179352.1141930"},{"key":"e_1_2_1_50_1","series-title":"SIAM review 41, 2","volume-title":"Fast marching methods","author":"Sethian James A.","year":"1999","unstructured":"James A. Sethian. 1999. Fast marching methods. SIAM review 41, 2 (1999)."},{"key":"e_1_2_1_51_1","volume-title":"Efficient inter-geodesic distance computation and fast classical scaling. TPAMI 42, 1","author":"Shamai Gil","year":"2018","unstructured":"Gil Shamai, Michael Zibulevsky, and Ron Kimmel. 2018. Efficient inter-geodesic distance computation and fast classical scaling. TPAMI 42, 1 (2018)."},{"key":"e_1_2_1_52_1","article-title":"You can find geodesic paths in triangle meshes by just flipping edges","volume":"39","author":"Sharp Nicholas","year":"2020","unstructured":"Nicholas Sharp and Keenan Crane. 2020. You can find geodesic paths in triangle meshes by just flipping edges. ACM Trans. Graph. (SIGGRAPH ASIA) 39, 6 (2020).","journal-title":"ACM Trans. Graph. (SIGGRAPH ASIA)"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Martin Simonovsky and Nikos Komodakis. 2017. Dynamic edge-conditioned filters in convolutional neural networks on graphs. In CVPR.","DOI":"10.1109\/CVPR.2017.11"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601175"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073228"},{"key":"e_1_2_1_56_1","article-title":"Parallel and scalable heat methods for geodesic distance computation","volume":"43","author":"Tao Jiong","year":"2019","unstructured":"Jiong Tao, Juyong Zhang, Bailin Deng, Zheng Fang, Yue Peng, and Ying He. 2019. Parallel and scalable heat methods for geodesic distance computation. IEEE Trans. Pattern Anal. Mach. Intell. 43, 2 (2019).","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"e_1_2_1_57_1","volume-title":"Guibas","author":"Thomas Hugues","year":"2019","unstructured":"Hugues Thomas, Charles R. Qi, Jean-Emmanuel Deschaud, Beatriz Marcotegui, Fran\u00e7ois Goulette, and Leonidas J. Guibas. 2019. KPConv: Flexible and deformable convolution for point clouds. In ICCV."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.412624"},{"key":"e_1_2_1_59_1","volume-title":"Graph attention networks. stat 1050, 20","author":"Velickovic Petar","year":"2017","unstructured":"Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. stat 1050, 20 (2017)."},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"Nanyang Wang Yinda Zhang Zhuwen Li Yanwei Fu Wei Liu and Yu-Gang Jiang. 2018. Pixel2Mesh: Generating 3D mesh models from single RGB images. In CVPR.","DOI":"10.1007\/978-3-030-01252-6_4"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530087"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3326362"},{"key":"e_1_2_1_63_1","volume-title":"Parallel algorithms for approximation of distance maps on parametric surfaces. ACM Transactions on Graphics (TOG)","author":"Weber Ofir","year":"2008","unstructured":"Ofir Weber, Yohai S Devir, Alexander M Bronstein, Michael M Bronstein, and Ron Kimmel. 2008. Parallel algorithms for approximation of distance maps on parametric surfaces. ACM Transactions on Graphics (TOG) (2008)."},{"key":"e_1_2_1_64_1","unstructured":"Yuxin Wu and Kaiming He. 2018. Group normalization. In ECCV."},{"key":"e_1_2_1_65_1","article-title":"A comprehensive survey on graph neural networks","volume":"32","author":"Wu Zonghan","year":"2020","unstructured":"Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems 32, 1 (2020).","journal-title":"IEEE Transactions on Neural Networks and Learning Systems"},{"key":"e_1_2_1_66_1","volume-title":"a high-dimensional embedding approach for fast geodesic distance queries","author":"Xia Qianwei","year":"2021","unstructured":"Qianwei Xia, Juyong Zhang, Zheng Fang, Jin Li, Mingyue Zhang, Bailin Deng, and Ying He. 2021. GeodesicEmbedding (GE): a high-dimensional embedding approach for fast geodesic distance queries. IEEE. T. Vis. Comput. Gr. (2021)."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559761"},{"key":"e_1_2_1_68_1","unstructured":"Shi-Qing Xin Xiang Ying and Ying He. 2012. Constant-time all-pairs geodesic distance query on triangle meshes. In I3D."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2407404"},{"key":"e_1_2_1_70_1","volume-title":"How powerful are graph neural networks? arXiv preprint arXiv:1810.00826","author":"Xu Keyulu","year":"2018","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018b. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 (2018)."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/1618452.1618484"},{"key":"e_1_2_1_72_1","unstructured":"Yifan Xu Tianqi Fan Mingye Xu Long Zeng and Yu Qiao. 2018a. SpiderCNN: Deep Learning on Point Sets with Parameterized Convolutional Filters. In ECCV."},{"key":"e_1_2_1_73_1","unstructured":"Luh Yen Francois Fouss Christine Decaestecker Pascal Francq and Marco Saerens. 2007. Graph nodes clustering based on the commute-time kernel. In Advances in Knowledge Discovery and Data Mining."},{"key":"e_1_2_1_74_1","volume-title":"Guibas","author":"Yi Li","year":"2017","unstructured":"Li Yi, Hao Su, Xingwen Guo, and Leonidas J. Guibas. 2017. SyncSpecCNN: Synchronized spectral CNN for 3D shape segmentation. In CVPR."},{"key":"e_1_2_1_75_1","article-title":"Saddle vertex graph (SVG) a novel solution to the discrete geodesic problem","volume":"32","author":"Ying Xiang","year":"2013","unstructured":"Xiang Ying, Xiaoning Wang, and Ying He. 2013. Saddle vertex graph (SVG) a novel solution to the discrete geodesic problem. ACM Trans. Graph. (SIGGRAPH ASIA) 32, 6 (2013).","journal-title":"ACM Trans. Graph. (SIGGRAPH ASIA)"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534161"},{"key":"e_1_2_1_77_1","volume-title":"Wenping Wang, and Ying He.","author":"Zhang Qijian","year":"2023","unstructured":"Qijian Zhang, Junhui Hou, Yohanes Yudhi Adikusuma, Wenping Wang, and Ying He. 2023. NeuroGF: A Neural Representation for Fast Geodesic Distance and Path Queries. arXiv preprint arXiv:2306.00658 (2023)."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.998671"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618317","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T11:50:44Z","timestamp":1733313044000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618317"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,5]]},"references-count":78,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12,5]]}},"alternative-id":["10.1145\/3618317"],"URL":"https:\/\/doi.org\/10.1145\/3618317","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2023,12,5]]},"assertion":[{"value":"2023-12-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}