[논문 리뷰] ORB-SLAM: a Versatile and Accurate Monocular SLAM System

💡 본 문서는 'ORB-SLAM: a Versatile and Accurate Monocular SLAM System'에 대해 정리해놓은 글입니다.
feature-based SLAM에 있어 기본이 되는 논문인 ORB-SLAM에 대해 정리하였으니 참고하시기 바랍니다.
참고: Raul Mur-Artal, J. M. M. Montiel, Juan D. Tardos. 『ORB-SLAM: a Versatile and Accurate Monocular SLAM System』. IEEE: transaction on robotics, 2015.​

Abstract

본 연구에서는 크고 작은 실내외 환경에서 실시간으로 작동하는 feature-based monocular SLAM system을 제안한다. 이 시스템은 심한 motion 잡음에도 견고하고, 광범위한 loop closing을 허용하며 완전한 자동 초기화를 포함한다.

최근 몇년간의 우수한 알고리즘을 바탕으로 tracking, mapping, relocalization, loop closing 등 모든 SLAM 작업에 동일한 기능을 사용하는 새로운 시스템을 처음부터 설계했다. 본 연구에서는 가장 인기있는 데이터셋의 27개의 sequence를 가지고 평가를 진행하였다. ORB-SLAM은 다른 SLAM에 비해 전례없는 성능을 달성한다.​

Overview

SLAM은 크게 Feature-Based SLAM과 Direct SLAM으로 나누어집니다. Feature-Based SLAM은 영상에서 특징점을 추출하여 SLAM을 적용하는 방식이고 Direct SLAM은 Pixel 정보를 그대로 SLAM에 적용하는 방식입니다. 이중 ORB-SLAM은 Feature-Based SLAM입니다.

Feature는 Image에 존재하는 Corner를 의미합니다. Corner를 검출하는 대표적인 방법은 Harris Corner, SIFT, SURF, FAST, ORB 등이 있습니다.

ORB-SLAM은 FAST-9를 이용해 특징점을 검출한 후 Intensity Centroid(→ Corner의 Pixel 값은 그 중심과 차이가 있고 그 벡터는 방향성을 만드는 데 사용된다는 이론)로 특징점의 방향(Orientation)을 계산합니다.

ORB SLAM 구조

ORB SLAM은 3개의 thread를 활용하기 때문에 속도가 굉장히 빠르다.

1. Tracking thread

• 지도에서 현재의 위치를 찾는다.
• 이를 위해 기존의 지도정보와 ORB feature를 활용하여 현재의 위치를 추정한다.

2. Local mapping

• 각각의 keyframe 정보를 지도의 mapping한다. (2d point -> 3d point)

3. Loop closing

• 영상정보를 통해 지도를 만들다보면 drift 현상이 발생한다. (위치가 어긋남)
• SLAM으로 만들어진 지도정보를 통해 현재의 위치를 교정해준다.

SolvePnP

Represent Camera motion

1. Translation

• 카메라가 3차원 공간에서 이동한 경우, 이동량을 translation이라고 한다.
• 3차원 점 (x,y,z)에서 (x',y',z')으로 이동한 경우, translation은 vector t = (x'-x, y'-y, z'-z)로 표현할 수 있다.​

2. Rotation

• 카메라가 x,y,z에서 회전한 경우

3. Pose estimation

• SovlePnP는 카메라의 이러한 Pose를 추정하는 것이다.
• 카메라가 고정되어 있을 때 물체의 pose를 추정한다.
• 물체가 고정되어 있다면 카메라의 pose를 추정한다.​

Pose estimation시 필요한 정보

1. 2d coordinates of a few points
   • 2차원 이미지 상의 점 (x,y)​
2. 3d locations of the same points
   • 2차원 이미지에 대응하는 3차원 상의 점 (x,y,z)
   • world coordinates라고도 불림
3. Intrinsic parameters of the camera
   • 초점 거리 (focal lenght of camera)
   • optical center in the image
   • radial distortion​
4. pose estimation을 표현하는 방법
   • 카메라의 pose(rotation, translation)을 알고 있다고 가정할 때, world coordinates의 점 P(U,V,W)를 다음 수식을 통해 camera coordinates의 점 (X,Y,Z)로 투영할 수 있다.
   • camera coordinates를 구한 후, camera coordinates로부터 image coordinates를 구할 수 있다.
   • 이를 활용하여 2D point(x,y), 3D point(U,V,W), camera intrinsic matrix(focal length, optical center)를 알 때 역으로 rotation과 translation을 예측할 수 있다.

 

SolvePnP

1. input

- objectPoints : world coordinate 상의 3차원 점들

- imagePoint : 3차원 점들에 대응하는 image상의 2차원 점들

- cameraMatrix : camera intrinsic parameter

- distCoeffs : camera distortion coefficients

2. output

- rotation vector (Rodrigues)

- translation vector​

3. Rodrigues란

- 위 식에서 rotation은 3*3 matrix로 표현된다.

- 이 3*3 매트릭스를 4개의 값(회전축 벡터 + 회전각)으로 표현하는 방법

ORB SLAM에서 SolvePnP사용

• SolvePnP는 Tracking 부분에서 initial pose estimation 단계에서 카메라 위치 추정을 위해 사용됨
• 영상에서 추출한 ORB feature를 기반으로 카메라 위치 추정
• 기존의 map 정보 (3d)와 Extract ORB로 얻은 특징점 (2D)정보를 가지고 이동한 값을 찾는다. (camera Intrinsic parameters는 이전의 이미 구해두었다고 가정)

 

Bag of Words

Bag of Words

문서를 자동으로 분류하는 방법 중 하나로, 문서 내의 단어의 빈도와 분포를 보고 어떤 종류의 문서인지 판단하는 기법

1. 등장하는 단어로부터 단어장을 생성해 출현 횟수 측정
2. 각 단어의 출현 빈도로부터 히스토그램 생성
3. 히스토그램으로부터 문서의 속성을 분류

영상처리에서의 Bag of Words

영상 feature(SIFT, BRIEF, ORB...)를 추출한 후, clustering을 거쳐 feature를 대표할 수 있는 코드 생성 및 코드를 모아놓은 코드북 생성

임의의 영상에서 feature를 추출한 후 clustering을 거친 결과를 codebook의 code와 비교해 히스토그램으로 표현해 이미지 분류 및 인식

ORB SLAM에서의 Bag of Words

영상에서 추출한 ORB feature로부터 code 및 codebook 생성하며, ORB SLAM을 이루는 3가지 시스템인 Tracking, Local Mapping, Loop Closing 전반에 걸쳐 사용한다.

1. Tracking

Traking과정에서 lost가 발생한 경우, 새로 들어오는 영상의 ORB feature를 이전에 생성된 keyframe의 map point로 구성된 bag of words와 비교하는 과정인 global relocalization을 거친다.

이후 충분히 유효한 값이 나오면 tracking을 이어서 실시한다.

2. Local Mapping

새로운 keyframe이 생성되는 경우 keyframe을 나타내는 bag of words를 계산해 새로운 map point의 triangulation의 계산을 돕는다.

3. Loop Closing

새로운 keyfream이 Local Mapping 과정에서 만들어진 keyframe의 bag of words 내의 값과 유사하다면 이전에 지나온 장소라고 판단해 Loop Closing이 일어날 수 있는 후보로 분류한다.

Bundle adjustment

Bundle adjustment(이하 BA)

BA는 *reprojection error를 최소화시키도록 3차원 포인트의 위치 및 카메라의 위치를 최적화하는 과정이다.

• reprojection error : 맵 상의 3차원 포인트들을 keyframe 이미지들에 projection시킨 위치와 해당 영상 프레임에서 실제 관측된 위치의 차이

Bundle adjustment flow chart

1. 영상에서 특징점을 검출하고 카메라 자세를 추정한다.
2. 특징점과 카메라 자세로 부터 3차원 점을 계산한다.
3. 카메라 자세와 3차원 점을 보정하기 위해 BA를 사용한다.

ORB SLAM에서의 Bundle Adjustment

1. Traking thread (Montion only BA)

카메라 포즈를 최적화한다. 3차원 점을(X) 2차원 점으로 투영시킨 후, 2차원 점(x)과의 차이가 최소화 되는 Rotation과 translation을 구한다.

2. Local mapping (Local BA)

Local map에 대한 키프레임과 맵 포인트를 최적화한다. 각각의 keyframe에 대해 위치를 보정해준다.

3. Loop closing (Full BA)

루프 클로징 이후 모든 키프레임과 맵 포인트를 최적화하며, 맵 생성시 누적된 오차를 수정한다. 수식은 Local BA식에서 모든 키프레임과 포인트로 확장한다.

 

1. Tracking thread

영상에서 특징점을 추출하여 *key freame을 생성하고, 카메라의 위치(camera pose)를 추정하는 과정

• key frame: 유의미한 특징점을 많이 가지는 frame (지도를 만드는데 사용될 중요한 정보를 담고있는 frame)​ 

1.1 Extract ORB

input 영상 전처리 과정으로 ORB Feature descriptor를 이용하여 영상 내 특징점 검출한다.

1.2 Pose Estimation or Relocalisation

카메라의 위치를 추정하는 단계로 Tracking이 잘되는지에 따라 다른 접근방법​을 가진다.

1.2.1 Tracking이 잘되는 경우

• 이전 frame을 통한 pose estimation
• constant velocity motion model을 사용하여 카메라 위치 추정 (등속도로 움직인다는 가정) -> guided search 수행 -> pose optimization

1.2.2 Tracking이 lost된 경우 (global relocalisation)

• back of words와 place recognition 모듈을 이용하여 global relocalization 수행 -> traking 회복
• solve PnP를 이용하여 카메라 위치 추정 -> guided search 수행 -> pose optimization

 

1.3 Track Local Map

더 많은 map point 대응쌍을 찾기 위해 local map을 frame에 투영시켜 pose optimization을 수행한다.

1.4 New Keyframe Decision

다음 4가지 조건을 모두 충족시 key frame으로 결정한다.

1. 마지막 global relocalization후, 최소 20frame 이후의 frame (너무 유사하면 의미가 없음)
2. Local mapping 수행이 적합하거나 마지막 keyframe 추가 후, 20 freame 이후의 frame
3. 현재 frame이 최소 50개 이상의 특징점을 track
4. 현재 frame이 reference keyframe의 90% 이하의 특징점을 track​

2. Local Mapping thread

중복되는 key frame과 tracking 후에 생성된 map point들을 최적화 한다.

2.1 KeyFrame Insertion

• tracking thread에서 새로운 key frame이 생성되면 이 key frame의 bag of words를 계산한다.
• 이를 바탕으로 새로운 key frame과 원본 영상 프레임의 map point를 비교한다.
• 그 후, covisibility graph를 update한다.
  • covisibility graph : 두 대 이상의 시점에서 겹치는 부분의 개수를 표현한 것

2.2 Recent MapPoints Culling

• Traking 과정 후에 생긴 Map point들과 새로 삽입된 key frame을 비교하여 bad point를 제거한다.
• low visibility, not trackable 점

2.3 New Points Creation

• 앞에서 수정된 Covisibility graph를 이용하여 현재 프레임과 연결되어 있는 프레임들을 찾는다.
• 찾은 프레임과 현재 프레임의 Map Point 쌍을 이용하여 Triangulate 한다.
• Triangulate 과정 후 생긴 프레임의 map point를 생성한다.
• 이 Map point들 중 현재 프레임과 covisibility graph 상에서 연결되어 있는 map point들만 project 시킨다.
• 그 후, covisibility graph를 다시 update한다.

2.4 Local BA

• map point 개수를 최적화 하는 과정이다.
• 현재 key frame과 covisibility 관계에 있는 key frame을 찾는다.
• 각 프레임들을 비교하여 같은 곳을 표시하는 map point들을 연결하고, 그러지 못한 map point는 outliers로 판단하여 제거한다.

2.5 Local KeyFrames Culling

• 다음과 같은 제약조건을 두어 key frame의 개수를 제한한다.
• 모든 key frame들은 적어도 3개 이상의 다른 key frame의 map point들과 90%의 covisibility 연결이 되어 있어야 한다.
• key frame이 너무 많으면 relocalisation과 bundle adjustment의 효과가 적어진다.

​3. Loop Closing thread

이전에 방문한 적 있는 공간인지를 확인하고 방문했던 공간이라고 판단되면 이전에 생성된 지도와 통합하는 기법

• 이전에 방문한 위치가 잘못된 Global location에 remapped해줌
• 에러가 누적되면 사전의 방문된 공간이 다른 위치로 나옴
• place recognition​​을 통해 이전의 방문했던 공간인지를 확인한다.

 

Place recognition

Bag of words 방법을 사용한다. (영상에서 feature들을 추출한 후, 추출된 feature들을 대표할 수 있는 값(code)들로 구성되는 codebook을 생성하는 기법)​

1. visual vocabulary

- 많은 이미지들로부터 feature 추출 후, descriptor를 모으고 descriptor들을 몇개씩 묶어 clustering한 가운데 값을 vocabulary라 한다.

2. recognition database

- keyframe 생성 시, visual vocabulary를 사용해 keyframe에 대한 이미지 특징을 표현한 data를 만들어 저장​

3.1 Loop detection

- recognition database를 후보군으로 현재 keyframe에서 나온 visual vocabulary를 통해 표현된 data를 후보군 안에 모든 data와 비교하여 진행

- 동일한 장소라도 판단되는 일정 기준을 만족하면 지도 통합

 

Map Data

ORB SLAM으로 부터 생성되는 데이터

1. Map point

- frame에서 검출된 feature들을 3d로 지도에 mapping한 point

- 각 map point(pi)가 가지는 World 좌표계 상의 pi의 위치

- Representative ORB descriptor : 각 map point를 포함한 keyframes의 ORB descriptor중에서 hamming distance가 최소인 ORB desciptor

- viewing distance : 각 map point의 최대, 최소 가시 거리

 

2. key frames

지도 생성시 특징이 될만한 위치를 나타내는 frame (유의미한 feature를 다수 보유)

• camera pose : 카메라 자세 및 위치
• camera intrinsics : focal length와 principal point를 포함한 카메라 정보
• ORB feature in the frame : frame에서 추출된 모든 ORB feature

3. covisibility graph

keyframe간의 맵포인트 공유관계를 나타낸 graph (Spanning tree)

• node : keyframe
• edge : share observations of map points
• min share map points : 15

4. essential graph (spanning tree)

covisibility 그래프의 핵심 정보만을 저장한 subgraph (Minimum Spanning tree)

• min sharred map point : 100

 

# 참고

• Raul Mur-Artal, J. M. M. Montiel, Juan D. Tardos. 『ORB-SLAM: a Versatile and Accurate Monocular SLAM System』. IEEE: transaction on robotics, 2015.: https://arxiv.org/pdf/1502.00956v2.pdf
• https://www.youtube.com/watch?v=mth-SMWnfas
• https://elecs.tistory.com/319
• https://m.blog.naver.com/PostView.nhn?blogId=ghd3079&logNo=221496302601&proxyReferer=https:%2F%2Fwww.google.com%2F