We present a novel approach, Super Ray, for efficiently updating point clouds to occupancy map representations such as grids and octrees. In this paper, we define a super ray for points as a representative ray to them with an associated frustum. A super ray is constructed in a way that updating those points has the same set of cells accessed during the map update process. As a result, we can perform the update process with a super ray in a single traversal on the map, resulting in performance improvement without compromising any accuracy of the map. For constructing super rays efficiently, we propose mapping lines for handling 2-D and 3-D cases from an observation that edges or grid points branch out the access pattern of updating the map. Our method is general enough to be applied for variety of occupancy map structures based on axis-aligned space subdivisions such as grid and octrees. We test our method into indoor and outdoor benchmarks, and achieve 2.5 times on average (up to 3.5 times) performance improvement over the state-of-the-art update method for OctoMap and grid maps.
로봇은 주변 환경을 인지하고 그에 반응하기 위해 다양한 센서를 사용한다. Point clouds는 주변 환경을 점으로 표현하는 센서 데이터로 주변 환경의 기하학적 정보를 제공한다. 하지만 이 데이터는 센서 노이즈가 섞인 많은 수의 점으로 이루어져있기 때문에, 이를 모션 플래닝이나 충돌 탐지와 같은 응용분야에서 직접적으로 사용하기 어렵다. 따라서 Point clouds를 효율적으로 사용하기 위해, grid 또는 octree 기반의 점유맵이 제안되었다. 이를 통해 다양한 응용분야에서 성능 향상을 이루었지만, 점유맵을 생성하고 업데이트하는 과정에 많은 시간을 필요로 한다.
본 연구는 최신 업데이트 알고리즘을 개선하여, 점유맵의 표현 정확도를 잃지 않으며 업데이트 속도를 향상시키는 기법을 제안하였다. 본 알고리즘은 점유맵에서 같은 공간을 업데이트하는 point를 묶음으로써, 점유맵을 동시에 업데이트할 수 있는 새로운 개념인 super ray를 정의하였다. Point clouds를 점유맵에서 업데이트하지 않고, super ray를 점유맵에 업데이트함으로써 업데이트 속도를 향상시킬 수 있다. 본 연구에서 제안한 알고리즘은 매 프레임마다 센서로부터 얻은 Point clouds에서 super ray를 생성하기 위해, 점유맵의 같은 공간을 업데이트하는 point가 존재할 수 있는 영역을 정의한다. 본 연구는 격자점에 의해 point가 점유맵을 업데이트하는 영역을 접근하는 패턴이 달라진다는 사실을 바탕으로, Point clouds로부터 super ray를 효율적으로 생성하기 위한 새로운 개념인 mapping line을 제안한다. 모든 point를 mapping line에 영사시킴으로써, 점유맵의 같은 공간을 업데이트하는 point끼리 묶고, 이를 대표하는 하나의 point를 super ray로 선정한다. super ray로 묶여진 point들이 제공하던 점유 정보를 잃어버리지 않으며 공간의 점유 확률을 업데이트하기 위해, super ray가 업데이트하는 점유 확률에 묶여진 point의 개수만큼 가중치를 주어 업데이트한다. 본 연구는 상대적으로 해결하기 쉬운 2차원에서 개념을 확립하고, 이를 해결하기 어려운 3차원으로 확장함으로써, 2차원과 3차원에서 모두 사용이 가능함을 보여주었다.
본 논문에서 제안한 방법은 Point clouds이 업데이트하는 점유맵의 공간에 접근하는 수를 줄임으로써, 기존 방식을 통해 생성된 점유맵의 표현 정확도를 잃지 않으며 평균 2.5배 (최대 3.5배) 업데이트 속도를 향상 시켰다. 본 연구의 우수성을 증명하기 위해 범용적으로 사용되는 데이터 셋과 다양한 조건에서의 실험을 통해 제안한 방법의 우수성을 증명하였다. 본 연구는 점유맵의 표현 정확도를 잃지 않기 때문에 점유맵을 사용하는 응용분야에 적용이 가능하며, 향상된 업데이트 속도는 응용 분야의 성능을 향상시킬 수 있다.
