{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T22:20:58Z","timestamp":1775254858530,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,10,22]],"date-time":"2018-10-22T00:00:00Z","timestamp":1540166400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Machine Vision and Applications"],"published-print":{"date-parts":[[2019,3]]},"DOI":"10.1007\/s00138-018-0985-0","type":"journal-article","created":{"date-parts":[[2018,10,22]],"date-time":"2018-10-22T02:11:28Z","timestamp":1540174288000},"page":"291-307","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["GridDS: a hybrid data structure for residue computation in point set matching"],"prefix":"10.1007","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1005-4267","authenticated-orcid":false,"given":"Ferran","family":"Roure","sequence":"first","affiliation":[]},{"given":"Xavier","family":"Llad\u00f3","sequence":"additional","affiliation":[]},{"given":"Joaquim","family":"Salvi","sequence":"additional","affiliation":[]},{"given":"Yago","family":"Diez","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,10,22]]},"reference":[{"key":"985_CR1","doi-asserted-by":"crossref","unstructured":"Aiger, D., Mitra, N.J., Cohen-Or, D.: 4-Points congruent sets for robust pairwise surface registration. In: ACM Transactions on Graphics, vol.\u00a027, p.\u00a085 (2008)","DOI":"10.1145\/1360612.1360684"},{"key":"985_CR2","doi-asserted-by":"crossref","unstructured":"Aluru, S., Sevilgen, F.E.: Dynamic compressed hyperoctrees with application to the n-body problem. In: Foundations of Software Technology and Theoretical Computer Science, pp. 21\u201333. Springer (1999)","DOI":"10.1007\/3-540-46691-6_2"},{"key":"985_CR3","doi-asserted-by":"crossref","unstructured":"Andreadis, A., Gregor, R., Sipiran, I., Mavridis, P., Papaioannou, G., Schreck, T.: Fractured 3D object restoration and completion. In: ACM SIGGRAPH 2015 Posters, p.\u00a074. ACM (2015)","DOI":"10.1145\/2787626.2792633"},{"key":"985_CR4","first-page":"271","volume":"93","author":"S Arya","year":"1993","unstructured":"Arya, S., Mount, D.M.: Approximate nearest neighbor queries in fixed dimensions. SODA 93, 271\u2013280 (1993)","journal-title":"SODA"},{"issue":"6","key":"985_CR5","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S Arya","year":"1998","unstructured":"Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM (JACM) 45(6), 891\u2013923 (1998)","journal-title":"J. ACM (JACM)"},{"key":"985_CR6","doi-asserted-by":"crossref","unstructured":"B\u00e6rentzen, J.A., Gravesen, J., Anton, F., Aan\u00e6s, H.: 3D surface registration via iterative closest point (ICP). In: Guide to Computational Geometry Processing, pp. 263\u2013275. Springer (2012)","DOI":"10.1007\/978-1-4471-4075-7_15"},{"issue":"2","key":"985_CR7","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1109\/34.121791","volume":"14","author":"PJ Besl","year":"1992","unstructured":"Besl, P.J., McKay, N.D.: A method for registration of 3-D shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14(2), 239\u2013256 (1992)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"5","key":"985_CR8","first-page":"6","volume":"2","author":"AM Bronstein","year":"2010","unstructured":"Bronstein, A.M.: Shrec 2010: robust feature detection and description benchmark. Eurogr. Workshop 3D Object Retr. 2(5), 6 (2010)","journal-title":"Eurogr. Workshop 3D Object Retr."},{"key":"985_CR9","doi-asserted-by":"crossref","unstructured":"Buchin, K., Diez, Y., van Diggelen, T., Meulemans, W.: Efficient trajectory queries under the fr\u00e9chet distance (gis cup). In: Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL\u201917, pp. 101:1\u2013101:4. ACM, New York, NY, USA (2017). https:\/\/doi.org\/10.1145\/3139958.3140064","DOI":"10.1145\/3139958.3140064"},{"key":"985_CR10","unstructured":"Choi, S., Zhou, Q.Y., Koltun, V.: Robust reconstruction of indoor scenes. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015, pp. 5556\u20135565. IEEE (2015)"},{"key":"985_CR11","doi-asserted-by":"publisher","first-page":"2127","DOI":"10.1016\/j.patrec.2012.07.006","volume":"33","author":"Y D\u00edez","year":"2012","unstructured":"D\u00edez, Y., Mart\u00ed, J., Salvi, J.: Hierarchical normal space sampling to speed up point cloud coarse matching. Pattern Recognit. Lett. 33, 2127\u20132133 (2012)","journal-title":"Pattern Recognit. Lett."},{"issue":"3","key":"985_CR12","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/2692160","volume":"47","author":"Y D\u00edez","year":"2015","unstructured":"D\u00edez, Y., Roure, F., Llad\u00f3, X., Salvi, J.: A qualitative review on 3D coarse registration methods. ACM Comput. Surv. (CSUR) 47(3), 45 (2015)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"985_CR13","doi-asserted-by":"crossref","unstructured":"Elbaz, G., Avraham, T., Fischer, A.: 3D point cloud registration for localization using a deep neural network auto-encoder. In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), vol.\u00a000, pp. 2472\u20132481 (2017). https:\/\/doi.org\/10.1109\/CVPR.2017.265","DOI":"10.1109\/CVPR.2017.265"},{"key":"985_CR14","doi-asserted-by":"publisher","DOI":"10.1201\/b14581","volume-title":"Real-Time Collision Detection","author":"C Ericson","year":"2004","unstructured":"Ericson, C.: Real-Time Collision Detection. CRC Press, Boca Raton (2004)"},{"key":"985_CR15","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.patcog.2016.02.023","volume":"59","author":"J Fan","year":"2016","unstructured":"Fan, J., Yang, J., Ai, D., Xia, L., Zhao, Y., Gao, X., Wang, Y.: Convex hull indexed Gaussian mixture model (CH-GMM) for 3D point set registration. Pattern Recognit. 59, 126\u2013141 (2016)","journal-title":"Pattern Recognit."},{"key":"985_CR16","doi-asserted-by":"publisher","first-page":"1000","DOI":"10.1109\/T-C.1975.224110","volume":"10","author":"JH Friedman","year":"1975","unstructured":"Friedman, J.H., Baskett, F., Shustek, L.J.: An algorithm for finding nearest neighbors. IEEE Trans. comput. 10, 1000\u20131006 (1975)","journal-title":"IEEE Trans. comput."},{"issue":"3","key":"985_CR17","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/355744.355745","volume":"3","author":"JH Friedman","year":"1977","unstructured":"Friedman, J.H., Bentley, J.L., Finkel, R.A.: An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw. (TOMS) 3(3), 209\u2013226 (1977)","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"key":"985_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-85962-5_8","volume-title":"Oct-Tree Algorithms for Solid Modeling","author":"K Fujimura","year":"1983","unstructured":"Fujimura, K., Toriya, H., Yamaguchi, K., Kunii, T.: Oct-Tree Algorithms for Solid Modeling. Springer, Berlin (1983)"},{"key":"985_CR19","unstructured":"Gelfand, N., Mitra, N.J., Guibas, L.J., Pottmann, H.: Robust global registration. In: Eurographics Symposium on Geometry Processing, pp. 197\u2013206 (2005)"},{"key":"985_CR20","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1016\/j.proeng.2015.01.440","volume":"100","author":"B Jerbi","year":"2015","unstructured":"Jerbi, B., Suligoj, F., Svaco, M., Sekoranja, B.: Robot assisted 3D point cloud object registration. Procedia Eng. 100, 847\u2013852 (2015). https:\/\/doi.org\/10.1016\/j.proeng.2015.01.440","journal-title":"Procedia Eng."},{"issue":"5","key":"985_CR21","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1109\/34.765655","volume":"21","author":"AE Johnson","year":"1999","unstructured":"Johnson, A.E., Hebert, M.: Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Trans. Pattern Anal. Mach. Intell. 21(5), 433\u2013449 (1999)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"985_CR22","doi-asserted-by":"crossref","unstructured":"Kim, H., Hilton, A.: Evaluation of 3D feature descriptors for multi-modal data registration. In: 2013 International Conference on 3D Vision-3DV 2013, IEEE, pp. 119\u2013126 (2013)","DOI":"10.1109\/3DV.2013.24"},{"key":"985_CR23","unstructured":"K\u00f6rtgen, M., Park, G.J., Novotni, M., Klein, R.: 3D shape matching with 3D shape contexts. In: Central European Seminar on Computer Graphics, vol.\u00a03, p.\u00a05 (2003)"},{"issue":"1","key":"985_CR24","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1016\/j.patcog.2012.07.014","volume":"46","author":"Z Lian","year":"2013","unstructured":"Lian, Z., Godil, A., Bustos, B., Daoudi, M., Hermans, J., Kawamura, S., Kurita, Y., Lavou\u00e9, G., Van Nguyen, H., Ohbuchi, R., et al.: A comparison of methods for non-rigid 3D shape retrieval. Pattern Recognit. 46(1), 449\u2013461 (2013)","journal-title":"Pattern Recognit."},{"key":"985_CR25","doi-asserted-by":"crossref","unstructured":"Manay, S., Hong, B.W., Yezzi, A., Soatto, S.: Integral invariant signatures. In: European Conference on Computer Vision, pp. 87\u201399 (2004)","DOI":"10.1007\/978-3-540-24673-2_8"},{"key":"985_CR26","doi-asserted-by":"crossref","unstructured":"Mellado, N., Aiger, D., Mitra, N.J.: Super 4PCS fast global pointcloud registration via smart indexing. In: Computer Graphics Forum, vol.\u00a033, pp. 205\u2013215. Wiley Online Library (2014)","DOI":"10.1111\/cgf.12446"},{"issue":"2","key":"985_CR27","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/s11263-009-0296-z","volume":"89","author":"A Mian","year":"2010","unstructured":"Mian, A., Bennamoun, M., Owens, R.: On the repeatability and quality of keypoints for local feature-based 3D object retrieval from cluttered scenes. Int. J. Comput. Vis. 89(2), 348\u2013361 (2010)","journal-title":"Int. J. Comput. Vis."},{"issue":"1","key":"985_CR28","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.cagd.2008.01.002","volume":"26","author":"H Pottmann","year":"2009","unstructured":"Pottmann, H., Wallner, J., Huang, Q.X., Yang, Y.L.: Integral invariants for robust geometry processing. Comput. Aided Geom. Des. 26(1), 37\u201360 (2009)","journal-title":"Comput. Aided Geom. Des."},{"issue":"4","key":"985_CR29","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/s00138-016-0751-0","volume":"27","author":"T Pribani\u0107","year":"2016","unstructured":"Pribani\u0107, T., Diez, Y., Roure, F., Salvi, J.: An efficient surface registration using smartphone. Mach. Vis. Appl. 27(4), 559\u2013576 (2016)","journal-title":"Mach. Vis. Appl."},{"issue":"8","key":"985_CR30","doi-asserted-by":"publisher","first-page":"1255","DOI":"10.1016\/j.imavis.2010.01.003","volume":"28","author":"T Pribani\u0107","year":"2010","unstructured":"Pribani\u0107, T., Mrvo\u0161, S., Salvi, J.: Efficient multiple phase shift patterns for dense 3D acquisition in structured light scanning. Image Vis. Comput. 28(8), 1255\u20131266 (2010)","journal-title":"Image Vis. Comput."},{"key":"985_CR31","doi-asserted-by":"crossref","unstructured":"Roure, F., Diez, Y., Llad, X., Forest, J., Pribanic, T., Salvi, J.: A study on the robustness of shape descriptors to common scanning artifacts. In: 2015 14th IAPR International Conference on Machine Vision Applications (MVA), pp. 522\u2013525 (2015). https:\/\/doi.org\/10.1109\/MVA.2015.7153245","DOI":"10.1109\/MVA.2015.7153245"},{"key":"985_CR32","doi-asserted-by":"crossref","unstructured":"Roure, F., Diez, Y., Llad\u00f3, X., Forest, J., Pribanic, T., Salvi, J.: An experimental benchmark for point set coarse registration. In: International Conference on Computer Vision Theory and Applications (2015)","DOI":"10.5220\/0005361306790685"},{"key":"985_CR33","doi-asserted-by":"crossref","unstructured":"Roure, F., Llad\u00f3, X., Salvi, J., Pribanic, T., Diez, Y.: Hierarchical techniques to improve hybrid point cloud registration. In: VISIGRAPP (4: VISAPP), pp. 44\u201351 (2017)","DOI":"10.5220\/0006112600440051"},{"key":"985_CR34","doi-asserted-by":"crossref","unstructured":"Rusinkiewicz, S., Levoy, M.: Efficient variants of the ICP algorithm. In: IEEE International Conference on 3D Digital Imaging and Modeling, pp. 145\u2013152 (2001)","DOI":"10.1109\/IM.2001.924423"},{"key":"985_CR35","unstructured":"Rusu, R.B., Blodow, N., Beetz, M.: Fast point feature histograms (FPFH) for 3D registration. In: IEEE International Conference on Robotics and Automation, 2009. ICRA\u201909, pp. 3212\u20133217 (2009)"},{"key":"985_CR36","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.cviu.2014.04.011","volume":"125","author":"S Salti","year":"2014","unstructured":"Salti, S., Tombari, F., di Stefano, L.: Shot: unique signatures of histograms for surface and texture description. Comput. Vis. Image Underst. 125, 251\u2013264 (2014)","journal-title":"Comput. Vis. Image Underst."},{"key":"985_CR37","doi-asserted-by":"crossref","unstructured":"Salti, S., Tombari, F., Stefano, L.D.: A performance evaluation of 3D keypoint detectors. In: IEEE International Conference on 3D Imaging, Modeling, Processing, Visualization and Transmission, pp. 236\u2013243 (2011)","DOI":"10.1109\/3DIMPVT.2011.37"},{"issue":"5","key":"985_CR38","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1016\/j.imavis.2006.05.012","volume":"25","author":"J Salvi","year":"2007","unstructured":"Salvi, J., Matabosch, C., Fofi, D., Forest, J.: A review of recent range image registration methods with accuracy evaluation. Image Vis. Comput. 25(5), 578\u2013596 (2007)","journal-title":"Image Vis. Comput."},{"key":"985_CR39","unstructured":"Schnabel, R., Klein, R.: Octree-based point-cloud compression. In: SPBG, pp. 111\u2013120 (2006)"},{"issue":"11","key":"985_CR40","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1007\/s00371-011-0610-y","volume":"27","author":"I Sipiran","year":"2011","unstructured":"Sipiran, I., Bustos, B.: Harris 3D: a robust extension of the harris operator for interest point detection on 3D meshes. Vis. Comput. 27(11), 963\u2013976 (2011)","journal-title":"Vis. Comput."},{"key":"985_CR41","doi-asserted-by":"publisher","first-page":"1383","DOI":"10.1111\/j.1467-8659.2009.01515.x","volume":"28","author":"J Sun","year":"2009","unstructured":"Sun, J., Ovsjanikov, M., Guibas, L.: A concise and provably informative multi-scale signature based on heat diffusion. Comput. Graph. Forum 28, 1383\u20131392 (2009)","journal-title":"Comput. Graph. Forum"},{"issue":"1","key":"985_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11263-017-1037-3","volume":"126","author":"A Tonioni","year":"2018","unstructured":"Tonioni, A., Salti, S., Tombari, F., Spezialetti, R., Stefano, L.D.: Learning to detect good 3D keypoints. Int. J. Comput. Vis. 126(1), 1\u201320 (2018). https:\/\/doi.org\/10.1007\/s11263-017-1037-3","journal-title":"Int. J. Comput. Vis."},{"key":"985_CR43","doi-asserted-by":"crossref","unstructured":"Yang, J., Li, K., Li, K., Lai, Y.K.: Sparse non-rigid registration of 3D shapes. In: Computer Graphics Forum, vol.\u00a034, pp. 89\u201399. Wiley Online Library (2015)","DOI":"10.1111\/cgf.12699"},{"key":"985_CR44","doi-asserted-by":"crossref","unstructured":"Zaharescu, A., Boyer, E., Varanasi, K., Horaud, R.: Surface feature detection and description with applications to mesh matching. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 373\u2013380 (2009)","DOI":"10.1109\/CVPR.2009.5206748"},{"issue":"2","key":"985_CR45","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s00138-017-0885-8","volume":"29","author":"J Zhang","year":"2018","unstructured":"Zhang, J., Sun, J.: Instance-based object recognition in 3D point clouds using discriminative shape primitives. Mach. Vis. Appl. 29(2), 285\u2013297 (2018). https:\/\/doi.org\/10.1007\/s00138-017-0885-8","journal-title":"Mach. Vis. Appl."},{"key":"985_CR46","doi-asserted-by":"crossref","unstructured":"Zhong, Y.: Intrinsic shape signatures: a shape descriptor for 3D object recognition. In: IEEE International Conference on Computer Vision Workshops, pp. 689\u2013696 (2009)","DOI":"10.1109\/ICCVW.2009.5457637"},{"key":"985_CR47","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1016\/j.patcog.2017.11.029","volume":"76","author":"Y Zou","year":"2018","unstructured":"Zou, Y., Wang, X., Zhang, T., Liang, B., Song, J., Liu, H.: Broph: an efficient and compact binary descriptor for 3D point clouds. Pattern Recognit. 76, 522\u2013536 (2018). https:\/\/doi.org\/10.1016\/j.patcog.2017.11.029","journal-title":"Pattern Recognit."}],"container-title":["Machine Vision and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00138-018-0985-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00138-018-0985-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00138-018-0985-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T20:59:41Z","timestamp":1775249981000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00138-018-0985-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,22]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["985"],"URL":"https:\/\/doi.org\/10.1007\/s00138-018-0985-0","relation":{},"ISSN":["0932-8092","1432-1769"],"issn-type":[{"value":"0932-8092","type":"print"},{"value":"1432-1769","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,22]]},"assertion":[{"value":"12 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}