ORB (FAST جهت‌دار و BRIEF چرخش‌یافته / Oriented FAST and Rotated BRIEF)

هدف#

در این فصل،

• مبانی ORB را خواهیم دید.

تئوری#

به عنوان یک علاقه‌مند به OpenCV، مهم‌ترین نکته درباره ORB این است که از «OpenCV Labs» بیرون آمده است. این الگوریتم توسط Ethan Rublee، Vincent Rabaud، Kurt Konolige و Gary R. Bradski در مقاله‌شان با عنوان ORB: An efficient alternative to SIFT or SURF در سال ۲۰۱۱ معرفی شد. همان‌طور که عنوان نشان می‌دهد، این الگوریتم از نظر هزینه محاسباتی، عملکرد تطبیق و به‌ویژه از نظر حق ثبت اختراع، جایگزین خوبی برای SIFT و SURF است. بله، SIFT و SURF دارای حق ثبت اختراع هستند و باید برای استفاده از آن‌ها هزینه پرداخت کنید. اما ORB اینطور نیست!!!

ORB اساساً ترکیبی از آشکارساز نقطه کلیدی FAST و توصیف‌گر BRIEF با تغییرات بسیار برای بهبود عملکرد است. ابتدا از FAST برای یافتن نقاط کلیدی استفاده می‌کند، سپس معیار گوشه هریس را برای یافتن N نقطه برتر در میان آن‌ها اعمال می‌کند. همچنین از هرم (pyramid) برای تولید ویژگی‌های چندمقیاسی استفاده می‌کند. اما یک مشکل این است که FAST جهت (orientation) را محاسبه نمی‌کند. پس چه می‌شود با پایداری در برابر چرخش (rotation invariance)؟ نویسندگان تغییر زیر را ارائه دادند.

الگوریتم مرکز ثقل وزن‌دار شدت (intensity weighted centroid) پچ را با قرار دادن گوشه شناسایی‌شده در مرکز محاسبه می‌کند. جهت بردار از این نقطه گوشه به مرکز ثقل، جهت‌گیری را می‌دهد. برای بهبود پایداری در برابر چرخش، گشتاورها (moments) با x و y محاسبه می‌شوند که باید در یک ناحیه دایره‌ای با شعاع $r$ باشند، جایی که $r$ اندازه پچ است.

اکنون برای توصیف‌گرها، ORB از توصیف‌گرهای BRIEF استفاده می‌کند. اما قبلاً دیدیم که BRIEF در برابر چرخش عملکرد ضعیفی دارد. پس ORB چه می‌کند؟ BRIEF را بر اساس جهت‌گیری نقاط کلیدی «هدایت» می‌کند (steer). برای هر مجموعه ویژگی از $n$ آزمون دودویی در مکان $(x_i,y_i)$، یک ماتریس $2\times n$ به نام $S$ تعریف می‌کند که مختصات این پیکسل‌ها را در بر دارد. سپس با استفاده از جهت‌گیری پچ $\theta$، ماتریس چرخش آن یافته می‌شود و $S$ را می‌چرخاند تا نسخه چرخش‌یافته (هدایت‌شده) $S_{\theta }$ به دست آید.

ORB زاویه را به افزایش‌های $2\pi /30$ (۱۲ درجه) گسسته می‌کند و یک جدول جستجو از الگوهای BRIEF از پیش محاسبه‌شده می‌سازد. تا زمانی که جهت‌گیری نقطه کلیدی $\theta$ در میان دیدها ثابت باشد، مجموعه درست نقاط $S_{\theta }$ برای محاسبه توصیف‌گر آن استفاده خواهد شد.

BRIEF یک ویژگی مهم دارد: هر ویژگی بیتی (bit feature) واریانس زیادی دارد و میانگینی نزدیک به ۰.۵ دارد. اما پس از اینکه در امتداد جهت نقطه کلیدی جهت‌گیری می‌یابد، این ویژگی را از دست می‌دهد و توزیع بیشتری پیدا می‌کند. واریانس بالا یک ویژگی را قابل تمایزتر می‌کند، زیرا به ورودی‌ها به طور متفاوت پاسخ می‌دهد. ویژگی مطلوب دیگر این است که آزمون‌ها ناهمبسته (uncorrelated) باشند، زیرا در این صورت هر آزمون به نتیجه کمک خواهد کرد. برای حل تمام این مشکلات، ORB یک جستجوی حریصانه در میان تمام آزمون‌های دودویی ممکن انجام می‌دهد تا آن‌هایی را که هم واریانس بالا دارند، هم میانگین نزدیک به ۰.۵ دارند و هم ناهمبسته هستند پیدا کند. نتیجه rBRIEF نامیده می‌شود.

برای تطبیق توصیف‌گر، از multi-probe LSH که نسبت به LSH سنتی بهبود یافته است استفاده می‌شود. مقاله می‌گوید ORB خیلی سریع‌تر از SURF و SIFT است و توصیف‌گر ORB بهتر از SURF عمل می‌کند. ORB انتخاب خوبی برای دستگاه‌های کم‌مصرف جهت دوخت پانوراما (panorama stitching) و غیره است.

ORB در OpenCV#

مثل همیشه، باید یک شیء ORB با تابع cv.ORB() یا با استفاده از رابط مشترک ویژگی‌ها ایجاد کنیم. تعدادی پارامتر اختیاری دارد. مفیدترین آن‌ها nFeatures است که حداکثر تعداد ویژگی‌های نگه‌داری‌شده را نشان می‌دهد (به طور پیش‌فرض ۵۰۰)، و scoreType که مشخص می‌کند آیا امتیاز هریس یا امتیاز FAST برای رتبه‌بندی ویژگی‌ها استفاده شود (به طور پیش‌فرض، امتیاز هریس) و غیره. پارامتر دیگری به نام WTA_K تعداد نقاطی را تعیین می‌کند که هر عنصر از توصیف‌گر BRIEF جهت‌دار را تولید می‌کنند. به طور پیش‌فرض عدد دو است، یعنی در هر بار دو نقطه انتخاب می‌شود. در این حالت، برای تطبیق، از فاصله NORM_HAMMING استفاده می‌شود. اگر WTA_K برابر ۳ یا ۴ باشد، که ۳ یا ۴ نقطه را برای تولید توصیف‌گر BRIEF می‌گیرد، آنگاه فاصله تطبیق توسط NORM_HAMMING2 تعریف می‌شود.

در زیر کدی ساده آمده است که نحوه استفاده از ORB را نشان می‌دهد.

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

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

# Initiate ORB detector
orb = cv.ORB_create()

# 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 را در فصل دیگری انجام خواهیم داد.

منابع اضافی#

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