Super 4PCS Fast Global Pointcloud Registration via Smart Indexing. (August 2014)
- Record Type:
- Journal Article
- Title:
- Super 4PCS Fast Global Pointcloud Registration via Smart Indexing. (August 2014)
- Main Title:
- Super 4PCS Fast Global Pointcloud Registration via Smart Indexing
- Authors:
- Mellado, Nicolas
Aiger, Dror
Mitra, Niloy J. - Abstract:
- <abstract abstract-type="main"> <title>Abstract</title> <p>Data acquisition in large‐scale 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‐of‐the‐art 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 <italic>S<sc>uper</sc> 4PCS</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 'instance problem' and solve it efficiently using a smart indexing data organization. The algorithm is simple, memory‐efficient, and fast. We demonstrate that <italic>S<sc>uper</sc> 4PCS</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<abstract abstract-type="main"> <title>Abstract</title> <p>Data acquisition in large‐scale 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‐of‐the‐art 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 <italic>S<sc>uper</sc> 4PCS</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 'instance problem' and solve it efficiently using a smart indexing data organization. The algorithm is simple, memory‐efficient, and fast. We demonstrate that <italic>S<sc>uper</sc> 4PCS</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 <ext-link ext-link-type="uri" xlink:href="http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink">http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/</ext-link>.</p> </abstract> … (more)
- Is Part Of:
- Computer graphics forum. Volume 33:Number 5(2014)
- Journal:
- Computer graphics forum
- Issue:
- Volume 33:Number 5(2014)
- Issue Display:
- Volume 33, Issue 5 (2014)
- Year:
- 2014
- Volume:
- 33
- Issue:
- 5
- Issue Sort Value:
- 2014-0033-0005-0000
- Page Start:
- 205
- Page End:
- 215
- Publication Date:
- 2014-08
- Subjects:
- Computer graphics -- Periodicals
006.605 - Journal URLs:
- http://onlinelibrary.wiley.com/doi/10.1111/j.1467-8659.1982.tb00001.x/abstract ↗
http://onlinelibrary.wiley.com/ ↗
http://www.blackwell-synergy.com/servlet/useragent?func=showIssues&code=cgf ↗ - DOI:
- 10.1111/cgf.12446 ↗
- Languages:
- English
- ISSNs:
- 0167-7055
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3393.982000
British Library DSC - BLDSS-3PM
British Library STI - ELD Digital store - Ingest File:
- 4219.xml