الگوریتم Sift – چگونگی تناظریابی تصاویر در نرم افزار های پردازش تصویر

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

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

1. مختصات سه بعدی نقاط گره ای را پیدا کند
2. بتواند پارامترهای توجیه نسبی را بدست بیاورد(یعنی هر عکس متوجه بشود که وضعیتش نسبت به دیگر عکسها به چه صورت است)

برای این مورد یک الگوریتمی وجود دارد که به نظر بنده انقلابی در فتوگرامتری نوین است. به اسم الگوریتم زیفت یا الگوریتم سیفت Sift Algorithm (Scale-invariant feature transform)

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

گریزی به فتوگرامتری کلاسیک

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

اما در فتوگرامتری نوین این کار امکان‌پذیر نیست. در نقشه برداری با پهپاد تعداد عکس ها بسیار زیاد است و نمی شود کسی پشت سیستم بنشیند و دونه دونه این عکس هارو با هم توجیه کند. پس باید یک روش جدیدی به وجود می آمد.

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

مراحل الگوریتم Sift

الگوریتم Sift دو مرحله اصلی دارد(در این مطلب قصد ندارم وارد مبانی تئوریک بشویم و به همین دو مرحله اصلی بسنده می کنیم)

1. Feature Matching
2. Feature Extraction

Feature Matching

ابتدا نرم افزار در تمام تصاویر می گردد و یک سری نقاط خاصی رو پیدا می کند(این که از کجا این نقاط را پیدا می کند در حوصله این مطلب نیست) به این نقاط Key Point گفته می شود.

اگر دقت کرده باشید در نرم افزار متاشیپ زمانی که میخواهید Align انجام بدهید در قسمت Advanced گزینه ای وجود دارد با عنوان Key Point Limit که میتوانیم نرم افزار تعداد این Key Pointها را محدود کنیم تا از یک حدی بیشتر نشود. البته شما میتوانید با صفر قرار دادن این گزینه در نرم افزار هر چقدر می توانید Key Point پبدا کند.

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

این مسئله در الگوریتم Sift حل شده است. یعنی اگر فاصله شما نسبت به سوژه کم یا زیاد بشود یا حتی وضعیت روشنایی تغییر کند یا حتی جهت تصاویر شما تغییر کند، الگوریتم سیفت میتواند به راحتی این نقاط مشترک را پیدا کند.

خوب گفتیم در مرحله اول Key Pointهارو پیدا می کند. فرض کنید در نرم افزار در عکس اول 50 هزار نقطه پیدا کرده در عکس دوم 60 هزار نقطه و در عکس سوم 40 هزار نقطه تصویری پیدا کرده.

هر نقطه تصویری دو مختصات x و y دارد و 128 ویژگی خاص به اون نقطه که توصیف‌گر نرم افزار یا الگوریتم سیفت می‌تواند برای ما مشخص کند. نکته بارز الگوریتم سیفت همین 128 ویژگی است که برای هر کدام از این نقاط در نظر می‌گیرد.

در مرحله دوم چه اتفاقی می افتد؟

Feature Extraction

مرحله دوم Feature Matching است. یعنی نرم افزار شروع می کند و از بین همه Key point که استخراج کرده می‌گردد تا ببیند برای نقطه اول در تصویر اول چه نقطه متناظری در تصویر دوم وجود دارد. نقطه متناظر نقطه ای است که در آن 128 ویژگی با نقطه اول برابر باشد. به نقاط گرهی Tie Point گفته می شود.

باز هم در نرم افزار متاشیپ می توانیم برای Tie Pointها در قسمت Advanced محدودیت تعیین کنیم. که بهتر است آن را هم صفر تعیین کنید.

الگوریتم این عمل را برای تمام نقاط تکرار می کند. فرض کنیم در مثال ما 20 هزار Tie Point بدست آورده است.

اگر نقاط متناظر را a’ و نقاط اولیه را a در نظر بگیریم مختصات تمام نقاط را بصورت زیر خواهیم داشت:

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

1. پارامترهای توجیه نسبی    dx, dy, dz, ω, φ, κ
2. مختصات سه بعدی نقاط گرهی در فضای مدرن   Sparce Cloud