SURF(Speeded-Up Robust Features)

SURF란???

말그대로 빠르게 강인한 특징점을 찾아보자!!! 이거 아입니까??

이 논문에서는 SIFT외에도 다른 방법들과 비교를 했는데 최대한 SIFT못지 않게 성능을 유지하면서 계산속도를 향상 시키고자했다

그래서 중요한 속도향상을 위해 제안한 방법들을 요약해보면

1. Integral image를 이용. (4개의 point만 알면 그영역의 면적을 간단하게 바로 계산 가능)
2. 간편화한 Detector와 Descriptor활용 (차원수를 줄임)
3. Contrast를 이용한 간단한 매칭

이렇게 3가지를 들 수 있습니다.

그럼 이제부터 하나씩 파헤쳐 보겠습니다.

주요 속도 상승의 요인인 Integral image
 - 임의의 크기의 사각형을 일정시간 내에 계산

- I(x)공식을 보면 먼저 영상에 대해서 면적을 쭉~ 계산해놓은다음 A, B, C, D 4점만 알면 S라는 면적을 빠르게 계산할 수 있다.
A를 알면 O(0,0)부터 A까지의 사각형 면적을 알수 있고 C를 알면 C까지의 사각형..이런식으로 각각의 점의 위치까지의 사각형의 면적을 알고 있기 때문에 단순히 덧셈 뺄셈 연산만 해주면됩니다. A에서 C와 B의 면적을 빼준후 D의 면적을 더해주면 S의 면적이 나온다는것을 살짝 훑어만 보시면 알수 있을거라 생각합니다.!!! ^_^;

Interest Point Detection
 - 헤시안(Hessian) 매트릭스 기반으로 검출을 합니다.

 - 논문에서는 정확성이 좋고 Determinant가 max값인 위치에서 blob같은 구조를 검출하기 위해서라고합니다.
 - 만약 determinant가 음수이고 eigenvalue가 서로 다른 부호이면 point는 극값이 아닙니다. 반면에 determinant가 양수이고 eigenvalue가 둘다 음수이거나 양수이면 두 개의 경우 모두 point가 극값으로 구별됩니다.
 - SURF의 경우에는 2차미분을 Gaussian을 사용하는데 그것은 Scale-space를 분석하는데 가우시안이 가장 최적이라고 논문에서 언급하고 있습니다. 따라서 x축, y축, 그리고 xy축(대각)에 대해 4개 entry를 헤시안으로 계산하면 Interest point후보자들이 뽑히게 됩니다.

 - 아래 그림처럼 9x9 박스 필터를 사용하는데 계산을 좀더 간편하고 단순하게 하기위해서 근사화한 Dxx와 Dyy박스필터를 이용합니다.

- 위의 공식에서 보이듯이 논문에서는 실제로 0.9라는 Weight를 사용햇다고 합니다. 가우시안 커널과 approximated가우시안 커널사이에 에너지를 보존하기위해서 W를 계산했다고하는데 정확히 어떤 공식을 사용해서 만들었는지는 잘모르겠습니다. 어쨋든 이 헤시안의 근사화한 determinant는 location X에서 이미지안에 blob response를 나타냅니다. 이 응답은 다른 스케일 전체에 걸쳐서 blob response map에 저장이됩니다.

 - 여기서도 SIFT와 비슷하게 영상 피라미드를 구성하는데 SIFT에서는 다른 크기의 이미지에 적용하면서 크기 불변을 보장한 반면 SURF에서는 박스 필터 크기를 변경해가면서 적용을 했습니다.(왜냐하면 결국 이거나 저거나 똑같다 이말아입니까?)

-  여기서는 아래 그림처럼 박스필터 사이즈를 up-scaling하면서 분석을 하는데요. 이러한 smpling type을 사용한 주된 동기는 계산적인 효율성이라고 보시면됩니다. 위에서도 언급했다시피 여기서는 intergral image를 사용하기 때문에 최대한 이것들을 사용하는게 계산적으로 이득 아입니까?? 추가로 여기서는 downsample하지 않기 때문에 aliasing이 없다는 장점을 들었는데요 반면에 scale invariance가 제한적일 수 있다는 단점이 있네요.

- 아래 표를 보시면 3개의 옥타브가있고 점점 스케일이 지수적으로 증가하는 것을 볼 수 있습니다. 옥타브가 증가하면 filter size의 증가량이 2배로 점차 증가하는 것을 확인 할 수 있습니다. (그리고 자세히보시면 옥타브별로 같은 필터 크기임에도 불구하고 네모상자의 크기가 다른것을 확인할 수 있는데요 왜그럴까요??? .........?__?? 알아맞춰보시기 바랍니다.)

- 이렇게 SIFT와 유사하게 옥타브별로 서로다른 스케일의 영상을 뽑아냈으면!!! Non-Maximal Suppression을 이용해서 이웃한 점들과 비교하여 중심점이 가장클경우 키포인트 후보자로 뽑게 됩니다.(SIFT와 이부분은 동일합니다.)


Interest Point Descriptor
 - 각 Interest Point에 orientation을 할당합니다.

 - 위에 그림은 별거 없습니다. 찾아진 interest point중심으로 6s(s:scale)의 원안의 이웃들에서 x, y방향의 Haar wavelet response를 계산합니다. 오른쪽의 원안에 파란 점들이 response값들이 분포되있는 거라고 보시면됩니다. 그리고 화살표 방향은 약60도크기의 부채꼴 모양 영역에서 response의 합을 벡터로 나타낸 것입니다.
 - 60도크기의 window를 쭈우욱 슬라이딩하면서 x, y축 response의 합을 계산해서 벡터를 생성시키고 벡터길이가 가장 긴 놈이 orientation으로 할당이 되게 됩니다.
 - 여기서도 Haar wavelet filter를 이용하기 때문에  interal image의 효과를 만끽할 수 있겠죠??

 - 위에서 보시면 Descriptor를 생성하기 위해서 Interest point주위에 20s크기의 window를 구성합니다. 두번째로 앞에서 할당한 orientation에 따라서 window도 oriented시킵니다.
 - 그리고 descriptor window를 4x4로 다시 나눕니다. 나눠진 각각의 구역은 5x5크기로 분배된 샘플 포인트들을 Haar wavelet으로 계산합니다.

 - 위에서는 consrast에 invariant하다는 것을 보여주고있습니다. 여기서는 단순히 x, y축에대한 response값을 합한 것 뿐만아니라 절대값으로 합한 값도 이용해서 contrast에 강하다는 것을 보여주고 있네요

Matching
 - 이전에 헤시안 매트릭스에서 계산한 라플라시안의 부호를 비교해서 간단하게 매칭을 할 수 있습니다.
 - 추가적인 연산 비용이 들지 않고 Descriptor의 성능 감소없이 매칭 속도가 증가합니다.