ORB (Oriented FAST and Rotated BRIEF)

출처: https://docs.opencv.org/3.4/d1/d89/tutorial_py_orb.html

OpenCV: ORB (Oriented FAST and Rotated BRIEF)

※ 본 포스팅의 위의 ORB 설명 문서를 번역 및 보충 설명한 것입니다. 번역이 매끄럽지 못한 부분이 있어도 양해 부탁드립니다.

---

ORB: An efficient alternative to SIFT or SURF 

- Developed at OpenCV labs by Ethan Rublee, Vincent Rabaud, Kurt Konolige, and Gary R. Bradski in 2011

 

특징)

- 상업적 용도로 사용이 가능하다(반면, SIFT와 SURF는 특허가 걸려있다)

- FAST 특징점 추출방법과 BRIEF 묘사자의 Fusion이다(각각의 장점을 살리고, 부족한 부분은 개선하였다)

- SURF 보다 몇배수 빠르며, SIFT 보다 더 잘 작동한다고 저자는 주장한다.

    - FAST 특징 추출 알고리즘에서 방향 불변성 + 스케일 불변성 특성 추가

    - BRIEF 묘사자에서 상관성과 분산을 고려한 벡터 샘플링

 

 

상세 1) - Keypoint 추출

- 먼저, FAST로 Keypoint를 추출한다.

- Harris Corner 측정을 적용하여 Top N 개 점을 찾는다.

- 피라미드를 사용하여 Multi-Scale 특징점을 계산한다. 

- (FAST 알고리즘 개선) FAST 알고리즘은 방향(Orientation)을 계산하지 못하므로 이부분을 개선하였다.

    - 패치 중앙에 모서리가 있을 경우, 강도를 가중치로 하는 패치의 중앙점를 계산한다.

      (Compute Intensity weighted centroid of patch)

    - 코너 중심점(O)으로 부터 패치 중앙점(C)으로 방향이 Orientation($\theta$)을 나타낸다.   $ \theta = atan2(m_{01}, m_{10}) $

패치 방향을 Theta로 나타낼 수 있다. 그리고 Theta 만큼 패치를 회전 시킨다

- Rotation Invariance(회전 불변성 즉, 회전이 있어도 특징점 추출이 영향을 받지 않음)을 개선하기 위해 반경 r의 원형 영역에 있어야 하는 x, y로 모멘트가 계산된다. r은 패치의 크기이다.

 

 

상세 2) - Descriptor 계산

- ORB는 BRIEF 묘사자를 사용한다.

- BRIEF 알고리즘은 FAST 알고리즘으로 추출한 키 포인트를 이진 특징 벡터로 변환한다.

- BRIEF는 키 포인트 주변의 랜덤 픽셀 쌍을 선택한다.

    - 첫번째 픽셀은 키 포인트를 중심으로 하는 가우시한 분포에서 선택한다.

    - 두번째 픽셀은 첫번째 픽셀을 중심으로하는 2배 큰 분산을 가지는 분포(혹은 시그마)에서 선택한다. 

    - 첫번째 픽셀이, 두번째 픽셀보다 밝다면 '1'을 부여한다. 반대라면 '0'.

    - BRIEF는 128번 반복하여 키 포인트 마다 128bit 벡터를 생성한다.  

 

임의의 두 랜덤 픽셀 쌍 선택

- n 이진 테스트의 벡터는 아래와 같이 정의한다.

$$ f(n) = \sum_{1<i<n}2^{i-1}\tau(p;x_i;y_i) $$

 

- (BRIEF 알고리즘 개선) 하지만, BRIEF 알고리즘은 방향이 변함에 따라 성능이 떨어진다. 이부분을 개선하였다.

    - ORB는 BRIEF를 키 포인트 방향에 따라 방향 조종하였다

    - 위치 $(x_i, y_i)$에서 n개의 이진 테스트의 기능 집합에 대해 2xN 행렬(S)을 정의한다.

\begin{pmatrix} x_1, ... x_n \\ y_1, ... y_n \end{pmatrix}

 

    - 행렬 S 는 해당 픽셀 좌표를 포함하게 된다.

    - 패치 방향 $\theta$를 이용해서 방향 행렬을 구하게 되고, S를 $\theta$ 만큼 회전시켜 $S_\theta$로 만든다. 

$$ S_{\theta} = R_{\theta}S $$

 

    - ORB는 2$\pi$ / 30 즉, 12º 간격으로 이산화하고, 미리 계산된 BRIEF 패턴의 LookUp 테이블을 구성한다. 

    - 키포인트 방향 $\theta$가 뷰 전체에서 유지되는 한(?), 정확한 점 집합 $S_\theta$ 가 묘사자를 계산하는 데 사용된다.

 

- BRIEF는 각 비트 특징이 큰 분산을 가지고, 평균이 0.5에 가까운 중요한 특성을 지닌다. 하지만, 위에 나열된 방법에 따라 키포인트 방향에 따라 방향을 바꾸면, 분산은 더욱 커지게 된다. 큰 분산은 특징을 더욱 분별력있게 만들어준다. 

- 또 다른 개선점은 테스트의 상관성을 없엔것이다. ORB는 가능한 모든 이진 테스트 준에서 Greedy Search를 수행하여 분산이 크고, 평균이 0.5에 가깝고 상관관계가 없는 테스트를 선별한다. 이에 따른 결과는 rBRIEF로 불린다.

- 묘사자 매칭을 위해, 기존의 LSH를 개선한 다중 프로브 LSH가 사용된다. 

글로는 잘 이해가 되지 않아, 상세한 단계는 논문을 참고해봐야 할 듯 싶다.

 

(보충) ORB's Orientation Compensation (자료)

KeyPoint 추출 보충 설명

- ORB는 코너 방향 측정치를 이용한다 (코너 방향은 Intensity weighted centroid로 대신한다)

- 패치의 모멘트는 아래와 같이 정의된다.

$$ m_{pq} = \Sigma_{x, y}x^py^qI(x, y) $$

- 위의 모멘트를 이용하여 Centroid는 아래와 같이 구할 수 있다 (Center of Mass)

$$ C = ( \frac{m_{10}}{m_{00}}, \frac{m_{01}}{m_{00}} ) $$

- 따라서, 코너 중심점 (O)로 부터 Centroid 의 벡터 즉, 패치의 방향은 다음과 같이 정의할 수 있다

$$ \theta = atan2(m_{01}, m_{10}) $$

- 방향을 구했다면, 패치를 회전시켜 묘사자를 계산한다. 

 

 

Descriptor 계산 보충 설명

- (Sampling Pairs의 학습) Sampling Pair는 상관도가 낮기를 원하여 새로운 Pair가 묘사자에게 새로운 정보를 매번 제공해 줄 수 있기를 원한다.

- Pair가 높은 분산을 갖기를 원한다. 높은 분산은 피처 분별이 뚜렸하게 한다.

- 저자는 Sampling 쌍을 학습하여, 이러한 두가지 속성을 갖게 하였다(낮은 상관도와 높은 분산)

   205,000 개의 가능한 데스트가 있었으며, 이중 256개의 테스트만 선택되었다.

- (학습 방식) PASCAL VOC 2006 데이터셋으로 부터 얻은 300,000개의 키 포인트를 학습 시켰다.

    1. 모든 학습 패치에 대해 테스트를 수행한다. 

    2. 평균이 0.5에 가까운 것을 기준으로 테스트를 정렬한다. 벡터 T를 구성한다. 

    3. Greed Search

        3-1. 첫번째 테스트를 벡터 R로 둔다. 벡터 T로 부터 제거한다.

        3-2. 다음 테스트 벡터 T를 정해, R과 비교한다. 만약 상관도가 Threshold 보다 높다면 버리고, 낮다면 R에 추가한다. 

        3-3. 256개의 R 벡터가 모일 때 까지 반복한다. 만약 Threshold가 높아서 256개가 모이지 않았다면, Threshold를 조정해서 256개를 다시 수집한다.

    4. 테스트가 완료되면, 상관도가 각각 낮고 높은 분산을 가지는 256개의 벡터 R을 얻을 수 있다.

 

 

결론

- ORB는 이진 묘사자이며 BRIEF 와 유사하지만, 회전 불변성을 개선하였고, Sampling Pairs를 학습하였다.

- 비 기하학적 변환(Blur, JPEG 압축, Exposure, Illumination)에서는 BRIEF가 ORB 보다 성능이 뛰어나다

- 하지만, 회전 혹은 스케일 변화 등 기하학적인 변환(Affine Transformation)이 있으면 BRIEF가 성능이 떨어지기 때문에 ORB가 이를 개선하여 더 성능이 좋다.

- 시점의 변환(Perspective Transformation)에서는 BRIEF가 ORB 보다 조금 더 성능이 좋다고 한다.

 

 

ORB In OpenCV

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

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

# Initiate ORB detector
orb = cv.ORB_create() # orb 객체 생성

# find the keypoints with ORB
kp = orb.detect(img,None) # 키 포인트 추출

# compute the descriptors with ORB
kp, des = orb.compute(img, kp) # 묘사자 계산

# draw only keypoints location,not size and orientation
img2 = cv.drawKeypoints(img, kp, None, color=(0,255,0), flags=0)
plt.imshow(img2), plt.show()

ORB Kepoint &amp;amp;amp;amp;amp; descriptor

 

 

추가 참고 사이트)

https://gilscvblog.com/2013/10/04/a-tutorial-on-binary-descriptors-part-3-the-orb-descriptor/

A tutorial on binary descriptors – part 3 – The ORB descriptor

https://medium.com/data-breach/introduction-to-orb-oriented-fast-and-rotated-brief-4220e8ec40cf

Introduction to ORB (Oriented FAST and Rotated BRIEF)