بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بهبود ردیابی هدف با استفاده از الگوریتم KLT با رویکرد بازگشتی
چکیده
در این مقاله روش ترکیبی KLT که شــامل یافتن بهترین ویژگی برای ردیابی، تطبیق الگو و تصــحیح خطا در ردیابی هدف اســت بهبود داده میشـود. در الگوریتم ترکیبی هرگاه نقاط ویژگی در اثر تصـحیح خطا و افزایش عدم شباهت به صفر برسد این الگوریتم دچار مشـکل میشـود. راه حل پیشـنهادی با انتخاب یک آستانه مناسب و اعمال یک رویکرد بازگشتی، الگوریتم را قادر میسازد تا ردیابی هدف متحرک را در فریمهای بیشتری انجام دهد. در الگوریتم پیشــنهادی به منظور اســتخراج نقاط بیشتر، ناحیهی هدف در فریم جاری تیزتر1 میشود و سپس نقاط ویژگی برای تطبیق الگو استخراج میشود. الگوریتم پیشنهادی از اطلاعات چهار ضلعی محصــور کنندهی هدف در فریمهای قبلی برای تطبیق دقیق و مقابله با تغییر مقیاس هدف اســتفاده میکند. روش پیشــنهادی بر روی 8 مجموعه دنبالهی ویدئویی اعمال گردید و سـه معیار ارزیابی کیفیت برای سنجش کارایی، استفاده شد. ارزیابی نشان داد که میانگین خطای پیکسـل مرکزی 6/47 و متوسـط همپوشـانی ناحیهی هدف 0/63 و سـرعت اجرا به طور متوسـط 30/97 است. در مقایســه با روش ترکیبی KLT علاوه بر دقت الگوریتم ردیابی، ســرعت اجرا نیز بهبود یافته اســت زیرا برنامه اســتخراج ویژگی از ناحیهی هدف، به زبان سی پیاده سازی شده است.
واژههای کلیدی: الگوریتم KLT، بازگشتی، ردیابی هدف
-1 مقدمه:
ردیابی هدف متحرک به مفهوم تعقیب هدف متحرک در یک ســری تصــاویر متوالی اســت. تاکنون روشهای مختلفی برای ردیابی هدف متحرک در تصـاویر متوالی پیشـنهاد شـده اسـت که از جمله میتوان به روشهای شـار نوری، روشهای تطبیق مشــخصه و روشهای پیرامون فعال اشاره کرد. روش شار نوری بردارهای حرکت را برای کلیهی نقاط تصویر محاسبه میکند و بیشتر به منظور آشکارسازی هدف مورد استفاده قرار میگیرد که میتوان از روشهای مشتقگیری، تطبیق ناحیه و روش فاز نام برد.
در روشهای تطبیق مشـخصـه ابتدا یک مجموعه ویژگی از جمله لبهها، گوشـهها از تصویر استخراج میشود و سپس تناظری بین نقاط ویژگی در تصــویرهای متوالی برقرار میگردد. در ســال 1991 ســه عامل یکتایی، نزدیکی و تشــابه برای پیدا کردن تطبیق مشخصه معرفی شد .[1] در مدلهای پیرامون فعال [3 ,2] یک پیرامون اطراف هدف در نظر گرفته میشود و توسط برخی از نقاط مشـخص هدف مورد نظر ردیابی میگردد. در این روش تغییرات شدت روشنایی، انسداد (پنهان شدن) هدف، حرکت با سرعت ثابت یا شـتاب گرفتن هدف، پس زمینه نامناسـب، چرخش و تغییر مقیاس هدف در الگوریتمهای پیشـنهادی در نظر گرفته نمیشــد که باعث عملکرد ناصـحیح در بعضـی از تصـاویر ویدویی میشود. هم چنین در این الگوریتمها عمل ردیابی با فرض ثابت بودن دوربین انجام شده است.
در سـالهای اخیر این چالشها مرتفع و روشهای نوینی پیشنهاد شده است. این الگوریتمهای ردیابی پیشنهادی در دو گروه مهم طبقهبندی میشوند .[4] این دستهبندی براساس مدل ظاهری هدف به صورت الگوریتمهای ردیابی مولد[9-5] 1 یا تبعیضی-10] 2 [13-10] انجام میشود.
هدف الگوریتمهای مولد و تبعیضـی مقابله با انسـداد هدف از طریق ذخیره کردن دنبالهای از الگوهای پیشین و بهروز رسانی الگوها میباشد. لازم به ذکر است که این الگوریتمها در زمان اجرا قابل مقایسه با الگوریتمهای تطبیق مشخصه نیستند.
در روشهای تطبیق مشـخصـه هنگامی که هدف توسط شیء دیگری مسدود نشود و شیء مورد ردیابی صلب باشد ردیاب عملکرد خوبی خواهد داشـت. یکی از روشهای ردیابی تطبیق مشـخصـه، الگوریتم ردیابی برخط (surf) میباشد [14]، که توسط Guijin Wang و همکارانش در سـال 2011 ارائه شـد. روشهای تطبیق مشـخصـه سرعت اجرای خوبی دارند ولی انتخاب ویژگیهایی که بتواند هدف را در فریم های متوالی ردیابی کند، مشکلی است که هنوز باقی مانده است.
در سیستمهای بینایی ماشین، ردیابی خوب مستلزم ویژگیهای خوب3 میباشد. چالش موجود در انتخاب ویژگی است که در مقابل تغییر شـدت روشـنایی، انسـداد، تغییر مقیاس و دوران مقاوم باشد. در مرجع [15] نحوه انتخاب ویژگی خوب به تفضیل بیان شده است. بعد از انتخاب یک ویژگی خوب و مورد اعتماد باید بهترین تطبیق را برای این نقاط در فریم های متوالی پیدا کرد .[16]
در روش ترکیبی از الگوریتم LK4 استفاده شده است. در این الگوریتم بعد از یافتن بهترین تطبیق برای یک ویژگی باید عملکرد آن ویژگی در فریم های متوالی بررسی شود. این عمل با استفاده از روش خطای پیشرو - پسرو5 انجام میشود .[17] ایدهی اصلی این روش ترکیبی این اسـت که در صورتی که عدم شباهت الگوها برای یک ویژگی افزایش یافت یا این که یک ویژگی در ردیابی پیشرو و ردیابی پسـرو نتیجهی یکسـانی نداشت آن ویژگی باید حذف شود. مشکل از همین قسمت شروع میشود که مشخص نشده است در صـورتی که ویژگیها به صـفر رسـید ادامه ردیابی چگونه انجام خواهد شـد. چون در دنیای واقعی هدف پیوســته در اثر تغییرات
باید یک تابع
J(Ax + d) = I(x)
شدت روشنایی، انسداد و نویز قرار میگیرد و ممکن است نقطهای که به عنوان ویژگی در نظر گرفته شده است در فریمهای متوالی تطبیقی پیدا نکند و حذف شود؛ لذا لازم است یک آستانه برای تعداد ویژگیهایی که میخواهد ردیابی شود در نظر گرفته شود. سـاختار مقاله به صـورت زیر میباشد. در بخش اول انتخاب ویژگی خوب تشریح میگردد. سپس یافتن بهترین تطبیق مورد بررسی قرار داده میشود و در نهایت روش تصحیح خطا در ردیابی نقاط ویژگی ارائه میشود. در بخش چهارم روش پیشنهادی بیان میشود و تکنیک مورد استفاده در ردیابی نقاط ویژگی توضیح داده خواهد شد. در بخش پنجم آزمایشها و نتیجهگیری بحث میشود.
-2 انتخاب یک ویژگی خوب
در مرجع [15] روشــی برای بررســی ویژگیها به منظور تشــخیص انســداد یا عدم انســداد ارائه شــده اســت. ویژگیهایی که داخل پنجرهی تطبیق قرار میگیرند میتواند شــامل گوشــه یا ناحیههایی با بافت زیاد باشــد. چون ظاهر هدف در حال تغییر میباشــد، احتمال وجود ناحیهای غنی از بافت ضـعیف استمثلاً.اگر ناحیهی هدف مرز منعکسکنندهی نور از یک سطح براق باشد، بافتی در این ناحیه وجود نخواهد داشت، تا به عنوان ویژگی انتخاب شود. وجود چنین ویژگیهایی ردیابی را با مشکل مواجه خواهد کرد.
مشـکل اصـلی دیگر این است که در صورت انسداد هدف ویژگیهای خوب استخراج شده نیز مسدود میشوند و نقطهی تطبیقی در فریم جاری وجود نخواهد داشت و الگوریتم با مشکل مواجه میشود.
در [15] همچنین بر کیفیت ویژگیها از طریق اندازهگیری عدم شـــباهت (تغییرهای ظاهرشـــده در یک ویژگی بین فریم جاری و فریم اول را نشـان میدهد) نظارت میشود. ایدهی اصلی به این صورت است که پس از استخراج ویژگی و محاسبه میانگین مربعات خطا برای یک ویژگی در فریم جاری و فریم اول هنگامی که عدم شـباهت رشــد میکند، ویژگی اسـتخراج شــده باید کنار گذاشــته شود.
مرجع [15] خود یک روش ترکیبی میباشــد چون از هر دو مدل انتقال محض و دوران برای محاســبهی عدم شــباهت اســتفاده میکند . در صـــورتی که ناحیهی هدف کوچک باشـــد تعداد پارامترهای مورد نیاز برای تطبیق الگو در مدل افاین کافی نبوده و لذا ردیابی قابل اعتماد نخواهد بود در این حالت در صورتی که تغییرات درون فریمی هدف کوچک باشد می توان از مدل انتقال محض
برای ردیابی نقاط ویژگی استفاده کرد که به صورت معادله (1) ارائه میشود: (1)
d بردار انتقال ویژگی x میباشـــد. یک نقطهی x در تصـــویر اول I به نقطهی Ax + d در تصـــویر دوم J منتقل میشـــود درحالیکه = + و یک ماتریس همانی اسـت، تا در صورتی که تعداد پارامترهای افاین کافی نبود بتوان از مدل انتقال محض برای تطبیق استفاده کرد و یک ماتریس تبدیل است.
در این بخش هدف یافتن نقطه تطبیقی نیسـت بلکه با فرض بهدسـت آوردن بهترین تطبیق بررسی میشود که آیا برای این ویژگی در فریمهای متوالی عدم شـباهت افزایش پیدا میکند یا خیر، در صورتی که عدم شباهت افزایش پیدا کند این ویژگی کنار گذاشته میشود. لذا هدف کمینه کردن معادلهی (2) است که به عنوان عدم شباهت شناخته میشود:
پنجرهی ویژگی داده شـده اسـت و w(x) یک تابع وزن است. در حالت سادهتر، w(x)=1 میباشدمتناوباً. شبیه به گوسی باشد تا به ناحیهی مرکزی پنجره اهمیت بیشتری بدهد.در این روش هدف این اسـت که بعد از استخراج ویژگی، آن ویژگیهایی که بیشترین صلبیت را دارند نگه دارد و هر کدام که عدم شـباهت آنها در فریم های متوالی رشـد کرد، را حذف کند. این مورد در Error! Reference source not found.وشکل 2) بیشتر مورد بررسی قرار میگیرد:
همانطور که در شـکل 1 آمده اسـت، اگر هدف ردیابی علامت ترافیکی در فریم 1، 11 و 21 باشـد از تبدیل به دست آمده دریافت میشــود که عدم شــباهت برای ویژگیهایی که در ناحیه هدف انتخاب شــدهاند یک نمودار ثابت دارد و ناحیهی هدف در فریمهای متوالی بعد از اعمال تبدیل، شباهت بسیاری به فریم اول دارد. در شکل 2 سطر اول فریمهای 21،16،11،6،1 از یک دنباله ویدئویی و سطر دوم بعد از اعمال تبدیل بر روی این فریمها مشخص شده است.
این نشــان میدهد، نقاطی که به عنوان ویژگی برای ردیابی علامت ترافیکی انتخاب شــدهاند یک ویژگی خوب میباشــند. چون عدم شباهت آنها همانطور که در نمودار شکل 3) مشخص شده است مقدار ثابتی میباشد.
در شـکل 3 انتقال محض با خط فاصـلهدار، حرکت افاین با خط پیوسـته، عدم شـباهت اندازهگیری شده از شکل 1 با علامت (+) و شـکل 4 با دایره مشـخص شـده اسـت. همانطور که در Error! Reference source not found. مشاهده میشود اگر هدف ردیابی یک شیء براق باشد چون از این ناحیه نمیتوان ویژگی قوی استخراج کرد، عدم شباهت برای این ناحیه در فریمهای متوالی افزایش پیدا میکند. در سـطر اول شـکل 5) خروجی دوربین مشخص شده است و سطر پایین ناحیهی هدف را بعد از اعمال تبدیل نشان میدهد که بیانگر افزایش عدم شباهت در ناحیهی هدف برای ویژگیهای استخراج شده است.
شکل :(4) در این دنبالههای ویدئویی هدف ردیابی پنجرهی روشن در پسزمینه میباشد .[15]
شکل :(5) ردیابی علامت ترافیکی و تبدیل یافتهی آن .[15]
شکل 5 در سطر اول پنجره روشن که در فریم میانی توسط علامت ترافیکی مسدود شده است مشخص شده و در سطر دوم حاصل فریمهای بالا بعد از اعمال ماتریس تبدیل میباشــد. از شــکل 3) میتوان فهمید در صــورتی که در این دنبالههای ویدئویی علامت ترافیکی به عنوان ویژگی انتخاب شـود عدم شباهت برای ویژگیهای آن در هر دو مدل تبدیل افاین و انتقال محض یک مقدار ثابت باقی خواهد ماند، اما اگر سطح براق به عنوان ویژگی انتخاب شود، عدم شباهت این ناحیه به مرور افزایش پیدا میکند.ِ
-3 یافتن بهترین تطبیق برای ویژگیهای خوب
رویکردی که الگوریتم اصـلی LK برای یافتن بهترین تطبیق اسـتفاده میکند به صـورت زیر میباشـد :[16] هدف در این الگوریتم یافتن بهترین تطبیق T(x) برای تصویر ورودی I(x) میباشد، که x = (x, y)T بردار ستونی از مختصات پیکسل است. در این حالت T(x) یک زیرمجموعه از تصویر اول در زمان = 1 میباشد و I(x) تصویر ورودی در زمان t = 2 میباشد.
( ; ) یک مجموعه پارامتری مجاز برای warp میباشــد، که یک بردار از پارامترها اســت. در این حالت تابع تبدیل( ( ; پیکســل را در دســتگاه مختصــات الگوی ) میگیرد و آن را به موقعیتی در مختصــات تصویر تبدیل میکند.
هـدف الگوریتم Lucas-Kanade کمینه کردن مجموع مربعات خطا بین الگوی هدف و تصـــویر اســـت که با تبدیل به سیستم مختصات منتقل شده است.
به منظور اعمال تبدیل W(x; p) روی I برای رسـیدن به سـیسـتم مختصات T(x) باید از دورنیابی پیکسلها در I استفاده
کرد. الگوریتم LK برای یافتن مینیمم معادله 3) فرض میکند که تخمین اولیه از p معلوم اســت و مقدار آورد.
در هر مرحله مقدار p با توجه به مقدار ∆p به روز رسـانی میشود این دو گام تکرار میشود تا تخمین پارامتر
p همگرا شـود. شرط همگرایی میباشد. با نوشتن بسط تیلور مرتبه اول برای معاله (4) نتیجه میشود:
که گرادیان تصویرI در میباشد. یعنی: ∇I در مختصات تصویر I محاسبه میشود، سپس توسط تخمین جــاری از تبــدیــل ژاکوبین تبــدیــل میبــاشـــد. اگر مختصـــات منتقــل خواهــد شـــد و آنگاه:
اگر از معادله ی (5) نسبت به ∆p مشتق گرفته شود:
که تصاویر گرادیان نزولی نامیده میشود. معادله (7) برابر صفر قرار داده میشود تا مینیمم معادلهی (5) بهدست آید:
که H ماتریس n ∗ n هسین میباشد:
پارامتر به روز رسانی گرادیان نزولی گویند.
در این مقاله همچنین اثبات شـــده اســـت که حتی اگر ناحیهی هدف در فریم دوم، از موقعیت واقعی هدف خیلی دور باشـــد، این الگوریتم با تغییر ∆p در نهایت همگرا خواهد شد.
-3 تصحیح خطا به روش خطای پیشرو - پسرو
در مرجع [15] معیار خوبی برای بررسـی ویژگی ها آورده نشده است. مقاله [17] از خطای پشرو - پسرو به منظور محاسبهی عدم شـباهت استفاده میکند. یعنی ردیابی به طور همزمان به صورت رو به جلو و رو به عقب اجرا میشود و تفاوت بین این دو خط سیر اندازهگیری میشـود. در این خط سیر دو طرفه نقاطی که به درستی تطبیق پیدا کردند به عنوان ویژگی قوی نگه داشته میشوند و بقیه حذف خواهند شـــد. هنوز هم ســـخن از کنار گذاشـــتن ویژگیها وجود دارد و با ادامه ردیابی در فریمهای متوالی تعداد این ویژگیها به صفر میرسد و هدف از دسترس الگوریتم خارج میشود.
ردیابی نقطه یک روش معمول در بینایی کامپیوتر است: با توجه به موقعیت نقطهی داده شده در زمان t، هدف تخمین مکان آن در زمان + 1 میباشد. در عمل، چون نقاط از نظر ظاهری به طور چشمگیری تغییر میکنند یا از دید دوربین خارج میشوند، تحت این شرایط، نتیجه ردیابی اغلب با مشکل مواجه میشود. در شکل 6) ردیاب قادر است نقطه شماره 1 را در ردیابی پیشرو و پسرو به درسـتی به یک ناحیه محدود کند. نتیجه ردیابی این نقطه به صورت پیشرو یا پسرو خط سیر یکسانی خواهد داشت. از طرف دیگر، ردیاب نقطه شماره 2 را در ردیابی پسرو به ناحیههای متفاوتی نسبت به نقطهی واقعی نگاشت میکند.
