Keypoint Detection

1. Keypoint의 개념과 중요성

• Keypoint(키포인트): 이미지에서 특징적인 위치를 나타내는 점으로, 특정 위치(산봉우리, 건물 모서리, 입구 등)나 독특한 패턴이 있는 지점
• 활용 분야:
  • 서로 다른 이미지에서 상응하는 위치 찾기(카메라 포즈 계산 선행 작업)
  • 다른 이미지 정렬(image mosaics 생성, 비디오 안정화)
  • 객체 인식 및 분류
• 장점: 잡음(clutter)이나 가림(occlusion), 큰 스케일과 방향 변화에도 매칭이 가능함

2. Harris Corner Detector

2.1 기본 원리

• 작은 창(window)을 통해 점을 인식하고, 모든 방향으로 창을 이동했을 때 큰 반응 변화가 있는 지점 탐색
• 구조 행렬(structure matrix) M의 고유값(eigenvalues) λ₁, λ₂를 기반으로 판단

2.2 수학적 접근

• 이미지 이동에 따른 강도 변화: E(u, v) = Σ w(x, y)[I(x+u, y+v) - I(x, y)]²
• 테일러 확장과 행렬 연산을 통해: E(u, v) ≈ [u v] M [u v]ᵀ
• 여기서 M = Σ w(x,y) [Ix² IxIy; IxIy Iy²]
  • Ix: x방향 미분, Iy: y방향 미분

2.3 코너 응답 함수(Corner Response)

• R = det(M) - k × trace(M)² = λ₁λ₂ - k(λ₁+λ₂)²
  • k: 조절 파라미터(일반적으로 0.04~0.06)
• 응답 해석:
  • R > 0: 코너(corner)
  • R < 0: 에지(edge)
  • |R| 작음: 평평한 영역(flat region)

2.4 특성

• 불변성(Invariant): 밝기 오프셋, 이동(shift), 회전(rotation)에 불변
• 한계: 스케일 변화에 불변하지 않음

3. SIFT(Scale Invariant Feature Transform) Detector

3.1 개요

• Lowe에 의해 제안된 스케일, 회전, 밝기 변화, 시점 변화에 강인한 특징점 추출 방법

3.2 주요 단계

1. 스케일 공간 구성(Scale space construction)

   • 가우시안 커널을 이용해 여러 스케일에서의 이미지 생성
   • 옥타브(octave)별로 구성: 각 옥타브는 다른 스케일 σ 사용

2. DoG(Difference of Gaussian) 계산

   • 인접한 가우시안 이미지 간의 차이 계산
   • 에지 검출에 사용되는 방법으로, 스케일 공간에서 픽셀 값 변화 탐지

3. Local Extrema 검출

   • 3x3x3 블록 내에서 DoG 이미지의 극값(local extrema) 찾기
   • 주변 26개 이웃 픽셀과 비교하여 최대값 또는 최소값인 픽셀을 특징점 후보로 선정

4. 불안정한 키포인트 제거

   • 대비(contrast)가 낮은 점이나 에지 위의 점 제거

5. 방향(Orientation) 할당

   • 각 키포인트에 지역 이미지 그래디언트를 기반으로 방향 할당
   • 회전 불변성 확보

6. 디스크립터(Descriptor) 생성

   • 키포인트 주변 영역을 4x4 영역으로 나누고, 각 영역에서 8방향 그래디언트 히스토그램 계산
   • 128(8x4x4) 차원의 디스크립터 벡터 생성

3.3 이미지 매칭

• 유일성(uniqueness)에 초점을 맞춘 특징점 매칭
• 최근접 거리(d₁)와 차근접 거리(d₂)의 비율(d₁/d₂)이 임계값(보통 0.49) 이하일 때 매칭 성공

3.4 특성

• 스케일, 회전, 밝기 변화, 시점 변화에 강인함
• 다양한 파라미터가 성능에 영향을 미침

4. SURF(Speeded Up Robust Features) Detector

4.1 개요

• SIFT의 변형으로, 속도를 크게 향상시킨 방법
• 적분 이미지(integral image)와 박스 필터(box filter)를 사용하여 계산 가속화

4.2 주요 단계

1. 적분 이미지 계산

   • 효율적인 박스 필터 연산을 위한 전처리

2. Hessian 행렬 결정자(Determinant) 계산

   • 2차 가우스 커널 대신 박스 필터로 근사화
   • det(Happrox) = Dxx * Dyy - ω * Dxy² (ω = 0.83)

3. 결정자 응답 정규화

   • 스케일에 따른 응답 정규화

4. Non-maximal Suppression과 임계값 적용

   • 26개 이웃 내에서 최대값 찾기
   • 임계값으로 필터링

5. 관심점(interest point) 방향 계산

   • 하르 웨이블릿(Haar wavelet) 응답을 이용한 방향 할당

6. 관심점 디스크립터 계산

   • 주요 방향을 따라 20σ 크기의 영역에서 계산

4.3 특성

• 스케일과 회전에 불변
• 다양한 시점 변화에 덜 민감
• 주로 단일 객체 검출에 사용
• SIFT보다 빠른 처리 속도

5. LIFT(Learned Invariant Feature Transform) Detector

5.1 개요

• 딥러닝 기반 특징점 추출 방법
• 전체 특징점 처리 파이프라인을 구현하는 심층 신경망 아키텍처

5.2 주요 구성 요소

1. Detector(검출기)

   • 이미지에서 특징점 위치 검출

2. Orientation Estimator(방향 추정기)

   • 특징점의 방향 계산

3. Descriptor(디스크립터)

   • 특징점의 주변 정보를 벡터로 표현

5.3 성능

• 다양한 데이터셋에서 기존 방법들보다 우수한 매칭 성능
• 특히 Strecha, DTU, Webcam 데이터셋에서 높은 매칭 점수 기록

6. 시험 대비 핵심 요약

키포인트 탐지기 비교

탐지기	기본 원리	특징	장단점
Harris	구조 행렬 M의 고유값	코너 응답 R = det(M) - k×trace(M)²	+ 회전, 이동 불변- 스케일 변화에 취약
SIFT	DoG와 스케일 공간	128차원 디스크립터	+ 스케일, 회전, 밝기 변화에 강인- 계산 비용 높음
SURF	Hessian 행렬과 박스 필터	Haar 웨이블릿 사용	+ SIFT보다 빠름+ 스케일, 회전 불변- 복잡한 변형에 SIFT보다 약함
LIFT	딥러닝 기반	전체 파이프라인 학습	+ 높은 매칭 성능- 학습 데이터에 의존적

객관식 문제 대비 핵심 개념

1. Harris detector

   • 코너 응답: R = det(M) - k×trace(M)²
   • 평평한 영역(flat): 모든 방향으로 변화 없음 (λ₁≈λ₂≈0)
   • 에지(edge): 에지 방향으로 변화 없음 (λ₁>>λ₂ 또는 λ₂>>λ₁)
   • 코너(corner): 모든 방향으로 상당한 변화 (λ₁, λ₂ 모두 큼)
   • 회전, 이동에는 불변하지만 스케일 변화에는 불변하지 않음

2. SIFT detector

   • 스케일 공간: σ는 가우시안 커널의 표준편차
   • DoG(Difference of Gaussian): 인접 가우시안 이미지의 차이
   • 로컬 익스트리마(Local Extrema): 3x3x3 블록 내 최대/최소값
   • 디스크립터: 8방향 그래디언트 히스토그램(8×4×4=128차원)
   • 매칭 기준: d₁/d₂ < 0.49 (최근접 거리/차근접 거리)

3. SURF detector

   • 적분 이미지와 박스 필터로 속도 개선
   • Hessian 행렬 결정자: det(Happrox) = Dxx * Dyy - ω * Dxy²
   • Haar 웨이블릿을 이용한 방향 및 디스크립터 계산
   • 일반적으로 64차원 디스크립터 사용

4. LIFT detector

   • 딥러닝 기반 접근법
   • 검출기, 방향 추정기, 디스크립터 세 가지 주요 구성요소
   • 전체 특징점 처리 과정을 학습을 통해 최적화

주요 암기 사항

• Harris detector의 코너 응답 공식과 고유값 해석
• SIFT의 4단계 알고리즘과 DoG 개념
• SURF에서 사용하는 적분 이미지와 박스 필터의 역할
• 각 방법의 불변 특성(invariance) 비교
• 특징점 디스크립터의 차원: SIFT(128), SURF(64 또는 128)
• 특징점 매칭에서 유사도 측정 방법(L2 거리 등)
• 스케일 공간(Scale space)의 개념과 구성 방법