Octree

• 다른 이름: sparse voxel octree
• 카테고리: Sensing › 3D maps & reconstruction
• 태그: mapping, data-structures, 3d-perception, occupancy-mapping, point-clouds

3D 공간을 재귀적으로 여덟 개의 정육면체로 나누고 데이터가 있는 곳에만 세밀한 셀을 할당하는 트리 자료 구조로, 압축적인 지도와 빠른 공간 질의를 위해 쓰인다.

정의

옥트리(octree)는 모든 노드가 공간의 정육면체 하나를 나타내고 최대 여덟 개의 자식을 가질 수 있는 트리로, 각 자식은 정육면체를 세 축 모두를 따라 반으로 나누어 얻는 팔분 공간 하나에 해당한다. 루트는 전체 부피를 덮고, 한 단계 내려갈 때마다 셀 크기가 반으로 줄어든다. 가지는 측정된 표면 점처럼 관심 있는 무언가가 있는 곳에서만 세분되므로, 넓은 빈 영역이나 관측되지 않은 영역은 하나의 거친 노드로 남는다. 옥트리는 1980년대 초 Donald Meagher가 솔리드 모델링을 위해 기술했으며, 지금은 그래픽스, 점군 처리, 로봇 매핑에서 표준이다.

주된 매력은 메모리다. 큰 건물 전체에 걸친 세밀한 해상도의 조밀 복셀 격자는 모든 셀에 저장 공간이 필요한 반면, 옥트리의 저장 공간은 대략 관측된 표면적에 비례해 늘어난다. 또한 다중 해상도 접근을 제공한다. 계획기는 빠른 확인을 위해 거친 셀을 질의하고 세부가 필요하면 아래로 내려갈 수 있다. Hornung과 동료들이 만든 널리 쓰이는 라이브러리 OctoMap에서는 각 리프가 거리 측정으로 갱신되는 로그 오즈 형태의 확률적 점유 값을 가지므로, 지도가 점유, 자유, 미지 공간을 구별한다. 상태가 같은 자식들은 메모리를 아끼기 위해 부모로 다시 병합된다.

옥트리는 이런 압축성을 위해 속도를 일부 희생한다. 리프에 도달하려면 트리를 따라 내려가야 하는데, 이는 평면 배열을 인덱싱하는 것보다 느리다. 복셀 해싱과 VDB 구조 같은 대안은 일부 작업에서 더 빠른 접근을 제공한다. 옥트리는 점군에서 최근접 이웃 탐색과 충돌 검사를 가속하는 데에도 쓰이며, 최근의 신경 매핑 시스템에서는 학습된 특징을 저장하는 희소 복셀을 조직하고 새 깊이 프레임이 들어올 때마다 점진적으로 자란다.

중요한 이유

로봇에게는 메모리를 다 쓰지 않으면서 유용한 해상도로 넓은 영역을 덮는 3D 지도가 필요하다. 옥트리는 이를 실용적으로 만들며, 매니퓰레이션과 항공 내비게이션에 쓰이는 흔한 점유 매핑 및 충돌 검사 도구의 기반이다.

주요 응용

• OctoMap을 이용한 확률적 3D 점유 매핑
• 로봇 암과 드론을 위한 충돌 검사
• 점군에서의 최근접 이웃 및 반경 탐색
• 신경 암시적 매핑과 조밀 매핑을 위한 희소 복셀 구조
• 점군 압축과 상세도 수준(level-of-detail) 렌더링

실제 사례

창고 안을 비행하는 드론을 위한 3D 지도를 만드는 팀은 깊이 카메라나 LiDAR 점군을 오도메트리에서 얻은 자세와 함께 몇 센티미터 해상도의 OctoMap에 입력한다. 각 광선은 지나가는 셀을 자유일 가능성이 더 높다고, 끝의 셀을 점유일 가능성이 더 높다고 표시한다. 계획기는 후보 경로를 따라 옥트리의 점유를 질의하며, 미지 공간은 장애물로 취급한다. 로봇 암에서는 MoveIt이 깊이 센서로부터 같은 종류의 옥트리를 받아 팔의 계획 장면을 최신 상태로 유지할 수 있다. 엔지니어는 해상도, 센서 범위, 적중 및 빗나감 확률을 튜닝하여 세부, 메모리, 그리고 움직이는 물체가 얼마나 빨리 지워지는지 사이의 균형을 맞춘다.

흔한 오해

• 옥트리는 복셀 격자와 같다 — 복셀 격자는 모든 셀을 저장하는 반면, 옥트리는 필요한 곳만 세분하고 균일한 영역은 병합한다
• 옥트리는 항상 평면 격자보다 빠르다 — 메모리는 절약하지만 조회할 때마다 트리를 따라 내려가므로, 일부 질의에서는 조밀 격자나 해시 격자가 더 빠를 수 있다
• 옥트리의 빈 공간은 자유 공간을 뜻한다 — 점유 옥트리에서 관측되지 않은 공간은 미지이며, 계획기는 보통 이를 자유 공간과 다르게 다루어야 한다

알아야 할 사람

• 매핑 및 SLAM 엔지니어
• 모션 계획 및 충돌 검사 개발자
• 3D 환경에서 작업하는 드론 자율 비행 엔지니어
• 신경 및 조밀 매핑 시스템 개발자

관련 기술

• OctoMap
• 복셀 해싱(Voxel Hashing)
• OpenVDB
• Point Cloud Library(PCL)
• MoveIt

관련 용어

• Point Cloud
• SLAM
• Signed Distance Field
• Neural Implicit Representation
• LIDAR
• Depth Camera

관련 프로젝트

• LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
• Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
• OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
• RTAB-Map: Versatile graph-based SLAM supporting RGB-D, stereo, and LiDAR with real-time operation
• LeGO-LOAM: Classic lightweight, ground-optimized lidar odometry and mapping baseline (IROS 2018)
• GLIM: GPU-accelerated 3D lidar SLAM framework for any range sensor, from AIST

동영상

• Using Octrees and A* for Efficient Pathfinding: git-amend

위키백과

• 팔진트리