[논문 리뷰] STD: Stable Triangle Descriptor for 3D place recognition

[2023,ICRA] STD: Stable Triangle Descriptor for 3D place recognition 논문 리뷰

Introduction

efficient LiDAR-based place recognition solution은 다음과 같은 요구사항을 만족해야한다.

• Rotation and Translation invariance
• solution should better provide relative pose
• LiDAR point cloud density나 환경에 robust해야 한다.(point cloud의 sparsity가 거리, scene, LiDAR 종류에 따라 바뀌기 때문에)

이러한 요구사항을 만족하기 위해, 본 논문에서는 stable triangle descriptor(STD)라는 new descriptor를 개발했다.

triangle로 임의의 three key points를 encoding 한다.

polygon을 사용하는 다른 descriptor들과 달리 triangle을 사용하게 되면 더 안정적이다.

이유는, triangle의 특성상 변의 길이가 uniquely하게 결정되기 때문이다.(각도 또한 마찬가지)

Key point 주변의 local descriptor와 비교할 때도 triangle의 모양은 completely rotation and translation invariance하다.

Triangle descriptor를 위한 key point들을 추출하기 위해, plane에 point cloud를 projection하고, boundary에서 key point를 추출한 다음, key point를 triangle로 형성한다고 한다.

Matching은 triangle의 similarity에 기반한다고 한다.

본 논문에서 주장하는 기여는 다음과 같다.

• Design a triangle descriptor, 삼각형 변의 길이와 각 삼각형 꼭짓점에 붙어 있는 인접한 평면의 법선벡터들 사이의 각도로 구성된 six-dim vector이다. completely invariant to rotation and translation.

• Fast key point extraction method

• Evaluate under multiple types of scenarios and different LiDAR data(Spinning and Solid-state)

Methodology

Stable Triangle Descriptor

Keyframe에서 loop detection을 수행, keyframe은 축적된 포인트들을 가지고 있기 때문에, 특정 LiDAR scan 패턴과 관계없이 증가된 point cloud density를 가진다.

point cloud의 keyframe이 주어지면,

첫 번째로, region growing에 따른 plane detection을 수행한다.

구체적으로, 전체 point cloud를 voxel들로 나눈다.

각 voxel은 point 그룹들을 포함하고 있으며, 이들의 covariance matrix를 아래와 같은 식을 통해 계산한다.

k-th largest eigenvalue를 활용하여 plane detection의 criterion을 다음과 같이 설정했다고 한다.
($\sigma_{1}$, $\sigma_{2}$ 는 pre-set hyperparameters)

이러한 criterion에 따라, voxel내의 점들이 평면을 형성하는지 확인할 수 있으며,

이러한 voxel을 plane voxel이라고 한다.

이후 해당 평면을 키우기 위해 이웃하는 voxel을 찾고, 이웃 voxel이 평면인 경우(임계값 이하의 거리, 동일한 법선 방향)

성장 중인 평면에 추가한다고 한다.

이웃 voxel이 동일 평면이 아닌 경우, 성장 중인 평면의 boundary voxel 목록에 추가된다고 한다.

성장 과정은 추가된 이웃하는 voxel이 모두 확장되거나 boundary voxel에 도달할 때까지 반복된다.(아래 그림 참조)

(Plane voxel 관련 Reference : [2022, IEEE RA-L] Efficient and Probabilistic Adaptive Voxel Mapping for Accurate Online LiDAR Odometry)

그리고, boundary voxel을 활용하여, 이를 해당하는 plane에 투영한다.

각 평면에 대해 해당 평면과 일치하는 image plane을 생성하고 각 픽셀은 해당 plane의 boundary voxel에 포함된 점들의 최대 거리를 나타낸다.
(아래 그림)

이 다음, 5 by 5 이웃에서 가장 큰 픽셀 값이 있는 점을 선택하여 keypoint로 지정한다.

추출된 각 키포인트는 input point cloud의 3D 점에 해당하며, 추출된 해당 평면의 법선과 연결될 수 있다.

Triangle descriptor를 구성하기 위해, keyframe에서 추출된 key point와 함께 k-D Tree를 구성하고, 각 점으로부터 20 near neighbor points를 search한다.

같은 변 길이의 중복되는 descriptor는 제거된다.

각 triangle descritor는 세 개의 정점인 $p_{1}$, $p_{2}$, $p_{3}$ 와 해당하는 projection normal vector인 $n_1$, $n_2$, $n_3$가 있다.

삼각형의 꼭짓점은 변의 길이 규칙에 따라 오름차순으로 배열되어 있다.

triangle descriptor $\Delta$는 다음과 같은 항목을 가진다.

descriptor에 추가로, keyframe에서 추출한 n개의 평면들 또한 geometrical verification step을 위해 저장한다고 한다.

(이 그림을 보면서 이해했다.)

Search of Loop Candidates

keyframe으로부터, 수백개의 descriptor가 추출되었고, 이를 빠르게 query하고 descriptor를 matching하기 위해 모든 descriptor를 저장하는데 Hash table을 사용한다.

hash key를 계산하기 위해 descriptor에서 rotation and translation invariance한 6개의 속성을 이용한다.

6개의 속성은 3개의 변과 normal vector들의 내적 3개이다.

속성이 비슷한 descriptor는 동일한 hash key를 가지게 되어, 동일한 컨테이너에 저장된다.

이제, query한 keyframe에서 ## Stable Triangle Descriptor에서 설명한대로 모든 descriptor를 추출하고 각 descriptor에 대해 hask key를 계산한다.

그리고 각 descriptor의 hask key에 해당하는 hash table container로 이동하여 이 컨테이너에 속한 descriptor를 가진 keyframe에 한 번씩 투표한다.

모든 query keyframe의 임의의 descriptor가 처리될 때 까지 voting을 수행한다.

voting에서 상위 10개에 든 keyframe은 후보가 되어 실제 detection에서 사용된다.

Loop Detection

이제 loop candidate keyframe이 주어졌을 때, 본 논문에서는 geometrical verification을 수행한다.

geometrical verification은 부정확한 descriptor matching 쌍으로 인한 잘못된 detection을 제거하기 위함이다.

triangle의 변의 길이가 결정된 후에 triangle의 모양이 uniquely하게 결정되기 때문에,

triangle descriptor $\Delta_a$와 $\Delta_b$가 매칭되었을 때,

이 둘의 정점(각각의 $p_{1}$, $p_{2}$, $p_{3}$)의 대응을 알게 되었고, SVD를 활용해 두 keyframe간의 relative transformation $T=(R,t)$를 쉽게 계산할 수 있다.

robustness를 증가시키기 위해, RANSAC도 사용했다고 한다.

이렇게 계산한 transformation에 기반해,

geometrical verification을 위해 현재 frame과 후보 frame간의 plane overlap을 계산한다고 한다.

중심점 $g$와 normal vector $u$가 voxel의 plane $\pi$를 나타낸다고 하자.

Plane group of current group은 $^{B} \Pi = (^{B} g_{1}, ^{B} u_{1}),…,(^{B} g_{n}, ^{B} u_{n})$

Plane group of candidate group은 $^{C} \Pi = (^{C} g_{1}, ^{C} u_{1}),…,(^{C} g_{m}, ^{C} u_{m})$

$(^{C} g_{1}, ^{C} g_{2},…,^{C} g_{m}) \in \ ^{C} \Pi$ 를 k-D tree로 구성하고(k=3)

$(^{B} g_{1}, ^{B} g_{2},…,^{B} g_{n}) \in \ ^{B} \Pi$ 를 얻은 transformation을 통해 transform을 수행한다.

그리고 변환한 점과 k-D tree에서 가장 가까운 포인트 $^{C} g_{j}$ 를 search하고, 이 점의 두 평면이 일치하는지를 확인한다.

일치 여부는 normal vector의 차이와 point-to-plane 거리를 통해 확인한다.

($\sigma_{n}$, $\sigma_{d}$ 는 pre-set hyperparameters)

pair에서 식(4)가 만족되면, 두 평면은 일치한다.

current frame과 모든 평면을 확인한 후, 평면 일치율에 대한 백분율을 계산한다.

이 백분율이 특정 threshold를 초과하면 valid loop detection으로 간주한다.

geometric verification based on planes 방법이 ICP-based 방법들보다 훨씬 효율적이라 한다.
(point cloud 수보다 plane수가 훨씬 적기 때문에)

또한, 위에서 계산한 normal vector difference와 point-to-plane 거리를 추가로 최적화할 수도 있다고 한다.

Experiments

생략, SOTA

참고자료

Yuan, Chongjian, et al. “Std: Stable triangle descriptor for 3d place recognition.” 2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2023.

Yuan, Chongjian, et al. “Efficient and probabilistic adaptive voxel mapping for accurate online lidar odometry.” IEEE Robotics and Automation Letters 7.3 (2022): 8518-8525.

📣
포스팅에서 오류나 궁금한 점은 Comments를 작성해 주시면, 많은 도움이 됩니다.💡