منبع پایان نامه ارشد با موضوع اندازه گیری و پایان نامه


Widget not in any sidebars

مطابق آن چه ذکر شد، توابع معروف اندازه گیری فوق بر اساس مجموع اختلاف در شدت رنگ پیکسل های دو بلوک می باشند. پس از محاسبه لازم و یافتن بهترین متناظر برای هر بلوک، اختلاف موقعیت دو بلوک در راستای محور های مختصات نشان دهنده بردار جابجایی می باشد. بنابراین به هر بلوک یک بردار جابجایی اختصاص داده می شود. مراحل فوق در ادامه (شکل شماره 3-1) به طور کامل نشان داده شده است. با توجه به این که تصویر اصلی از تعدادی بلوک تشکیل شده است، به جای واژه بردارهای جابجایی از واژه میدان بردار جابجایی برای هر مجموعه بردارهای جابجایی در هر فریم استفاده می کنیم. هر میدان بردار جابجایی به مثابه ماتریسی می باشد که هر درایه آن نشان دهنده بردار جابجایی مربوط به بلوک متناظر آن است. پس از محاسبه میدان بردار جابجایی مربوط به یک فریم خاص، ضمن در نظر گرفتن مکان این بردارها و با دسته بندی آن ها، حرکت نواحی متحرک تصویر شناسایی خواهد شد. البته لازم به یاد آوری ست که این فرض که تمام پیکسل های موجود در یک بلوک دارای بردار جابجایی مشابه هستند لزوما صحیح نیست. ولی برای راحتی محاسبات این فرض در نظر گرفته می شود ]16 [.
شکل سمت چپ : فریم لحظه k که بلوک بندی شده است. شکل سمت راست : فریم لحظه k+1. بلوک متناظر یافت شده و همچنین بردار جابجایی معادل (11،0 ) می باشد.
شکل سمت چپ : فریم لحظه k که بلوک بندی شده است. شکل سمت راست : فریم لحظه k+1. بلوک متناظر یافت شده و همچنین بردار جابجایی معادل (11،0 ) می باشد.
شکل شماره 3-1 الگوریتم تطبیق بلوکی
الگوریتم های جستجوی بلوک متناظر
همان گونه که پیش تر نیز ذکر کردیم، برای یافتن متناظر هر بلوک نیاز به جستجو در ناحیه مشخصی می باشد. اگر حداکثر جابجایی هر بلوک را در فاصله میان دو فریم متوالی برابر مقدار پارامتر p در نظر بگیریم، جستجو برای یافتن بهترین متناظر محدود به ناحیه ای مربعی به ابعاد می شود.
روش جستجوی کامل
روش جستجوی کامل اولین روش جستجوی مورد استفاده در الگوریتم های تطبیق بلوکی بود. این روش با جستجوی تمام نقاط ناحیه مورد نظر، بهترین جواب ممکن موجود در آن ناحیه را معرفی می کند. اگرچه این روش می تواند جواب بهینه را در ناحیه مورد نظر بیابد، حجم محاسبات بسیار زیاد آن مشکل عمده ای به شمار می رود. مقدار متغیر p با توجه به سرعت حرکت اهداف در نظر گرفته خواهد شد. دلیل این امر را می توان این گونه بیان کرد که این متغیر نشان دهنده سطح ناحیه مورد جستجو می باشد. اگر فرض را بر آن بگیریم که حداکثر جابجایی هدف در فاصله زمانی میان دو فریم متوالی به اندازه p پیکسل می باشد، برای یافتن بهترین بلوک متناظر نیاز به مقایسه بلوک ابتدایی موجود در فریم فعلی با بلوک مختلف در فریم بعدی می باشد. با توجه به اندازه بلوک ها و همچنین محاسبه تابع شباهت برای تمام بلوک ها، به وضوح می بینیم که حجم محاسبات برای یافتن بهترین بلوک متناظر با هر بلوک یک مقدار بسیار زیاد است. این حجم محاسبات وقتی نیاز به انجام همین اعمال برای تمام بلوک های تصویر باشد، به قدری افزایش می یابد که تقریبا کاربرد عملی روش مذکور به خصوص در الگوریتم های برخط را غیرممکن می سازد. به همین دلیل ایجاد روش مناسب تری برای جستجو که با حجم محاسبات بسیار کم تر که بتواند پاسخ قابل قبولی را ارائه دهد، مد نظر قرار گرفت. در این بین و پس از به وجود آمدن روش های بسیار، روش الگوریتم جستجوی سه مرحله ای موسوم به TSS بیش از بقیه مورد توجه قرار گرفت ]17، 18[. همچنین در این پایان نامه نیز از این روش برای جستجو استفاده شده است.
الگوریتم جستجوی سه مرحله ای TSS
این روش یکی از محبوب ترین الگوریتم های به وجود آمده برای جستجو می باشد. در بسیاری از کاربرد های بر خط مانند تلفن های تصویری و کنفرانس های ویدئویی که نیاز به استفاده از الگوریتم های تطبیق بلوکی با سرعت بسیار بالا می باشد، از این روش استفاده می شود. این روش بر اساس یک فرض اصلی استوار است که عموما و در اغلب موارد (به جز موارد خاص) برقرار است. این الگوریتم فرض می کند که میزان خطا با فاصله گرفتن از نقطه جواب بهینه به صورت یکنوا در تمام جهات افزایش می یابد. به عبارت بهتر در زمان جستجو، هر چه به نقطه بهینه نزدیک تر می شویم مقدار خطا باید لزوما کاهش یابد. بنابراین می توانیم از همان ابتدا با یافتن نواحی که احتمال وجود نقطه بهینه در آن ها بیش تر است، تعداد مراحل مورد نیاز برای جستجو را به مقدار چشم گیری کاهش دهیم.
نحوه عملکرد این روش به این صورت است که ابتدا در مرحله اول 9 بلوک اولیه که درون ناحیه مورد جستجو هستند را با بلوک مورد نظر مقایسه می کند. مکان این 9 بلوک بسته به مقدار تعیین شده برای p و بر اساس اندازه ناحیه جستجو می باشد. پس از محاسبه تابع اندازه گیری شباهت برای تمام این بلوک ها، ناحیه اطراف بلوکی که بیش ترین مقدار شباهت را دارد به عنوان ناحیه جدید در نظر گرفته می شود. با توجه به فرض اصلی این روش، نقطه بهینه احتمالا در اطراف این ناحیه قرار دارد. از این رو در مرحله بعد جستجو برای یافتن نقطه بهینه را مشابه مرحله قبل و این بار در این ناحیه انجام می دهیم. لازم به ذکر است که ناحیه مورد بحث بسیار کوچک تر از ناحیه اولیه می باشد. در این مرحله نیز 9 بلوک انتخاب می شود و پس از محاسبه شباهت ها، ناحیه اطراف بلوکی که بیشترین شباهت را دارد به عنوان ناحیه جدید در نظر گرفته می شود. این روند آن قدر ادامه می یابد تا منجر به یافتن یک نقطه خاص شود. در صورت برقراری فرض اصلی، این نقطه همان نقطه بهینه است و در غیر این صورت یک نقطه زیر بهینه نام می گیرد. با توجه به مقادیر استانداردی که عموما برای p در نظر می گیرند، معمولا این روش پس از سه مرحله نقطه مورد نظر را می یابد. دلیل اصلی نامگذاری آن نیز همین حقیقت می باشد. با توجه به مقدار دلخواه p تعداد مراحل لازم این الگوریتم برای رسیدن به جواب از رابطه زیر محاسبه می شود :
(3-3)
علامت [ . ]، در رابطه بالا نشان دهنده عمل گر جز صحیح می باشد.
به علاوه اندازه گام که نشان دهنده نحوه توزیع 9 بلوک و فاصله آن ها است نیز از رابطه زیر به دست خواهد آمد :
(3-4)
که در آن n نشان دهنده شماره مرحله جستجو می باشد.
اگر چه این روش مانند روش جستجوی کامل لزوما قادر به یافتن جواب بهینه نیست ، ولی با کاهش چشمگیر در حجم محاسبات جواب قابل قبولی را ارائه می دهد. به عنوان مثالی از این کاهش حجم محاسبات، فرض کنید که پارامتر p را معادل 7 در نظر بگیریم. در این حالت برای یافتن بلوک متناظر بهینه به ازا هر بلوک، با استفاده از روش جستجوی کامل به 15*15 مقایسه بلوکی احتیاج است. این در حالی است که با استفاده از این روش پس از 25 مقایسه به جواب مورد نظر خواهیم رسید. این کاهش چشمگیر در حجم محاسبات به خصوص در کاربردهای بر خط بسیار مورد توجه قرار می گیرد.
در شکل زیر نحوه عملکرد سه مرحله این الگوریتم جستجو نمایش داده شده است.
شکل شماره 3-2 الگوریتم جستجوی سه مرحله ای
شکل شماره 3-2 الگوریتم جستجوی سه مرحله ای

در این مثال مقدار p = 7 در نظر گرفته شده است. با توجه به رابطه (3-3) می توان دریافت که الگوریتم جستجو شامل 3 مرحله می باشد. همچنین با توجه به رابطه (3-4) گام در مرحله اول برابر 4 می باشد. همان طور که دیده می شود فاصله بین هر کدام از 9 نقطه ابتدایی که با دایره مشخص شده اند، برابر 4 پیکسل می باشد. همچنین در مرحله دوم که با مربع های سیاه مشخص شده است، فاصله مربع ها 2 و در مرحله پایانی که با مثلث ها سیاه مشخص است، فاصله آن ها از هم 1 می باشد. از آن جایی که نقطه مرکزی تصویر بالا مشخص کننده مکان بلوک در فریم قبلی بوده و نقطه نهایی هم بیان کننده مکان بهترین بلوک متناظر است، بردار جابجایی از تفاضل این دو مقدار حاصل می شود ]17، 18[.
در زیر ( شکل شماره 3-3 ) مرحله اول الگوریتم جستجوی TSS به صورت تصویری نشان داده شده است. بلوک مورد نظر از فریم قبل باید با بهترین بلوک از فریم فعلی که در تصویر نشان داده شده است، تطبیق یابد. به همین منظور مطابق روش TSS به مرکزیت موقعیت بلوک در فریم قبلی، 9 نقطه در فریم موجود در تصویر انتخاب می کنیم و به وسیله آن ها 9 بلوک به دست می آید. همان گونه که در تصویر دیده می شود، بلوک مربوط به فریم قبلی با تمام این 9 بلوک مقایسه می شود تا مطابق آن چه که پیش تر توضیح داده شد، ناحیه جدید مورد جستجو مشخص شود.
ردیف بالا : فریم جدید. ردیف پایین از چپ : یک بلوک از فریم قبلی، 9 بلوک از فریم موجود که باید با بلوک موجود مقایسه شوند.