GMOR: A Lightweight Robust Point Cloud Registration Framework via Geometric Maximum Overlapping

GMOR의 기술적 요약: 기하학적 최대 중첩(Geometric Maximum Overlapping)을 통한 경량화된 강건한 포인트 클라우드 등록 프레임워크

문제 정의
포인트 클라우드 등록은 노이즈 임계값 내에서 인라이어(inlier)의 수를 최대화함으로써 두 포인트 클라우드 사이의 강체 변환(6 자유도)을 추정하는 것을 목표로 한다. 공간적 호환성(Spatial Compatibility, SC) 그래프나 분기 한정 탐색(Branch-and-Bound, BnB)을 활용하는 기존의 최첨단(SOTA) 방식들은 높은 아웃라이어 비율에서도 우수한 성능을 보이지만, 몇 가지 중요한 한계에 직面한다. 그래프 기반 방식은 일반적으로 그래프 구축을 위해 이차 시간 및 공간 복잡도를 요구하여 확장성이 제한된다. 반대로, 다단계 BnB 탐색 방식은 분해된 단계들 사이에서 국소 최적해(local optima)가 전파됨으로써 정확도가 떨어지는 경우가 많다. 또한, 기존 접근 방식들은 종종 균등한 인라이어 카운팅에 의존하는데, 이는 신뢰도가 균일하지 않을 때 대응 관계 가중치(correspondence weights)를 활용하지 못한다는 단점이 있다.

방법론
본 논문은 6-DoF 강체 등록 문제를 2단계 회전 전용 BnB 탐색으로 분해하는 경량 프레임워크인 GMOR(Geometric Maximum Overlapping Registration)을 제안한다. 이 방법의 핵심은 강체 운동을 회전축을 따른 병진 운동과 해당 축에 대한 2D 강체 변환으로 분해하는 **샤를의 정리(Chasles' theorem)**에 기반한다.

1. 1단계: 회전축 탐색

   • 매개변수화: 회전축은 큐브 매핑(cube-mapping) 매개변수화를 사용하여 단위 반구상에서 탐색된다. 이를 통해 효율적인 2D BnB 탐색이 가능하다.
   • 최적화 목적 함수: 균등한 인라이어 카운팅 대신, 이 방법은 가중 대응 중첩(weighted correspondence overlap) 목적 함수를 최대화한다.
   • 알고리즘: 후보 회전축에 대해, 투영된 대응 관계의 **구간 스태빙(interval stabbing)**을 통해 해당 축 방향의 병진 운동을 추정한다. 이는 1D 범위 최대 쿼리(Range Maximum Query, RMQ) 문제로 정식화된다. 알고리즘은 아웃라이어를 사전 필터링하고 각 분기 노드에서 탐색 범위를 좁히기 위해 "점진적 수렴(gradually converged)" 전략을 채택한다.
   • 선택: 가장 높은 가중치를 가진 상위-$k$개의 후보 회전축을 선택하여 다음 단계로 진행함으로써 국소 최적해의 위험을 완화한다.

2. 2단계: 회전각 탐색

   • 분해: 선택된 각 축에 대해, 문제는 해당 축에 수직인 평면에서의 2D 강체 등록 문제로 축소된다. 이는 다시 1D 회전각 탐색으로 축소된다.
   • 기하학적 정식화: 주어진 각도에 대한 회전 중심은 기하학적으로 결정된다. 회전 중심에 대한 노이즈 제약 조건은 축 정렬된 경계 상자(axis-aligned bounding boxes)로 근사된다.
   • 알고리즘: 최적의 회전 중심을 찾는 문제는 쌍별로 교차하는 직사각형들에 대한 2D RMQ 문제, 즉 클리(Klee)의 직사각형 문제로 재정식화된다. 이는 레이지 프로파게이션(lazy propagation) 기능이 있는 **세그먼트 트리(segment tree)**에 의해 가속화된 스윕 라인(sweep line) 알고리즘을 사용하여 반복당 $O(N \log N)$ 시간 내에 결정론적으로 해결된다.

3. 후처리

   • 최종 강체 변환은 아웃라이어를 더욱 억제하고 변환 파라미터를 최적화하기 위해 Tukey의 biweight 커널을 사용하는 반복 가중 최소 제곱법(Iteratively Rewisted Least Squares, IRLS)을 사용하여 정밀하게 조정된다.

주요 기여

• 새로운 프레임워크: 단순한 인라이어 카운팅이 아닌 가중 대응 중첩 목적 함수를 최적화하는 2단계 회전 전용 BnB 프레임워크를 제안한다.
• 효율적인 탐색 전략: 전역 회전축 탐색을 위한 큐브 매핑 반구 매개변수화와 병진 추정을 위한 적응형 구간 스태빙을 도입하였다.
• 결정론적 솔루션: 2D RMQ(클리의 직사각형 문제)로 재정식화하여 스윕 라인 및 세그먼트 트리 알고리즘을 통해 해결 가능한 결정론적 솔루션을 제공한다.
• 복잡도 보장: 본 프레임워크는 최악의 경우에도 그래프 기반 방식의 확장성 문제를 해결하며 다항 시간 복잡도와 선형 공간 복잡도를 달성한다.

실험 결과
저자들은 실내(3DMatch, 3DLoMatch) 및 실외(KITTI) 데이터셋과 다양한 대응 관계 수 및 아웃라이어 비율을 가진 합성 데이터에서 GMOR을 평가하였다.

• 정확도: GMOR은 TEASER++, SC2-PCR++, MAC, TR-DE와 같은 SOTA 방식들과 비교하여 우수하거나 경쟁력 있는 정확도(회전 오차 및 병진 오차)를 보여주었다. 특히, 3DMatch 데이터셋(FPFH 사용 시 89.46%, FCGF 사용 시 93.22%)과 KITTI 데이터셋(RR 100%)에서 가장 높은 등록 재현율(Registration Recall, RR)을 달축성했다.
• 효율성: 이 방법은 그래프 기반 방식(예: SC2-PCR++, MAC)보다 훨씬 낮은 계산 시간을 보였으며, 종종 10배에서 60배까지 더 빠르게 실행되면서도 더 높은 정확도를 유지했다.
• 확장성: 합성 데이터에서 GMOR은 선형 공간 복잡도와 안정적인 메모리 사용량(100,000개의 대응 관계에 대해 100MB 미만)을 유지한 반면, 그래프 기반 방식은 메모리 부족 오류나 지수적 시간 증가를 겪었다.
• 강건성: 극단적인 아웃라이어 비율(최대 99%)과 다양한 대응 관계 수에서도 강건함을 유지했다.

의의 및 주장
본 논문은 구간 스태빙과 기하학적 중첩 최대화를 RMQ 문제로 규정함으로써 포인트 클라우드 등록에 대한 통합된 해석을 제공한다고 주장한다. 회전 전용 BnB 탐색과 계산 기하학 솔버를 결합함으로써, 이 방법은 그래프 기반 방식의 높은 메모리 비용을 초래하지 않으면서도 전역 최적성 보장을 희생하지 않고 효과적인 차원 축소를 달성한다. 저자들은 GMOR을 높은 정확도와 낮은 계산 오버헤드가 모두 중요한 경량 로보틱스 및 컴퓨터 비전 애플리 Anwendungen에 적합한 솔루션으로 포지셔닝한다. 또한, 이 프레임워크는 중력 사전 정보가 포함된 4-DoF 등록과 같은 제약 조건이 있는 설정도 특수 사례로서 자연스럽게 수용할 수 있다.