{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:20:00Z","timestamp":1775913600805,"version":"3.50.1"},"reference-count":35,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2014,8,23]],"date-time":"2014-08-23T00:00:00Z","timestamp":1408752000000},"content-version":"vor","delay-in-days":22,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Computer Graphics Forum"],"published-print":{"date-parts":[[2014,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Data acquisition in large\u2010scale scenes regularly involves accumulating information across multiple scans. A common approach is to locally align scan pairs using Iterative Closest Point (ICP) algorithm (or its variants), but requires static scenes and small motion between scan pairs. This prevents accumulating data across multiple scan sessions and\/or different acquisition modalities (e.g., stereo, depth scans). Alternatively, one can use a global registration algorithm allowing scans to be in arbitrary initial poses. The state\u2010of\u2010the\u2010art global registration algorithm, 4PCS, however has a quadratic time complexity in the number of data points. This vastly limits its applicability to acquisition of large environments. We present <jats:italic>S<jats:sc>uper<\/jats:sc> 4PCS<\/jats:italic> for global pointcloud registration that is optimal, i.e., runs in linear time (in the number of data points) and is also output sensitive in the complexity of the alignment problem based on the (unknown) overlap across scan pairs. Technically, we map the algorithm as an \u2018instance problem\u2019 and solve it efficiently using a smart indexing data organization. The algorithm is simple, memory\u2010efficient, and fast. We demonstrate that <jats:italic>S<jats:sc>uper<\/jats:sc> 4PCS<\/jats:italic> results in significant speedup over alternative approaches and allows unstructured efficient acquisition of scenes at scales previously not possible. Complete source code and datasets are available for research use at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/geometry.cs.ucl.ac.uk\/projects\/2014\/super4PCS\/\">http:\/\/geometry.cs.ucl.ac.uk\/projects\/2014\/super4PCS\/<\/jats:ext-link>.<\/jats:p>","DOI":"10.1111\/cgf.12446","type":"journal-article","created":{"date-parts":[[2014,8,23]],"date-time":"2014-08-23T13:44:48Z","timestamp":1408801488000},"page":"205-215","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":512,"title":["Super 4PCS Fast Global Pointcloud Registration via Smart Indexing"],"prefix":"10.1111","volume":"33","author":[{"given":"Nicolas","family":"Mellado","sequence":"first","affiliation":[{"name":"University College London"}]},{"given":"Dror","family":"Aiger","sequence":"additional","affiliation":[{"name":"Google Inc."}]},{"given":"Niloy J.","family":"Mitra","sequence":"additional","affiliation":[{"name":"University College London"}]}],"member":"311","published-online":{"date-parts":[[2014,8,23]]},"reference":[{"key":"e_1_2_9_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2009.05.014"},{"key":"e_1_2_9_3_2","doi-asserted-by":"crossref","unstructured":"AronovB. KoltunV. SharirM.:Incidences between points and circles in three and higher dimensions. InDiscrete Comput. Geom. (2005) pp.185\u20132006. 3","DOI":"10.1007\/s00454-004-1111-9"},{"key":"e_1_2_9_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360684"},{"key":"e_1_2_9_5_2","doi-asserted-by":"crossref","unstructured":"AlbarelliA. Rodol\u00e0E. TorselloA.:Loosely distinctive features for robust surface alignment. InECCV(2010) pp.519\u2013532. 3","DOI":"10.1007\/978-3-642-15555-0_38"},{"key":"e_1_2_9_6_2","doi-asserted-by":"crossref","unstructured":"ArvoJ.:A simple method for box\u2010sphere intersection testing. InGraphics Gems GlassnerA.S. (Ed.).1990. 6 7","DOI":"10.1016\/B978-0-08-050753-8.50071-1"},{"key":"e_1_2_9_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.121791"},{"issue":"5","key":"e_1_2_9_8_2","first-page":"1","article-title":"Sparse iterative closest point","volume":"32","author":"Bouaziz S.","year":"2013","journal-title":"CGF (SGP)"},{"issue":"11","key":"e_1_2_9_9_2","article-title":"Supermatching: Feature matching using supersym\u2010metric geometric constraints","volume":"19","author":"Cheng Z.\u2010Q.","year":"2013","journal-title":"IEEE TVCG"},{"key":"e_1_2_9_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-012-0552-5"},{"key":"e_1_2_9_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189314"},{"key":"e_1_2_9_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.809117"},{"key":"e_1_2_9_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0262-8856(92)90066-C"},{"key":"e_1_2_9_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2012.07.006"},{"key":"e_1_2_9_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"e_1_2_9_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/358669.358692"},{"key":"e_1_2_9_17_2","doi-asserted-by":"publisher","DOI":"10.1086\/427976"},{"key":"e_1_2_9_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1043-4"},{"key":"e_1_2_9_19_2","unstructured":"GuennebaudG. IacobB. ETAL.:Eigen v3.http:\/\/eigen.tuxfamily.org 2010. 7"},{"key":"e_1_2_9_20_2","unstructured":"GelfandN. MitraN.J. GuibasL.J. PottmannH.:Robust global registration. InProc. SGP(2005) pp.197\u2013206. 3"},{"key":"e_1_2_9_21_2","unstructured":"IzadiS. KimD. HilligesO. MolyneauxD. NewcombeR. KohliP. ShottonJ. HodgesS. FreemanD. DavisonA. FitzgibbonA.:Kinectfusion: Real\u2010time 3d reconstruction and interaction using a moving depth camera. InProc. UIST(2011) pp.559\u2013568. 2"},{"key":"e_1_2_9_22_2","doi-asserted-by":"crossref","unstructured":"IraniS. RaghavanP.:Combinatorial and experimental results for randomized point matching algorithms. InProc. Symposium on Computational Geometry(1996) pp.68\u201377. 2","DOI":"10.1145\/237218.237240"},{"key":"e_1_2_9_23_2","unstructured":"LiX. GuskovI.:Multi\u2010scale features for approximate alignment of point\u2010based surfaces. InProc. SGP(2005). 3"},{"key":"e_1_2_9_24_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03174.x"},{"key":"e_1_2_9_25_2","doi-asserted-by":"crossref","unstructured":"MitraN.J. GelfandN. PottmannH. GuibasL.:Registration of point cloud data from a geometric optimization perspective. InProc. SGP(2004) pp.23\u201331. 2","DOI":"10.1145\/1057432.1057435"},{"key":"e_1_2_9_26_2","doi-asserted-by":"crossref","unstructured":"PapazovC. BurschkaD.:Stochastic optimization for rigid point set registration. InProc. Intern. Symposium on Advances in Visual Computing(2009) pp.1043\u20131054. 3","DOI":"10.1007\/978-3-642-10331-5_97"},{"key":"e_1_2_9_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2011.05.008"},{"key":"e_1_2_9_28_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/342\/06151"},{"key":"e_1_2_9_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2008.01.002"},{"key":"e_1_2_9_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-012-0568-x"},{"key":"e_1_2_9_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566600"},{"key":"e_1_2_9_32_2","first-page":"145","volume-title":"Proc. 3DIM","author":"Rusinkiewicz S.","year":"2001"},{"key":"e_1_2_9_33_2","doi-asserted-by":"crossref","unstructured":"ShangL. GreenspanM.:Pose determination by potentialwell space embedding. InProc. 3DIM(2007) pp.297\u2013304. 2","DOI":"10.1109\/3DIM.2007.40"},{"issue":"7","key":"e_1_2_9_34_2","first-page":"1199","article-title":"Registration of 3d point clouds and meshes: A survey from rigid to nonrigid","volume":"19","author":"Tam G.","year":"2013","journal-title":"IEEE TVCG"},{"key":"e_1_2_9_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2010.11.021"},{"key":"e_1_2_9_36_2","doi-asserted-by":"publisher","DOI":"10.1561\/0600000017"}],"container-title":["Computer Graphics Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1111%2Fcgf.12446","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/cgf.12446","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T03:26:48Z","timestamp":1697426808000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1111\/cgf.12446"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.1111\/cgf.12446"],"URL":"https:\/\/doi.org\/10.1111\/cgf.12446","archive":["Portico"],"relation":{},"ISSN":["0167-7055","1467-8659"],"issn-type":[{"value":"0167-7055","type":"print"},{"value":"1467-8659","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8]]},"assertion":[{"value":"2014-08-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}