강건한 쌍별 표면 정합을 위한 4점 일치 집합

우리는 넓은 기초를 사용하는 3D 포인트 집합을 위한 빠르고 강건한 정렬 방식인 4PCS를 소개합니다. 이 기법은 노이즈 및 이상치에 견고하다고 알려져 있습니다. 이 알고리즘은 미리 필터링하거나 노이즈 제거를 하지 않고도 이상치로 오염된 원시 노이즈 데이터의 등록을 허용합니다. 또한, 이 방법은 시끄러운 환경에서 기본 표면 간의 신뢰할 수 있는 등록을 확립하는 데 필요한 시험 횟수를 획기적으로 줄여줍니다. 본 연구는 주어진 평면 4점 집합에 대해 강체 변환 하에서 대략적으로 일치하는 모든 동치 평면 4점 집합을 추출하는 새로운 기술에 기반합니다. 이 추출 절차는 후보 포인트의 수를 n, 보고된 4점 집합의 수를 k라고 할 때 대략 O(n^2 + k) 시간 내에 실행됩니다. 실제로 노이즈 수준이 낮고 충분한 겹침이 있을 때, 지역 기술자를 사용하면 시간 복잡도가 O(n + k)로 줄어듭니다. 우리는 또한 유사성 및 아핀 변환을 처리하기 위한 확장을 제안합니다. 우리의 기술은 일반적인 무작위 정렬 기술에 비해 한 자리 수의 점근적 가속을 달성합니다. 우리는 다양한 노이즈, 이상치, 겹침 정도를 가진 여러 범위 스캔 집합에 대해 알고리즘의 강건성을 입증합니다.