In computer vision and robotics, point set registration is a fundamental issue used to estimate the relative position and orientation (pose) of an object in an environment. In a rapidly changing scene, this method must be executed frequently and in a timely manner, or the pose estimation becomes outdated. The point registration method is a computational bottleneck of a vision-processing pipeline. For this reason, this paper focuses on speeding up a widely used point registration method, the iterative closest point (ICP) algorithm. In addition, the ICP algorithm is transformed into a massively parallel algorithm and mapped onto a vector processor to realize a speedup of approximately an order of magnitude. Finally, we provide algorithmic and run-time analysis.
KonoligeK.Small vision systems: hardware and implementation. In: YShiraiSHirose (eds) Robotics research. London: Springer, 1998. pp. 203–212.
2.
MyronenkoASongX.Point set registration: coherent point drift. IEEE Trans Pattern Anal Mach Intell2010; 32: 2262–2275.
3.
StamperRLLiebermanMFDrakeMV. Visual field theory and methods. In: RLStamperMFLiebermanMVDrake (eds) Becker-Shaffer’s Diagnosis and Therapy of the Glaucomas. 8th ed.Edinburgh: Mosby, pp. 91–97.
4.
RaettigRM. Accelerating point set registration for automated aerial refueling. Air force institute of technology Wright-Patterson, AFB OH, 2021.
5.
BeslPJMcKayND. Method for registration of 3-d shapes. In: Sensor fusion IV: control paradigms and data structures, vol. 1611, Boston, MA, 14–15November1991, pp. 586–606. Bellingham, WA: International Society for Optics and Photonics.
6.
AndersonJDTaylorCNWischgollT.Delaunay walk for fast nearest neighbor: accelerating correspondence matching for ICP. Mach Vis Appl2022; 33: 31.
7.
ParkSYSubbaraoM.An accurate and fast point-to plane-registration technique. Pattern Recognit Lett2003; 24: 2967–2976.
8.
BlaisGLevineMD.Registering multiview range data to create 3d computer objects. IEEE Trans Pattern Anal Mach Intell1995; 17: 820–824.
9.
ChenYMedioniG. Object modeling by registration of multiple range images. In: IEEE international conference on robotics and automation, Sacramento, CA, 9–11April1991.
10.
CoverTHartP.Nearest neighbor pattern classification. IEEE Trans Inform Theory1967; 13: 21–27.
11.
GarciaVDebreuveEBarlaudM.Fast k nearest neighbor search using GPU. In: IEEE computer society conference on computer vision and pattern recognition workshops, Anchorage, AK, 23–28June2008, pp. 1–6. New York: IEEE.
12.
FriedmanJHBentleyJLFinkelRA.An algorithm for finding best matches in logarithmic expected time. ACM Trans Math Softw1977; 3: 209–226.
13.
SproullRF.Refinements to nearest-neighbor searching ink-dimensional trees. Algorithmica1991; 6: 579–589.
14.
ShibataTKatoTWadaT.K-ddecision tree: an accelerated and memory efficient nearest neighbor classifier. In: Third IEEE international conference on data mining, Melbourne, FL, 22–22November2003, pp. 641–644. New York: IEEE.
15.
RobinsonJPiekenbrockMBurchettL, et al. Parallelized iterative closest point for autonomous aerial refueling. In: International symposium on visual computing, Las Vegas, NV, 12–14December2016, pp. 593–602. Cham: Springer.
16.
LangisCGreenspanMGodinG. The parallel iterative closest point algorithm. In: Proceedings third international conference on 3-D digital imaging and modeling, Quebec City, QC, Canada, 28May2001–1June2001, pp. 195–202. New York: IEEE.
17.
GramaAKumarVGuptaA, et al. Introduction to Parallel Computing. London: Pearson Education, 2003.
18.
RahmanMMGalanakouPKalantzisG.A fast GPU point-cloud registration algorithm. In: IEEE/ACIS international conference on software engineering, artificial intelligence, networking and parallel/distributed computing (SNPD), Busan, South Korea, 27–29June2018.
19.
GolubGHReinschC.Singular value decomposition and least squares solutions. Numer Math1970; 14: 403–420.
20.
TamakiTAbeMRaytchevB, et al. Softassign and EM-ICP on GPU. In: First international conference on networking and computing, Higashi, Japan, 17–19November2010.
21.
GrangerSPennecX. Multi-scale EM-ICP: a fast and robust approach for surface registration. In: European conference on computer vision, Copenhagen, Denmark, 28–31May2002, pp. 418–432. Berlin: Springer.
OdenL. Lessons learned from comparing C-CUDA and python-numba for GPU-computing. In: 28th euromicro international conference on parallel, distributed and network-based processing (PDP), Västerås, Sweden, 11–13March2020, pp. 216–223. New York: IEEE.
AwatramaniMZambrenoJRoverD.Increasing GPU throughput using Kernel interleaved thread block scheduling. In: IEEE 31st international conference on computer design (ICCD), Asheville, NC, 6–9October2013, pp. 503–506. New York: IEEE.
29.
FungWWLShamIYuanG, et al. Dynamic warp formation and scheduling for efficient GPU control flow. In: 40th Annual IEEE/ACM international symposium on microarchitecture (MICRO 2007), Chicago, IL, 1–5December2007, pp. 407–420. New York: IEEE.
30.
StrattonJAAnssariNRodriguesC, et al. Optimization and architecture effects on GPU computing workload performance. In: Innovative parallel computing (InPar), San Jose, CA, 13–14May2012, pp. 1–10. New York: IEEE.
31.
RichterERaettigRMackJ, et al. Accelerated shadow detection and removal method. In: 2019 IEEE/ACS 16th international conference on computer systems and applications, Abu Dhabi, United Arab Emirates, 3–7November2019, pp. 1–8. New York: IEEE.
