FAST (Features from Accelerated Segment Test)

FAST(Rosten & Drummond, 2006)는 단 하나를 위해 설계된 코너 검출기다: 속도. 이미지 기울기와 구조 텐서를 계산하거나(Harris/Shi-Tomasi) 스케일 공간을 구성하는 것(SIFT) 대신, FAST는 후보 픽셀 주변의 작은 원 위에서 몇 개의 강도 비교만으로 코너인지 아닌지를 결정한다 — 매 프레임의 모든 픽셀에서 고속으로 실행할 수 있을 만큼 저렴하며, 이 덕분에 실시간 SLAM 프론트엔드(PTAM, SVO, 그리고 ORB를 통해 ORB-SLAM 계열)의 기본 검출기가 되었다.

세그먼트 테스트

강도 $I_p$ 를 가진 후보 픽셀 $p$ 와, 그 주위 반지름 3인 브레젠험 원 위의 16개 픽셀을 생각해 보자. 픽셀 $p$ 는 이 원 위에 최소 $n$ 개의 연속된 호가 존재하고, 그 호에 속한 모든 픽셀이 임계값 $t$ 가 주어졌을 때 $p$ 보다 유의미하게 밝거나 모두 유의미하게 어두우면 코너로 판정된다.

\forall x \in \text{arc}: \quad I_x > I_p + t \qquad \text{or} \qquad \forall x \in \text{arc}: \quad I_x < I_p - t

고전적인 선택은 $n = 12$ (FAST-12: 16개 중 12개)이며, 이는 매우 효과적인 **고속 테스트(high-speed test)**를 허용한다: 나침반 방향의 네 픽셀(위, 오른쪽, 아래, 왼쪽 — 위치 1, 5, 9, 13)만 검사한다. 12픽셀 연속 호가 존재한다면, 이 네 개 중 최소 세 개는 $I_p + t$ 보다 밝거나 $I_p - t$ 보다 어두워야 한다. 세 개 미만이 통과하면 $p$ 는 단 네 번의 비교만으로 거부된다. 이미지 픽셀의 대부분은 코너가 아니므로, 이 조기 종료가 평균 비용을 지배한다.

기계 학습 변형

수공예 나침반 테스트에는 두 가지 약점이 있다: $n < 12$ 로 일반화되지 않으며, 고정된 질문 순서가 실제 이미지 통계에 대해 최적이 아니다. 그래서 Rosten과 Drummond는 검출기를 학습했다: 원 위의 16개 픽셀 각각을 $I_p$ 에 대해 밝음/어두움/유사로 분류하고, (정보 이득을 최대화하는 ID3 알고리즘으로 구축된) 결정 트리가 학습 이미지에서 가장 적은 예상 비교 횟수로 코너를 분류하는 픽셀 질의 순서를 학습한다. 트리는 중첩된 if문으로 컴파일된다. 이렇게 해서 FAST-9( $n = 9$ ) — 보통 가장 반복성이 높은 변형 — 가 실용적으로 만들어졌으며, 이는 OpenCV의 cv::FastFeatureDetector가 구현하는 방식이다.

비최대 억제

세그먼트 테스트는 하나의 코너 주변의 여러 인접 픽셀에서 반응한다. 코너당 하나의 응답만 유지하기 위해, 각 검출에 대해 코너 점수가 계산된다.

V = \max\!\left( \sum_{x \in S_{\text{bright}}} (I_x - I_p) - t,\;\; \sum_{x \in S_{\text{dark}}} (I_p - I_x) - t \right),

즉 뒷받침하는 호의 최대 총 대비이며, 비최대 억제는 3×3 근방에서 $V$ 의 지역 극댓값만 유지한다. SLAM 프론트엔드에서는 검출 결과가 추가로 이미지 격자로 버킷화되어, 특징이 하나의 텍스처가 있는 영역에 몰리지 않고 프레임 전체를 커버하게 한다.

변형

FAST-9 / FAST-12: 호의 길이 $n$ . FAST-9는 더 많은 코너를 검출하고 보통 가장 반복성이 높으며, FAST-12는 학습된 트리가 없어도 4픽셀 조기 종료를 허용한다.
AGAST(Mair 외, 2010): 단일 학습된 트리를 런타임의 지역 이미지 통계에 적응하는 범용 결정 트리로 대체하여, 학습 이미지에 대한 의존을 제거한다(BRISK에서 사용).
oFAST: ORB의 FAST에 패치의 강도 중심으로부터 얻은 방향각을 더하고, 이미지 피라미드에 걸친 검출과 검출 결과를 순위화·정리하기 위한 Harris 응답을 추가한 것.

FAST가 제공하지 않는 것

디스크립터 없음 — FAST는 위치만 찾는다. BRIEF/ORB와 짝지어 쓰거나 KLT 트랙 또는 직접 정합(direct alignment)의 시드로 사용된다.
스케일 불변성 없음 — 여러 스케일에서 코너를 검출하려면 이미지 피라미드의 모든 레벨에서 실행해야 한다.
방향 정보 없음 — ORB의 oFAST가 패치의 강도 중심을 통해 방향을 추가한다.
임계값 민감성 — 단일 전역 $t$ 는 대비가 다른 장면들에 걸쳐 잘 동작하지 않는다. 시스템은 셀별로 $t$ 를 조정하거나 특징이 너무 적게 발견되면 완화한다(ORB-SLAM이 하는 방식).

SLAM에서의 의미

특징 검출은 트래킹 루프 안에서 매 프레임마다 실행되므로, 그 비용은 임베디드 하드웨어에서 달성 가능한 프레임 레이트를 직접 제한한다. FAST는 완전한 검출-기술-매칭 파이프라인을 CPU에서 실시간으로 만들었다 — PTAM은 트래킹에 FAST를 사용했고, SVO는 FAST 코너에서 깊이 필터를 시드하며, VIO 프론트엔드(VINS-Mono, MSCKF 구현체들)는 FAST 코너를 검출해 KLT로 추적하고, ORB(oFAST + rBRIEF)는 이를 ORB-SLAM 계열의 완전한 특징으로 만들었다. 세그먼트 테스트를 알면 실전에서 관찰하게 될 FAST의 실패 모드도 설명된다: 잡음 하의 에지에서의 반응, 고대비 텍스처에서의 클러스터링, 모션 블러에 대한 민감성(기울기가 뭉개지면 원의 대비가 무너진다).

실습

고전적 지역 특징 검출