728x90

< FAST Algorithm for Corner Detection >

이번 장에서는

FAST 알고리즘의 기본에 대해서 이해하고
FAST 알고리즘을 이용하여 모서리를 찾을 것이다.

Theory

지금까지 여러가지의 특성 탐지법을 봤고 대다수가 괜찮았다. 하지만 실시간의 관점을 볼 때, 그 방법들은 충분히 빠르지 않다. 한 가지 가장 좋은 예시는 제한된 연산 자원을 가진 SLAM 모바일 로봇이다.

이에 대한 해결책으로, FAST 알고리즘이 2006년에 등장했다. 알고리즘에 대한 간단한 요약을 아래를 참조하자. 해당 논문에 더 자세한 설명이 있다!

Feature Detection using FAST

관심이 있는 지점 혹은 아닌 이미지내의 픽셀 p를 고른다. 이 픽셀의 강도(intensity)를 Ip 라고 하자.
적합한 임계값인 t를 고른다.
테스트 대상 픽셀 주위의 16개 픽셀의 원을 고려한다.

아래 사진을 보면 이해가 쉽다.

픽셀 p 주변에 점선으로 원을 그려 16개의 픽셀을 골라내는 것이다.

이제 픽셀 p는 원안에 Ip+t보다 모두 밝은 n개의 인접 픽셀이 있거나, Ip−t보다 모두 어두운 경우 모서리가 된다. n은 12로 정해졌다.
모서리가 아닌 큰 수를 제외시키기 위해 고속 테스트가 제안되었다. 이 테스트는 4개 픽셀 1,9,5,13만 검사한다.(첫 1과 9는 그들이 너무 밝거나 어두울 때 테스트된다. 그렇다면 5, 13을 확인한다) 만약 p가 모서리라면 이 중에서 적어도 3개는 Ip+t 보다 밝거나, Ip−t보다 어두워야한다. 이런 경우 둘 다 아니라면, p는 모서리가 될 수 없다.

하지만 다음과 약점이 존재한다.

n < 12인 경우 테스트하려는 픽셀 후보들을 많이 버리지 못한다.
이미지 검출 효율성이 질문의 순서와 모서리 형태의 분포에 의존적이기에 픽셀 선택은 최적이 아니다.
고속 테스트의 결과는 버려진다.
모서리 주변으로 다중 특성들이 발견된다.

1~3번 약점은 머신러닝 접근으로 해결되고, 마지막은 NMS(Non-Maximal Suppresion)으로 해결된다.

Machine Learning a Corner Detection

학습을 위한 이미지 세트를 선택한다.
모든 이미지에 대해 FAST 알고리즘을 실행시켜 특징점을 찾아낸다.
모든 특징점에 대해, 주변 16개의 픽셀을 벡터로서 저장한다. 특징 벡터 P를 얻기 위해, 이를 모든 이미지에 대해 실행한다.
16개중 각 픽셀은 다음과 같은 3가지 상태의 값을 가질 수 있다.

이 상태에 의존하여, 특징 벡터 P는 3가지로 나뉜다. Pd,Ps,Pb
p가 모서리면 True이고 아니면 False인 boolean 변수인 Kp를 정의한다.
Pd,Ps,Pb에 Kp변수를 이용하여 ID3 알고리즘(의사결정나무 분류기)을 사용한다. Kp의 엔트로피를 측정함으로써 후보 픽셀이 모서리인지 아닌지에 대해 많은 정보를 제공하는 픽셀 x를 선택한다.
이는 엔트로피가 0이 될 때 까지 하위집합(Pd,Ps,Pb)에 대해 재귀적으로(Recursively) 적용된다.
다른 이미지내의 빠른 탐지가 가능한 의사결정나무가 생성된다.

NMS (Non-Maximal Suppresion)

인접한 지역에서 복수의 관심 지점을 탐지한 것도 문제이다. 이러한 문제들이 NMS를 이용하여 해결될 수 있다.

스코어 함수 V를 탐지된 모든 특성점들에 대해 계산한다. V는 p와 이를 둘러싼 16개 픽셀 값들 간의 차이의 절대값을 모두 더한 것이다.
두 개의 근접한 키포인트를 고려하고 그들의 V값을 계산한다.
낮은 V값을 가지는 하나를 제거한다.

Summary

이는 존재하는 다른 모서리 탐지기보다 몇 배 빠르다.

하지만 높은 정도의 노이즈에 강건하지 않다.(노이즈 많을수록 결과상태가 안좋음) 이는 임계값에 의존적이다.

FAST Feature Detector in OpenCV

이것은 OpenCV에서 다른 특징 검출기로 불린다. 원하는 경우, 임계값, NMS 적용여부, 사용할 인접값등을 지정할 수 있다.

인접부에 대해, 3가지 플래그가 정의된다.

cv2.FAST_FEATURE_DETECTOR_TYPE_5_8,cv2.FAST_FEATURE_DETECTOR_TYPE_7_12,cv2.FAST_FEATURE_DETECTOR_TYPE_9_16
아래의 코드는 FAST 특성점을 어떻게 찾고 그리는지 보여준다.

import numpy as np
import cv2

img = cv2.imread('./images/cube.jpg')
img = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
img2,img3 = None,None

# 디폴트 값으로 FAST 객체를 시작한다
# ()안에 임계값 넣기
fast = cv2.FastFeatureDetector_create(100)

# 키포인트를 찾고 그린다
kp = fast.detect(img,None)
img2 = cv2.drawKeypoints(img,kp,img2,(255,0,0))
cv2.imshow('FAST1',img2)

# NMS 사용 X
fast.setNonmaxSuppression(0)
kp = fast.detect(img,None)
img3 = cv2.drawKeypoints(img,kp,img3,(255,0,0))
cv2.imshow('FAST2',img3)

cv2.waitKey(0)
cv2.destroyAllWindows()

위의 결과가 NMS를 사용해서 검출된 부분이 더 적은 것을 볼 수 있다. 임계값은 100으로 지정했다.

NMS를 사용하지 않은 결과이다.