تشخیص و توصیف ویژگی

الگوریتم FAST برای تشخیص گوشه (FAST Algorithm for Corner Detection)

۵ دقیقه مطالعهOpenCV 5.xبه‌روزرسانی: ۹ آبان ۱۴۰۵

هدف#

در این فصل،

مبانی الگوریتم FAST را درک خواهیم کرد.
گوشه‌ها را با استفاده از قابلیت‌های OpenCV برای الگوریتم FAST پیدا خواهیم کرد.

تئوری#

ما آشکارسازهای ویژگی متعددی را دیدیم که بسیاری از آن‌ها واقعاً عملکرد خوبی دارند. اما از دیدگاه کاربردهای بلادرنگ (real-time)، آن‌ها به اندازه کافی سریع نیستند. یک مثال خوب، ربات موبایل SLAM (تعیین موقعیت و نقشه‌برداری همزمان / Simultaneous Localization and Mapping) است که منابع محاسباتی محدودی دارد.

به عنوان راه‌حلی برای این مشکل، الگوریتم FAST (ویژگی‌های حاصل از آزمون بخش شتاب‌یافته / Features from Accelerated Segment Test) توسط Edward Rosten و Tom Drummond در مقاله‌شان با عنوان «یادگیری ماشین برای تشخیص گوشه با سرعت بالا» در سال ۲۰۰۶ پیشنهاد شد (که بعداً در سال ۲۰۱۰ بازنگری شد). خلاصه‌ای از الگوریتم در زیر ارائه شده است. برای جزئیات بیشتر به مقاله اصلی مراجعه کنید (تمام تصاویر از مقاله اصلی گرفته شده‌اند).

تشخیص ویژگی با استفاده از FAST#

یک پیکسل $p$ در تصویر را انتخاب کنید که باید بررسی شود که آیا یک نقطه مورد علاقه (interest point) است یا خیر. شدت روشنایی آن را $I_{p}$ بنامید.
یک مقدار آستانه (threshold) مناسب $t$ انتخاب کنید.
یک دایره از ۱۶ پیکسل را اطراف پیکسل مورد آزمایش در نظر بگیرید. (تصویر زیر را ببینید)
اکنون پیکسل $p$ یک گوشه است اگر مجموعه‌ای از $n$ پیکسل پیوسته در این دایره (از ۱۶ پیکسل) وجود داشته باشد که همگی از $I_{p} + t$ روشن‌تر باشند، یا همگی از $I_{p} - t$ تاریک‌تر باشند. (خطوط چین‌دار سفید در تصویر بالا نشان داده شده‌اند.) $n$ برابر ۱۲ انتخاب شده است.
یک آزمون با سرعت بالا (high-speed test) پیشنهاد شده است تا تعداد زیادی از غیرگوشه‌ها را حذف کند. این آزمون فقط چهار پیکسل در موقعیت‌های ۱، ۹، ۵ و ۱۳ را بررسی می‌کند (ابتدا ۱ و ۹ آزمایش می‌شوند که آیا خیلی روشن‌تر یا تاریک‌تر هستند. اگر چنین باشد، ۵ و ۱۳ بررسی می‌شوند). اگر $p$ یک گوشه باشد، آنگاه حداقل سه تا از این چهار پیکسل باید همگی از $I_{p} + t$ روشن‌تر یا از $I_{p} - t$ تاریک‌تر باشند. اگر هیچ‌کدام از این موارد صدق نکند، آنگاه $p$ نمی‌تواند یک گوشه باشد. سپس معیار آزمون بخش کامل می‌تواند برای نامزدهای قبول‌شده با بررسی تمام پیکسل‌های دایره اعمال شود. این آشکارساز به خودی خود عملکرد بالایی دارد، اما چندین نقطه ضعف دارد:
- برای n < 12 نامزدهای کافی را رد نمی‌کند.
- انتخاب پیکسل‌ها بهینه نیست زیرا کارایی آن به ترتیب سؤالات و توزیع نمای گوشه‌ها بستگی دارد.
- نتایج آزمون‌های با سرعت بالا دور انداخته می‌شوند.
- چندین ویژگی مجاور یکدیگر تشخیص داده می‌شوند.

سه نکته اول با رویکرد یادگیری ماشین برطرف شده‌اند. نکته آخر با استفاده از سرکوب غیربیشینه (non-maximal suppression) حل می‌شود.

یادگیری ماشین برای آشکارساز گوشه#

مجموعه‌ای از تصاویر برای آموزش انتخاب کنید (ترجیحاً از حوزه کاربردی هدف)
الگوریتم FAST را روی هر یک از تصاویر اجرا کنید تا نقاط ویژگی پیدا شوند.
برای هر نقطه ویژگی، ۱۶ پیکسل اطراف آن را به عنوان یک بردار ذخیره کنید. این کار را برای تمام تصاویر انجام دهید تا بردار ویژگی $P$ به دست آید.
هر پیکسل (مثلاً $x$ ) در این ۱۶ پیکسل می‌تواند یکی از سه حالت زیر را داشته باشد:
بسته به این حالت‌ها، بردار ویژگی $P$ به ۳ زیرمجموعه $P_{d}$ ، $P_{s}$ ، $P_{b}$ تقسیم می‌شود.
یک متغیر بولی جدید $K_{p}$ تعریف کنید که اگر $p$ یک گوشه باشد درست (true) و در غیر این صورت نادرست (false) است.
از الگوریتم ID3 (طبقه‌بند درخت تصمیم / decision tree classifier) برای پرس‌وجو از هر زیرمجموعه با استفاده از متغیر $K_{p}$ برای دانش درباره کلاس واقعی استفاده کنید. این الگوریتم $x$ را که بیشترین اطلاعات را درباره اینکه آیا پیکسل نامزد یک گوشه است یا نه، ارائه می‌دهد (که با آنتروپی $K_{p}$ اندازه‌گیری می‌شود) انتخاب می‌کند.
این روش به صورت بازگشتی برای تمام زیرمجموعه‌ها اعمال می‌شود تا زمانی که آنتروپی آن‌ها صفر شود.
درخت تصمیم ساخته‌شده برای تشخیص سریع در تصاویر دیگر استفاده می‌شود.

سرکوب غیربیشینه (Non-maximal Suppression)#

تشخیص چندین نقطه مورد علاقه در مکان‌های مجاور مشکل دیگری است. این مشکل با استفاده از سرکوب غیربیشینه (Non-maximum Suppression) حل می‌شود.

یک تابع امتیاز $V$ برای تمام نقاط ویژگی تشخیص داده‌شده محاسبه کنید. $V$ مجموع قدرمطلق اختلاف بین $p$ و مقادیر ۱۶ پیکسل اطراف آن است.
دو نقطه کلیدی (keypoint) مجاور را در نظر بگیرید و مقادیر $V$ آن‌ها را محاسبه کنید.
آنکه مقدار $V$ کمتری دارد را حذف کنید.

خلاصه#

این الگوریتم چندین برابر سریع‌تر از سایر آشکارسازهای گوشه موجود است.

اما در برابر سطوح بالای نویز مقاوم نیست و به یک آستانه وابسته است.

آشکارساز ویژگی FAST در OpenCV#

این آشکارساز مانند هر آشکارساز ویژگی دیگری در OpenCV فراخوانی می‌شود. در صورت تمایل می‌توانید آستانه، اینکه آیا سرکوب غیربیشینه اعمال شود یا نه، همسایگی مورد استفاده و غیره را مشخص کنید.

برای همسایگی، سه پرچم (flag) تعریف شده‌اند: cv.FAST_FEATURE_DETECTOR_TYPE_5_8، cv.FAST_FEATURE_DETECTOR_TYPE_7_12 و cv.FAST_FEATURE_DETECTOR_TYPE_9_16. در زیر کدی ساده برای تشخیص و رسم نقاط ویژگی FAST آمده است.

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

img = cv.imread('blox.jpg', cv.IMREAD_GRAYSCALE) # `<opencv_root>/samples/data/blox.jpg`

# Initiate FAST object with default values
fast = cv.FastFeatureDetector_create()

# find and draw the keypoints
kp = fast.detect(img,None)
img2 = cv.drawKeypoints(img, kp, None, color=(255,0,0))

# Print all default params
print( "Threshold: {}".format(fast.getThreshold()) )
print( "nonmaxSuppression:{}".format(fast.getNonmaxSuppression()) )
print( "neighborhood: {}".format(fast.getType()) )
print( "Total Keypoints with nonmaxSuppression: {}".format(len(kp)) )

cv.imwrite('fast_true.png', img2)

# Disable nonmaxSuppression
fast.setNonmaxSuppression(0)
kp = fast.detect(img, None)

print( "Total Keypoints without nonmaxSuppression: {}".format(len(kp)) )

img3 = cv.drawKeypoints(img, kp, None, color=(255,0,0))

cv.imwrite('fast_false.png', img3)

نتایج را ببینید. تصویر اول FAST با سرکوب غیربیشینه و تصویر دوم بدون سرکوب غیربیشینه را نشان می‌دهد:

الگوریتم FAST برای تشخیص گوشه (FAST Algorithm for Corner Detection) — تصویر ۳

منابع اضافی#

Edward Rosten and Tom Drummond, "Machine learning for high speed corner detection" in 9th European Conference on Computer Vision, vol. 1, 2006, pp. 430–443.
Edward Rosten, Reid Porter, and Tom Drummond, "Faster and better: a machine learning approach to corner detection" in IEEE Trans. Pattern Analysis and Machine Intelligence, 2010, vol 32, pp. 105-119.