[영상처리] SIFT 알고리즘

SIFT

David Lowe가 제안한 불변성 특징점 검출 알고리즘으로 크기, 회전, 위치 변화에도 강건한 키포인트를 추출해 비교할 수 있습니다.

주요 흐름

1. scale-space 생성

• 다양한 크기에서 특징점을 찾기 위해 이미지 피라미드 생성
• 블러 처리를 여러번 적용한 이미지들 구성
• DoG를 이용해 계산 (이를 통해 LoG 근사값 도달 가능)

2. 키포인트 후보 검출

• 키포인트 : 이미지 내 반복적으로 검출되는 두드러진 점
• DoG 이미지에서 국소 극점 검출
• 현재 픽셀이 주변 픽셀보다 극대/극소이면 키포인트 후보가 됨

3. 키포인트 정제

• 잡음 제거 및 대응 불가능한 점 제거

4. 방향 할당 및 특징 벡터 생성

• 특징 벡터 : 키포인트를 중심으로 잘라낸 이미지 조각을 벡터로 생성한 것
• 각 키포인트에 dominant orientation 적용해 회전 불변성 확보
• 주변 gradient를 기반으로 128차원 특징 벡터 생성

dominant orientation

• 히스토그램에서 가장 큰 값을 가지는 방향을 keypoint의 기본 방향으로 설정
• 최고 방향의 80% 이상인 다른 지역 존재 시 방향 추가
• 이런 과정을 통해 회전된 이미지에서도 동일한 키포인트 검출 가능

특징 벡터 비교

각 특징 벡터는 128차원으로 유클리드 거리로 비교해 유사도를 판단한다.
이를 통해 가까운 벡터끼리 매칭하는 것이다.

Homography

SIFT로 추출한 키포인트를 기반으로 이미지 간 좌표 변환 행렬을 계산할 수 있다.

• 4쌍 이상의 키포인트 매칭 필요
• 선형 방정식 세운 뒤 SVD 사용해 호모그라피 계산

RANSAC

무작위 샘플링을 통해 데이터 사이의 합의를 지키지 않는 이상치를 제거하는 알고리즘이다.

1. 4쌍의 매칭 무작위 선택
2. 호모그라피 계산
3. 이 행렬을 만족하는 inliers와 그렇지 않은 outliers 구분
4. inliers 수가 만족될 때까지 혹은 미리 정한 횟수만큼 반복
5. inliers 수가 만족되면 물체 인식 성공
6. 미리 정한 횟수에 도달하면 물체 인식 실패
7. 최종적으로 inlier만 사용해 호모그라피 재계산