성능이 좋은 특징 검출기는 많이 존재합니다. 하지만 실시간 어플리케이션 관점에서 봤을 때, 처리 속도가 생각보다 느립니다. 한 가지 좋은 예시로 계산 리소스가 제한된 SLAM(Simulataneous Localization and Mapping) 모바일 로봇입니다.
이에 대한 해결책으로 FAST(Features from Accelerated Segment Test)는 특징점을 추출하고 이후 많은 컴퓨터 비전 작업에서 객체를 추적 및 매핑하는 데 사용할 수 있는 코너 검출 방법입니다. FAST 코너 검출기는 Edward Rosten과 Tom Drummond가 개발했으며, 2006년에 발표되었습니다. FAST 코너 검출기의 가장 큰 장점은 연산 효율성입니다. 또한 머신러닝 기술이 적용되면, 연산 시간과 자원 측면에서 우수한 성능을 실현할 수 있습니다. FAST 코너 검출기는 이러한 빠른 처리 속도 때문에 실시간 영상 처리 어플리케이션에 가장 적합합니다.
FAST를 사용한 특징 검출 (Feature Detection using FAST)
- 영상에서 관심점으로 식별된 픽셀 p를 선택합니다. Ip는 픽셀의 강도입니다.
- 적절한 임계값 t를 설정합니다.
- 픽셀 p 주위의 16 픽셀의 원을 계산합니다.
- 원에서 Ip + t 보다 더 밝거나 Ip - t 보다 더 어두운 n개의 연속된 픽셀 집합이 존재할 경우 픽셀 p를 코너로 판단합니다. (해당 예시에서는 n = 12)
- 알고리즘을 빠르게 만들려면 먼저 원의 픽셀 1, 5, 9, 13의 강도를 Ip와 비교합니다. 이 네 개의 픽셀 중 적어도 세 개는 관심점이 존재하도록 임계값 기준을 충족해야 합니다.
- 네 개의 픽셀 값(I1, I5, I9, I13) 중 3개 이상이 lp + t보다 크거나 같지 않으면, p는 관심점(코너)가 아닙니다. 따라서 픽셀 p를 관심점 후보에서 제외합니다. 만약 3개 이상이 lp + t보다 크거나 작으면 16개 픽셀을 모두 확인하고 12개의 연속된 픽셀이 기준을 만족하는지 확인합니다.
- 영상의 모든 픽셀에 대해 이 과정을 반복합니다.
이 알고리즘에는 몇 가지 제한이 있습니다. 첫 번째로, n < 12일 경우, 검출되는 관심점의 수가 매우 많아지기 때문에 알고리즘이 느려질 수 있습니다. 두 번째로는 16개의 픽셀들이 조회되는 순서에 따라 알고리즘의 속도가 달라집니다. 이러한 문제를 다루기 위해 머신러닝 접근법이 알고리즘에 추가되었습니다.
머신러닝 접근법 (Machine Learning Approach)
- 훈련시킬 영상 세트를 선택합니다. (가급적이면 타겟 어플리케이션 도메인의 영상이 좋습니다.)
- FAST 알고리즘을 통해 모든 영상의 특징점을 찾습니다.
- 모든 특징점에 대해 주변의 16 픽셀을 벡터로 저장합니다. 특징 벡터 p를 얻기 위해 모든 이미지에 대해 해당 작업을 수행합니다.
- 이 16 픽셀의 각 픽셀 x는 아래 세 개의 상태를 가질 수 있습니다.
- 이러한 상태에 따라 특징 벡터 P는 Pd, Ps, Pb의 3가지 하위 집합으로 나뉩니다.
- 변수 Kp를 정의합니다. p가 관심점이라면 true, 관심점이 아니라면 false가 됩니다.
- ID3 알고리즘(결정 트리 분류기)을 사용하여 true 클래스에 대한 지식(knowledge)에 대해 변수 Kp를 사용한 각 하위 집합을 질의(query)합니다. (참고 : https://ko.wikipedia.org/wiki/%EA%B5%AC%EA%B8%80_%EC%A7%80%EC%8B%9D_%EA%B7%B8%EB%9E%98%ED%94%84)
- ID3 알고리즘은 엔트로피 최소화 원리로 작동합니다. 최소 쿼리 수로 실제 클래스(관심점 유무)를 찾을 수 있도록 16 픽셀을 질의합니다. 또는 픽셀 p에 대한 정보가 가장 많은 픽셀 x를 선택합니다. 집합 P의 엔트로피는 수학적으로 다음과 같이 나타낼 수 있습니다.
- 엔트로피가 0이 될 때까지 모든 하위 집합에 반복적으로 적용됩니다.
- 이렇게 만들어진 의사 결정 트리는 다른 영상에서 빠르게 검출하기 위해 사용됩니다.
비최대 억제 (Non-maximal Suppression)
인접한 위치에서 여러 관심점을 검출하는 것은 또 다른 문제입니다. 비최대 억제(Non-maximal Suppression)를 사용하여 해결합니다.
- 검출된 모든 특징점에 대해 score function V를 계산합니다. V는 p와 주변 16개의 픽셀 값 사이의 차이에 대한 절대값의 합계입니다.
- 인접한 두 특징점을 고려하여 V 값을 계산합니다.
- V 값이 낮은 것은 제외합니다.
FAST 알고리즘의 한계 (Limitations of the FAST Algorithm)
다른 코너 검출 방법들은 FAST 알고리즘과 아주 다르게 동작하며, FAST 알고리즘은 x축과 y축에 대해 완벽하게 정렬된(평행한) 컴퓨터 생성 영상(computer-generated images)에서 코너를 검출하지 못합니다. 검출된 코너의 양쪽 엣지들를 포함하는 중심 주변에 어둡거나 밝은 픽셀 값의 원이 있어야 하므로 선명한 영상이 제대로 동작하지 않습니다.
FAST 알고리즘은 코너 중심 주변에 4분의 3 이상의 대비되는 픽셀들로 구성된 원이 필요하기 때문입니다. 컴퓨터 생성 영상에서 코너에 있는 상자의 양쪽 엣지들은 사용된 픽셀의 원에 있으므로 코너 테스트가 실패합니다. 이 문제에 대한 해결 방법은 코너 판단 정확도는 떨어지지만 검출은 할 수 있도록 영상에 (가우시안 필터를 사용한) 블러를 적용하는 것입니다.
(원 저작자에게 이용 허락을 받고 옮긴 글입니다.)
Introduction to FAST (Features from Accelerated Segment Test)
Features from accelerated segment test (FAST) is a corner detection method, which could be used to extract feature points …..
medium.com