Visual Object Recognition: SIFT Descriptor

• Visual Object Recognition is the main topic

Local Descriptors

• Once a set of interest regions has been extracted from an image, their content needs encoding in a descriptor suitable for discriminative matching.
• The most popular option for this step is the SIFT descriptor (Lowe 2004).
• The Scale Invariant Feature Transform (SIFT) was originally introduced by Lowe as a combination of a 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 using the region scale to select the level of Gaussian blur.
• Sampling is performed in a regular grid of 16 × 16 locations covering the interest region.
• For each sampled location, the gradient orientation is entered into a coarser 4 × 4 grid of gradient orientation histograms with 8 orientation bins each, weighted by the corresponding pixel's gradient magnitude and by a circular Gaussian weighting function with a σ of half the region size.
• The purpose of this Gaussian window is to give higher weights to pixels closer to the middle of the region, which are less affected by small localization inaccuracies of the interest region detector.
• Image gradients are sampled in a regular grid and are then entered into a larger 4 × 4 grid of local gradient orientation histograms for each (orientation normalized) scale invariant region.

SURF Detector/Descriptor

• The SURF ("Speeded-Up Robust Features") approach has been designed as an efficient alternative to SIFT (Bay et al. 2006, 2008).
• Instead of relying on ideal Gaussian derivatives, its computation is based on simple 2D box filters, which can be efficiently evaluated using integral images.
• SURF combines a Hessian-Laplace region detector with its own gradient orientation-based feature descriptor.
• Instead of relying on Gaussian derivatives for its internal computations, it is based on simple 2D box filters ("Haar wavelets"), which approximate the effects of derivative filter kernels and are 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 images of the specific objects being identified.
• Candidate matches are identified by searching among all previously seen local descriptors and retrieving those nearest to Euclidean distance in the feature space.
• A basic solution to identifying local feature matches involves scanning through all previously seen descriptors, comparing them to the current input descriptor, and taking those within some threshold as candidates.
• Linear-time scans are unrealistic with regard to computational complexity.
• In practical applications with databases of millions of features, efficient algorithms for 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.
• Because each exemplar image could easily contain hundreds to thousands of interest points, rapidly increasing the DB, efficient similarity search is key.

Efficient Similarity Search

• Tree-based algorithms and hashing based algorithms are options to search,

Tree-Based Algorithms

• The kd-tree is a binary tree storing a database of k-dimensional points in its leaf nodes.
• Recursively partitions the points into axis aligned cells, dividing the points approximately in half by a line perpendicular to one of the k coordinate axes.
• Division strategies aim to maintain balanced trees and/or uniformly shaped cells (e.g., by choosing the next axis to split according to that which has the largest variance among the database points, or by cycling through the axes in order).
• To find the point nearest to some query, traverse the tree following the same divisions used to enter the database points.
• Once reaching a leaf node, the points found there are compared to the query, and the nearest one becomes the "current best".
• The point is nearer than others to the query, so this is the absolute nearest.
• Search continues by backtracking along the unexplored branches, checking whether the circle formed about the query by the radius given by the current best match intersects with a subtree's cell area.
• If the subtree has closer points, the search recurses and updates the current best; otherwise, the subtree is pruned.

Hashing-Based Algorithms and Binary Codes

• Hashing algorithms provide an effective alternative to tree-based data structures.
• Approximate similarity search trades precision for query time reductions, addressing the inadequacy of existing exact nearest-neighbor techniques for high-dimensional data.
• Locality-sensitive hashing (LSH) is an algorithm offering sub-linear time search by hashing highly similar examples together in a hash table.
• LSH ensures a randomized hash function maps two inputs to the same bucket with high probability only when similar; given a new query, one only searches colliding database examples to find those most likely to lie in the inputs near neighborhood.

Reducing Ambiguous Matches

• When matching local feature sets extracted from real-world images, many stem from background clutter, lacking meaningful neighbors in the other set.
• Other features on repetitive structures may have ambiguous matches (e.g., a building with many identical windows).
• It is important to distinguish reliable matches from unreliable ones based on descriptors.
• Considering the ratio of the distance to the closest neighbor to that of the second-closest one as a decision criterion is an often-used strategy.
• The nearest neighbor local feature originating from an exemplar in the database of training images, as well as the second nearest neighbor, originating from a different object, are used.
• A high ratio of the distance to the first neighbor over the distance to the second suggests ambiguity; a low ratio suggests reliability.

Indexing Features With Visual Vocabularies

• A visual vocabulary is a strategy that draws inspiration from text retrieval.
• This enables 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 the local descriptors to discrete tokens, we can then "match" them by simply looking up features assigned to the identical token.