스퍼 4PCS: 스마트 인덱싱을 통한 빠른 글로벌 포인트 클라우드 등록

대규모 장면에서의 데이터 수집은 일반적으로 여러 스캔 데이터를 누적하는 방식을 포함한다. 일반적인 접근 방식은 반복 최근접점(Iterative Closest Point, ICP) 알고리즘(또는 그 변형)을 사용하여 스캔 쌍을 국소적으로 정렬하는 것이다. 그러나 이 방법은 정적인 장면과 스캔 쌍 간의 작은 이동만을 전제로 하므로, 여러 스캔 세션에 걸쳐 데이터를 누적하거나 다양한 촬영 모달리티(예: 스테레오, 깊이 스캔)를 활용한 데이터 수집을 제한한다. 대안적으로, 스캔 데이터가 임의의 초기 자세에 있어도 가능하도록 하는 전역 정렬(global registration) 알고리즘을 사용할 수 있다. 현재 최첨단 전역 정렬 알고리즘인 4PCS는 데이터 포인트 수에 대해 2차 시간 복잡도를 가지며, 이로 인해 대규모 환경의 데이터 수집에 매우 제한적인 적용이 가능하다. 본 연구에서는 데이터 포인트 수에 대해 선형 시간(즉, 최적의 시간 복잡도)으로 동작하며, 스캔 쌍 간의 겹침(unknown overlap)에 따라 정렬 문제의 복잡도에 따라 출력 민감(output-sensitive)인 전역 포인트 클라우드 정렬 알고리즘인 Super 4PCS를 제안한다. 기술적으로 본 알고리즘을 '인스턴스 문제(instance problem)'로 변환하고, 지능적인 인덱싱 데이터 구조를 활용하여 효율적으로 해결한다. 제안된 알고리즘은 간단하고 메모리 효율적이며 매우 빠르다. 실험을 통해 Super 4PCS가 기존 대안적 접근법에 비해 상당한 속도 향상을 제공함을 보이며, 이전까지 불가능했던 규모의 장면에 대해 비구조적이고 효율적인 데이터 수집을 가능하게 한다. 연구용으로 완전한 소스 코드와 데이터셋은 http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/ 에서 제공된다.