SIFT Descriptor: Image Feature Encoding

Local Descriptors

• After extracting regions of interest from an image, their content must be encoded in a descriptor suitable for discriminative matching.
• The SIFT descriptor is the most popular choice for this encoding step (Lowe 2004).

SIFT Descriptor

• The Scale Invariant Feature Transform (SIFT) was introduced by Lowe as a combination of a Difference of Gaussians (DoG) interest region detector and a feature descriptor

SIFT Descriptor Computation

• Descriptor computation begins with a scale and rotation normalized region extracted from one of the aforementioned detectors.
• The image gradient magnitude and orientation are sampled around a keypoint using the region scale to select the Gaussian blur level.
• Sampling occurs on a regular 16 × 16 grid covering the interest region.
• For each sample, the gradient orientation is entered into a 4×4 grid of gradient orientation histograms with 8 orientation bins each.
• These bins are weighted by the pixel's gradient magnitude and a circular Gaussian weighting function with a σ of half the region size.
• The Gaussian window gives higher weights to pixels closer to the middle of the region to reduce the impact of small localization inaccuracies.

SURF Detector/Descriptor

• SURF ("Speeded-Up Robust Features") is an efficient alternative to SIFT (Bay et al. 2006, 2008).
• SURF relies on simple 2D box filters for computation instead of relying on ideal Gaussian derivatives.
• It efficiently uses integral images and combines a Hessian-Laplace region detector with a gradient orientation-based feature descriptor.
• SURF internals use simple 2D box filters ("Haar wavelets") instead of the Gaussian derivatives, and approximate the effects of derivative filter kernels for efficiency.

Matching Local Features

• Given an image and its local features, these features are matched against similar-looking local features in other images.
• Candidate matches are identified by searching for the nearest local descriptors according to Euclidean distance in the feature space.
• A basic solution involves scanning all previously seen descriptors, comparing them to the current input descriptor, and selecting those within a threshold.
• This linear-time scan approach is often computationally unrealistic, especially with millions of features in practical applications.
• Efficient algorithms for nearest neighbor or similarity search become crucial in such cases.

Efficient Similarity Search: Tree-Based Algorithms

• The kd-tree is a binary tree that stores a database of k-dimensional points in its leaf nodes.
• It recursively divides the points into axis-aligned cells using lines perpendicular to one of the k coordinate axes.
• Division strategies aim to maintain balanced trees and uniformly shaped cells, for example, by splitting along the axis with the largest variance or cycling through axes.
• The nearest point to a query is found by traversing the tree and comparing points in leaf nodes.
• The closest point becomes the initial "current best".
• The search backtracks along unexplored branches to check for intersections between the query circle and subtree cell areas.
• If there's an intersection, the subtree is considered, and nearer points update the current best; otherwise, the subtree is pruned.

Hashing-Based Algorithms and Binary Codes

• Hashing algorithms provide effective alternatives to tree-based data structures.
• Randomized approximate hashing-based similarity search algorithms address the inadequacy of exact nearest-neighbor techniques for high-dimensional data.
• Approximate similarity search trades precision for reduced query time.
• Locality-sensitive hashing (LSH) offers sub-linear time search by hashing similar examples together in a hash table.
• LSH assumes that a randomized hash function will map similar inputs to the same bucket with high probability.
• With a new query, only colliding database examples need to be searched.

Rule of Thumb for Reducing Ambiguous Matches

• When matching local feature sets from real-world images, many features stem from background clutter, lacking meaningful neighbors in another set.
• Other features may have ambiguous matches due to repetitive structures, like identical windows on a building.
• Distinguishing reliable matches from unreliable ones based on descriptor distance alone is insufficient, as some descriptors are more discriminative.

Strategy for Reducing Ambiguous Matches

• An often-used strategy, initially proposed by Lowe (2004), uses the ratio of the distance to the closest neighbor to that of the second-closest one.
• The nearest neighbor local feature originating from an exemplar in training images is identified.
• The second nearest neighbor originating from a different object is also considered.
• A relatively large ratio of the distance to the first neighbor over the distance to the second neighbor suggests an ambiguous match.
• A low ratio indicates a reliable match.

Indexing Features with Visual Vocabularies

• The visual vocabulary approach is strategy inspired by text retrieval.
• It allows efficient indexing for local image features.
• The local feature space is quantized rather than preparing tree or hashing data structures for direct similarity search.
• Local descriptors are mapped to discrete tokens to "match" features by looking them up by identical token.