چکیده
روش انتقال میانگین یکی از روش‌های خوشه‌بندی ثابت شده‌ای است که به صورت گسترده در کاربردهای تصویربرداری همچون قطعه‌بندی تصویر و ویدیو، نویززدایی، مسیریابی اشیاء، طبقه‌بندی بافت و غیره مورد استفاده قرار گرفته است. با این وجود روش انتقال میانگین دارای پیچیدگی زمانی نسبتاً بالایی است که در بسیاری از نقاط داده‌ای، ابرخطی می‌باشد. در این مقاله، روش انتقال میانگین سریع جدیدی ارائه می‌نماییم که بر نمونه‌برداری تصادفی برآورد چگالی کرنل (KDE) مبتنی می‌باشد. به صورت تئوری نشان می‌دهیم که KDE کاهش یافته حاصل، به KDE داده‌های کامل با دقت معینی نزدیک می‌باشد. به‌علاوه ثابت می‌کنیم که پیچیدگی زمانی روش انتقال میانگین سریع پیشنهادی نسبت به پیچیدگی زمانی روش انتقال میانگین اصلی به میزان بسیار قابل ملاحظه‌ای پایین‌تر می‌باشد؛ بهره نوعی برای مجموعه داده‌های بزرگ، چندین مرتبه می‌باشد. آزمایش‌های انجام شده نشان می‌دهند که نتایج قطعه‌بندی تصویر و ویدیو روش انتقال میانگین سریع پیشنهادی با نتایج قطعه‌بندی تصویر و ویدیو مبتنی بر رئش انتقال میانگین استاندارد مشابه می‌باشد. همچنین کاربرد جدید روش انتقال میانگین سریع برای ساخت موثر سلسله‌مراتب گرافی برای تصاویر را نیز ارائه می‌نماییم؛ ساختار حاصل برای حل مسائل بینایی کامپیوتر که می‌توان آنها را همانند مسائل گراف شامل استریو، قطعه‌بندی نیمه‌خودکار و شار اپتیکی مطرح نمود بسیار سودمند می‌باشند.
1. مقدمه
برآورد چگالی کرنل و روش خوشه‌بندی انتقال میانگین از روش‌های بسیار مقبول در زمینه بینایی رایانه‌ای می‌باشند، به عنوان مثال منابع [10، 5] و مراجع ذکر شده در آنها را ملاحظه نمایید. از روش انتقال میانگین به صورت گسترده در کاربردهای تصویربرداری همچون قطعه‌بندی تصویر و ویدیو [5، 20]، نویززدایی [3]، مسیریابی اشیاء [7] و طبقه‌بندی بافت [11] و غیره استفاده شده است. به طور کلی روش انتقال میانگین از دو مرحله تشکیل شده است: (الف) ساخت چگالی احتمالی که توزیع نقاط مربوطه را در برخی از جاهای فضای ویژگی منعکس می‌نماید و (ب) نگاشت هر نقطه در مد (بیشینه) چگالی که به آن نزدیک می‌باشد.
یکی از مشکلات اصلی در بکارگیری روش انتقال میانگین مبتنی بر خوشه‌بندی در مجموعه داده‌های بزرگ، پیچیدگی محاسباتی آن است که در تعدادی از نقاط داده‌ای، ابرخطی می‌باشد. روش‌های در دسترس مختلفی برای افزایش سرعت روش انتقال مانگین وجود دارند. دمنتون و مگرت [8] از یک روش متوالی، مقیاس فضامانند در انتقال میانگین با افزایش پهنای باند استفاده کرده‌اند. یانگ و همکارانش [23] برای افزایش سرعت کلی در توالی انتقال میانگین، از تبدیل گاوسی سریع بهره برده‌اند. گائو و همکارانش [13]، مجموع انتقال میانگین را به تعدادی از زیرمجموعه‌های موضعی تفکیک نموده‌اند. پاریس و دوراند [17] از تفکیک‌پذیری کرنل گاوسی چندبعدی برای اجرای d حلقه یک بعدی جداگانه استفاده نموده‌اند. وانگ و همکارانش [21] از ساختار داده زیرکی، درخت دوتایی، جهت افزایش سرعت انتقال میانگین استفاده کرده‌اند. همچنین مقاله ویوالدی و سواتو در مورد ”انتقال سریع“ [19] نیز در حدی به این مقوله مربوط می‌باشد.
این مقاله در نشریه آی تریپل ای منتشر شده و ترجمه آن با عنوان انتقال میانگین در سایت ای ترجمه به صورت رایگان قابل دانلود می باشد. جهت دانلود رایگان مقاله فارسی و انگلیسی روی عنوان فارسی (آبی رنگ) کلیک نمایید.
منبع:
