الگوریتم SIFT یک الگوریتم برای استخر اج ویژگی ها از تصویر است. از ویژگی های استخر اجی توسط این الگوریتم بر ای جستجو تطابق محتوایی تصاویر استفاده می شود. این الگیوریتم قابليت های بالایی در بازیابی محتوایی اطلاعات از تصاویر ویدئو را دارد.این الگوریتم نسبت به تبدیلات affine ، تغييرات نورپردازی، نویز تغيير زاویه دید و انسداد تا حدی چایدار است. می توان از این الگوریتم در کارهای همچون registration ، شناسایی شی، شناسایی چهره، دنبال کردن شی … استفاده نمود .الگوریتم SIFT شامل سه فاز استخر اج ویژگی ها، توصيف ویژگی ها تطبيق ویژگی ها می باشد در ادامه به تشریح هر یک از این مر احل می پردازیم

استخراج ویژگی ها

اصولا استخراج ویژگی یک مرحله کلیدی درهر سيستم بازشناسی الگو محسوب می شود . برای دست یابی به بيشترین کارایی در سيستم نياز است ویژگی های مقاوم تری از تصاویر استخراج شوند. در الگوریتم SIFT در ابتدا نقاط کليدی تصاویر تشخيص داده می شوند. نقاط کليدی به نقاطی از تصویر گفته می شود که در فضای مقياس تصویر اکسترمم باشند. در کل برای استخراج ویژگی ها دراین الگوریتم از سه مرحله: استخر اج اکسترمم های مستقل از مقياس ، بهبود دقت مكان اکسترمم ها, حذف اکسترمم های ناپایدار تخصیص جهت به اکسترمم ها استفاده می شود.

استخراج اکسترمم های مستقل از مقیاس

برای استخر اج اکسترمم های مستقل از مقياس باید مجموعه ای از تصاویر گوسی تصاویر DOG از تصویر اصلی ایجاد کرد. سپس آن ها را در لایه های منظمی قر ار داد. این فرآیند در شكل زیر نشان داده شده است. به هر دسته از این لایه ها یک اکتاو گفته می شود. علت استفاده از این اکتاو ها استخراج ویژگی های تغيير ناپذیر نسبت به مقياس می باشد.

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

خروجی این عمليات یک نمونه نرم می باشد که با تغییر مقدار k می توان میزان نرمی تصویر را تغییر داد .

بدین ترتيب اکتاو اول تشكيل می شود . برای ایجاد اکتاوهای بعدی با استفاده از روش های Down sampling مقياس کاهش داده می شود. این کار با در نظر گرفتن رزولوشن تصویر اصلی ادامه می یابد. معمولا ایجاد 3 تا 4 اکتاو برای تصاویر معمولی کافی می باشد. همانطور که در بالا اشاره شد برای ایجاد اکتاو از مقياس دو برابر مقياس تصاویر اصلی استفاده می شود. این بدین علت است که با این کار می توانيم یژگی های بيشتری از تصویر استخراج کرد . حال اگر تصویر اصلی دارای رزولوشن بالایی باشد می توان برای ایجاد اکتاو اول از همان تصویر اصلی استفاده کرد. لازم به ذکر است که اکسترمم های تابع لاپلاسین که تقریبی از تابع DoG است برای تعيين ویژگی های مستقل از مقياس مناسب می باشد همانطور که در شکل زیر نشان داده شده است به سه لایه وسط هر اکتاو تصویرDOG لایه مکانی گفته می شود که در ادامه نشان خواهيم داد که چگونه از این فضای لایه ها نقاط اکسترمم استخراج می شود تصاویر اختلاف گوسی طبق رابطه زیر از تصاویر گوسی ساخته می شود .

حالا برای استخر اج ویژگی ها هر پيكسل در سطوح ميانی تصاویر یا همان لایه های مکانی با 8 پیکسل همسایه خود 9 پیکسل همسایه DOG پایین و 9 پيكسل همسایگی تصویر DOG بالا و در مجموع 26 پيكسل می شود مقایسه می گر دد در صورتی که پيكسل مورد نظر اکسترمم (ماکزیمم یا مینیمم ) باشد ذخیره خواهد شد .

بهبود دقت مكان اکسترمم ها و حذف اکسترمم های ناپایدار

برای بهبود دقت مکانی اکسترمم ها در ابتدا برازش یک تابع quadratic 3D در همسایگی 26 تایی هر نقطه که به شکل است با سری تیلور تابع بسط داده می شود

در 26 نقطه همسایه ،برای مشتق گرفتن در جهت X ستون های چپ و راست از هم کم می شوند برای مشتق در جهت Y سطرهای بالا و پایین باید از هم کم شوند و برای مشتق گرفتن در جهت سیگما مشتق بر روی صفحه بالا و پایین حساب می شود برای اکسترمم, مشتق تابع فوق برابر صفر قرار داده می شود .

بنابراین مقدار تابع در مكان جدید طبق رابطه زیر می بباشد و با استفاده از قدرمطلق این مقدار می توان نقاط ناپایدار و یا نقاطی که روی لبه قرار گرفته اند را حذف می کند

برای حذف نقاط ناپدار و نقاط با کنتراست پایین یک مقدار آستانه به شکل زیر در نظر گرفته می شود در صورتی که این رابطه برای هر نقطه ای برقرار باشد این نقطه ناپایدار است و باید حذف گردد

تخصیص جهت به اکسترمم ها

تخصیص جهت به نقاط اکسترمم باعث می شود که در الگوریتم SIFT علاوه بر استخراج نقاط تغییر ناپذیر نسبت به مقیاس ,نقاط نسبت به جهت نيز تغيير ناپذیر باشند. به منظور تخصیص جهت به نقاط اکسترمم همانطور که در شکل زیر پیداست در ابتدا پنجره ای دایره ای شکلی در اطراف هر نقطه اکسترمم در تصویر گوسی که نقطه در آن مقیاس استخراج شده است در نظر گرفته شده است

بعد از در نظر گرفتن پنجره دایره ای شكل دامنه و جهت گرادیان برای پيكسل های آن دایره محاسبه می گردد. این فرایند در شکل زیر نمایش داده شده است .

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

در پایان این مرحله بردار ویژگی استخراج شده و هر ویژگی دارای 4 بعد شامل مختصات مقیاس و زوایه مورد نظر می باشد.

توصیف ویژگی ها

یک روش ساده توصیف ویژگی ها همانطور که در شکل زیر نشان داده شده است قرار دادن پنجره ای در اطراف ویژگی ها و محاسبه هیستوگرام این پچ ها می باشد برای تطبیق این پچ ها هیستوگرام دو تکه باید مشابه باشد .

اصولا توصيفگر ها باید دارای دو مشخصه مهم باشند: اول آنكه نسبت به چرخش و مقياس مستقل باشند و دوم باید نسبت به تغييرات روشنایی پایدار باشند. برای ایجاد این دو مشخصه در توصيفگرها باید مر احل زیر را برای هر توصيفگر انجام شود:

• ایجاد یک مربع 4*4 در اطراف هر نقطه در تصویر گوسی
• چرخاندن مربع نسبت به جهت اصلی
• محاسبه مقادیر و جهت گرادیان برای پیکسل ها و وزن دهی مربع
• محاسبه هیستوگرام جهت در هر سلول مربع و بهبود آن

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

تطبیق ویژگی ها

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