Visual Object Recognition: Local Descriptors & SIFT

Visual Object Recognition

• The lecture covers local descriptors, matching local features, and indexing features with visual vocabularies

Local Descriptors

• Once interest regions are extracted from an image, their content must be encoded in a descriptor optimized for discriminative matching
• The SIFT descriptor is a popular choice
• The Scale Invariant Feature Transform (SIFT) was originally introduced by Lowe and combines a DoG interest region detector with a feature descriptor

SIFT Descriptor

• Descriptor computation starts from a scale, and rotation-normalized region that is extracted with a detector
• Image gradient magnitude and orientation are sampled around the keypoint location, while the region scale is used to select the level of Gaussian blur
• Sampling is performed in a 16 × 16 grid covering the interest region
• For each location sampled, the gradient orientation is entered into a coarser 4 × 4 grid of gradient orientation histograms with 8 orientation bins each
• These bins are weighted by the corresponding pixel's gradient magnitude and by a circular Gaussian weighting function
• The Gaussian window favors pixels closer to the middle of the region to minimize the impact of localization inaccuracies

SURF Detector/Descriptor

• SURF ("Speeded-Up Robust Features") is an efficient alternative to SIFT
• Instead of Gaussian derivatives, computation uses simple 2D box filters that are efficiently evaluated using integral images
• SURF combines a Hessian-Laplace region detector with its gradient orientation-based feature descriptor
• Computations are based on simple 2D box filters ("Haar wavelets")
• Box filters approximate the effects of derivative filter kernels but can be efficiently evaluated

Matching Local Features

• It is necessary to match the local features to similar-looking local features in other images
• To identify candidate matches, one has to search for local descriptors, and then retrieve the nearest ones
• The simplest solution is to scan all previously seen descriptors, compare them to the current input descriptor, and select those within a given threshold
• This linear-time scan isn't realistic due to computational complexities
• Applications with millions of features require efficient algorithms for nearest neighbor or similarity searches
• Each exemplar image has hundreds/thousands of interest points which causes the database of descriptors to become very large
• Therefore, the database has to be mapped to certain data structures to make similarity searches more efficient

Efficient Similarity Search

• Tree-based algorithms and hashing-based algorithms and binary codes are both efficient similarity searches

Tree-Based Algorithms

• The kd-tree is a binary tree that stores a database of k-dimensional points in its leaf nodes
• It recursively partitions points into axis-aligned cells, dividing the points approximately in half using a line perpendicular to one of the k coordinate axes
• Division strategies aim to maintain balanced trees and/or uniformly shaped cells by choosing the next axis to split
• Choose the axis to split depending on which has the largest variance among the database points, or by cycling through the axes in order
• To find the query's nearest point, the tree is traversed which follows the divisions that were used to enter the database points
• The points found are compared to the query upon reaching a leaf node
• The nearest point then becomes the current best
• The best query point needs to be an absolute nearest because it cannot be nearer to some points on the other side of the dividing hyperplane
• After determining the above, the search continues by backtracking along unexplored branches
• It is checked whether the circle formed by the query by the radius given by the current best match intersects with the subtree's cell area
• If there is an intersection, that subtree is further evaluated, and any nearer points found during the search are used to update the current best
• the subtree can be pruned if there is no intersection

Hashing-Based Algorithms and Binary Codes

• Hashing algorithms are an effective alternative to tree-based data structures
• Motivated by the inadequacy of existing exact nearest-neighbor techniques to provide sub-linear time search for high-dimensional data, randomized approximate hashing-based similarity search algorithms have been explored
• In approximate similarity search, some precision in the search is traded off for substantial query time reductions
• Locality-sensitive hashing (LSH) is an algorithm that offers sub-linear time search by hashing highly similar examples together in a hash table
• If a randomized hash function will map two inputs to the same bucket with high probability only if they are similar, then, one only needs to search the colliding database examples to find those that are most probable to lie in the input's near neighborhood

Reducing Ambiguous Matches

• When matching local feature sets extracted from real-world images, features stem from background clutter and have no meaningful neighbor in the other set
• Other features lie on repetitive structures which may result in ambiguous matches
• Therefore, one needs a way to distinguish reliable and unreliable matches
• This determination cannot be made based on descriptor distance alone because some descriptors are more discriminative than others
• An often-used strategy is to consider the ratio of the distance to the closest neighbor to that of the second-closest one as a decision criterion
• The nearest neighbor local feature originating from an exemplar in the database of training images is identified
• The second nearest neighbor that originates from a different object than the nearest neighbor feature is then considered
• A relatively large ratio is a sign that the match is reliable, and a low ratio suggests it may be ambiguous

Indexing Features With Visual Vocabularies

• A visual vocabulary is a strategy inspired by the text retrieval community that enables efficient indexing for local image features
• Rather than preparing a tree or hashing data structure to aid in direct similarity search, the idea is to quantize the local feature space
• By mapping the local descriptors to discrete tokens, "matching" can be done by looking up features assigned to the identical token