SURF(Speed-Up Robust Features)

SURF는 2008년 Herbert Bay가 제안한 방법입니다.

[Bay 08] Bay, Herbert, et al. "Speeded-up robust features (SURF)." Computer vision and image understanding 110.3 (2008): 346-359.

2004년 SIFT의 등장 이후 물체의 descriptor에 대한 관심이 높아진 이후로 많은 연구가 있었습니다.

SIFT의 최대 단점인 연산의 복잡성을 해소 하기 위한 방법으로 한때 많은 관심(성능)을 보인 

SURF 기술자를 정리해 봅시다.

위 논문에서는 SIFT 외에도 다른 방법들과 비교를 했지만 SIFT 못지 않게 성능을 유지하며 계산 속도를

향상 시키고자 했습니다.

그래서 속도 향상을 위해 제안한 방법을 요약하면 크게 총 3가지로 정리할 수 있습니다.

1. Integral Image(적분 이미지) 이용

 SURF에서는 SIFT와는 다르게 적분 영상을 사용하여 관심점과 영역을 찾습니다. 관심점 계산을 위해 

고속 헤시안 검출(Fast Hessian Detector)를 사용하는데, 이때 적분 영상을 사용합니다.

적분 영상이란 말 그대로 영상을 적분하는것을 말합니다.

적분이란? 고등학교 학생 때의 기억을 더듬어 보면 어떤 영역의 넓이를 구했던 것을 생각해 볼 수 있습니다.

그렇다면 영상의 적분이란 영상이 갖는 영역의 넓이(밝기의 합)을 구하는 것을 추론할 수 있습니다.

영상의 밝기의 합은 그냥 선형으로 영역을 계산하면 되지 않을까 생각하기 쉽지만 많은 영역을

n^2으로 계산하면 연산속도가 매우 느립니다. 따라서 적분 영상을 처음에 하나 만들어 두고 영상의 부분합을

구하면 빠른 속도로 계산할 수 있습니다.

그렇다면 영상의 Integral Image는 어떻게 계산할까요?

아래 그림을 보면 한눈에 이해 할 수 있습니다.

위 그림의 왼쪽 이미지는 기존 이미지를 의미하고, 오른쪽은 적분 이미지를 의미합니다.

적분 이미지는 (0,0)부터 현재 좌표점까지의 밝기값의 누적으로 계산할 수 있습니다.

만약 (1,1)를 구할때는 (0,0) + (0,1) + (1,0) + (1,1)의 총합을 (1,1)에 저장하면 됩니다.

영상의 적분 이미지를 생성해 두고 영상의 부분 합을 계한하려고 하면 

D = D + A - B - C

3번의 더하기 빼기로 영역의 밝기 부분합을 구할 수 있습니다.

빨강 부분에 관한 합을 적분 부분합 식을 이용하면

 D = 21 + 4 - 11 - 11 = 3 

를 빠른 속도로 계산할 수 있습니다.

2. 축소한 detector와 descriptor를 사용하여 빠른 (차원수 축소)

 관심점을 계산하기 위해 SURF는 헤시안(Hessian) 행렬을 사용합니다.

논문에서는 정확성이 좋고 determinant가 최대값인 위치의 blob 구조를 검출하기 위해서라고 나와 있습니다.

[그림출처 : http://www.quora.com/What-are-the-benefits-of-calculating-the-eigenvector-of-a-Hessian-matrix-in-image-processing]

 만약 determinant(행렬식)가 음수이고 eigenvalue가 서로 다른 부호이면 해당 좌표는 관심점이 아니고

determinant가 양수이고, eigenvalue가 둘 다 음수 혹은 양수이면 해당 좌표는 관심점으로 판단합니다.

SURF의 경우 2차 미분을 Gaussian을 사용하는데, Scale-space를 분석하는데 가우시안이 가장 최적이라고

판단하여 사용함을 논문에 명시하였습니다. 따라서 x,y,xy에 대한 헤시안 행렬을 계산하면 관심점(Interest Point)

로 판단합니다.

또한 가우시안 분포 헤시안 행렬을 계산할때 계산을 좀 더 단순화 시키기 위해 근사화한 Dxx와 Dyy 박스필터를 

사용합니다.

 위 사진과 같이 근사화한 박스 필터를 사용하므로써 적분이미지 계산으로 영역의 넓이를 빠르게 구하고 

구한 넓이로 헤시안 행렬을 계산해 관심점을 판단합니다.

논문에서 weight값은 0.9를 사용했습니다. 

 SURF도 스케일에 robust하기 위해 SIFT와 비슷하게 여러 스케일에서 관심점을 추출합니다. 

아래 그림을 보면 SIFT 필터 사이즈를 고정시키고, 이미지 사이즈를 줄여 관심점을 검출하는 반면, 

SURF는 SIFT와는 반대로 이미지 스케일을 고정시키고 필터 사이즈를 키워가며 관심점을 추출합니다.

SIFT와 다른 차이점을 둔 이유는 계산의 효율성 때문일 것 같습니다. 적분 이미지를 사용하기 때문에

위치를 변경하는것 만으로 필터 사이즈를 조절할 수 있기 때문입니다. 또한 down sampling하지 않기 

때문에 aliasing이 없는 장점이 있습니다.(scale invariance 가 제한적일 수 있음 - 단점)

아래 그림을 보면 3계의 옥타브가 있고 점점 스케일이 증가하는것을 확인할 수 있습니다. 

옥타브가 증가하면 필터 사이즈가 2배로 증가하는 것을 볼 수 있습니다.

(논문에서는 하나의 옥타브에 4번 scale up)

 

 선정한 관심점을 비 최대치 억제(non maximum suppression)을 통해 크기 공간에 대한 극대값(검출된 관심점)

을 선정합니다. 또한 이 극대값에 대해 보간법을 적용하여 보간된 관심점을 특징 벡터로 저장하여 사용합니다.

(Sub-Pixel로 보간)

 최종 보간된 관심점을 중심으로 6s(scale)의 원 안에 있는 이웃들에 관해 x, y 방향의 Haar wavelet response를 

계산합니다. 오른쪽 원 안의 파란 점이 response값의 분포입니다. 그리고 빨간 화살표는 부채꼴 모양 안의 영역에 있는

response의 합을 벡터로 표현한 것입니다. 60도 크기의 window를 슬라이딩 하면서 x,y축의 response의 합을 계산해서

벡터를 생성시키고 벡터 길이가 가장 긴 것이 orientation으로 할당됩니다.

이때 Haar wavelet filter를 이용하기 때문에 적분 이미지의 장점을 적용할 수 있습니다.(빠른 계산)

 위 그림을 보면 descriptor를 생성하기 위해 관심점 주위 20scale 크기의 window를 구성해 이미지를 회전에 

invariant 하기 위해 회전시킨 뒤 계산합니다. 이때 앞에서 구한 orientation를 활용하면 됩니다.

또한 descriptor window를 4×4로 나눈뒤, 나눠진 구역은 5×5 haar wavelet로 구성합니다.

 논문에서는 또한 contrast에 invariant하다는 것을 보여주기 위해 단순히 x, y 축에 대한 response값을 

합한 것이 아니라, 각 값에 대한 절대값을 합하여 contrast에 강하다는것을 증명하고 있습니다.

3. Contrast를 이용한 빠른 매칭

 hessian 행렬을 계산한 라플라시안 부호를 비교해 간단히 매칭을 시도합니다.(부호 비교)