ORB ( Oriented Fast and Rotated BRIEF )

패치 Patch

• 이미지에서 특정 영역을 잘라낸 것을 의미. 즉, 특정 pixel을 중심으로 주변 픽셀을 포함한 '원본의 작은 부분 이미지'이다.

 

 

 

해리스 응답 함수 harris corner response ( 식1 )

 

ORB 

• 이미지에서 특징점(feature point)를 검출하고, 이를 기술(descriptor)하는 방법중 하나이다.
• SIFT나 SURF와 같은 알고리즘을 대체할수 있는빠르고 가벼운 방법이다.
• 알고리즘 개요
  • ORB는 2가지 주요 알고리즘을 결합한 방식으로 구성됨.
    • 1. FAST( Features from Accerlerated Segment Test) 코너 검출을 개선하여 특징점을 찾음
    • 2. BRIEF ( Binary Robust Independent Elementary Features ) 디스크립터를 회전에 강하게 변형해서 특징점을 기술한다.
• 주요 동작 과정
  • 1. keypoint detection  =>  FAST 적용 + Harris corner 응답값을 사용한 정제
  • 2. keypoint ordering  =>  FAST로 검출된 keypoint를 강한 순서대로 정렬
  • 3. 스케일 불변성 확보  => 이미지 피라미드 활용 
    • 스케일 불변성 : 동일한 물체에 대해서, 보는 위치나 거리가 달라져도 같은 물체는 동일하게 인식할 수 있는 능력
  • 4. Orientatation Assignment ( 특징점 방향  할당 ) -> 회전에 강한 BRIEF를 생성하기 위한 방향 계산
  • 5. Descriptor Computation ( 디스크립터 생성 ) -> BRIEF를 회전에 강하게 변형
• 장점
  • 1. SIFT , SURF보다 계산 속도가 훨씬 빠르다.
  • 2. SIFT , SURF는 특허가 있으나, ORB는 무료로 사용가능
  • 3. FAST + harris corner response + rBRIEF 적용으로 강한 불변성 제공
  • 4. Hamming 거리 기반 매칭이 가능해서 빠른 매칭 가능 ( BRIEF에서 추가된거 )
• 단점
  • 1. 이진 descriptor 특성상 명암 변화에 영향을 받을 수 있음.
  • 2. 빠른 연산을 위해서 정밀도를 희생함.... 이로 인해 SIFT/SURF보다 정확도가 떨어질수있음.

 

 

 

 

 

식2. Gradient in X-axis ( 오른쪽 픽셀과 왼쪽 픽셇의 차이 )

식3. Gradient in Y-axis ( 아래쪽 픽셀과 위쪽 픽셀의 차이 )

식4. 전체 패치의 gradient 합산

식5. orientation 계산

식 6 . 회전보강의 과정

ORB의 상세과정

• 1. 특징점 검출 ( FAST  + harris corner response값 )
  • 1-1. 우선 ORB는 FAST알고리즘을 사용해서 keypoint를 검출한다. 하지만 FAST는 강한 corner를 구별하는 능력이 부족하기에, ORB는 harris corner response를 이용하여 특징점들을 정렬한다. ( 식 1 참고 )
• 2. 이미지 피라미드를 활용하여 스케일 불변성 확보
  • SIFT/SURF처럼 이미지 피라미드를 사용하여, 다양한 스케일에서도 특징점을 검출할수있게 한다.
    • 1. image pyramid는 origin image에서 점점 축소된 이미지(다중 해상도)를 생성
    • 2. 각각의 피라미드 레벨에서 FAST특징점을 검출 
    • 3. 특징점의 크기를 pyramid 레벨에 따라서 조절하여, 스케일 불변성 확보
• 3. orientation assignment ( ORB의 방향 계산 )
  • FAST특징점에는 회전 불변성이 없다. 그래서 이를 해결하고자 패치 내 픽셀들의 gradient를 계산하여 방향을 정의한다.
  • 방향을 계산하는 기본 아이디어
    • 특정한 점을 중심으로 해당 주변 pixel들의 밝기( 강도, intensity ) 변화 방향을 분석하면, 해당되는 점의 주된 방향(orientation)을 찾을 수 있음. 이떄 이 방향을 ORB에서 특징점의 기분 방향( keypoint orientation )으로 설정하면, 이미지가 회전해도 해당 방향을 기준으로 descriptor를 정렬할수있다. ( 파란 색은 같은 값을 의미 )  
  • 계산 과정
    • 3-1. keypoint를 중심으로 patch를 선택. ( patch의 크기는 image pyramid의 scale에 따라서 달라진다. ) 
    • 3-2. 패치내에서의 x축과 y축의 gradient를 계산 ( 식 2 , 식 3 참고 )
    • 3-3. patch 내 모든 pixel의 Gradient를 한꺼번에 합산 ( 즉, x방향과 y방향의 총합을 구함. 식4참고  ) 
      • 이렇게 하면 patch 전체의 주된 강도 변화 방향을 알수있음
    • 3-4. orientation 계산
      • arctan함수를 사용하여 방향을 계산. ( 이로 인하여 기울기의 주된 방향을 구할수있음. 즉, 특징점이 어느 방향으로 가장 강하게 변화하는지 찾음. 식 5 참고 ) 
  • 이렇게 구한 theta가 ORB에서 특징점의 기분 방향이 된다. 그래서 이 방향을 기준으로 BRIEF discriptor를 회전시켜서 회전 불변성을 얻는다.
• 4. ORB의 BRIEF discriptor를 생성
  • 기존의 BRIEF는 회전 불변성이 부족하다. 그래서 ORB에서는 keypoint에서 계산된 방향 theta만큼 BRIEF 패턴을 회전시켜 적용한다. ( 식 6 참고 )
• 5. 스케일 불변성을 확보하기 위한 반복...
  • 원본 크기보다 작은 이미지들도 똑같이 fast와 harrison으로 특징점 검출하고, 방향을 계산해서 brief로 회전불변성을 가지게 하는 과정을 반복