دانلود رایگان مقاله انتقال میانگین سریع از طریق نمایش چگالی تراکم

چکیده

           روش انتقال میانگین یکی از روش‌های خوشه‌بندی ثابت شده‌ای است که به صورت گسترده در کاربردهای تصویربرداری همچون قطعه‌بندی تصویر و ویدیو، نویززدایی، مسیریابی اشیاء، طبقه‌بندی بافت و غیره مورد استفاده قرار گرفته است. با این وجود روش انتقال میانگین دارای پیچیدگی زمانی نسبتاً بالایی است که در بسیاری از نقاط داده‌ای، ابرخطی می‌باشد. در این مقاله، روش انتقال میانگین سریع جدیدی ارائه می‌نماییم که بر نمونه‌برداری تصادفی برآورد چگالی کرنل (KDE) مبتنی می‌باشد. به صورت تئوری نشان می‌دهیم که KDE کاهش یافته حاصل، به KDE داده‌های کامل با دقت معینی نزدیک می‌باشد. به‌علاوه ثابت می‌کنیم که پیچیدگی زمانی روش انتقال میانگین سریع پیشنهادی نسبت به پیچیدگی زمانی روش انتقال میانگین اصلی به میزان بسیار قابل ملاحظه‌ای پایین‌تر می‌باشد؛ بهره نوعی برای مجموعه داده‌های بزرگ، چندین مرتبه می‌باشد. آزمایش‌های انجام شده نشان می‌دهند که نتایج قطعه‌بندی تصویر و ویدیو روش انتقال میانگین سریع پیشنهادی با نتایج قطعه‌بندی تصویر و ویدیو مبتنی بر رئش انتقال میانگین استاندارد مشابه می‌باشد. همچنین کاربرد جدید روش انتقال میانگین سریع برای ساخت موثر سلسله‌مراتب گرافی برای تصاویر را نیز ارائه می‌نماییم؛ ساختار حاصل برای حل مسائل بینایی کامپیوتر که می‌توان آنها را همانند مسائل گراف شامل استریو، قطعه‌بندی نیمه‌خودکار و شار اپتیکی مطرح نمود بسیار سودمند می‌باشند.

1. مقدمه

            برآورد چگالی کرنل و روش خوشه‌بندی انتقال میانگین از روش‌های بسیار مقبول در زمینه بینایی رایانه‌ای می‌باشند، به عنوان مثال منابع [10، 5] و مراجع ذکر شده در آنها را ملاحظه نمایید. از روش انتقال میانگین به صورت گسترده در کاربردهای تصویربرداری همچون قطعه‌بندی تصویر و ویدیو [5، 20]، نویززدایی [3]، مسیریابی اشیاء [7] و طبقه‌بندی بافت [11] و غیره استفاده شده است. به طور کلی روش انتقال میانگین از دو مرحله تشکیل شده است: (الف) ساخت چگالی احتمالی که توزیع نقاط مربوطه را در برخی از جاهای فضای ویژگی منعکس می‌نماید و (ب) نگاشت هر نقطه در مد (بیشینه) چگالی که به آن نزدیک می‌باشد.

            یکی از مشکلات اصلی در بکارگیری روش انتقال میانگین مبتنی بر خوشه‌بندی در مجموعه داده‌های بزرگ، پیچیدگی محاسباتی آن است که در تعدادی از نقاط داده‌ای، ابرخطی می‌باشد. روش‌های در دسترس مختلفی برای افزایش سرعت روش انتقال مانگین وجود دارند. دمنتون و مگرت [8] از یک روش متوالی، مقیاس فضامانند در انتقال میانگین با افزایش پهنای باند استفاده کرده‌اند. یانگ و همکارانش [23] برای افزایش سرعت کلی در توالی انتقال میانگین، از تبدیل گاوسی سریع بهره برده‌اند. گائو و همکارانش [13]، مجموع انتقال میانگین را به تعدادی از زیرمجموعه‌های موضعی تفکیک نموده‌اند. پاریس و دوراند [17] از تفکیک‌پذیری کرنل گاوسی چندبعدی برای اجرای d حلقه یک بعدی جداگانه استفاده نموده‌اند. وانگ و همکارانش [21] از ساختار داده زیرکی، درخت دوتایی، جهت افزایش سرعت انتقال میانگین استفاده کرده‌اند. همچنین مقاله ویوالدی و سواتو در مورد ”انتقال سریع“ [19] نیز در حدی به این مقوله مربوط می‌باشد.

            در این مقاله روش جدیدی را معرفی نموده‌ایم که در آن مستقیماً با تشریح یا پیچیدگی فضای برآورد چگالی کرنل مواجه می‌باشیم که در تعدادی از نقاط داده‌ای خطی می‌باشند. تمرکز اصلی این مقاله بر روی روش انتقال میانگین سریع جدیدی است که بر محاسبه برآورد چگالی کوچک شده کرنل با استفاده از روش‌های نمونه‌برداری مبتنی می‌باشد. به صورت نظری نشان می‌دهیم که KDE کاهش یافته، به KDE داده‌های کامل با دقت موردنظر نزدیک می‌باشد. پیچیدگی زمانی روش انتقال میانگین سریع پیشنهادی مبتنی بر KDE کاهش یافته، به میزان قابل توجهی از پیچیدگی زمانی روش انتقال میانگین اصلی کمتر می‌باشد؛ مقدار بهره نوعی در مورد مجموعه داده‌های بزرگ، چند برابر است. در تعدادی از آزمایش‌های انجام شده در خصوص قطعه‌بندی، وجود این بهره بزرگ را به صورت تجربی اثبات می‌نماییم.

           روش انجام فرایند ساخت KDE ارائه شده متراکم‌تر، ساده می‌باشد؛ به‌علاوه، روش جدید بر روش‌های موجود برای افزایش انتقال میانگین متعامد بوده و در اکثر حالات می‌توان آن را همراستا با این روش‌های قدیمی‌تر برای عملکرد بسیار بهتر به اجرا درآورد. شایان ذکر است با اینکه پژوهش‌های متعددی در خصوص (نمایش KDE متراکم) در گذشته انجام پذیرفته‌اند اما این پژوهش‌ها شدیداً بر روش‌های مبتنی بر شبکه‌های عصبی و نگاشت‌های خودآرا استوار هستند [18، 22، 12]. شبکه‌های عصبی به پیچیدگی اجرایی بالایی (همچنین مسائل دیگر) منجر می‌گردند که در این پژوهش تلاش نموده‌ایم از آن اجتناب نماییم.

          بقیه قسمت‌های این مقاله به صورت زیر سازمان یافته‌اند. در بخش 2، در ابتدا به صورت خلاصه چارچوب KDE و الگوریتم انتقال میانگین برای یافتن مد موردنظر را مورد بررسی قرار داده‌ایم. سپس روش نمونه‌برداری برای ایجاد نمایشی متراکم‌تر از KDE ارائه نموده‌ایم. سپس براساس این KDE متراکم، روش انتقال میانگین سریع خود را تعریف و پیچیدگی محاسباتی آن را در مقایسه با انتقال میانگین استاندارد مورد تحلیل قرار داده‌ایم. همچنین قانونی بری انتخاب پهنای باند بهینه برای روش انتقال میانگین سریع ارائه نموده‌ایم. در بخش 3، عملکرد روش پیشنهادی در کارهای قطعه‌بندی تصویر و ویدیو را نشان داده و نتایج آن را با روش انتقال میانگین استاندارد مقایسه کرده‌ایم. در بخش 4، کاربرد نوین روش انتقال میانگین سریع برای ایجاد سلسه‌مراتب گراف چندمقیاسی برای تصاویر را ارائه نموده‌ایم. بخش 5 نیز به نتیجه‌گیری اختصاص داده شده است.

2. انتقال میانگین سریع

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

2.1. مروری بر روش انتقال میانگین

            در این بخش، روش انتقال میانگین عادی را مورد بررسی قرار می‌دهیم. به صورت خلاصه، این کار را با تعریف برآورد چگالی کرنل (KDE) آغاز می‌نماییم. داده‌های در دسترس ما، مجموعه‌ای از نقاط {x_i }_(i=1)^n هستند که گاهی اوقات به آنها بردارهای ویژگی اتلاق شده و در فضای اقلیدسی موجودیت دارند: x_i∈R^d. در کاربردهای بینایی کامپیوتری، معمولاً یک چنین برداری به ازای هر پیکسل (یا وکسل در حالت سه بعدی) وجود دارد؛ این احتمال وجود دارد که این بردار رنگ، رنگی که موقعیت به آن اضافه شده است، بافت و غیره باشد. 

Abstract

           The Mean Shift procedure is a well established clustering technique that is widely used in imaging applications such as image and video segmentation, denoising, object tracking, texture classification, and others. However, the Mean Shift procedure has relatively high time complexity which is superlinear in the number of data points. In this paper we present a novel fast Mean Shift procedure which is based on the random sampling of the Kernel Density Estimate (KDE). We show theoretically that the resulting reduced KDE is close to the complete data KDE, to within a given accuracy. Moreover, we prove that the time complexity of the proposed fast Mean Shift procedure based on the reduced KDE is considerably lower than that of the original Mean Shift; the typical gain is of several orders for big data sets. Experiments show that image and video segmentation results of the proposed fast Mean Shift method are similar to those based on the standard Mean shift procedure. We also present a new application of the Fast Mean Shift method to the efficient construction of graph hierarchies for images; the resulting structure is potentially useful for solving computer vision problems which can be posed as graph problems, including stereo, semi-automatic segmentation, and optical flow.

1. Introduction

            Kernel density estimation and the Mean Shift clustering procedure are well accepted techniques in the field of computer vision, see for example [10, 5] and references therein. Mean Shift is widely used in many imaging applications such as image and video segmentation [5, 20], denoising [3], object tracking [7], and texture classification [11], inter alia. Roughly speaking, the Mean Shift procedure consists of two steps: (i) the construction of a probability density which reflects the underlying distribution of points in some feature space, and (ii) the mapping of each point to the mode (maximum) of the density which is closest to it.

            One of the main difficulties in applying Mean Shift based clustering to big data sets is its computational complexity which is superlinear in the number of data points. There are several existing techniques which have been developed to increase the speed of Mean Shift. DeMenthon and Megret [8] use an iterative, scale-space like approach to MeanShift, with increasing bandwidth. Yang et al. [23] use the Fast Gauss Transform to speed up the sum in the Mean Shift iteration. Guo et al. [13] decompose the Mean Shift sum into a number of local subsets. Paris and Durand [17] use the separability of the multidimensional Gaussian kernel to perform d separate one-dimensional convolutions. Wang et al. [21] use a clever data structure, the dual tree, to speed up Mean Shift. Also somewhat related is the paper by Vevaldi and Soatto on “Quick Shift” [19].

            In this paper, we introduce a new technique, which deals directly with the description or space complexity of the Kernel Density Estimate, which is linear in the number of data points. The main focus of this paper is a novel fast Mean Shift procedure which is based on the computation of a pared down Kernel Density Estimate, using sampling techniques. We show theoretically that the resulting reduced KDE is close to the complete data KDE, to within a given accuracy. The time complexity of the proposed fast Mean Shift procedure based on the reduced KDE is considerably lower than that of the original Mean Shift; the typical gain is of several orders for big data sets. We verify this large gain experimentally in a number of segmentation experiments.

            The method for constructing the more compactly represented KDE is easy to implement; furthermore, the new technique is orthogonal to the existing techniques for speeding up Mean Shift, and in most cases, can be implemented along side these older methods for even better performance. Note that while there has been some work in this regard (compact KDE representation) in the past, it mainly involves techniques which rely heavily on neural networks and self-organizing maps [18, 22, 12]. Neural networks lead to a high implementation complexity (as well as other issues) which we wish to avoid in this work.

           The remainder of the paper is organized as follows. In Section 2 we first briefly review the KDE framework and the Mean Shift algorithm for mode finding. Then we propose a sampling method for constructing the compact representation of KDE. Next, based on this compact KDE, we define our Fast Mean Shift procedure, and analyze its computational complexity as compared to the standard Mean Shift. We also provide a rule for optimal bandwidth selection for the Fast Mean Shift procedure. In Section 3, we demonstrate the performance of the proposed method on the tasks of image and video segmentation, and compare results with standard Mean Shift. In Section 4, we present a new application of the Fast Mean Shift method for constructing multiscale graph hierarchies for images. Section 5 concludes.

2. Fast Mean Shift

          In this section, we present the Fast Mean Shift algorithm. After a brief review of the standard Mean Shift algorithm, we move to a general discussion of compact representations for the kernel density estimate, and prove that a samplingbased scheme gives us such a representation. Given this compact representation, we then propose a fast technique for Mean Shift, and show that its complexity is considerably lower than that of the standard Mean Shift. We then examine a soft clustering variant of this algorithm, and conclude with a discussion of the optimal choice of bandwidth.

2.1. Review of Mean Shift

          In this section, we review the ordinary Mean Shift procedure. We begin by briefly defining the Kernel Density Estimate (KDE). Our data is a set of points {xi} n i=1, sometimes referred to as feature vectors, living in a Euclidean space: xi ∈ R d . In computer vision applications, there is generally one such vector per pixel (or voxel in the threedimensional case); the vector may be colour, colour augmented with position, texture, and so on.

چکیده
1. مقدمه
2. انتقال میانگین سریع
2.1. مروری بر روش انتقال میانگین
2. 2. KDE متراکم‌تر: مسئله
3. 2. KDE متراکم‌تر از طریق نمونه‌برداری
2.4. انتقال میانگین سریع
2.5. تحلیل پیچیدگی
2.6. متغیر: قطعه‌بندی نرم یا کارتون‌ها
2.7. پهنای باند بهینه
3. آزمون‌های قطعه‌بندی
3.1. قطعه‌بندی تصویر
 3.2. تغییر ضریب نمونه‌برداری n/m
3.3. قطعه‌بندی ویدیو
4. کاربردها: سلسله مراتب گراف
4.1. سلسله مرتبه گراف
4.2. مثال
5. نتیجه‌گیری
منابع 

Abstract
1. Introduction
2. Fast Mean Shift
2.1. Review of Mean Shift
2.2. A More Compact KDE: the Problem
2.3. A More Compact KDE via Sampling
2.4. Fast Mean Shift
2.5. Complexity Analysis
2.6. Variant: Soft Segmentation or Cartoons
2.7. The Optimal Bandwidth
3. Segmentation Experiments
3.1. Image Segmentation
3.2. Varying the Sampling Factor n/m
3.3. Video Segmentation
4. Application: Graph Hierarchies
4.1. A Graph Hierarchy
4.2. An Example
5. Conclusions
References