[Vision] Key-Point Extraction: 영상 특징점 추출

💡 본 문서는 '영상 특징점 추출 방법'에 대해 정리해놓은 글입니다.
영상에서의 특징점을 추출하는 방법인 Key-Point Extraction 과 관련된 변천사를 정리하였으니 참고하시기 바랍니다.

1. 영상 특징점

영상에서 물체를 추적하거나 인식할 때, 영상과 영상을 매칭하는 가장 일반적인 방법은 영상에서 주요 특징점(keypoint)을 뽑아서 매칭하는 것이다. 

좋은 영상 특징점(keypoint)이 되기 위한 조건

• 물체의 형태나 크기, 위치가 변해도 쉽게 식별이 가능할 것
• 카메라의 시점, 조명이 변해도 영상에서 해당 지점을 쉽게 찾아낼 수 있을 것

영상에서 이러한 조건을 만족하는 가장 좋은 keypoint를 coner point라고한다. 그리고 대부분의 keypoint추출 알고리즘들은 이러한 coner point 검출을 바탕으로 하고 있다.

2. Harris Corner [1988]

[Harris88] C. Harris and M. Stephens, "A combined corner and edge detector", Alvey Vision Conference, 1988

영상에서 coner point, keypoint를 찾는 가장 대표적인 방법은 1988년에 발표된 Harris corner detector이다. 영상에서 corner를 찾는 기본적인 아이디어는 영상에서 작은 윈도우를 조금씩 shift 시켰을 때, 코너점의 경우는 모든 방향으로 영상변화가 커야 한다는 점이다.

이 아이디어는 원래 1980년 Moravec corner detector에 나온 내용이다. moravec은 이 아이디어를 구현하기 위해 영상의 각 픽셀 위치에 대해 윈도우를 수직, 수평, 좌대각선, 우대각선 이렇게 4개 방향으로 1픽셀씩 이동시켰을 때의 영상변화량(SSD) E를 계산한 후, E의 최소값을 해당 픽셀의 영상변화량 값으로 설정하고, 설정된 min(E)값이 지역적으로 극대가 되는 지점을 코너점으로 찾는 방법을 사용했다.

Harris conner detector는 Moravec의 방법을 수정 보완한 것이다. Harris detector는 영상의 평행이동, 회전변화에는 불변(invariant)이고 affine 변화, 조명(illumination) 변화에도 어느 정도는 강인성을 가지고 있다. 하지만 영상의 크기(scale) 변화에는 영향을 받기 때문에 응용에 따라서는 여러 영상 스케일에서 특징점을 뽑을 필요가 있다.

3. Shi & Tomasi [1994]

[Shi94] J. Shi and C. Tomasi, "Good features to track", in CVPR 1994

Shi-Tomasi 특징점 추출 방법은 goodFeaturesToTrack() 이라는 함수명으로 opencv에 구현되어 있으며, 흔히 optical flow 등을 계산할 때 사용할 특징점을 추출하는 용도 등으로 사용됩니다. 논문에 보면, 기존의 방법들은 코너점 등 직관에 의지하여 특징점을 찾았는데 자신들 생각에는 좋은 특징점이란 추적 알고리즘에 최적화되도록(추적이 용이하도록) 뽑아야 하며 따라서 기존 방법처럼 단순한 평행이동(translation) 만을 가정해서는 안되고 affine 변화까지 고려해서 특징점을 선택해야 한다는 등의 설명이 나옵니다.

Shi-Tomasi의 결론은 Harris 방법처럼 M의 두 eigenvalue를 같이 고려하는 것보다는 λ1, λ2 중 최소값만을 고려하는 것이 더 좋다는 것입니다. 즉, Harris corner와 Shi-Tomasi corner를 비교해 보면 Harris는 λ1, λ2가 모두 비슷하게 큰 경우에 corner점으로 식별하고, Shi-Tomasi는 λ1, λ2 중 최소값만 임계치보다 크면 corner점으로 식별하는 방식입니다.

☞ 그런데, 저는 Harris가 더 좋은 방법이라고 생각합니다. 왜냐하면 최소값이 임계값보다 크더라도 다른 한 값이 월등히 더 크면 코너점이라기 보다는 edge로 보는 것이 더 타당하기 때문입니다 (물론 픽셀의 밝기값은 한계(최대255)가 있기 때문에 최소값만 고려해도 결과적으로는 큰 차이가 없습니다). 또한 Harris 방법은 eigenvalue를 직접 구할 필요없이 M에서 바로 식 (3)의 R을 계산하여 코너점을 판단하기 때문에 속도면에서도 이득입니다.

4. SIFT - DoG [2004]

[Lowe04] Lowe, D.G., "Distinctive image features from scale-invariant keypoints", IJCV 2004.

SIFT(Scale Invariant Feature Transform)은 2004년 발표한 특징점 추출 알고리즘이다. 기존의 Harris corner가 영상의 스케일 변화에 민감한 문제를 해결하기 위해 DoG(Difference of Gaussian)를 기반으로 이미지 내에서 뿐만 아니라 스케일 축으로도 코너성이 극대인 점을 찾는다.​

SIFT에서는 이미지 i가 있을 때, i의 크기를 단계적으로 축소시켜서 일련의 축소된 이미지들을 생성한다(이미지 피라미드). 이 때, 각 스케일의 영상마다 코너성을 조사해서 코너점(코너성이 로컬하게 극대이면서 임계값 이상)들을 찾는다. 그러면 각 스케일 이미지마다 코너점들이 검출되는데, 대부분의 경우 인접한 여러 영상 스케일에 걸쳐서 동일한 지점이 코너점으로 검출된다. 그중 스케일 축을 따라서도 코너성이 극대인 점을 찾는다. 이 점을 scale invariant한 특징점이라고 한다.

 

scale invariant한 특징점은 입력 이미지의 스케일이 어떻게 주어지더라도 해당 특징점을 찾아낼 수 있다. SIFT는 이미지 피라미드상에서 LAPLACIAN 값이 극대 또는 극소가 되는 점들을 특징점으로 잡는다.

5. FAST [2006]

[Rosten06] E. Rosten and T. Drummond, "Machine learning for high-speed corner detection", in ECCV 2006

FAST(Features from Accelerated Segment Test)는 2006년 발표한 극도의 빠름을 추구한 특징점 추출 알고리즘이다. FAST는 속도에 최적화됨에도 불구하고 특징점의 품질(repeatability)가 기존의 방법들보다 뛰어나다.

FAST에서는 어떤 점 P가 코너인지 여부를 p를 중심으로 하는 반지름 3인 원 상의 16개 픽셀값을 보고 판단한다. p보다 일정값 이상 밝은 픽셀들이 n개 이상 연속되어 있거나 일정값 이상 어두운 픽셀들이 n개 이상 연속되어 있으면 p를 코너점으로 판단한다.

FAST 알고리즘은 n을 어떻게 잡느냐에 따라서 FAST-9, FAST-10, FAST-11, FAST-12, ..., FAST-16과 같이 다양한 버전이 가능합니다. 즉, FAST-9는 p보다 일정값 이상 밝거나 어두운 픽셀들이 원을 따라서 연속적으로 9개 이상 존재하는 경우를 코너점으로 검출하는 알고리즘이다.

FAST 알고리즘에서는 어떤 점 p가 코너점인지 여부를 판단하기 위해 같은 유형의 연속된 점들의 개수를 직접 세는 대신에 decision tree를 이용하여 코너점 여부를 빠르게 판단하는 방법을 사용한다. 이를 위해 픽셀의 밝기값을 p보다 휠씬 밝거나 어두운 경우, p와 유사한 경우의 3가지 값으로 분류하고 이를 이용하여 원주상의 픽셀들의 밝기분포를 16차원의 ternary 벡터로 표현한다. 이를 decision tree에 입력하여 코너점 여부를 분류한다.

FAST 코너의 한가지 문제점은 어떤 점 p가 코너점으로 인식되면 p와 인접한 주변 점들도 같이 코너점으로 검출되는 경우가 많다. FAST는 이러한 문제를 해결하기 위해 non-maximal suppression 후처리 방법을 사용한다. 인접한 여러 점들 중 코너성이 극대인 점만을 남기고 나머지를 제거한다.

저자의 실험에 의하면, 여러 FAST 버전들 중 FAST-9의 성능이 가장 좋으며 기존 방법에 비해 10배 이상의 속도 증가를 가져온다고 합니다. 특징점의 품질(repeatability) 또한 기존 방법들을 상회하는 결과를 보여줍니다.

Fast의 속도 성능 https://darkpgmr.tistory.com/131

6. AGAST [2010]

[Mair10] E. Mair, G. Hager, D. Burschka, M. Suppa, and G. Hirzinger, "Adaptive and generic corner detection based on the accelerated segment test," in ECCV 2010

논문의 주장에 따르면 AGAST 방법이 FAST에 비해 20 ~ 30% 정도 속도가 더 빠르다고 합니다.

7. 주요 불변 특징량(descriptor) 방법에서 사용하는 특징점(keypoint)

SIFT, SURF, BRIEF, ORB, FREAK 등과 같은 지역적 불변 특징량 (local invariant feature descriptor) 방법들에서 사용하는 특징점(keypoint)이 어떤 것인지 간단히 살펴 보고자 합니다.

먼저, 지역 불변 특징량(descriptor)과 특징점(keypoint)을 서로 구분할 필요가 있는데 keypoint는 특징이 되는 점의 영상좌표 (x,y)를 의미하고(scale space까지 고려한다면 (x,y,s)), descriptor는 해당 keypoint 위치에서 추출한 지역적 영상 특징 정보(ex. gradient 분포 히스토그램 등)를 의미합니다.

대표적인 지역 불변 특징량(descriptor)들로는 SIFT, SURF, ORB 등이 있는데, descriptor 계산을 위해서는 일단은 keypoint를 뽑아야 하기 때문에 이들 지역 불변 특징량 방법들도 나름의 특징점 추출 방법을 가지고 있습니다. 사실 지역 불변 특징량과 특징점은 서로 별개의 얘기이기 때문에 임의의 keypoint + descriptor 조합이 가능합니다. 예를 들어, FAST로 특징점을 뽑은 후 SIFT로 descriptor를 계산하는 것도 가능합니다.

SIFT의 경우는 앞서 DoG를 이용하여 특징점을 추출한다고 설명한 바 있는데, 그외 다른 지역 불변 특징량 방법들에서는 어떤 특징점 추출 방법들이 사용되는지 간단히 살펴보겠습니다.

SURF [Bay06]

: Bay, H., Tuytelaars, T., and Van Gool, L., "Surf: Speeded up robust features," in ECCV 2006

• Scale space 상에서 Hessian 행렬의 행렬식(determinant)이 극대인 점들을 특징점으로 검출.
• SURF에서 사용한 특징점 추출 방법을 Fast Hessian이라 부름.

Ferns [Ozuysal07]

: Ozuysal, M., Fua, P., and Lepetit, V., "Fast Keypoint Recognition in Ten Lines of Code," in CVPR 2007

• Scale space 상에서 Laplacian이 극대인 점들을 특징점으로 검출
• 단 3개의 scale로만 구성된 이미지 피라미드에서 Laplacian 극대점을 찾은 점에서 모든 스케일에 대해서 특징점을 찾은 SIFT와 차이가 있음

BRIEF [Calonder10]

: Calonder, M., Lepetit, V., Strecha, C., and Fua, P, "Brief: Binary robust independent elementary features," in ECCV 2010

• BRIEF에는 별도의 특징점 추출 방법이 포함되어 있지 않음
• SURF의 특징점을 그대로 사용하여 SURF와 성능을 비교하거나 Star(CenSurE) 특징점을 이용하여 성능을 비교

ORB [Rublee11]

: Rublee, E., Rabaud, V., Konolige, K., and Bradski, G., "ORB: an efficient alternative to SIFT or SURF," in ICCV 2011

• FAST-9 을 이용하여 특징점을 검출한 후 나름의 방법(Intensity Centroid)으로 특징점의 방향(orientation)을 계산

BRISK [Leutenegger11]

: Leutenegger, S., Chli, M., and Siegwart, R. Y., "BRISK: Binary robust invariant scalable keypoints," in ICCV 2011

• Scale space 상에서 FAST-9을 이용하여 FAST score가 극대인 점을 특징점으로 검출

FREAK [Alahi12]

: A. Alahi, R. Ortiz, and P. Vandergheynst, "FREAK: Fast Retina Keypoint," in CVPR 2012

• 별도의 특징점 추출 방법을 제공하지 않고 BRISK에서 사용한 특징점 추출 방법을 그대로 사용

참고

• [Blog] 영상 특징점(keypoint) 추출방법: https://darkpgmr.tistory.com/131
• [Blong] ORB-SLAM: a Versatile and Accurate Monocular SLAM System: https://blog.naver.com/PostView.nhn?blogId=dnjswns2280&logNo=222086846193&categoryNo=20&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=search