이 문서는 중국어 원서인 “입문 Visual SLAM 이론에서 연습까지 14 강(视觉SLAM十四讲 从理论到实践)” 책의 원저자로부터 한글 번역 허가를 받고 구글 번역기를 이용하여 작성된 문서입니다. 본 문서는 아래의 Contribution을 특징으로 합니다.
- 중국어 전공 서적을 구글 번역기를 이용해 한글로 초벌 번역했습니다.
- 초벌 번역 후 매끄럽지 않은 문장은 문맥에 맞게 수정되었습니다.
- 문서 내용 중 참고할만한 웹문서를 코멘트로 추가했습니다.
- SLAM 연구에서 주로 사용되는 용어는 한글로 번역된 용어보다 주로 사용되는 영어로 된 용어 그대로 표시하였습니다.
그럼에도 불구하고 부정확하거나 매끄럽지 않은 부분이 있을수 있습니다. 그런 부분은 코멘트로 제안해주시면 반영하도록 노력하겠습니다. 또한 읽으시다가 잘 이해가 가지 않는 부분도 코멘트로 질문해주시면 답변해드리도록 하겠습니다.
번역 참가자:
- 신동원 (광주과학기술원 박사과정)
- 김선호 (VIRNECT 선임연구원)
- 조원재 (일본국립농업기술혁신공학센터 연구원)
- 장형기 (Imperial College London 석사)
- 박준영 (광주과학기술원 석사과정)
2018년 10월 1일 신동원 드림
카메라 포즈와 공간 포인트를 사용한 맵 최적화를 BA라고하며, 대규모 위치 추정 및 매핑 문제를 효과적으로 해결할 수 있습니다. 그러나 시간이 지남에 따라 로봇의 이동 궤적이 길어지고 지도의 규모가 계속 커질 것입니다. BA와 같은 방법에서, 계산 효율은 계속 떨어질 것입니다. 앞의 논의를 토대로 포인트의 라인 피팅 문제가 대다수의 최적화 문제를 설명한다는 것을 알게 되었습니다. 사실 몇번의 관측 후, 특징점이 수렴하는 경우, 공간 상의 위치 추정치는 대체로 고정된 값으로 수렴합니다. 수렴 지점을 최적화하는 것은 다소 우스운 것 같습니다. 따라서 여러 최적화 후에 특징점을 수정하고 실제 위치 추정치를 실제로 최적화하는 대신 포즈 추정의 제약 조건으로 간주합니다.
이 사고 방식을 생각해 보면, 우리는 생각할 것입니다 : 랜드마크를 완전히 무시하고 트랙을 따라갈 수 있습니까? 로봇의 포즈만 고려하는 그래프 최적화를 구성 할 수 있으며, 두 개의 키 프레임 사이의 피쳐 매칭 후에 얻은 모션 추정을 통해 포즈 노드 간의 에지를 초기 값으로 지정할 수 있습니다. 차이점은 초기 추정이 완료되면 더 이상 해당 랜드마크의 위치를 최적화하지 않고 모든 카메라 포즈 간의 연결만 최적화한다는 것입니다. 이 방법으로 많은 특징점 최적화 계산을 저장하고 그림 11-1과 같이 키프레임의 궤도만 유지함으로써 소위 포즈 그래프를 구성합니다.
그림 11-1 포즈 그래프의 도식. Bundle Adjustment에서 랜드마크 점을 더 이상 최적화하지 않고 포즈 노드의 constraint로 간주 할 때, 계산 규모가 훨씬 작은 포즈 그래프를 얻을 수 있습니다.
우리는 BA에서 특징점의 수가 포즈 노드보다 훨씬 많습니다. 키프레임은 종종 핵심 포인트와 관련이 있으며, 희박한 상태에서도 실시간 BA의 최대 계산 규모는 현재 주류 CPU에서 일반적으로 수십만 포인트에 달합니다. 이는 SLAM 응용 프로그램이 실시간으로 동작하는 것을 어렵게 합니다. 그러므로 로봇이 보다 넓은 시간과 공간에서 움직일 때, 슬라이딩 윈도우 방법 [77]과 같은 일부 데이터를 버리거나 Pose Graph에서와 같이 랜드 마크 점의 최적화를 무시하는 방법을 고려해야합니다.
따라서 포즈 그래프 최적화의 노드와 에지는 무엇을 의미합니까? 여기서 노드는 으로 표현된 카메라 포즈를 나타냅니다. 에지는 두 포즈 노드 간의 상대적인 움직임의 추정치입니다. 움직임의 추정치는 특징점 방식이나 direct method에서 나올 수 있고, 예를 들어,
와
사이의 움직임
을 추정합니다. 이 모션을 표현하는 몇 가지 방법이 있으며, 더 자연스러운 방법을 사용합니다:
(11.1)
또는
(11.2)
그래프 최적화에 대한 아이디어에 따르면 실제로 방정식은 정확하게 설정되지 않으므로 최소 제곱 오차를 설정한 다음 이전과 마찬가지로 최적화 변수의 미분에 대한 오차를 논의합니다. 여기에서 위 공식의 를 방정식의 오른쪽으로 이동하고 오차
를 구성합니다.
(11.3)
[생략]
다음은 포즈 맵 최적화에 g2o를 사용하는 방법을 보여줍니다. 먼저 독자는 그림 11-2와 같이 slambook / chll / sphere.g2o에있는 g2o_Viewer로 사전 생성 된 시뮬레이션 포즈를 열도록 요청받습니다.
그림 11-2 g2o 시뮬레이션으로 생성 된 포즈 맵. 실제 값은 완전한 구이며, 누적 오류가있는 시뮬레이션 데이터는 참값에 노이즈를 추가하여 얻습니다.
포즈는 g2o의 자체 작성 프로그램에 의해 생성됩니다. 이것의 궤적은 아래에서 위로 여러 층으로 구성된 볼입니다. 각 레이어는 완벽한 원입니다. 서로 다른 크기의 여러 원형 레이어가 완전한 구형을 형성하며, 2500개의 포즈 노드 (그림 11-2의 왼쪽 위에 있음)가 상승 원의 과정으로 볼 수 있습니다. 그런 다음, 시뮬레이션 프로그램은 odometry edge (주행 거리계)라고 불리는 t-1에서 t까지의 엣지를 생성합니다. 또한 레이어와 레이어 사이의 가장자리가 만들어지며 이를 루프 폐쇄라고합니다 (루프 폐쇄에 대한 자세한 내용은 다음 강의에서 설명 함). 그런 다음 각 측에 관측 잡음을 추가하고 주행 측의 노이즈을 기반으로 노드의 초기 값을 재설정하십시오. 이렇게 하면 누적 오차가 있는 포즈 데이터가 얻어지며 (그림 11-2, 오른쪽 아래) 부분적으로 구의 일부처럼 보이지만 전체 모양이 구와 멀리 떨어져 있습니다. 이제 우리는이 잡음이 많은 가장자리와 노드에서 왔습니다. 초기 값부터 시작하여 전체 포즈 맵을 최적화하여 근사값을 가진 데이터를 얻으십시오.
물론, 실제 로봇은 구형 운동 궤도와 완전한 주행 및 루프 관측 데이터를 갖지 않을 것입니다. 이렇게 구성된 볼을 시뮬레이션 할 때의 이점은 최적화 결과가 올바른지 시각적으로 확인할 수 있다는 것입니다. 독자는 g2o_viewer의 optimize 함수를 클릭하여 각 단계의 최적화 결과 및 수렴 프로세스를 볼 수 있습니다. 반면에 sphere.g2o는 텍스트 편집기로 열 수있는 텍스트 파일이기도합니다. 파일의 첫 번째 절반은 노드로 구성되며 두 번째 절반은 에지로 구성됩니다.
[코드 그림]
보시다시피, 이 섹션의 포인트 유형은 카메라 포즈를 나타내는 VERTEX_SE3입니다. G2o는 쿼터니언과 이동 벡터를 사용하여 기본적으로 표현하므로 다음 필드의 의미는 입니다. 첫 번째 3개는 이동 벡터 요소이고 마지막 4 개는 단위 쿼터니온으로 표현된 회전입니다. 마찬가지로 정보 모서리는 두 개의 노드인 의 ID입니다. 정보 행렬은 대칭 행렬이기 때문에 절반만 저장하면됩니다. 정보 행렬은 대각 행렬로 설정됨을 알 수 있다.
이 포즈를 최적화하기 위해 g2o의 기본 정점과 가장자리를 사용할 수 있습니다. 이 정점은 쿼터니언으로 표시됩니다. 시뮬레이션 데이터도 g2o에 의해 생성되므로 g2o 자체의 최적화는 더 많은 작업을 수행 할 필요가 없으며 최적화 매개 변수를 구성하기 만하면됩니다. slambook / chll / pose_graph_g2o_SE3.cpp 프로그램은 Levenberg–Marquardt 메서드를 사용하여 포즈를 최적화하고 결과를 reSuIt.g2o 파일에 저장하는 방법을 보여줍니다.
slambook/ch11/pose_graph_g2o_SE3.cpp
Levenberg–Marquardt 방법을 사용하고 반복 횟수를 30 번 선택하여 6x6 블록 솔버를 선택했습니다. 이 프로그램을 호출하여 포즈지도를 최적화하십시오.
[코드 그림]
그런 다음 g2o_viewer를 사용하여 result.g2o를 열면 그림 11-3과 같은 결과가 표시됩니다.
그림 11-3. g2o 고유의 정점 및 가장자리를 사용하여 결과를 해결하십시오.
결과는 불규칙한 모양에서 겉으로보기에 완전한 공으로 최적화됩니다. 이 프로세스는 g2o_viewer에서 최적화 버튼을 클릭했을 때와 본질적으로 동일합니다. 아래에서 우리는 이전의 Lie 대수 유도법을 기반으로 Lie 대수 에 대한 최적화를 구현합니다.
[생략]
볼의 예가 대표적인 경우입니다. 실제로 SLAM의 자세에 있을수도 있는 실제 거리계와 루프 폐쇄와 비슷한 오도메트리와 루프 폐쇄가 있습니다. 동시에 "볼"에는 일정한 규모의 계산이 있습니다. 이 노드는 총 2,500 개의 포즈 노드와 거의 10,000 개의 에지를 가지며 (실시간 요구 사항이 강한 frontend에 비해) 최적화하는 데 많은 시간이 걸리는 것으로 나타났습니다. 반면에 포즈 맵은 일반적으로 가장 간단한 구조 중 하나로 간주됩니다. 로봇이 어떻게 움직이는지 가정하지 않는다는 전제하에, 로봇이 곧게 움직여서 드문 드문 밴드 모양의 포즈를 형성 할 수 있기 때문에 희박성에 관해 더 자세히 논의하는 것은 어렵습니다. 또한 "왼손잡이와 오른손잡이"일 수도 있습니다 느린 동작에서 많은 수의 작은 루프를 형성하려면 최적화 (Loopy motion)가 필요합니다. 그러면 "볼"과 같이 더 밀집된 포즈가됩니다. 어쨌든 우리는 더 이상의 정보를 얻기 전에 더 이상 포즈 맵의 솔루션 구조를 사용할 수 없습니다.
PTAM이 도입 된 이후 Backend optimization이 반드시 frontend 이미지 데이터에 실시간으로 응답하지는 않습니다. 사람들은 frontend를 백 엔드에서 분리하여 두 개의 별도 스레드로 실행하는 경향이 있습니다 (역사적으로 추적 및 매핑이라고도 함). 하지만 매핑 부분은 주로 백 엔드를 참조합니다. frontend는 실시간으로 비디오 (예 : 초당 30 프레임)에 반응해야하며 최적화가 완료되면 결과가 frontend로 반환되는 한 느리게 실행될 수 있습니다. 그래서 우리는 대개 Backend optimization에 매우 빠른 요구 사항을 요구하지 않습니다.
[생략]
[생략]
그러나 지금까지는 최적화의 관점에서 Factor 그래프 최적화와 일반 그래프 최적화 간에 차이가 크지 않습니다. 최소 제곱 문제로 끝나기 때문에 지속적으로 목표를 만들기 위한 그라디언트를 찾고 있기 때문입니다. 팩터 그래프 최적화의 희박성은 그래프 최적화와 유사하며 sparse QR 분해, Schur complement 또는 촐레스키 분해를 통해 팩터 그래프 최적화 솔루션을 가속화 할 수 있습니다. 여기서 우리는 다음의 궁금증을 가질 수 있습니다. Factor 그래프 최적화가 일반적인 그래프 최적화와 같은 것일까요? 상황은 정확히 이와 같지 않습니다.
Kaess et al.에 의해 제안 된 iSAM (Incremental Smooth and Mapping)에서 요소 그래프는 Backend optimization를 단계적으로 처리 할 수 있도록 보다 세밀하게 처리됩니다. 제6강의 내용을 상기하면서, 일반 그래프 최적화에서 최종 계산은 Incremental 방정식임을 알 수 있습니다. 이것이 목적 함수를 조정하는 방법입니다.
[수식]
목적 함수의 최적화 변수는 목적 함수를 떨어 뜨립니다. 어떤 그라디언트 강하 전략이 채택 되더라도 마침내 우리는
[수식]
선형 방정식을 풀어야합니다. 지난 강의에서는 방정식의 희소성을 사용하여 솔루션을 가속화하는 과정을 소개했습니다. 그러나 그래프 최적화가 고정되어 있지 않기 때문에 로봇이 움직이면 새로운 노드와 엣지가 맵에 추가되어 크기가 커집니다. 매번 새로운 노드가 추가될때, 모든 노드의 업데이트 양을 다시 계산해야할까요? (Jacobi의 계산 [선형화] 및 업데이트 된 방정식의 계산 포함).
분명히 이것은 경제적이지 않습니다. Incremental 업데이트를 설명하기 위해 그림 11-8을 예제로 사용합니다. 이것은 포즈 맵입니다. 노드에 오도미터로 노드를 추가하면 영향을 받는 노드는 마지막 노드만 연결된 것으로 추정 할 수 있으며 이전 노드의 추정치는 변경되지 않은 것으로 근사 할 수 있습니다. 따라서 최적화할 필요가 없습니다. 왜 근사치를 말하고 싶니? 노드를 실제로 추가하면 이전 추정치에 영향을 미치기 때문에 가장 최근 데이터에 가장 큰 영향을 미치며 멀리있는 데이터에 거의 영향을 미치지 않으므로 무시할 수 있습니다. 점진적인 기능이 실현 가능하다고 생각하면 많은 계산을 줄일 수 있습니다. 최소한 노드를 추가 할 때마다 전체 그래프를 최적화 할 필요는 없습니다. 그러나 Loop closure detection 방식에서 노드를 추가하는 경우 영향을 받는 범위는 루프백 시작부터 현재 프레임까지 세그먼트의 모든 노드 여야합니다. 즉, 전체 트랙을 다시 조정할 수 있습니다. 이렇게 하면 계산량이 늘어나지만 루프 외부의 노드에는 영향을 미치지 않으므로 전체 그림을 최적화 할 필요가 없습니다. 요약하면 그래프에 노드를 추가함으로써 영향을 받는 영역을 분석함으로써 불필요한 계산을 줄이고 백 엔드 최적화 프로세스를 가속화 할 수 있다는 것을 알게되었습니다.
그림 11-8 Incremental 업데이트 다이어그램.
이 아이디어를 바탕으로, Kaess 등이 제안한 incremental 팩터 그래프 최적화는 위의 문제를 어느 정도 해결합니다. 기술적인 관점에서 각 최적화에서 중간 결과를 저장하고, 새로운 변수 및 팩터가 추가되면 먼저 팩터 그래프 간의 연결 및 영향 관계를 분석하고 이전에 저장 될 수있는 정보를 고려해야합니다. 다시 계산해야하는 사용을 계속하고 마지막으로 증가분 최적화를 처리하십시오.
그런데 많은 양의 기술적 세부 사항을 소개하고 확률 그래프 이론에 대한 지식을 필요로하는 특정 작업 단계는 이 책에서 다루지 않습니다. 따라서 이 절은 독자에게 옵션으로 제공되는 독서 자료입니다. 관심있는 독자는 iSAM 및 iSAM2와 같은 원본 문서를 읽고 세부 정보를 이해할 수 있습니다. 마지막으로 증분식 분석에도 불구하고 영향을 받은 노드가 비슷하다는 것을 알아야하므로 실제로 그래프의 크기가 어느 정도 변경되면 전체 그래프 최적화를 다시 수행해야합니다.
아래에서는 factor 그래프를 사용한 포즈 최적화의 예를 보여줍니다. 우리는 여전히 이전의 "공"의 데이터를 사용하지만, 이번에는 g2o를 이용한 일반 그래프가 아닌 팩터 그래프를 사용합니다. 이론적으로 문헌 [83, 84]에서 factor 그래프 최적화에 기반한 SLAM backend 라이브러리 인 GTSAM을 사용할 것입니다. 이를 바탕으로 이전 섹션에서 "공"의 예를 최적화합니다.
최신 버전의 gtsam은 4.0이며 https : //bitbucket.org/gtborg/gtsam에 있습니다. 다음 명령을 입력하여 다운로드 할 수 있습니다 :
[코드]
gtsam이 크기 때문에 3rdparty 폴더에서는 사용할 수 없습니다. 과거에 우리가 만났던 라이브러리와 마찬가지로 gtsam도 cmake 프로젝트입니다. 우리는 cmake에 따라 컴파일하고 설치합니다. Gtsam은 주로 Eigen과 tbb 라이브러리가 더 적습니다. 독자가 책을 따라 간다면 대부분의 라이브러리를 설치해야하며 tbb 라이브러리 만 설치하면됩니다.
[코드]
그런 다음 cmake 명령을 사용하여 gtsam을 컴파일하고 설치하십시오. 여기서는 자세히 설명하지 않습니다. gtsam 라이브러리는 비교적 크고 Factor 그래프와 관련된 많은 요소를 통합하고 기본 행렬 및 Lie 대수 연산까지도 포함하므로 컴파일 및 설치에 많은 시간이 소요되므로 참을성있게 기다려주십시오. 설치가 끝나면 /usr/local/include에있는 헤더 파일과 /usr/local/lib에있는 라이브러리 파일을 찾을 수 있습니다. gtsam 라이브러리 파일은 상대적으로 간단하며 하나의 libgtsam.so만으로 구성됩니다. 따라서 자신의 프로젝트에 CMakeLists.txt를 작성하여 gtsam을 호출하는 방법을 알아야합니다.
"공"의 예를 보여 드리겠습니다. 이전 실험에서와 마찬가지로 sphere.g2 파일에서 노드 및 에지 정보를 읽고 이를 Factor 그래프로 변환 한 다음 처리를 위해 gtsam으로 전달한 다음 최적화 결과를 g2o 파일에 다시 쓰고 노드를 g2o로 "가장합니다". 그리고 디스플레이를 위한 가장자리. 이것이 gtsam의 "Incremental"성격을 반영하지는 않지만 적어도 이 예제를 사용하여 사용법을 경험할 수 있습니다.
slambook/ch11/pose__graph_gtsam.cpp
데모에서는 g2o 파일을 텍스트로 읽고 gtsam 인터페이스로의 변환을 완료합니다. 코드에서 g2o와 gtsam의 유사점과 차이점에 유의하십시오.
유사점: 그것들은 근본적으로 최소 제곱 최적화 문제이기 때문에 우리가 설정해야하는 것은 유사합니다. 요컨대, 꼭짓점의 초기 값 (factor 그래프의 변수에 해당)과 에지 (factor에 해당)의 관찰 및 노이즈 크기. 최적화 설정과 관련하여 Gauss-Newton 방법이나 Levenberg-Marquardt 방법을 사용하여 자세한 매개 변수를 구성 할 수도 있지만 인터페이스가 약간 다릅니다. G2o는 최적화 된 알고리즘 객체를 구현하여 구현되지만 gtsam은 최적화 매개 변수로 전달됩니다.
차이점 : g2o의 노이즈 모델은 gtsam과 약간 다릅니다. 코드에서 변환을 수행했습니다. sparse 처리 측면에서 gtsam은 QR 분해 또는 촐레스키 분해를 사용할 수 있습니다. 단, 여기에서는 특정 프로세스에 대해서는 설명하지 않았습니다. 독자는 매개 변수가 어떻게 구성되어 있는지 추적하고 gtsam이 제공하는 솔루션을 확인할 수 있습니다. 단순한 포즈 그래프는 활용하기가 희박하기 때문에 여기서 약간의 차이가 있습니다.
마지막으로 gtsam 최적화 결과를 g2o 출력 파일로 변환하고 그림 11-9와 같이 g2o_viewer를 사용하여 이 결과를 볼 수도 있습니다.
그림 11-9 gtsam의 최적화 결과.
다음은 터미널 출력의 최적화 정보입니다.
[그림]
우리는 반복의 최대 횟수가 20으로 설정되었지만 gtsam이 5회만 반복 한 후에 알고리즘이 정복되었음을 발견했습니다. 마찬가지로 gtsam의 오류 정의가 g2o와 다르므로 오류 크기를 직접 비교하는 것은 별로 의미가 없습니다. g2o_viewer로 result_gtsam.g2 파일을 열고 최적화를 선택하면 g2o 측정 항목의 오류는 약 44,360이고 이는 Lie 대수 최적화를 사용한 이전 섹션의 결과와 일치하지만 gtsam의 반복 횟수는 적습니다.
불행히도 이 예제는 gtsam의 점진적인 특성을 반영하지 않습니다. g2 파일에서 노드와 가장자리를 시간순으로 정렬 한 다음 gtsam에 하나씩 차례로 배치하면 점진적 기능에 대해 더 잘 설명 할 수 있습니다. 우리는이 실험을 연습으로 두고 독자에게 건네줍니다.