(SLAM) Feature Detection & Matching 정리

Classical point matching pipline

1. Detect Keypoint

• 이미지에서 특징점 검출
• 이미지의 스케일 및 회전, 조명 변화에도 동일한 위치에서 검출되는 것이 목표

2. Extract Descriptor

• 이미지에서 각 특징점 주변의 정보를 설명하는 벡터 추출/생성

3. Keypoint Matching

• 두 이미지의 각각 Descriptor를 서로 비교하여 유사(correspondence)한 특징점을 매칭함

---

Feature Point Detectors

Moravec corner (1980)

• 최초의 범용 corner keypoint 검출기로, 이후 Harris Corner Detector 등의 발전된 방법의 기반이됨
• 픽셀 주변의 윈도우를 여러 방향으로 조금씩 이동시키면서 SSD(Sum of Squared Difference)를 이용하여 밝기 변화를 측정
• 여러 방향(보통 4방향 또는 8방향)에 대해 밝기 변화를 계산하고, 임계값 이상의 변화를 corner로 판단

Harris corner (1988)

• 모든 방향으로의 intensity 변화량을 연속적으로 분석해서 코너를 판별함
• Moravec의 이산 방향 비교를 개선하여 gradient 기반의 2차 형태(quadratic form) 로 일반화함
• Corner-ness score 계산을 기반으로 flat, edge, corner 영역을 정의할 수 있으며, 최신 알고리즘에도 널리 응용됨

SIFT (2002)

• 딥러닝 기반 검출기가 나올 때 까지 가장 정확하고 안정적인 local feature detector
• scale, rotation, illumination 변화에 강인한 feature point + descriptor 생성 알고리즘
• 이미지의 스케일 별 DoG(Difference of Gaussian)의 결과를 이용하여 keypoint를 추출함
• 대상 픽셀 주변 16x16 영역에 대한 gradients 정보를 128차원 벡터로 추출함 → 매칭 성능이 좋지만 연산량 증가

FAST (2006)

• 매우 빠른 corner detector로 Harris corenr의 17배, SIFT의 42배 속도
• SIFT/Harris와 달리 수학적 최적화보다 결정 트리 기반의 빠른 판별이 핵심이며, 중심 픽셀을 기준으로 원형 주변 픽셀들이 연속적으로 밝거나 어두우면 코너로 판단함
• 대상 픽셀을 중심으로 주변에 반지름 3의 원을 잡고 16개 픽셀을 검사함. 처음 일부 위치만 빠르게 검사하는 early rejection 등을 이용하여 매우빠른 속도로 코너 후보를 추출하고, 후처리(NMS)를 통해 local max만 남김

BRIEF (2010)

• 사전 정의된 패턴을 이용해 patch의 형태를 빠르게 담은 binary descriptor
• SIFT의 descriptor는 성능이 뛰어나지만, FP 연산으로 인해 메모리 비용이 높고 속도가 느림
• keypoint 주변 패치 내에서 미리 정의된 픽셀 쌍들의 밝기를 비교해서 0또는 1의 비트열로 특징을 표현하여 descriptor 생성 (a < b =1 else 0, 보통 128bit 이상 구성)
• 매칭 시에는 일반적인 L2 distance 대신, hamming distance 기반 norm 연산
  • 두 descriptor의 비트 값을 순서대로 비교하여, 서로 다른 값의 비트의 개수가 곧 distance

Bucketing (2010)

• 이미지 전체에 고루 local feature를 검출하기 위해 이미지를 일정한 grid로 나누고, 각 영역마다 상위 N개를 선택하는 등, feature 개수를 제한하는 기법 (ORB-SLAM에서 사용)
• FAST, SIFT 같은 detector를 그대로 쓰면 특징점이 texture 많은 영역에만 몰림 → feature 분포 불균형 → 안정성 저하
• 공간적 균일성을 확보하기 위한 SLAM/VO 에서는 필수

ORB (2011)

• FAST detector + BRIEF descriptor를 결합하면서, scale과 rotation 문제를 해결한 실용적 feature detection & matching 알고리즘 (SIFT 수준의 강인성을 최대한 유지하면서, 속도는 binary 기반으로 극단적으로 끌어올린 것)
• scale invariant를 위해 Image pyramid 기반 여러 scale에서 FAST를 수행함
• rotation invariant를 위해 keypoint 주변의 intensity centroid(밝기 분포의 무게중심) 로 방향 θ를 추정하고, BRIEF의 픽셀 비교 패턴을 θ만큼 회전(rotated-BRIEF)하여 descriptor를 생성함

intensity centroid 계산

물리에서 질량과 무게중심의 위치 관계는 아래와 같다. $C=\frac{{\sum }_i(r_i\times m_i)}{{\sum }_i(m_i)}$

• $C$ : 무게중심의 위치(원점으로 부터)
• $r_i$ : 기준위치(원점)로부터 $i$ 위치의 거리
• $m_i$ : $i$ 위치의 질량

2차원(x, y) 이미지에서 밝기값(질량)이 다음과 같을 때 x축과 y축 각 centroid를 아래와 같이 구할 수 있다.

10 20 30
10 20 30
10 30 50

3x3 행렬의 가운데를 원점(0, 0) 으로 함

(-1,-1) (0,-1) (1,-1)  
(-1,0) (0,0) (1,0)  
(-1,1) (0,1) (1,1)

총 밝기 ($m_{00}$)
$m_{00}=\sum I(x,y)=210$ x 방향 모멘트 ($m_{10}$)
$m_{10}=\sum xI(x,y)$ $-1\cdot (10+10+10)+$ $0\cdot (20+20+30)+$ $1\cdot (30+30+50)=$ $m_{10}=-30+0+110=80$ y 방향 모멘트 ($m_{01}$)
$m_{01}=\sum xI(x,y)$ $-1\cdot (10+20+30)+$ $0\cdot (10+20+30)+$ $1\cdot (10+30+50)=$ $m_{01}=-60+0+90=30$ Centroid 계산
$C_x=\frac{m_{10}}{m_{00}}=\frac{80}{210}=0.38$ $C_y=\frac{m_{01}}{m_{00}}=\frac{30}{210}=0.14$ $C_{xy}=(0.38,0.14)$ 방향(각도) 계산
$\theta ={\tan }^{-1}\left(\frac{m_{01}}{m_{10}}\right)={\tan }^{-1}(0.375)=20.5°$

AKAZE (2013)

• 비선형 scale-space를 사용하는 고성능 feature detector + descriptor 알고리즘으로, SIFT의 정확도와 ORB 계열의 속도 사이를 현실적으로 타협한 구조 (SIFT와 ORB 사이 성능)
• SIFT와 ORB는 gaussian 방식을 사용하였고, A개념KAZE는 non-linear diffusion 방식으로 edge는 유지하면서 필요한 부분만 부드럽게 해서 특징을 찾을 수 있음

FLANN (2014)

• 고차원 feature descriptor를 빠르게 매칭하기 위한 근사 최근접 탐색(ANN) 라이브러리로, 핵심은 정확한 최근접(NN)이 아니라, “충분히 가까운” 이웃을 훨씬 빠르게 찾는 것
• SIFT에서 128D float vector, ORB에서 256-bit binary 를 매칭하려면 모든 벡터 쌍을 비교해야한다 (Brute-force: $O(N^2)$)
• FLANN은 정확한 NN을 포기하고, 빠른 근사 NN을 찾는 방법으로 여러 ANN 알고리즘이 자동 선택되어 사용할 수 있음
• 대표 알고리즘으로 float descriptor 용으로 KD-Tree, 매우 큰 데이터셋에 유리한 Hierarchical K-Means, binary discriptor 를 위한 Locality Sensitive Hashing(LSH) 등이 있다
• SIFT + FLANN(KD-Tree/K-Means), ORB + FLANN(LSH)

HBST (2018)

• binary descriptor(ORB, BRIEF)를 매우 빠르게 매칭하기 위한 트리 기반 최근접 탐색 구조
• Hamming distance를 직접 계산하지 않고, 각 비트를 기준으로 분기하는 이진 트리를 만들어 탐색 공간을 줄이는 것 ($O(\log N)$)

HBST 트리 생성 예시

다음 5개의 binary discriptor에 대해 트리 생성 예시

A: 1 0 1 0 
B: 1 1 1 0 
C: 0 0 1 1 
D: 0 1 0 1 
E: 1 0 0 1

1. bit index 0 기준 분기

왼쪽 (bit0 = 0) : C, D
오른쪽 (bit0 = 1) : A, B, E

2. 이를 모든 bit index에 반복하면 아래와 같은 최종 트리 구조

            [bit0]
          /      \
     [bit1]      [bit1]
     /   \       /    \
    C     D   [bit2]   B
              /   \
             E     A

3. 새로운 descriptor가 들어오면

Q : 1 0 1 1

전체를 각각 비교할 필요없이 3번의 bit 체크로 A과 같은 위치에 도달함

ANMS (2018)

• Bucketing 기법보다 발전된 feature 분포 조절 방법으로, 단순 grid 방식이 아닌 거리를 기반으로 주변에 더 강한 feature가 있는지 비교하여 선별하는 방법
• 각 후보 포인트는 자신보다 강한 포인트와의 거리(r)를 계산하고, 그 거리 중 최소값이 큰 포인트일수록 우선적으로 선택됨

SuperPoint (2018)

• 딥러닝 기반으로 keypoint detection과 descriptor를 동시에 수행하는 end-to-end 모델로, 라벨 없이(self-supervised) 학습하면서도 SIFT/ORB 를 대체할 수준의 성능을 보임
• 하나의 CNN 구조로 keypoint 위치 + descriptor를 동시에 예측하는 self-supervised feature extractor
• 초기 detector인 MagicPoint를 학습하기 위해 여러 다각형 도형의 코너를 자동 라벨링한 데이터를 생성함 (synthetic 데이터)
• 이후 실제 이미지 데이터를 MagicPoint를 통해 feature를 추출하고, 추가로 homography 기반 warping을 통해 이미지를 변환하고 pseudo label 을 생성하여 학습에 사용함
• MagicPoint는 “코너의 본질을 학습하는 단계”, SuperPoint는 “실제 환경에 맞게 refinement하는 단계”

SuperGlue (2020) & LightGlue (2023)

• keypoint와 descriptor를 입력으로 받아 GNN 기반으로 feature matching을 수행하는 방법
• 각 이미지의 keypoints 를 노드로하는 두 이미지에 대한 그래프를 구성하여 global context-aware matching 을 학습함

---

참고

• Visual SLAM을 위한 feature detection 1시간 마스터 - YouTube
• 모라벡(Moravec) 알고리즘 · Monch
• 다크 프로그래머 :: 영상 특징점(keypoint) 추출방법
• Exploring Correlations in Images with SIFT and FLANN: An Efficient Approach to Feature Matching | by Lucas Massucci | Medium
• Computer Vision - Corner Detection
• [Computer Vision-04] Corner Detection