RSS

[review] Real-Time SLAM Relocalisation

13 Jun

발표 : ICCV 2007

제목 : Real-Time SLAM Relocalisation

저자 : Brian Williams, Georg Klein and Ian Reid

소속 : University of Oxford, UK

페이퍼 : http://www.robots.ox.ac.uk/~lav/Papers/williams_etal_iccv2007/williams_etal_iccv2007.pdf

동영상 : http://www.youtube.com/watch?v=uXqDA4do_s0

Metaio SDK가 가진 feature들 중에 instant 3D tracking 이라는게 있는데, 이 거는 스마트폰으로 어떤 장소나 환경을 동영상 촬영(?)하면서 3D point cloud를 학습하고, 이 학습된 3D map을 가지고 있으면 나중에 다른 기기(pc or other smart phone)로 해당 장소를 비췄을 때, 인식을 하여 증강시키는 것이다.  Metaio는 이 기술에 대해 공식적으로 밝힌 바(그냥 “slam”이라고만 했음)는 없지만 내가 예상하기에 지금 이 논문을 기반으로 만들지 않았을까 한다.  Relocalization은 slam을 하는 도중에 추적에 실패 했을 때, 다시 복귀 (failure recovery)하는 기능이다.  Instant 3D tracking과 비교해 보면, 3D map을 학습하는 단계는 slam을 성공적으로 수행하는 단계이고, 나중에 다른 기기로 해당 장소를 비춰서 인식하는 단계는 복귀하는 단계로 볼 수 있는 것이다.  다른 점은 Relocalization은 실제로 추적에 실패하는 경우이고, Instant 3D tracking은 추적에 실패했다고 가정하는 것이다.

이 논문에서는 relocalization을 하는 방법으로 ([1]에 기반한) randomized list classifier를 쓰고 있다.  중요한 건 randomized list classifier가 2D feature descriptor임에도 불구하고, 3D relocalization에 쓰였는데 이에 대한 defense가 없다는 것이다.  random fern 학습 시에 여러 affine transform들을 시켜서 학습하므로 이것으로 3D view point 변화를 커버할 수 있다고 생각했나 보다.  그러면 3D point에 대해 처음 random fern 학습시킬 때의 point of view랑 비슷한 view로 가져가야지만 그 point에 대해 relocalization이 될 텐데, 이는 relocalization 할 때도 임의의 view point가 아니라 더 선호되는 view point가 있다는 말이 된다.  따라서 실제적으로는 잘 될지 모르겠지만, 이론적으로는 좀 한계가 있어 보인다.

Fua와 Lepetit이 만든 random fern을 본 논문의 목적인 real-time slam에 맞게, 즉 online learning에 맞게 어떻게 modify시켰는지에 대해 역점을 둬서 기술하고 있다.  ICCV 논문으로서는 좀 부족한 듯 싶다.  변형된 부분(modification)은 다음과 같다.

  • 원래 random fern은 tree의 각 노드마다에서 이루어지는 두 점의 intensity 대소 비교시, 그 두 점의 위치가 각 노드마다 다 다르다.  즉 depth 3개 짜리면 7개(2^3 -1)의 노드(test)가 생성되는데 그 test들에 사용되는 두 점의 위치가 다 다르며, 어떻게 하는 지는 모르겠지만 information gain을 최대화 하기 위해 어떤 최적화 과정을 거쳐서 정해진다고 한다.  하지만 online 학습인 slam의 경우에는(즉 어떤 환경을 맞닥드릴지 모르는 경우에는) 이런 특정 경우에 맞는 최적화가 의미가 없어지며, 그냥 random하게 정하는게 올바른 판단이라고 한다.  Random하게 한다면 굳이 같은 level의 node들의 test가 달라야 할 필요가 있냐 하는 의문을 던지고 있다.  즉 첫번째 level에서 intensity 비교를 통해 왼쪽과 오른쪽으로 나뉠 텐데, 여기서 다시 왼쪽과 오른쪽의 node에서의 test가 서로 다른 두 점에서 이루어 질 필요가 있냐 하는 것이다.  Random이면 굳이 random을 두 번 튕길 필요가 없다는 것이다.  그냥 random을 한 번 튕기면 되고, 그 random도 프로그램 돌기 점에 미리 튕겨 놓으면 된다는 것이다.  일단 준비해야 하는 test의 수는 L레벨에 대해 2^L – 1에서 L로 줄어든다.
  • 무슨 말인지 잘은 모르겠는데, classifier간에 independence를 가정한다고 한다.  [1]의 경우 학습 단계에서 random fern이 normalizaton을 통해 확률이 되어서 유사한 feature의 classifier들끼리 서로 간의 확률을 낮추는데, 여기서는 independent하게 해줘서 서로 간에 영향을 안미친다고 한다 (뭔소린지 모르겠다).
  • Random fern이 확률 분포를 가지고 있는게 아니라, 그냥 binary 값을 가지고 있다고 한다.  그러니까 0은 0, non-zero는 1.  이로서 메모리 사이즈 줄이고…. 확률로 안간다고 하는 건, 앞서 언급한 꼭지와 관련이 있어 보인다.
  • texture less한 영역에 대해 두 점의 대소비교를 할 때, 약간의 노이즈가 껴도 (원래는 두 점이 같은 값이 나와야 되는데) 대소 비교에 영향을 미친다.  따라서 단순한 대소비교가 아니라 어느 정도 차이가 나는지를 따진다.
  • 앞 꼭지와 일맥상통한 얘긴데, [1]에서는 학습시 여러 patch를 만들 때, noise에 강건하라고 일부로 noise를 심어 주는데, 여기서는 굳이 noise까지 심어 주진 않고, 대신 어떤 노드에서 대소비교시 별로 차이가 안나면 양 쪽 자식을 다 타주는 것이다.  이로서 프로그램 적으로 noise를 가상으로 심어주는 역할을 한다. (아이디어 괜찮다.)

실제 rolocalization 할 때는, 트랙킹 실패 후 카메라 feed image에 대해 RANSAC으로 여러 feature correspondence hypotheses에서 가장 좋은 hypotheses의 model을 선택한다고 한다.  그리고 random walk를 적용해 시간이 지남에 따라 search 영역을 점점 증가시키고, 해당 시간에 절대 도달할 수 없는 위치의 feature는 random fern에서 좋은 결과가 나왔다고 해도 무시한다고 한다.  근데 문제는 hypothesis를 3개의 점을 가지고 한다고 한다.  3점가지고 되나?  어떻게?  5점은 있어야 되지 않나?

이 논문의 전신인 [2]를 보면 3-point 알고리듬을 쓰고 있고 이 이유에 대해 다시 [3]을 reference로 들고 있는데 이유를 잘 모르겠다.  3 correspondence로는 unique한 하나의 hypothesis가 아니라 4개의 hypothesis가 나오는데, 논문에 보면 그 4개의 가정에 대해 다 RANSAC test를 해 준다고 한다. 그런데 이 게 5개의 점을 가지고 unique한 1개의 가정을 만드는 거 보다 RANSAC에 있어서 만들어 줘야 하는 hypotheses 수가 오히려 더 많다.

위 식은 하나의 hypothesis model을 만들기 위해 n개의 점이 필요하고, inlier rate가 \omega일 때, 확률 p의 confidence로 inlier들로만 이루어진 hypothesis를 한 번 도출하기 위해 필요한 hypotheses 발생 수k를 구하는 식이다. p = 0.95, \omega = 0.6 이라고 가정할 때, 3-point와 5-point의 경우를 비교해 보면 각각,

  • 3-point, 4 hypotheses
    k = 4\frac{\log (1 - 0.95)}{\log (1 - 0.6^3)} = 49
  • 5-point, 1 hypothesis
    k = \frac{\log (1 - 0.95)}{\log (1 - 0.6^5)} = 37

이런 식으로 5-point 알고리듬이 RANSAC iteration 수가 더 적게 나온다 (이렇게 계산하는게 옳지 않은가?).  암튼, 그럼에도 불구하고 3-point, 4 hypotheses를 쓰는 이유를 guess해 보면 5-point 알고리듬은 matrix 연산등의 계산량이 많은 반면, 3-point 알고리듬은 4차 다항식 문제이고, 적절한 근의 공식같은게 존재해서 바로 사칙연산으로 모델 파라미터가 나올 수 있어서이지 않을까한다(에이! 모르겠다).

[1] M. Ozuysal, P. Fua, and V. Lepetit. “Fast keypoint recognition in ten lines of code”. CVPR 2007

[2] Brian Williams, Paul Smith and Ian Reid. “Automatic Relocalisation for a Single-Camera Simultaneous Localisation and Mapping System”, ICRA 2007.

[3] R. M. Haralick, C. Lee, K. Ottenberg, and M. Nolle. “Review and analysis of solutions of the three point perspective problem”. IJCV 1994

Advertisements
 
 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: