영상 특징점(keypoint) 추출방법

영상 특징점이 무엇이고 어떻게 뽑는지, 그리고 대표적인 방법에는 어떤 것들이 있는지 정리해 봅니다.

1. 영상 특징점이란?

2. Harris corner [1988]

3. Shi & Tomasi [1994]

4. SIFT - DoG [2004]

5. FAST [2006]

6. AGAST [2010]

7. 주요 불변 특징량(SURF, BRIEF, ORB 등) 방법에서 사용하는 특징점

1. 영상 특징점이란?

영상에서 물체를 추적하거나 인식할 때, 영상과 영상을 매칭할 때 가장 일반적인 방법은 영상에서 주요 특징점(keypoint)을 뽑아서 매칭하는 것입니다. 특징점을 영어로는 보통 keypoint 또는 interesting point라 부릅니다.

<그림 1>

위 그림에서 첫번째 이미지와 대응되는 지점을 두번째 이미지에서 찾는다고 했을 때, A는 쉽게 찾을 수 있지만 B는 찾기가 어렵습니다. 이와 같이 영상을 매칭하는데 있어서 A처럼 주위 배경과 구분되면서 식별이 용이한 지점을 특징점으로 잡는게 유리함은 누구나 쉽게 알 수 있을 것입니다.

좋은 영상 특징점(keypoint)이 되기 위한 조건을 적어보면 다음과 같습니다.

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

영상에서 이러한 조건을 만족하는 가장 좋은 특징점은 바로 코너점(corner point)입니다. 그리고 대부분의 특징점(keypoint) 추출 알고리즘들은 이러한 코너점 검출을 바탕으로 하고 있습니다.

2. Harris Corner [1988]

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

영상에서 코너점, 특징점(keypoint)을 찾는 가장 대표적인 방법은 1988년에 발표된 Harris corner detector 입니다.

영상에서 코너(corner)를 찾는 기본적인 아이디어는 아래 그림과 같이 영상에서 작은 윈도우를 조금씩 이동(shift)시켰을 때, 코너점의 경우는 모든 방향으로 영상변화가 커야 한다는 점입니다.

<그림 2> 출처: Matching with Invariant Features, Lecture Notes 2004

위 아이디어는 원래 1980년 Moravec's corner detector (Moravec, H, "Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover", Tech Report CMU-RI-TR-3, Carnegie-Mellon University, Robotics Institute, September 1980)에 나온 내용입니다. Moravec은 이 아이디어를 구현하기 위해 영상의 각 픽셀 위치에 대해 윈도우를 수직, 수평, 좌대각선, 우대각선 이렇게 4개 방향으로 1 픽셀씩 이동시켰을 때의 영상변화량(SSD) E를 계산한 후,  E의 최소값을 해당 픽셀의 영상변화량 값으로 설정, 설정된 min(E) 값이 지역적으로 극대가 되는 지점을 코너점으로 찾는 방법을 사용했습니다.

Harris corner detector는 Moravec의 방법을 수정 보완한 것으로서, Harris 방법에서 사용한 구현 과정을 이해하기 위해서는 어느정도 수학적 지식을 필요로 합니다 (저도 다 이해가 되는건 아니지만 되는 대로 적어보겠습니다).

먼저, (△x, △y)만큼 윈도우를 이동시켰을 때 영상의 SSD(sum of squared difference) 변화량 E는 다음과 같습니다 (W: 로컬 윈도우).

 --- (1)

이 때, shift값 (△x,△y)이 매우 작다고 가정하고 그레디언트(gradient)를 이용하여 I를 선형 근사하면 (1차 테일러 근사),

 --- (2)

가 됩니다.

이 때, 2×2 행렬 M의 두 eigenvalue를 λ1, λ2 (λ1≥λ2)라 하면 영상 변화량 E는 윈도우를 λ1의 고유벡터(eigenvector) 방향으로 shift 시킬 때 최대가 되고, λ2의 고유벡터 방향으로 shift시킬 때 최소가 됩니다 (why? 그렇다고 합니다 ㅠ.ㅠ). 또한 두 고유값(eigenvalue) λ1, λ2는 해당 고유벡터 방향으로의 실제 영상 변화량(E) 값이 됩니다 (단, 윈도우의 shift 크기가 1일 경우).

따라서, M의 두 고유값 λ1, λ2를 구했을 때, 두 값이 모두 큰 값이면 코너점(corner point), 모두 작은값이면 'flat'한 지역, 하나는 크고 다른 하나는 작은 값이면 'edge' 영역으로 판단할 수 있습니다.

실제 Harris 방법에서는 M의 고유값을 직접 구하지 않고 det(M)=λ1λ2, tr(M)=λ1+λ2 임을 이용하여 다음 수식의 부호로 코너점 여부를 결정합니다.

 --- (3)

즉, R>0면 코너점, R<0면 edge, |R|이 매우 작은 값이면 R 부호에 관계없이 flat으로 판단 (단, k는 경험적 상수로서 0.04 ~ 0.06 사이의 값).

<그림 3> 출처: Matching with Invariant Features, Lecture Notes 2004

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

<그림 4> 출처: Matching with Invariant Features, Lecture Notes 2004

☞ 참고로, 이러한 스케일 문제를 보완하기 위한 한 방법으로 2001년도에 발표된 Harris-Laplacian 방법(K. Mikolajczyk and C. Schmid, "Indexing based on scale invariant interest points", in ICCV 2001)에서는 여러 영상 스케일에서 Harris 코너를 뽑은 후, 이들 중 스케일 변화에 대해 Laplacian이 극대인 점을 선택하는 방식이 사용되었습니다.

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 중 최소값만을 고려하는 것이 더 좋다는 것입니다. 즉, Shi-Tomasi 특징점은 다음 수식을 만족하는 점들로 주어집니다.

 --- (4)

단, k는 미리 정의된 threshold, λ1, λ2는 Harris corner의 식(2)에 행렬 M의 두 eigenvalue.

즉, 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)에서 사용하는 특징점 추출 방법입니다. SIFT에서는 기존의 Harris 코너가 영상의 스케일 변화에 민감한 문제를 해결하기 위하여 DoG(Difference of Gaussian)를 기반으로 이미지 내에서 뿐만 아니라 스케일 축으로도 코너성이 극대인 점을 찾습니다.

SIFT에서 사용한 특징점 추출 방법을 이해하기 위해서는 먼저 스케일에 불변인 즉, scale invariant한 특징점을 추출한다는 말의 의미를 이해할 필요가 있습니다. 어떤 입력 이미지 I가 있을 때, I의 크기를 단계적으로 축소시켜서 일련의 축소된 이미지들을 생성할 수 있습니다 (이렇게 생성된 이미지들의 집합을 보통 이미지 피라미드라고 부릅니다). 이 때, 각 스케일의 영상마다 코너성을 조사해서 코너점(코너성이 로컬하게 극대이면서 임계값 이상)들을 찾습니다. 그러면 각 스케일 이미지마다 코너점들이 검출될 터인데, 대부분의 경우 인접한 여러 영상 스케일에 걸쳐서 동일한 지점이 코너점으로 검출될 것입니다. 동일한 지점이 여러 영상 스케일에 걸쳐 코너점으로 검출된 경우, 그중 스케일 축을 따라서도 코너성이 극대인 점을 찾으면 스케일에 불변인 특징점이 됩니다.

<그림 5> image pyramid

여기서, 스케일에 불변인 특징점이란 의미는 입력 이미지의 스케일이 어떻게 주어지더라도 해당 특징점을 찾아낼 수 있다는 의미입니다. 서로 다른 스케일의 입력 영상 I1, I2가 있다고 하겠습니다. 이 때, I1에서 특징점을 찾을 때 I1의 입력 스케일에서만 특징점을 찾는게 아니라 I1으로부터 이미지 피라미드를 구축한 후에 여러 스케일에 걸쳐서 특징점을 찾습니다(각각의 스케일 이미지 내에서 코너성이 극대일 뿐만 아니라 스케일 축으로도 코너성이 극대인 점들). I2에서도 마찬가지로 여러 스케일에 걸쳐 특징점을 찾아냅니다. 이렇게 특징점을 찾으면 입력 이미지의 스케일에 관계없이 동일한 특징점을 찾을 수 있게 됩니다. 또한 해당 특징점이 I1의 어떤 스케일에서 찾아졌는지와 I2의 어떤 스케일에서 발견된 것인지는 서로 다를 수 있지만 I1, I2에서 계산된 코너성은 거의 동일할 것입니다.

SIFT 방법으로 돌아가서, SIFT에서 특징점을 추출하는 기본적인 원리는 위와 같지만 코너성을 측정하기 위해 Harris 방법과는 달리 Laplacian 함수값을 사용합니다. 즉, SIFT에서는 각 영상 스케일마다 Laplacian 값을 계산하되 그 값이 이미지 내에서 뿐만 아니라 스케일 축으로도 극대(또는 극소)인 점들을 특징점으로 선택합니다. 참고로, Laplacian은 이미지의 밝기 변화에 대한 2차 미분값으로서 다음과 같이 계산되며

 --- (5)

그 특징은 영상의 밝기 변화가 일정(constant velocity)한 곳에서는 0에 가까운 값, 영역의 경계와 같이 밝기 변화가 급격한 곳에서는 높은 값(절대값)을 나타냅니다.

(이후의 내용은 SIFT에서 Laplacian을 DoG를 이용하여 근사적으로 계산한 방법에 관한 것으로서 건너뛰어도 무방합니다)

실제 SIFT에서는 속도 문제로 인해 Laplacian을 직접 계산하지는 않고 DoG(Difference of Gaussian)를 이용하여 각 스케일별 Laplacian을 근사적으로 계산합니다. DoG는 입력영상에 Gaussian 필터를 점진적으로 적용하여 블러링(blurring)시킨 이미지들에서 인접 이미지들간의 차(subtraction) 영상을 의미하며 이론적으로는 LoG(Laplacian of Gaussian) 필터를 적용한 것과 거의 동일한 결과를 갖습니다.

<그림 6> SIFT의 DoG 계산

그리고 이렇게 얻어진 DoG 피라미드에서 극대 또는 극소점을 찾으면 SIFT의 특징점이 됩니다.

☞ 위에서 Gaussian 필터를 적용하여 영상을 blurring 시키는 것은 영상의 스케일을 확대시키는 의미를 갖습니다. 이러한 원리 및 DoG, LoG 등에 대해 이해하기 위해서는 'scale space' 이론에 대해 어느정도 알고 있어야 합니다. Scale space 이론에 대해서는 조만간 별도로 포스팅을 하겠습니다. 일단 여기서는, SIFT에서는 이미지 피라미드 상에서 Laplacian 값이 극대 또는 극소가 되는 점들을 특징점으로 잡는다 정도로만 이해해도 무방하리라 생각됩니다. =>Scale Space와 이미지 피라미드(image pyramid)

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)는 영국 캠브리지 대학의 Edward Rosten이 개발한 방법으로 FAST라는 이름에서 알 수 있듯이 극도의 빠름을 추구한 특징점 추출 방법입니다. 하지만 FAST가 정말 뛰어난 점은 FAST가 속도에 최적화되어 설계된 기술임에도 불구하고 그 특징점의 품질(repeatability: 다양한 영상 변화에서도 동일한 특징점이 반복되어 검출되는 정도) 또한 기존의 방법들(Harris, DoG, ...)을 상회한다는 점에 있습니다.

FAST 또한 코너점을 찾는 방법중 하나로서 그 기본 방법은 다음과 같습니다.

<그림 7> FAST corner detector

FAST에서는 위 그림과 같이 어떤 점 p가 코너(corner)인지 여부를 p를 중심으로 하는 반지름 3인 원 상의 16개 픽셀값을 보고 판단합니다. 그래서 p보다 일정값 이상 밝은(>p+t) 픽셀들이 n개 이상 연속되어 있거나 또는 일정값 이상 어두운(<p-t) 픽셀들이 n개 이상 연속되어 있으면 p를 코너점으로 판단합니다.

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

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

FAST 코너의 한가지 문제점은 어떤 점 p가 코너점으로 인식되면 p와 인접한 주변 점들도 같이 코너점으로 검출되는 경우가 많다는 점입니다. FAST에서는 이 문제를 해결하기 위해 non-maximal suppression라 불리는 추가적인 후처리 단계를 적용합니다.

Non-maximal suppression의 목적은 인접한 여러 점들이 코너점으로 검출된 경우 그중 코너성이 극대인 점만을 남기고 나머지를 제거하는 것입니다. 그런데, 앞서 설명한 decision tree 방식은 코너점 여부를 On/Off 방식으로 결정할 뿐, 코너 정도를 수치화하지는 못하기 때문에 FAST 논문에서는 다음과 같은 별도의 수치화 함수를 정의합니다.

 --- (6)

Non-maximal suppression 단계에서는 decision tree를 통해 검출된 코너점들에 대해 각각 식 (6)의 V를 계산한 후, 인접한 코너점들 중 자신보다 높은 V값을 갖는 코너점이 있으면 해당 코너점을 제거하는 방식으로 코너성이 극대인 점들을 찾아냅니다.

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

<그림 8> FAST의 속도 성능

<그림 9> FAST의 repeatability 성능

☞ 개발자 홈페이지(http://www.edwardrosten.com/work/fast.html)에 가면 FAST에 대한 다양한 소스코드, FAQ 및 관련자료를 얻을 수 있습니다.

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

FAST의 성능을 좀더 빠르게 개선한 방법이라고 합니다. 논문을 조금 읽어봤지만 당체 무슨 말인지.. 어쨌든 논문의 주장에 따르면 AGAST 방법이 FAST에 비해 20 ~ 30% 정도 속도가 더 빠르다고 합니다.

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

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에서 사용한 특징점 추출 방법을 그대로 사용

☞ 이상으로 주요 영상 특징점(keypoint) 추출 방법들에 대해 정리를 해 보았습니다. SIFT, SURF, BRIEF, ORB, FREAK 등 주요 불변 영상 특징량(descriptor) 방법들에 대해서는 별도 글로 포스팅할 예정입니다.

by 다크 프로그래머