SIFT Descriptor

Local Descriptors

• Encoding the content from extracted regions is necessary for discriminative matching.
• The SIFT descriptor (Lowe 2004) is a popular choice for this step.
• The original SIFT was introduced by Lowe using a Difference of Gaussians (DoG) interest region detector and a corresponding feature descriptor.

SIFT Descriptor

• The descriptor computation starts from a scale and rotation normalized region extracted with one of the above-mentioned detectors.
• Image gradient magnitude and orientation is sampled around the keypoint location.
• Region scale is used to select the Gaussian blur level, i.e., the level of the Gaussian pyramid at which this computation is performed.
• Sampling is performed in a regular grid of 16 x 16 locations covering the interest region.
• The gradient orientation is entered into a coarser 4x4 grid of gradient orientation histograms with 8 orientation bins.
• Weighting is by the corresponding pixel's gradient magnitude and by a circular Gaussian weighting function with a oof half the region size.
• Higher weights are assigned to pixels closer to the middle to give more importance to the region, which are less affected by small localization inaccuracies of the interest region detector.
• Image gradients are sampled in a regular grid and entered into a larger 4×4 grid of local gradient orientation histograms for each orientation normalized scale invariant region.

SURF Detector/Descriptor

• The Speeded-Up Robust Features (SURF) approach is an efficient alternative to SIFT (Bay et al. 2006, 2008).
• Computation is based on simple 2D box filters, which can be efficiently evaluated using integral images, rather than ideal Gaussian derivatives.
• SURF combines a Hessian-Laplace region detector with its own gradient orientation-based feature descriptor.
• It is based on simple 2D box filters ("Haar wavelets") instead of Gaussian derivatives for its internal computations.
• The box filters approximate the effects of the derivative filter kernels but can be efficiently evaluated using integral images.

Matching Local Features

• Given an image and its local features, it is important to match them to similar-looking local features in other images to model specific objects for recognition.
• Goal is to search among all previously seen local descriptors to identify candidate matches, and retrieve those that are nearest according to Euclidean distance in the feature space.
• The naive solution is to scan through all previously seen descriptors, compare them to the current input descriptor, and take those within some threshold as candidates.
• A linear-time scan is usually unrealistic computationally, therefore efficient algorithms for the nearest neighbor or similarity search are crucial.
• The goal when matching local features is to find those descriptors from any previously seen model (exemplar) that are near in the feature space to those local features in a novel image.
• The database of descriptors quickly becomes very large, because each exemplar image may contain on the order of hundreds to thousands of interest points.
• To make searching for matches practical, the database must be mapped to data structures for efficient similarity search.

Efficient Similarity Search

• Tree-based algorithms and Hashing-based algorithms are effective alternative to tree-based data structures

Tree-Based Algorithms

• The kd-tree is a binary tree storing a database of k-dimensional points in its leaf nodes.
• Partitioning is done recursively into axis-aligned cells, dividing the points approximately in half by a line perpendicular to one of the kcoordinate axes.
• Division strategies aim to maintain balanced trees and/or uniformly shaped cells.
• The next axis to split is chosen according to that which has the largest variance among the database points, or by cycling through the axes in order.
• Traversing the tree following the divisions used to enter database points finds the point nearest to some query.
• Points are compared to the query upon reaching a leaf node.
• The nearest one becomes the "current best".
• Continuing the search includes backtracking along unexplored branches, checking whether the circle formed about the query by the radius given by the current best match intersects with a subtrees cell area.
• If the subtree is considered further and any nearer points found as the search recurses are used to update the current best, the subtree can be pruned.

Hashing-Based Algorithms and Binary Codes

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

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.
• Other features lie on repetitive structures and may therefore have ambiguous matches.
• It is important to distinguish reliable matches from unreliable ones, which cannot be done with the descriptor distance alone.
• The ratio of the distance to the first neighbor over the distance to the second neighbor should be relatively large as a sign that the match may be ambiguous; if low it suggests that it's reliable.
• An often-used strategy (Lowe, 2004) is to consider the ratio of the distance to the closest neighbor to that of the second-closest one as a decision criterion.
• Specifically, the nearest neighbor local feature originating from an exemplar in the database of training images is identified.
• Then, the second-nearest neighbor originating from a different object than the nearest neighbor feature is considered.

Indexing Features With Visual Vocabularies

• A visual vocabulary takes inspiration from the text retrieval community andenables efficient indexing for local image features.
• Rather than using 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, they can be matched by simply looking up features assigned to the identical token.