SIFT Descriptor

Local Descriptors

• After extracting regions of interest from an image, encode the content in a descriptor suitable for discriminative matching
• The SIFT descriptor, introduced by Lowe, is commonly used
• Scale Invariant Feature Transform (SIFT) combines a DoG interest region detector with a feature descriptor

SIFT Descriptor

• Compute the descriptor from a scale and rotation normalized region extracted with one the detectors
• Image gradient magnitude and orientation is sampled around the keypoint
• The region scale selects the level of Gaussian blur, to select the level of the Gaussian pyramid on which this computation is performed
• Sample in a grid of 16 × 16 locations covering interest region
• Enter gradient orientation into a grid of 4 × 4 gradient orientation histograms, each with 8 orientation bins
• Gradients are weighted by the pixel's gradient magnitude
• Apply a circular Gaussian weighting function with a σ of half the region size
• The Gaussian window weights pixels closer to the middle of the region higher to reduce localization inaccuracies

SURF Detector/Descriptor

• SURF ("Speeded-Up Robust Features") allows for an efficient alternative to SIFT
• Instead of using ideal Gaussian derivatives, computation uses 2D box filters evaluated using intergral images
• Hessian-Laplace region detector is combined with a gradient orientation-based feature descriptor
• Simple 2D box filters (Haar wavelets) that approximate the effects of derivative filter kernels are used

Matching Local Features

• Images and local features are needed to match similar-looking local features in other images
• Match local features to model images of objects
• Search all previously seen local descriptors to identify candidate matches and retrieve the nearest according to Euclidean distance
• All previously tested seen descriptors compared to the input descriptors selects candidates within a threshold
• Linear-time scanning may be unrealistic due to computational complexity.
• Due to a large number of features, algorithms for nearest neighbor or similarity search are crucial to reduce complexity
• Matching finds descriptors from previous models nearest local features in a novel image
• Map database must be mapped for efficient similarity search to deal with interest points for exemplar images

Efficient Similarity Search

• Tree-Based Algorithms are used for efficient search
• Kd-tree is a binary tree storing k-dimensional points in leaf nodes that recursively partitions points into aligned cells
• Tree cuts the points in half, by a line perpendicular to one of the k coordinate axes
• Division strategies maintain balanced trees and or uniformly shaped cells
• Choose next axis to split according to the largest variance among the database points, or by cycling through the axes

Searching the Tree

• Find the point nearest to a query by traversing the tree following the divisions that were used to enter the database points
• Then, compare the found nodes to the query
• The nearest point becomes the "current best"
• The query does not need to be the absolute nearest; point is close to the initial dividing split on the tree
• The search backtracks along unexplored branches
• The circle formed about the query by the radius intersects a subtree's cell area
• If subtree is considered, any nearer points found update the current best; otherwise the subtree is pruned

Hashing-Based Algorithms and Binary Codes

• Hashing algorithms provide an alternative to tree-based data structures
• Randomized approximate hashing-based similarity search algorithms explore sub-linear time search for high-dimensional data
• Approximate similarity searches trade off precision for query time reductions
• Locality-sensitive hashing (LSH) provides sub-linear time via hash table mapping
• It uses randomized hash function to map two inputs to the same bucket with high probability as long as they are similar
• Then, given a new query, the colliding database examples are searched to find those most probable to lie in the input's near neighborhood

Rule of Thumb for Reducing Ambiguous Matches

• Matching local feature sets from real-world images will contain background clutter with no neighbor in other sets
• Other feature on repetitive structure may have ambiguous matches, such as in an image w/ windows
• A way to distinguish reliable matches from unreliable ones cannot be done by descriptor distances alone, thus some descriptors discriminate
• An often-used strategy considers the ratio of the distance to the closest neighbor to that of the second-closest as a decision criterion
• Identify the nearest neighbor local feature originating from an exemplar in the database, then consider the second nearest neighbor from a different object
• If the ratio of the distance to the first neighbor is larger, that can be ambiguous; if ratio is low, is a reliable match

Indexing Features with Visual Vocabularies

• Visual vocabulary is a strategy which enables indexing for local image features
• Rather than preparing a tree or use hashing to aid in direct similarity search, it quantizes the local feature space
• By mapping local descriptors to discrete tokens, they can be "matched" by looking up features assigned to the identical token