[cite]10.1007/11744023_34[/cite]

1 Introduction

컴퓨터 비전 영역에서의 작업들은 이미지에서 코너 지점을 찾는 일로부터 시작한다고 해도 과언이 아닙니다. 물체의 추적이나 SLAM, 이미지끼리의 매칭이나 인식 등에서 코너는 핵심적인 역할을 하고 있습니다. 기존의 SIFT(Dog)나 SUSAN, Harris 등은 좋은 방법이긴 하나 상대적으로 그 계산이 복잡하였던 것이 사실입니다. 특히 SLAM과 같이 계산이 실시간으로 이루어져야만 하는 분야에서는 시간적인 부분이 걸림돌이 될 수밖에 없습니다. 설명하려는 FAST 방법은 시간 복잡도를 최우선시 하여 계산을 최대한 단순화시키는 것에 중점을 둔 방법입니다.

논문에서는 Harris, SIFT(DoG), SUSAN 등의 방법에 대해 간단히 설명을 하고 있으나 생략하고 넘어가겠습니다.

2 High-speed corner detection

2.1 FAST: Features from Accelrated Segment Test

먼저 전체적인 흐름을 살펴보자면 이렇습니다. 코너인지 아닌지 판단할 한 픽셀 p가 있다고 생각해봅시다. 이 p 주위로 3 픽셀 길이의 반지름을 갖는 원을 그려봅니다. 그러면 논문의 그림 1과 같이 앞서 그린 원을 따라서 16개의 픽셀을 구할 수 있습니다. 이 원에 해당하는 픽셀 값들을 조사하였을 때, 중앙의 p의 픽셀보다 밝은 값, 혹은 어두운 값이 n 개 연속으로 나열되어 있다면 이 부분은 자연스럽게 코너라고 생각할 수 있습니다. 보통 n은 12를 사용하며, 노이즈를 감안하여 밝고 어두운 값은 픽셀 값 $ I_p \pm t $ 보다 크거나 작아야 합니다.

n=12를 사용함으로써 얻는 이득은 한가지가 더 있는데, 그것은 1, 5, 9, 13번 픽셀, 이 4개의 픽셀믄을 조사하여 코너가 아닌지를 먼저 판단할 수 있다는 점입니다. 4개 픽셀의 테스트를 통과한 픽셀만 16개의 픽셀에 대해 먼저 조사함으로써 시간을 절약할 수 있습니다.

사실 이 FAST 방법은 저자가 이전에 제안한 방법인데, 이것의 단점 4가지를 논문에서 언급하고 있습니다. 간단히 이야기하면 알고리즘의 성능이 n에 영향을 받는 것과 계산에 사용되는 원형 픽셀은 코너 주변에 대한 어떠한 가정을 토대로 이루어져 있다는 것, 그리고 비슷한 코너들이 뭉쳐서 검출된다는 점입니다.

2.2 Machine learning a corner detector

앞에서 언급한 문제점 중, 앞의 2가지를 해결하기 위하여 이제 기계학습 방법인 ID3를 적용하고자 합니다. 따라서 학습에 이용할 트레이닝 이미지가 필요합니다.

먼저 기존의 FAST 방법을 이용하여 트레이닝 이미지에서 코너를 모두 구합니다. 그 결과는 $ K_p $라고 합시다. 그리고 이미지의 각 픽셀 p 에 대하여 그 주변의 원에 속하는 한 픽셀 $ x \in {1, ... 16 } $이 p보다 밝은지, 비슷한지, 어두운지를 판단하여 상태 $ S_{p \rightarrow x} \in {d, s, b}$를 부여합니다. 따라서 각 x마다 이를 계산을 해야하므로, 각 픽셀은 모든 방향에 따른 16개의 상태 값을 할당받게 됩니다.

이제 앞에서 구한 상태 값을 토대로 상태 값에 따라 코너인지 아닌지를 빠르게 판단할 수 있도록 ID3 알고리즘을 통하여 결정트리를 생성합니다.

이 때, 어느 한 상태에 해당하는 픽셀들 $ p \in P $ 이 갖는 엔트로피는 다음과 같이 계산된다.

$$H(P) = (c + \bar{c})\log_2(c+\bar{c}) - c\log_2 c - \bar{c} \log_2 \bar{c}$$

여기서 $ c $ 는 $ P $ 내에 있는 코너의 수, $ \bar{c} $는 코너가 아닌 픽셀의 수를 의미합니다.

따라서 어느 한 x를 선택하였을 때, information gain은,

$$H(P) - H(P_d) - H(P_s) - H(P_b)$$

가 됩니다. $ P_d, P_s, P_b $는 한 x에 대하여 같은 상태를 할당 받은 픽셀의 세 집합입니다.

ID3 알고리즘에 따라 가장 정보가 많은 x를 선택합니다. 그리고 그 x의 세 픽셀 집합 $ P_d, P_s, P_b $은 다음으로 정보가 많은 x에 대하여 계속적으로 3개 집합으로 쪼개지면서 결정트리를 생성합니다. 결정트리가 완성되고 나면 이를 통하여 12개의 픽셀을 모두 조사할 필요없이 더 빠르게 판단할 수 있게 됩니다.

2.3 Non-maximal suppression

앞에서 언급한 코너들이 뭉쳐서 나오는 문제를 해결할 차례입니다. 다른 방법들과는 달리 코너에 대한 반응성을 계산하는 것이 아니기 때문에 각 코너에 대하여 함수를 새로 만들어줄 필요가 있습니다. 여기서는 주변에 있는 코너들에 대하여 함수 V를 적용해보고 가장 높은 값을 가지는 코너만을 남기도록 합니다.

$$v = \max( \sum_{x\in S_{\text{bright}}}|I_{p \rightarrow x} - I_p| - t, \sum_{x\in S_{\text{dark}}}|I_{p \rightarrow x} - I_p| - t)$$

2.4 Timing results

논문에 따르면 기존의 FAST 알고리즘보다 두 배정도 빠르며, n=9를 상ㅇ하였을 대가 가장 결과가 좋았다고 밝히고 있습니다.

5 Conclusions

저자가 밝히는 장점은,

• 다른 코너 검출 방법보다 수배 빠르다.
• 큰 변화에서도 높은 반복성을 보인다.

단점은,

• 노이즈에 민감하다.
• 픽셀의 값을 직접 판단하기 때문에 양자화 상태에 따라 잘못 검출될 수 있다.
• 문턱치 t에 영향을 받는다.

을 언급하고 있습니다.