SIFT Descriptor: Image Feature Encoding

Local Descriptors

• When interest regions from an image are extracted, their content gets encoded in a descriptor suitable for discriminative matching.
• The SIFT descriptor (Lowe 2004) is the most popular choice for describing local features.
• The Scale Invariant Feature Transform (SIFT) was first introduced by Lowe using a DoG interest region detector and a feature descriptor.

SIFT Descriptor

• Descriptor computation starts from a scale and rotation normalized region using one of the above-mentioned detectors.
• As a first step, the image gradient magnitude and orientation is sampled around the keypoint location to select the level of Gaussian blur using the Gaussian pyramid.
• Sampling is performed in a regular grid of 16 × 16 locations to cover the interest region.
• For each sampled location, the gradient orientation goes into a coarser 4 × 4 grid of gradient orientation histograms with 8 orientation bins
• The histograms get weighted by the corresponding pixel's gradient magnitude and a circular Gaussian weighting function with a σ of half the region size.
• The weighting function gives higher weights to pixels closer to the region's middle, which are less affected by localization inaccuracies.
• For each (orientation normalized) scale invariant region, image gradients get sampled in a regular grid
• These are then entered into a larger 4 × 4 grid of local gradient orientation histograms

SURF Detector/Descriptor

• The SURF (“Speeded-Up Robust Features") approach has been designed as an efficient alternative to SIFT (Bay et al. 2006, 2008).
• Computation is based on simple 2D box filters, which are efficiently evaluated using integral images.
• SURF combines a Hessian-Laplace region detector with a gradient orientation-based feature descriptor.
• It is based on simple 2D box filters ("Haar wavelets"), which approximate the effects of the derivative filter kernels.

Matching Local Features

• An image's local features should be able to be matched to similar-looking local features (e.g., to model images of the specific objects being recognized).
• To identify candidate matches, search among all previously seen local descriptors, and retrieve those that are nearest according to Euclidean distance in the feature space.
• The basic solution 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 in terms of computational complexity.
• Efficient algorithms for nearest neighbor or similarity search are crucial in many practical applications that involve searching for matches in a database of millions of features.
• The goal when matching local features is to find descriptors from any previously seen exemplary model, which are present in the feature space close to those in a novel image.
• Since each exemplar image may have hundreds to thousands of interest points, the database expands quickly and must be mapped to data structures to allow for efficient similarity search.

Efficient Similarity Search

• TREE-BASED ALGORITHMS
• The kd-tree is a binary tree storing a database of k-dimensional points in its leaf nodes, and recursively partitions the points into axis aligned cells.
• It divides the points approximately in half by a perpendicular line to one of the k coordinate axes.
• Division strategies aim to maintain balanced trees and/or uniformly shaped cells by choosing the axis to split according to the one with largest variance among the database points, or cycling through the axes in order.
• To find the point nearest to some query, traverse the tree using the divisions used to enter the database points, and comparing points to the query.
• The nearest one becomes the "current best".
• The search continues by backtracking along the unexplored branches to check if the circle formed by the query/radius intersects with a subtree's cell area.
• If it does, any nearer points found as the search recurses are used to update the current best, if not 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 exist because of inadequacies in existing nearest-neighbor techniques that provide sub-linear time search for high-dimensional data.
• Approximate similarity search trades off some precision for faster query times.
• Locality-sensitive hashing (LSH) is one such algorithm that offers sub-linear time search by hashing highly similar examples.
• LSH uses randomized hash functions that map similar inputs to the same bucket with high probability, then searches the colliding database examples to find those most probable to lie in the input's near neighborhood.

A Rule of Thumb for Reducing Ambiguous Matches

• Real-world images will have features stem from background clutter and no meaningful neighbor in the other set.
• Other features on repetitive structures may have ambiguous matches (e.g., a building with many identical windows).
• It is necessary to distinguish reliable matches from unreliable ones, as descriptors are more discriminative than others.
• One strategy (by 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.
• Check for the nearest neighbor local feature originating from an exemplar in the database of training images, then consider the second nearest neighbor that originates from a different object than the nearest neighbor feature.
• The match may be ambiguous if the ratio of the distance to the first neighbor over the distance to the second neighbor is large, or reliable if the ratio is low.

Indexing Features With Visual Vocabularies

• A visual vocabulary draws inspiration from the text retrieval community and enables efficient indexing for local image features.
• The idea is to quantize the local feature space versus preparing a tree or hashing data structure to aid in direct similarity search.
• The local descriptors get mapped to discrete tokens, which can then be "matched" by looking up features assigned to the identical token.