در نوشته های تشخیص گوشه ها با الگوریتم Harris در OpenCV برخی از آشکارسازهای (Detector) گوشه مانند هریس را آموزش دادیم. الگوریتم هریس از نظر چرخش ثابت است، به این معنی که حتی اگر تصویر چرخانده شود، بازهم می توانیم گوشه های مشابه را پیدا کنیم. این بدیهی است، زیرا که گوشه ها در تصویر چرخانده شده باز هم نیز گوشه ها باقی می مانند. اما آیا زمانی که تصویری را تغییر مقیاس (تغییر اندازه) می دهیم، گوشه ها در تصویر تغییر مقیاس شده (حالا چه کاهش یا افزایش مقایس باشد)، بازهم همانند تصویر نخستین و پیش از تغییر مقیاس است. پاسخ خیر است، پس یک گوشه در تصویر تغییر مقیاس داده شده دیگر گوشه نخواهد بود.

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

به گفته دیگر، تشخیص دهنده هریس، نسبت به مقیاس تغییرپذیر است یعنی ممکن است یک پیکسل در یک مقیاس تصویر به عنوان گوشه در نظر گرفته شود، امّا همان پیکسل در مقیاس دیگر همان تصویر به عنوان گوشه در نظر گرفته نشود.

تطبیق دادن تصویر ها

تطبیق دادن ویژگی در میان تصویرها یا به زبان ساده تطبیق دادن دو تصویر، یکی از کاربردهای پایه ای و پر کاربرد در پردازش تصویر و بینایی ماشین است. زمانی که تصویر بسیار به یکدیگر نزدیک و همانند باشند، الگوریتم گوشه یابی هریس کاربرد دارد ولی همیشه اینگونه نیست و شما تصویرهایی با مقایس ها و جهت های گوناگون دارید و در اینجا است که شما می توانید از الگوریتم Scale Invariant Feature Transform کمک بگیرید.

توجه کنید گوشه ها (Corner) و لبه ها (Edge) ها دو ویژگی تصویرها هستند.

الگوریتم SIFT، تغییر مقیاس دو تصویر تاثیری بر روند پیدا کردن گوشه ها ندارد ولی شما می توانید برخی دیگر از ویژگی های تصویر مانند مقیاس (Scale)، چرخش (Rotation)، روشنایی (Illumination) و منظر یا نقطه دید (Perspective) را تغییر دهیم ولی بازهم نتیجه دلخوه که یافتن گوشه های تصویر است را بدست آوریم. در واقع چون الگوریتم نسبت به مقایس تغییر ناپذیر است، پس با Zoom-In یا Zoom-Out، نباید بر نتیجه تاثیری داشته باشد.

در شکل های زیر نخست سه تصویر کوچکتر (مقیاس کمتر) و با جهت (Oriention) متفاوت از دومین تصویر را نشان داده ایم، اکنون مسئله این است که بخواهیم اشیا درون تصویرهای کوچکتر را در تصویر بزرگتر (اولیه) پیدا کنیم. در اینجا چون تصویرهای با مقیاس متفاوت داریم، پس الگوریتم SIFT کاربردی است. در واپسین شکل می بینید که گوشه ها پیدا شده اند.

الگوریتم SIFT

در سال ۲۰۰۲ David Lowe الگوریتمی به نام SIFT (کوتاه شده Scale-Invariant Feature Transform) را ارائه داده که روشی است که نقطه های مورد علاقه رو مستقل از جهت و تغییر اندازه پیدا می کند. از یک دید این الگوریتم دو گام تشخیص (Detect) و محاسبه (Compute) را در بر می گیرد. در گام تشخیص، نقطه های مورد علاقه در تصویر شناسایی می شوند. در گام محاسبه، مقدارهای ویژگی های واقعی برای هر نقطه مورد علاقه محاسبه می شود.

چیزی که فراموش کردم آنکه در برخی از مستندات واژه نقطه کلیدی (Keypoint) به جای نقطه مورد علاقه به کار می رود.

همانند آنچه که در الگوریتم FAST گفته شده، در الگوریتم SIFT نیز متدی به نام ()detect برای تشخیص و شناسایی نقطه های مورد علاقه یا Keypoint ها به کار گرفته می شود. بر پایه مستدات OpenCV الگوریتم SIFT دربرگیرنده چندین گام است که در ادامه آنها آموزش داده شده اند. این گام ها عبارتند از:

  • Scale-space Extrema Detection یا استخراج یا تشخیص اکسترمم های فضای مقیاس
  • Keypoint Localization محلی سازی نقطه های کلیدی
  • Orientation Assignment
  • Keypoint Descriptor
  • Keypoint Matching

الگوریتم SIFT هم شناساگر (تشخیص دهنده یا Detector) و هم توصیفگر است که مرحله استخراج یا تشخیص ویژگی در آن، خود شامل سه مرحله است: استخراج اکسترمم های فضای مقیاس، بهبود دقّت موقعیت و حذف اکسترمم های ناپایدار و در آخر تخصیص جهت به هر ویژگی، که ایجاد شده است.

گام های به کارگیری الگوریتم SIFT به زبان ساده

۱ – پیدا کردن و ساختن فضایی (Space) برای اطمنیان از تغییر ناپذیری مقایس (Scale)

در این گام ما تصویر اولیه را در اختیار داریم و بر روی آن یک فیلتر گوسی (Gaussian Filter). بنابراین در این لحظه ما برخی از نقطه ها (Points) های غیر مهم را حذف کرده ایم و همچنین میزان نویزهای تصویر اولیه را نیز کاهش داده ایم. سپس تصویر را تغییر اندازه می دهیم و دوباره همین فرایند تکرار می شود.

۲ – پیدا کردن تفاوت میان گوس ها (Guassian)

در گام ۱ چندین تصویر فیلتر گوسی شده داریم و اکنون در دومین گام، تفاوت میان ارزش ها (مقدارهای) هر یک از این تصویرها را پیدا می کنیم. این گام باعث می شود تا تغییر ناپذیری مقیاس را بسازیم.

۳ – نقطه های کلیدی

در طی سومین گام، نقطه های مهم یا نقطه های کلیدی تشخیص داده می شوند. در واقع دراین گام به دنبال کمترین و بیشترین اکسترمم های محلی هستیم. هر پیکسل با پیکسل های همسایه خودش بررسی می شود و زمانی یک پیکسل، نقطه کلیدی است که اگر از همه پیکسل های همسایه اش کمتر (Minimum) یا بیشتر (Maximum) باشد.

سپس یک زیر مجموعه از پیکسل ها (Subpixels) های بیشترین یا کمترین پیدا می شود. برای این منظور، از مفهوم ریاضی به نام بسط تیلور (Taylor Expansion) کمک گرفته می شود. سپس دوباره باید بیشترین یا کمترین را پیدا کنیم. به هر حال در پایان الگوریتم SIFT، نقطه های کلیدی برابر با گوشه های تصویر هستند.

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

۴ – نقطه های کلیدی غیر ضروروی

در این گام و به کمک یک مقدار آستانه می خواهیم نقطه های کلیدی غیر ضروروی را حذف کنیم، بنابراین روشنایی (Intensity) هر پیکسل با مقدار آستانه سنجیده شده و سپس اگر از مقدار آستانه کمتر باشد، پس آن پیکسل دیگر نقطه کلیدی نخواهد بود.

۵ – جهت یابی نقطه های کلیدی  Orientation of Key Points

در این گام جهت شیب (Direction of Gradient) و بزرگی (Magnitude) را برای هر نقطه کلیدی و همسایگان آن می یابیم، سپس به شایع ترین جهت گیری در اطراف نقطه کلیدی نگاه می کنیم و همان را به آن اختصاص می دهیم. ما برای یافتن این جهت ها و رسیدن به هدف نهایی ، از هیستوگرام استفاده می کنیم

۶ – ویژگی های کلیدی

برای یکتا بودن نقطه های کلیدی ، ویژگی های کلیدی (Key Features) را از آنها استخراج می کنیم. همچنین، ما اطمینان می دهیم که در حالی که این نقطه های کلیدی را با تصویر دوم می سنجیم ، آنها نباید دقیقاً همانند یکدیکر باشند، بلکه تقریباً همانند یکدیگر هستند.