[논문 리뷰] Scan Context: Egocentric Spatial Descriptor for Place Recognition within 3D Point Cloud Map

KAIST 학생분들이 쓰신 논문이네요! Scan Context라는 Spatial Descriptor 개념을 제시한 논문인데, 간단히 요약하자면 어떤 위치에서 관측된 point cloud의 특징을 요약할 수 있는 descriptor를 제작해 LiDAR 기반 SLAM에서의 loop closure detection 또는 global localization등에 응용할 수 있도록 제안한 연구입니다. 비유를 해 보자면, 2D 이미지에서 특징점을 뽑은 다음에 각각의 특징점들을 ORB나 SURF등의 descriptor들을 사용해서 벡터로 encoding을 해 놓는 것처럼 어떤 특정한 위치에서의 point cloud data를 알아볼 수 있는, 말하자면 "요약본"을 제시한 것이라고 할 수 있겠습니다. 임의의 포인트 클라우드에 대해서 이 descriptor를 계산할 수 있고, 서로 다른 descriptor를 비교해 어느 정도의 유사도가 확인된다면 이 둘은 비슷한 장소에서 관측한 point cloud 구나~ 라고 할 수 있다는 것입니다. 이렇게 대강의 유사도를 확인한 다음부터는 icp나 NDT등의 알고리즘을 사용해서 alignment를 통해 localization을 해 나갈 수도 있겠죠??

 

다른 글에서 간략하게 설명한 적이 있는데, point cloud라는 데이터를 다룰 때 주의해야 할 점으로는 이게 기본적으로 정렬되지 않은, 즉 순서가 없는 데이터라는 사실과 변환 불변성, 즉 다른 방향에서 보았다고 해서 같은 데이터를 다른 데이터로 인식해서는 안 된다는 것 등이 있습니다. 하나의 point cloud를 묘사(요약)하는 descriptor는 이런 조건을 꼭 만족시켜야 합니다(추가적으로 noise에 대한 강건성도 당연히 중요하겠죠??). 당연히 Scan Context에도 이러한 사항들이 고려되어 있습니다.

 

위의 그림이 Scan Context를 통해 point cloud를 묘사하는 과정입니다. 일단은 왼쪽 그림과 같이 point cloud data가 존재하는 공간을 LiDAR의 위치를 원점으로 하는 cylindrical coordinate로 나타내고, 이 좌표계를 기준으로 공간을 복셀화(voxelize)합니다. 보통은 복셀화를 한다고 하면 Cartesian 좌표계를 기준으로 정육면체 모양의 복셀들로 공간을 나누는 것이 보통인데, 여기서는 원통 좌표계를 사용해서 복셀화를 합니다. 여기서 각 복셀에는 point가 없을 수도 있고, 한 개 있을 수도 있고, 여러개 있을 수도 있겠죠? 각 복셀에 들어갈 값으로는 "각 복셀 내부의 가장 높은 point의 z좌표" 를 선택합니다. 이제 이걸 $ \mathit{N_{r}}\times\mathit{N_{s}} $크기의 matrix(오른쪽 그림)으로 나타냅니다. 저는 처음에는 뭐가 어디로 들어간 건지 좀 헷갈렸는데, matrix의 한 요소에 대응되는 복셀은 다음과 같습니다. 

 

Point cloud가 2차원 이미지로 인코딩되었습니다! 이거에 더해서 약간의 위치 차이에 대한 인식 강건성을 확보하기 위해 포인트 클라우드를 사방으로(논문에서는 8가지 방향)으로 약간씩 shift하고 그 8가지에 대한 Scan Context들도 모두 구해 놓습니다. 

 

두 Scan Context 데이터 간의 거리는 각각의 column vector 사이의 코사인 거리의 합으로 정의됩니다. 하지만 당연하게도 포인트 클라우드를 획득한 위치가 비슷하더라도 rotation이 다르면 scan context의 생김새는 완전 다르기 때문에, 둘 중 하나를 골라서 한 칸씩 옆으로 shift시키며 모든 rotation 가능성(위 그림으로 치면 60개)에 대한 거리를 모두 구하고 그 중 최소값을 선택합니다. 이렇게 하면 위치가 비슷하고 방향이 다르더라도 두 데이터 사이의 거리가 정상적으로 구해집니다.

 

다음으로는 다수의 Scan Context를 비교하면서 search를 진행할 수 있도록 이 고차원 데이터를 요약하는 descriptor인 "Ring key"를 정의합니다. 이 descriptor는 rotation에 관계없이 같은 point cloud라면 같은 값을 지니기에 다수의 Scan Context 데이터들을 비교하기에 적절합니다. Ring key는 벡터 $ \mathbf{k} $로, 각 원소는 Scan Context의 각 row vector를 encoding function에 통과시킨 값입니다(벡터의 길이는 row의 길이가 되겠네요. 위의 그림으로 치면 20). Encoding function은 단순한 occupancy ratio로, 쉽게 말하면 row vector 중에 값이 존재하는 요소의 비율입니다(길이 10의 벡터에서 값이 3개만 존재한다면 ratio는 0.3). Scan context의 고차원 정보는 상당 부분 잃어버리지만 다량의 데이터를 빠르게 비교하기에는 좋아 보입니다.

 

예를 들어 보자면 10000개의 Scan Context 데이터가 있다면 Ring key를 비교해서 후보를 한 50개 정도로 줄이고, 그 50개 간의 거리는 직접 계산해서 가장 유사한 데이터를 선택하는 식으로 검색이 가능합니다. 물론 그 중에서도 같은 장소의 데이터가 없을 수 있기에 threshold를 설정할 필요가 있겠습니다.

 

Loop detection에 Scan Context를 적용한 결과

 

Scan Context를 이용해 대략의 initial guess를 구하고 이를 이용해 ICP를 진행한 결과

이후 다른 point cloud encoder들과의 비교와 응용 방안 등을 제시하였고, 조금 높은 computational complexity를 요구하지만 우수한 loop detection 성능을 보인다고 주장하였습니다.

 

 

---------- 개인적인 생각 ----------

 

Scan Context를 LiDAR 기반 SLAM 방법론인 LeGO-LOAM에 적용한 SC-LeGO-LOAM이라는 알고리즘이 있습니다. 아마 loop closure detection에 사용한 것이겠죠? 요것도 시간이 나면 한번 리뷰를..