라이다-관성 측정 장치 오도메트리(LIDAR-Inertial Odometry, LIO) 시스템은 자율주행 차량, 로보틱스, 증강 현실 등 다양한 분야에서 주변 환경을 3차원으로 인식하고 자신의 위치를 추정하는 데 필수적인 기술로 자리 잡았다.1 이 시스템의 핵심 성능 지표는 정확성(accuracy), 강건성(robustness), 그리고 효율성(efficiency)의 세 가지로 요약될 수 있다.2 특히, 로봇이 실시간으로 주변 환경과 상호작용하고 경로를 계획하기 위해서는, 센서 데이터를 지연 없이 처리하는 효율성이 무엇보다 중요하다. 그러나 LIO 시스템의 파이프라인, 특히 지속적으로 업데이트되는 3D 맵을 관리하는 모듈은 상당한 계산 부하를 유발하며, 이는 전체 시스템의 실시간 성능을 저해하는 주요 병목 지점(bottleneck)으로 작용한다.2
전통적인 LIO 시스템은 맵 관리를 위해 주로 kd-tree나 해시(hash) 기반 복셀(voxel)과 같은 공간 자료 구조에 의존해왔다. 이러한 구조들은 대규모 포인트 클라우드 데이터를 효율적으로 저장하고 검색하기 위해 고안되었지만, LIO의 특수한 요구사항, 즉 빈번한 동적 업데이트와 빠른 이웃 탐색이라는 과제 앞에서 명확한 한계를 드러낸다.
첫째, kd-tree 구조는 특정 지점의 k-최근접 이웃(k-Nearest Neighbor, k-NN)을 빠르게 찾는 데 강점을 보인다.3 FAST-LIO2 시스템에서 사용된 ikd-Tree는 이러한 kd-tree를 동적으로 업데이트할 수 있도록 개선한 버전으로, 새로운 포인트가 추가되거나 오래된 포인트가 삭제될 때 전체 트리를 재구성하는 대신 부분적인 수정만을 수행하여 맵 업데이트 시간을 크게 단축시켰다.2 그럼에도 불구하고, 트리의 특정 부분에서 삽입 및 삭제가 빈번하게 발생하여 트리가 불균형해지면, 균형을 맞추기 위한 부분적인 재구성 작업이 여전히 필요하며 이는 계산 비용을 유발한다.3
둘째, 해시 기반 복셀 구조는 kd-tree에 비해 맵의 삽입, 삭제, 쿼리 연산에서 더 낮은 시간 복잡도를 가진다.2 Faster-LIO 시스템에서 제안된 iVox는 해시 테이블과 LRU(Least Recently Used) 캐시 정책을 결합하여 복셀 맵을 관리한다.2 이 구조는 병렬 처리를 통해 ikd-Tree의 성능을 능가하는 효율성을 보여주었으나, 근본적인 한계를 내포하고 있다. 해시 구조는 해시 함수 자체의 계산에 따르는 오버헤드와 서로 다른 키가 동일한 해시 값으로 매핑되는 해시 충돌(hash collision) 문제를 피할 수 없다. 이러한 문제들로 인해 해시 테이블은 이론적으로 가장 빠른 접근 속도인 O(1)을 보장하는 배열(array) 구조만큼의 순수한 속도를 달성하기 어렵다.2
이러한 기존 자료 구조들의 한계를 극복하기 위해, FR-LIO 시스템의 일부로 RC-Vox (Robocentric Voxel Map)라는 새로운 맵 관리 구조가 제안되었다.1 RC-Vox의 핵심은 기존 접근법들이 확장 가능한 전역 맵(global map)을 효율적으로 관리하는 방법에 초점을 맞춘 것과 달리, 문제 자체를 ‘LIO 프론트엔드 오도메트리에 필요한 지역 맵(local map)을 어떻게 가장 빠르게 처리할 것인가’로 재정의한 데 있다. LIO 시스템의 실시간 성능은 상태 추정 단계의 속도에 크게 좌우되며, 이 과정은 본질적으로 현재 라이다 스캔과 주변 맵 사이의 대응점을 찾는 k-NN 탐색에 의존한다.2 RC-Vox 개발자들은 오도메트리가 ‘로컬’ 작업이라는 본질에 착안하여, 전역 맵의 무한한 확장성을 과감히 포기하는 대신 로컬 맵의 접근 속도를 극한으로 끌어올리는 방향을 선택했다.
이를 위해 RC-Vox는 그동안 대규모 포인트 클라우드 표현에 있어 막대한 메모리 소비 문제($O(N^3)$) 때문에 기피되어 온 배열 구조를 과감하게 채택했다.2 이는 로봇을 중심으로 한 고정된 크기의 지역 맵만을 유지하는 ‘로보센트릭(robocentric)’ 접근 방식을 통해 가능해졌다. 즉, RC-Vox는 가장 적합한 도구를 선택한 것을 넘어, 문제 자체를 도구(배열)에 맞게 재구성한 혁신적인 발상이라 할 수 있다. 본 보고서는 이 RC-Vox의 개념적 기반, 아키텍처, 작동 메커니즘, 그리고 성능을 심층적으로 고찰하고자 한다.
RC-Vox는 이름에서 알 수 있듯이 로봇을 중심으로(robocentric) 하는 복셀 맵 구조이다. 보다 구체적으로, RC-Vox는 로봇의 현재 위치를 기준으로 하는 고정된 크기의 정육면체(cube) 형태의 가상 공간 내에서 지역 맵 포인트(local map points)를 유지하고 관리하는 역할을 한다.1 이 큐브의 한 변의 길이는 일반적으로 라이다 센서의 유효 측정 범위(예: 150m)의 두 배로 설정된다. 이는 로봇이 어떤 방향으로든 이동하더라도, 포인트 클라우드 정합(registration)을 수행하는 데 필요한 주변 맵 정보를 충분히 확보하기 위함이다.2
중요한 점은 RC-Vox 내에 저장되는 모든 포인트의 좌표 자체는 전역 좌표계(global coordinate system)를 기준으로 표현된다는 것이다.2 그러나 이 포인트들의 관리, 즉 저장, 검색, 삭제는 오직 로봇 중심의 지역 맵 내에서만 이루어진다. 이는 전역 맵 전체를 메모리에 상주시키거나 디스크에서 불러오는 대신, 현재 위치 추정에 직접적으로 필요한 데이터만을 효율적으로 다루겠다는 설계 철학을 반영한다.
RC-Vox의 가장 근본적인 설계 철학은 속도를 위해 확장성을 희생하는 트레이드오프에 있다. 이를 구현하기 위한 핵심 선택은 포인터 기반의 트리 구조(kd-tree)나 해시 테이블 대신, 직접 주소 지정(direct addressing)이 가능한 고정 크기 3D 배열을 기본 자료 구조로 채택한 것이다.2
이 선택은 시간 복잡도와 공간 복잡도 사이의 고전적인 트레이드오프를 명확히 보여준다.
RC-Vox는 이 문제를 로봇 주변의 ‘지역 맵’으로 범위를 한정함으로써 해결한다. 관리해야 할 공간의 크기가 고정되므로, 배열의 메모리 요구량이 예측 가능하고 감당할 수 있는 수준으로 유지된다. 대신, LIO 시스템의 프론트엔드 성능에 가장 치명적인 영향을 미치는 데이터 접근 속도의 이점을 극대화하는 전략을 취한 것이다.
이러한 설계는 ‘로보센트릭’이라는 개념에 이중적인 의미를 부여한다. 첫째, 공간적으로 로봇 주변의 데이터만을 다룬다는 의미이다. 둘째, 계산 복잡도 측면에서 오도메트리 연산을 전체 맵의 크기와 무관하게 상수 시간(constant time)에 가까운 성능으로 묶어두는 역할을 한다. ikd-Tree나 iVox와 같은 전역 맵 구조는 탐사 영역이 넓어질수록 데이터의 총량이 증가하고, 비록 점근적 시간 복잡도가 효율적일지라도 실제 연산 시간은 미세하게나마 증가할 수 있다. 반면, RC-Vox는 로봇이 얼마나 멀리 이동하든 오도메트리 모듈이 처리해야 할 데이터의 양과 구조의 크기가 변하지 않는다.2 결과적으로, RC-Vox 기반 시스템의 프론트엔드 성능은 전체 맵의 크기와 사실상 분리(decoupled)된다. 이는 장시간, 대규모 환경 탐사 시에도 일관된 실시간 성능을 보장하는 결정적인 요인이며, 단순한 최적화를 넘어 시스템 아키텍처 수준의 강건성을 확보하는 설계라 평가할 수 있다.
마지막으로, RC-Vox는 물리적으로는 ‘정적’인 고정 크기 배열을 사용하지만, ‘모듈로 연산(modulo operation)’이라는 수학적 기법을 통해 로봇의 움직임에 따라 맵 데이터를 배열 내에서 ‘동적’으로 순환시켜 관리한다.2 이는 정적 구조의 속도 이점과 동적 데이터 관리의 유연성을 결합한 하이브리드 접근 방식으로, RC-Vox의 핵심 작동 원리 중 하나이다.
RC-Vox는 배열 구조의 빠른 접근 속도를 활용하면서도, 단일 거대 배열이 가질 수 있는 메모리 비효율성과 희소 데이터(sparse data) 관리의 어려움을 완화하기 위해 독창적인 고정 크기의 2계층 3D 배열 구조(fixed-size, two-layer 3D array structure)를 채택했다.1 이 계층적 구조는 공간을 서로 다른 해상도로 분할하여 관리함으로써 메모리 사용과 접근 속도 사이의 균형을 맞춘다. 상위 계층은 TLA(Top-Level Array), 하위 계층은 BLA(Bottom-Level Array)로 명명된다.2
이러한 접근 방식은 컴퓨터 그래픽스나 데이터베이스 분야에서 오랫동안 연구되어 온 ‘계층적 그리드(Grid Hierarchy)’나 ‘그리드 파일(Grid File)’과 개념적으로 유사하다.9 단일 플랫 그리드(Flat Grid)는 접근은 빠르지만 메모리 낭비가 심한 반면 9, RC-Vox의 TLA는 데이터 대신 포인터를 저장하여 1차적으로 공간을 분할하고, BLA는 필요한 부분에만 세부 그리드를 동적으로 할당하는 ‘적응형(adaptive)’ 그리드 전략을 사용한다. 이는 완전히 동적인 트리(Octree)나 해시 테이블과, 완전히 정적인 플랫 그리드 사이의 영리한 절충안이다. 포인터 추적이 거의 없고(TLA에서 BLA로 단 한 번), 메모리 접근 패턴이 규칙적이고 예측 가능하여 CPU 캐시 효율성(cache friendliness)이 매우 높다는 장점이 있다.9 따라서 RC-Vox는 새로운 발명이라기보다는, LIO라는 특정 도메인의 제약 조건(로컬 맵, 실시간성)에 맞춰 고전적인 자료구조를 극한으로 튜닝하고 최적화한 엔지니어링의 성과로 볼 수 있다.
TLA는 RC-Vox 구조의 최상위 계층으로, 전체 지역 맵 공간을 거시적으로 분할하는 거친 해상도(coarse resolution)의 그리드(grid) 역할을 수행한다.2
BLA는 TLA 그리드 하나하나의 내부 공간을 미시적으로 분할하는 고해상도(fine resolution)의 복셀(voxel) 배열이다.2
std::vector와 같은 동적 배열 형태로 구현된다.결론적으로, TLA는 빠른 거시적 위치 탐색을, BLA는 필요한 곳에만 할당되는 효율적인 미시적 데이터 저장을 담당함으로써, RC-Vox는 속도와 메모리 효율이라는 두 마리 토끼를 모두 잡는 정교한 아키텍처를 완성한다.
RC-Vox의 아키텍처가 ‘어떻게 구성되어 있는가’를 설명한다면, 작동 메커니즘은 ‘어떻게 동작하는가’에 대한 답을 제공한다. 핵심 메커니즘은 로봇의 움직임에 따라 맵을 효율적으로 업데이트하는 증분 매핑과, 포인트 클라우드 정합의 핵심인 k-NN 탐색을 가속화하는 전략으로 나뉜다.
RC-Vox의 증분 매핑은 고정된 크기의 배열(TLA) 위에서 무한히 넓은 공간을 탐사하는 것처럼 보이게 만드는 독창적인 기법이다. 그 핵심에는 모듈로 연산(modulo operation)이 있다. 이 과정은 3차원 공간에서 동작하는 환형 버퍼(Circular Buffer) 또는 링 버퍼(Ring Buffer)와 개념적으로 동일하다.
k-NN 탐색은 LIO의 상태 추정 단계에서 가장 많은 계산량을 차지하는 작업 중 하나이다. 전통적으로는 쿼리 포인트가 속한 복셀과 그 주변의 26개 이웃 복셀(3x3x3 큐브)을 모두 검색하여 가장 가까운 포인트들을 찾아야 했다. RC-Vox는 이 과정의 비효율성을 개선하기 위해 계산 부하를 전가(shifting the computational load)하는 영리한 전략을 사용한다.
이 전략의 배경에는 LIO 시스템의 두 주요 단계, 즉 ‘상태 추정’과 ‘매핑’의 실행 빈도와 시간 민감도가 비대칭적이라는 통찰이 있다. 상태 추정(k-NN 탐색 포함)은 IMU 데이터가 들어올 때마다 수백~수천 Hz의 매우 높은 빈도로 실행되며, 지연 시간에 극도로 민감하다.5 반면, 맵 업데이트(포인트 삽입)는 라이다 스캔 주기에 맞춰 상대적으로 낮은 빈도(예: 10~20 Hz)로 실행되며 시간적 여유가 있다.
RC-Vox는 이 비대칭성을 이용하여 다음과 같이 동작한다:
결과적으로, 계산 비용이 높은 ‘주변 복셀 탐색’ 작업이 빈번하고 민감한 상태 추정 단계에서 제거되고, 대신 ‘이웃 복셀에 포인트 복사’라는 추가 작업이 덜 민감하고 빈도가 낮은 매핑 단계로 옮겨진다. 이는 시스템 전체의 평균 응답 시간과 최악 응답 시간을 모두 향상시키는 효과를 가져온다. 이 기법은 전형적인 사전 계산(pre-computation) 또는 캐싱(caching) 전략을 시공간적 자료구조에 창의적으로 적용한 사례로 평가할 수 있다.
RC-Vox의 작동 메커니즘을 명확히 이해하기 위해, 핵심 연산을 정의하는 수학적 공식을 상세히 기술한다. 모든 좌표는 전역 좌표계 기준이며, 연산은 3차원의 각 축에 대해 독립적으로 적용된다.
로봇의 현재 전역 좌표를 $r_{curr} \in \mathbb{R}^3$, 시스템 초기화 시 정의된 TLA 원점의 전역 좌표를 $t_{init} \in \mathbb{R}^3$라 하자. TLA 그리드의 크기가 $g$일 때, 로봇의 현재 위치에 정렬된 지역 맵의 원점 $m_{curr} \in \mathbb{R}^3$는 다음과 같이 계산된다.2 \(m_{curr} = \lfloor (r_{curr} - t_{init}) / g \rfloor \cdot g + t_{init}\) 여기서 $\lfloor \cdot \rfloor$는 각 요소에 대한 floor 연산(버림)을 의미한다. 이 식은 로봇의 위치를 가장 가까운 그리드 경계로 “스냅(snap)”하여 지역 맵의 기준점을 설정하는 역할을 한다.
전역 좌표 $p \in \mathbb{R}^3$를 가진 포인트가 매핑될 TLA의 3차원 인덱스 $IT_p \in \mathbb{Z}^3$를 계산하는 과정은 두 단계로 이루어진다. 먼저, 현재 지역 맵 원점의 TLA 인덱스 $IT_{m_{curr}}$를 계산한다.
\(IT_{m_{curr}} = \lfloor (r_{curr} - t_{init}) / g \rfloor \% N_{TLA}\)
여기서 $N_{TLA}$는 TLA의 한 축에 대한 그리드의 개수(예: $2\lambda l / g$)이고, %는 정수 나눗셈의 나머지, 즉 모듈로 연산을 의미한다. 그 다음, 포인트 $p$의 최종 TLA 인덱스 $IT_p$는 다음과 같이 계산된다.2
\(IT_p = (\lfloor (p - m_{curr}) / g \rfloor + IT_{m_{curr}}) \% N_{TLA}\)
이 두 공식은 전역 좌표계 상의 무한한 공간을 TLA라는 유한하고 순환적인 인덱스 공간으로 변환하는 RC-Vox의 핵심적인 변환 과정이다.
포인트 $p$가 속한 TLA 그리드에 대해 BLA가 생성될 때, 해당 BLA의 원점 좌표 $bor_i \in \mathbb{R}^3$는 다음과 같이 먼저 결정된다.2 \(bor_i = \lfloor (p - t_{init}) / g \rfloor \cdot g + t_{init}\) 이 BLA 원점 $bor_i$를 기준으로, BLA 복셀의 크기가 $v$일 때, 포인트 $p$가 매핑될 BLA의 3차원 인덱스 $IB_p \in \mathbb{Z}^3$는 다음과 같이 계산된다.2 \(IB_p = \lfloor (p - bor_i) / v \rfloor\) 이 식은 TLA 그리드라는 거시적 공간 내에서 포인트의 미시적 위치를 복셀 단위로 정확하게 특정하는 역할을 수행한다.
RC-Vox의 설계가 이론적으로 우수하다는 점을 넘어, 실제 LIO 시스템에서 얼마나 효과적인지를 정량적으로 평가하는 것은 매우 중요하다. FR-LIO 논문에서 제시된 실험 결과는 RC-Vox가 기존의 대표적인 맵 관리 자료구조인 ikd-Tree와 iVox에 비해 상당한 성능 우위를 가짐을 명확히 보여준다.2
아래 표는 M2DGR 데이터셋을 사용하여 LIO 시스템의 주요 모듈별 평균 연산 시간을 비교한 것이다. 이 표는 RC-Vox의 성능 우위를 직관적으로 보여주는 핵심적인 증거이다. 단순히 ‘빠르다’는 주장을 넘어, 어떤 연산에서, 얼마나 빠른지를 구체적인 수치로 증명한다. 특히 RC-Vox가 단일 스레드(Single)로 동작함에도 불구하고 병렬 처리(Paral)된 경쟁자보다 빠르다는 점은 그 설계의 근본적인 효율성을 입증한다.
Table 1: 주요 맵 관리 자료구조의 연산 시간 비교 (M2DGR 데이터셋 기준)
| 모듈 (Module) | ikd-Tree (Single) [ms] | iVox (Paral) [ms] | RC-Vox (Single) [ms] |
|---|---|---|---|
| 증분 매핑 (Incremental Mapping) | ~6.0 | ~1.5 | ~1.6 |
| 맵 삭제 (Map Delete) | ~1.0 | ~0.1 | ~0.1 |
| 상태 추정 (State Estimation) | ~10.0 | ~4.0 | ~2.5 |
| 총합 (Total) | ~17.0 | ~5.6 | ~4.2 |
주: 위 표의 수치는 FR-LIO 논문8에 제시된 그래프를 기반으로 한 근사치이며, 시스템의 주요 연산 시간을 나타낸다.
표의 데이터를 통해 각 모듈별 성능을 심층적으로 분석할 수 있다.
상태 추정 단계의 압도적 우위: 가장 주목할 만한 부분은 상태 추정 단계에서의 성능이다. RC-Vox(Single)는 약 2.5ms를 소요하여, 병렬 처리된 iVox(Paral)의 약 4.0ms보다 약 37.5% 더 빠르며, 단일 스레드 ikd-Tree(Single)의 약 10.0ms에 비해서는 4배나 빠르다. 이는 앞서 설명한 개선된 k-NN 탐색 전략이 결정적인 역할을 했음을 증명한다. 계산 부하가 가장 큰 주변 복셀 탐색 과정을 매핑 단계로 이전함으로써, 실시간성이 가장 중요한 상태 추정 단계의 연산량을 극적으로 줄인 것이다.2 또한, 포인터 추적이나 해시 충돌 처리 없이 인덱스로 직접 접근하는 배열 구조의 본질적인 속도 이점이 이 단계에서 가장 크게 발휘된다.
매핑 및 삭제 단계의 경쟁력: 증분 매핑 단계에서 RC-Vox는 이웃 복셀에 데이터를 중복으로 기록하는 추가적인 오버헤드가 있음에도 불구하고, 병렬 처리된 iVox와 거의 동등한 성능(약 1.5ms vs 1.6ms)을 보인다. 이는 배열 구조의 빠른 쓰기(write) 접근 속도가 추가적인 작업을 상쇄할 만큼 효율적이라는 것을 의미한다.8
맵 삭제 단계에서는 RC-Vox와 iVox 모두 매우 빠른 성능을 보여주는데, 이는 RC-Vox의 경우 단순히 배열의 특정 영역을 초기화하는 작업에 해당하기 때문이다. 반면, ikd-Tree는 노드 삭제와 트리 재조정에 상대적으로 많은 시간을 소요한다.
종합 성능: 결과적으로 RC-Vox는 단일 스레드 환경에서도 현재 가장 빠른 LIO 시스템 중 하나인 Faster-LIO의 병렬 처리 버전보다도 빠른 총 연산 시간(약 4.2ms vs 5.6ms)을 달성했다.1 이는 RC-Vox가 LIO 시스템의 프론트엔드 효율성을 한 단계 끌어올린 혁신적인 자료구조임을 정량적으로 입증하는 결과이다.
RC-Vox는 LIO 시스템, 특히 프론트엔드 오도메트리의 효율성 문제를 해결하기 위한 새로운 패러다임을 제시했다는 점에서 큰 의의를 가진다. 그 핵심 기여는 다음과 같이 요약할 수 있다.
모든 공학적 설계와 마찬가지로, RC-Vox 또한 특정 목적을 위해 다른 부분을 희생한 트레이드오프의 산물이며, 다음과 같은 잠재적 한계점을 가진다.
RC-Vox의 견고한 기본 구조를 바탕으로 다음과 같은 방향으로의 확장을 기대할 수 있다.
| Speed test of ikd-Tree, iVox and RC-Vox | Download Scientific Diagram - ResearchGate, 8월 1, 2025에 액세스, https://www.researchgate.net/figure/Speed-test-of-ikd-Tree-iVox-and-RC-Vox_fig4_368361497 |
| SNI-SLAM: Semantic Neural Implicit SLAM | CVF Open Access, 8월 1, 2025에 액세스, https://openaccess.thecvf.com/content/CVPR2024/papers/Zhu_SNI-SLAM_Semantic_Neural_Implicit_SLAM_CVPR_2024_paper.pdf |