Search
✅

SURF Algorithms

링크
Category
Vision Study
Keywords
SIFT
SURF
상위 개념
하위 개념
속성
Subcategory
개념 정리
날짜

Speed Up Robust Feature

•
순서는 SIFT와 유사
1.
KeyPoint Localization
2.
Orientation Assignment
3.
Descriptor
•
SIFT에 비해 향상된 속도
•
Keyword
◦
Box Filter
◦
Fast Hessian Detector
◦
Integral Image _ 적분 이미지

Keypoint Localization

•
SIFT의 방법 : Image Resolution Scale을 다르게 해서 DoG를 통해 Feature 추출
Integral Image 생성을 한다.
II∑(x,y)=∑i=0x∑j=0yI(i,j)II_{\sum}(x,y) = \sum_{i=0}^x \sum_{j=0}^y I(i,j)
Integral Image는 픽셀 값을 누적해서 더한 값이다.
B = A+B에 해당하는 면적, C=A+C에 해당하는 면적, D=ABCD에 해당하는 면적
ii(1)=Aii(1) = A
ii(2)=A+Bii(2) = A + B
ii(3)=A+Cii(3) = A + C
ii(4)=A+B+C+Dii(4) = A + B + C + D
D=ii(4)−ii(3)−ii(2)+ii(1)D = ii(4) - ii(3) - ii(2) + ii(1)
1
2
3
4
5
6
7
8
9
1
3
7
5
12
21
12
27
45
위와 같은 이미지가 있을 때, 빨간 곳 픽셀의 부분합을 구하고 싶으면 오른쪽의 integral image에서
45 - 12 - 7 + 1 이런 식으로 구하면 된다.
이거를 어떻게 활용하느냐?
일단 이 알고리즘에서도 Hessian Matrix를 활용해서 Edge 검출을 하는데 그 식이 조금 다르다.

Fast Hessian Detector

H(p,σ)=[Lxx(p,σ)Lxy(p,σ)Lyx(p,σ)Lyy(p,σ)],p=(x,y), σ=scaleH(p,\sigma) = \begin{bmatrix}L_{xx}(p, \sigma) & L_{xy}(p, \sigma)\\L_{yx}(p, \sigma)&L_{yy}(p, \sigma)\end{bmatrix}, p = (x,y), ~ \sigma=scale
이 L(ρ,σ)L(\rho, \sigma) 함수를 구하기 위해 integral image가 사용이 된다.
Lxx(p,σ)L_{xx}(p,\sigma), Lyy(p,σ)L_{yy}(p,\sigma), Lxy(p,σ)L_{xy}(p,\sigma)를 통한 방식은 SIFT의 DoG의 방식과 차이가 나는데
여기서는 Box Filter를 통해 LoG에 근사시키는 방식을 이용한다.
이 방식의 장점은 Integral Image → Box Filter를 통해 Convolution을 쉽게 사용할 수 있다는 점이다.
일단 아래의 그림을 보면 각 Box Filter가 있다.
Lxx, Lyy : Gaussian Smoothing 적용 후 x,y에 대해 2번 미분한 연산자
Lxy : GS 적용 후 x에 대해 한번 y에 대해 한번 미분한 연산자
근데 SURF에선 해당 연산자를 근사시켜서 사용
이미지에 해당 Box를 씌워서 각 픽셀의 integral image 값에 1, -1, -2를 곱하며 연산을 한다. 검은 부분이 음수값
Dyy=α∗1+β∗1−2∗γD_{yy} = \alpha * 1 + \beta * 1 -2*\gamma
Dxx=α∗1+β∗1−1∗γD_{xx} = \alpha * 1 + \beta * 1 -1 *\gamma
Dxy=α∗1+β∗1−1∗γ−1∗δD_{xy} = \alpha * 1 + \beta * 1 - 1*\gamma -1*\delta
H(p,σ)=[Dxx(p,σ)Dxy(p,σ)Dyx(p,σ)Dyy(p,σ)],p=(x,y), σ=scaleH(p,\sigma) = \begin{bmatrix}D_{xx}(p, \sigma) & D_{xy}(p, \sigma)\\D_{yx}(p, \sigma)&D_{yy}(p, \sigma)\end{bmatrix}, p = (x,y), ~ \sigma=scale
이 식의 행렬식은 아래와 같다.
det(H)=DxxDyy−(wDxy)2det(H) = D_{xx}D_{yy} -( w D_{xy})^2
이고 논문에서 weight는 0.9로 설정을 했다.
det값이 양수, 고유값이 둘다 양수 또는 둘다 음수이면 해당 좌표는 keypoint가 된다.
SIFT에서는 이미지의 scale을 다르게 해서 연산을 했지만
SURF에서는 Box filter의 scale을 다르게 해서 연산을 한다.
한 옥타브 내에서 9x9 → 15x15 → 21x21 → 27x27, 15x15 → 27x27 → 39x39 → 51x51 처럼 4번 scale up을 진행한다.

Orientation Assignment

위에서 찾은 어떤 크기 공간 내 Keypoint 들 중에서 최대값을 다시 가려내고
이 점들에 대해 Haar Wavelet response를 적용한다
위 그림의 파란 점들이 point 주변(6 scale : 반지름 6pixel..?) 내에서 원 안의 값에 대해 x,y 축에 대해 response 값을 구하고 분포를 나타낸 것이다.
60도 정도의 부채꼴 모양을 슬라이딩하면서 해당 범위 내 분포의 합을 벡터로 표현한 것이 빨간 벡터이고
계속 슬라이딩 하면서 해당 범위 내의 가장 큰 값이 Orientation. 주방향이 된다.

Descriptor

keypoint를 기준으로 20 scale만큼 범위를 잡고. 위에선 구한 Orientation에 맞게 window를 회전 시킨다.
그리고 20x20 window를 4x4로 나뉜 뒤, 다시 각 region를 5x5로 나눈다.
그러고 각 region에 대해 haar wavelet response를 구한다.
4x4로 나눈 각 region에 대해 vector=(∑dx,∑dy,∑∣dx∣,∑∣dy∣)vector = (\sum d_x, \sum d_y, \sum |d_x|, \sum |d_y|) 가 생기고
총 64 차원의 descriptor를 가질 수 있다.