بخشی از مقاله
چکیده
یک گام اساسی در تجزیه و تحلیل ویدئو کشف و ردیابی اشیاء متحرک میباشد. در این مقاله به بررسی و مقایسه سه الگوریتم ردیابی مبتنی بر تطبیق مشخصه که به صورت بلادرنگ هدف را دنبال می کنند پرداخته می شود. یکی از چالشهای موجود انتخاب ویژگیهایی است که در مقابل تغییر شدت روشنایی، انسداد، تغییر مقیاس و دوران مقاوم باشند. ابتدا نقاط ویژگی توسط یکی از آشکارسازهای های KLT، SIFT و BRISK برای ناحیهی هدف که در فریم اول مشخص شده، استخراج میشود.
سپس در فریمهای بعدی نقاط ویژگی در یک پنجرهی بزرگتر پیرامون موقعیت هدف در فریم قبلی جستجو میشود. در گام تطبیق ویژگیها بهترین تطبیق برای نقاط کلیدی استخراج شده در فریم های متوالی توسط بخش تطبیقی الگوریتم KLT به دست می آید. روش پیشنهادی بر روی 14 مجموعه دنبالهی ویدئویی اعمال گردید و دو معیار ارزیابی کیفیت برای سنجش کارایی، استفاده شد. در ارزیابی ها میانگین خطای پیکسل مرکزی 11/65 و سرعت اجرا به طور متوسط 35/97 برای الگوریتم استخراج نقاط کلیدی BRISK حاصل شد که حاکی از برتری این الگوریتم در استخراج نقاط کلیدی و ردیابی اشیاء صلب در فریم های متوالی نسبت به الگوریتم KLT و SIRF می باشد.
مقدمه
ردیابی هدف متحرک به مفهوم تعقیب هدف متحرک در یک سری تصاویر متوالی است. ردیابی هدف یکی از مسائل دشوار در بینایی ماشین میباشد. کشف و ردیابی اشیاء متحرک یک گام اساسی در تجزیه و تحلیل ویدئو میباشد و به همین خاطر بطور گستردهای در سیستمهای بینایی ماشین مانند سیستمهای نظارتی، کنترل ترافیک، ناوبری خودکار، تعامل انسان با کامپیوتر و رباتیک استفاده میشود، زیرا سیستمهای مذکور نیازمند دریافت و پردازش ویدئوهای دریافتی از محیط اطراف خود و در نهایت تجزیه و تحلیل رفتار و رخدادهای موجود در این ویدئوها میباشند.
از آنجایی که دقت و سرعت از عوامل مهم در عملکرد مطلوب سیستمهای مذکور می-باشند، در نتیجه ارائه روشهای ردیابی اشیاء متحرک که دارای زمان مصرفی کم و دقت بالا باشند منجر به افزایش سطح کیفیت عملکرد این سیستمها خواهد شد. اشیاء متحرک مورد ردیابی میتواند هر شی متحرکی مانند ماهی درون آب، قایق درون دریا، عابر پیاده در پیادهرو، اتومبیل در بزارگراهها و غیره باشد. به عنوان مثال در یک سیستم ناوبری خودکار - اتومبیل بدون راننده - باید بتوان اشیاء متحرک موجود در اطراف سیستم را تشخیص داده و در هر زمان موقیت این اشیاء را برای اجتناب از برخورد با دیگر اشیاء تعیین کرد.
الگوریتمهای ردیابی باید بتوانند در مقابل چالشهای زیادی مانند تغییرات شدت روشنایی محیط، تغییر جهت ناگهانی اشیاء، وجود انواع مختلف اشیاء، همپوشانی و غیره از خود انعطاف نشان دهند. تاکنون روشهای مختلفی برای ردیابی هدف متحرک در تصاویر متوالی پیشنهاد شده است که از جمله میتوان به روشهای شار نوری، روشهای تطبیق مشخصه و روشهای پیرامون فعال اشاره کرد.
در روشهای تطبیق مشخصه ابتدا یک مجموعه ویژگی از جمله لبهها، گوشهها از تصویر استخراج میشود و سپس تناظری بین نقاط ویژگی در تصویرهای متوالی برقرار میگردد. سرعت اجرای روشهای تطبیق مشخصه نسبت به سایر روشهای ردیابی بسیار بیشتر می-باشد . [1] این مقاله به صورت زیر سازماندهی شده است: در بخش بعدی کارهای انجام شده در زمینه ردیابی و استخراج نقاط کلیدی آورده می شود. سپس روش های استخراج نقاط کلیدی مورد بررسی قرار می گیرد و در بخش اخر آزمایشات و نیتجه گیری بحث می شود.
کارهای انجام شده
در الگوریتمهای ارائه شده برای ردیابی از ویژگیهای زیادی مانند ویژگیهای لبه [3 , 2]، نقاط گوشه [7-4]، بافت [9 , 8] و رنگ ,10] [11 و غیره استفاده میشود. انتخاب مناسب ویژگیها در ردیابی نقش کلیدی را بازی میکند. از میان ویژگیهای نامبرده ویژگیهای گوشه بطور گستردهای در ردیابی استفاده شدهاند. زیرا نقاط گوشه نسبت به تغییرات شدت روشنایی محیط، تغییر جهت اشیاء متحرک و تغییر زاویه شی انعطاف پذیرترند.
یکی از آشکارسازهای نقاط ویژگی هریس میباشد که نسبت به دوران مقاوم است .[4] آشکارساز نقاط کلیدی Harris-Laplace و Hessian-Laplace و[13 ,12 ,5] DoG1 نسبت به دوران و تغییر مقیاس مقاوم هستند. Lowe در مقاله خود الگوریتم SIFT را که نسبت به تغییر مقیاس و دوران تصویر و تا حدودی نسبت به تغییر روشنایی و تغییر زاویه دید مقاوم است، پیشنهاد داد .[5] اثبات ریاضی مقاوم بودن SIFT در برابر تغییر مقیاس در مرجع [14] بررسی شده است.
در مرجع [15] کشف و ردیابی اشیاء متحرک با بروزرسانی مدل پسزمینه با الگوریتم فیلتر میانه انجام می شود. در هر گام پسزمینه با جایگذاری مقدار میانه همسایههای هر پیکسل به روز رسانی شده و با اعمال الگوریتم تفریق پسزمینه نواحی متحرک به دست می آید. در ادامه با الگوریتم مولفههای متصل اشیاء متحرک کشف شده و از مرکز هر شی به عنوان فاکتور ردیابی استفاده می شود.
در مراجع [17 ,16] ابتدا ویژگیهای مرتبط با اشیاء متحرک استخراج شده و در هر مرحله به دنبال اشیاء با این ویژگیهای مشخص میگردند. در این مقاله روش های ردیابی مبتنی بر تطبیق مشخصه که از روش های استخراج ویژگی SIFT، KLT و BRISK استفاده می کنند، مورد تحلیل و ارزیابی قرار می گیرند. در این روش های ردیابی برخی فرضیات بر صورت مسئله حاکم است که عبارت اند از: ثابت بودن دوربین، پس زمینه نسبتا ساده، عدم انسداد هدف.
الگوریتم های استخراج نقاط کلیدی برای ردیابی اشیاء متحرک
در این قسمت به بررسی جزئیات هر یک از الگوریتم های استخراج نقاط کلیدی SIFT، KLT و BRISK پرداخته می شود.
-1 استخراج ویژگی SIFT
Sift یک روش برای آشکارسازی و استخراج عوارض مستقل از تصاویر میباشد که میتواند برای تناظریابی2 بین تصاویر مورد استفاده قرار بگیرد. خصوصیات اصلی عوارض مناسب عبارتاند از: بسیار مشخص و متمایز باشند، به آسانی استخراج شوند، مستقل باشند، یعنی نباید وابستگی به مقیاس، دوران، تغییرات در دید سه بعدی، تغییرات در روشنایی تصویر و میزان نویز تصویر داشته باشند. .1-1 آشکار کردن نقاط کمینه و بیشینه در فضای مقیاس3 با استفاده از مفاهیم هرم تصویری4 و فضای مقیاس، آشکار کردن نقاط کمینه و بیشینه در فضای مقیاس انجام میپذیرد. مطابق شکل 1 ابتدا تصویر در چند مقیاس مختلف تشکیل می شود سپس برای هر مقیاس تصویری، پنج تصویر با انحراف معیار مختلف بهوجود می آید که در نتیجه به تعداد مقیاسهای مختلف دستههای پنج تصویری ایجاد می شود. در معادلات - 1 - ، - 2 - و - 3 - محاسبات لازم برای استخراج نقاط کلیدی کاندید آورده شده است.
هرم تصویری با تابع گوسین [5]
.2-1 انتخاب نقاط کلیدی از بین نقاط کمینه و بیشینهی اصلی در این مرحله مقادیر شدت روشنایی سطوح خاکستری هر پیکسل با 8 پیکسل مجاور آن و همچنین با 9 پیکسل در تصاویر مجاور بالایی مقایسه میگردد، اگر مقدار این پیکسل از تمام 26 پیکسل همسایه بیشتر یا کمتر بود این نقطه به عنوان نقطه کلیدی انتخاب میشود.
.3-1 تعیین موقعیت مکانی هر نقطه کلیدی در این مرحله موقعیت هر نقطه اصلی از لحاظ مختصات تعیین می- گردد و نقاطی که دارای کنتراست کم میباشند حذف میشوند.
-2 استخراج ویژگی KLT
الگوریتم [7] KLT یکی از الگوریتمهای ردیابی مبتنی بر تطبیق مشخصه میباشد. الگوریتم ترکیبی KLT از سه بخش تشکیل شده است. در ادامه بخشهای انتخاب یک ویژگی خوب، یافتن بهترین تطبیق برای ویژگیهای خوب و تصحیح خطا به روش پیشرو - پسرو به اختصار تشریح میشود..2-2 انتخاب یک ویژگی خوب در مرجع [7] بر کیفیت ویژگیها از طریق اندازهگیری عدم شباهت نظارت میشود . عدم شباهت مشخص کنندهی تغییرهای ظاهرشده در یک ویژگی بین فریم جاری و چند فریم قبلی میباشد. ایدهی اصلی به این صورت است که پس از استخراج ویژگی، معیار شباهت از طریق محاسبه میانگین مربعات خطا در فریم جاری و چند فریم قبلی، محاسبه میشود. در صورتیکه عدم شباهت این ویژگی در طول چند فریم رشد کرد، ویژگی استخراج شده کنار گذاشته می-شود.
شش پارامتر ظاهر شده در ماتریس تبدیل و بردار جابهجایی d میباشد. . در صورتیکه ناحیهی هدف کوچک باشد تعداد پارامترهای مورد نیاز برای تطبیق الگو در مدل همگر کافی نبوده و لذا ردیابی قابل اعتماد نخواهد بود. در این حالت در صورتیکه تغییرات درون فریمی هدف کوچک باشد میتوان از مدل انتقال محض برای ردیابی نقاط ویژگی استفاده کرد. هدف از این بخش یافتن نقطه تطبیقی نمیباشد، بلکه با فرض بهدست آوردن بهترین تطبیق بررسی میشود آیا برای این ویژگی عدم شباهت در فریمهای متوالی افزایش مییابد یا خیر؟ در صورتی-که عدم شباهت افزایش پیدا کند این ویژگی کنار گذاشته میشود؛ لذا هدف کمینه کردن رابطه - 5 - میباشد که به عنوان عدم شباهت در نظر گرفته میشود. پنجرهی ویژگی و - - مشخص کنندهی یک تابع وزن میباشد. در حالت ساده، - - = 1 در نظر گرفته میشود و برای اهمیت دادن به ناحیهی مرکزی پنجرهی ویژگی، میتواند به صورت یک تابع گوسی در نظر گرفته شود.
.3-2 یافتن بهترین تطبیق برای ویژگیهای خوب
هدف الگوریتم [18] LK یافتن بهترین تطبیق - - برای تصویر ورودی - - میباشد، که = - , - بردار ستونی از مختصات پیکسلهای تصویر، - - تصویر ورودی در زمان = 1 و - - یک زیرمجموعه از تصویر دوم در زمان = 2 میباشد. یافتن بهترین تطبیق از طریق کمینه کردن مجموع مربعات خطا بین الگوی هدف - - و تصویر انجام میشود. در الگوریتم LK تابع هزینهای که به منظور یافتن بهترین تطبیق مورد استفاده قرار میگیرد به صورت عبارت - 6 - میباشد.
.4-2 تصحیح خطا به روش خطای پیشرو - پسرو در مرجع [7] معیار کاملی برای بررسی ویژگیها آورده نشده است. مقاله [19] از خطای پیشرو - پسرو به منظور محاسبهی عدم شباهت استفاده میکند. یعنی ردیابی به طور همزمان به صورت رو به جلو و رو به عقب اجرا میشود و تفاوت بین این دو خط سیر اندازهگیری میشود. در این خط سیر دو طرفه نقاطی که به درستی تطبیق پیدا کردند به عنوان ویژگی قوی نگه داشته میشوند و بقیه حذف خواهند شد. خطای پیشرو - پسرو با استفاده از فاصلهی اقلیدسی بین دو خط سیر به صورت رابطه - 7 - تعریف میشود.
-3 استخراج ویژگی BRISK
در مرجع [21] نقاط کلیدی از لایه های اکتاو هرم تصویری و لایه های بین آن استخراج می شود. همچنین موقعیت و مقیاس هر نقطه کلیدی در یک دامنه ی پیوسته از طریق تابع تطبیق درجه دوم محاسبه می شود. در BRISK لایه های هرمی فضای مقیاس شامل n اکتاو و n اکتاو درونی ، n = 4 و = - 0,1, … , − 1 - می باشد. اکتاوها توسط نمونه برداری نیمه ای، از تصویر اصلی
تشکیل می شوند و هر اکتاو درونی بین لایه های و +1 قرار می گیرد. در شکل 2 نحوه ی نمونه برداری از هرم های تصاویر و یافتن نقطه ی کلیدی نشان داده شده است.
استخراج نقاط کلیدی از بین هرم تصاویر [21]
در این الگوریتم از ماسک 9-16 استفاده می شود. در واقع باید 9 پیکسل متوالی در دایره ی 16 پیکسلی روشن تر یا تیره تر از پیکسل مرکزی باشد تا شرایط مسئله محقق شود. در ابتدا ماسک 9-16 روی هر اکتاو و اکتاو درونی به صورت جداگانه با استفاده از آستانه مشابه برای تشخیص ناحیه های بالقوه استفاده می شود. سپس فرآیند حذف غیر ماکزیمم ها انجام می شود. برای هر ماکزیمم استخراج شده فرآیند پالایش مقیاس پیوسته به صورت زیر پیکسل انجام می شود.
به منظور ساده سازی فرآیند پالایش یک معادله ی دوبعدی درجه دوم به هر یک از تکه های سه تایی اختصاص داده می شود. در نهایت امتیازات پالایش شده به یک منحنی یک بعدی پیرامون محور مقیاس اختصاص داده می شود تا مقیاس در موقعیت ماکزیمم تخمین زده شود. در گام نهایی مختصات تصویر بین لایه های بعدی برای تعیین مقیاس درون یابی مجدد می شود تا موقعیت نقطه کلیدی مشخص شود.
آزمایشات و نتیجه گیری
در این قسمت الگوریتم های ردیابی KLT، SIFT و BRISK مورد بررسی قرار می گیرند. در فرآیند ردیابی مبتنی بر روش های تطبیق مشخصه گام اول استخراج نقاط کلیدی می باشد. سپس در فریم های متوالی بهترین تطبیق برای این نقاط به دست می آید.
