Review: OpenStreetSLAM

G. Floros, B. van der Zander and B. Leibe, "OpenStreetSLAM: Global vehicle localization using OpenStreetMaps," 2013 IEEE International Conference on Robotics and Automation, Karlsruhe, 2013, pp. ...

0. Introduction

기존 GPS는 항상 사용 가능한 게 아니고(음영 지역), 오차도 수 미터에 달한다. 이러한 문제를 극복하기 위해 연구자들은 이전부터 차량 위에 장착된 카메라를 이용하려고 노력했다.

이러한 비전 기반 방법은 크게 두 가지로 나뉜다. 1) Google Street View data처럼 특수하게 장착된 플랫폼 [3]에서 획득한 geotagged image corpora를 사용하여 localiztion을 수행하는 방법과

2) VSLAM 기반으로 수행하는 방법이다. VSLAM 프레임 워크의 주요 문제 중 하나는 drift가 누적되어 장거리에서 localization이 잘 안된다는 점이다. 해결책으로 loop로 운전하고 loopclosing을 진행하는 방법이 있다.

geotagged image corpora?

기본적인 가정은 단거리에서 VO가 충분히 정확하다는 것이다. 대부분의 기존 VO 알고리즘에 적용되는 이 가정을 기반으로 공개적으로 사용 가능한 지도(OpenStreetMap)을 이용하여 시간이 지남에 따라 정확한 현지화를 제공하는 현지화 시스템을 구축한다. 본 논문의 프레임 워크는 차량의 대략적인 초기 GPS위치를 입력으로 취하고 주변 지역의 해당 지도를 다운로드 하고 특정 최소 거리를 주행 한 후에 차량의 위치를 파악한다. 그 다음 Monte Carlo Localization 프레임 워크를 통해 VO를 motion model에 대한 입력으로 사용하고 chamfer matching을 사용하여 차량의 위치를 추적하여 맵에 대한 여러 hypotheses를 일치시키고 평가한다. 실험 결과를 보면 drift 축적과 같은 VO 시스템의 기존 문제를 극복하는 성능을 볼 수 있다.

Monte Carlo Localization framework

1. Related Work

VO쪽에서 Global localization에 관한 논문들 중 Kitt et al. [5] 와 최근 Alcantarilla et al. [6]를 살펴볼 필요가 있다. 이 방법들의 기본 파이프 라인은 Feature extraction > feature matching > 3D reconstruction of point cloud > estimation of the pose of the vehicle으로 구성된다. windowed bundle adjustment는 마지막에 실행한다. 이 방식의 주요 단점은 drift가 시간이 지남에 따라 누적된다는 것 이다. 그러면 결국 차량이 일정 거리를 이동 한 후 localization error가 너무 커져서 더 먼 거리에서의 localization이 거의 불가능해진다.

VO 접근법과 병행하여 VSLAM을 수행하는 방법도 많다 [4], [7]. VSLAM 파이프 라인은 VO 파이프라인과 유사하지만 차이점도 있다. 전자의 경우는 재구성된 3D 포인트가 랜드마크로 사용되며 그 3D 포인트들의 위치가 카메라 포즈와 함께 최적화된다는 차이점이 있다. drift 누적문제를 완화하기 위해 차량이 루프에서 운전하거나 다른 차량으로 이전에 동일한 경로를 매핑해야 알고리즘이 동일한 랜드마크를 인식하여 localization error를 보정할 수 있다. 그러나 루프에서 운전하는 것은 일반적은 상황이 아니고, 사전 계산된 랜드 마크 이미지의 feature map는 용량이 너무 크다.

한편, 이미 2D (e.g. Google Maps, OpenStreetMaps) 또는 3D 거리뷰(e.g. Google Maps 3D)의 형태로 제공되는 지도 정보를 Localization에 사용하는 연구가 있었다. Hentschel et al. [8] 가 로봇 위치 파악 및 탐색을 용이하게 하기위해 OpenStreetMap을 사용한 전례가 있다. building footprint가 있는 cadastral 지도가 추출되고 Monte Carlo Localization framework를 통해 로봇의 GPS를 사용해 로봇의 위치를 파악한다. 최근 Senlet et al. [9], [10]은 Google Static Maps를 사용하여 Global localization을 수행하는 시스템을 제시했다. Stereo depth map을 사용하여 장면의 local reconstruction을 2D맵과 비교하는 방법이다. 앞서 언급한 두 가지 접근 방식 모두 OpenStreetMap을 사용하여 localization 성능을 높일 수 있음을 보인다. 그러나 이들의 시스템은 initial localization을 수동으로 해야하고 환경이 비교적 단순하고 이동 경로가 짧은 교외 지역에서만 테스트 되었다. 또한 이런 시스템은 stereo depth estimation이나 local 3D reconstruction을 수행하므로 연산 부하가 지나치게 높다.

우리는 street graph 형태의 유용한 지도 정보와 함께 VO 알고리즘의 장점을 결합하는 새로운 global localization 접근 방식을 제안한다. 우리 시스템은 대략 1km 반경의 지도에서 차량의 초기 위치를 자동으로 파악하기 위해 매우 대략적인 초기 GPS 추정값만 필요로 한다. 그런 다음 MCL 단계는 chamfer matching을 통해 Global localization 작업을 수행하여 다양한 위치 hypotheses를 거리 지도에 일치시킨다.

Visual Odometry pipeline.

이 시스템은 MCL 프레임 워크로 구성되며, 여기서 VO는 프레임 간 차량의 움직임을 추정한다. 그런 다음 VO의 결과물을 Particle filter 알고리즘의 Motion model에 입력하여 여러 particle을 생성한다. 각각의 particle 은 지도와 일치하는 정도에 따라 평가된다. 다음 장에서는 통합 프레임 워크를 형성하기 위한 개별 구성 요소와 그 조합을 소개하고 구현 세부 정보를 제공한다.

3. Visual Odometry (VO)

VO 구성 요소의 front-end에서 feature extraction은 입력 이미지에서 실행된다. 왼쪽과 오른쪽 카메라 이미지에서 Harris corners [11]를 추출한다. 우리는 세 가지 이유로 이 specific type의 기능을 선택했다. 첫째, Harris corner는 서로 다른 이미지 변환에서 높은 응답 안정성과 반복성을 갖는 것으로 알려져있다.[12] 둘째, 매우 효율적으로 구현할 수 있으므로 real time 시스템에 적합하다. 마지막으로, 우리 시스템에는 loop closing 이 포함되어 있지 않기 때문에 Scale invariance를 설명하기 위해 더 정교한 descriptor가 필요하지 않다. 우리는 Nister et al[13] 처럼 10x10 Grid를 사용하여 이미지를 세분화 하여 100개의 buckets 에 각각 relative threshold 적용하여 전체 이미지에 대해 균일한 feature coverage를 적용한다.

relative threshold

http://egloos.zum.com/jinhwanlee/v/10488022

[13] 의 관련내용 정리

추출된 각각의 harris corner에 대해 11x11 pixel patch descriptor가 계산된다. 그런 다음 왼쪽 및 오른 쪽의 이미지의 descriptor는 normalized cross-correlation을 사용하여 이전 프레임과 일치시킨다. 이때, feature가 mutual nearest neighbor인 경우만 일치한다고 한다.[13] 그 다음 유효한 일치 항목이 Triangulation 되고 해당 3D point가 생성된다.

마지막 단에서 카메라 시스템의 포즈는 재구성 된 포인트 중 3로부터 추정한다. 카메라 포즈에 대한 hypothesis는 각 triplet에서 생성된 다음 RANSAC 프레임워크에 입력되어 back-projection error measure 기반으로 평가되고 최상의 hypothesis를 선택한다. 우리 VO 구성 요소는 feature-based이므로 scene에서 다른 움직이는 물체의 존재에 크게 영향을 받는다. 이러한 영향을 완화하려면, 일정 속도의 칼만 필터로 카메라 포즈를 추적하여, 포즈 추정 알고리즘 결과 값이 일치하지 않을 때마다 카메라 경로를 추정한다. [15]

[15] 살펴보기

4. OpenStreetMap Data Representation

OpenStreetMap (OSM) 데이터는 해당 웹 사이트를 통해 액세스 할 수 있으며, 사용자는 경도 및 위도 측면에서 바운딩 박스 b를 지정하여 관심 영역의 지도를 다운로드 할 수 있다. $b = (lat_{min}, lon_{min}, lat_{max}, lon_{max}).$

지도는 XML 형식으로 제공되며, nodes, ways 및 relations [16]의 세 가지 기본 entities를 구조로 한다. 노드 n은 지도의 point 요소를 나타내며 GPS 좌표, 위경도 $n = (lat,lon)$로 정의된다. linear 및 area 요소들은 $w = \{n_{i}\}_{i=1...k}$ 와 같은 형태의 노드 집합 w로 표현된다. 관계 r은 앞서 언급한 geometric entities간의 더 복잡한 관계를 표시하기 위해 쓰인다. 거리나 건물과 같은 관심영역의 맵은 해당 영역의 street graph를 만들기 위해 XML 파일에서 뽑아서 써서 모델링 할 수 있다.

지도 구조에 관한 내용 추가 [16] 정밀지도랑 비교하면 더 좋음

5. Chamfer Matching

Chamfer matching은 homogeneous 변환 $H=(\theta, t_x, t_y)$, $H \in SE(2)$을 찾아서 query edge map $Q =\{q_i\}$을 template edge map $T = \{t_i\}$ 와 매치시키고 정렬하는 인기있는 알고리즘이다. 대상은 다음과 같은 최소화 문제로 공식화 될 수 있다.

chamfer matching 자세하게 공부

Chamfer matching 알고리즘은 두 가지 장점이 있다. 첫째, query가 templete에 정확히 맞지 않더라도 가장 일치하는 정렬을 찾음으로써 작은 정렬 불량 및 변형에 강하다. 둘째, distance transform image를 사용하여 매칭 cost를 매우 효율적으로 연산 할 수 있다. 특히, distance transform의 연산은 이미지를 두 번 통과해야하며 [18] linear complexity $O(n)$에서 (3)의 평가를 가능하게 한다. 여러 접근법[19], [20]은 가장자리 방향의 정보를 통합하여 chamfer matching 의 robustness를 높이려 했다. 이를 실현하기 위해 edge를 여러 방향의 평면으로 quantize 하거나, 따로 추정하거나, 추가 방향 term을 포함하도록 matching cost function를 증가시킨다. 이러한 접근 방식들은 결과를 개선하지만 연산량이 증가한다.

최근 Liu et al. 의 FDCM (Fast Directional Chamfer Matching) [21]은 edge orientation 정보를 통합하여 최적의 결과를 생성하는 알고리즘을 도입했으며 동시에 다른 Chamfer 매칭 보다 45배 빠르다. 이 알고리즘은 edge map이 일련의 2D point 에서 line segment로 변환된다는 사실을 이용했다. 이 변환은 $m\ll n$일 때, edge set의 cardinality를 $n$개의 점에서 $m$개의 선분으로 줄인다.

에지 방향 정보가 매칭 비용 함수에 추가되고 3D 거리 변환이 계산되어 매칭 비용 함수를 더 빠르게 평가할 수 있습니다.