تبدیل ویژگی مقیاس‌نابسته

تبدیل ویژگی مستقل از مقیاس (SIFT) یک الگوریتم در بینایی ماشین است که برای استخراج ویژگی‌های مشخص از تصاویر، برای استفاده در الگوریتم‌های کارهایی چون تطبیق نماهای مختلف یک جسم یا صحنه (برای نمونه در دید دوچشمی) و شناسایی اجسام به کار می‌رود. ویژگی‌های به‌دست آمده نسبت به مقیاس تصویر و چرخش ناوردا و نسبت به تغییر دیدگاه و تغییرات نورپردازی تا اندازه‌ای ناوردایند. نام تبدیل مقیاس‌نابسته ویژگی از آن سو که الگوریتم داده‌های تصویر را به مختصات مقیاس‌نابسته‌ای نسبت به ویژگی‌های محلی تبدیل می‌کند بر آن نهاده شد.

الگوریتم توسط دیوید لوو در دانشگاه بریتیش کلمبیا ساخته شد، که امتیاز ثبت اختراع آن در ایالات متحده را نیز دارد.

مراحل اصلی

به‌طور کلی تشخیص در الگوریتم sift از طریق دو بخش انجام می‌شود که عبارتند از:

• تشخیص نقاط کلیدی تصویر
• محاسبه اطلاعات توصیف کننده نقاط

تشخیص نقاط کلیدی تصویر بدین صورت انجام می‌شود که نقاط کلیدی به نقاطی از تصویر که در فضای مقیاس تصویر اکسترمم است اطلاق می‌شود و فضای مقیاس تصویر شامل مجموعه ای از تصاویر است. تصاویر این مجموعه با استفاده از کانولوشن تصویر اصلی با فیلترهای گوسی با مقیاس‌های مختلف تولید می‌شوند.

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

فضای مقیاس شامل چند تصویر است که با چند بار اعمال فیلتر گوسی به‌دست می‌آید.

در ساخت فضای مقیاس سپس عمل ریسمپلینگ انجام می‌شود و یک اکتاو جدید ساخته می‌شود. در هر اکتاو تفاضل گوسی‌ها (DoG)محاسبه می‌شود.

برای یافتن نقاط کلیدی اکسترمم‌های تابع d محاسبه می‌شود. هر نقطه با هشت همسایه و نقاط همسایه در صفحات مجاور در نظر گرفته می‌شود. سپس نقاط نامناسب حذف می‌شوند.

ا اینجا به ازای هر نقطه کلیدی، یک مختصات و یک مقیاس داریم یعنی: (x, y , δ)

بردار گرادیان در هر نقطه تصویر، جهت و اندازه بیشترین تغییرات را نشان می‌دهد و عمود بر لبه است.

برای ثابت بودن نسبت به دوران، یک دستگاه مختصات از روی گرادیان تعریف می‌شود.

در یک پنجره اطراف هر نقطه کلیدی، یک هیستوگرام از گرادیان‌ها ساخته می‌شود و جهتی که بیشترین فراوانی را دارد به عنوان جهت غالب انتخاب می‌شود.

به هر نقطه کلیدی یک بردار ویژگی شامل ۱۲۸ مولفه اختصاص داده می‌شود. پنجره اطراف نقطه کلیدی به ۴*۴ زیرپنجره تقسیم می‌شود و در هر زیرپنجره یک هیستوگرام از گرادیان‌ها رسم می‌شود (هر هیستوگرام شامل ۸ مقدار است)

تعداد ویژگی‌ها برابر خواهد بود: ۴*۴*۸ = ۱۲۸

نمایش نحوه نمایش ویژگی‌ها

گام‌های اصلی در محاسبه ویژگی‌های تصویر عبارت‌اند از:

1. آشکارسازی اکسترمم‌های فضای مقیاس - هر پیکسل در تصاویر با هشت همسایه‌اش و نه پیکسل (پیکسل متناظر و هشت همسایه‌اش) از هر یک از تصاویر دیگر سری مقایسه می‌شود.
2. محلی‌سازی کلیدنقطه‌ها - کلیدنقطه‌ها از اکسترمم‌های فضای مقیاس برگزیده می‌شوند.

   1. 

      تمامی کلیدنقطه‌های یافت شده در دو تصویر ورودی

3. گرایش گماری - برای هر کلیدنقطه در یک پنجره ۱۶x۱۶، نمودار فراوانی گرایش گرادیان‌ها به کمک درونیابی دوسویه محاسبه می‌شوند.
4. توصیفگر کلیدنقطه - نمایش در یک بردار ۱۲۸ عنصری.
5. تطبیق نقاط- برای به‌کارگیری کلیدنقطگان SIFT در تطبیق و بازشناسی جسم، لوو از یک الگوریتم نزدیک‌ترین همسایه، به همراه یک نگاشت هاف سود جست (آنگونه که در لوو، ۲۰۰۴ آمده است).

   1. 

      تمامی تطابق‌ها و تناظرهای یافت شده با استفاده از الگوریتم نزدیکترین همسایه‌ها

6. تشخیص خوشه با استفاده از روش رای‌گیری نگاشت هاف - در این روش، خوشه‌های مورد اطمینان که با فرضیه یک مدل هماهنگ است یافت می‌شود. در این الگوریتم هر ویژگی برای تمامی موقعیت اشیا رای می‌دهد و در نهایت احتمال برگزیده شدن تفسیری صحیح، از احتمال همه ویژگی‌ها به تنهایی بیشتر است.

   1. 

      خوشه منتخب انتخاب شده بین تمامی تناظرها که با رنگ قرمز نمایش داده شده است.

7. تأیید مدل با استفاده از روش کمترین مربعات - درجه آزادی مدلی که نگاشت چرخش، اندازه، کشیدگی و انتقال را انجام می‌دهد، ۶ است. همچنین به ازای هر تطبیق در فضای دوبعدی، دو معادله خواهیم داشت. از آنجا که تعداد تطبیق‌های ما بیشتر از ۳ می‌باشد، با استفاده از روش کمترین مربعات، میزان خطا را کمینه می‌کنیم. در این مرحله می‌توانیم داده‌های ناهنجار را نیز تشخیص دهیم.

   1. 

      نمایش نگاشت به دست آمده از تطبیق‌ها

مقایسه با دیگر الگوریتم‌های استخراج ویژگی

این روش یکی از روش‌های اصلی استخراج ویژگی در بینایی ماشین است. دلیل اصلی که این روش را از باقی روش‌ها جدا می‌سازد، مقاوم بودن این روش نسبت به اندازه، چرخش و تبدیلات افین است. آزمایش‌های زیادی در راستای عملکرد روش‌های گوناگون توصیفگرهای محلی انجام شده است. خلاصه‌ای از این مطالعات در زیر آمده است:

• در میان تمامی روش‌ها، الگوریتم‌های مانند تبدیل ویژگی مقیاس‌نابسته بیشترین دقت را در تطبیق ویژگی‌های تحت یک نگاشت افین با درجه ۵۰ دارد.
• این روش همچنین عملکرد کلی بهتری در سطح گسترده‌ای از تصاویر را دارا است.

پیشرفت‌های بعدی

این الگوریتم از نظر محاسباتی، الگوریتم زمان‌بری محسوب می‌شود و به همین خاطر در سال‌های بعد الگوریتم‌های دیگری برای کاهش این سربار معرفی شدند ولی معمولاً این کاهش سربار در ازای کاهش کیفیت نقاط تطبیق داده شده، ارائه می‌شود.

از جمله این الگوریتم‌ها می‌توان به SURF, ORB, PCA SIFT و KAZE اشاره کرد.

برای مثال الگوریتم SURF از همان منطق استفاده می‌کند اما سریعتر از روش تبدیل ویژگی مقیاس نابسته است. با این حال این سرعت در ازای دقت و مقاومت کمتر نسبت به تغییرات به دست می‌آید. همچنین الگوریتم ORB که در مواردی که با یک سیستم بی‌درنگ سر و کار داریم استفاده می‌شود؛ زیرا با تلفیق ویژگی‌های مثبت چند الگوریتم، روشی سریع با عملکرد قابل قبول ارائه کرده است. آما همچنان از نظر اعتمادپذیری، روش تبدیل ویژگی مقیاس نابسته در صدر قرار می‌گیرد.

پیاده‌سازی و استفاده

برای استفاده از این الگوریتم کافی است که از یکی ز کتابخانه‌های آماده‌ای که در پایتون یا باقی زبان‌ها پیاده‌سازی شده استفاده کنید و ویژگی‌های تصویر را به کمک این الگوریتم استخراج کنید. در زبان پایتون و سی‌پلاس‌پلاس می‌توانیم از کتابخانه openCV که با نام CV2 شناخته می‌شود استفاده کنیم و به کمک تابع cv2.drawKeypoints این نقاط را در تصویر نشان دهیم. تصاویری که در این صفحه نمایش داده شد نیز به کمک همین توابع اجرا شده بود.

کاربردها

این نوع الگوریتم بیشتر در کارهای شناسایی شی، شناسایی چهره، دنبال کردن شی و دنبال کردن حرکت فرد، مدل‌سازی سه بعدی صحنه، ساخت پانوراما، بخش‌بندی تصویر، شناسایی مکان، تعیین مکان ربات، نقشه ربات و … استفاده می‌شود. این روش احتیاجی به بخش‌بندی ندارد.

SIFT بخشی بنیادی از الگوریتم‌های ViPR و vSLAM ساخته شده توسط شرکت اوُلوشن رباتیکز است که یک الگوریتم هدفیابی/محلی‌سازی بر اساس SIFT نیز برای ایبوی سونی پیاده‌سازی کرده است که به کمک آن ایستگاه پر کردن باتری خود را پیدا می‌کند. همچنین از این روش برای ساخت تصاویر پانوراما و تلفیق چند تصویر استفاده می‌شود. از این الگوریتم در واقعیت مجازی نیز استفاده می‌شود و به کمک آن اشیا سه بعدی توسط تصاویر دو بعدی تشکیل می‌شود.

جستارهای درونی

• استخراج ویژگی
• دوخت تصاویر

پیوند به بیرون

• Object recognition from local scale-invariant features: مقاله کنفرانس که الگوریتم را تشریح می‌کند (۱۹۹۹)
• libsift: پیاده‌سازی SIFT با سی‌شارپ
• ابزاری به نام autopano-sift برای ایجاد خودکار سراسرنما از یک مجموعه تصاویر، برای تطبیق اجسام در تصاویر از SIFT استفاده می‌کند
• توصیف جزئی تر بخش‌های مختلف الگوریتم SIFT

منابع

• Lowe, D. G. , "distinctive image features from scale-invariant keypoints", International Journal of Computer Vision، ۲۰۰۴