چهارشنبه 28 شهریور 1397 | Wednesday 19 th of September 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
4 - 2 - 2 - 5 - جستجوی مؤثر

برای محاسبه نمودار CECHیک ناحیه با ابعاد n×nو حد استانه Td‌، از یک الگوریتم ساده با پیچیدگی زمانی O(n2Td2)استفاده می‌شود ‌. ان چه در بخش قبل توصیف شد یک روش ساده و سر راست است که در عوض پر هزینه نیز هست ‌. در این بخش چند تکنیک به کار برده خواهد شد که به طور موثری باعث صرفه جویی در زمان محاسبات می‌شود ‌.

اولاً از ان جا که نمودار CECHدارای خاصیت جمع پذیری است ‌، برای سه ناحیه مانند A‌، Bو Cاز تصویر Iداریم :

 

نکته دوم اینکه Dxو Dyبه صورت Dx<<mmو Dy<<mnهستند‌، بنابراین هر پنجره جستجو با پنجره‌های جستجوی هم جوار[1] خود ‌، روی هم افتادگی هایی دارد ‌. از این ویژگی می‌توان به منظور افزایش کارایی به صورت زیر بهره مند شد :

ذخیره CECHپنجره هایی که قبلا بررسی شده‌اند و استفاده از ان‌ها برای محاسبه بخشی از نمودار CECHپنجره بعدی که با ان روی هم افتادگی و اشتراک دارند ‌. به عنوان مثال ‌، فرض کنید CECHمربوط به ناحیه B1محاسبه شده باشد و CECHمربوط به پنجره B2که با B1روی هم افتادگی دارند مطلوب باشد ‌. همچنین فرض کنید که S1مجموعه‌ای از پیکسل‌های B1باشد که جزو B2نیستند و A1مجموعه‌ای از پیکسل‌های B2باشند که در B1نباشند ‌. CECHمربوط به B2را می‌توان به صورت زیر محاسبه کرد :

 

این محاسبات بسیار سریع انجام می‌شوند زیرا CECH{B1,I}مشخص است و نواحی A1و S1نیز کوچک هستند ‌. زمانیکه نمودار CECHیکی از پنجره‌ها محاسبه شود ‌، از این تکنیک می‌توان به صورت بازگشتی برای محاسبه کارامد نمودار‌های CECHتمام پنجره‌های باقی مانده استفاده کرد ‌.

یکی دیگر از ویژگی‌های مفید CECHبه صورت زیر است :

به بیان دیگر ‌، ممکن است بعضی از عناصر نمودار CECHدر عامل مقیاس گذاری پایینی‌، وقتی که CECHبرای عوامل مقیاس گذاری دیگر محاسبه شده‌اند ‌، تکرار شوند ‌. مثلاً وقتی s=2باشد ‌، در محاسبات نمودار CECH‌، تقریبا به میزان یک چهارم (25/0) صرفه جویی می‌شود ‌.      

 



[1]adjacent search windows 

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26