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

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

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

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

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

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

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

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

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

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

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

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

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

به هر نقطه کلیدی یک بردار ویژگی شامل 128 مولفه اختصاص داده می شود. پنجره اطراف نقطه کلیدی به 4*4 زیرپنجره تقسیم می شود و در هر زیرپنجره یک هیستوگرام از گرادیان ها رسم می شود( هر هیستوگرام شامل 8 مقدار است.)

تعداد ویژگی ها برابر خواهد بود : 4*4*8 = 128

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

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

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

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

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

 در میان تمامی روش‌ها، الگوریتم‌های مانند تبدیل ویژگی مقیاس‌نابسته بیشترین دقت را در تطبیق ویژگی‌های تحت یک نگاشت افین با درجه 50 دارد. 

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

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

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

از جمله این الگوریتم‌ها می‌توان به 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، ۲۰۰۴
 
الگوریتم‌ها
بینایی رایانه‌ای
تبدیل‌ها
یادگیری ماشینی
کشف ویژگی‌ها