This paper presents a method for extracting distinctive invariant features from images that can be used to perform reliable matching between different views of an object or scene. The features are invariant to image scale and rotation, and are shown to provide robust matching across a a substantial range of affine distortion, change in 3D viewpoint, addition of noise, and change in illumination.The features are highly distinctive, in the sense that a single feature can be correctly matched with high probability against a large database of features from many images. This paper also describes an approach to using these features for object recognition.The recognition proceeds by matching individual features to a database of features from known objects using a fast nearest-neighbor algorithm, followed by a Hough transform to identify clusters belonging to a single object, and finally performing verification through least-squares solution for consistent pose parameters. This approach to recognition can robustly identify objects among clutter and occlusion while achieving near real-time performance

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

1 Introduction
Image matching is a fundamental aspect of many problems in computer vision, including object or scene recognition, solving for 3D structure from multiple images, stereo correspondence, and motion tracking. This paper describes image features that have many properties that make them suitable for matching differing images of an object or scene. The features are invariant to image scaling and rotation, and partially invariant to change in illumination and 3D camera viewpoint. They are well localized in both the spatial and frequency domains, reducing the probability of disruption by occlusion, clutter, or noise. Large numbers of features can be extracted from typical images with efficient algorithms. In addition, the features are highly distinctive, which allows a single feature to be correctly matched with high probability against a large database of features, providing a basis for object and scene recognition.The cost of extracting these features is minimized by taking a cascade filtering approach,in which the more expensive operations are applied only at locations that pass an initial test.

مقدمه (معرفی) مقاله الگوریتم sift

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

Following are the major stages of computation used to generate the set of image features

Scale-space extrema detection: The first stage of computation searches over all scales and image locations. It is implemented efficiently by using a difference-of-Gaussian function to identify potential interest points that are invariant to scale and orientation.

Keypoint localization: At each candidate location, a detailed model is fit to determine location and scale. Keypoints are selected based on measures of their stability.

Orientation assignment: One or more orientations are assigned to each keypoint location based on local image gradient directions. All future operations are performed on image data that has been transformed relative to the assigned orientation, scale, and location for each feature, thereby providing invariance to these transformations.

Keypoint descriptor: The local image gradients are measured at the selected scale in the region around each keypoint. These are transformed into a representation that allows for significant levels of local shape distortion and change in illumination.

در زیر مراحل اصلی محاسبه مورد استفاده برای تولید مجموعه ای از ویژگی های تصویر آورده شده است:

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

محلی سازی نقطه کلیدی: در هر مکان کاندید ، یک مدل دقیق برای تعیین مکان و مقیاس مناسب است. نقاط کلیدی بر اساس معیارهای پایداریشان انتخاب می شوند.

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

توصیفگر نقطه کلیدی : گرادیان های محلی تصویر در مقیاس انتخاب شده در منطقه اطراف هر نقطه کلیدی اندازه گیری می شوند. این موارد به نمایشی تبدیل می شوند که سطح قابل توجهی از تغییر شکل محلی و تغییر در نور را امکان پذیر می سازد.

This approach has been named the Scale Invariant Feature Transform (SIFT), as it transforms image data into scale-invariant coordinates relative to local features. An important aspect of this approach is that it generates large numbers of features that densely cover the image over the full range of scales and locations. A typical image of size 500×500 pixels will give rise to about 2000 stable features (although this number depends on both image content and choices for various parameters). The quantity of features is particularly important for object recognition, where the ability to detect small objects in cluttered backgrounds requires that at least 3 features be correctly matched from each object for reliable identification. For image matching and recognition, SIFT features are first extracted from a set of reference images and stored in a database. A new image is matched by individually comparing each feature from the new image to this previous database and finding candidate matching features based on Euclidean distance of their feature vectors. This paper will discuss fast nearest-neighbor algorithms that can perform this computation rapidly against large databases. …. The keypoint descriptors are highly distinctive, which allows a single feature to find its correct match with good probability in a large database of features. However, in a cluttered image, many features from the background will not have any correct match in the database, giving rise to many false matches in addition to the correct ones. The correct matches can b filtered from the full set of matches by identifying subsets of key points that agree on the object and its location, scale, and orientation in the new image. The probability that several features will agree on these parameters by chance is much lower than the probability that any individual feature match will be in error. The determination of these consistent clusters can be performed rapidly by using an efficient hash table implementation of the generalized Hough transform. Each cluster of 3 or more features that agree on an object and its pose is then subject to further detailed verification. First, a least-squared estimate is made for an affine approximation to the object pose. Any other image features consistent with this pose are identified, and outliers are discarded. Finally, a detailed computation is made of the probability that a particular set of features indicates the presence of an object, given the accuracy of fit and number of probable false matches. Object matches that pass all these tests can be identified as correct with high confidence

این روش به این دلیل که داده های تصویر را به مختصات غیر متغیر نسبت به مقیاس به ویژگی های محلی تبدیل می کند ، تبدیل ویژگی مستقل از مقیاس (SIFT) نامیده شده است. یک جنبه مهم این رویکرد این است که تعداد زیادی ویژگی ایجاد می کند که تصویر را در دامنه کامل مقیاس و مکان پوشش می دهد. یک تصویر معمولی با اندازه 500×500 پیکسل باعث ایجاد 2000 ویژگی پایدار می شود (اگرچه این تعداد به انتخاب پارامترهای مختلف و محتوای تصویر بستگی دارد). کمیت ویژگی ها به ویژه برای تشخیص شی مهم است ، جایی که توانایی تشخیص اشیا کوچک در زمینه های به هم ریخته ای نیاز دارد که حداقل 3 ویژگی به درستی از هر شی برای شناسایی قابل اعتماد تطبیق داده شود. برای تطبیق و شناسایی تصویر ، ویژگی های SIFT ابتدا از مجموعه ای از تصاویر مرجع استخراج شده و در پایگاه داده ذخیره می شوند. یک تصویر جدید منحصرانه با مقایسه هر ویژگی از این تصویر جدید با پایگاه داده قبلی و پیدا کردن ویژگی های کاندید تطبیق مبتنی بر فاصله اقلیدسی بردارهای ویژگی ,مطابقت داده می شود . در این مقاله الگوریتم های سریع, نزدیکترین همسایه که می توانند این محاسبات را به سرعت برای پایگاه های داده بزرگ انجام دهند ، مورد بحث قرار می گیرند.

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

Detection of scale-space extrema
As described in the introduction, we will detect key points using a cascade filtering approach that uses efficient algorithms to identify candidate locations that are then examined in further detail. The first stage of keypoint detection is to identify locations and scales that can be repeatably assigned under differing views of the same object. Detecting locations that are invariant to scale change of the image can be accomplished by searching for stable features across all possible scales, using a continuous function of scale known as scale space (Witkin,1983). It has been shown by Koenderink (1984) and Lindeberg (1994) that under a variety of reasonable assumptions the only possible scale-space kernel is the Gaussian function. Therefore, the scale space of an image is defined as a function, L(x, y, δ), that is produced from the convolution of a variable-scale Gaussian, G(x, y, δ), with an input image, I(x, y):

تشخیص اکسترمم فضای مقیاس
همانطور که در مقدمه توضیح داده شد ، ما با استفاده از رویکرد فیلتر کردن آبشاری که با استفاده از الگوریتم های کارآمد مکانهای کاندید را شناسایی می کند و سپس با جزئیات بیشتر بررسی می شوند ، نقاط کلیدی را تشخیص خواهیم داد. اولین مرحله از تشخیص نقاط کلیدی، شناسایی مکان ها و مقیاس هایی است که بتوانند تحت دیدهای متفاوت از همان شی قابل تکرار باشند. با جستجوی ویژگیهای پایدار در همه مقیاسهای ممکن ، با استفاده از یک تابع شناخته شده مقیاس که به عنوان فضای مقیاس شناخته می شود ، می توان مکانهایی را که برای تغییر مقیاس تصویر مقاوم هستند ، شناسایی کرد (Witkin، 1983).توسط كوندرینك (1984) و لیندبرگ (1994) نشان داده شده است كه تحت انواع فرضیات معقول تنها هسته فضای مقیاس ممكن تابع گوسی می باشد. بنابراین ، فضای مقیاس یک تصویر به عنوان تابعی تعریف می شود (L(x, y, δ که از کانولوشن فضای متغیر گوسی (G(x, y, δ با عکس وروی (I (x ، y تولید می شود

L(x, y, δ) = G(x, y, δ) ∗ I(x, y)

علامت ∗ برای کانولوشن استفاده شده و تابع گوسی به شرح زیر است :

To efficiently detect stable keypoint locations in scale space, we have proposed (Lowe, 1999) using scale-space extrema in the difference-of-Gaussian function convolved with the image, D(x, y, δ ), which can be computed from the difference of two nearby scales separated by a constant multiplicative factor k.. There are a number of reasons for choosing this function. First, it is a particularly efficient function to compute, as the smoothed images, L, need to be computed in any case for scale space feature description, and D can therefore be computed by simple image subtraction.

برای تشخیص کارآمد مکانهای پایدار نقاط کلیدی در فضای مقیاس ، ما پیشنهاد کرده ایم (Lowe، 1999) از اکسترمم های فضای مقیاس در تفاضل تابع گاوسی که با تصویر کانوالو شده است (D(x, y,δ که می تواند از اختلاف دو مقیاس مجاور با یک ضریب ثابت k محاسبه شود , استفاده شود .

D(x, y, δ ) = (G(x, y, kδ ) − G(x, y, δ )) ∗ I(x, y)
= L(x, y, k δ ) − L(x, y, δ )

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

In addition, the difference-of-Gaussian function provides a close approximation to the scale-normalized Laplacian of Gaussian, δ ^2 ∇ ^2 G, as studied by Lindeberg (1994). Lindeberg showed that the normalization of the Laplacian with the factor δ^2 is required for true scale invariance. In detailed experimental comparisons, Mikolajczyk (2002) found that the maxima and minima of δ ^2 ∇ ^2 G produce the most stable image features compared to a range of other possible image functions, such as the gradient, Hessian, or Harris corner function.The relationship between D and δ ^2 ∇ ^2 G can be understood from the heat diffusion equation (parameterized in terms of δ rather than the more usual t = δ ^2 ).

علاوه بر این ، تابع تفاضل گاوسی ,تقریب نزدیک به لاپلاسین نرمال مقیاس از گاوسین ، δ ^2 ∇ ^2 G ، همانطور که توسط (Lindeberg (1994 مطالعه شده است ، فراهم می کند. لیندبرگ نشان داد که نرمال کردن لاپلاسین با فاکتور δ ^2 برای عدم تغییر مقیاس واقعی مورد نیاز است. در مقایسه های آزمایشی دقیق ، (Mikolajczyk (2002 دریافت که حداکثر و حداقل δ ^2 ∇ ^2 G پایدارترین ویژگی های تصویر را در مقایسه با طیف وسیعی از توابع تصویر ممکن دیگر مانند عملکرد گوشه گرادیان ، هسیان یا هریس , ایجاد می کند. رابطه بین D و δ ^2 ∇ ^2 G را می توان از معادله انتشار گرما فهمید (پارامترها در این ترم δ بیشتر t= δ ^2 ):

This shows that when the difference-of-Gaussian function has scales differing by a constant factor it already incorporates the δ ^2 scale normalization required for the scale-invariant Laplacian

این نشان می دهد که وقتی تابع تفاضل گاوسی مقیاس هایی متنوع با یک فاکتور ثابت دارد ، در حال حاضر مقیاس δ ^2 نرمال سازی مورد نیاز برای مقیاس ثابت لاپلاسین را در بر می گیرد.

The factor (k − 1) in the equation is a constant over all scales and therefore does not influence extrema location. The approximation error will go to zero as k goes to 1, but in practice we have found that the approximation has almost no impact on the stability of extrema detection or localization for even significant differences in scale, such as k = √2. An efficient approach to construction of D(x, y, δ ) is shown in Figure 1. The initial image is incrementally convolved with Gaussians to produce images separated by a constant factor k in scale space, shown stacked in the left column. We choose to divide each octave of scale space (i.e., doubling of δ ) into an integer number, s, of intervals, so k = 2^1/s. We must produce s + 3 images in the stack of blurred images for each octave, so that final extrema detection covers a complete octave. Adjacent image scales are subtracted to produce the difference-of-Gaussian images shown on the right. Once a complete octave has been processed, we resample the Gaussian image that has twice the initial value of δ (it will be 2 images from the top of the stack) by taking every second pixel in each row and column. The accuracy of sampling relative to δ is no different than for the start of the previous octave, while computation is greatly reduced.

فاکتور (k – 1) در این معادله در تمام مقیاس ها ثابت است و بنابراین بر مکان اکسترمم تأثیر نمی گذارد. خطای تقریب با رفتن k به 1 به صفر می رسد ، اما در عمل متوجه شده ایم که تقریب تقریباً تاثیری بر پایداری تشخیص یا محلی سازی اکسترمم ها حتی برای تفاوت های چشمگیر در مقیاس مانند k = √2 ندارد. یک روش کارآمد برای ساخت D (x ، y ، δ ) در شکل 1 نشان داده شده است. تصویر اولیه به تدریج با گاوسین کانوالو می شود و تصاویر جدا شده با یک عامل ثابت k را در فضای مقیاس تولید می کند ، که در ستون سمت چپ انباشته شده است. ما انتخاب می کنیم که هر اکتاو از فضای مقیاس (یعنی دو برابر شدن δ ) را به یک عدد صحیح ، s ، از سطوح(تعداد لول) ، یعنی k = 2^1 / s تقسیم کنیم. ما باید 3+s تصویر را در پشته تصاویربلور شده برای هر اکتاو تولید کنیم ، بنابراین تشخیص آخرین اکسترمم یک اکتاو کامل را پوشش می دهد.مقیاس های تصویر مجاور برای تولید تصاویر اختلاف گاوسی که در سمت راست نشان داده شده است ، کم می شوند. هنگامی که یک اکتاو کامل پردازش شد ، با گرفتن هر پیکسل دوم در هر سطر و ستون ، تصویر گاوسی را که دو برابر مقدار اولیه دارد (2 تصویر از بالای پشته خواهد بود) نمونه برداری می کنیم. دقت نمونه برداری مربوط به δ نسبت به شروع اکتاو قبلی تفاوتی ندارد ، در حالی که محاسبات بسیار کاهش می یابد.

In order to detect the local maxima and minima of D(x, y, δ ), each sample point is compared to its eight neighbors in the current image and nine neighbors in the scale above and below (see Figure 2). It is selected only if it is larger than all of these neighbors or smaller than all of them. The cost of this check is reasonably low due to the fact that most sample points will be eliminated following the first few checks. An important issue is to determine the frequency of sampling in the image and scale domains that is needed to reliably detect the extrema. Unfortunately, it turns out that there is no minimum spacing of samples that will detect all extrema, as the extrema can be arbitrarily close together. This can be seen by considering a white circle on a black background, which will have a single scale space maximum where the circular positive central region of the difference-of-Gaussian function matches the size and location of the circle. For a very elongated ellipse, there will be two maxima near each end of the ellipse. As the locations of maxima are a continuous function of the image, for some ellipse with intermediate elongation there will be a transition from a single maximum to two, with the maxima arbitrarily close to each other near the transition. Therefore, we must settle for a solution that trades off efficiency with completeness.In fact,as might be expected and is confirmed by our experiments, extrema that are close together are quite unstable to small perturbations of the image. We can determine the best choices experimentally by studying a range of sampling frequencies and using those that provide the most reliable results under a realistic simulation of the matching task

تشخیص اکسترمم محلی

به منظور تشخیص حداکثر و حداقلهای محلی D(x, y, δ ) ، هر نقطه نمونه با هشت همسایه خود در تصویر فعلی و نه همسایه با مقیاس بالا و پایین مقایسه می شود (شکل 2 را ببینید). فقط در صورتی بزرگتر از همه همسایگان یا کوچکتر از همه انتخاب می شود. هزینه این چک به دلیل اینکه بسیاری از نقاط نمونه پس از چند بررسی اول حذف می شوند ، به طور منطقی کم می شود . یک مسئله مهم تعیین تکرار نمونه برداری در دامنه های تصویر و مقیاس است که برای شناسایی قابل اعتماد اکسترمم ها مورد نیاز است. متأسفانه ، معلوم می شود که حداقل فضایی از نمونه ها که تمام اکسترمم را تشخیص دهد ،وجود ندارد زیرا ممکن است اکسترمم ها به طور دلخواهانه(خودسرانه) به هم نزدیک شوند. این را می توان با در نظر گرفتن یک دایره سفید روی پس زمینه سیاه مشاهده کرد ، که یک فضای مقیاس واحد در صورتی ناحیه مرکزی مثبت دایره ای تابع تفاضل گاوسی با اندازه و محل دایره منطبق شود, حداکثر خواهد شد . برای یک بیضوی بسیار کشیده ، نزدیک به هر انتهای بیضی دو حداکثر وجود دارد. از آنجا که مکان های ماکزیمم تابعی پیوسته از تصویر است ، برای برخی از بیضی ها با کشیدگی متوسط ، یک انتقال از یک حداکثر به دو ، با حداکثر به طور دلخواه نزدیک به یکدیگر در نزدیکی انتقال, وجود خواهد داشت.بنابراین ، ما باید به راه حلی رضایت دهیم که تعادل را به طور موثر و کامل اجرا کند. در حقیقت ، همانطور که انتظار می رود و توسط آزمایش های ما تأیید شده است ، اکسترمم ها که به هم نزدیک هستند در برابر اغتشاشات کوچک تصویر کاملاً ناپایدار هستند. ما می توانیم با مطالعه طیف وسیعی از تکرار های نمونه برداری و استفاده از مواردی که قابل اطمینان ترین نتایج را در یک شبیه سازی واقعی از کار تطبیق می دهند ، بهترین انتخاب ها را به صورت آزمایشی تعیین کنیم.

The experimental determination of sampling frequency that maximizes extrema stability is shown in Figures 3 and 4. These figures (and most other simulations in this paper) are based on a matching task using a collection of 32 real images drawn from a diverse range, including outdoor scenes, human faces, aerial photographs, and industrial images (the image domain was found to have almost no influence on any of the results). Each image was then subject to a range of transformations, including rotation, scaling, affine stretch, change in brightness and contrast, and addition of image noise. Because the changes were synthetic, it was possible to precisely predict where each feature in an original image should appear in the transformed image, allowing for measurement of correct repeatability and positional accuracy for each feature. Figure 3 shows these simulation results used to examine the effect of varying the number of scales per octave at which the image function is sampled prior to extrema detection. In this case, each image was resampled following rotation by a random angle and scaling by a random amount between 0.2 of 0.9 times the original size. Keypoints from the reduced resolution image were matched against those from the original image so that the scales for all keypoints would be be present in the matched image. In addition, 1% image noise was added, meaning that each pixel had a random number added from the uniform interval [-0.01,0.01] where pixel values are in the range [0,1] (equivalent to providing slightly less than 6 bits of accuracy for image pixels).

تکرار نمونه برداری در فضای مقیاس

در شکل 3 و 4 تعیین تجربی تکرار نمونه برداری با حداکثر ثبات اکسترمم نشان داده شده است. این شکل ها (و بیشتر شبیه سازی های دیگر در این مقاله) بر اساس یک کار تطبیق با استفاده از مجموعه ای از 32 تصویر واقعی از یک طیف متنوع ، از جمله فضای باز صحنه ها ، چهره های انسانی ، عکس های هوایی و تصاویر صنعتی طراحی شده است (مشخص شد که دامنه تصویر تقریباً هیچ تاثیری در هیچ یک از نتایج ندارد).سپس هر تصویر تحت بازه ای از تبدیلات از جمله چرخش ، مقیاس ، افاین ، تغییر در روشنایی و کنتراست و اضافه شدن نویز تصویر قرار گرفت. از آنجا که این تغییرات مصنوعی بودند ، می توان به طور دقیق پیش بینی کرد که هر یک از ویژگی های یک تصویر اصلی باید چقدر در تصویر, تغییر شکل یافته وجود داشته باشد ، که امکان اندازه گیری تکرار صحیح و دقت موقعیتی برای هر ویژگی را فراهم می کند.شکل 3 این نتایج شبیه سازی را نشان می دهد که برای بررسی تأثیر تغییر تعداد مقیاس در هر اکتاو که در آن تابع تصویر قبل از تشخیص اکسترمم در آن نمونه برداری می شود ، استفاده شده است. در این حالت ، هر تصویر به دنبال چرخش با یک زاویه تصادفی و مقیاس گذاری با مقدار تصادفی بین 0.2 تا 0.9 برابر اندازه اصلی ، نمونه برداری شد. نقاط کلیدی از تصویر با وضوح کاهش یافته با آنهایی که از تصویر اصلی هستند مطابقت داشتند بنابراین مقیاس ها تمام نقاط کلیدی در تصویر منطبق شده باید حضورداشته باشند. علاوه بر این ، 1٪ نویز تصویر اضافه شده است ، به این معنی که هر پیکسل دارای یک عدد تصادفی از فاصله یکنواخت [-0.01،0.01] است که در آن مقادیر پیکسل در محدوده [0،1] است (معادل کمی کمتر از 6 بیت از دقت پیکسل های تصویر).

The top line in the first graph of Figure 3 shows the percent of keypoints that are detected at a matching location and scale in the transformed image. For all examples in this paper, we define a matching scale as being within a factor of √2 of the correct scale, and a matching location as being within δ pixels, where δ is the scale of the keypoint (defined from equation (1) as the standard deviation of the smallest Gaussian used in the difference-of-Gaussian function). The lower line on this graph shows the number of keypoints that are correctly matched to a database of 40,000 keypoints using the nearest-neighbor matching procedure to be described in Section 6 (this shows that once the keypoint is repeatably located, it is likely to be useful for recognition and matching tasks). As this graph shows, the highest repeatability is obtained when sampling 3 scales per octave, and this is the number of scale samples used for all other experiments throughout this paper. It might seem surprising that the repeatability does not continue to improve as more scales are sampled. The reason is that this results in many more local extrema being detected, but these extrema are on average less stable and therefore are less likely to be detected in the transformed image. This is shown by the second graph in Figure 3, which shows the average number of keypoints detected and correctly matched in each image. The number of keypoints rises with increased sampling of scales and the total number of correct matches also rises. Since the success of object recognition often depends more on the quantity of correctly matched keypoints, as opposed to their percentage correct matching, for many applications it will be optimal to use a larger number of scale samples. However, the cost of computation also rises with this number, so for the experiments in this paper we have chosen to use just 3 scale samples per octave. To summarize, these experiments show that the scale-space difference-of-Gaussian function has a large number of extrema and that it would be very expensive to detect them all. Fortunately, we can detect the most stable and useful subset even with a coarse sampling of scales.

خط بالا در نمودار اول شکل 3 , درصد نقاط کلیدی را نشان می دهد که در یک مکان و مقیاس منطبق در تصویر تبدیل شده شناسایی می شوند. برای همه نمونه های این مقاله ، مقیاس تطبیق را با فاکتور √2 به عنوان مقیاس صحیح و یک مکان تطبیقی را به اندازه δ پیکسل ها تعریف می کنیم ، جایی که δ مقیاس نقطه کلیدی است (تعریف شده از معادله (1) به عنوان انحراف معیار کوچکترین گوسی که در تابع اختلاف گوسی استفاده می شود) خط پایین این نمودار تعداد نقاط کلیدی را نشان می دهد که به درستی با یک پایگاه داده 40،000 نقطه کلید با استفاده از روش تطبیق نزدیکترین همسایه مطابقت داده می شود که در بخش 6 شرح داده شده است (این نشان می دهد که اگر نقطه کلیدی به طور مکرر(با تکرار پذیری ) شناسایی شود ، احتمالاً برای تشخیص و تطبیق مفید است). همانطور که این نمودار نشان می دهد ، بالاترین تکرارپذیری در هنگام نمونه گیری از 3 مقیاس در هر اکتاو بدست می آید و این تعداد نمونه های مقیاس برای سایر آزمایشات در کل این مقاله استفاده می شود.ممکن است تعجب آور باشد که تکرارپذیری با نمونه برداری از مقیاس های بیشتر ، همچنان بهبود نمی یابد. دلیل این امر این است که این امر منجر به شناسایی اکسترمم بیشتر می شود ، اما این اکسترم به طور متوسط دارای پایداری کمتری هستند و بنابراین در تصویر تغییر شکل یافته کمتر تشخیص داده می شوند. این توسط نمودار دوم در شکل 3 نشان داده شده است که میانگین تعداد نقاط کلیدی شناسایی شده و مطابقت صحیح در هر تصویر را نشان می دهد. با افزایش نمونه برداری از مقیاس ها ، تعداد نقاط اصلی افزایش می یابد و تعداد کل تطابق های صحیح نیز افزایش می یابد. از آنجایی که موفقیت در تشخیص شی اغلب به کمیت تطابق درست نقاط کلیدی بستگی دارد ، برخلاف درصد تطبیق صحیح آنها ، استفاده از تعداد بیشتری از نمونه های مقیاس برای بسیاری از برنامه ها بهینه خواهد بود. با این حال ، هزینه محاسبه نیز با این تعداد افزایش می یابد ، بنابراین برای آزمایش های این مقاله ما انتخاب کرده ایم که فقط از 3 نمونه مقیاس در هر اکتاو استفاده کنیم.به طور خلاصه ، این آزمایشات نشان می دهد که فضای مقیاس تابع تفاضل گاوسی دارای تعداد زیادی از اکسترمم است و تشخیص همه آنها بسیار هزینه بر است. خوشبختانه ، ما می توانیم پایدارترین و مفیدترین زیرمجموعه را حتی با یک نمونه گیری درشت از مقیاس ها تشخیص دهیم.

Frequency of sampling in the spatial domain
Just as we determined the frequency of sampling per octave of scale space, so we must determine the frequency of sampling in the image domain relative to the scale of smoothing. Given that extrema can be arbitrarily close together, there will be a similar trade-off between sampling frequency and rate of detection. Figure 4 shows an experimental determination of the amount of prior smoothing, δ , that is applied to each image level before building the scale space representation for an octave. Again, the top line is the repeatability of keypoint detection, and the results show that the repeatability continues to increase with δ . However, there is a cost to using a large δ in terms of efficiency, so we have chosen to use δ = 1.6, which provides close to optimal repeatability. This value is used throughout this paper and was used for the results in Figure 3. Of course, if we pre-smooth the image before extrema detection, we are effectively discarding the highest spatial frequencies. Therefore, to make full use of the input, the image can be expanded to create more sample points than were present in the original. We double the size of the input image using linear interpolation prior to building the first level of the pyramid. While the equivalent operation could effectively have been performed by using sets of subpixel-offset filters on the original image, the image doubling leads to a more efficient implementation. We assume that the original image has a blur of at least δ = 0.5 (the minimum needed to prevent significant aliasing), and that therefore the doubled image has δ = 1.0 relative to its new pixel spacing. This means that little additional smoothing is needed prior to creation of the first octave of scale space. The image doubling increases the number of stable keypoints by almost a factor of 4, but no significant further improvements were found with a larger expansion factor.

تکرار نمونه برداری در حوزه مکانی

همانطور که تکرار نمونه برداری در هر از اکتاو فضای مقیاس را تعیین کردیم ، بنابراین باید تکرار نمونه برداری را نیز در دامنه تصویر نسبت به مقیاس بلرینگ تعیین کنیم. با توجه به اینکه اکسترمم ها می تواند خودسرانه به هم نزدیک شود ، یک تعادل مشابه بین تکرار نمونه برداری و نرخ تشخیص ایجاد شود. شکل 4 آزمایش تعیین مقدار بلور کردن قبلی , δ , را نشان می دهد ، که برای هر سطح تصویر قبل از ساختن فضای مقیاس برای یک اکتاو اعمال می شود. باز هم ، خط اول تکرارپذیری تشخیص نقاط کلیدی است ، و نتایج نشان می دهد که تکرارپذیری همچنان با افزاش δ ادامه می یابد. با این حال ، استفاده از یک δ بزرگ از نظر کارایی هزینه دارد ، بنابراین ما استفاده از δ = 1.6 را انتخاب کرده ایم که تکرارپذیری تقریباً بهینه را فراهم می کند. این مقدار در کل این مقاله استفاده شده و برای نتایج در شکل 3 استفاده شده است.مطمئناً ، اگر ما قبل از تشخیص اکسترمم تصویر را صاف(بلور) کنیم ، به طور موثر بالاترین تکرار های مکانی را کنار می گذاریم. بنابراین ، برای استفاده کامل از ورودی ، می توان تصویر را گسترش داد تا نقاط نمونه بیشتری از آنچه در نسخه اصلی وجود دارد، ایجاد کند. ما قبل از ساخت سطح اول هرم ، با استفاده از درون یابی خطی ، اندازه تصویر ورودی را دو برابر می کنیم. در حالی که می توان با استفاده از مجموعه فیلترهای آفست ساب پیکسل بر روی تصویر اصلی ، عملکرد معادل آن را انجام داد ، دو برابر شدن تصویر منجر به اجرای کارآمدتر می شود.ما فرض می کنیم که تصویر اصلی دارای تاری حداقل δ = 0/5 (حداقل مورد نیاز برای جلوگیری از ایجاد aliasing) است و بنابراین تصویر دو برابر شده نسبت به فاصله پیکسل جدید خود δ برابر با 1.0 است. این بدان معنی است که قبل از ایجاد اولین اکتاو فضای مقیاس ، به اضافه کردن صافی (بلور) کمی نیاز است. دوبرابر شدن تصویر تعداد نقاط کلیدی پایدار را تقریباً با ضریب 4 افزایش می دهد ، اما با ضریب انبساط بزرگتر هیچ پیشرفت قابل توجه دیگری یافت نشد.

Accurate keypoint localization
Once a keypoint candidate has been found by comparing a pixel to its neighbors, the next step is to perform a detailed fit to the nearby data for location, scale, and ratio of principal curvatures. This information allows points to be rejected that have low contrast (and are therefore sensitive to noise) or are poorly localized along an edge. The initial implementation of this approach (Lowe, 1999) simply located keypoints at the location and scale of the central sample point. However, recently Brown has developed a method (Brown and Lowe, 2002) for fitting a 3D quadratic function to the local sample points to determine the interpolated location of the maximum, and his experiments showed that this provides a substantial improvement to matching and stability. His approach uses the Taylor expansion (up to the quadratic terms) of the scale-space function, D(x, y, δ ), shifted so that the origin is at the sample point. where D and its derivatives are evaluated at the sample point and x = (x, y, δ )^T is the offset from this point. The location of the extremum, ˆx, is determined by taking the derivative of this function with respect to x and setting it to zero, giving

محلی سازی دقیق نقاط کلیدی
هنگامی که با مقایسه یک پیکسل با همسایگان خود ، یک نقطه کلیدی کاندید پیدا شد ، مرحله بعدی انجام یک تناسب دقیق با داده های مجاور برای مکان ، مقیاس و نسبت انحناهای اصلی است. این اطلاعات اجازه می دهد تا نقاطی که دارای کنتراست کم هستند (و بنابراین به نویز حساس هستند) یا در امتداد لبه قرار گرفته اند رد شوند.اجرای اولیه این روش (لوو ، 1999) به راحتی نقاط كلیدی را در محل و مقیاس نقطه نمونه مرکزی قرار داد. با این وجود ، اخیراً براون روشی را برای برازش یک تابع درجه دوم سه بعدی در نقاط نمونه محلی برای تعیین مکان درون یابی حداکثر (ماکسیم ها)ایجاد کرده است و آزمایشات وی نشان داده است که این امر بهبود قابل توجهی در تطبیق و پایداری ایجاد می کند. رویکرد او از تیلور (تا اصطلاحات درجه دوم) تابع فضای مقیاس ، D (x ، y ، δ ) ، تغییر یافته استفاده می کند به طوری که مبدا در نقطه نمونه باشد جایی که D و مشتقات آن در نقطه نمونه ارزیابی می شوند و x = (x ، y ، δ ) ^T انحراف از این نقطه است. محل اکسترمم ، ˆx ، با گرفتن مشتق این تابع نسبت به x و مساوی صفر قرار دادن ، تعیین می شود (رابطه 3)

As suggested by Brown, the Hessian and derivative of D are approximated by using differences of neighboring sample points. The resulting 3×3 linear system can be solved with minimal cost. If the offset ˆx is larger than 0.5 in any dimension, then it means that the extremum lies closer to a different sample point. In this case, the sample point is changed and the interpolation performed instead about that point. The final offset ˆx is added to the location of its sample point to get the interpolated estimate for the location of the extremum. The function value at the extremum, D(ˆx), is useful for rejecting unstable extrema with low contrast. This can be obtained by substituting equation (3) into (2), giving. For the experiments in this paper, all extrema with a value of |D(ˆx)| less than 0.03 were discarded (as before, we assume image pixel values in the range [0,1]). Figure 5 shows the effects of keypoint selection on a natural image. In order to avoid too much clutter, a low-resolution 233 by 189 pixel image is used and keypoints are shown as vectors giving the location, scale, and orientation of each keypoint (orientation assignment is described below). Figure 5 (a) shows the original image, which is shown at reduced contrast behind the subsequent figures. Figure 5 (b) shows the 832 keypoints at all detected maxima and minima of the difference-of-Gaussian function, while (c) shows the 729 keypoints that remain following removal of those with a value of |D(ˆx)| less than 0.03. Part (d) will be explained in the following section

همانطور که توسط براون پیشنهاد شده است ، هسیان و مشتق D با استفاده از اختلاف نقاط نمونه همسایه تقریب زده می شوند. سیستم خطی 3×3 حاصل با حداقل هزینه قابل حل است. اگر انحراف در هر ابعادی بزرگتر از 0.5 باشد ، این بدان معناست که اکسترمم به اشتباه به نقطه نمونه دیگری نزدیکتر است. در این حالت ، نقطه نمونه تغییر کرده و به جای آن درون یابی در اطراف آن نقطه انجام می شود. انحراف نهایی ˆx به محل نقطه نمونه خود اضافه می شود تا برآورد درون یابی محل اکسترمم را بدست آورد. مقدار تابع در اکسترمم ، D (ˆx) ، برای رد کردن اکسترمم های ناپایدار با کنتراست کم مفید است. این را می توان با جایگزینی معادله (3) در (2) ، بدست آورد

برای آزمایش های انجام شده در این مقاله ، همه اکسترمم با مقدار | D (ˆx) | کمتر از 0.03 کنار گذاشته شد (مانند قبل ، ما مقادیر پیکسل تصویر را در محدوده [0،1] فرض می کنیم).شکل 5 اثرات انتخاب نقاط کلیدی بر روی یک تصویر طبیعی را نشان می دهد. به منظور جلوگیری از شلوغی زیاد ، از یک تصویر پیکسل با وضوح پایین 233 در 189 استفاده شده و نقاط کلیدی به عنوان بردارهایی که مکان ، مقیاس و جهت گیری هر نقطه کلیدی را نشان می دهند ، نشان داده می شوند (انتساب جهت گیری در زیر توضیح داده شده است). شکل 5 (الف) تصویر اصلی را نشان می دهد که با کنتراست کاهش یافته در پشت شکل های بعدی نشان داده شده است. شکل 5 (b) 832 نقطه کلیدی را در حداکثر و حداقل های تشخیص شده از تابع اختلاف گاوسی نشان می دهد ، در حالی که (c) 729 نقطه کلیدی را نشان می دهد که پس از حذف موارد با مقدار | D (ˆx) | کمتر از 03/0. قسمت (د) در بخش زیر توضیح داده خواهد شد.

Eliminating edge responses
For stability, it is not sufficient to reject keypoints with low contrast. The difference-of Gaussian function will have a strong response along edges, even if the location along the edge is poorly determined and therefore unstable to small amounts of noise.A poorly defined peak in the difference-of-Gaussian function will have a large principal curvature across the edge but a small one in the perpendicular direction. The principal curvatures can be computed from a 2×2 Hessian matrix, H, computed at the location and scale of the keypoint. The derivatives are estimated by taking differences of neighboring sample points.The eigenvalues of H are proportional to the principal curvatures of D. Borrowing from the approach used by Harris and Stephens (1988), we can avoid explicitly computing the eigenvalues, as we are only concerned with their ratio. Let α be the eigenvalue with the largest magnitude and β  be the smaller one. Then, we can compute the sum of the eigenvalues from the trace of H and their product from the determinant. In the unlikely event that the determinant is negative, the curvatures have different signs so the point is discarded as not being an extremum. Let r be the ratio between the largest magnitude eigenvalue and the smaller one, so that α = rβ . Then, In the unlikely event that the determinant is negative, the curvatures have different signs so the point is discarded as not being an extremum. Let r be the ratio between the largest magnitude eigenvalue and the smaller one, so that α = rβ . Then….. which depends only on the ratio of the eigenvalues rather than their individual values. The quantity (r+1)2/r is at a minimum when the two eigenvalues are equal and it increases with r. Therefore, to check that the ratio of principal curvatures is below some threshold, r, we only need to check … This is very efficient to compute, with less than 20 floating point operations required to test each keypoint. The experiments in this paper use a value of r = 10, which eliminates keypoints that have a ratio between the principal curvatures greater than 10. The transition from Figure 5 (c) to (d) shows the effects of this operation.

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

مشتقات با در نظر گرفتن اختلاف نقاط نمونه همسایه تخمین زده می شوند. مقادیر ویژه H متناسب با انحنای اصلی D هستند.. با اقتباس از رویکردی که هریس و استیون (1988) به کار بردند ، می توانیم از محاسبه صریح مقادیر ویژه خودداری کنیم ، زیرا فقط به نسبت آنها علاقمندیم. بگذارید α مقدار ویژه با بزرگترین مقدار باشد و β کوچکتر باشد. سپس ، ما می توانیم مجموع مقادیر ویژه را از تریس H و حاصلضرب آنها را از دترمینان محاسبه کنیم.

با بعید بودن این اتفاق که دترمینان منفی شود ، انحناها علائم مختلفی دارند بنابراین نقطه به عنوان یک حالت اکسترمم کنار گذاشته می شود. بگذارید r نسبت بین مقدار ویژه بزرگتر و مقدار کوچکتر باشد α = rβ ، بنابراین

که فقط به نسبت مقادیر ویژه و نه به ارزشهای فردی آنها بستگی دارد. کمیت (r + 1) 2 / r هنگامی که دو مقدار ویژه برابر هستند حداقل است و با r افزایش می یابد. بنابراین ، برای بررسی اینکه آیا نسبت انحنای اصلی پایین برخی از آستانه ها است ، فقط باید بررسی کنیم

این برای محاسبه بسیار کارآمد است ، برای آزمایش هر نقطه کلیدی کمتر از 20 عملیات نقطه شناور لازم است. آزمایش های انجام شده در این مقاله از مقدار r = 10 استفاده می کند که نقاط کلیدی را که دارای نسبت انحنای اصلی بیشتر از 10 هستند حذف می کند. انتقال از شکل 5 (c) به (d) اثرات این عملیات را نشان می دهد.

Orientation assignment
By assigning a consistent orientation to each keypoint based on local image properties, the keypoint descriptor can be represented relative to this orientation and therefore achieve invariance to image rotation. This approach contrasts with the orientation invariant descriptors of Schmid andMohr (1997), in which each image property is based on a rotationally invariant measure. The disadvantage of that approach is that it limits the descriptors that can be used and discards image information by not requiring all measures to be based on a consistent rotation….. Following experimentation with a number of approaches to assigning a local orientation,the following approach was found to give the most stable results. The scale of the keypoint is used to select the Gaussian smoothed image, L, with the closest scale, so that all computations are performed in a scale-invariant manner. For each image sample, L(x, y), at this scale, the gradient magnitude, m(x, y), and orientation, θ(x, y), is precomputed using pixel differences….. An orientation histogram is formed from the gradient orientations of sample points within a region around the keypoint. The orientation histogram has 36 bins covering the 360 degree range of orientations. Each sample added to the histogram is weighted by its gradient magnitude and by a Gaussian-weighted circular window with a δ that is 1.5 times that of the scale of the keypoint. …. Peaks in the orientation histogram correspond to dominant directions of local gradients.The highest peak in the histogram is detected, and then any other local peak that is within 80% of the highest peak is used to also create a keypoint with that orientation. Therefore, for locations with multiple peaks of similar magnitude, there will be multiple keypoints created at the same location and scale but different orientations. Only about 15% of points are assigned multiple orientations, but these contribute significantly to the stability of matching. Finally, a parabola is fit to the 3 histogram values closest to each peak to interpolate the peak position for better accuracy. …. Figure 6 shows the experimental stability of location, scale, and orientation assignment under differing amounts of image noise. As before the images are rotated and scaled by random amounts. The top line shows the stability of keypoint location and scale assignment.The second line shows the stability of matching when the orientation assignment is also required to be within 15 degrees. As shown by the gap between the top two lines, the orientation assignment remains accurate 95% of the time even after addition of ±10% pixel noise (equivalent to a camera providing less than 3 bits of precision). The measured variance of orientation for the correct matches is about 2.5 degrees, rising to 3.9 degrees for 10% noise. The bottom line in Figure 6 shows the final accuracy of correctly matching a keypoint descriptor to a database of 40,000 keypoints (to be discussed below). As this graph shows, the SIFT features are resistant to even large amounts of pixel noise, and the major cause of error is the initial location and scale detection .

تخصیص جهت
با اختصاص یک جهت ثابت به هر نقطه کلیدی بر اساس ویژگی های محلی تصویر، توصیفگر نقاط کلیدی می تواند با این جهت نشان داده شود و بنابراین به مقاومت در چرخش تصویر دست یابد. این رویکرد با توصیفگرهای مقاوم جهت استاز اشمید و مور (1997) در تضاد است ، که در آن هر ویژگی تصویر بر اساس معیار ثابت چرخشی است. نقطه ضعف این روش این است که توصیفگرهایی را که می توان استفاده کرد محدود می کند و اطلاعات تصویر را با عدم نیاز به تمام اقدامات مبتنی بر یک چرخش ثابت ، دور می اندازد.به دنبال آزمایش با تعدادی از روش ها برای تخصیص جهت محلی ، در روش زیر با ثبات ترین نتایج یافت شد. مقیاس نقطه کلیدی برای انتخاب تصویرنرم شده گوسی ، L ، با نزدیکترین مقیاس استفاده می شود ، به طوری که همه محاسبات به روش مقاوم نسبت به مقیاس انجام می شود. برای هر نمونه تصویر ، L (x، y) ، در این مقیاس ، اندازه گرادیان ، m (x ، y) و جهت گیری ، θ(x ، y) ، با استفاده از اختلاف پیکسل از قبل محاسبه می شود.

یک هیستوگرام جهت از گرادیان جهت ها نقاط نمونه در یک منطقه اطراف نقطه اصلی تشکیل می شود. هیستوگرام جهت دارای 36 بین برای پوشش 360 درجه است. هر نمونه اضافه شده به هیستوگرام با اندازه گرادیان خود و با یک پنجره دایره ای با گاوسی وزن دار شده با یک سیگما 1.5 برابر مقیاس نقطه کلیدی می شود.قله ها در هیستوگرام جهت با جهات شیب محلی مطابقت دارند. بالاترین قله در هیستوگرام شناسایی می شود و سپس هر قله محلی دیگر که در 80٪ بالاترین قله باشد برای ایجاد یک نقطه کلیدی با آن جهت استفاده می شود. بنابراین ، برای مکانهایی با قله های متعدد با اندازه مشابه ، چندین کلید اصلی در همان مکان و مقیاس ایجاد می شوند اما جهت مختلف وجود دارد. فقط حدود 15٪ از نقاط دارای چند جهت هستند ، اما اینها به طور قابل توجهی به ثبات تطبیق کمک می کنند. سرانجام ، یک سهمی با 3 مقدار هیستوگرام نزدیک به هر قله متناسب است تا موقعیت قله را برای دقت بهتر درون یابی کند.شکل 6 ثبات آزمایشی مکان ، مقیاس و انتساب جهت را در مقادیر مختلف نویز تصویر نشان می دهد. مانند قبل ,تصاویر با مقادیر تصادفی چرخانده و مقیاس بندی می شوند. خط بالا پایداری مکان و تعیین مقدار مقیاس را نشان می دهد. خط دوم ثبات تطبیق را زمانی نشان می دهد که انتساب جهت نیز 15 درجه لازم باشد. همانطور که با فاصله بین دو خط بالا نشان داده شده است ، انتساب جهت گیری در 95٪ دقت پس از اضافه شدن(کم شدن) 10 درصد پیکسل نویز (معادل دوربین با دقت کمتر از 3 بیت) حفظ می شود. واریانس جهت اندازه گیری شده برای تطابق های صحیح حدود 2.5 درجه است و برای 10٪ نویز به 3.9 درجه افزایش می یابد. خط آخر در شکل 6 دقت نهایی مطابقت صحیح توصیفگر نقاط کلیدی را با پایگاه داده 40000 نقطه کلیدی نشان می دهد (که در زیر به آن پرداخته می شود). همانطور که این نمودار نشان می دهد ، ویژگی های SIFT حتی در برابر مقدار زیادی از نویز پیکسل نیز مقاوم هستند و علت اصلی خطا ، تعیین مکان و مقیاس اولیه است.

The local image descriptor
The previous operations have assigned an image location, scale, and orientation to each keypoint.These parameters impose a repeatable local 2D coordinate system in which to describe the local image region, and therefore provide invariance to these parameters. The next step is to compute a descriptor for the local image region that is highly distinctive yet is as invariant as possible to remaining variations, such as change in illumination or 3D viewpoint…. One obvious approach would be to sample the local image intensities around the keypoint at the appropriate scale, and to match these using a normalized correlation measure.However, simple correlation of image patches is highly sensitive to changes that cause misregistration of samples, such as affine or 3D viewpoint change or non-rigid deformations. A better approach has been demonstrated by Edelman, Intrator, and Poggio (1997). Their proposed representation was based upon a model of biological vision, in particular of complex neurons in primary visual cortex. These complex neurons respond to a gradient at a particular orientation and spatial frequency, but the location of the gradient on the retina is allowed to shift over a small receptive field rather than being precisely localized. … Edelman et al. hypothesized that the function of these complex neurons was to allow for matching and recognition of 3D objects from a range of viewpoints. They have performed detailed experiments using 3D computer models of object and animal shapes which show that matching gradients while allowing for shifts in their position results in much better classification under 3D rotation. For example, recognition accuracy for 3D objects rotated in depth by 20 degrees increased from 35% for correlation of gradients to 94% using the complex cell model. Our implementation described below was inspired by this idea, but allows for positional shift using a different computational mechanism.

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

یک روش واضح این است که از روشنایی محلی تصویر در اطراف نقطه کلیدی در مقیاس مناسب نمونه برداری کرده و با استفاده از معیار همبستگی نرمال شده ، این موارد را مطابقت دهید. با این حال ، همبستگی ساده پچ های تصویر نسبت به تغییراتی که باعث ثبت اشتباه نمونه ها می شود ، مانند تغییر دیدگاه سه بعدی یا آفاین یا تغییر شکل های غیرسخت ، بسیار حساس است. روش بهتری توسط Edelman ، Intrator و Poggio (1997) نشان داده شده است. نمایش پیشنهادی آنها بر اساس یک مدل دید بیولوژیکی ، به ویژه نورونهای پیچیده در قشر بینایی اولیه بود. این سلولهای عصبی پیچیده به یک گرادیان در یک جهت گیری خاص و فرکانس مکانی پاسخ می دهند ، اما محل شیب در شبکیه مجاز است تا به جای اینکه دقیقاً محلی باشد ، از یک میدان پذیرای کوچک جابجا شود.ادلمن و همکاران این فرضیه که عملکرد این سلولهای عصبی پیچیده اجازه تطبیق و تشخیص اشیا 3D سه بعدی را از طیف وسیعی از دیدگاهها فراهم می کند. آنها آزمایش های مفصلی را با استفاده از مدل های سه بعدی رایانه ای اشکال حیوانات و اشیا انجام داده اند که نشان می دهد شیب های منطبق در حالی که امکان تغییر موقعیت آنها را فراهم می کند ، منجر به طبقه بندی بسیار بهتر تحت چرخش سه بعدی می شود. به عنوان مثال ، دقت تشخیص برای اشیا 3D سه بعدی که در عمق 20 درجه چرخانده می شوند ، از 35٪ برای همبستگی شیب ها به 94٪ با استفاده از مدل سلول پیچیده افزایش یافته است. اجرای ما که در زیر توضیح داده شده از این ایده الهام گرفته شده است ، اما امکان تغییر موضعی با استفاده ازمکانیسم محاسباتی را فراهم می کند.

Descriptor representation
Figure 7 illustrates the computation of the keypoint descriptor. First the image gradient magnitudes and orientations are sampled around the keypoint location, using the scale of the keypoint to select the level of Gaussian blur for the image. In order to achieve orientation invariance, the coordinates of the descriptor and the gradient orientations are rotated relative to the keypoint orientation. For efficiency, the gradients are precomputed for all levels of the pyramid as described in Section 5. These are illustrated with small arrows at each sample location on the left side of Figure 7. A Gaussian weighting function with δ equal to one half the width of the descriptor window is used to assign a weight to the magnitude of each sample point. This is illustrated with a circular window on the left side of Figure 7, although, of course, the weight falls off smoothly. The purpose of this Gaussian window is to avoid sudden changes in the descriptor with small changes in the position of the window, and to give less emphasis to gradients that are far from the center of the descriptor, as these are most affected by misregistration errors…. The keypoint descriptor is shown on the right side of Figure 7. It allows for significant shift in gradient positions by creating orientation histograms over 4×4 sample regions. The figure shows eight directions for each orientation histogram, with the length of each arrow corresponding to the magnitude of that histogram entry. A gradient sample on the left can shift up to 4 sample positions while still contributing to the same histogram on the right, thereby achieving the objective of allowing for larger local positional shifts… It is important to avoid all boundary affects in which the descriptor abruptly changes as a sample shifts smoothly from being within one histogram to another or from one orientation to another. Therefore, trilinear interpolation is used to distribute the value of each gradient sample into adjacent histogram bins. In other words, each entry into a bin is multiplied by a weight of 1 − d for each dimension, where d is the distance of the sample from the central value of the bin as measured in units of the histogram bin spacing…. The descriptor is formed from a vector containing the values of all the orientation histogram entries, corresponding to the lengths of the arrows on the right side of Figure 7. The figure shows a 2×2 array of orientation histograms, whereas our experiments below show that the best results are achieved with a 4×4 array of histograms with 8 orientation bins in each. Therefore, the experiments in this paper use a 4x4x8 = 128 element feature vector for each keypoint. …. Finally, the feature vector is modified to reduce the effects of illumination change. First,the vector is normalized to unit length. A change in image contrast in which each pixel value is multiplied by a constant will multiply gradients by the same constant, so this contrast change will be canceled by vector normalization. A brightness change in which a constant is added to each image pixel will not affect the gradient values, as they are computed from pixel differences. Therefore, the descriptor is invariant to affine changes in illumination. However, non-linear illumination changes can also occur due to camera saturation or due to illumination changes that affect 3D surfaces with differing orientations by different amounts. These effects can cause a large change in relative magnitudes for some gradients, but are less likely to affect the gradient orientations. Therefore, we reduce the influence of large gradient magnitudes by thresholding the values in the unit feature vector to each be no larger than 0.2, and then renormalizing to unit length. This means that matching the magnitudes for large gradients is no longer as important, and that the distribution of orientations has greater emphasis. The value of 0.2 was determined experimentally using images containing differing illuminations for the same 3D objects.

نمایش توصیف گر
شکل 7 محاسبه توصیفگر نقطه کلیدی را نشان می دهد. ابتدا اندازه گردایان تصویر و جهت اطراف نقطه کلیدی با استفاده از مقیاس نقطه کلیدی برای انتخاب سطح نرم شدن گوسین برای تصویرنمونه برداری شده اند . به منظور دستیابی به جهت ثابت ، مختصات توصیفگر و جهت گرادیان نسبت به جهت نقطه کلیدی چرخانده می شوند. برای کارآیی ، شیب ها برای تمام سطوح هرم مطابق با بخش 5 محاسبه می شوند. اینها با فلش های کوچک در هر مکان نمونه در سمت چپ شکل 7 نشان داده شده است.از تابع وزن دار گاوسی با δ برابر نیمی از عرض پنجره توصیفگر برای تعیین وزنی به اندازه هر نقطه نمونه استفاده می شود. این با یک پنجره مدور در سمت چپ شکل 7 نشان داده شده است ، اگرچه ، البته ، وزن به آرامی پایین می آید. هدف از این پنجره گاوسی جلوگیری از تغییرات ناگهانی توصیف کننده با تغییرات اندک در موقعیت پنجره و تأکید کمتر بر گرادیان هایی است که از مرکز توصیف کننده فاصله زیادی دارند ، زیرا بیشتر تحت تأثیر خطاهای ثبت نادرست قرار می گیرند.توصیفگر نقاط کلیدی در سمت راست شکل 7 نشان داده شده است. با ایجاد هیستوگرام های جهت در مناطق نمونه 4×4 امکان تغییر چشمگیر در موقعیت های گرادیان را فراهم می کند. در این شکل هشت جهت برای هر هیستوگرام جهت نشان داده شده است که طول هر پیکان مربوط به اندازه ورودی هیستوگرام است. یک نمونه گرادیان در سمت چپ می تواند تا 4 موقعیت نمونه را جابجا کند در حالی که هنوز به همان هیستوگرام سمت راست کمک می کند ، در نتیجه به هدف اجازه تغییر مکان موضعی بزرگتر می دهد.مهم است که از تأثیرات مرزی که در آن توصیف کننده ناگهان تغییر می کند ، به عنوان مثال تغییر یکنواخت نمونه از درون یک هیستوگرام به دیگری یا از یک جهت به جهت دیگر ، جلوگیری شود. بنابراین ، از توزیع سه خطی برای توزیع مقدار هر نمونه گرادیان در بین های هیستوگرام مجاور استفاده می شود.به عبارت دیگر ، هر ورودی به یک بین در وزن 1 – d برای هر بعد ضرب می شود ، جایی که d فاصله نمونه از مقدار مرکزی بین است که در واحد فاصله بین هیستوگرام اندازه گیری می شود.توصیفگر از یک بردار تشکیل شده است که شامل مقادیر تمام ورودی های هیستوگرام جهت هست ، ارتباط طول پیکان ها در سمت راست شکل 7 است. این شکل یک آرایه 2×2 از هیستوگرام های جهت را نشان می دهد ، در حالی که آزمایش های ما در زیر نشان می دهد بهترین نتایج با یک آرایه 4×4 هیستوگرام با 8 بین جهت گیری در هر کدام بدست می آید. بنابراین ، آزمایش های انجام شده در این مقاله برای هر نقطه کلیدی از بردار ویژگی عنصر 4x4x8 = 128 استفاده می کند.

سرانجام ، بردار ویژگی اصلاح می شود تا اثرات تغییر نور را کاهش دهد. ابتدا بردار به طول واحد نرمال می شود. تغییر در کنتراست تصویر که در آن هر مقدار پیکسل در یک ثابت ضرب می شود ، گرادیان ها را در همان ثابت ضرب می کند ، بنابراین این تغییر کنتراست با نرمال سازی بردار لغو می شود. یک تغییر روشنایی که در آن یک ثابت به هر پیکسل تصویر اضافه می شود ، بر مقادیر گرادیان تأثیر نخواهد گذاشت ، زیرا آنها از اختلاف پیکسل محاسبه می شوند. بنابراین ، توصیف کننده برای تغییر افاین روشنایی ثابت هست. با این حال ، تغییرات روشنایی غیرخطی نیز می تواند به دلیل اشباع دوربین یا به دلیل تغییرات روشنایی که روی سطوح سه بعدی با جهت های متفاوت با مقادیر مختلف تأثیر می گذارد,ظاهر شوند. این اثرات می تواند تغییر بزرگی در اندازه های برخی از گرادیان ها ایجاد کند ، اما با احتمالاً کمتر روی جهت گیری های شیب تأثیر می گذارد. بنابراین ، با کاهش تاثیرمقادیر زیاد گرادیان با آستانه گذاری مقادیر در یک بردار ویژگی واحد که بزرگ تر از 0.2 نباشد و سپس به بردار واحد دوباره نرمال کنیم. این بدان معناست که مطابقت اندازه ها برای گرادیان های بزرگ دیگر آنقدر مهم نیست و توزیع جهت ها تأکید بیشتری دارد. مقدار 0.2 با استفاده از تصاویر حاوی نورهای متفاوت برای اشیا 3D سه بعدی به صورت آزمایشی تعیین شد.

Descriptor testing
There are two parameters that can be used to vary the complexity of the descriptor: the number of orientations, r, in the histograms, and the width, n, of the n×n array of orientation histograms. The size of the resulting descriptor vector is rn^2. As the complexity of the descriptor grows, it will be able to discriminate better in a large database, but it will also be more sensitive to shape distortions and occlusion… Figure 8 shows experimental results in which the number of orientations and size of the descriptor were varied. The graph was generated for a viewpoint transformation in which a planar surface is tilted by 50 degrees away from the viewer and 4% image noise is added. This is near the limits of reliable matching, as it is in these more difficult cases that descriptor performance is most important … The results show the percent of keypoints that find a correct match to the single closest neighbor among a database of 40,000 keypoints. The graph shows that a single orientation histogram (n = 1) is very poor at discriminating, but the results continue to improve up to a 4×4 array of histograms with 8 orientations. After that, adding more orientations or a larger descriptor can actually hurt matching by making the descriptor more sensitive to distortion. These results were broadly similar for other degrees of viewpoint change and noise, although in some simpler cases discrimination continued to improve (from already high levels) with 5×5 and higher descriptor sizes …. Throughout this paper we use a 4×4 descriptor with 8 orientations, resulting in feature vectors with 128 dimensions.While the dimensionality of the descriptor may seem high, we have found that it consistently performs better than lower-dimensional descriptors on a range of matching tasks and that the computational cost of matching remains low when using the approximate nearest-neighbor methods described below.

تست توصیف کننده
دو پارامتر وجود دارد که می تواند برای تغییر پیچیدگی توصیف کننده استفاده شود: تعداد جهت ها ، r ، در هیستوگرام ها و عرض n آرایه n × n هیستوگرام های جهت . اندازه بردار توصیف کننده حاصل rn^2 است. همانطور که پیچیدگی توصیفگر رشد می کند ، قادر خواهد بود در یک پایگاه داده بزرگ تمایز بهتری داشته باشد ، اما همچنین به اعوجاج شکل و انسداد حساسیت بیشتری خواهد داشت.شکل 8 نتایج آزمایشی را نشان می دهد که در آنها تعداد جهت ها و اندازه توصیف کننده متنوع است. نمودار برای تبدیل دیدگاه ایجاد شده است که در آن یک سطح مسطح 50 درجه از بیننده متمایل شده و 4٪ نویز تصویر اضافه می شود. این نزدیک به مرزهای تطبیق قابل اعتماد است ، زیرا مهمترین عملکرد توصیف کننده در این موارد دشوارتر است.نتایج نشان دهنده درصد نقاط کلیدی است که مطابقت صحیحی با نزدیکترین همسایه در میان پایگاه داده 40،000 نقطه کلیدی دارند. نمودار نشان می دهد که یک هیستوگرام جهت منفرد (n = 1) در تشخیص بسیار ضعیف است ، اما نتایج همچنان به یک آرایه 4×4 از هیستوگرام با 8 جهت بهبود می یابد. پس از آن ، افزودن جهت های بیشتر یا توصیف کننده بزرگتر با حساسیت بیشتر توصیف کننده به تحریف ، می تواند به مطابقت آسیب برساند. این نتایج برای سایر درجات تغییر دیدگاه و نویز به طور کلی مشابه بود ، اگرچه در موارد ساده تر با 5 * 5 و اندازه توصیف بالاتر ، تبعیض همچنان ادامه داشت (از سطح بالا).در طول این مقاله ما از یک توصیفگر 4×4 با 8 جهت استفاده می کنیم و در نتیجه بردارهای مشخصه با ابعاد 128 ایجاد می کنیم. اگرچه ابعاد توصیف کننده بالا به نظر می رسد ، ما دریافته ایم که عملکرد آن به طور مداوم نسبت به توصیف کننده ابعاد پایین در طیف وسیعی از تطابق بهتر است و هنگام استفاده از روشهای تقریبی همسایه که در زیر توضیح داده شده است ، هزینه محاسباتی تطبیق پایین است.

Sensitivity to affine change
The sensitivity of the descriptor to affine change is examined in Figure 9. The graph shows the reliability of keypoint location and scale selection, orientation assignment, and nearest neighbor matching to a database as a function of rotation in depth of a plane away from a viewer. It can be seen that each stage of computation has reduced repeatability with increasing affine distortion, but that the final matching accuracy remains above 50% out to a 50 degree change in viewpoint… To achieve reliable matching over a wider viewpoint angle, one of the affine-invariant
detectors could be used to select and resample image regions, as discussed in Section 2. As mentioned there, none of these approaches is truly affine-invariant, as they all start from initial feature locations determined in a non-affine-invariant manner. In what appears to be the most affine-invariant method, Mikolajczyk (2002) has proposed and run detailed experiments with the Harris-affine detector. He found that its keypoint repeatability is below that given here out to about a 50 degree viewpoint angle, but that it then retains close to 40% repeatability out to an angle of 70 degrees, which provides better performance for extreme affine changes. The disadvantages are a much higher computational cost, a reduction in the number of keypoints, and poorer stability for small affine changes due to errors in assigning a consistent affine frame under noise. In practice, the allowable range of rotation for 3D objects is considerably less than for planar surfaces, so affine invariance is usually not the limiting factor in the ability to match across viewpoint change. If a wide range of affine invariance is desired, such as for a surface that is known to be planar, then a simple solution is to adopt the approach of Pritchard and Heidrich (2003) in which additional SIFT features are generated from 4 affinetransformed versions of the training image corresponding to 60 degree viewpoint changes.This allows for the use of standard SIFT features with no additional cost when processing the image to be recognized, but results in an increase in the size of the feature database by afactor of 3

حساسیت به تغییر افاین
حساسیت توصیف کننده به تغییر افاین در شکل 9 بررسی شده است. نمودار قابلیت اطمینان مکان نقطه کلیدی و انتخاب مقیاس ، انتساب جهت و تطبیق همسایگی با یک پایگاه داده را به عنوان تابعی از چرخش در عمق صفحه ای دور از یک بیننده نشان می دهد. دیده می شود که هر مرحله از محاسبه با افزایش اعوجاج افاین تکرارپذیری را کاهش می دهد ، اما دقت تطبیق نهایی تطبیق بیش از 50 % تا تغییر 50 درجه در دیدگاه باقی می ماند.برای دستیابی به تطبیق قابل اعتماد با یک زاویه دید وسیع تر ، می توان از یکی از آشکارسازهای مقاوم به افاین برای انتخاب و نمونه برداری از نواحی تصویر استفاده کرد ، همانطور که در بخش 2 مورد بحث قرار گرفت. از ابتدا شروع کنیدمکان های اولیه ویژگی به روشی غیرمقاوم به افاین مشخص کنید . در روشی که به نظر می رسد مقاوم ترین روش نسبت به افاین باشد ، Mikolajczyk (2002) آزمایش های مفصلی را با آشکارسازهریس-آفین پیشنهاد و اجرا کرده است. وی دریافت که تکرارپذیری نقاط کلیدی آن کمتر از زاویه دید 50 درجه در اینجا است ، اما پس از آن نزدیک به 40٪ تکرارپذیری تا زاویه 70 درجه را حفظ می کند ، که عملکرد بهتری را برای اکسترمم ها در افاین فراهم می کند. معایب آن یک هزینه محاسباتی بسیار بالاتر ، کاهش تعداد نقاط کلیدی و ثبات ضعیف تر برای تغییرات کوچک افاین به دلیل اشتباهات در تعیین یک قاب آفین سازگار تحت نویز است. در عمل ، دامنه چرخش مجاز برای اشیا 3D سه بعدی به طور قابل توجهی کمتر از سطوح مسطح است ، بنابراین عدم تغییر شیب معمولاً عامل محدود کننده توانایی مطابقت با تغییر دیدگاه نیست. اگر طیف گسترده ای از عدم تغییر در آیفون مورد نظر باشد ، مثلاً برای سطحی که مسطح شناخته شده است ، یک راه حل ساده این است که رویکرد پریچارد و هیدریش (2003) را اجرا کنید که در آن ویژگی های اضافی SIFT از 4 نسخه تبدیل افاین از تصویر آموزش مربوط به تغییرات دید 60 درجه تولید می شود.این امکان را می دهد تا از ویژگی های استاندارد SIFT بدون هزینه اضافی هنگام پردازش تصویر برای شناسایی استفاده شود ، اما منجر به افزایش اندازه پایگاه داده ویژگی ها با ضریب 3 می شود.

Matching to large databases
An important remaining issue for measuring the distinctiveness of features is how the reliability of matching varies as a function of the number of features in the database being matched. Most of the examples in this paper are generated using a database of 32 images with about 40,000 keypoints. Figure 10 shows how the matching reliability varies as a function of database size. This figure was generated using a larger database of 112 images, with a viewpoint depth rotation of 30 degrees and 2% image noise in addition to the usual random image rotation and scale change… The dashed line shows the portion of image features for which the nearest neighbor in the database was the correct match, as a function of database size shown on a logarithmic scale. The leftmost point is matching against features from only a single image while the rightmost point is selecting matches from a database of all features from the 112 images. It can be seen that matching reliability does decrease as a function of the number of distractors, yet all indications are that many correct matches will continue to be found out to very large database sizes…. The solid line is the percentage of keypoints that were identified at the correct matching location and orientation in the transformed image, so it is only these points that have any chance of having matching descriptors in the database. The reason this line is flat is that the test was run over the full database for each value, while only varying the portion of the database used for distractors. It is of interest that the gap between the two lines is small, indicating that matching failures are due more to issues with initial feature localization and orientation assignment than to problems with feature distinctiveness, even out to large database sizes.

تطبیق با پایگاه های داده بزرگ
یک مسئله مهم باقی مانده برای اندازه گیری متمایز بودن ویژگی ها این است که چگونه قابلیت اطمینان مطابقت به عنوان تابعی از تعداد ویژگی های پایگاه داده مورد تطبیق ، تغییر داد. بیشتر نمونه های این مقاله با استفاده از پایگاه داده ای با 32 تصویر تولید شده است با حدود 40،000 نقطه کلیدی. شکل 10 نشان می دهد که چگونه قابلیت اطمینان مطابقت به عنوان تابعی از اندازه پایگاه داده تغییر می کند. این رقم با استفاده از یک پایگاه داده بزرگتر از 112 تصویر ، با چرخش عمق دید 30 درجه و 2٪ نویز تصویر علاوه بر چرخش تصادفی تصویر و تغییر مقیاس ، ایجاد شده است.خط تیره بخشی از ویژگی های تصویر را نشان می دهد که نزدیکترین همسایه در پایگاه داده مطابقت صحیح با آنها دارد ، به عنوان تابعی از اندازه پایگاه داده که در مقیاس لگاریتمی نشان داده شده است. سمت چپ ترین نقطه مطابقت با ویژگی های فقط یک تصویر است در حالی که سمت راست انتخاب موارد منطبق از پایگاه داده تمام ویژگی ها از 112 تصویر است. دیده می شود که قابلیت اطمینان مطابقت به عنوان تابعی از تعداد عوامل تحریف کاهش می یابد ، اما همه نشانه ها نشان می دهد که بسیاری از موارد منطبق با اندازه های پایگاه داده بسیار بزرگ کشف می شوند.خط ثابت درصدی از نقاط کلیدی است که در مکان و جهت درست تطبیق در تصویر تبدیل شده مشخص شده است ، بنابراین فقط این نقاط هستند که احتمال داشتن توصیف کننده های منطبق در پایگاه داده را دارند. دلیل مسطح بودن این خط این است که آزمون بر روی پایگاه داده کامل برای هر مقدار اجرا شده است ، در حالی که فقط بخشی از پایگاه داده مورد استفاده برای عوامل منحرف کننده تغییر می کند. جالب است که فاصله بین دو خط کم است ، نشان می دهد که عدم تطابق بیشتر به دلیل مشکلات مربوط به محلی سازی اولیه ویژگی و تعیین جهت است تا مشکلات تمایز ویژگی ، حتی در اندازه های پایگاه داده بزرگ.

Application to object recognition
The major topic of this paper is the derivation of distinctive invariant keypoints, as described above. To demonstrate their application, we will now give a brief description of their use for object recognition in the presence of clutter and occlusion. More details on applications of these features to recognition are available in other papers (Lowe, 1999; Lowe, 2001; Se,Lowe and Little, 2002).Object recognition is performed by first matching each keypoint independently to the database of keypoints extracted from training images. Many of these initial matches will be incorrect due to ambiguous features or features that arise from background clutter. Therefore,clusters of at least 3 features are first identified that agree on an object and its pose, as these clusters have a much higher probability of being correct than individual feature matches.Then, each cluster is checked by performing a detailed geometric fit to the model, and the result is used to accept or reject the interpretation.

برنامه شناسایی اشیا
موضوع اصلی این مقاله استخراج نقاط کلیدهای متمایز مقاوم است ، همانطور که در بالا توضیح داده شد. برای نشان دادن کاربرد آنها ، اکنون شرح مختصری از کاربرد آنها برای تشخیص شی در حضور شلوغی و انسداد ارائه می دهیم. جزئیات بیشتر در مورد کاربردهای این ویژگی ها برای شناسایی در سایر مقالات موجود است (Lowe، 1999؛ Lowe، 2001؛ Se، Lowe and Little، 2002). تشخیص شی با اولین تطبیق هر نقطه کلیدی به طور مستقل با پایگاه داده نقاط کلیدی استخراج شده از تصاویر آموزشی انجام می شود. به دلیل ویژگی های مبهم یا ویژگی های مبهم ناشی از بهم ریختگی پس زمینه ، بسیاری از این تطابق های اولیه نادرست خواهند بود. بنابراین ابتدا خوشه هایی با حداقل 3 ویژگی شناسایی می شوند که بر روی یک شی و موقعیت آن اتفاق نظر دارند ، زیرا احتمال درست بودن این خوشه ها بسیار بیشتر از تطابق ویژگی های فردی است. سپس ، هر خوشه با انجام یک تناسب هندسی دقیق با مدل بررسی می شود و از نتیجه برای پذیرش یا رد تفسیر استفاده می شود.

Keypoint matching
The best candidate match for each keypoint is found by identifying its nearest neighbor in the database of keypoints from training images. The nearest neighbor is defined as the keypoint with minimum Euclidean distance for the invariant descriptor vector as was described in Section 6. However, many features from an image will not have any correct match in the training database because they arise from background clutter or were not detected in the training images.Therefore, it would be useful to have a way to discard features that do not have any good match to the database. A global threshold on distance to the closest feature does not perform well, as some descriptors are much more discriminative than others. A more effective measure is obtained by comparing the distance of the closest neighbor to that of the second-closest neighbor. If there are multiple training images of the same object, then we define the second-closest neighbor as being the closest neighbor that is known to come from a different object than the first, such as by only using images known to contain different objects.This measure performs well because correct matches need to have the closest neighbor significantly closer than the closest incorrect match to achieve reliable matching. For false matches, there will likely be a number of other false matches within similar distances due to the high dimensionality of the feature space. We can think of the second-closest match as providing an estimate of the density of false matches within this portion of the feature space and at the same time identifying specific instances of feature ambiguity…. Figure 11 shows the value of this measure for real image data. The probability density functions for correct and incorrect matches are shown in terms of the ratio of closest to second-closest neighbors of each keypoint. Matches for which the nearest neighbor was a correct match have a PDF that is centered at a much lower ratio than that for incorrect matches. For our object recognition implementation, we reject all matches in which the distance ratio is greater than 0.8, which eliminates 90% of the false matches while discarding less than 5% of the correct matches. This figure was generated by matching images following random scale and orientation change, a depth rotation of 30 degrees, and addition of 2% image noise, against a database of 40,000 keypoints

تطبیق نقطه کلیدی
بهترین نامزدها تطابق برای هر نقطه کلیدی با شناسایی نزدیکترین همسایه آن در پایگاه داده از نقاط اکلیدی از تصاویر آموزشی یافت می شود. همانطور که در بخش 6 شرح داده شده است ، نزدیکترین همسایه به عنوان نقطه کلیدی با حداقل فاصله اقلیدسی برای بردار توصیف کننده ثابت تعریف شده است. .با این حال ، بسیاری از ویژگی ها در یک تصویر هیچ تطابق درستی در پایگاه داده آموزشی ندارند در هم ریختگی در بک گراند یا عدم تشخیص در تصاویر آموزشی رخ داده است. بنابراین داشتن روشی برای کنار گذاشتن ویژگی هایی که مطابقت چندان خوبی با پایگاه داده ندارند ، مفید خواهد بود. آستانه جهانی فاصله تا نزدیکترین ویژگی عملکرد خوبی ندارد ، زیرا برخی از توصیف کنندگان بیش از دیگران افتراق آور هستند .با مقايسه فاصله نزديك ترين همسايه با دومين همسايه نزديك تر ، معيار موثرتري بدست مي آيد. اگر چندین تصویر آموزشی از یک جسم وجود داشته باشد ، پس ما همسایه دوم را به عنوان نزدیکترین همسایه تعریف می کنیم که مشخص است از جسمی متفاوت از مورد اول است ، مثلا فقط با استفاده از تصاویر شناخته شده حاوی اشیا مختلف. این معیار به خوبی عمل می کند زیرا تطابقات صحیح باید نزدیکترین همسایه را برای دستیابی به تطبیق قابل اعتماد نسبت به تطبیق نادرست داشته باشد . برای تطابق های کاذب ، به دلیل ابعاد زیاد فضای ویژگی ، احتمالاً تعداد دیگری تطابق نادرست در فواصل مشابه وجود خواهد داشت. ما می توانیم دومین تطبیق نزدیک را به عنوان تخمین تراکم تطابق نادرست در این قسمت از فضای ویژگی و در عین حال شناسایی موارد خاص ابهام ویژگی در نظر بگیریم. شکل 11 مقدار این اندازه گیری را برای داده های تصویر واقعی نشان می دهد. توابع چگالی احتمال برای تطابق صحیح و نادرست از نظر نسبت نزدیکترین به دومین نزدیکترین همسایه از هر نقطه کلیدی نشان داده شده است. تطابق هایی که نزدیکترین همسایه برای آنها مطابقت صحیح دارد دارای PDF هستند که با نسبت بسیار کمتری نسبت به تطابق نادرست در مرکز قرار دارند. برای پیاده سازی شناسایی شی ما ، همه موارد منطبقی را که نسبت فاصله آنها بیشتر از 0.8 باشد ، رد می کنیم ، که 90٪ از موارد منطبق غلط را حذف می کند در حالی که کمتر از 5٪ مطابقت های صحیح را کنار می گذارد. این رقم با تطبیق تصاویر به دنبال تغییر مقیاس و جهت گیری تصادفی ، چرخش عمق 30 درجه و افزودن 2٪ نویز تصویر ، در برابر پایگاه داده 40000 نقطه کلید ایجاد شده است.

Efficient nearest neighbor indexing
No algorithms are known that can identify the exact nearest neighbors of points in high dimensional spaces that are any more efficient than exhaustive search. Our keypoint descriptor has a 128-dimensional feature vector, and the best algorithms, such as the k-d tree (Friedman et al., 1977) provide no speedup over exhaustive search for more than about 10 dimensional spaces. Therefore, we have used an approximate algorithm, called the Best-Bin-First (BBF) algorithm (Beis and Lowe, 1997). This is approximate in the sense that it returns the closest neighbor with high probability…. The BBF algorithm uses a modified search ordering for the k-d tree algorithm so that bins in feature space are searched in the order of their closest distance from the query location.This priority search order was first examined by Arya and Mount (1993), and they provide further study of its computational properties in (Arya et al., 1998). This search order requires the use of a heap-based priority queue for efficient determination of the search order. An approximate answer can be returned with low cost by cutting off further search after a specific number of the nearest bins have been explored. In our implementation, we cut off search after checking the first 200 nearest-neighbor candidates. For a database of 100,000 keypoints, this provides a speedup over exact nearest neighbor search by about 2 orders of magnitude yet results in less than a 5%loss in the number of correct matches. One reason the BBF algorithm works particularly well for this problem is that we only consider matches in which the nearest neighbor is less than 0.8 times the distance to the second-nearest neighbor (as described in the previous section), and therefore there is no need to exactly solve the most difficult cases in which many neighbors are at very similar distances.

نمایه سازی کارآمد نزدیکترین همسایه
هیچ الگوریتمی شناخته نشده است که بتواند نزدیکترین همسایگان نقاط را در فضاهای با ابعاد بالا شناسایی کند که کارآیی بیشتری نسبت به جستجوی جامع دارند. توصیفگرنقاط کلیدی ما دارای بردار ویژگی 128 بعدی است و بهترین الگوریتم ها مانند درخت k-d (فریدمن و همکاران ، 1977) بیش از حدود 10 فضای بعدی هیچ جستجوی جامعی را ارائه نمی دهند. بنابراین ، ما از یک الگوریتم تقریبی استفاده کرده ایم ، بنام Best-Bin-First (BBF)الگوریتم (بیس و لو ، 1997). این از این نظر تقریبی است که نزدیکترین همسایه را با احتمال زیاد برمی گرداند.

الگوریتم BBF از یک ترتیب جستجوی اصلاح شده برای الگوریتم درخت k-d استفاده می کند تا بین های موجود در فضای ویژگی به ترتیب نزدیکترین فاصله خود از مکان پرس و جو جستجو شوند. این دستور اولویت جستجو برای اولین بار توسط Arya and Mount (1993) مورد بررسی قرار گرفت ، و آنها مطالعه بیشتری در مورد خصوصیات محاسباتی آن در (Arya و همکاران ، 1998) ارائه می دهند. این دستور جستجو نیاز به استفاده از یک صف اولویت مبتنی بر heap برای تعیین کارآمد دستور جستجو دارد. با قطع جستجوی بیشتر پس از بررسی تعداد مشخصی از نزدیکترین بین ها ، می توانید پاسخ تقریبی را با هزینه کم برگردانید.در اجرای ما ، پس از بررسی 200 نامزد نزدیکترین همسایه ، جستجو را قطع کردیم. برای یک پایگاه داده از 100000 نقطه کلیدی ، این سرعت بیش از جستجوی دقیقترین همسایه را با حدود 2 مرتبه اندازه فراهم می کند اما در نتیجه کمتر از 5 درصد از دست دادن تعداد مطابقت های صحیح است. یک دلیل که الگوریتم BBF به ویژه برای این مشکل خوب کار می کند این است که ما فقط تطابقات را در نظر می گیریم که در آن نزدیکترین همسایه کمتر از 0.8 برابر فاصله از همسایه نزدیکترین دوم باشد (همانطور که در بخش قبلی توضیح داده شده است) ، و بنابراین نیازی نیست دقیقاً سخت ترین مواردی را که در آن همسایگان در فاصله های بسیار مشابه قرار دارند ، حل کنیم.

Clustering with the Hough transform
To maximize the performance of object recognition for small or highly occluded objects, we wish to identify objects with the fewest possible number of feature matches. We have found that reliable recognition is possible with as few as 3 features. A typical image contains 2,000 or more features which may come from many different objects as well as background clutter. While the distance ratio test described in Section 7.1 will allow us to discard many of the false matches arising from background clutter, this does not remove matches from other valid objects, and we often still need to identify correct subsets of matches containing less than 1% inliers among 99% outliers. Many well-known robust fitting methods, such as RANSAC or Least Median of Squares, perform poorly when the percent of inliers falls much below 50%. Fortunately, much better performance can be obtained by clustering features in pose space using the Hough transform (Hough, 1962; Ballard, 1981; Grimson 1990)…. The Hough transform identifies clusters of features with a consistent interpretation by using each feature to vote for all object poses that are consistent with the feature. When clusters of features are found to vote for the same pose of an object, the probability of the interpretation being correct is much higher than for any single feature. Each of our keypoints specifies 4 parameters: 2D location, scale, and orientation, and each matched keypoint in the database has a record of the keypoint’s parameters relative to the training image in which it was found. Therefore, we can create a Hough transform entry predicting the model location,orientation, and scale from the match hypothesis. This prediction has large error bounds, as the similarity transform implied by these 4 parameters is only an approximation to the full 6 degree-of-freedom pose space for a 3D object and also does not account for any nonrigid deformations. Therefore, we use broad bin sizes of 30 degrees for orientation, a factor of 2 for scale, and 0.25 times the maximum projected training image dimension (using the predicted scale) for location. To avoid the problem of boundary effects in bin assignment, each keypoint match votes for the 2 closest bins in each dimension, giving a total of 16 entries for each hypothesis and further broadening the pose range. .. In most implementations of the Hough transform, a multi-dimensional array is used to represent the bins. However, many of the potential bins will remain empty, and it is difficult to compute the range of possible bin values due to their mutual dependence (for example the dependency of location discretization on the selected scale). These problems can be avoided by using a pseudo-random hash function of the bin values to insert votes into a onedimensional hash table, in which collisions are easily detected.

خوشه بندی با تبدیل هاف
برای به حداکثر رساندن عملکرد تشخیص شی برای اشیا کوچک یا بسیار مسدود ، می خواهیم اشیایی را با کمترین تعداد تطابق ویژگی شناسایی کنیم. ما دریافته ایم که شناخت قابل اعتماد با حداقل 3 ویژگی امکان پذیر است. یک تصویر معمولی شامل 2000 ویژگی یا بیشتر است که ممکن است از اشیا مختلف و همچنین بهم ریختگی پس زمینه حاصل شود. در حالی که آزمون نسبت فاصله توصیف شده در بخش 7.1 به ما امکان می دهد بسیاری از موارد منطبق نادرست ناشی از بهم ریختگی پس زمینه را کنار بگذاریم ، اما این مورد تطابق را از سایر اشیا معتبر حذف نمی کند و ما اغلب هنوز نیاز به شناسایی زیر مجموعه های صحیح موارد منطبق با کمتر از 1٪ داریم Inlier در میان 99٪ پرت کردن. بسیاری از روشهای اتصالات مقاوم معروف ، مانند RANSAC یا Least Median of Squares ، هنگامی که درصد ورودیها خیلی کمتر از 50٪ باشد ، عملکرد ضعیفی دارند. خوشبختانه با خوشه بندی ویژگی ها در فضای ژست با استفاده از تبدیل هاو می توان عملکرد بسیار بهتری را بدست آورد (Hough، 1962؛ Ballard، 1981؛ Grimson 1990).

تبدیل Hough خوشه های ویژگی ها را با یک تفسیر سازگار با استفاده از هر ویژگی برای رأی دادن به همه موقعیت های شی که با ویژگی سازگار هستند ، شناسایی می کند. وقتی مشخص شد که خوشه های ویژگی ها به همان موقعیت یک شی رأی می دهند ، احتمال درست بودن تفسیر بسیار بیشتر از هر ویژگی تک است.هر یک از نقاط کلیدی ما 4 پارامتر را مشخص می کند: مکان 2 بعدی، مقیاس و جهت و هر نقطه کلیدی تطبیق داده شده در پایگاه داده دارای پارامترهای نقطه کلید نسبت به تصویر آموزشی است که در آن یافت شده است. بنابراین ، ما می توانیم یک ورودی تبدیل هاف با پیش بینی مکان ، جهت و مقیاس مدل از فرضیه مطابقت ایجاد کنیم.این پیش بینی خطای مرزی زیادی دارد ، زیرا تبدیل شباهت ضمنی با این 4 پارامتر فقط یک تقریب نسبت به فضای ژست 6 درجه آزادی کامل برای یک شی سه بعدی است و همچنین هیچ گونه تغییر شکل غیر صاف را در بر نمی گیرد. بنابراین ، ما از جهت استفاده از ابعاد گسترده 30 درجه جهت ، ضریب 2 برای مقیاس و 0.25 برابر حداکثر ابعاد تصویر آموزش پیش بینی شده (با استفاده از مقیاس پیش بینی شده) برای مکان استفاده می کنیم.برای جلوگیری از مشکل اثرات مرزی در انتساب بین ، هر تطبیق نقطه کلیدی به 2 نزدیکترین بین در هر بعد رأی می دهد ، در مجموع 16 ورودی برای هر فرضیه ارائه می دهد و دامنه موقعیت را بیشتر گسترش می دهد.

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

The Hough transform is used to identify all clusters with at least 3 entries in a bin. Each such cluster is then subject to a geometric verification procedure in which a least-squares solution is performed for the best affine projection parameters relating the training image to the new image. An affine transformation correctly accounts for 3D rotation of a planar surface under orthographic projection, but the approximation can be poor for 3D rotation of non-planar objects. A more general solution would be to solve for the fundamental matrix (Luong and Faugeras, 1996; Hartley and Zisserman, 2000). However, a fundamental matrix solution requires at least 7 point matches as compared to only 3 for the affine solution and in practice
requires even more matches for good stability. We would like to perform recognition with as few as 3 feature matches, so the affine solution provides a better starting point and we can account for errors in the affine approximation by allowing for large residual errors. If we imagine placing a sphere around an object, then rotation of the sphere by 30 degrees will move no point within the sphere by more than 0.25 times the projected diameter of the sphere. For the examples of typical 3D objects used in this paper, an affine solution works well given that we allow residual errors up to 0.25 times the maximum projected dimension of the object. A more general approach is given in (Brown and Lowe, 2002), in which the
initial solution is based on a similarity transform, which then progresses to solution for the fundamental matrix in those cases in which a sufficient number of matches are found.

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

یک تغییر شکل آیفین به درستی چرخش سه بعدی یک سطح مسطح را تحت برآورد ارتوگرافی محاسبه می کند ، اما برای چرخش سه بعدی اجسام غیر مسطح تقریب می تواند ضعیف باشد. یک راه حل کلی تر ، حل ماتریس اساسی است (Luong and Faugeras، 1996؛ Hartley and Zisserman، 2000).با این حال ، یک راه حل ماتریس اساسی به حداقل 7 امتیاز تطبیق در مقایسه با فقط 3 برای راه حل affine نیاز دارد و در عمل حتی برای ثبات خوب به تطابقات بیشتری نیاز دارد. ما می خواهیم با 3 تطبیق از ویژگی ها تشخیص را انجام دهیم ، بنابراین راه حل affine نقطه شروع بهتری را فراهم می کند و ما می توانیم با اجازه دادن به خطاهای بزرگ باقیمانده ، خطاهای مربوط به تقریب اافاین را حساب کنیم.اگر تصور کنیم که کره ای را به دور یک جسم قرار می دهیم ، چرخش کره به میزان 30 درجه هیچ نقطه ای از کره را با بیش از 0.25 برابر قطر پیش بینی شده کره منتقل نخواهد کرد. برای مثالهایی از اشیا 3D سه بعدی معمولی که در این مقاله استفاده می شود ، با توجه به اینکه خطاهای باقیمانده را تا 0.25 برابر حداکثر ابعاد پیش بینی شده جسم مجاز می دانیم ، یک راه حل afine به خوبی کار می کند. یک رویکرد کلی تر در (براون و لوو ، 2002) ارائه شده است ، که در آن راه حل اولیه مبتنی بر یک تغییر شباهت است ، و سپس در مواردی که تعداد کافی تطابق پیدا می شود به راه حل برای ماتریس اساسی می رسد.

که مجموع مربعات فواصل از مکانهای مدل پیش بینی شده تا مکانهای تصویر مربوطه را به حداقل می رساند. این رویکرد حداقل مربعات را می توان به راحتی برای حل وضعیت 3D و پارامترهای داخلی اشیا مفصلی و انعطاف پذیر گسترش داد (Lowe، 1991).

با بررسی توافق بین هر یک از ویژگی های تصویر و مدل ، اکنون می توان موارد پرت را حذف کرد. با توجه به دقیق ترین راه حل حداقل مربعات ، اکنون لازم است که هر تطبیق در نیمی از محدوده خطایی که برای بین های پارامترهای تبدیل Hough استفاده شده است توافق کنیم اگر بعد از دور انداختن موارد پرت کمتر از 3 امتیاز باقی بماند ،تطبیق رد می شود. با دور ریختن پرت ها ، راه حل حداقل مربعات با نقاط باقی مانده دوباره حل می شود و روند تکرار می شود. علاوه بر این ، از یک مرحله تطبیق بالا به پایین برای افزودن موارد منطبق دیگر که با موقعیت مدل پیش بینی شده موافقت می کنند ، استفاده می شود. اینها ممکن است به دلیل تقریب تبدیل شباهت یا خطاهای دیگر از بین تبدیل Hough فراموش شده باشند.تصمیم نهایی در مورد پذیرش یا رد یک فرضیه مدل بر اساس یک مدل احتمالی دقیق ارائه شده در مقاله قبلی است (Lowe، 2001). این روش ابتدا با توجه به اندازه پیش بینی شده مدل، ، تعداد مورد انتظار تطابق نادرست را با حالت مدل , تعداد ویژگی های موجود در منطقه و دقت مناسب بودن محاسبه می کند. سپس یک تجزیه و تحلیل بیزی احتمال حضور شی را بر اساس تعداد واقعی ویژگیهای مطابقت یافته پیدا می کند. اگر احتمال نهایی برای تفسیر صحیح بیشتر از 0.98 باشد ، ما یک مدل را قبول می کنیم.برای اشیائی که به مناطق کوچک یک تصویر پیش بینی می شوند ، 3 ویژگی ممکن است برای شناسایی قابل اعتماد کافی باشد. برای اشیا بزرگ که بیشتر یک تصویر با بافت بسیار زیاد را پوشش می دهد ، تعداد مورد انتظار تطابق کاذب بیشتر است و ممکن است 10 تطابق ویژگی ضروری باشد.

نتیجه

نقاط کلیدی SIFT که در این مقاله توضیح داده شده اند به ویژه به دلیل متمایز بودن بسیار مفید هستند ، این امر باعث می شود تا مطابقت صحیح برای یک نقطه کلیدی از یک پایگاه داده بزرگ از سایر کلیدهای کلیدی انتخاب شود. این متمایز بودن با جمع آوری یک بردار با ابعاد بالا که نمایانگر شیب های تصویر در یک منطقه محلی از تصویر است ، حاصل می شود. نشان داده شده است كه نقاط کلیدی در چرخش و مقیاس تصویر ثابت هستند و در طیف وسیعی از اعوجاج افاین ، افزودن نویز و تغییر در نور قوی هستند. تعداد زیادی نقاط کلیدی می تواند از تصاویر معمولی استخراج شود ، که منجر به استحکام کمتری در استخراج اشیا کوچک در میان بی نظمی می شود. این واقعیت که نقاط کلیدی در طیف کاملی از مقیاس ها شناسایی می شوند ، به این معنی است ویژگی های کوچک محلی برای تطبیق اشیا کوچک و بسیار مسدود موجود است ، در حالی که کلیدهای بزرگ برای تصاویر تحت نویز و تاری عملکرد خوبی دارند. محاسبه آنها کارآمد است ، به طوری که می توان چند هزار نقطه کلیدی را از یک تصویر معمولی با عملکرد تقریباً بلادرنگ در سخت افزار رایانه استاندارد استخراج کرد.در این مقاله روشهایی برای استفاده از نقاط کلیدی برای تشخیص شی ارائه شده است. رویکردی که توصیف کردیم از جستجوی تقریبی نزدیکترین همسایه ، تبدیل Hough برای شناسایی خوشه هایی که در مورد موقعیت جسم توافق دارند ، تعیین ژست حداقل مربعات و تأیید نهایی استفاده می کند. سایر کاربردهای بالقوه شامل تطبیق دید برای بازسازی سه بعدی ، ردیابی حرکت و تقسیم بندی ، موقعیت ربات ، مونتاژ پانورامای تصویر ، کالیبراسیون اپی قطبی و سایر مواردی است که نیاز به شناسایی مکان های منطبق بین تصاویر دارد.جهت استخراج ویژگیهای تصویر متغیر و متمایز، جهت تحقیق بیشتر جهت های زیادی وجود دارد. آزمایش سیستماتیک بر روی مجموعه داده ها با دید کامل 3D و تغییرات روشنایی مورد نیاز است. ویژگی های توصیف شده در این مقاله فقط از یک تصویر با شدت تک رنگ استفاده می کنند ، بنابراین می توان متمایز بودن بیشتری را از جمله توصیف رنگهای ثابت تغییر داد.