[OpenCV] SIFT, SURF에 대한 간단 설명

SIFT(Scale-Invariant Feature Transform)

이미지의 크기와 회전에 불변하는 특징을 추출하는 알고리즘

 

알고리즘

1. 가우시안 피라미드 생성
2. DOG 피라미드 생성
3. 극점 검출
4. 약한 극점 제거하고, 나머지를 키포인트(특징점)로 삼음
5. 키포인트 orientation(방향) 계산
6. 키포인트 descriptors(기술자) 계산

 

1. 가우시안 피라미드 생성

한 옥타브 내에선 토대 영상을 점진적으로 가우시안 스무딩

다음 옥타브는 이전 옥타브의 4번째 영상을 가로, 세로 1/2배씩 한 것을 토대 영상으로

 

가우시안 피라미드 생성

 

2. DOG 피라미드 생성

같은 옥타브 내에서 인접한 두 개의 가우시안 스무딩 이미지들을 빼주는 것

 

DOG

 

3. 극점 검출

극대값, 극소값 위치 찾음

극점 검출

 

동일한 옥타브 내에 연속된 3장의 DOG 이미지 필요

현재 픽셀 주변 8개 픽셀, 위·아래 각각 9개 픽셀, 총 26개 픽셀 검사

현재 픽셀이 26개의 이웃 픽셀 중 가장 크거나 작을 때 극점.

but, 실제 극값은 픽셀과 픽셀 사이에 위치할 가능성이 있어 이는 대략적인 것.

→ taylor expansion - 극점 위치 미세조정

 

4. 약한 극점 제거, 나머지를 키포인트(특징점)로 삼음

제거 기준

1. 낮은 대비(contrast) : DOG 이미지에서 키포인트들의 픽셀 값이 threshold보다 작으면 제거
2. 엣지(edge): 키포인트에서 수직, 수평 변화량 계산 → 한쪽 방향으로만 변화가 크면 엣지로 간주하고 제거

                          ∵ 엣지 위에 있는 극값들은 노이즈일 가능성이 높음 → 코너 점들만 키포인트로 사용

 

약한 극점 제거

 

5. 키포인트 orientation(방향) 계산

키포인트에 orientation을 할당 → 회전 불변성 만족

현재 키포인트 주변의 그레디언트 크기에 따른 히스토그램 생성

 

그레디언트 크기에 따른 히스토그램 생성

 

윈도우 내의 모든 픽셀에서 그레디언트 방향의 값을 bin에 채움

가장 빈도 수가 높은 orientation을 찾아내서 키포인트의 방향으로 할당

 

6. 키포인트 descriptors(기술자) 계산

각 키포인트들은 구별될 수 있어야 함

→ 키포인트 주변의 모양 변화에 대한 경향을 파악하여 128개의 숫자로 표현

1. 키포인트 주변 16x16 윈도우 세팅, 이 윈도우는 16개의 4x4 윈도우로 구성
2. 16개의 4x4 윈도우 내에서 픽셀들의 그레디언트 계산(8방향 - 8개 bin을 가진 히스토그램)
3. 16개의 윈도우 각각 8개의 bin값이 있으므로, 16x8=128 개의 숫자
4. 회전 의존성을 해결하기 위하여 각각 그레디언트 방향 - 키포인트 방향

→ 각각 키포인트 구별 가능

 

키포인트 descriptors(기술자) 계산

 

 

SURF(Speeded Up Robust Features)

SIFT 알고리즘보다 속도 향상, 성능 비슷

알고리즘

1. 키포인트 추출
2. 키포인트 orientation(방향) 계산
3. 키포인트 descriptors(기술자) 계산

 

1. 키포인트 추출

적분 영상(Integral Image) 사용

적분 영상을 이용하여 특정 영역의 밝기 부분합 구하기

→ 특정 영역의 밝기 부분합을 구할 수 있음

 

if ) D 영역의 밝기 부분합을 알고 싶다

→ D = ii(d) + ii(a) - ii(b) - ii(c) (ii(x): x에서 적분 영상 값)

 

빨간 사각형의 밝기 부분합 = 21 + 4 - 11 - 11 = 3

밝기 부분합 구하기

 

Fast Hessian Detector 사용 → 특징점 검출

D_xx, D_yy, D_xy 에 근사화한 박스필터 사용 → 헤이시안 행렬식

 

헤이시안 행렬식

 

→ 각 필터 사이즈 별로 특징점 검출 = 여러 스케일에서 특징점 검출과 동일한 효과

 

2. 키포인트 orientation(방향) 계산

특징점이 검출된 스케일 정보 s를 이용, 반지름 6s의 원 안의 픽셀에 대하여 x, y 방향으로 그레디언트 계산

→ 가장 큰 크기를 가지는 방향을 주 방향으로

 

3. 키포인트 descriptors(기술자) 계산

특징점이 검출된 스케일 정보 s를 이용, 반지름 20s 크기의 윈도우 구성

16개의 4x4 윈도우로 분할 , 이를 각각 5x5 윈도우로 분할, haar wavelet filter 사용

→ 64개의 정보를 가진 descriptors(기술자) 생성

 

키포인트 descriptors(기술자) 계산