SIFT Descriptor for Image Analysis

Local Descriptors

• After interest regions are extracted from an image, their content needs to be encoded in a descriptor for discriminative matching.
• The SIFT descriptor (Lowe 2004) is the most popular choice for this encoding.
• The Scale Invariant Feature Transform (SIFT) was introduced by Lowe as a DoG detector and feature descriptor combination.

SIFT Descriptor

• The descriptor computation begins with a scale and rotation normalized region.
• Image gradient magnitude and orientation is sampled, selecting the Gaussian blur level using the region scale.
• Sampling occurs in a regular grid of 16 × 16 locations covering the interest region.
• Gradient orientation is entered into a 4 × 4 grid of orientation histograms with 8 orientation bins.
• Orientation histograms are weighted by the corresponding pixel's gradient magnitude and a circular Gaussian weighting function, with a σ of half the region size.
• A Gaussian window gives higher weights to pixels closer to the middle, reducing the impact of small localization inaccuracies.
• For each (orientation normalized) scale invariant region, image gradients are sampled in a regular grid and are then entered into a larger 4 × 4 grid of local gradient orientation histograms.

SURF Detector/Descriptor

• The SURF ("Speeded-Up Robust Features") approach is an efficient alternative to SIFT developed by Bay et al. in 2006 and 2008.
• Computation is based on simple 2D box filters evaluated using integral images rather than ideal Gaussian derivatives.
• SURF combines a Hessian-Laplace region detector with a gradient orientation-based feature descriptor.
• Internal computations are based on simple 2D box filters ("Haar wavelets") which approximate derivative filter kernel effects, efficiently evaluated using integral images.

Matching Local Features

• Local features must be matched to similar features in other images to recognize objects.
• Identifying candidate matches requires searching previously seen local descriptors and retrieving those nearest by Euclidean distance.
• A naive solution of scanning all descriptors is often computationally unrealistic.
• In practical applications with millions of features, efficient nearest neighbor or similarity search algorithms are crucial.
• The goal when matching local features is to find descriptors from any previously seen model that are near in the feature space to those local features in a novel image.
• Since each exemplar image may easily contain on the order of hundreds to thousands of interest points, the database of descriptors quickly becomes very large and must be mapped to data structures for efficient similarity search.

Efficient Similarity Search

• Tree-Based Algorithms
• Kd-trees, a type of binary tree, store databases of k-dimensional points in leaf nodes.
• Kd-trees recursively partition points into axis-aligned cells, dividing points approximately in half using a line perpendicular to a coordinate axis.
• Kd-tree division strategies aim to maintain balanced trees/uniformly shaped cells, which involves either splitting a next axis according to largest variance among the database points, or axes cycling in order.
• To find the point nearest to a query, the tree is traversed following the same divisions applied to the database points; at a leaf node, found points are compared to the query.
• The nearest point becomes the initial "current best", despite not necessarily being the absolute nearest.
• Next, backtracking occurs along unexplored branches, checking if the circle formed about the query intersects with a subtree's cell area using the "current best" radius
• If the circle does intersect, that subtree is considered further, and nearer points update the "current best"; if not, the subtree can be pruned.

Hashing-Based Algorithms and Binary Codes

• Hashing algorithms provide an effective alternative to tree-based data structures.
• Existing exact nearest-neighbor techniques are inadequate for providing sub-linear time searches on high-dimensional data.
• Randomized approximate hashing-based similarity search algorithms have been explored.
• Approximate similarity search aims to trade off some precision for substantial query time reductions.
• Locality-sensitive hashing (LSH) offers sub-linear time search by hashing similar examples together in a hash table.
• LSH hashing guarantees that randomized hash functions will map inputs to the same bucket with high probability if they are similar.
• Given a new query, only the colliding database examples need searching to find those most probable to lie in the inputs near neighborhood.

A Rule of Thumb for Reducing Ambiguous Matches

• When matching local feature sets extracted from real-world images, some features will stem from background and have no meaningful neighbor in the other set.
• Other features on repetitive structures may have ambiguous matches, for example, identical windows will be ambiguous.
• Must reliably distinguish matches, unable to use descriptor distance alone.
• An often-used strategy (initially proposed by Lowe (2004)) uses the ratio of the distance to the closest neighbor to the distance to the second-closest one as a decision criterion.
• Identify the nearest neighbor local feature originating from an exemplar in the database of training images, and then consider the second nearest neighbor that originates from a different object than the nearest neighbor feature.
• Ratio-based match: A large ratio suggests ambiguity, and a low ratio suggests a reliable match.

Indexing Features With Visual Vocabularies

• The visual vocabulary strategy draws inspiration from text retrieval, enabling efficient indexing for local image features.
• The local feature space is quantized instead of preparing a tree or hashing data structure to aid in direct similarity search.
• By mapping local descriptors to discrete tokens, they can be ""matched"" by looking up features assigned to identical tokens.