반복 근접점

Iterative closest point
반복적 근접점 알고리즘의 이면에 있는 아이디어

반복 근접점(ICP)[1][2][3][4]은 두 점 구름 사이의 차이를 최소화하기 위해 사용되는 알고리즘입니다.ICP는 종종 다른 스캔에서 2D 또는 3D 표면을 재구성하고 로봇을 위치시키고 최적의 경로 계획을 달성하는 데 사용됩니다(특히 미끄러운 지형으로 인해 휠 주행 측정이 신뢰할 수 없는 경우). 뼈 모델을 공동 등록하는 데 사용됩니다.

개요

반복 근접점 또는 일부 소스에서는 기준 또는 표적이 고정된 한 점 구름(수직 구름)이 유지되고 다른 점인 소스는 참조와 가장 잘 일치하도록 변환됩니다.알고리즘은 일치하는 쌍의 좌표 간 차이 제곱합과 같은 일반적으로 소스로부터 기준점 구름까지의 거리인 오차 메트릭을 최소화하는 데 필요한 변환(변환과 회전의 조합)을 반복적으로 수정합니다.ICP는 [5]3차원 모델을 정렬하는 데 널리 사용되는 알고리즘 중 하나로, 필요한 견고한 변환에 대한 초기 추측을 제공합니다.ICP 알고리즘은 Chen과 Medioni,[3] Besl과 McKay에 [2]의해 처음 도입되었습니다.

반복 근접점 알고리즘은 Kabsch 알고리즘 및 직교 Procrustes 문제에 대한 다른 솔루션과 대조되는 반면, Kabsch 알고리즘은 점 집합 간의 대응을 추정 변수로 취급합니다.

입력: 참조 및 소스 점 구름, 소스를 참조에 정렬하기 위한 변환의 초기 추정(옵션), 반복을 중지하는 기준.

출력: 세련된 변환.

기본적으로 알고리즘 단계는 다음과 같습니다.[5]

  1. 소스 점 구름의 각 점(일반적으로 조밀 또는 각 모델의 정점 쌍 선택이라고 함)에 대해 참조 점 구름(또는 선택한 세트)에서 가장 가까운 점을 일치시킵니다.
  2. 각 소스 포인트를 이전 단계에서 발견한 일치에 가장 잘 맞추는 루트 평균 제곱 포인트 투 포인트 거리 메트릭 최소화 기술을 사용하여 회전과 변환의 조합을 추정합니다.이 단계에는 정렬 전에 가중치 점 및 특이치 기각이 포함될 수도 있습니다.
  3. 얻어진 변환을 사용하여 소스 포인트를 변환합니다.
  4. 반복한다(점들을 다시 연관짓는 등).

Zhang은 효율적인 근접점 계산을 위해 수정된 k-d 트리 알고리즘을 제안한다.이 작업에서는 거리 분포에 기초한 통계 방법을 사용하여 특이치, 폐색, 외관 및 소실을 처리하며, 이는 부분 집합-하위 집합 매칭을 가능하게 한다.

많은 ICP [6]베리안트가 있으며 포인트 투 포인트와 포인트 투 플레인이 가장 인기 있습니다.후자는 일반적으로 구조화된 [7][8]환경에서 더 나은 성능을 발휘합니다.

실장

  • MeshLab은 오픈소스 메쉬 처리 도구이며, ICP 알고리즘의 GNU General Public License 구현을 포함합니다.
  • CloudCompare는 ICP 알고리즘 구현을 포함하는 오픈 소스 포인트 및 모델 처리 도구입니다.GNU General Public License에 따라 출시됩니다.
  • PCL(Point Cloud Library)은 n차원 포인트 클라우드 및 3D 지오메트리 처리를 위한 오픈 소스 프레임워크입니다.여기에는 ICP [9]알고리즘의 여러 변종이 포함되어 있습니다.
  • ICP 알고리즘의 오픈 소스 C++ 실장은 VTK, ITK 및 Open3D 라이브러리에서 이용할 수 있습니다.
  • libpointmatcher는 BSD 라이선스로 출시된 포인트 투 포인트 및 포인트 투 플레인 ICP 구현입니다.
  • simpleICP는 ICP 알고리즘의 간단한 버전을 다양한 언어로 구현한 것입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Arun, Somani; Thomas S. Huang; Steven D. Blostein (1987). "Least-square fitting of two 3-D point sets". IEEE Pattern Analysis and Machine Intelligence. 9 (5): 698–700. doi:10.1109/TPAMI.1987.4767965. PMID 21869429.
  2. ^ a b Besl, Paul J.; N.D. McKay (1992). "A Method for Registration of 3-D Shapes". IEEE Transactions on Pattern Analysis and Machine Intelligence. 14 (2): 239–256. doi:10.1109/34.121791.
  3. ^ a b Chen, Yang; Gerard Medioni (1991). "Object modelling by registration of multiple range images". Image Vision Comput. 10 (3): 145–155. doi:10.1016/0262-8856(92)90066-C.
  4. ^ a b Zhang, Zhengyou (1994). "Iterative point matching for registration of free-form curves and surfaces". International Journal of Computer Vision. 13 (12): 119–152. CiteSeerX 10.1.1.175.770. doi:10.1007/BF01427149.
  5. ^ a b Rusinkiewicz, Szymon; Marc Levoy (2001). Efficient Variants of the ICP Algorithm. Proceedings Third International Conference on 3-D Digital Imaging and Modeling. Quebec City, Quebec, Canada. pp. 145–152. doi:10.1109/IM.2001.924423.
  6. ^ Pomerleau, François; Colas, Francis; Siegwart, Roland (2015). "A Review of Point Cloud Registration Algorithms for Mobile Robotics". Foundations and Trends in Robotics. 4 (1): 1–104. CiteSeerX 10.1.1.709.2212. doi:10.1561/2300000035.
  7. ^ Kok-Lim Low (February 2004). "Linear Least-Squares Optimization for Point-to-Plane ICP Surface Registration" (PDF). Comp.nys.edu.sg. Technical Report TR04-004, Department of Computer Science, University of North Carolina at Chapel Hill. Retrieved 2017-02-27.
  8. ^ 프랑수아 포멜로, 프란시스 콜라스, 롤랑 지그와르, 스테판 마그네나.실제 데이터 세트의 ICP 변형 비교.Autonomous Robots, 34(3)페이지, 133-148, DOI: 10.1007/s10514-013-9327-2, 2013년 4월.
  9. ^ Holz, Dirk; Ichim, Alexandru E.; Tombari, Federico; Rusu, Radu B.; Behnke, Sven (2015). "Registration with the Point Cloud Library: A Modular Framework for Aligning in 3-D". IEEE Robotics Automation Magazine. 22 (4): 110–124. doi:10.1109/MRA.2015.2432331.