Fast Algorithm for Corner Detection

출처 : https://docs.opencv.org/master/df/d0c/tutorial_py_fast.html

OpenCV: FAST Algorithm for Corner Detection

※ 본 포스팅은 위의 링크 글을 번역한 것입니다.

 

목차)

1. FAST Algorithm for Corner Detection(2006)

2. Machine Learning a Corner Detector(2010)

3. 결론

4. FAST Feature Detector in OpenCV

---

FAST Algorithm for Corner Detection(2006)

- Fast(Features from Accelerated Segments Test) (link) by Edward Rosten and Tom Drummond

 

  1) 이미지에서 점 p를 선택한다. Intensity를 $I_p$ 라 한다.

  2) 적절한 Threshold(t)를 선택한다.

  3) 테스트할 픽셀을 둘러싸는 16 pixel 원형을 선택한다.

  4) 원 안에 연속하는 $I_p$보다 어두운 픽셀($ I_i < I_p - threshold $) 혹은

      연속하는 $I_p$보다 밝은 픽셀 ($ I_i > I_p + threshold $) 픽셀이 있다면 점 p는 코너이다. 

      ex) 연속하는 픽셀 Threshold는 예를 들어 n=12로 둘 수 있다.

 

  5) High-Speed Test는 코너가 아닌 점들을 빠르게 제거하기 위함이다.

    - 이 테스트는 1, 9, 5, 13번호인 4개의 픽셀만 검사한다. (가로, 세로 끝점)

    - 1, 9번 점이 너무 밝거나 어둡다면 테스트 한다. 그리고, 5, 13 번 점을 테스트한다.

    - 만약 p가 코너라면, 적어도 3개의 것이 $ I_p + thres $ 보다 밝거나, $ I_p - thres $ 보다 어두워야 한다. 

    - 만약에 위의 경우에 해당하지 않는다면, p는 코너가 아니다. 

    - 원의 모든 픽셀을 검사하여, 통과된 후보에 전체 세그먼트 테스트 기준(Full segment test criterion)(?) 을 적용할 수 있다. 

결국엔 가로, 세로 4지점 중 3지점이 p보다 모두 밝거나, 어두워야지 만이 코너가 될수 있다는 것이다. 직관적이고 단순하다.

 

6) 취약점

- n이 작아질 경우 코너 후보군이 많아 질 수 있다.

- 질문 순서(?)와 코너 분포에 따라 효율성이 달라지기 때문에 픽셀 선택이 항상 최적은 아니다.

- 고속 테스트(High-Speed Test) 결과는 버려진다

- 인접한 다중 피처들이 선택된다.

 

첫 3개의 점은 머신 러닝 방법으로 처리되며, 마지막 하나는 non-maximal suppression 방법으로 처리된다.

 

 

Machine Learning a Corner Detector(2010)

1. 학습을 위한 이미지 선택

2. 특징점 추출을 위한 FAST 알고리즘 구동

3. 모든 특징점에 대해, 주변 16 pixel을 저장한다. 추후 특징 벡터 P로 나타낸다.

4. 각 픽셀(x)은 아래 3가지 상태 중 하나를 가진다.

5. 이 상태에 따라 특징 벡터 P는 3가지 집합으로 나뉜다. $P_d$, $P_s$, $P_d$.

6. Boolean 변수 $K_p$는 p가 코너면 True, 아니면 False 값을 가진다.

7. ID3 알고리즘(의사 결정 분류기)를 사용하여 실제 클래스에 대한 지식에 대해 변수 $K_p$를 사용하여 각 하위 집합을 쿼리(?) 합니다. $K_p$ 엔트로피로 측정한 후보 픽셀이 모서리인지 여부에 대한 가장 많은 정보를 담고 있는 픽셀(x)를 선택한다.

8. 엔트로피가 '0'이 될때 까지, 모든 하위 집합에 대해 재귀적으로 적용한다.

9. 생성된 의사 결정 트리는 다른 이미지에서 빠르게 감지하는데 사용된다.

 

 

결론

- 다른 코너 탐지기 보다 몇배 빠르다.

- 하지만, 노이즈에 견고하지 못하며 Threshold에 결과를 의존하게 된다.

 

OpenCV 함수

- Input 형식 : Mat 

- Output 형식 : vector<Point2f> 

void featureDetection(IN Mat img_1, OUT vector<Point2f>& points1)	
{ 
  vector<KeyPoint> keypoints_1;
  int fast_threshold = 20;
  bool nonmaxSuppression = true;
  FAST(img_1, keypoints_1, fast_threshold, nonmaxSuppression);
  KeyPoint::convert(keypoints_1, points1, vector<int>());
}

 

FAST Feature Detector in OpenCV

- 이웃점에 대해 처리하는 3가지 Flag가 있다.

- cv.FAST_FEATURE_DETECTOR_TYPE_5_8, cv.FAST_FEATURE_DETECTOR_TYPE_7_12, 

  cv.FAST_FEATURE_DETECTOR_TYPE_9_16

import numpy as np
import cv2 as cv
from matplotlib import pyplot as plt

img = cv.imread('blox.jpg',0) # `<opencv_root>/samples/data/blox.jpg`

# Initiate FAST object with default values
fast = cv.FastFeatureDetector_create()

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

# Print all default params
print( "Threshold: {}".format(fast.getThreshold()) )
print( "nonmaxSuppression:{}".format(fast.getNonmaxSuppression()) )
print( "neighborhood: {}".format(fast.getType()) )
print( "Total Keypoints with nonmaxSuppression: {}".format(len(kp)) )

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

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

print( "Total Keypoints without nonmaxSuppression: {}".format(len(kp)) )

img3 = cv.drawKeypoints(img, kp, None, color=(255,0,0))
cv.imwrite('fast_false.png', img3)

 

(좌) FAST 알고리즘, (우) FAST 알고리즘 without NMS

 

---

https://docs.opencv.org/master/df/d0c/tutorial_py_fast.html