[1]

ردیابی اهداف بر اساس تعیین موقعیت جسم در فریم های متوالی تصویر انجام می­پذیرد. برای رهگیری بلادرنگ اجسام متحرک مانوری همچنین جهت کاهش تاثیر نویز، از روش­های بازگشتی تخمین بیزین استفاده می­گردد. تکنیک‌های تخمین اغلب بر اساس الگوی فیشر یا الگوی بیزین بیان می­گردند]1. [در الگوی بیزین، پارامتر مجهول تغییر تصادفی دارد درصورتیکه پارامترفوق در الگوی فیشر ثابت می­باشد. دیدگاه تئوری بیزین در تعیین موقعیت و ردیابی اجسام متحرک، بر اساس تخمین از یک معادله بازگشتی می‌باشد و مطابق آن، تخمین برای سیستم های خطی با نویز گوسی، بر پایه الگوریتم فیلترکالمن بیان می‌گردد. برای سیستم­های غیرخطی با نویز­گوسی، قبل از بکارگیری فیلترکالمن بایستی سیستم را توسط بسط تیلور مرتبه اول حول بهترین تخمین موجود، خطی نمود. این خطی­سازی، نزدیک حالت تخمین زده انجام گرفته و تحت الگوریتم فیلترکالمن­پیشرفته[1] بیان می­گردد ]1­[.

بجای خطی­کردن سیستم جهت استفاده از فیلترکالمن، مساله تخمین را می­توان بصورت مستقیم انجام داد و تابع توزیع چگالی احتمال جسم را بصورت عددی و شمارشی بدست آورد که می­تواند برای مدل­های قطعی و مدل­های تصادفی انجام پذیرد. امروزه با رشد روش­ها و شیوه­های آماری، مساله تخمین یک پارامتر یا حالت یک سیستم غیرخطی تصادفی درکنار مشاهدات و اندازه­گیری­های نویزی، توسط تکنیک تخمین مونته­کارلو[2] برای حل مسائل پیچیده آماری انجام می­گیرد که در قالب الگوریتم فیلترذره[3] بیان می‌گردد]2[. در این مقاله تخمین موقعیت اولیه اجسام متحرک با مانورهای تصادفی بر اساس الگوریتم بازنمونه‌برداری فیلترذره انجام می­گیرد. ابتکاری که در این مقاله برای افزایش میزان دقت صورت پذیرفته است استفاده از فرآیند گرادیان داده ها توسط بردار MeanShift به منظور تخمین موقعیت نهایی جسم میباشد. لذا در این مقاله قصد بر آن است که الگوریتم MeanShift با تخمین موقعیت جسم بر اساس الگوریتم بازنمونه­برداری فیلترذره ترکیب شده و میزان دقت نهایی ردیابی جسم بررسی شود.

الگوریتم MeanShift یک روش تکراری، مبتنی بر مقایسه هیستوگرام هدف در فریم قبلی و هیستوگرام کاندید هدف در فریم جاری می­باشد. هدف نهایی این الگوریتم ماکزیمم نمودن همبستگی میان دو هیستوگرام می­باشد. برای یافتن هدف در فریم جاری، فاصله باتاچاریا[4] میان مدل‌هدف و کاندیدهدف باید کمینه شود. فرآیند موقعیت‌یابی از مکان تخمین زده شده توسط الگوریتم بازنمونه‌برداری فیلترذره در فریم جاری شروع و جستجو در همسایگی آن با استفاده از گرادیان داده­ها توسط بردار MeanShift، ادامه می­یابد.

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

در رسم هیستوگرام یک محدوده، هر پیکسل دارای ارزش یک است، اما در توزیع احتمال، ارزش هرپیکسل وزن آن است که توسط تابع کرنل تعیین می­گردد به نحوی که هرچه پیکسل به مرکز کرنل نزدیکتر باشد، وزن بیشتری دارد. وزن تعریف شده در واقع نسبت احتمال هیستوگرام مدل هدف و کاندیدهدف تخمین زده شده می‌باشد. بنابراین در هر فریم، مرکزجرم وزن ها محاسبه شده و کاندیدهدف به مرکزجرم جسم نزدیک شده و دوباره وزن ها محاسبه می­گردد و مرکزجرم جدید بدست می آید. این روند تا همگرایی کاندیدهدف به مرکزجرم جسم ادامه می­یابد.

در ردیابی بر اساس الگوریتم MeanShift به­تنهایی، می­بایستی دقت داشت که کاندید هدف به‌طور ناگهانی و شدید از موقعیت ابتدایی تغییر نکند]5[، لذا برای مواقعی که هدف تغییرات ناگهانی دارد و دارای مانور حرکتی است، این الگوریتم دارای محدودیت بوده و به شکست منجر می‌گردد. محدودیت مذکور به‌طور قابل ملاحظه­ای در الگوریتم ترکیبی این مقاله برطرف شده است، به این صورت که موقعیت اولیه­ای برای اهداف مانوری با استفاده از الگوریتم باز نمونه‌برداری فیلتر ذره تخمین زده شده و ازآنجاکه این موقعیت بطوردقیق در مرکز جرم هدف نیست، استفاده از الگوریتم MeanShift می­تواند موقعیت کاندید هدف را در مرکز جرم هدف قرارداد که این کار موجب دقت بالای ردیابی خواهد شد. ازآنجاکه شعاع کرنل نیز در هر فریم متناسب با ابعاد کاندید هدف تغییر می­کند، تخمین موقعیت در مرکز جرم هدف می‌تواند دقت تعیین شعاع کرنل در آن فریم را به نحو مطلوبی بهبود دهد. با توجه به اینکه ویژگی استفاده‌شده در این مقاله بر اساس هیستوگرام وزندارشده تعیین می‌شود، روش ارائه‌شده در برابر تغییر شکل جسم مقاومت بالایی خواهد داشت.

در ادامه در بخش‌های جداگانه، الگوریتم فیلتر ذره در تخمین حالت جسم بررسی‌شده و تخمین چگالی کرنل و الگوریتم MeanShift و چگونگی وفقی سازی شعاع کرنل تشریح می­گردند.

1- فیلتر ذره

فیلتر ذره یک روش جدید برای به دست آوردن تابع توزیع احتمال فیلتر ذره روشی جدید برای به دست آوردن تابع توزیع احتمال پسین بر پایه تئوری بیزین است. الگوریتم فیلتر ذره بر مبنای روش­های مونته کارلوی زنجیره­ای[5] بوده که در آن از نمایش ذره­ای چگالی احتمال، برای تخمین پارامترهای یک توزیع دلخواه استفاده می­شود. فیلتر ذره راه‌حل کاملی برای تخمین بهینه حالت جسم در شرایطی که مدل سیستم غیرخطی با توزیع نویز غیر گوسی است، است. مدل انتقال یا حرکت سیستم با زبان احتمالات به‌صورت  و مدل مشاهده و یا اندازه­گیری سیستم با  بیان می­شود،  نماینده بردار حالت سیستم در حالت کنونی و  نماینده مشاهده در سیستم است.

معادلات بازگشتی بیزین از دو مرحله زیر تشکیل‌شده‌اند:

مرحله پیش‌بینی:

مرحله بروز رسانی:

انتگرال­گیری بر روی متغیرهای فضای حالت فرایند صورت می‌گیرد. درصورتی‌که ابعاد فضای حالت زیاد باشد، هزینه محاسبات بالا خواهد بود. روش شبیه­سازی مونت‌کارلو به‌جای محاسبه انتگرال در تمامی نقاط، مقدار آن را با نمونه­برداری در نقاطی که بیشترین سهم را در محاسبه انتگرال دارند، انجام می­دهد. به این صورت که برای محاسبه انتگرال

آن را به‌صورت حاصل‌ضرب عبارت g (x) = f (x). p(x) تبدیل می­نماید که در آن p(x) نشان‌دهنده تابع احتمالی است که شرایط  را برآورده کند. لذا با این شرایط، I امید ریاضی تابع دلخواه f (x) خواهد بود.

 حال اگر از مدل حالت سیستم تا لحظه k که با تابع احتمال  بیان می­شود، به تعداد N ذره (1N>>) مستقل و هم توزیع مانند () نمونه­برداری شود:

تخمینی از این توزیع به‌صورت زیر تعریف می­شود:

که در آن  نشان دهنده تابع دلتای دیراک در نقطه () است. اگر امید ریاضی تابع دلخواه f(.)نسبت به  با I نشان داده شود:

آنگاه تخمین مونت‌کارلوی انتگرال به‌صورت حاصل جمع مقادیر تابع f(.)به ازای نمونه­های به‌دست‌آمده، به‌صورت زیر خواهد بود:

اگر نمونه‌های  مستقل باشند، آنگاه  یک تخمین نااریب است و مطابق با قانون اعداد بزرگ با I قابل تقریب خواهد بود و درصورتی‌که N عدد بسیار بزرگی باشد تخمین به‌خوبی به سمت مقدار واقعی همگرا خواهد شد. همچنین نشان داده می­شود که سرعت همگرایی تخمین، مستقل از واریانس و ابعاد فضای ویژگی بوده و فقط به تعداد ذرات N وابسته است، چنین خصوصیتی مهم‌ترین مزیت انتگرال­گیری مونت‌کارلو نسبت به روش­های انتگرال­گیری عددی است]2[.

1-1- نمونه‌برداری بااهمیت[6]

در اغلب موارد، نمونه­برداری به‌صورت مستقیم از توزیع چگالی p(x) در هر مرحله زمانی به دلایلی مانند پیچیدگی، ابعاد بالا، در دسترس نبودن آن به‌صورت دقیق، چندمتغیره بودن و... ممکن نیست، به همین دلیل می‌توان به‌جای آن از توزیع دیگری مثل q(x) که بسیار شبیه p(x) است، نمونه­برداری انجام داد و بعد با وزنده‌ی صحیح به همان تخمین مونت‌کارلو نزدیک شد. q(x) را توزیع پیشنهادی[7] می­نامند، لذا انتگرال به‌صورت زیر نوشته می‌شود:

لذا تخمین مونت‌کارلوی آن برای 1 N  نمونه مستقل مطابق با توزی  q(x) به‌صورت زیر است:

عبارت  وزن­های بااهمیت نامیده می­شود و ازآنجاکه فاکتور نرمالیزاسیون مربوط به p(x) را نداریم، لذا وزن­های بااهمیت به‌دست‌آمده را نرمالیزه کرده و داریم]3[:

 وزن نرمالیزه شده نمونه i ام‌است که به‌صورت زیر است:

در نمونه­برداری بااهمیت در هر مرحله زمانی، باید نمونه­برداری از توزیع  را به همراه محاسبه وزن­ها انجام داد که محاسبات را در هر مرحله بالا می­برد. روش نمونه­برداری بااهمیت دنباله­ای به حل این مشکل می‌پردازد.

1-2- نمونه‌برداری بااهمیت دنباله­ای (SIS)[8]

ایده اصلی درروش نمونه­برداری بااهمیت دنباله­ای، استفاده دوباره از نمونه­های تولیدشده در مراحل زمانی قبل برای نمونه­برداری از تابع توزیع پسین در مرحله جدید است. این فرایند موجب ثابت ماندن هزینه محاسباتی الگوریتم در هر مرحله می­شود، به این منظور باید بتوان تابع توزیع پیشنهادی هرلحظه k را به‌صورت زیر تجزیه کرد:

لذا برای نمونه­برداری از توزیع پیشنهادی در مرحله k فقط لازم است که از توزیع q(x_k| X_k-1,Z_k) برای  نمونه­برداری شود. اگر { ,i =1,2,…,N} نمایش موقعیت ذرات در لحظه k و وزن مربوط به ذرات در لحظه k به‌صورت { ,i =1,2,…,N} باشد و وزن­ها در هرلحظه زمانی به‌صورت  نرمالیزه باشند. در این صورت توزیع پسین توام در لحظه k به‌صورت زیر تقریب زده می­شود:

 وزن­های بااهمیت ذرات بوده و به‌صورت زیر است:

که از یک توزیع پیشنهادی مانندq(X_k | Z_k)  نمونه­برداری شده است. وزن­ها را می‌توان به‌صورت بازگشتی نیز به دست آورد. لذا داریم]2[:

به جمله­ای که در معادله (16) در هر مرحله زمانی به وزن مرحله قبل ضرب می‌گردد، وزن نمونه گویند، که البته نرمالیزه نیز باید شد.

در این روش تعداد ذرات N در فضای حالت به‌گونه‌ای انتخاب می­شوند که کل فضای حالت را پوشش دهند، هر چه تعداد ذرات بیشتر باشد، تخمین دقیق­تر خواهد بود]2[.

شکل (1) روش نمونه­برداری بااهمیت را به‌صورت شما تیک نشان می­دهد. نقاط دایره­ای، توزیع ذرات و قطر آن‌ها وزن ذرات را نشان می­دهد. با فرض اینکه همه ذرات در لحظه k وزن یکسانی داشته باشند، توزیع احتمال پسین در لحظه k رسم می­شود، به‌این‌ترتیب وزن ذرات در لحظه k+1 با استفاده از توزیع احتمال پسین در لحظه k (توزیع پیشین در لحظه k+1) بروز می­گردند. لذا وزن ذرات، یعنی قطر نقاط دایره­ای، در مکان­هایی که مقدار تابع توزیع احتمال کوچک‌تر است، کمتر می­باشند. لذا با استخراج ذرات و وزن مربوط به آن‌ها، توزیع پسین به‌صورت معادله (14) بیان می­شود. ساختار توضیح داده‌شده در این قسمت که توزیع پسین توام در هر مرحله، با استفاده از نمونه­های وزندار­شده توصیف می­گردند، اساس کاری فیلترهای ذره­ای محسوب می­شوند.

شکل (1): نمایش روش SIS از تابع چگالی احتمال پسین

1-3- توزیع پیشنهادی

موضوع اساسی در فیلترهای ذره، انتخاب توزیع پیشنهادی مناسب است، ساده­ترین انتخاب، توزیع پیشین است]13[، یعنی:

که در حالت کلی معادل نمونه­برداری از تابع چگالی احتمال نویز خواهد بود؛ یعنی:

و معادله (16) برای وزن­ها به حالت زیر تغییر می­کند:

مشکلات این روش، افزایش واریانس وزن­ها است]10[، چراکه واریانس وزن­ها در این توزیع پیشنهادی، در هر مرحله افزایش می­یابد و تنها چند ذره وزن زیادی دارند، یعنی پس از گذشت زمان اندکی، بیشتر نمونه­ها وزن نرمالیزه شده نزدیک به صفر خواهند داشت و تنها یک نمونه دارای وزن بزرگی است که از این پدیده بانام انحطاط[9] ذرات یاد می­شود. لذا تخمین مناسبی از توزیع پسین توام را ارائه نمی­کند. همچنین در این حالت اکثر توان محاسباتی، به نمونه­برداری و محاسبه وزن برای نمونه­هایی اختصاص‌یافته که به دلیل وزن به سیارکم، تأثیر ناچیزی روی تخمین نهایی دارند و موجب اتلاف توان محاسباتی موجود خواهد شد. برای حل مشکل انحطاط، انتخاب توزیع پیشنهادی در مرحله k باید به صورتی باشد که واریانس شرطی وزن‌ها را کمینه کند]11[. به این توزیع، توزیع پیشنهادی بهینه[10] گفته می­شود که از اطلاعات به‌دست‌آمده از مشاهده آخر نیز در نمونه­برداری استفاده می­کند، این توزیع به فرم زیر است:

طبق معادله (16) وزن­ها برای این توزیع به‌صورت زیر به دست می­آیند:

وزن­ها به نمونه­های تولیدشده در مرحله فعلی () وابسته نمی­باشند، لذا امکان موازی­سازی نمونه­برداری و محاسبه وزن­ها در هر مرحله را میسر می‌کند]14[. در شبیه­سازی این مقاله از این نوع توزیع استفاده‌شده است.

1-4- باز نمونه‌برداری دنباله­ای (SIR)[11]

باز نمونه‌برداری، روشی برای حل مشکل انحطاط از طریق صفر کردن واریانس وزن­هاست، این روش نقشی اساسی در کارایی روش­های مونته کارلوی دنباله­ای بازی می­کند. در مرحله باز نمونه‌برداری از میان نمونه­های وزنده‌ی شده در انتهای یک مرحله زمانی SIS، N بار نمونه­برداری انجام می­شود. شانس انتخاب شدن هر ذره به وزن آن وابسته است. درنتیجه در این مرحله، نمونه­هایی با وزن بیشتر چندین مرتبه کپی شده و نمونه­هایی با وزن کمتر حذف می­شوند. در انتهای این مرحله وزن همه نمونه­های انتخاب‌شده برابر با  خواهد شد. شکل (2) نمای گرافیکی مرحله باز نمونه‌برداری را برای 10 ذره نشان می­دهد. به این روش که از نمونه­برداری بااهمیت دنباله­ای، باز نمونه‌برداری می­کند، باز نمونه‌برداری دنباله­ای (SIR) گویند و اگرچه SIR گامی حیاتی برای مقابله با انحطاط در فیلترهای­ذره­ای است، ولی مشکلاتی را نیز به دنبال خواهد داشت]12[، چراکه SIR خود تخمینی از تخمین وزن‌دار SIS است، درنتیجه SIR به‌ناچار خطایی را در تخمین آن مرحله ایجاد خواهد کرد و دیگر اینکه SIR باعث کپی شدن ذرات با وزن­های بیشتر و حذف نمونه­های با وزن کم می­شود. این موضوع باعث می­شود که نمونه­ها گذشته یکسانی پیدا کنند. در عمل ممکن است به حالتی برسیم که همگی ذرات موجود در مرحله زمانی k، نمونه­هایی یکسان برای تعیین موقعیت در آن مرحله داشته باشند، یعنی موقعیت جسم تنها با یک نمونه تخمین زده‌شده است. به این پدیده فقر نمونه[12] گفته می­شود. لذا باید تا جایی که امکان دارد در SIR بااحتیاط رفتار نمود.

شکل (2): نمای گرافیکی بازنموده برداری N ذره]2[

شکل (3) نحوه جایگزینی وزن­ها در مرحله SIR را نشان می‌دهد که در آن ابتدا عددی بین صفر و یک به‌صورت اتفاقی و با توزیع یکنواخت تولید می­شود. با تصویر کردن آن بر روی تابع سمت چپ، که تابع تجمعی وزن‌های نرمالیزه است، اندیس ذره­ای که باید در جمعیت مرحله بعدی حضورداشته باشد به دست می­آید، لذا ذره‌ای که وزن بیشتر داشته باشد، احتمال انتخاب شدن بیشتری را دارد. موقعیت و وزن، برای هر ذره به میزان چگالی در آن نقطه از فضای حالت وابسته است و این روش، موقعیت هر ذره و وزن متناظرش را برای هر مشاهده به‌صورت بازگشتی بروز می­کند. در پایان این مرحله یک مجموعه جدید از ذرات با موقعیت­ها و وزن‌های جدید به دست می­آیند]15[.

شکل (3) نحوه جایگزینی وزن‌ها در مرحله SIR

در این مقاله معیاری برای سنجش میزان انحطاط و جلوگیری از واگرایی بیان‌شده که با عنوان تعداد نمونه­های مؤثر[13] معرفی می‌گردد. این معیار، به وضعیت نمونه­ها در هر مرحله، عددی مثبت و کوچک‌تر از  نسبت می­دهد که می­توان از آن به‌عنوان تعداد نمونه­هایی که به‌صورت مؤثر توزیع هدف را تخمین می­زنند، تعبیر کرد.

تعداد نمونه­های مؤثر را با  نشان داده و به‌صورت زیر است:

اگر تعداد نمونه­ها از مقدار آستانه از پیش تعیین­شده­ای کمتر باشد، یعنی  (مقدار آستانه N/2)، آنگاه باز نمونه‌برداری انجام می­پذیرد. لذا  است که حد بالای آن برای موقع است که ذرات دارای وزن­های یکسانی باشند و حد پایین آن برای مواقعی است که جمع احتمال ذرات در مرحله k، برابر یک باشد.

فلوچارت کلی الگوریتم باز نمونه‌برداری در شکل (4) ترسیم‌شده است]2[.

شکل (4) فلوچارت کلی الگوریتم بازنموده برداری

تخمین موقعیت نهایی و عدم قطعیت مکانی (واریانس) در استفاده از الگوریتم فیلتر ذره می­تواند به‌صورت زیر محاسبه گردد:

2- تخمین چگالی کرنل

تخمین چگالی یک مفهوم اساسی در مباحث آمار است و به‌طور وسیعی در الگوریتم­های تشخیص و ردیابی مورداستفاده قرار می‌گیرد. طبق تعریف، تخمین چگالی از روی نمونه­های مورد مشاهده تخمین زده می­شود. ازآنجاکه چگالی تخمین زده‌شده به ساختار نمونه­ها وابسته است]6[، با هر تابع چگالی اختیاری تحت شرایطی خاص، قابل‌ارائه است. یکی از عمومی­ترین روش­های تخمین چگالی غیر پارامتریک، روش تخمین چگالی کرنل است]7[.

تخمین چگالی کرنل به‌صورت زیر تعریف می­گردد:

که در آن h پهنای پنجره کرنل، n تعداد پیکسل­ها،  موقعیت پیکسل­ها و k نیز ثابت بهنجارش است. توابع کرنل مختلفی با خواص متفاوت در مقالات بیان‌شده است. این توابع متقارن و تک مد هستند و در نقاط دور از مرکز به‌سرعت به سمت صفر میل می‌کنند. در این مقاله از تابع کرنل Epanechnikov به‌صورت زیر است]4[:

این کرنل نسبت به سایر توابع کرنل دیگر، با توجه به جسم در حال ردیابی در این مقاله تأثیر پس‌زمینه را بیشتر کاهش می­دهد]6[.

2-1- مدل هدف

برای مشخص کردن مدل هدف، ابتدا یک فضای ویژگی انتخاب می­شود، مدل هدف توسط تابع چگالی احتمال آن در فضای ویژگی با q نشان داده می­شود، مدل هدف در این مقاله هیستوگرام سطح خاکستری است. اگر تعداد ویژگی‌ها u = 0,1,…,m باشد، داریم]4[:

که m در این مقاله 255 است. ازآنجاکه مدل هدف، هیستوگرام است، جهت اعمال اعتبار بیشتر به نقاط حول مرکز جرم، از کرنل Epanechnikov برای انجام ماسک در فضای مکان استفاده‌شده است، چراکه پیکسل­های دور از مرکز به خاطر پنهان­شدگی­های جزئی، شبه هدف‌ها و تداخل با زمینه، کمترین اعتبار رادارند.

هیستوگرام مدل هدف با اعمال چگالی کرنل، وزن‌دار شده و به آن هیستوگرام وزندار­شده مدل هدف گفته و به‌صورت:

بیان می­شود که I تعداد پیکسل­ها در محدوده موردنظر،  موقعیت پیکسل­ها در آن محدوده و f نیز فاکتوری جهت تضمین برقراری معادله (27) است]3[.

شکل (5) در قسمت (الف) پنجره محاط بر جسم موردنظر، جهت تعیین مدل هدف در فریم اول را نشان می‌دهد و در قسمت (ب) هیستوگرام وزندارشده سطوح خاکستری مدل هدف که البته نرمالیزه هم­ شده است را باوجود کرنل Epanechnikov نشان می­دهد که موجب کمتر شدن تأثیر پس‌زمینه در هیستوگرام مدل هدف شده است.

شکل (5): (الف) پنجره محاط بر هدف جهت تعیین مدل هدف (ب) هیستوگرام وزندارشده و نرمالیزه شده مدل هدف

2-2- مدل ذرات کاندید هدف

الگوریتم فیلتر ذره، در فریم بعدی موقعیت N ذره را در محدوده­ای اطراف مرکز جرم فریم قبلی به‌صورت تصادفی، پیشگویی می­کند و هرکدام از آن‌ها می­توانند کاندیدی برای موقعیت جدید هدف باشند، لذا هیستوگرام وزندارشده همه این ذرات همانند مدل‌ هدف، به دست می­آیند. لذا اگر کاندید هدف در موقعیت y تعریف شود و تابع چگالی احتمال آن با P(Y) نمایش داده شود، برای هر ذره می­توان نوشت:

و با اعمال کرنلی شبیه مدل هدف، هیستوگرام وزندارشده مدل ذرات کاندید، برای هر ذره به‌صورت زیر است:

f نیز فاکتوری جهت تضمین برقراری معادله (29) به‌صورت زیر است]5[:

2-3- ضریب باتاچاریا

این ضریب میزان مشابهت دو توزیع احتمال گسسته را بیان می‌کند، هرچه دو توزیع شباهت بیشتری با یکدیگر داشته باشند، مقدار عددی آن به یک نزدیک می­گردد و هر چه شباهت کمتر باشد، این ضریب به صفر میل پیدا می­کند. تابع  را به‌عنوان تابع مشابهت میان q و p تعریف می­کنیم که نقش احتمال را بازی می­کند و بیشینه آن در ناحیه کاندید هدف، حضور هدف را در آن فریم با توجه به مشابهت با q نشان می­دهد و به‌صورت:

تعریف می­گردد. برای اینکه این مقادیر مختلف میان مدل هدف و مدل ذرات کاندید هدف، قابل قیاس باشند، این ضریب باید دارای یک ساختار متریک باشد، لذا از تابع فاصله باتاچاریا جهت بررسی میزان اختلاف بین دو توزیع استفاده می­شود:

که این معیار برای هر توزیع دلخواه معتبر بوده و دارای یک ساختار متریک می­باشد و هرچه دو توزیع شباهت بیشتری با یکدیگر داشته باشند، مقدار آن به صفر میل می‌کند]3[.

2-4- تابع درستنمایی مشاهده[14]

تابع درستنمایی مشاهده برای فرایند ردیابی در فیلتر ذره بسیار حیاتی می­باشد، چراکه این تابع موجب وزندارشدن ذرات جهت ورود به مرحله بازنموده برداری می­شوند. این تابع به‌صورت]3[:

بوده که d را از روی فاصله باتاچاریا جایگزین کرده و عددی بین صفر و یک است،  نیز پارامتری تأثیرگذار که میزان واریانس در نظر گرفته‌شده جهت مقایسه مدل هدف با مدل کاندید می‌باشد که در شبیه‌سازی این مقاله 0.1 در نظر گرفته شده است]3[.

3- الگوریتم MeanShift

در الگوریتم MeanShift به دنبال کمینه کردن فاصله­باتاچاریا میان مدل هدف با مدل‌پائین باید بود. کمینه­سازی فاصله‌باتاچاریا معادل بیشینه شدن ضریب­باتاچاریا  می‌باشد. جستجو برای موقعیت نهایی هدف در فریم جاری از موقعیت) هدف که توسط الگوریتم باز نمونه‌برداری فیلتر ذره در فریم جاری تخمین شده، آغاز می­گردد. لذا ابتدا احتمال به‌عنوان کاندید هدف در موقعیت ) از فریم جاری مطابق با معادله (30) محاسبه می­شود. با استفاده از بسط تیلور حول مقدار )، تقریب خطی ضریب باتاچاریا به‌صورت زیر به دست می­آید]5[:

این تقریب در استفاده از الگوریتم MeanShift به‌تنهایی، هنگامی صادق بود که کاندید هدف  به‌طور ناگهانی و شدید از موقعیت ابتدایی  تغییر نکند که در اغلب موارد که هدف حرکت مانوری نداشته باشد، فرض قابل قبولی برای پیرابندهای متوالی تصویر می­باشد]5[ ولی در این مقاله با ترکیب الگوریتم MeanShift و الگوریتم باز نمونه‌برداری فیلتر ذره نیازی به بیان این محدودیت نیست.

ضریب باتاچاریا توسط معادله (30) به‌صورت زیر به دست می­آید:

که در آن  وزن ویژه هر پیکسل بوده و به‌صورت زیر می­باشد:

بنابراین برای کمینه کردن فاصله­باتاچاریا، ازآنجاکه جمله اول معادله (36) مستقل از y است، کافی است جمله دوم این معادله بیشینه شود. همان­طور که مشاهده می­شود این جمله، تخمین چگالی محاسبه‌شده توسط نمایه کرنل  در موقعیت y از فریم جاری با داده­های وزندار­شده  است. مدهای این چگالی با اعمال فرآیند MeanShift و جستجوی بیشینه همسایگی محلی یافت می­شوند]18[. در این فرآیند، کرنل بطوربازگشتی از موقعیت جاری  به موقعیت جدید  به‌صورت زیر حرکت می­کند:

فرض بر آن است که مشتق برای همه  به‌جز برای نقاط محدودی موجود است. مراحل الگوریتم موقعیت­یابی MeanShift در فلوچارت شکل (6) ترسیم‌شده است]5[.

شکل (6): فلوچارت الگوریتم موقعیت‌یابی MeanShift

آستانه بحرانی توقف ، با در نظر گرفتن این نکته که تاچه حد بردارهای  و  به یک پیکسل مشابه اشاره کنند، به دست می­آید. یک آستانه پایین موجب افزایش دقت خواهد شد. برای قید بلادرنگ بودن، تعداد تکرار فرآیند MeanShift به تعدادی محدود می­شود، به‌طور نوعی 20 تکرار درنظرگرفته می­شود؛ اما در عمل میانگین تعداد تکرارها خیلی کوچک­تر و در حدود 4 تکرار است]5[. در شبیه‌سازی این مقاله از تعداد 4 تکرار استفاده‌شده است.

شبیه‌سازی الگوریتم موقعیت­یابی MeanShift می‌تواند ازآنچه در شکل (6) ترسیم‌شده است، ساده­تر شود. به این صورت که در الگوریتم عملی، فقط محاسبه وزن با توجه به معادله (37) انجام‌شده، سپس موقعیت جدید کاندید هدف با توجه به معادله (38) به دست می­آید و میزان جابجایی کرنل توسط آستانه بحرانی توقف ، آزمایش می­شود. ضریب باتاچاریا نیز فقط بعد از کامل شدن الگوریتم، برای ارزیابی میزان مشابهت بین مدل هدف و مدل کاندید هدف انجام می­شود]5[.

4- وفقی سازی شعاع کرنل

 هنگامی‌که اندازه و ابعاد هدف تغییر می­کند، اگر شعاع کرنل که در فریم ابتدایی با توجه به ابعاد هدف تعیین‌شده است، بدون تغییر باقی بماند، می‌تواند موجب شکست الگوریتم گردد و یا به یک موقعیت­یابی ضعیف منجر شود]8[. برای رفع این مشکل، روش مؤثری برای وفق دادن پنجره احاطه‌کننده هدف با مقیاس جدید هدف، پیشنهاد می‌شود. این روش بر مشاهده تغییرات سریع مقدار پیکسل­های تصویروزندار شده، در راستای مرزهای هدف استوار است. لذا چهار الگوی همبستگی  و  با ابعاد h×3 و  و  با ابعاد w ×3 که موقعیت مرزهای چپ، راست، بالا و پایین می‌باشند، مطابق شکل (7) معرفی می‌شوند:

شکل (7): الگوهای همبستگی (از چپ به راست) برای موقعیت‌های چپ، راست، بالا، پایین

h و w ارتفاع و پهنای مستطیل احاطه‌کننده هدف در فریم قبلی است. موقعیت اولیه مرزها  و  و  و  در فریم ابتدایی توسط کاربر تعیین می­گردد و موقعیت ­نهایی مرزها در فریم جاری توسط معادله­های (39) تا (43) تعیین می‌شوند ()]9[.

که  و و نیز ارتفاع و پهنای الگوی همبستگی می­باشد.لذا با یافتن موقعیت­های بالا، پایین، چپ و راست می­توان ابعاد هدف را تعیین و با داشتن پهنا و ارتفاع هدف، می­توان شعاع کرنل را برای فریم بعدی به‌طور مناسب انتخاب نمود.

5- شبیه‌سازی

در این مقاله برای ردیابی یک جسم با مانور زیاد، از هواپیمای جنگنده F22 با 1703 فریم که دارای مانورهای حرکتی با تغییرات در جهت و زاویه به‌صورت تصادفی می‌باشد، استفاده‌شده است.

برای شروع فرایند ردیابی، در فریم اول که قرار است ردیابی آغاز گردد، یک پنجره مستطیلی بر روی هدف محاط کرده و با اعمال کرنل Epanechnikov متناسب با ابعاد پنجره احاطه‌کننده هدف، هیستوگرام وزندارشده سطوح خاکستری، به‌عنوان مدل هدف به دست می‌آید.

شکل (8) در قسمت (الف) جسم موردنظر در فریم اول شروع ردیابی را نشان می­دهد و در قسمت (ب) پنجره محاط بر جسم موردنظر جهت تعیین مدل هدف نشان داده‌شده است و در قسمت (ج) هیستوگرام وزندارشده سطوح خاکستری مدل هدف که البته نرمالیزه هم شده است را با اعمال کرنل Epanechnikov نشان می­دهد.

در فریم اول، ذرات N=100 را در مختصات مرکز جرم هدف، مقداردهی اولیه نموده و برای فریم بعدی که شروع ردیابی می­باشد، ذرات بر اساس مختصات هدف در فریم قبلی با اعمال نویز تصادفی در واریانس مشخص پیشگویی می­گردند، لازم به ذکر است که واریانس حداکثر به‌اندازه سه برابر ابعاد مستطیل احاطه‌کننده هدف است و هنگامی‌که هدف را از دست می­دهد تا ده برابر این ابعاد بزرگ‌شده و جستجو را ادامه می­دهد تا هدف را بیابد که زمان پردازش به‌طور طبیعی در این حالت بالا می­رود، لذا همواره هدف را در احاطه دارد.

شکل (8): (الف) جسم مورد­نظر جهت ردیابی (ب) پنجره محاط بر هدف جهت تعیین مدل­هدف (ج) هیستوگرام وزندارشده و نرمالیزه شده مدل­هدف

پیرامون هرکدام از ذرات نمونه، پنجره­ای با همان ابعاد مستطیل محاط بر هدف، قرار داده و کرنل Epanechnikov به محدوده هر ذره اعمال می­شود. فاصله­باتاچاریا، میزان شباهت میان مدل هدف را با تمام مدل ذرات­کاندید بررسی می­کند و تابع توزیع درستنمایی مشاهده، ذرات کاندید هدف را وزن‌دار می­کند.

در مرحله باز نمونه‌برداری ذرات وزن پایین در موقعیت ذرات با وزن بالا قرار می­گیرند و سرانجام موقعیت اولیه جسم تحت عنوان  با توجه به معادله­های (23) و (24)، تخمین زده می­شود و وزن همه ذرات نمونه انتخاب‌شده برابر N/1 (N=100) خواهد شد.

این موقعیت اولیه  وارد الگوریتم MeanShift شده و مطابق با شکل (6)، موقعیت نهایی جسم در هر فریم تعیین می­گردد. با تعیین مرکز جرم هدف در هر فریم موقعیت­های بالا، پایین، چپ و راست ابعاد هدف با توجه به معادله­های (39) تا (43) به‌دست‌آمده و شعاع کرنل برای فریم بعدی به‌طور مناسب انتخاب می­گردد.

شکل (9) در قسمت (الف) نحوه پراکندگی ذرات را با توجه به واریانس سه برابر پنجره احاطه‌کننده هدف، جهت تعیین موقعیت‌‌ جسم در فریم بعدی نشان می­دهد و در قسمت (ب) نحوه تغییر مکان ذرات با وزن کمتر به موقعیت ذرات با وزن بیشتر در مرحله باز نمونه‌برداری، نشان داده‌شده است و در قسمت (ج) تخمین موقعیت اولیه جسم، بعد از مرحله باز نمونه‌برداری فیلتر ذره در فریم بعدی نشان داده‌شده است و در قسمت (د) تخمین موقعیت جسم بعد از مرحله MeanShift نشان داده‌شده است. همان‌گونه که مشاهده می‌شود، تخمین موقعیت جسم در این مرحله به مرکز جرم هدف نزدیک‌تر است.

در این مقاله با در نظر گرفتن تعداد ذرات N=100 و واریانس پراکندگی تصادفی ذرات به‌اندازه سه برابر پنجره احاطه‌کننده هدف، شبیه­سازی انجام‌گرفته است. مرحله باز نمونه‌برداری با توجه به میزان وزن ذرات به‌صورت وفقی در هر فریم تغییر می­کند. شعاع کرنل نیز بعد از تخمین نهایی موقعیت جسم، به‌صورت وفقی متناسب با ابعاد هدف، تغییر می­کند. شکل (10) نمونه­ای از تغییرات شعاع کرنل در برخی فریم­ها را نمایش می­دهد، همان­طور که مشاهده می­شود الگوریتم به‌خوبی مقیاس هدف را می­یابد و در برابر چرخش هدف بسیار مقاوم می­باشد، چراکه چرخش هدف می­تواند با تغییر شکل، تغییر رنگ (یا سطح خاکستری) و تغییر اندازه همراه باشد که هرکدام به‌نوبه خود مشکل سازند و این الگوریتم مقاومت بالایی در برابر این چرخش­ها دارد.

بعد از مرحله باز نمونه‌برداری فیلتر ذره، تخمین موقعیت هدف در برخی فریم­ها، در مرکز جرم هدف واقع نمی­شود و لذا شعاع کرنل نیز که متناسب با تعیین موقعیت هدف به‌صورت وفقی تغییر می­کند، دچار خطا در تعیین دقیق ابعاد­ جدید هدف می­گردد.

شکل (9): الگوهای: (الف) مرحله پراکندگی ذرات (ب) تغییر موقعیت ذرات بعد از مرحله باز نمونه‌برداری (ج) تخمین موقعیت اولیه هدف بعد از الگوریتم فیلتر ذره (د) تخمین نهایی موقعیت هدف بعد از فرآیند MeanShift

شکل (10): تغییرات وفقی شعاع کرنل متناسب با ابعاد هدف

شکل (11) تعیین موقعیت جسم در برخی پیرابندهای منتخب را بعد از الگوریتم باز نمونه‌برداری فیلتر ذره نشان می­دهد، همان­طور که مشاهده می­شود در این پیرابندها تعیین موقعیت در مرکز جرم هدف واقع نشده است. لذا در این مقاله، موقعیت­های تعیین‌شده توسط فیلتر ذره، به‌عنوان موقعیت اولیه برای الگوریتم MeanShift درنظرگرفته می‌شود و از طریق این الگوریتم سعی در تخمین موقعیت نهایی هدف، درست در مرکز جرم هدف راداریم، البته تعداد مراحل این الگوریتم را 4 مرتبه لحاظ نمودیم تا میزان زمان پردازش بیش‌ازحد بالا نرود. شکل (12) تعیین موقعیت جسم در پیرابندهای منتخب را با الگوریتم ترکیبی باز نمونه‌برداری فیلتر ذره و MeanShift نشان می­دهد، همان­طور که مشاهده می­شود تعیین موقعیت در مرکز جرم هدف واقع‌شده است.

شکل (11): موقعیت هدف در پیرابندهای منتخب با الگوریتم باز نمونه‌برداری فیلتر ذره

شکل (12): موقعیت هدف در فریم‌های منتخب با الگوریتم ترکیبی باز نمونه‌برداری فیلتر ذره و MeanShift

شکل (13): زمان پردازش هر فریم با الگوریتم باز نمونه‌برداری فیلتر ذره

شکل (14): تغییر مراحل باز نمونه‌برداری هر فریم با الگوریتم باز نمونه‌برداری فیلتر ذره

شکل (13) مدت‌زمان پردازش هر فریم را با الگوریتم باز نمونه‌برداری فیلتر ذره نشان می­دهد و شکل (14) نیز تعداد تکرارهای مرحله باز نمونه‌برداری شکل (13) را نمایش می­دهد که وفقی بودن آن نیز، نقش بسزایی در کاهش زمان پردازش دارد، زمان متوسط این الگوریتم با تعداد 100 ذره، 35 میلی­ثانیه می­باشد و آن‌گونه که در شکل (11) نیز مشاهده می­شود، تخمین موقعیت­ها به‌طور دقیق در مرکز جرم هدف نیست.

شکل (15) مدت‌زمان پردازش هر فریم را با الگوریتم ترکیبی باز نمونه‌برداری فیلتر ذره و MeanShift نشان می­دهد و شکل (16) نیز تعداد تکرارهای مرحله باز نمونه‌برداری شکل (15) را نمایش می‌دهد، زمان متوسط این الگوریتم ترکیبی 41 میلی­ثانیه می­باشد که نسبت به شبیه‌سازی زمان متوسط الگوریتم باز نمونه‌برداری فیلتر ذره حدود 6 میلی­ثانیه افزایش زمان را نشان می­دهد ولی دقت تعیین هدف در تمامی فریم‌ها بالاتر و به‌صورت تقریبی در مرکز جرم هدف واقع‌شده است.

در جدول (1) نیز مدت‌زمان پردازش برخی فریم‌های منتخب در شکل (12) با دو الگوریتم باز نمونه‌برداری فیلتر ذره و الگوریتم ترکیبی باز نمونه‌برداری فیلتر ذره و MeanShift، به‌صورت کمی با یکدیگر مقایسه شده است.

فلوچارت کاملی از الگوریتم ترکیبی باز نمونه‌برداری فیلتر ذره و MeanShift که در این مقاله شبیه‌سازی گردیده است نیز پیوست گردیده است.

شکل (15): زمان پردازش هر فریم با الگوریتم ترکیبی باز نمونه‌برداری فیلتر ذره وMeanShift

شکل (16): تغییر مراحل باز نمونه‌برداری هر فریم با الگوریتم ترکیبی باز نمونه‌برداری فیلتر ذره وMeanShift

جدول (1): مقایسه زمان پردازش در برخی فریم‌های منتخب با دو الگوریتم