Skip to content

Features from accelerated segment test

Features from accelerated segment test (FAST) is a corner detection method, which could be used to extract feature points and later used to track and map objects in many computer vision tasks. The FAST corner detector was originally developed by Edward Rosten and Tom Drummond, and was published in 2006. The most promising advantage of the FAST corner detector is its computational efficiency. Referring to its name, it is indeed faster than many other well-known feature extraction methods, such as difference of Gaussians (DoG) used by the SIFT, SUSAN and Harris detectors. Moreover, when machine learning techniques are applied, superior performance in terms of computation time and resources can be realised. The FAST corner detector is very suitable for real-time video processing application because of this high-speed performance.

About

FAST(Features from Accelerated Segment Test)도 코너를 찾는 알고리즘이다. 이름처럼 빠른 연산으로 유명하다.

  1. 한 픽셀 𝑝를 중심으로하는 3픽셀의 반지름을 가지는 원을 만들고,
  2. 그 원 위의 16개의 픽셀 값을 보고 코너를 찾는다.
  3. 𝑝보다 기준값 이상 밝거나, 어두운 픽셀들이 𝑛개 이상 연속적으로 존재하면 𝑝 를 Corner로 판단한다.

𝑛에 따라 FAST-9, FAST-10, FAST-11, FAST-12 등의 여러 버전이 가능하지만, FAST 논문에서는 FAST-9의 성능이 가장 좋다고 한다. 하지만, 이렇게 개수를 세는 방식은 너무 많은 픽셀을 코너라고 판단했고, 16개의 픽셀의 순서를 어떻게 하느냐에 따라서도 추출되는 코너가 바뀔 수 있다는 등등의 이유로 FAST에서는 그냥 숫자를 세어 코너를 판단하는 것이 아니라, Decision Tree를 이용해서 코너인가 아닌가를 판단한다. 이때, 16개의 픽셀은 기준값으로 𝑝보다 기준값보다 큰, 𝑝보다 기준값보다 작은, 𝑝와 유사한 밝기로 바꾸어 16차원의 벡터로 표현하고, 모든 픽셀, 모든 이미지에 대한 벡터를 쌓아 훈련시킨다. 이 때 타겟값은 특징점인지 아닌지인데, 이는 라벨링을 해주어야 한다. 또하나의 문제점은 한 점이 코너로 판단되면, 주변의 픽셀 또한 코너로 인식되는데, 이는 non-maximal suppression라는 후처리 작업으로 해결했다. 코너성을 대변하는 수치를 계산하고 이를 기준으로 인접 픽셀에 대해 가장 높은 코너성 수치를 가지는 픽셀만 코너로 선택하는 것이다.

Example

다음 코드는 FAST를 사용해 체크보드 이미지의 코너를 찾은 예이다. 

fast = cv2.FastFeatureDetector_create()
kps = fast.detect(img, None)
img2 = cv2.drawKeypoints(img, kps, img, color=(255, 255, 255))

print("기준값: ", fast.getThreshold())
print("nonmaxSuppression: ", fast.getNonmaxSuppression())
print("nonmaxSuppression 후처리 후, 추출된 전체 특징점: ", len(kps))
plt.figure(figsize=(7,7))
plt.imshow(img2, cmap='gray')
plt.title("FAST 로 찾은 Corner")
plt.axis("off")
plt.show()

See also

Favorite site

References

  1. Datascienceschool.net_-_7eb4b2a440824bb0a8c2c7ce3da7a4e2.ipynb.zip ↩