Curved-Voxel Clustering for Accurate Segmentation of 3D LiDAR Point Clouds with Real-Time Performance

본 문서에서는 IROS 2019에서 발표된 Curved-Voxel Clustering for Accurate Segmentation of 3D LiDAR Point Clouds with Real-Time Performance 논문을 소개합니다. 논문에 대한 상세 정보는 다음과 같습니다.

• Title: Curved-Voxel Clustering for Accurate Segmentation of 3D LiDAR Point Clouds with Real-Time Performance [link]
• Authors: Seungcheol Park, Shuyu Wang, Hunjung Lim, and U Kang
• Conference: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2019

Segmentation of 3D LiDAR Point Clouds

3차원 라이다 센서 (3D LiDAR sensor)란 빛을 이용하여 주변 물체까지의 거리를 측정하여 센서 주변에 있는 물체들에 대한 위치 정보를 전달해주는 장치입니다. 라이다 센서는 실내에서 사용되는 안내 로봇부터 자율주행 차량까지 다양한 분야에서 사용되고 있습니다. 이때, 라이다 센서는 주로 주변에 물체가 있는지 없는지를 인식 (detection)하거나, 물체가 있다면 어떤 물체인지를 식별 (classification)하는 일을 주로 하게 됩니다. 특히 실내외에서 사람을 인식하는 보행자 식별 (pedestrian classification) 과정은 안전을 위해서도 중요하기 때문에 활발하게 연구되고 있는 분야입니다.

그림 1. 라이다 센서를 이용한 보행자 식별 과정의 예시

그림 1은 현관에 설치된 라이다 센서를 통해 보행자를 인식하는 예시를 보여주고 있습니다. 라이다 센서가 인식한 점 정보 (Input Data)를 전달받은 후 다음과 같은 네 단계를 통해 보행자 인식이 이루어 집니다. 

1. 관심 영역 필터링 (ROI filtering): 우리가 관심을 가지는 영역 (range of interetst, ROI)에 해당하지 않는 정보들을 제거해줍니다. 본 예시에서는 현관에 라이다 센서가 있다는 사실을 알고있기 때문에, 고정되어 있는 문, 기둥에 대한 점들을 제거해준 것을 확인할 수 있습니다.
2. 지면 제거 (ground removal): 보행자 인식에 관계없는 지면 정보를 제거해 줍니다. 가장 기본적인 방법은 라이다의 높이를 고려하여 일정 높이 이하의 점 정보를 제거해주는 것입니다.
3. 분할 (segmentation): 다음으로 식별과정을 하기 위한 전 단계로서 각 물체별로 점들을 구분해줍니다. 그림을 보면 두 명의 사람이 각각 다른 색들로 표현되어 구분되어 있는 것을 알 수 있습니다. 이때, 일정 거리 내에 있는 가까운 점들을 묶어주는 군집화 (clustering) 방법이 주로 사용됩니다.
4. 식별 (classification): 마지막으로 분할된 각 물체별로 어떤 물체인지를 식별하게 되고, 그 결과 두 명의 사람이 있음을 알 수 있게 됩니다.

본 논문에서는 위 네 가지 단계 중 세 번째 단계인 분할 단계를 정확하고 효율적으로 하는 방법에 대한 연구를 진행하였습니다. 정확한 분할 단계는 보행자 식별률에 직접적으로 영향을 주기 때문에, 보행자의 안전에 있어서 필수적인 요소 이며, 보행자를 빠르게 인지하고 반응하기 위해서는 빠른 분할 기술 또한 필수적입니다. 그렇다면 어떻게 하면 이 분할 과정을 정확하고 빠르게 할 수 있을까요? 이어지는 절에서는 정확한 분할을 위해 분할 알고리즘 (segmentation algorithm)이 만족해야 하는 조건에 대해서 살펴보도록 하겠습니다.

Desired Properties for Segmenting 3D LiDAR Point Clouds

분할 알고리즘의 목표는 주어진 점 정보들을 각 물체별로 올바르게 묶어주어서 식별과정을 진행할 수 있도록 전달하는 것입니다. 본 글에서는 하나의 물체로 묶인 점들을 같은 색으로 표현하였는데, 좋은 분할 알고리즘은 하나의 물체를 하나의 색으로 잘 묶고, 서로 다른 물체는 구분하여 다른 색으로 잘 묶어주는 것을 의미합니다. 이는 그림 2를 보시면 쉽게 이해하실 수 있습니다. 총 5명으로 이루어진 데이터를 (a)는 정확히 5명으로 분할하였지만, (b)는 가까운 거리의 사람들을 구분하지 못하고 총 3개의 점 묶음으로 분할한 것을 알 수 있습니다. (b)와 같은 분할 결과를 이용하여 식별 과정을 거치게 되면, 보행자가 아닌 다른 큰 물체로 인식하여 문제가 생길 수 있기 때문에, (a)와 같은 정확한 분할 과정은 안전을 위해서도 필수적입니다.

그림 2. 분할이 잘 된 결과 (a)와 분할지 잘 되지 않는 결과 (b)

본 논문에서는 점 정보들을 정확하게 분할 하기 위해 분할 알고리즘이 만족해야하는 세 가지 조건들을 제시하였습니다. 이에 대해서 아래 그림 3의 예시들을 통해 알아보도록 하겠습니다.

그림 3. 정확한 분할을 위해 분할 알고리즘이 만족해야 하는 세 가지 조건들

우선, 그림 3은 본 논문에서 제시한 세 가지 조건들 (1열)과 각각의 조건들을 만족해야하는 상황의 예시들 (2열), 그 상황에서 알고리즘의 동작 방식 예시들 (3열)과 실제로 세 가지 조건을 만족하지 못하는 분할 알고리즘 (RBNN)의 분할 결과와 세 가지 조건을 만족하는 분할 알고리즘 (CVC)의 분할 결과의 비교(4열)를 나타내고 있습니다. 본 논문에서는 일정 영역 내에 있는 점들을 모두 하나의 물체로 묶어주는 군집화 알고리즘 (clustering algorithm)을 기준으로 하여 설명하였으며, 3열의 붉은 색 점선은 RBNN의 군집화 기준 영역을, 파란색 점선은 CVC의 군집화 기준 영역을 의미합니다. 이때, RBNN은 기존 연구에서 주로 사용되던 군집화 방법으로, 거리에 관계없이 일정 거리 내에 있는 모든 점들을 묶어주는 알고리즘입니다. 저자가 제시한 세 가지 조건들은 아래와 같습니다. 아래의 내용들을 그림 3과 함께 비교하며 보시면 이해하기에 조금 더 편할 것 같습니다.

1. 센서로부터의 거리에 따라 다른 크기를 가질 수 있어야 한다 (distance from sensor).
   : 라이다 센서는 센서로부터 방사상으로 빛을 방출하기 때문에, 거리가 멀어질 수록 가장 가까운 두 점 사이의 간격 또한 멀어지게 됩니다. 정확한 분할을 위해서는 센서로부터의 거리에 따라 물체를 분할하는 기준을 달리 해줄 수 있어야 합니다. 이 기준을 만족하지 못하면 먼 거리에 있는 한 사람을 여러 색으로 구분하여 인식하게 됩니다.
2. 수직, 수평 방향으로 다른 크기를 가질 수 있어야 한다 (directional resolution).
   : 라이다 센서는 수직, 수평 방향의 해상도 차이가 매우 큽니다. 그림 3의 예시들만 보더라도 수평 방향으로는 점들이 빼곡하지만, 수직 방향으로는 점들 사이의 거리가 먼 것을 알 수 있습니다. 그렇기 때문에 수직 방향의 점들을 묶어주기 위해서는 상당히 먼 거리의 점들을 묶어주어야 하는데, 이러한 기준을 수평 방향에도 똑같이 적용해준다면 가까운 거리에 있는 두 사람을 제대로 구분할 수 없습니다. 그러므로 수직, 수평 방향으로 각각 독립적인 기준을 가질 수 있어야 합니다.
3. 방사상으로도 독립적인 크기를 가질 수 있어야 한다. (rarity of points).: 물체가 기울기를 가지는 경우, 상하 거리 뿐만 아니라, 방사상으로도 거리가 생겨 한 물체에서 나온 점들이라 하더라도 두 점 사이의 거리가 더욱 멀어질 수 있습니다. 조건 3의 예시를 보면 걷는 사람의 뒷 다리의 경우 가만히 서있었다면 하나의 군집으로 묶일 수 있었겠지만, 기울기가 생기는 바람에 붉은 색 영역에 점들이 포함되지 못하는 것을 알 수 있습니다. 이러한 경우 뒷 다리 부분을 같은 물체로 인식을 하지 못해서 다른 색으로 나타낼 수 있음을 알 수 있습니다. 이를 방지하기 위해 방사상으로도 독립적인 크기를 가질 수 있어야 합니다.

그림 3의 4열을 보시면, 세 가지 모든 조건을 만족하는 CVC의 경우에만 먼 거리의 사람, 가까운 거리의 두 사람, 걷고 있는 사람의 모든 경우에 대해 올바르게 분할하고 있음을 알 수 있습니다.

Proposed Method

이번 절에서는 앞서 말씀드린 세 가지 조건을 모두 만족하면서도 빠른 속도로 분할을 할 수 있는 알고리즘인 Curved-Voxel Clustering (CVC)에 대해 설명해드리겠습니다. CVC는 3차원 공간을 Curved-Voxel이라는 새로운 형태의 단위로 분할한 후에, 이웃한 Curved-Voxel 속에 들어있는 점들을 하나의 물체로 묶어주는 알고리즘입니다. 이 때 Cruved-Voxel은 3차원 구면 좌표계의 세 축 방향으로 일정한 범위를 가지는 공간 단위인데, 아래 그림 4와 같이 나타낼 수 있습니다.

그림 4. Curved-Voxel의 투시도 (a)와 평면도 (b)

Curved-Voxel은 라이다를 중심으로 공간을 분할하기 때문에, 이를 이용하는 분할 알고리즘은 정확한 분할을 위한 세 가지 조건을 다음과 같이 모두 만족하는 것을 알 수 있습니다.

• 조건 1: Curved-Voxel은 방사상으로 뻗는 형태를 가지기 때문에, 라이다로부터 멀어질 수록 크기가 커지는 특징이 있어 거리가 먼 사람도 정확하게 분할 할 수 있습니다.
• 조건 2: Curved-voxel은 수평, 수직 방향으로 각각 독립적인 크기 기준을 가지고 있어 라이다의 해상도에 맞게 이를 조절할 수 있습니다.
• 조건 3: Curved-Voxel은 방사상으로의 길이를 독립적으로 조절할 수 있어 기울어진 물체도 제대로 분할할 수 있습니다.

CVC에서는 이러한 Curved-Voxel을 효율적으로 활용하기 위하여 해쉬 테이블 (hash table)을 사용합니다. 각각의 Curved-Voxel을 원점을 기준으로 그 순서에 따라 번호를 부여하면, 한 점이 어떤 Curved-Voxel에 있는지는 바로 알 수 있지만, 반대로 한 Curved-Voxel 속에 어떤 점들이 있는지를 알려면 모든 점들을 확인해봐야해서 시간이 매우 오래 걸리게 됩니다. 그러므로 이에 대해 각각의 Curved-Voxel 속에 어떤 점들이 들어있는지에 대한 정보를 미리 해쉬 테이블 형태로 저장해 둠으로써 전체적인 시간 소모를 크게 줄일 수 있습니다.

Experimental Results

 지금까지 CVC가 Curved-Voxel을 활용하여 라이다 센서로부터 얻은 점 정보를 정확하게 분할할 수 있는 알고리즘이며, 해쉬 테이블을 이용해서 효율적으로 분할을 진행한다는 것을 알 수 있었습니다. 본 절에서는 대표적인 분할 알고리즘들인 RBNN, DBSCAN, 그리고 Cluster-all 알고리즘들과 CVC의 실험 결과를 비교하여 실제로 CVC가 다른 알고리즘들에 비해 빠르고 정확한 알고리즘인지를 알아보도록 하겠습니다.

그림 5. 인조 데이터에 대한 분할 알고리즘들의 속도 비교 결과

그림 5은 인조 데이터 (synthetic data)에 대한 거리별 분할 속도를 나타내고 있습니다. 본 실험에서는 다양한 거리에서 5000개의 점을 얼마나 빠르게 분할하는지를 비교해보았습니다. 저희가 제안한 알고리즘인 CVC는 파란색 동그라미로 나타나있는데, 5m 이내의 가까운 거리에서는 Cluster-all 알고리즘에 비해 느린 속도를 보였지만, 그 이후로는 모든 알고리즘들 중 가장 빠른 속도를 보이고 있는 것을 알 수 있습니다. 이는 거리에 따라 Curved-Voxel의 크기가 달라지는데, 가까운 거리에서는 크기가 매우 작아 많은 Curved-Voxel에 대해 연산을 해야하기 때문이며, 거리가 조금만 멀어져도 가장 빠른 것을 알 수 있습니다. 그리고, 모든 거리에서 초당 20회 이상의 분할을 실시한 것을 확인할 수 있는데, 라이다 센서가 초당 10개의 프레임 (frame)을 반환하는 것을 고려하였을 때 매우 빠른 속도로 분할이 가능한 것을 알 수 있습니다.

그림 6. 실제 데이터에 대한 분할 알고리즘들의 속도 비교 결과

그림 6는 실제 데이터 (real-world data)에 대한 분할 속도를 나타내고 있습니다. 이때, 가로 축에 있는 L-CAS 1, 2, 3, HALL, 그리고 OFFICE는 각각 데이터 셋들의 이름을 나타냅니다. 실험 결과 실제 데이터에 대해서는 모든 데이터 셋에 대해서 CVC가 가장 빠른 분할 속도를 보였으며, 두 번째로 빠른 분할 알고리즘에 비해 약 1.7배 더 빠른 분할 속도를 보이는 것을 알 수 있습니다. 실제 데이터의 경우 다양한 거리들이 혼재되어 있고, 5m보다 먼 거리의 데이터가 더욱 많기 때문에 이러한 결과를 보인 것을 알 수 있습니다.
 위 두 가지 실험 결과를 통해 우리는 해쉬 테이블을 활용한 CVC 알고리즘이 인조 데이터 및 현실 데이터 모두에서 빠르게 분할 과정을 진행한다는 것을 알 수 있었습니다. 이어지는 마지막 실험에서는 CVC의 정확도에 대해서 알아보도록 하겠습니다.

그림 7. 실제 데이터에 대한 분할 알고리즘들의 정확도 비교 결과

그림 7는 실제 데이터에 대한 분할 알고리즘의 정확도를 나타내고 있습니다. 보행자 데이터에 대한 분석의 경우 두 명 이상이 가까운 거리에 있는 경우 이들을 구분하는 것이 어렵기 때문에, 한 명만 있는 경우 (pedestrian)와 두 명 이상이 가까운 거리에 있는 경우 (group) 를 나누어 분석하였습니다. 본 논문에서는 총 100개의 단일 보행자 데이터와 50개의 그룹 데이터를 이용하여 실험을 진행하였습니다. 실험 결과 대부분의 알고리즘에서 단일 보행자에 대해서는 높은 정확도를 보였으며, 이 중 CVC가 100%의 정확도로 가장 높은 정확도를 보였습니다. 다음으로 두 명이상의 보행자가 있는 경우에는 CVC만이 50%를 넘는 정확도를 보였으며 다른 알고리즘들에 비해 30%이상 높은 정확도를 보인 것을 알 수 있습니다. 이를 통해 CVC가 실제 데이터에 대해 정확한 분할을 진행할 수 있으며, 본 논문에서 제시한 정확한 분할을 위해 만족해야하는 세 가지 조건들도 모두 유의미 했음을 알 수 있습니다.

Conclusion

본 문서에서는 IROS 2019에서 발표했던 "Curved-Voxel Clustering for Accurate Segmentation of 3D LiDAR Point Clouds with Real-Time Performance"에 대해 소개하였습니다. 해당 논문은 3차원 라이다 센서로부터 얻은 점 정보를 빠르고 정확하게 분할할 수 있는 기법인 CVC을 제안하였고, 실험 결과를 통해 인조 데이터 및 실제 데이터에 대해 다른 기법보다 빠르고, 정확하다는 것을 검증하였습니다. CVC는 LiDAR 센서를 사용하는 모든 분야에서 활용될 수 있으며, 대표적인 예로는 자율 주행 자동차에서 매우 중요한 문제인, 물체 식별 (object classification), 보행자 식별 (pedestrian classification), 그리고 물체 추적 (object tracking)등의 문제 해결에도 도움이 될 수 있습니다. 또한 실험을 통해 실제 데이터 상에서 사람을 더욱 잘 찾아낼 수 있는 것을 검증하였기 때문에, 자율주행차 혹은 실내에서 사용되는 로봇의 안정성을 향상시키는데 큰 도움이 될 것으로 보입니다. 본 논문에 조금 더 알아보고 싶으신 분들은 (링크)를 통해 논문 전문을 확인하실 수 있습니다.