بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه الگوریتم کارا برای تطبیق اهداف در دنباله تصاویر ویدئویی
چکیده
در این مقاله تطبیق هدف با استفاده از خصیصه مورد بررسی قرار گرفته است. در ابتدا الگوریتم های BRISK و SIFT را به عنوان دو الگوریتم مطرح مورد بررسی قرار میدهیم و با الهام از این دو الگوریتم، الگوریتم جدیدی را پیشنهاد میکنیم. این الگوریتم از الگوی جهتی برای توصیف خصیصه استفاده میکند. جهت این الگو در جهت عمود بر زاویه خصیصه قرار میگیرد که این امر باعث میشود که اطلاعات مفیدتری از روشناییهای اطراف خصیصه در ساخت بردار توصیفگر استفاده شود. همچنین در الگوریتم پیشنهادی همانند الگوریتم BRISK از مقادیر باینری در بردار خروجی استفاده شده است. نتایج این پژوهش نشان میدهد که قدرت تمایز و پایداری الگوریتمهای پیشنهادی نسبت به الگوریتم BRISK قوی تر شده است و از نظر کارآمدی الگوریتم تا حدود زیادی با الگوریتم BRISK برابر است.
واژه های کلیدی تطبیق تصویر، BRISK، .SIFT
-1 مقدمه
تطبیق تصویر1 عبارت است از روی هم قرار دادن دو تصـویری کـه در دو زمان متفاوت و یا از دو سنسور مختلف یا از دو نقطه نظر متفاوت بدست آمده است. به علت تنوع تصاویر و انـواع گونـاگون تخریـ ب هـای تصاویر، ما نمیتوانیم به صورت کلی یک روش کاربردی را برای همـهی روش های تطبیق طراحی کنیم. هر روش طراحی شده برای تطبیـق بـه نوع تبدیل هندسی بین تصاویر، مقدار خرابی نویز، میزان دقت و کاربرد آن روش وابسته است. با این حال الگوریتم های تطبیق را به سه مرحله تقسیم میکنیم:[1]
1. آشکارسازی خصیصه2
2. توصیف خصیصه
3. انطباق خصیصه3
مرحله اول آشکار سازی خصیصه میباشد. خصیصه در تصـویر بـه معنای، مکانی از تصویر است که به طور ادراکی جالب توجه یا به عبارت دیگر نقاط انتزاعی در تصویر گفته میشود .[1] سپس برای هر خصیصه آشکار شده یک بردار توصیف میسازیم. این بردار توصیف باید منحصـر به فرد و مقاوم نسبت به برخی تغییرات رایج تصاویر باشد. در مرحلـهی
سوم با استفاده از این توصیفها، خصیصه های متناظر را در دو تصویر بر هم انطباق میدهیم.
در ایــن پــژوهش الگــوریتم جدیــدی کــه آن را 4 DP-BRISK مینامیم برای تطبیق تصاویر ارائه شده است. این الگوریتم از دو قسمت آشکارســاز و توصـیفگر نقــاطکلیـدی تشــکیل شــده اســت. در قســمت آشکارساز نقاط کلیدی، ما از الگوریتم 5DOG استفاده میکنیم ولی به طور کلی از هر آشکارساز نقاط کلیدی که نسبت به تغییـر مقیـاس غیـر حساس باشد میتوان استفاده کرد.
توصیفگر الگوریتم DP-BRISK از الگـویی جهتـی بـرای سـاخت بردار خروجی استفاده میکند برای ایـن کـار جهـت گرادیـان نقطـه ی کلیدی را بدست میآوریم ایـن جهـت بیشـترین تغییـرات روشـنایی را نشان میدهد . الگوی جهتی را در راستای نقطهی کلیدی قرار میدهیم. این کار باعث میشود اطلاعات بیشتری در ساخت بردار باینری خروجی دخیل شود و الگوریتم قدرت تمایز بیشتری کسب کند.
این توصیفگر از برداری باینری استفاده میکند تا انطباق خصیصـه با سرعت بیشتری صورت بگیرد. همچنـین اسـتفاده از بـرداری بـاینری باعث میشود پیاده سازی سخت افزاری این الگوریتم راحتتر شود.
روند ارائه مطالب این مقاله به این صورت است کـه در بخـش دوم کارهای مرتبط را مرور میکنیم. در بخش سوم روش پیشنهادی تطبیق
را به تفصیل مورد بررسی قرار میدهیم و در بخش آخـر نتـایج را مـورد بررسی قرار میدهیم.
-2 کارهای مرتبط
یکی از بهترین الگوریتمهای تطبیق تصاویر الگوریتم 6SIFT میباشد که توسط دیوید لوو معرفی شده است.[2] در این الگوریتم خصیصهها از طریق تابع DOG که تقریب خوبی از تابع گرادیان است و هزینه محاسباتی کمی نسبت به آن دارد، بدست میآید.[3] روش توصیف در این الگوریتم بر اساس هیستوگرام گرادیان در پیکسلهای نواحی اطراف خصیصه میباشد. بای و همکارانش در [4] روش تطبیق 7SURF را معرفی کردند. در این الگوریتم از موجک هار8 برای توصیف نقاطکلیدی استفاده شده است.
یکی دیگر از الگوریتمهای مهم تطبیق تصاویر، BRISK میباشد که توسط استفان لوتنیگر و همکارانش معرفی شده است.[5] در این الگوریتم با استفاده از فضای مقیاس و آشکارساز گوشه AGAST [6]خصیصههای مقاوم به تغییر مقیاس آشکار میشود. آنها برای این کار هرمی از تصویر درست کرده و بر روی هر لایه هرم فضای مقیاس، آشکارساز گوشه AGAST را با آستانههای یکسان اعمال میکنند. سپس مقیاس هر یک از این خصیصهها با استفاده از درونیابی امتیازات بدست آمده از آشکارساز گوشه AGAST، به طور دقیق تخمین میزنند.
پس از آشکارسازی نقاط خصیصه، برای هر یک از خصیصهها یک توصیف به کار میبرند . این توصیف یک کد باینری 512 بیتی میباشد که بر اساس مقایسه شدت روشنایی اطراف خصیصه است. سپس در بخش آخر هر توصیف در تصویر مرجع را با تمام توصیفهای تصویر دریافتی را از طریق اپراتور منطقی یایانحصاری (XOR) مقایسه کرده و اگر میزان خطا از آستانه T کمتر بود آن دو توصیف را بر هم انطباق میدهند.
الکساندر آلاهی و همکارانش توصیفگرهای FREAK را معرفی کردند.[7] نحوهی ساخت این توصیفگر همانند توصیفگر BRISK ولی با الگوی نمونه برداری متفاوت میباشد. در این الگوریتم الگوی نمونه برداری از سیستم بینایی انسان یا به طور دقیقتر از شبکیه چشم انسان الهام گرفته شده است. در این الگو هر چه از مرکز ناحیه دور میشویم، انحراف معیار تابع گوسی بزرگتر میشود و تراکم نقاط مانند شبکیه
چشم انسان کمتر میشود. آلاهی ادعا کرده که توصیفگر FREAK نیاز به حافظه ی کمتری در زمان اجرا دارد و در نهایت سریعتر از الگوریتم BRISK عمل میکند.
-3 روش پیشنهادی
الگوریتم های تطبیـق BRISK و FREAK بـا اسـتفاده از الگـو و مقایسه روشناییهای نقاط الگـو، کـدی بـاینری را بـه عنـوان خروجـی میدهد. در این قسمت با الهام از این دو الگوریتم به سـاخت توصـیفگر DP-BRISK میپردازیم که از نظر قـدرت و پایـداری از توصـیفگرهای بالا بهتر عمل میکند.
در این الگوریتم نقاط کلیدی بدست آمده، نسبت به مقیاس تصویر و چرخش تغییر ناپذیرند و نسبت به تغییر دیدگاه و تغییرات نورپردازی تا حدودی بهتر از BRISK عمل میکند.
همچنین الگـوریتم DP-BRISK بـه صـورت مـاژول مـی باشـد و میتوان توصیفگر را با دیگر الگوریتمهای آشکارساز نقاط کلیدی به کـار برد. البته این الگوریتمها باید نسبت به تغییر مقیاس غیر حساس باشند و ضریب مقیاس نقاط کلیدی را تخمین بزنند.
1-3 آشکارسازی نقاط کلیدی
در این الگوریتم میتوان از هر آشکارساز نقاط کلیدی که مقدار ضریب مقیاس را برای نقاط کلیدی بدست میآورد میتوان استفاده کرد. در الگوریتم پیشنهادی در این پژوهش از آشکارساز نقاطکلیدی به کار رفته در الگوریتم SIFT استفاده شده است. این آشکارساز از تابع DOG برای بدست آوردن نقاط کلیدی استفاده میکند که تقریب خوبی از تابع لاپلاسین نرمالیزه شده میباشد. روش کار به این صورت است که ابتدا فضای مقیاسی از تصویر درست میکنیم و سپس لایه های این فضای مقیاس را با فیلتر گوسی مات میکنیم .[8] سپس تصاویر مات شده فضای مقیاس را از هم کم میکنیم تا توابع DOG تولید شود.
پس از ساخت فضای مقیاس DOG، نقاطی را که اکسترممهای سه بعدی هستند را به عنوان نقاط کلیدی تعریف میکنیم. منظور از اکسترممهای سه بعدی نقاطی از تصویر میباشند که این نقاط نسبت به همسایگی 8 در همان لایه و 9 همسایگی در لایه های بالا و پایین، اکسترمم هستند. سپس مختصات و ضریب مقیاس هر نقطهی کلیدی را در ماتریسی ذخیره میکنیم تا در ساخت توصیفگر استفاده شود.
2-3 توصیفگر خصیصه
توصیفگر DP-BRISK از یک رشتهی باینری برای بردار خروجی استفاده میکند، که از نتیجهی مقایسهی روشنایی پیکسلهای اطراف
نقاط کلیدی، بدست آمده است. در این توصیفگر یک جهت به هر نقاط کلیدی اختصاص داده میشود. این جهت برای نرمال کردن خصیصه استفاده میشود تا توصیفگر نسبت به چرخش غیر حساس شود.
الگوی نمونه برداری و تخمین جهت نقطهی کلیدی:
ایده اصلی این الگوریتم در این بخش همانند الگوریتم BRISK میباشد. برای بدست آوردن جهت نقاط کلیدی از الگوی نشان داده شده در شکل 1-3، استفاده میشود. مرکز الگو را بر روی نقاط کلیدی آشکار شده قرار میدهیم و برای جلوگیری از تداخل فرکانسی حاصل از نمونهکاهی و همچنین کاهش حساسیت به نویز هر نقطهی الگو را با فیلتر پایینگذر گوسی فیلتر میکنیم .[5]
شکل 1-3 الگو استفاده شده را نشان میدهد. نقاط آبی نقاط نمونه برداری الگو است و مختصات آن را با pi نمایش میدهیم و دایره های قرمز، اندازهی انحراف معیار فیلتر گوسی (σi) متناظر آن نقطه است. اندازه ی انحراف معیار را بزرگتر انتخاب میکنیم تا اندازه انحراف دو نقطهی مجاور الگو با هم همپوشانی داشته باشند. این کار سبب میشود تا همه پیکسلهای اطراف نقاط کلیدی، برای تخمین جهت مورد استفاده قرار بگیرند.
شکل (1-3 الگوی استفاده شده در الگوریتم جدید برای تخمین جهت نقاط کلیدی. نقاط آبی، نقاط الگو و دایرههای قرمز، اندازهی انحراف معیار فیلتر گوسی متناظر با نقاط نمونهبرداری شده میباشد.
سپس این الگو را با ضریب مقیاس بدست آمده از فضای مقیاس، بزرگ کرده و مرکز این الگو را به مکان نقطه کلیدی در تصویر اصلی انتقال میدهیم.
گرادیان محلی بین دو نقطه (pi,pj) با استفاده از رابطهی تقریبی زیر محاسبه میشود.
)1(
I(pj,σj) و I(pi,σi) میزان روشنایی فیلتر شده با فیلتر گوسی در نقاط pi و pj را نشان میدهد. گرادیان در تصویر میزان تغییرات روشنایی است. سپس مجموعه را به صورت زیر تعریف میکنیم.
این مجموعه، تمام زوج نقاط را بدون در نظر گرفتن ترتیب نقاط در خود جای میدهد. تعداد کل زوج نقاط برای الگو شکل 1-3 برابر است با
که در آن N برابر با تعداد نقاط الگو میباشد. حال زیر مجموعهای به نام "فاصله زیاد" را از مجموعه تعریف میکنیم و آنها را به صورت زیر نمایش میدهیم.
مجموعه زوج نقاطی از مجموعه است که فاصلهی زوج نقاط با یکدیگر از آستانهی بیشتر میباشد. t مقدار ضریب مقیاس نقطهکلیدی است. تعداد زوج نقاط این مجموعه برای آستانه برابر با 870 میباشد.
پس از ساخت مجموعهی به محاسبهی جهت نقطهکلیدی میپردازیم. برای این کار، با استفاده از فرمول (1) گرادیان محلی تمام زوج نقاط مجموعهی را بدست میآوریم. سپس با استفاده از فرمول (5) میانگین گرادیان محلی همه زوج نقاط را محاسبه میکنیم.
فرمول بالا میزان تغییرات روشنایی غالب در نواحی اطراف نقاط کلیدی را نشان میدهد. مقدار برابر با طول مجموعهی میباشد. تغییرات روشنایی غالب نقطهی کلیدی از میانگین گرادیان محلی زوج نقاط بدست میآید. پس از محاسبهی با استفاده از تانژانت معکوس، زاویهای را به نقاط کلیدی نسبت میدهیم. این زاویه جهت بیشترین تغییرات روشنایی در پیکسلهای اطراف نقطهی کلیدی را نشان میدهد.
