ORB (Oriented FAST and Rotated BRIEF)

ORB (Oriented FAST and Rotated BRIEF)

Goal

• ORB의 기초에 대해서 알아보겠습니다

Theory

OpenCV 애호가로서 ORB에서 가장 중요한 점은 "OpenCV Labs"에서 나온 것입니다. 이 알고리즘은 Ethan Rublee, Vincent Rabaud, Kurt Konolige 및 Gary R. Bradski가 2011 년 그들의 논문 ORB: An efficient alternative to SIFT or SURF에서 제기했습니다. 제목에서 알 수 있듯이 SIFT 및 SURF 의 좋은 대안입니다. 계산비용, 매칭 성능 에서 대안으로써 좋으며 가장 중요한 것은 특허가 그렇습니다. SIFT와 SURF는 특허를 받아서 사용하기 위해 비용을 지불해야합니다. 하지만 ORB는 아닙니다!!!

ORB는 기본적으로 FAST keypoint detector와 성능 향상을 위한 여러 가지 수정 된 BRIEF descriptor를 융합 한 것입니다. 먼저 FAST를 사용하여 keypoints를 찾은 다음 해리스 코너 측정을 적용하여 그 중 상위 N 포인트를 찾습니다. 또한 피라미드를 사용하여 멀티 스케일 features을 생성합니다. 그러나 한 가지 문제는 FAST가 방향을 계산하지 않는다는 것입니다. 그럼, 회전 불변성은 어떨까요? 저자는 다음과 같은 수정 작업을했습니다.

중앙에 있는 코너에있는 intensity weighted centroid of the patch을 계산합니다. 이 corner point에서 centroid까지의 벡터 방향은 orientation을 나타냅니다. 회전 불변량을 개선하기 위해 모멘트는 $r$ 은 반경내의 원형 영역에 있어야하는 x와 y로 계산됩니다. $r$ 은 Patch 의 사이즈를 나타냅니다.

이제 descriptors 의 경우 ORB는 BRIEF descriptors를 사용합니다. 그러나 우리는 이미 BRIEF가 회전과 함께 제대로 작동하지 않는 것을 보았습니다. ORB가 하는 일은 keypoints의 방향에 따라 BRIEF를 "조종"하는 것입니다. 모든 $(x_i,y_i)$ 위치에서의 $n$ 이진 테스트 의 feature 집합에 대해 $2 n$ matrix 를 정의한다. $S$ 는 이 픽셀들의 좌표를 포함하고 있다. 따라서 patch 의 $\theta$ 방향 을 사용하는데, 이것의 rotation matrix 가 발견되고, $S$ 를 steered(rotated) version $S_{\theta}$ 을 얻기 위해 회전시킨다.

ORB가 각도를 discretize 하게 되는데, $2\pi/30$ 만큼씩의 increments 를 이용합니다. (12 degrees), 그리고 사전 계산 된 BRIEF 패턴의 lookup table을 구성 할 수있습니다. 키포인트 방향 $\theta$가 across views와 일치 하는 한, the correct set 의 점인 $S_\theta$가 이의 descriptor 로 사용되는데에 사용될 것이다.

BRIEF는 각 bit feature가 큰 분산을 가지며 평균이 0.5에 가깝다는 중요한 특성을 가지고 있습니다. 그러나 keypoint direction을 따라 지향되면 이 속성을 잃고 분산됩니다. 높은 분산은 입력에 differentially 하게 응답하게 하기 때문에 feature를 더욱 discriminative 하게 합니다. 또 하나의 바람직한 특성은 각 테스트가 그 결과에 기여할 것이기 때문에 테스트들이 상관 관계가없는 것입니다. 이 모든 문제를 해결하기 위해 ORB는 가능한 모든 binary tests 중에서 greedy search을 실행하여 분산이 크고 평균 0.5에 가까울뿐만 아니라 상관 관계가없는 것을 찾습니다. 그 결과를 rBRIEF라고합니다.

descriptor matching을 위해, 전통적인 LSH를 향상시키는 multi-probe LSH가 사용됩니다. 이 논문에 따르면 ORB는 SURF보다 훨씬 빠르며 SIFT와 ORB descriptor는 SURF보다 잘 작동한다고합니다. ORB는 파노라마 스티칭 (panorama stitching) 등을위한 저전력 디바이스에서 좋은 선택입니다.

ORB in OpenCV

통상, 우리는 cv2.ORB () 함수를 사용하거나 feature2d 공통 인터페이스를 사용하여 ORB 객체를 생성해야합니다. 여러 가지 선택적 매개 변수가 있습니다. 가장 유용한 것들은 보유 할 피쳐들의 최대 수 (디폴트는 500)를 나타내는 nFeatures, Harris score 또는 features의 순위를 매기기위한 FAST score (기본적으로 해리스 스코어) 등을 나타내는 scoreType이다. 또 다른 파라미터 인 WTA_K는, 방향성을 가지는 BRIEF descriptor의 각 요소를 생성하는 포인트 수를 결정한다. 기본적으로 두 개입니다. 즉 한 번에 두 개의 점을 선택합니다. 이 경우 matching하기 위해 NORM_HAMMING distance가 사용됩니다. WTA_K가 3 또는 4 인 경우 BRIEF descriptor를 생성하기 위해 3 또는 4 포인트가 소요되며 NORM_HAMMING2에 의해 matching distance가 정의됩니다.

다음은 ORB의 사용법을 보여주는 간단한 코드입니다.

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

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

# Initiate STAR detector
orb = cv2.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 = cv2.drawKeypoints(img,kp,color=(0,255,0), flags=0)
plt.imshow(img2),plt.show()

결과는 아래와 같았습니다.

ORB feature matching에 대해서는 다음 챕터에서 알아볼 것입니다.

Additional Resources

1. Ethan Rublee, Vincent Rabaud, Kurt Konolige, Gary R. Bradski: ORB: An efficient alternative to SIFT or SURF. ICCV 2011: 2564-2571.

https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_orb/py_orb.html