SURF 알고리즘 설명
- Hessian Detector를 이용한 Blob 특징을 검출하고 특징 주변의 기술자를 생성
- 이미지 블러나 회전, 크기변형에 강한 특징
- view point의 변화나 조명 변화에 약한 특징이 있음
1. Hessian Detector를 이용한 Blob 특징 추출
1) Hessian Matrix
- 헤세 행렬은 다변수함수가 극값을 가질 때, 그것이 극대인지, 극소인지 판정할 때 사용한다.
- Hessian 행렬의 determinant를 구해 determinant의 값이 양수이고 eigenvalue가 둘다 음수 혹은 양수이면 관심점으로 판단
2. Descriptor (기술자 생성)
1) Dominant orientation
- Hessian Detector로 찾은 특징점에서 6s의 범위내 dx, dy 의 haar response를 구한다.
- 60도 범위내 Slinding window의 응답값을 구하고 값이 최대인 방향을 주방향으로 설정한다. 2) Feature Description (기술자 생성)
- 특징점 위치에서 20s x 20s 크기 윈도우롤 4x4 서브윈도우로 구분한다. 각 서브 윈도우에서는 가로, 세로 방향의 haar wavelet response 벡터를 구하는데 각 요소는 다음과 같다.
- 벡터로 표현된 Sub-Window의 4-Dimension는 전체 Window에서 64-dimension이 되며 이것이 SURF Descriptor이다.
- Feature의 특징구분을 위해 128 dimension의 Descriptor를 생성할 수 있는데 dx의 부호에 따른 ∑dy, |∑dy| 값을 각각 별개로 계산하는 방법으로 벡터 v의 차원을 늘인다. dy에 대해서도 동일한 방법을 적용하여 4차원에서 8차원으로 서브윈도우의 dimension을 변경한다.
3. Feature Matching
- Reference image [Ref]와 Input Image [input] 간 SURF 매칭
1) Ref와 Input간 SURF 추출
2) Ref와 Input의 SURF간 1:1의 매칭쌍 결정 (Nearest Neighbor Distance Ratio)
- Ref k번째 SURF에 대응하는 Inp의 SURF 찾기
Hessian Matrix의 Laplacian sign이 비교할 feature간 틀리면 비교하지 않는 방법으로 매칭 속도 개선
- Ref k번째 SURF와 가장 가까운 매칭된 Inp SURF를 l1이라 했을때 l2는 다음과 같다.
여기서 d는 매칭 SURF간 거리를 의미
- Ref와 Input 매칭쌍의 validation
- 불필요한 매칭쌍을 제거하였지만 아직까지 mismatching 이 다수 존재함
3) RANSAC 알고리즘으로 두 이미지간 기하 변형을 가장 표현한 SURF 매칭을 선정
- mismatching을 제거하고 두 이미지간 기하 변형 관계를 산출
- we use the ORSA algorithm, which combines the RANSAC [6] algorithm with hypothesis testing.
자료 출처
SURF
- http://vision0814.tistory.com/m/172
SURF matching
- http://www.ipol.im/pub/art/2015/69/
논문
[Bay 08] Bay, Herbert, et al. "Speeded-up robust features (SURF)." Computer vision and image understanding 110.3 (2008): 346-359.