[AGAST] Adaptive and Generic Corner Detection Based on the Accelerated Segment Test

FAST Corner Dection보다 빠른 방법에 관한 내용

링크 : http://www6.in.tum.de/Main/ResearchAgast

소스코드 다운로드 : http://sourceforge.net/projects/agastpp/

3.1 Configuration Space for a Binary Search Tree

FAST 처럼 공간 구성을 제한하는 것 대신에, 우리는 좀 더 효율적인 해답을 제공하기 위해 좀 더 세분화된 공간을 구성한다. 이러한 것을 하기위해서는 우리는 시간당 하나의 질문을 평가하는 것을 고려한다. 이러한 아이디어는 다음과 같다.

검사할 픽셀 중에 하나를 선택하고, 하나의 질문을 제기한다.

그 질문은 주어진 픽셀을 평가하는 것이며, 그 응답은 다음 픽셀과 질문을 결정하는데 사용된다.

따러서 코너를 찾는 것은 이진 결정 트리를 횡단하는 것으로 줄일 수 있다

질문할 픽셀을 구체화 하기 위해 요구된다. 결과적으로 두개 이상의 상태를 증가시킴으로 공간 구성은 증가한다.

 

S' 은 선행되는 상태이며, I은 픽셀의 밝기 값이다. 또한 u는 아직 알지 못하는 상태이다. 이진 트리로 표현할 경우, 세개로 이루어진 트리와는 다르게, 각 노드당 한번의 평가만을 허락한다. 구성 공간의 크기가 6^n 이므로 2진 트리로 표현하면 n=16일 때 2*10^12이다.

3.2 Building the Optimal Decision Tree

greedy 알고리즘으로 잘 알려진 ID3는 최적 결정 트리를 찾을때 잘 동작하지 않는다?

그러나 그러한 트리를 찾는 건 잘 알려진 문제이며, 전역 최적 해를 찾는 것은 NP 문제이다.

최적 트리를 찾는 방향의 몇개의 해답도 있다.

그러나, 전역 최적해를 근사하거나, 특정 경우로 제한된다.

최적 결정 트리를 찾기 위해 우리는 Backward induction Method[16] 와 유사한 알고리즘을 구현하였다.

우리는 결정 트리의 루트부터 구성 공간 전체를 방문한다. 

3.3 Adaptive Tree Switching

이부분이 핵심 부분인듯함.

다음에 다시 봐야겠네여.