Booil Jung

LiDAR SLAM을 위한 iVox-PHC 데이터 구조에 대한 심층 고찰

본 보고서에서 다루는 ‘iVox-PHC’는 3차원 포인트 클라우드(point cloud) 데이터를 효율적으로 관리하기 위해 설계된 컴퓨터 과학 분야의 특정 데이터 구조를 지칭한다. 이는 주로 자율주행, 로보틱스, 3D 맵핑과 같은 첨단 기술 분야에서 LiDAR(Light Detection and Ranging) 센서로부터 얻어지는 방대한 양의 공간 정보를 실시간으로 처리하기 위해 사용된다.

분석에 앞서, 연구 자료에서 발견되는 여러 동음이의어(homonym)와의 개념적 구분을 통해 혼란을 방지하고 보고서의 범위를 명확히 한정할 필요가 있다. 본 보고서의 주제와 관련 없는 용어들은 다음과 같다.

따라서 본 보고서는 오직 로보틱스 및 자율 시스템 분야의 LiDAR SLAM 알고리즘 내에서 사용되는 데이터 구조로서의 ‘iVox-PHC’에 대해서만 심층적으로 고찰한다.

LiDAR SLAM(Simultaneous Localization and Mapping)은 로봇이나 차량과 같은 자율 시스템이 사전 정보가 없는 미지의 환경을 탐색하며 3D 지도를 생성하는 동시에, 그 지도상에서 자신의 위치와 자세를 실시간으로 추정하는 핵심 기술이다. 특히, LiDAR 센서와 관성 측정 장치(IMU, Inertial Measurement Unit)의 측정값을 강결합(tightly-coupled)하여 처리하는 LIO(Lidar-Inertial Odometry) 시스템은 고속으로 움직이거나, 주변 환경에 기하학적 특징이 부족한(feature-less) 경우에도 강인하고 정확한 항법 성능을 제공한다.

이러한 LIO 시스템의 실시간 성능은 수십만 개에 달하는 3D 포인트로 구성된 포인트 클라우드를 얼마나 효율적으로 저장, 업데이트, 그리고 조회할 수 있는지에 달려있다. 전통적으로 많이 사용되던 k-d 트리(k-dimensional tree)와 같은 데이터 구조는 특정 영역 내의 포인트들을 검색하는 데에는 효율적이지만, 새로운 포인트가 추가될 때마다 트리의 균형을 다시 맞추는 재균형(rebalancing) 과정에서 상당한 계산 비용이 발생한다. 이로 인해 맵을 지속적으로 업데이트해야 하는 실시간 SLAM 애플리케이션에서는 병목 현상을 유발하는 한계점을 보였다.

iVox-PHC는 이러한 실시간 처리의 한계를 극복하기 위해 제안된 경량(lightweight) 고속 데이터 구조이다. 특히 홍콩대학 연구팀이 개발한 Faster-LIO 알고리즘의 핵심 구성 요소로 제안되면서 그 효율성을 입증했다.

iVox-PHC의 핵심 설계 철학은 k-d 트리와 같은 복잡한 트리 기반 구조나, 모든 이웃과의 거리를 계산해야 하는 엄격한(strict) k-최근접 이웃(k-Nearest Neighbors, k-NN) 탐색 방식을 지양하는 것이다. 대신, 공간 해싱(spatial hashing) 기법을 기반으로 필요한 공간만 효율적으로 사용하고, 유사 힐베르트 곡선을 이용한 근사(approximated) k-NN 탐색을 통해 맵 업데이트와 포인트 매칭에 소요되는 시간을 극적으로 단축시키는 것을 목표로 한다.

본 보고서는 iVox-PHC의 근본적인 동작 원리부터 시작하여, 타 데이터 구조와의 정량적, 정성적 성능 비교를 수행하고, 실제 시스템에 적용할 때 고려해야 할 사항들을 심층적으로 분석함으로써 이 기술의 공학적 가치와 내재적 한계를 종합적으로 규명하고자 한다.

iVox-PHC 데이터 구조는 ‘iVox’라는 증분적 희소 복셀 해싱 프레임워크와, 복셀 내부의 포인트들을 효율적으로 관리하기 위한 ‘PHC(유사 힐베르트 곡선)’라는 두 가지 핵심 기술의 결합으로 이루어진다.

iVox의 기본 개념은 3차원 공간을 효율적으로 관리하기 위해 희소 복셀(sparse voxel)과 공간 해싱(spatial hashing)을 결합한 것이다.

iVox는 복셀 내부에 포인트를 저장하고 탐색하는 방식에 따라 두 가지 구체적인 구현으로 나뉜다.

이 두 방식 사이의 선택은 성능 최적화를 위한 중요한 트레이드오프 관계를 가진다. Faster-LIO 논문에서는 복셀 당 포인트 수가 적을 때는 Linear iVox가, 많을 때는 iVox-PHC가 더 효율적이라고 명시하고 있다. 이는 각 방식의 시간 복잡도에서 비롯된 당연한 결과이다. 예를 들어, 복셀 내에 포인트가 3개($n=3$)만 있다면, Linear iVox는 단 3번의 거리 계산만으로 탐색을 완료한다. 반면 iVox-PHC는 이 3개의 포인트를 PHC로 변환하고 인덱싱하는 추가적인 오버헤드가 발생하므로 오히려 더 느릴 수 있다. 하지만 만약 복셀 내에 포인트가 100개($n=100$) 있다면, Linear iVox는 100번의 계산이 필요한 반면, iVox-PHC는 $K=6$과 같은 일반적인 차수를 사용할 경우 훨씬 적은 연산으로 근사 이웃을 찾을 수 있어 압도적으로 유리해진다.

결국 어떤 방식이 더 효율적인지는 LiDAR 센서의 해상도와 사용자가 설정하는 복셀 크기에 따라 결정되는 ‘예상 포인트 밀도’에 달려있다. 이러한 이유로 Faster-LIO의 빌드 시스템은 사용자가 컴파일 시점에 -DWITH_IVOX_NODE_TYPE_PHC=ON과 같은 플래그를 통해 두 방식 중 하나를 선택할 수 있도록 유연성을 제공한다.

iVox-PHC의 기술적 가치를 명확히 이해하기 위해서는 동시대에 제안된 다른 주요 포인트 클라우드 데이터 구조와의 비교가 필수적이다. 특히 FAST-LIO2에서 사용된 ikd-Tree와 FR-LIO에서 제안된 RC-Vox와의 비교는 SLAM 데이터 구조의 발전 방향을 이해하는 데 중요한 단서를 제공한다.

Table 1: 주요 포인트 클라우드 데이터 구조 비교

기준 (Criteria) linear iVox iVox-PHC ikd-Tree (FAST-LIO2) RC-Vox (FR-LIO)
기본 메커니즘 해시 맵 + 선형 배열 해시 맵 + 유사 힐베르트 곡선 증분적 k-d 트리 로봇 중심 2계층 3D 배열
k-NN 탐색 복잡도 $O(n)$ (복셀 내 포인트 수) $O(K)$ (PHC 차수) $O(\log N)$ (전체 포인트 수) $O(1) (배열 접근) + 최적화된 탐색
탐색 방식 근사 (복셀 단위) 근사 (복셀 + PHC) 엄격 (Strict) 근사 (배열 단위)
맵 업데이트 방식 증분적 해시 삽입 증분적 해시 삽입 증분적 트리 삽입/삭제 + 재균형 증분적 배열 할당 (모듈로 연산)
핵심 장점 구현 단순, 저밀도 환경에서 효율적 고밀도 환경에서 빠른 k-NN 탐색 엄격한 k-NN, 균형 잡힌 탐색 해싱 오버헤드 없음, 최고의 속도
핵심 단점 고밀도 환경에서 비효율적 PHC 오버헤드, 파라미터 민감 재균형 비용, 증분 업데이트 복잡 고정 크기, 메모리 관리 복잡

출처: 기반으로 재구성

iVox와 k-d 트리의 가장 근본적인 차이는 공간을 분할하고 접근하는 방식에 있다. iVox는 공간을 고정된 크기의 격자(grid)로 나누고, 해싱을 통해 각 격자에 $O(1)$ 시간 복잡도로 접근한다. 반면, k-d 트리는 데이터의 분포에 따라 공간을 동적으로 분할하는 트리 구조를 형성하며, 탐색에는 $O(\log N)$의 시간이 소요된다. FAST-LIO2 알고리즘에 사용된 ikd-Tree는 기존의 정적 k-d 트리를 개선하여 포인트의 증분적 삽입, 삭제, 그리고 트리의 재균형을 효율적으로 지원하도록 설계되었다.

이 두 구조의 성능 차이는 ‘엄격한 k-NN 탐색’의 필요성에 대한 철학적 차이에서 비롯된다. k-d 트리는 수학적으로 가장 가까운 이웃을 보장하는 ‘엄격한’ 탐색 결과를 제공하는 데 최적화되어 있다. 그러나 iVox의 설계는 LIO 시스템의 특성을 깊이 고려한 결과물이다. LIO 시스템은 LiDAR 데이터뿐만 아니라 IMU 데이터도 함께 사용하는데, IMU는 매우 높은 주기로 로봇의 움직임을 측정하여 다음 순간의 로봇 자세에 대한 매우 정확한 초기 추정치를 제공한다.

이 정확한 초기 추정치 덕분에, 시스템은 현재 스캔의 포인트들이 맵의 어느 부분과 정합되어야 하는지를 이미 높은 확률로 알고 있다. 따라서 전체 맵을 대상으로 광범위하게 이웃을 탐색할 필요가 없으며, 예상 위치 주변의 매우 좁은 영역 내에서만 지역적인 탐색을 수행하면 충분하다. Faster-LIO 논문은 바로 이 점을 지적하며, “정확한 초기 추정치 덕분에 엄격한 k-NN 탐색이나 범위 탐색은 불필요하다(Strict k-NN searches and range searches are unnecessary)”고 명시적으로 밝히고 있다.

결론적으로 iVox는 LIO라는 특정 응용 분야에 고도로 최적화된 도구이다. 엄격한 탐색의 정확성을 보장하는 대신, ‘충분히 좋은’ 근사 이웃을 훨씬 빠른 속도로 찾아내는 방식을 택한 것이다. 이는 센서 융합이 제공하는 이점을 최대한 활용하여 데이터 구조의 설계 자체를 간소화하고 가속화한 영리한 접근법이라 할 수 있다.

RC-Vox(Robocentric Voxel)는 FR-LIO 논문에서 iVox의 성능을 한 단계 더 끌어올리기 위해 제안된 차세대 데이터 구조이다. RC-Vox는 iVox의 직접적인 후속 기술로 볼 수 있으며, iVox의 근본적인 한계를 해결하는 데 초점을 맞추고 있다.

iVox의 성능 병목 지점은 아무리 빠른 해시 함수를 사용하더라도 피할 수 없는 ‘해시 함수 자체의 계산 비용’과 ‘해시 충돌 처리로 인한 오버헤드’이다. RC-Vox는 이 문제를 해결하기 위해 해시 테이블이라는 간접적인 접근 방식을 완전히 버리고, 고정 크기의 2계층 3D 배열(fixed-size, two-layer 3D array)이라는 직접 주소 지정 방식을 채택했다. 배열의 특정 인덱스에 접근하는 것은 진정한 의미의 $O(1)$ 연산으로, 해시 테이블의 평균(amortized) $O(1)$보다 빠르고 일관된 성능을 보장한다.

물론, 대규모 맵 전체를 거대한 배열로 표현하는 것은 엄청난 메모리 낭비를 초래한다. RC-Vox는 이 문제를 ‘로봇 중심(robocentric)’이라는 개념으로 해결한다. 즉, 맵 전체를 저장하는 대신, 현재 로봇의 위치를 중심으로 하는 일정 크기의 영역(예: LiDAR 최대 탐사 거리의 2배)만을 배열에 유지한다. 로봇이 이 영역의 경계를 벗어나면, 모듈로(modulo) 연산을 통해 배열의 인덱스를 순환시켜 마치 무한한 공간처럼 사용한다. 이를 통해 메모리 사용량을 일정하게 유지하면서도 배열의 빠른 접근 속도를 활용할 수 있다.

성능 비교 결과는 이러한 설계의 우수성을 명확히 보여준다. FR-LIO 논문에 따르면, 단일 스레드로 동작하는 RC-Vox 기반 시스템이 병렬 처리로 가속화된 iVox 기반 시스템(Faster-LIO)과 동등하거나 오히려 더 빠른 성능을 보인다. 이는 해싱 관련 오버헤드를 제거한 것이 결정적인 성능 향상으로 이어졌음을 증명한다. 이처럼 iVox의 한계가 RC-Vox의 설계를 직접적으로 동기 부여했다는 점은 LiDAR SLAM 데이터 구조 연구의 논리적인 발전 경로를 보여주는 중요한 대목이다.

iVox-PHC 데이터 구조는 경량화와 고속 처리가 핵심 요구사항인 다양한 실시간 자율 시스템에 성공적으로 적용되었다. Faster-LIO 알고리즘을 통해 입증된 바와 같이, 이 기술은 정확도를 희생하지 않으면서도 전례 없는 처리 속도를 달성했다.

Table 2: Faster-LIO (iVox) 성능 측정 데이터 (단위: ms/scan, 평균값)

환경 (Environment) FPS iVox 추가 시간 (avg) 증분 매핑 시간 (avg) PCL k-d 트리 시간 (avg)
실내 (Indoor) 585 0.007 0.036 0.195
실외 (Outdoor) 213 0.048 0.194 0.386
캠퍼스 (Campus) 417 0.120 0.181 0.247

출처:

이 표에서 ‘iVox 추가 시간’과 ‘증분 매핑 시간’은 iVox를 사용한 맵 업데이트에 소요되는 시간을 나타내며, PCL(Point Cloud Library)의 표준 k-d 트리 구축 시간과 비교했을 때 월등히 빠른 것을 확인할 수 있다.

iVox-PHC를 실제 시스템에 성공적으로 적용하기 위해서는 몇 가지 실용적인 고려사항과 파라미터 최적화 과정이 수반된다.

iVox-PHC는 고속 Lidar-Inertial Odometry(LIO) 시스템이라는 특정 응용 분야의 요구사항을 정확히 파악하고, 이에 맞춰 기존 데이터 구조를 영리하게 변형한 성공적인 사례이다. 이 기술의 핵심적인 공헌과 한계는 다음과 같이 요약할 수 있다.

결론적으로 iVox-PHC는 LIO를 위한 실시간 포인트 클라우드 관리 분야에서 중요한 기술적 이정표를 세웠으며, 속도와 정확성 사이의 트레이드오프를 어떻게 효과적으로 설계할 수 있는지에 대한 훌륭한 사례를 제시했다.

iVox, ikd-Tree, RC-Vox와 같은 데이터 구조들은 모두 인간이 정교하게 설계한 ‘규칙 기반(rule-based)’ 알고리즘의 정점에 있다. 이들은 공간을 어떻게 분할하고, 어떻게 인덱싱하며, 어떻게 탐색할지에 대한 명시적인 규칙에 따라 동작한다. 그러나 SLAM 연구의 최신 동향은 이러한 수동적 설계를 넘어, 데이터로부터 직접 최적의 방법을 학습하는 ‘학습 기반(learning-based)’ 접근법으로 빠르게 이동하고 있다.

이러한 패러다임의 전환은 iVox와 같은 데이터 구조의 미래 역할에 중요한 시사점을 던진다.

이러한 학습 기반 접근법들은 미래의 SLAM 시스템이 iVox와 같은 명시적인 데이터 구조에 의존하기보다, 신경망을 통해 맵의 압축된 잠재 표현(latent representation)을 학습하고, 이 학습된 특징 공간 내에서 위치 추정 및 맵핑을 수행할 가능성을 시사한다.

이러한 관점에서 볼 때, iVox-PHC는 특정 문제(실시간 LIO)에 대해 고전적인 컴퓨터 과학 알고리즘을 극한까지 최적화하여 이룬 성과물이라 평가할 수 있다. 이는 그 자체로 높은 기술적 가치를 지니지만, 동시에 SLAM 연구가 규칙 기반 설계에서 종단간 학습(end-to-end learning)으로 나아가는 거대한 흐름 속에서 중요한 과도기적 기술로 자리매김할 것으로 전망된다.