چکیده
روش انتقال میانگین یکی از روش‌های خوشه‌بندی ثابت شده‌ای است که به صورت گسترده در کاربردهای تصویربرداری همچون قطعه‌بندی تصویر و ویدیو، نویززدایی، مسیریابی اشیاء، طبقه‌بندی بافت و غیره مورد استفاده قرار گرفته است. با این وجود روش انتقال میانگین دارای پیچیدگی زمانی نسبتاً بالایی است که در بسیاری از نقاط داده‌ای، ابرخطی می‌باشد. در این مقاله، روش انتقال میانگین سریع جدیدی ارائه می‌نماییم که بر نمونه‌برداری تصادفی برآورد چگالی کرنل (KDE) مبتنی می‌باشد. به صورت تئوری نشان می‌دهیم که KDE کاهش یافته حاصل، به KDE داده‌های کامل با دقت معینی نزدیک می‌باشد. به‌علاوه ثابت می‌کنیم که پیچیدگی زمانی روش انتقال میانگین سریع پیشنهادی نسبت به پیچیدگی زمانی روش انتقال میانگین اصلی به میزان بسیار قابل ملاحظه‌ای پایین‌تر می‌باشد؛ بهره نوعی برای مجموعه داده‌های بزرگ، چندین مرتبه می‌باشد. آزمایش‌های انجام شده نشان می‌دهند که نتایج قطعه‌بندی تصویر و ویدیو روش انتقال میانگین سریع پیشنهادی با نتایج قطعه‌بندی تصویر و ویدیو مبتنی بر رئش انتقال میانگین استاندارد مشابه می‌باشد. همچنین کاربرد جدید روش انتقال میانگین سریع برای ساخت موثر سلسله‌مراتب گرافی برای تصاویر را نیز ارائه می‌نماییم؛ ساختار حاصل برای حل مسائل بینایی کامپیوتر که می‌توان آنها را همانند مسائل گراف شامل استریو، قطعه‌بندی نیمه‌خودکار و شار اپتیکی مطرح نمود بسیار سودمند می‌باشند.
مقدمه
برآورد چگالی کرنل و روش خوشه‌بندی انتقال میانگین از روش‌های بسیار مقبول در زمینه بینایی رایانه‌ای می‌باشند، به عنوان مثال منابع [10، 5] و مراجع ذکر شده در آنها را ملاحظه نمایید. از روش انتقال میانگین به صورت گسترده در کاربردهای تصویربرداری همچون قطعه‌بندی تصویر و ویدیو [5، 20]، نویززدایی [3]، مسیریابی اشیاء [7] و طبقه‌بندی بافت [11] و غیره استفاده شده است. به طور کلی روش انتقال میانگین از دو مرحله تشکیل شده است: (الف) ساخت چگالی احتمالی که توزیع نقاط مربوطه را در برخی از جاهای فضای ویژگی منعکس می‌نماید و (ب) نگاشت هر نقطه در مد (بیشینه) چگالی که به آن نزدیک می‌باشد.
یکی از مشکلات اصلی در بکارگیری روش انتقال میانگین مبتنی بر خوشه‌بندی در مجموعه داده‌های بزرگ، پیچیدگی محاسباتی آن است که در تعدادی از نقاط داده‌ای، ابرخطی می‌باشد. روش‌های در دسترس مختلفی برای افزایش سرعت روش انتقال مانگین وجود دارند. دمنتون و مگرت [8] از یک روش متوالی، مقیاس فضامانند در انتقال میانگین با افزایش پهنای باند استفاده کرده‌اند. یانگ و همکارانش [23] برای افزایش سرعت کلی در توالی انتقال میانگین، از تبدیل گاوسی سریع بهره برده‌اند. گائو و همکارانش [13]، مجموع انتقال میانگین را به تعدادی از زیرمجموعه‌های موضعی تفکیک نموده‌اند. پاریس و دوراند [17] از تفکیک‌پذیری کرنل گاوسی چندبعدی برای اجرای d حلقه یک بعدی جداگانه استفاده نموده‌اند. وانگ و همکارانش [21] از ساختار داده زیرکی، درخت دوتایی، جهت افزایش سرعت انتقال میانگین استفاده کرده‌اند. همچنین مقاله ویوالدی و سواتو در مورد ”انتقال سریع“ [19] نیز در حدی به این مقوله مربوط می‌باشد.
انتقال میانگین سریع
در این بخش، الگوریتم انتقال میانگین سریع را ارائه می‌نماییم. پس از مروری مختصر بر الگوریتم انتقال میانگین استاندارد، نمایش‌های متراکم موجود برای برآورد چگالی کرنل را به صورت کلی مورد بحث قرار داده و ثابت می‌نماییم که الگوی مبتنی بر نمونه‌برداری این نمایش را برای ما به ارمغان خواهد آورد. پس از بدست آوردن این نمایش فشرده، روش سریعی برای انتقال میانگین پیشنهاد نموده و نشان می‌دهیم که پیچیدگی آن از پیچیدگی مربوط به روش انتقال میانگین استاندارد بسیار کمتر می‌باشد. سپس گونه‌ای معتدل از خوشه‌بندی این الگوریتم را مورد بررسی قرار داده و بحث خود را با انتخاب بهینه پهنای باند به اتمام می‌رسانیم.
2.1. مروری بر روش انتقال میانگین
در این بخش، روش انتقال میانگین عادی را مورد بررسی قرار می‌دهیم. به صورت خلاصه، این کار را با تعریف برآورد چگالی کرنل (KDE) آغاز می‌نماییم. داده‌های در دسترس ما، مجموعه‌ای از نقاط {x_i }_(i=1)^n هستند که گاهی اوقات به آنها بردارهای ویژگی اتلاق شده و در فضای اقلیدسی موجودیت دارند: x_i∈R^d. در کاربردهای بینایی کامپیوتری، معمولاً یک چنین برداری به ازای هر پیکسل (یا وکسل در حالت سه بعدی) وجود دارد؛ این احتمال وجود دارد که این بردار رنگ، رنگی که موقعیت به آن اضافه شده است، بافت و غیره باشد.
آزمون های قطعه بندی
قطعه بندی تصویر
در آزمون قطعه‌بندی تصویر، عملکرد روش انتقال میانگین سریع پیشنهادی را با روش انتقال میانگین استاندارد در مورد سه تصویر با هم مقایسه می‌کنیم. بردارهای ویژگی 5 بعدی در نظر گرفته شده و از سه بردار رنگ Lab پیکسل‌های منفرد در تصویر و دو مختصه فضایی مربوطه ساخته شده‌اند. در جدول 1، اطلاعات مربوط به زمان‌بندی و خود تصاویر در شکل 1 نشان داده شده‌اند. در هر مثال، ضریب نمونه‌برداری برابر گذاشته شده است. تحلیل پیچیدگی انجام شده ما نشان می دهد که باید انتظار داشتن ضریب تسریعی در حدود 1024 را داشته باشیم؛ در حقیقت علی‌رغم استفاده از جستجوهای سریع نزدیک ترین همسایه‌ها (براساس درخت kd که علی‌رغم بحث های موجود در خصوص آن، در ابعاد پایین به خوبی عمل می‌نماید)، ضریب تسریعی در دو حالت از سه حالت موجود از این ضریب نمونه‌برداری تجاوز می‌نماید که در جدول 1 نشان داده شده است.
کاربردها: سلسله مراتب گراف
در این بخش، نحوه استفاده از الگوریتم انتقال میانگین سریع جهت ایجاد سلسه مرتبه گراف‌های متناظر با یک تصویر خاص نشان داده شده است. به دلیل درگیر بودن با تعدادی از مسائل بینایی رایانه‌ای همچون مسائل گراف و حل آنها با استفاده از الگوریتم‌های گرافی همچون برش‌های گراف [15]، داشتن ساختار چندمقیاسی در گراف‌های تصویر می‌تواند بسیار سودمند باشد. مثال‌هایی از این مسائل عبارتند از استریو، قطعه‌بندی نیمه‌خودکار و جریان اپتیکی و همچنین مسائل متعددی که به صورت بیشینه برآورد استقرایی بر روی میدان‌های تصادفی مارکوف با آنها مواجه هستیم. برای کمک به فرایند تسریع راه‌حل در این مسائل در روش چندمقیاسی معمول می‌توان از سلسله مراتب گراف چندمقیاسی استفاده نمود: مسئله موردنظر نخست در مقیاس درشت‌تر و دانه‌ای حل شده است؛ سپس راه‌حل این مسئله برای شروع افزایش مقیاس بعدی مورد استفاده قرار گرفته است؛ و غیره. این روش علاوه بر افزایش سرعت راه‌حل می‌تواند به نمونه‌هایی با جواب‌های دقیق‌تر منتهی گردد. برای مشاهده مثال مربوط به گونه‌ای دیگر از سلسله مرتبه گراف که بر روش‌های چندشبکه‌ای جبری استوار است، به مرجع [1] مراجعه نمایید.
نتیجه گیری
براساس محاسبه KDE کوچک شده و با استفاده از روش نمونه‌برداری، نسخه سریعی از الگوریتم انتقال میانگین را ارائه نموده‌ایم. نزدیکی KDE کوچک شده به KDE اصلی و همچنین پیچیدگی فوق‌العاده الگوریتم انتقال میانگین سریع در مقایسه با انتقال میانگین استاندارد را به صورت نظری نشان داده‌ایم. سرعت الگوریتم را به صورت تجربی اثبات نموده و کاربردپذیری بالقوه آن در خوشه‌بندی مجموعه داده‌های بزرگ همچون ویدیو و در محاسبه ساختار داده‌های پیچیده‌ای همچون سلسله مرتبه گراف نشان داده شده را نشان داده‌ایم. امیدواریم که بتوان این الگوریتم را در کاربردهایی همچون قطعه‌بندی سریع مجموعه داده‌های بزرگ موجود همچون تصاویر پزشکی خیلی زود مورد استفاده قرار داد.
این مقاله در سال 2009 در نشریه آی تریپل ای و در کنفرانس بینایی کامپیوتری و تشخیص الگو، توسط آزمایشگاه هیولت پاکارد منتشر شده و در سایت ای ترجمه جهت دانلود ارائه شده است. در صورت نیاز به دانلود رایگان اصل مقاله انگلیسی و ترجمه آن می توانید به پست دانلود ترجمه مقاله انتقال میانگین سریع از طریق نمایش چگالی تراکم در سایت ای ترجمه مراجعه نمایید.
