دانلود رایگان مقاله تشخیص لبه بر اساس الگوریتم تطبیق سریع انتقال میانگین

چکیده

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

1. مقدمه

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

            روش های متعددی برای تشخیص لبه وجود دارد، در بین آنها روش  انتقال میانگین یکی از رایج ترین روش ها برای تشخیص لبه می باشد. انتقال میانگین برآورد تراکم شیب را به صورت غیر پارامتری برای ما فراهم می کند. روش انتقال میانگین یک راه ظریف برای تعیین حداکثر تراکم بدون نیاز به تخمین تراکم به طور مستقیم را فراهم می کند.بردار انتقال میانگین همواره به جهتی اشاره می کند که تراکم در آن جهت به سمت حداکثر مقدار می رود. روند میانگین انتقال یک فرآیند تکرار شونده است که هر نقطه داده را به حداکثر تراکم سوق می دهد. در [2]، برای یافتن شی ای که به عنوان نامزد مطرح شود شبیه ترین شکل نسبت به مدل داده شده می باشد در حالیکه محل شی بعدی را نیز باید تعیین کنیم. این روش برای ما دقت در تعیین محل را فراهم می کند، همچنین محاسبات آن نیز سریع می باشد.هر چند که ، محدودیت این روش مبتنی بر انتقال میانگین این است که دارای مقیاس پذیر خوبی با ابعاد فضا نیست.اینطور نشان داده شده است که زمانی که ابعاد بیشتر از 6 می باشد، روش تجزیه و تحلیل باید به دقت انتخاب شود.[1]

             انتقال میانگین یک تخمین گر برای تراکم غیر پارامتری می باشد که تکرار محاسبات را با توجه به نزدیک ترین حالت یک نمونه توزیع شده انجام می دهد.پس از اینکه ادبیات آن را معرفی کردیم [3]،برای حل مشکلات مختلف کامپیوتری از روش هایی مثل اتصالات خطی [4]، تقسیم بندی[5]  و ردیابی شی [6]استفاده شده است.با وجود تضمینی که برای عملکرد آن در مقالات مختلفی مثل [7] ، [8] ، [9] داده شده است روش انتقال میانگین دارای دو محدودیت اصلی است ، که محدودیت اول ثبات در پهنای باند کرنل(هسته) می باشد.تغییر در مقیاس شی نیاز به تنظیم پهنای باند به منظور پیگری مداوم شی را دارد.یک رویکرد بصری برای تخمین مقیاس شی جست و جو برای بهترین مقیاس با آزمایش پهناهای مختلفی از کرنل(هسته)  و انتخاب پهنای باندی است که دارای حذاکثر میزان شباهت ظاهری باشد[6].در روشی دیگر این است که، پس از اینکه مرکز جسم تخمین زده شد،روند انتقال میانگین برای محاسبه پهنای باند کرنل(هسته)  را در این مقیاس از فضااعمال می کنیم،که سبب  شکل دهی ترکیب تصاویر با یک مجموعه از کرنل(هسته)  های گوسی در مقیاس های مختلفی می شود[8].

              دومین محدودیت از روش انتقال میانگین سنتی، استفاده رادیکالی از کرنل(هسته)  های متقارن است که سبب همگرا شدن شکل از هر سو می شود.از نظر اکثر ساختارهای غیرهمسانگرد از جسم، استفاده رادیکالی از کرنل (هسته) های متقارن برای تقسیم بندی تصاویر مشکل [9] و ردیابی شی لازم است.برای مثال ، برای نشان دادن یک شی از درازا که دارای یک کرنل (هسته) دایره ای شکل می باشد تخمین موقعیت ان با توجه به مناطق فارغ از شی در داخل کرنل (هسته) انجام می شود. این شی می تواند برای نمایش بهتر توسط یک کرنل(هسته)ناهمسانگرد متقارن ، مانند بیضی نشان داده شود.مقیاس و جهت گیری یک هسته نمایشگر یک شی می باشد که می توان آن را با ارزیابی لحظات مرتبه دوم از نیمرخ شی [10]  یا احتمالات ظاهر عقب آن بدست آورد[11].هر دوی این روش ها ،با این حال ، از لحاظ محاسباتی در مقایسه با روش ردیابی انتقال میانگین گران تر است.نتایج مشاهده در قسمت معرفی کرنل(هسته)  های ناهمسانگرد متقارن برای تجزیه و تحلیل انتقال میانگین مورد بررسی قرار گرفته است.بدین منظور،وانگ و همکارانش [9] عملکرد بهبود یافته ای از تقسیم بندی انتقال میانگین را برای زمانی که یک هسته دایره ای شکل با یک هسته بیضوی جایگزین می شود را ارائه کرده اند.در روش آنها، که در مقابل تجزیه و تحلی داده های محلی توزیع شده است،نویسنده ها جهت و مقیاسی از هسته بیضوی را از تصاویر تخمین زده اند.

             در این مقاله، ما روش انتقال میانگین سنتی را گسترش دادیم و روشی را با نام جست و جوی تقریبی نزدیک ترین همسایه را معرفی کردیم ، به عنوان مثال LSH (هش کردن محس های حساس)[12].ما نزدیک ترین همسایه ها را برای هر پیکسل توسط روش جست و جوی تقریبی همسایه بدست می آوریم،LSH.سپس،ما نتایج را به عنوان محدوده ای از تکرار ها در نظر می گیریم برای مثال پهنای باند است.پیکسل هایی که سبب ترویج همگرایی تکرارها نمی شوند را حذف می کنیم،که به طور چشمگیری سبب کاهش زمان مصرف شده برای تکرار همگرایی می شود.به همین دلیل ابتدا از روش جست و جوی تقریبی برای نزدیک ترین همسایه ها استفاده می کنیم مانند روش LSH ، که به طور چشمگیری سبب کاهش محاسبات تکراری به خصوص در ابعاد بالا می شود. علاوه بر آن، روش LSH می تواند برای تعیین پهنای باند پنجره کرنل به طور انطباقی به ما کمک کند.

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

Abstract

           Edge detection is arguably the most important operation in low level computer vision. Mean shift is an effective iterative algorithm widely used in edge detection. But the cost of computation prohibits Mean shift algorithm for high dimensions feature space. In this paper, a fast adaptive mean shift algorithm is proposed for edge detection. It makes use of one approximate nearest neighbors search method, i.e. LSH (Locality-Sensitive Hashing) firstly, which dramatically reduces the computation of iterations in high dimensions. Moreover, the LSH procedure can help to determine the bandwidth of the kernel window adaptively. The experimental results show the effectiveness of the proposed approach.

1. Introduction

            Edge detection is arguably the most important operation in low level computer vision with a plethora of techniques. An edge is the boundary between an object and its background (the outline of the object). Edge detection must be efficient and reliable because the validity, efficiency, and possibility of the completion of subsequent processing stages (in computer vision for example) rely on it. This means that if the edges in an image can be identified accurately, objects in the image can be located and basic properties such as area, perimeter, and shape can be measured. A fundamental difficulty in edge detection processes is the possible extraction of spurious edges that arise from noise and minor intensity changes which are often non-meaningful and disturbing, and may subsequent processing stages degrade computational performance. Thus, a proper selection of the edges may be very important.

            Numerous approaches have been dedicated for edge detection, among which the mean shift method is one of the most common methods. Mean-shift is a nonparametric density gradient estimator. The mean shift method presents an elegant way to locate these density maxima without having to estimate the density directly [1]. The mean shift vector always points to the direction of maximum increase in the density. The mean shift process is an iterative procedure that shifts each data point to these density maxima. In [2], it is employed to derive the object candidate that is the most similar to a given model while predicting the next object location. This method provides accurate localization, and it is computationally fast. However, the limitation of the approach based on mean shift is that it does not scale well with the dimension of the space. It was indicated that when the dimensionality is above 6, the analysis should be approached carefully [1].

            Mean shift is a nonparametric density estimator which iteratively computes the nearest mode of a sample distribution. After its introduction in the literature [3], it has been adopted to solve various computer vision problems, such as line fitting [4], segmentation [5] and object tracking [6]. Despite its promising performance, as discussed in various papers [7], [8]and [9], the traditional mean shift method has two main limitations, the first of which is the constancy of the kernel bandwidth. The change in the object scale requires an adjustment of the kernel bandwidth in order to consistently track the object. An intuitive approach to estimate the object scale is to search for the best scale by testing different kernel bandwidths and selecting the bandwidth which maximizes the appearance similarity [6]. Alternatively, after the object center is estimated, a mean shift procedure can compute the bandwidth of the kernel in the scale space, which is formed by convolving the image with a set of Gaussian kernels at various scales [8].

           The second limitation of the traditional mean shift method is the use of radically symmetric kernels which are isotropic in shape. In the view of often anisotropic structure of the object, radically symmetric kernels inhibit robust image segmentation [9] and object tracking. For example, representing an elongated object with a circular kernel will bias the position estimation due to the non-object regions residing inside the kernel. This object can be better represented by an anisotropic symmetric kernel, such as an ellipse. The scale and orientation of a kernel representing an object can be computed by evaluating the second order moments from the object silhouette [10] or the posterior appearance probabilities [11]. Both of these methods, however, are computationally expensive compared to the mean shift tracking method. This observation resulted in the introduction of anisotropic symmetric kernels to the mean shift analysis. In particular, Wang et al. [9] has shown the improved performance of the mean shift segmentation when a circular kernel is replaced with an elliptical kernel. In their approach, in contrast to analyzing the local data distribution, the authors estimated the orientation and the scale of the elliptical kernel from images.

           In this paper, we extend the traditional mean shift method by introducing an approximate nearest neighbor searching algorithm, i.e. LSH (LocalitySensitive Hashing) [12]. We get the nearest neighbors for each pixel by an approximate neighbor search method, LSH. Then, we store the results and take it as the range of iteration, i.e. bandwidth. The pixels that do not promote the convergence of iteration are removed, which dramatically decreases the time cost for convergence of iteration. It makes use of one approximate nearest neighbors search method, i.e. LSH (Locality-Sensitive Hashing) firstly, which dramatically reduces the computation of iterations in high dimensions. Moreover, the LSH procedure can help to determine the bandwidth of the kernel window adaptively.

            In the rest of this paper: Section 2 discusses the related works about the edge detection. In Section 3, our proposed approach that LSH-based mean shift algorithm is described. In Section 4, the experiments are done. Finally, we present our conclusion and future works.

چکیده
1. مقدمه
2.کارهای مرتبط
3. الگوریتم تشخیص لبه پیشنهاد شده
3.1. تخمین تراکم هسته و انتقال میانگین
3.2. الگوریتم LSH
3.3. LSH مبتنی بر الگوریتم انتقال میانگین
4. آزمایش ها
5. نتیجه گیری ها
منابع

Abstract
1. Introduction
2. Related works
3. The Proposed Edge Detection Algorithm
3.1. Kernel density estimation and mean shift
3.2. LSH algorithm
3.3. LSH-based Mean Shift algorithm
4. Experiments
5. Conclusions
References