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

We present an algorithm for clustering sets of detected interest points into groups that correspond to visually distinct structure. Through the use of a suitable colour and texture representation, our clustering method is able to identify keypoints that belong to separate objects or background regions. These clusters are then used to constrain the matching of keypoints over pairs of images, resulting in greatly improved matching under difficult conditions. We present a thorough evaluation of each component of the algorithm, and show its usefulness on difficult matching problems.

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

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

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

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

Introduction
The fundamental motivation behind the continued development of low-level perceptual grouping algorithms is the belief that a correct organization of the scene into meaningful regions or feature groups will lead to more efficient and reliable algorithms for object detection, tracking, and scene reconstruction. Existing algorithms, however, have limited success. Current state-of-the-art methods produce good results on simple scenes, but fail on more realistic ones.

In this paper, we present a clustering algorithm that enables standard keypoint matching techniques to recover useful matches under very challenging conditions. We show that through the use of a well designed representation of colour and texture, a spectral embedding on a set of arbitrarily distributed image samples yields a meaningful set of clusters that captures the structure of the scene, typically separating objects of interest from the background and from each other.When applied to image patches that correspond to the location of detected interest points, the resulting clusters provide strong constraints for typical interest point matching algorithms, resulting in a significant reduction in the number of false matches. This process is illustrated in Fig. 1

To support the case for our proposed method, each component of the algorithm is evaluated separately on images from the Berkeley Segmentation Database (BSD) [16]. We also present a clustering comparison with the normalized cuts method [22], a standard graph-based clustering algorithm that is closely related to spectral embedding. The evaluation brings additional insights about the nature of the problem of clustering keypoints by appearance, and provides solid evidence that the proposed framework is sound.

Having evaluated the performance of our algorithm on a standard image database, we demonstrate its usefulness for object detection and tracking on a series of difficult matching problems characterized by clutter, non-uniform illumination changes, and non-rigid transformations. It is shown that the clustering process leads to significantly better matches, allowing for the tracking of lightly texture objects in heavily cluttered backgrounds, matching under conditions of significant perspective and non-rigid deformations, and matching under non-uniform illumination changes.

گروه بندی ویژگی ها در محتوا
الگوریتمی که ما پیشنهاد می دهیم مربوط به کلاس گسترده تری از روش ها در دو زمینه بینایی رایانه است: سازماندهی ادراکی و تقسیم بندی تصویر. سازماندهی ادراکی (گروه بندی ادراکی) با مسئله کلی گروه بندی مجموعه ای از ویژگی های مشاهده شده در مجموعه های معنی دار سروکار دارد. این بر اساس مکتب روانشناسی گشتالت [25] است ، که به مطالعه چگونگی سازماندهی محرک بینایی توسط ناظران انسانی می پردازد.در بینایی رایانه ، گروه بندی ادراکی به مسئله اساسی استخراج کامل مرزها و سطوح از داده های پراکنده پرداخته است [10] ، [26]. از طرف دیگر ، تقسیم بندی تصویر مسئله تصمیم گیری در مورد اینکه کدام قسمتهای تصویر دارای ظاهر ثابت هستند را مورد بررسی قرار داده است. در حالی که این یک رشته جداگانه در دید رایانه در نظر گرفته می شود ، می توان تقسیم بندی تصویر را یک مورد خاص از گروه بندی ادراکی دانست ، یعنی گروه بندی پیکسل ها یا پچ های تصویر با توجه به شباهت ظاهری آنها.

عملکرد روشهای در هر دو زمینه طی سالها بهبود یافته است. الگوریتم های موجود از توصیفگرهای های ظاهر پیچیده و روش های بهینه سازی و استنتاج قدرتمند استفاده می کنند (برای نام بردن از چندین [22] ، [7] و [19] را ببینید). با این حال ، الگوریتم های فعلی هنوز توانایی در برخورد با تصاویر طبیعی معمولی را ندارند که اشیا ناهمگن یا بافت را در برابر زمینه های پیچیده به تصویر می کشد ، محدود هستند.این محدودیت ها توضیح می دهد که چرا خارج از مسائل تصویربرداری پزشکی ، روش های گروه بندی و تقسیم بندی تعداد کمی کاربرد مستقیم پیدا کرده اند. مسلماً این امر وجود دارد که پیچیدگی فزاینده الگوریتم های ردیابی و شناسایی شی تا حدی به دلیل محدودیت های در روش های سطح پایین موجود ایجاد می شود.

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

چارچوبی که ما در اینجا پیشنهاد می دهیم مربوط به الگوریتم های خوشه بندی طیفی ، مانند برش های نرمال شده [22] و بسیاری از پیشرفت های آن است. به روشهای موجود که از ویژگیهای حالت پایدار تصادفی بهره می برند [9]. و کارهای قبلی در مورد ترکیب نشانه [15] همراه با کارهای اخیر در اندازه گیری های تشابه بافت [23]. ما همچنین کارهای مرتبط را در روش خوشه بندی ارائه شده در [8] برای گروه بندی ویژگی ها و استخراج مرزها پیدا می کنیم ، و در چارچوب های مبتنی بر پچ اخیر برای تصویر نمایانگر نمایش [11] ، [12]. اگرچه این یک لیست جامع نیست ، اما بررسی های دقیق تقسیم بندی تصویر و گروه بندی ادراکی از [2] در دسترس است.سرانجام ، یادآور می شویم که در حالی که گروه بندی نقاط کلیدی از نظر ظاهری قبلاً به درستی بررسی نشده است ، مسئله معکوس (یعنی استفاده از تشخیص اشیا مبتنی بر نقطه کلید برای بهبود نتایج تقسیم بندی) موضوع تلاش های تحقیقاتی اخیر است [27].

Feature grouping in context
The algorithm we propose is related to a wider class of methods in two fields of computer vision: perceptual organization and image segmentation. Perceptual organization (perceptual grouping) deals with the general problem of grouping a set of observed features into meaningful sets. It is based on the Gestalt school of psychology [25], which studies how human observers organize visual stimuli.In computer vision, perceptual grouping has addressed the fundamental problem of extracting complete boundaries and surfaces from fragmented data [10], [26]. Image segmentation, on the other hand, has explored the problem of deciding which parts of the image have a consistent appearance. While it is often considered a separate field within computer vision, one could think of image segmentation as a special case of perceptual grouping, namely, that of grouping pixels or image patches according to their similarity of appearance.

The performance of state-of-the-art methods in both fields has improved over the years. Existing algorithms use complex appearance descriptors and powerful optimization and inference procedures (see [22], [7], and [19] to name just a few). However, current algorithms are still limited in their ability to deal with typical natural images depicting heterogeneous or textured objects against complex backgrounds. These limitations explain why, outside of medical imaging problems, grouping and segmentation methods have found few direct applications. It is arguably the case that the increasing complexity of object recognition and tracking algorithms arises in part because of the limitations of existing low-level vision methods.

Instead of focusing on the segmentation problem of extracting accurate object boundaries, we look at the grouping of a much smaller set of features: The keypoints detected on a given image. This has two principal advantages, first, it makes the clustering task simpler and less computationally demanding. Secondly, the clustering does not have to be exceedingly accurate in order to be useful. As long as the clustering method manages to reject most background clutter for a given object, standard robust matching techniques such as RANSAC will recover a useful match.

The framework we propose here is related to spectral clustering algorithms, such as normalized cuts [22] and its many extensions; to existing methods that take advantage of the steady-state properties of random walks [9]; and to previous work on cue combination [15] together with recent work in texture similarity measures [23]. We also find related work in the clustering method proposed in [8] for feature grouping and boundary extraction, and in recent patch-based frameworks for image represent arepresentation [11], [12]. While this is not an exhaustive list, thorough reviews of image segmentation and perceptual grouping are available from [2].Finally, we note that while the grouping of keypoints by appearance has not been properly studied before, the reverse problem (namely, the use of keypoint based object detection to improve segmentation results) is the topic of recent research efforts [27].

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

برای بقیه مقاله ما از علامت گذاری زیر استفاده می کنیم: I یک تصویر رنگی ورودی است ، P مجموعه ای ازپچ های محلی تصویر استخراج شده از I است ، ~ pi پچ ایم در P است که با مختصات تصویر (xi ، yi) همراه است. پچ شامل مقادیر پیکسل برای یک منطقه مربع با عرض مشخص شده به مرکزیت (xi ، yi) روی تصویر I است. ما فرض می کنیم که پچ ها با استفاده از یک آشکارسازنقاط کلیدی استاندارد مانند SIFT [13] شناسایی شده اند ، اما توجه داریم که الگوریتم به یک آشکارساز خاص بستگی ندارد. در واقع ، به تکه های مربعی نیز نیاز ندارد. پچ های نمونه برداری شده با شکل دلخواه شکل، به عنوان مثال از superpixels می توانند بدون تغییر در الگوریتم شرح داده شده در زیر نیز استفاده شوند. برای بررسی و ارزیابی گسترده از آشکارسازهای نقطه کلیدی ، لطفاً به [18] مراجعه کنید.

Representing Local Appearance
A critical component of any clustering method is the similarity measure that will govern the behaviour of the algorithm and the quality of the clusters. Even a good clustering algorithm working on weak similarity information can be expected to produce poor results. This section describes the colour and texture representation for local image patches, the similarity measure that provides suitable information for the clustering algorithm, and an evaluation of the proposed measure on test images from the BSD.An important observation derived from the evaluation is that the problem of grouping keypoint patches is in general harder than that of grouping pixels or uniformly distributed image patches.

For the rest of the paper we use the following notation: I is an input colour image, P is the set of local image patches extracted from I, ~pi is the ith patch in P associated with image coordinates (xi, yi). The patch contains the pixel values for a square region of a specified width centered at (xi, yi) on image I. We assume that the patches have been detected through the use of a standard keypoint detector such as SIFT [13], but we note that the algorithm does not depend on a specific detector. In fact, it does not require square patches either. Arbitrarily shaped and sampled patches derived, for example, from superpixels could be used as well without modifications to the algorithm described below. For an extensive review and evaluation of keypoint detectors please see [18].

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

ما از هیستوگرام های رنگی استاندارد برای نشان دادن ظاهر رنگ یک پچ تصویر محلی استفاده می کنیم. هیستوگرامها از این مزیت برخوردارند که آسان تولید می شوند و معیارهای شباهت آن به خوبی مطالعه شده اند برای سادگی ، ما از فضای رنگی RGB استفاده می کنیم ، اما توجه داریم که روش مشابه را می توان در هر فضای رنگی مناسب استفاده کرد و می توان آن را به راحتی به تجزیه و تحلیل تصاویر چند طیفی گسترش داد. ما هیستوگرام رنگ را برای یک پچ ~ pi به عنوان ~Hi نشان می دهیم.این هیستوگرام با محاسبه هیستوگرامهای 1 بعدی برای هر کانال رنگی موجود در patch ~ pi و سپس اتصال هیستوگرامهای جداگانه برای هر کانال رنگی در یک بردار منفرد ساخته می شود. اندازه وصله و تعداد سطرهای موجود در هیستوگرام پارامترهای الگوریتم هستند.برای نشان دادن بافت تصویر ، ما از توصیفگر بافتی که اخیراً پیشنهاد شده است و بر اساس ماتریس کوواریانس مشتقات تصویر در مقیاس خاص استفاده می کنیم ، [23]. این فرمول با رویکردهای قبلی فیلتر بانک ، مانند [24] ، مطابقت دارد. از همه مهمتر ، نشان داده شده است که عملکرد خوبی برای طبقه بندی اشیا ارائه می دهد. توصیفگر بافت Ci با ماتریس کوواریانس ارتباط دارد.

بردار مشتقات اول و دوم تصویر برای برخی از پیکسل های j ~ ~ pi است که با استفاده از تقریب های استاندارد اختلاف محدود محاسبه می شود ، ¯ ~ v بردار متوسط بیش از پچ است و N تعداد پیکسل های ~ pi است. در حالی که این معیار قبلاً برای تطبیق اشیا با تصویر کامل و برای تمایز بافت مورد استفاده قرار گرفته است ، اما طبق دانش ما ، در الگوریتم های طبقه بندی تصویری چندصفی موجود گنجانده نشده است.

The appearance representation we describe here was chosen for its simplicity and compactness. It does not require convolution of the image with large filter banks, nor the additional step of computing a suitable number of texton channels. Despite its simple form, we will show at the end of this section that it provides results that are competitive with regard to current (significantly more complex) state of-the-art approaches.

We use standard colour histograms to represent the colour appearance of a local image patch. Histograms have the advantage of being easy to generate and having well studied similarity measures [21]. For simplicity, we use the RGB colourspace, but we note that the same procedure can be used in any suitable colourspace and can be easily extended to the analysis of multi-spectral imagery. We denote the colour histogram for a patch ~pi as ~Hi.This histogram is formed by computing 1-dimensional histograms for each available colour channel in patch ~pi, and then concatenating the individual histograms for each colour channel into a single vector. The size of the patch and the number of bins in the histogram are parameters of the algorithm.To represent image texture, we use a recently proposed texture descriptor based on covariance matrices of image derivatives at a specific scale [23]. This formulation compares favourably to current state-of-the-art filter bank approaches, such as [24]; more importantly, it has been shown to provide good performance for object categorization. The texture descriptor Ci corresponds to the covariance matrix

is the vector of first and second image derivatives for some pixel j ∈ ~pi computed using standard finite difference approximations,¯~v is the mean vector over the patch, and N is the number of pixels in ~pi. While this measure has been used for full-image object matching and for texture discrimination before, it has, to our knowledge, not been incorporated into existing multi-cue visual classification algorithms.