SIFT와 SURF 이후의 Feature Descriptors들(딥러닝 이전까지), 그리고 SIFT와 SURF의 간단한 비교 실험

제 기억에 의하면 SIFT가 Lowe 교수에 의해서 제안된게 2004년이고 SURF가 Bay 교수에 의해서 제안된게 2006년이니 벌써 14년이상의 시간이 흘렀습니다. 당연히 이들 보다 좋은 feature descriptor를 만들기 위한 연구들은 계속 되었겠죠?

(물론 요즘 딥러닝 시대에는 어떤 식으로 연구가 되고 있는지 모르겠지만..) 

 

SIFT보다 SURF보다 정확도(처리 속도는 배제)를 높이기 위한 목적으로 나온 알고리즘도 있고, SIFT와 SURF처럼 유사한 정확도를 보이면서도 처리 속도를 빠르게 하기 위한 목적으로 나온 알고리즘도 있습니다(스마트폰 시장이 커진 것도 한몫 했겠죠?).

 

아래는 딥러닝 이전까지의 SIFT와 SURF 이후에 유명 저널 및 컨퍼런스에 출판된 feature descriptor 관련 논문들의 목록입니다. 출판 년도 별로 정리를 해봤습니다.

    

1. OSID(Ordinal Spatial Intensity Distribution)
Feng Tang, Suk Hwan Lim, Nelson L. Chang, Hai Tao: A novel feature descriptor invariant to complex brightness changes. 2631-2638, CVPR 2009.

 

2. WLD(Weber Local Descriptor)
Jie Chen; Shiguang Shan; Chu He; Guoying Zhao; Pietikainen, M.; Xilin Chen; Wen Gao; Dept. of Electr. & Inf. Eng., Univ. of Oulu, Oulu, Finland, WLD: A Robust Local Image Descriptor, PAMI 2009.

 

3. CHoG(Compressed Histogram of Gradients)
V. Chandrasekhar, G. Takacs, D. Chen, S. Tsai, R. Grzeszczuk, and B. Girod, "CHoG: compressed histogram of gradients", IEEE International Conference on Computer Vision and Pattern Recognition, June 2009.

 

4. BRIEF(Binary Robust Independent Elementary Features)
M. Calonder, V. Lepetit, C. Strecha, and P. Fua, BRIEF: Binary Robust Independent Elementary Features, European Conference on Computer Vision, Heraklion, Greece, 2010.

 

5. RIFF(Rotation Invariant Fast Features)
G. Takacs, V. Chandrasekhar, S. Tsai, D. Chen, R. Grzeszczuk, and B. Girod, "Unified real-time tracking and recognition with rotation-invariant fast features", IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), June 2010.

 

6. RIFF-Polar((Rotation Invariant Fast Features-Polar)
G. Takacs, V. Chandrasekhar, H. Chen, D. Chen, S. Tsai, R. Grzeszczuk, and B. Girod, "Permutable descriptors for orientation-invariant image matching", SPIE Workshop on Applications of Digital Image Processing (ADIP), August 2010. 

 

7. DAISY
E. Tola, V. Lepetit, and P. Fua. Daisy: An efficient dense descriptor applied to wide-baseline stereo. PAMI, 2010.

 

8. ORB(Oriented FAST and Rotated BRIEF)
ORB: an efficient alternative to SIFT or SURF, Ethan Rublee (Willow Garage), Vincent Rabaud (willowgarage), Kurt Konolige, Gary Bradski Hiroshi Ishiguro, Osaka University ICCV 2011.

9. DaLI(Deformation and Light Invariant)
Deformation and Illumination Invariant Feature Point Descriptor, Francesc Moreno(Institut de Robotica i Informatica Industrial (UPC/CSIC)), CVPR 2011.

 

SURF와 SIFT의 간단한 비교 실험

일단 어파인 불변 영역 검출기 중에 가장 성능이 우수하다고 알려져 있는 [1]MSER(maximally stable extremal regions)을 Feature Detector로 고정시키고, MSER로부터 추출된 특징점 주변에 [2]SURF를 이용하여 기술자 정보를 생성한 경우와 [3]SIFT를 이용하여 기술자 정보를 생성한 경우에 대해 실험을 했습니다.

기술자 정합의 경우 비교적 빠르면서 오정합 점을 잘 제거한다고 알려져 있는 [4]FLANN(Randomized KD-Tree)으로 고정시키고, 유사도 측정 방법에 사용되는 거리는 NNDR(Nearest Neighbor Distance Ratio)로 고정시키고,  아웃라이어 제거 및 호모그래피 추정은 [5]RANSAC과 [6]SVD를 이용하였습니다.

 

말로 자세하게 썼는데, 즉 아래와 같은 두개의 경우에 대해서 실험을 했습니다.

 

Case 1: Feature Detector(=MSER) + Feature Descriptor(=SIFT) + Descriptor Matching(=FLANN + NNDR) + Outlier Removal and Homography Estimation(RANSAC + SVD) 

Case 2: Feature Detector(=MSER) + Feature Descriptor(=SURF) + Descriptor Matching(=FLANN + NNDR) + Outlier Removal and Homography Estimation(RANSAC + SVD)

 

아래 보시는 바와 같은 기준 영상에 대해 질의 영상은 약간의 어파인 변환이 들어가 있고, 비교적 배경이 어지러운 영상을 선택하여 기술자 정합을 하고 호모그래피를 그려봤습니다.   

 

결과 분석은 아래와 같습니다.

 

Case 1과 Case 2는 모두 호모그래피를 정상적으로 그렸습니다. 사실 이는 질의 영상 자체가 영상의 광학적/기하학적 변환이 심하지 않기 때문에 가능했겠죠.

 

하지만 FLANN을 통해서 추출된 정정합점의 개수(good matched number를 보시면 Case 1은 29개인 반면에, Case는 25개)는 SIFT가 SURF보다 4개정도가 더 많습니다. 이정도의 차이는 과연 간과할만한 수치일까요? 아마도 질의 영상이 보다 광학적/기하학적 변환이 심해진다면 정정합점은 더 큰 차이가 벌어질 것으로 예상이 됩니다.

 

저도 사실 이건 예상이고, 실험을 해봐야만 알 것 같네요^^(추후 실험을 기대해주시길^^, 참고로 울만 교수님의 말씀처럼 정말로 큰 변환들에 대해서는 다른 도메인으로 처리하는 접근법이 필요한건지에 대한 증명도 실험적으로 해볼 생각입니다.^^)

 

good matched number는 Case 1이 더 많으니 ">"가 될테고, 두 경우 모두 호모그래피를 정상적으로 그렸으니 "="가 될테니 어찌되었든간에 Case 1과 Case 2의 비교는 정확도면에서는 "Case 1 >= Case 2" 라고 점수를 줄 수 있겠네요.

 

그럼 속도를 봐야겠죠?

어디보자.. Case 1과 Case 2 모두 당연히 동일한 Feature Detector를 썼으니, 약 0.14 초 정도가 소요되었고, Descriptor를 생성하는 시간은 Case 1이 약 0.44초가 걸렸고, Case 2가 약 0.13초가 걸렸으니 약 3.4배 Case 1이 더 느리다고 할 수 있겠네요.
SIFT 기술자는 역시 SURF 기술자보다 느린가봅니다. 그럼 왜 느릴까요?(이에 대한 분석도 나중에 시간이 나는데로 작성을 해보도록 하겠습니다^^)

다음으로 기술자를 정합하는데 걸리는 속도를 보면, Case 1이 약 0.023초 걸린 반면에 Case 2는 약 0.011초가 걸렸네요. 아마도 SIFT 기술자가 가지고 있는 정보량이 상당히 무거운가 봅니다. 똑같은 기술자 정합 알고리즘을 썼는데도 불구하고
약 2배 차이로 Case 1이 오래 걸리는걸 보면 말이죠. 이 역시 Bay 교수님의 논문을 보면 충분히 유추를 할 수 있을 것입니다(아마도 라플라시안 기호를 이용한 인덱싱이 핵심이 아닐까 싶습니다만..^^)

 

좀 더 많은 실험을 해봐야겠지만, 현재까지의 실험에 의하면 정확도는 "SIFT Descriptor Wins" 속도는 "SURF Descriptor Wins" 라고 말을 할 수 있을 것 같습니다.

 

Case 1:

Case 2:

 

참고 문헌

[1] J. Matas, O. Chum, M. Urba, and T. Pajdla. "Robust wide baseline stereo from maximally stable extremal regions." Proc. of British Machine Vision Conference, pages 384-396, 2002.
[2] SURF: Speeded Up Robust Features by Herbert Bay, Tinne Tuytelaars, Luc Van Gool, ECCV 2006
[3] Lowe, D. G.,“Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, 60, 2, pp. 91-110, 2004.
[4] Marius Muja, David G. Lowe: Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration. VISAPP (1) 2009: 331-340
[5] Martin A. Fischler and Robert C. Bolles (June 1981). "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography". Comm. of the ACM 24 (6): 381–395
[6] http://en.wikipedia.org/wiki/Singular_value_decomposition