공시야성 그래프 (Covisibility graph)

ORB-SLAM에서 두드러지게 도입된 **공시야성 그래프(covisibility graph)**는 키프레임에 대한 가중치가 있는 무방향 그래프이다:

이 그래프는 키프레임이 언제 어디서 생성되었는지와 무관하게 무엇이 무엇을 보는지를 인코딩한다. 같은 시점에서 몇 분 간격으로 촬영된 두 키프레임은 강하게 연결되어 있는 반면, 빠른 회전 중의 연속된 두 키프레임은 거의 연결되어 있지 않을 수 있다. 이 때문에 공시야성이 시각적 지도에서 시간이나 유클리드 거리보다 훨씬 더 나은 “이웃(neighbourhood)” 개념이 된다.

SLAM 시스템은 공시야성 그래프를 지속적으로 조회한다:

밀접하게 관련된 구조로 **필수 그래프(essential graph)**가 있다: 키프레임들의 신장 트리(spanning tree)로 이루어지며 여기에 고가중치 공시야성 엣지와 루프 클로저 엣지를 더한, 훨씬 더 희소한 부분 그래프이다. ORB-SLAM은 밀집한 공시야성 그래프 대신 필수 그래프에 대해 포즈 그래프 최적화를 실행하여, 완전한 최적화의 정확도 대부분을 훨씬 적은 비용으로 얻는다.

형식적 정의와 유지 관리

키프레임 KiK_i가 관측하는 지도점 집합을 Pi\mathcal{P}_i라 하자. 두 키프레임 간의 공시야성 가중치는 단순히

wij=∣Pi∩Pj∣,w_{ij} = \left| \mathcal{P}_i \cap \mathcal{P}_j \right|,

이며, 그래프는 wij≥θw_{ij} \geq \theta일 때 엣지 (i,j)(i, j)를 유지한다. 이는 포즈를 전혀 필요로 하지 않는다 — 관측에 대한 순수한 부기(bookkeeping)일 뿐이며 — 그래서 비용이 적고 점진적으로 갱신할 수 있다:

실제로 각 키프레임은 자신의 이웃들을 가중치 순으로 정렬하여 저장하므로, “가중치 상위 NN개의 공시야 키프레임”과 같은 쿼리(지역 BA 윈도우를 정의하거나 루프 후보를 확장하는 데 사용됨)는 O(1)O(1) 조회이다. ORB-SLAM 설계의 비대칭적인 임계값에 주목할 필요가 있다: 공시야성 그래프는 상대적으로 약한 엣지(θ≈15\theta \approx 15개의 공유 점)를 유지하는데, 이는 지역 매핑이 넉넉한 이웃으로부터 이득을 얻기 때문이고, 반면 필수 그래프는 강한 엣지만(θ=100\theta = 100) 유지하는데, 이는 포즈 그래프 최적화가 적으면서도 신뢰할 수 있는 제약을 원하기 때문이다.

왜 시간이나 거리가 아닌가?

대안들의 실패 모드를 제대로 이해해 둘 필요가 있다. 시간적 윈도우(최근 NN개의 프레임)는 카메라가 어떤 장소를 재방문할 때마다 깨진다: 같은 장면을 관측하는 오래된 키프레임들이 지역 BA에서 제외되어, 지도가 지역적으로 중복되고 드리프트를 일으킨다. 메트릭 이웃(반경 rr 미터 이내의 키프레임)은 방향에서 깨진다 — 반 미터 떨어져 있지만 반대쪽 벽을 향한 키프레임은 아무 관측도 공유하지 않으면서 비용만 더할 뿐이다 — 그리고 그 자체로 드리프트하고 있는 포즈 추정값에 의존한다. 공시야성은 이웃을 관측 공간에서 정의함으로써 이 두 문제를 모두 피한다: 정확히 같은 기하학을 제약하는 측정값을 가진 키프레임들만을 이웃으로 삼으며, 이는 정확히 지역 BA가 잘 조건화된 문제를 얻기 위해 필요한 집합이다.

흔한 함정

SLAM에서의 의미

공시야성 그래프는 특징점 기반 SLAM을 확장 가능하게 만드는 데이터 구조이다: 지역 BA의 비용을 제한하고, 지도점 탐색을 집중시키며, 루프 클로저 이후 빠른 전역 보정을 위한 희소한 골격(필수 그래프)을 제공한다. ORB-SLAM에서 도입된 이후, 이는 사실상 모든 후속 키프레임 기반 시스템(ORB-SLAM2/3와 그 수많은 파생 시스템을 포함)의 지도 관리에 영향을 미쳤다.

관련 문서