FAST( Features from Accerlerated Segment Test) 알고리즘

Corner

• 서로 다른 방향에서 변화가 크게 발생하는 영역.
  쉽게 말하면, edge가 2개 이상 만나는 지점이 코너라고 할 수 있다.
  • 코너는 영상에서 특정위치를 추적하거나, 패턴을 매칭하는데 중요한 역할을 한다.
  • Fast에서는 반지름 3인 원을 활룡한 코너 검출 방식으로 빠르게 검출함

 

FAST 알고리즘

• 컴퓨터 비전에서 특징점( corner , keypoint )검출을 빠르게 수행하는 알고리즘이다. 
  
  • 특히 slam , 영상 기반 물체 인식 , 영상 스티칭등에 많이 사용됨.
• 2006년에 제안된 알고리즘이며, 기존의 harris 코너 검출기보다 훨씬 빠르다.
• 기본 아이디어
  • FAST는 픽셀의 주변의 16개 이웃을 원형 형태로 배치하고, 특정한 패턴을 만족하는지 확인하여 코너를 검출함.
    • 1. 기본적인 원형 구조
      • 중심 픽셀 p의 주변에 반지름이 r=3인 원을 형성한다.
        그러면 원 위에 총 16개의 픽셀이 존재할 것 이다.
    • 2. 원을 이용한 corner 판별의 행심 아이다어
      • 중심 픽셀 p의 밝기 값과 16개의 원형 이웃 픽셀의 밝기 값을 비교한다.
        • 이때 코너를 정의하는 조건은 아래와 같다.
          • 이웃한 픽셀들 중에서 최소한 12개 이상이 중심 픽셀보다 '밝거나 어두운 방향으로' 크게 차이가 나야 corner로 판단한다.
          • ==> 즉, 12개 이상이 연속적으로 밝거나 어두운 경우에만 corner라고 판단한다.

• 장점
  • 속도가 매우 빨라서 실시간 시스템에서 활용이 가능. 
  • 계산량이 적어서 임베디드에서도 사용 가능
• 단점
  • scale변화에 취약하며 rotation에 약할수있음
  • 코너 응답이 정확하지 않을수도 있음 

 

 

 

FAST 알고리즘의  동작 과정

• 1. 중심 픽셀 p 를 선택
  • 입력 영상에서 특정한 하나의 픽셀을 선택해서 분석한다.
• 2. 주변 원형 픽셀 16개를 탐색
  • 픽셀의 좌표를 기준으로 반지름이 3인 원을 구성한다. 그리고 해당 픽셀들에 대한  밝기값도 저장한다.
• 3. FAST에 대한 조건 검사
  • FAST는 corner를 판별하기 위해서 아래 2가지의 질문을 확인한다.
  • 3-1. 4개 픽셀의 빠른 검사 ( First 4-point Test )
    • 속도를 높이기 위해서, 전체 16개를 검사하기 전에 특정 4개 픽셀만 먼저 검사한다. ( 검사하는 픽셀의 위치는 상,하,좌,우 4개이다. 1,5,9,13번 픽셀 )
      
      • ==> 4개중에서 3개 이상이 '밝거나 어두운 조건'을 만족 못하면 즉시 탈락. ( 탈락하면 더 이상 연산을 수행할 필요없이 다음 픽셀로 이동 한다. )
  • 3-2. 전체 16개 픽셀 검사 ( 12개의 연속 조건 )
    • 만약에 4개 픽셀 검사를 통과한다면, 전체 16개를 본격적으로 검사한다. 
      • ==> 16개 중에서 12개 이상이 '밝거나 어두운 조건' 만족시에만 corner라고 판단.
• 4. 결과 저장 및 다음 픽셀로 이동한다.
  • corner라고 판별된 경우에, 해당 위치를 특징점으로 저장함. 그리고 다음 픽셀을 선택하고 같은 과정을 반복한다.

 

 

import numpy as np
import cv2
import matplotlib.pyplot as plt

def detect_fast_features( image_path , threshold=50 , nonmax_suppression=True ):
    image = cv2.imread( image_path )
    gray = cv2.cvtColor( image , cv2.COLOR_BGR2GRAY )

    fast = cv2.FastFeatureDetector_create( threshold=threshold , nonmaxSuppression=nonmax_suppression )

    keypoints = fast.detect( gray , None )

    image_with_keypoints = cv2.drawKeypoints( image , keypoints , None , color=( 0 , 255 , 0 ) )

    plt.figure( figsize=(15,15) )
    plt.imshow( cv2.cvtColor( image_with_keypoints , cv2.COLOR_BGR2RGB ) )
    plt.axis("off")
    plt.title(f' fast keypoints ( threshold={threshold} , Nonmax Suppression={nonmax_suppression}) ' )
    plt.show()

    return keypoints
    
    
    
    
detect_fast_features("chess.jpg", threshold=50, nonmax_suppression=True)

원본

• cv2.FastFeatureDetector_create(threshold=None, nonmaxSuppression=None, type=None)
  
  • opencv에서 FAST알고리즘으로 keypoint를 검출하는 객체를 생성하는 함수이다.
    • threshold는 중심 픽셀과 주변 16개 픽셀의 밝기 차이를 비교해서 corner를 판단하는 임계값이다.
      기본값은 10이며, 일반적으로 30~60의 값을 설정하는 것이 적절하다. ( 값이 높을수록 검출되는 keypoint의 수가 줄어든다. )
    • nonmaxSuppression은 비최대 억제 여부를 설정하는 boolean값이다. 기본값은 True이다.
      True로 설정시 검출된 특징점 중에서 가장 강한 반응을 보이는 점만 선택하여 중복된 특징점을 제거하는 기능을 활성화 하는것. (  False이면 모든 검출된 특징점을 반환 )
    • type은 corner검출 방법을 지정하는 값이다. 기본값은 cv2.FAST_FEATURE_DETECTOR_TYPE_9_16이다. ( 이는 16개 주변 픽셀중 9개 이상의 픽셀이 기준보다 밝거나 어두운 경우에 corner로 판단. )

 

 

• fast.detect(img, None)
  • 입력된 이미지에서 특징점을 검출하는 부분이다.
  • image는 입력이미지이며, grayscale image이어야함.
  • mask는 선택 사항이며, 특징점 검출을 제한할 영역을 지정하는 mask image이다.