FAST Algorithm for Corner Detection

FAST Algorithm for Corner Detection

Goal

• 우리는 FAST algorithm의 기초를 알아볼 것입니다.
• 우리는 OpenCV 의 기능을 이용하여 corner 를 찾는 알고리즘인 FAST algorithm을 사용해 볼것 입니다.

Theory

몇 가지 feature 감지기를 보았고 그 중 많은 것들이 정말 좋습니다. 그러나 실시간 응용 관점에서 보면 충분히 빠르지 않습니다. 가장 좋은 예는 계산 자원이 제한적인 SLAM (Simultaneous Localization and Mapping) 모바일 로봇입니다.

이에 대한 해결책으로 Edward Rosten과 Tom Drummond가 2006 년 고속 코너 감지를위한 기계 학습 (2010 년에 개정)에서 FAST (Features from Accelerated Segment Test) 알고리즘을 제안했습니다. 알고리즘의 기본 요약은 다음과 같습니다. 자세한 내용은 원본 paper를 참조하십시오 (모든 이미지는 원본 paper에서 가져옵니다).

Feature Detection using FAST

1. 이미지에서 pixel $p$ 하나를 선택합니다.관심이 있는 지역인지 아닌지를 분별합니다.

   그것의 밝기강도를 $I_p$ 고 정의합시다.

   적절한 threshold value $t$ 을 선정합니다.

2. 테스트 단계에서 pixel 주변의 16개의 픽셀로 구성된 원을 고려한다. (아래의 이미지를 참고)

   

3. 이제, pixel $p$ 는 corner 이다. 만약, 거기에서 n 개의 set 이 존재한다면,

   원의 인접 픽셀(16 픽셀) 이 모두, $I_p + t $ 보다 밝거나 $ I_p - t $ 보다 어둡다면.

   (위의 이미지에서 흰색 dash line 으로 표시되는 부분). 위의 그림은 n 이 12로 선택되었을 때의 그림이다.

4. 많은 수의 non-corners 를 제외한 고속의 테스트가 제안되었습니다. 이 테스트는 오직 4개의 픽셀인 1, 9, 5, 13 (처음에는 1, 9 를 테스트 한후 이것이 너무 밝거나 어둡다면, 5와 13을 체크). 만약, $p$ 가 코너라면, 이중에 적어도 3개가 $I_p + t$ 보다 모두 밝거나 $I_p - t$ 보다 모두 어두워야 합니다. 만약, 둘다 아닌 경우에는 $p$ 는 코너가 될 수 없습니다.

그런 다음, 원의 모든 픽셀을 검사하면서 전체 세그먼트 테스트 기준을 전달 된 후보에 적용 할 수 있습니다. 이 검출기는 그 자체로 고성능을 나타내지 만 몇 가지 단점이 있습니다.

- $n <12$의 candidates 에서는 거부하지 않습니다.
- 픽셀의 선택은 질문의 순서 및 모서리 모양의 분포에 따라 효율성이 달라 지므로 최적이 아닙니다.
- high-speed tests 결과는 폐기됩니다.
- 여러 features 가 서로 인접하여 감지됩니다.

처음 3 개의 점은 machine learning적 접근 방식으로 해결됩니다. 마지막 것은 non-maximal suppression (최대가 아닌 억제)를 사용하여 다루게 됩니다.

Machine Learning a Corner Detector

1. training 이미지 세트를 선택하십시오 (선호하는 target application domain에서)

2. 모든 이미지에서 FAST 알고리즘을 실행하여 특징점을 찾습니다.

3. 모든 특징 점에 대해 벡터 주위에 16 픽셀을 저장합니다. 모든 이미지가 feature vector $P$ 를 얻도록해라.

4. 이 16 픽셀 안에 있는 각 픽셀 $(x)$ 은 아래의 3개의 상태중에 1가지 상태를 가질 수 있다. :

5. 이 상태들에 의존하여서 , the feature vector $P$

$P_d$ , $P_s$ , $P_b$ 의 3개의 서브 카테고리로 나누어 진다.

6. 새로운 boolean variable을 정의한다.

$K_p$ 는 $p$가 코너일때, true 이고 아닐 시에는 false 입니다.

7. true class에 대한 지식을 얻으려면, $K_p$변수를 사용하여 각 하위 집합을 쿼리하기 위해 ID3 알고리즘 (의사 결정 트리 분류기)을 사용합니다. $x$ 를 선택하고, 이는 $K_p$ 의 엔트로피를 측정하여candidate pixel 이 코너인지 아닌지에 대한 대부분의 정보를 생성합니다.

8. 이것은 엔트로피가 0이 될 때까지 모든 부분집합에 재귀 적으로 적용됩니다.

9. 이렇게 생성 된 의사 결정 트리는 다른 이미지의 빠른 탐지에 사용됩니다.

Non-maximal Suppression

인접한 위치에서 여러 관심 지점을 감지하는 것도 또 다른 문제입니다. 이는 Non-maximum Suppression (비 최대 억제)를 사용하여 해결됩니다.

1. score function $V$ 모든 감지된 feature points에 대해서 계산합니다. $V$ 를 $p$ 와 주변 16 픽셀에 대해서 absolute differece 를 구해 더한 것을 구합니다.
2. 2개의 인접한 keypoints 를 구하고 그들의 $V$ 를 계산합니다.
3. 그중에 $V$ 값이 작은 하나를 버립니다.

Summary

다른 기존 코너 감지기보다 몇 배 더 빠릅니다.
그러나 높은 수준의 잡음에는 robust하지 않습니다. threshold 값에 따라 달라집니다.

FAST Feature Detector in OpenCV

OpenCV에서 다른 any other feature detector라고 불립니다. 원하는 경우 threshold, non-maximum suppression 를 적용할지 아닌지, neighborhood 를 사용할지 아닌지 등을 지정할 수 있습니다.

neighborhood에 대해 세 개의 플래그가 정의됩니다 (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
from matplotlib import pyplot as plt

img = cv2.imread('simple.jpg',0)

# Initiate FAST object with default values
fast = cv2.FastFeatureDetector()

# find and draw the keypoints
kp = fast.detect(img,None)
img2 = cv2.drawKeypoints(img, kp, color=(255,0,0))

# Print all default params
print "Threshold: ", fast.getInt('threshold')
print "nonmaxSuppression: ", fast.getBool('nonmaxSuppression')
print "neighborhood: ", fast.getInt('type')
print "Total Keypoints with nonmaxSuppression: ", len(kp)

cv2.imwrite('fast_true.png',img2)

# Disable nonmaxSuppression
fast.setBool('nonmaxSuppression',0)
kp = fast.detect(img,None)

print "Total Keypoints without nonmaxSuppression: ", len(kp)

img3 = cv2.drawKeypoints(img, kp, color=(255,0,0))

cv2.imwrite('fast_false.png',img3)

결과보기. 첫 번째 이미지는 nonmaxSuppression이있는 FAST이고 두 번째 이미지는 nonmaxSuppression이없는 이미지를 보여줍니다.

Additional Resources

1. Edward Rosten and Tom Drummond, “Machine learning for high speed corner detection” in 9th European Conference on Computer Vision, vol. 1, 2006, pp. 430–443.
2. Edward Rosten, Reid Porter, and Tom Drummond, “Faster and better: a machine learning approach to corner detection” in IEEE Trans. Pattern Analysis and Machine Intelligence, 2010, vol 32, pp. 105-119.

https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_fast/py_fast.html