SIFT Descriptor

Local Descriptors

• Encoding content into a descriptor is needed for discriminative matching once a set of interest regions has been extracted from an image.
• The SIFT descriptor (Lowe 2004) is a popular choice for this encoding step.
• The Scale Invariant Feature Transform (SIFT) was introduced by Lowe which combines a DoG interest region detector and a feature descriptor.

SIFT Descriptor

• The computation of the descriptor starts from a scale and rotation normalized region which is extracted with one of the above-mentioned detectors.
• As a first step, the image gradient magnitude and orientation is sampled around the keypoint location.
• Region scale is used to select the level of Gaussian blur
• Sampling is performed in a regular grid of 16 × 16 locations over the interest region.
• The gradient orientation is entered into a coarser 4 × 4 grid of gradient orientation histograms with 8 orientation bins each, weighted by the corresponding pixel's gradient magnitude and by a circular Gaussian weighting function with a σ of half the region size for each sampled location.
• The purpose of the Gaussian window is to give higher weights to pixels closer to the middle of the region, which are less affected by small localization inaccuracies of the interest region detector.
• Gradients are sampled from image in regular grid and entered into 4 x 4 grid of local gradient orientation histograms for each (orientation normalized) scale invariant region.

SURF Detector/Descriptor

• SURF ("Speeded-Up Robust Features") is an efficient alternative to SIFT (Bay et al. 2006, 2008).
• Instead of relying on ideal Gaussian derivatives, its computation is based on simple 2D box filters, which can be efficiently evaluated using integral images.
• SURF combines a Hessian-Laplace region detector with its own gradient orientation-based feature descriptor.
• Internally, it is based on simple 2D box filters ("Haar wavelets").

Matching Local Features

• It is essential to match an image and its local features to similar-looking local features in other images to be able to model images of objects.
• To identify candidate matches, search previously seen local descriptors and retrieve those that are nearest according to Euclidean distance in the feature space.
• The naive solution to identifying local feature matches is to scan through all previously seen descriptors, compare them to the current input descriptor, and take those within some threshold as candidates.
• Linear-time scan is unrealistic because efficient algorithms for nearest neighbor or similarity search are crucial for matches in a database of millions of features

Efficient Similarity Search

• The goal is to find descriptors from any previously seen model (exemplar) that are near in the feature space to those local features in a novel image.
• Each exemplar image may easily contain on the order of hundreds to thousands of interest points.
• The database must be mapped to data structures for efficient similarity search as a result of the database of descriptors becoming very large.

Tree-Based Algorithms

• The kd-tree is a binary tree storing a database of k-dimensional points in its leaf nodes.
• It recursively partitions the points into axis aligned cells, dividing the points approximately in half by a line perpendicular to one of the k coordinate axes.
• The division strategies aim to maintain balanced trees and/or uniformly shaped cells, by cycling through the axes in order or choosing the axis to split with the largest variance among the database points.
• Upon reaching a leaf node, the points there are compared to the query by traversing the tree following the same divisions that were used to enter the database points to find the point nearest to a query.
• The nearest one becomes the "current best."
• The search continues by backtracking along the unexplored branches and checking if the circle formed about the query by the radius of the current best match intersects the subtree's cell area, as the point might not be the absolute nearest.
• If it does, that subtree is considered further, and any nearer points found as the search recurses are used to update the current best, otherwise, the subtree can be pruned.

Hashing-Based Algorithms and Binary Codes

• Hashing algorithms are an effective alternative to tree-based data structures.
• Randomized approximate hashing-based similarity search algorithms have been explored, due to the inadequacy of existing exact nearest-neighbor techniques to provide sub-linear time search for high-dimensional data.
• The idea in approximate similarity search trades off some precision in the search for the sake of query time reductions
• Locality-sensitive hashing (LSH) offers sub-linear time search by hashing highly similar examples together in a hash table.
• One only needs to search the colliding database examples to find those that are probable to lie in the input's near neighborhood where a randomized hash function will map two inputs to the same bucket with high probability if they are similar.

A Rule of Thumb for Reducing Ambiguous Matches

• When matching local feature sets extracted from real-world images, many features will stem from background clutter and will therefore have no meaningful neighbor in the other set.
• Features lie on repetitive structures and may therefore have ambiguous matches (imagine an image containing a building with many identical windows).
• A way to distinguish reliable matches from unreliable is needed, as they cannot be done based on the descriptor distance alone because some descriptors are more discriminative than others.
• To consider the ratio of the distance to the closest neighbor to that of the second-closest one proposed by Lowe (2004) is an often-used strategy.
• The nearest neighbor local feature from an exemplar in the database of training images is specifically identified, and then consider the second nearest neighbor that originates from a different object than the nearest neighbor feature.
• If the ratio of the distance to the first neighbor over the distance to the second neighbor is relatively large, the match may be ambiguous. If the ratio is low, it is a reliable match.

Indexing Features With Visual Vocabularies

• A visual vocabulary draws inspiration from the text retrieval community.
• A visual vocabulary enables efficient indexing for local image features.
• Instead of preparing a tree or hashing data structure to aid in direct similarity search, the idea is to quantize the local feature space.
• By mapping the local descriptors to discrete tokens, "matching" can be done by looking up features assigned to the identical token.