Loop Closure and Detection

• Loop Closure의 중요성

  

  • Frontend: trajectory/landmarks estimation
  • Backend: 위 데이터들 최적화
  • 인접 frame들의 관계만 고려하는 알고리즘의 경우, 생성된 에러들이 누적됨 → 장기적으로 estimation에서의 부정확한 결과, 전체적으로 일관되지 않은 결과가 나타남
  • Solution: Loop closure detection

    • provide long-term constraint

      → e.g., 순서상 멀리 떨어져 있는 노드인 $\mathrm{x}1$과 $\mathrm{x}{100}$ 사이의 pose constraint 계산 가능

    • 카메라가 이미 지나온 같은 장소를 지날 때, 유사한 데이터를 수집

    • Better closure detection → Better input to backend pose graph → better output

    • 전체 SLAM의 정확성/견고성 향상

  • VO: frontend + local backend
  • V-SLAM: VO + loop closure/global backend

• Loop Closure의 작동 방식

  • 방법1 - feature matching on any image pairs

    1. 어떤 이미지 쌍에 대해, feature matching을 수행
    2. 얼마나 correct match가 많은지에 따라, 실제로 유사한지 확인

    • 단점

      → 비교할 임의의 두 이미지가 쌍이 많아지면 연산량이 커짐 → $O(N^2)$

      → trajectory가 길어지면 real-time system에 적합하지 않음

  • 방법2 - Random sample

    • 과거 데이터를 임의로 추출하고 loop detection을 랜덤하게 수행
    • 예: $N$개의 frame 중에서 5개의 frame을 무작위로 선택하여 현재 프레임과 비교
    • 단점: 연산시간은 고정되지만, frame 수 $N$이 증가하면 loop를 감지할 확률이 현저히 낮아져 검출 효율성이 떨어짐

  • 방법3 - odometry-based

    • 기하학적 관계를 활용함 (누적 odometry error가 매우 작음이 가정으로 깔려있음)
    • 현재 카메라가 이전 위치 근처의 위치로 이동하면, 관계가 있는지 여부 파악
    • 단점: drift error 누적이 클 경우 부정확함

  • 방법4 - appearance-based

    • 두 이미지의 유사성을 기반으로 Loop closure detection 관계 결정

    • 이미지의 유사성 계산식 정의

      

    • 단점

      1. 주변 조명과 카메라 노출에 의해 영향을 많이 받음
      2. 카메라의 작은 화각의 변화에 따라 물체의 pixel 값을 바꾸어 큰 차이 값 초래

      → 실제로는 매우 유사한 이미지의 경우에도, $\bold{A-B}$는 위와 같은 이유로 큰 값을 얻음

      (= 이미지들 사이의 유사성을 잘 반영하지 않음)

• Precision and Recall

  • Loop closure detection의 Classification

    

    • Example

      

      → False Positive: 비슷해 보이는 다른 복도지만, loop로 판단해버림

      → False Negative: 같은 장소이지만, 조명 때문에 loop가 아님으로 판단해버림

    • 목표: High TP, TN / Low FP, FN

  • Loop closure detection 알고리즘의 성능 평가

    

    • Precision: 감지된 모든 loop들 중, 실제로 진짜 loop일 확률

    • Recall: 모든 실제 loop(정답)들을 정확하게 감지될 확률

    • 대개 Precision과 Recall은 상보적인 관계임

      → 엄격한 알고리즘 (높은 threshold) → 적은 loop 검출 → Precision 향상 / Recall 감소

      → 느슨한 알고리즘 (낮은 threshold) → 많은 loop 검출 → Recall 향상 / Precision 감소

    • Precision-Recall curve

      

      precision-recall curve

      → 알고리즘의 품질을 평가하기 위해, 다양한 매개 변수에서 Precision과 Recall 값을 테스트

      → 좋은 알고리즘은 높은 Recall에서 높은 Precision를 보장

Bag of Words

• Idea

  • 방법4처럼 두 이미지를 빼서 Loop를 감지하는 것은 다양한 이유로 안정적이지 못함
  • VO처럼 feature point를 사용해 loop를 감지하면 어떨까? → Bag-of-Words (BoW)

    • 하지만 단점도 존재

      → 단점1: feature matching은 시간 소요가 큼

      → 단점2: 조명 변화에 따라 feature description이 불안정함

• Bag-of-Words (BoW)

  • concept

    1. people, cars, dogs 같은 *“words”*의 개념을 통해 dictionary를 구성

    2. dictionary의 *“words”*를 통해 전체 이미지를 히스토그램으로 표현

       → 이 방법으로 이미지를 vector로 변환함

    3. 이미지들의 유사성을 비교

  • example

    1. 미리 정의된 dictionary에 word $w_1,w_2,w_3$가 있다고 가정

    2. 이미지 $A$에 대해, 포함된 word들은 아래와 같이 표현 가능

       

    3. dictionary는 고정되어 있으므로, 이미지 $A$를 vector $[1,0,0]^\mathrm{T}$로 정의 가능

       → 이미지를 하나의 벡터로 표현 가능 (이미지에 특정 feature가 있는지 표현)

       → feature가 있는지 없는지만 나타내므로, 공간적 위치와 순서에 대해 독립적

    4. 또 다른 이미지 $B$의 vector를 $[2,0,1]^\mathrm{T}$이라고 가정

       → feature가 나타났는지만 고려할 경우, $[1,0,1]^\mathrm{T}$로도 표현 가능

    5. $\mathcal{L_1}$ 정규화(elements의 절대 값의 합)을 통해, 이미지의 유사성을 비교

Structure of Dictionary

• BoW의 dictionary 생성문제 → 머신러닝의 clustering 문제와 비슷
• 위 문제를 개선한 Dictionary의 구조: k-d tree

Calculate the Similarity