Fast Approximate Nearest Neighbor Methods for Example-Based Video Search

The cost of computer storage is steadily decreasing. Many terabytes of video data can be easily collected using video cameras in public places for modern surveillance applications, or stored on video sharing websites. However, the growth in CPU speeds has recently slowed to a crawl. This situation implies that while the data is being collected, it cannot be cheaply processed in time. Searching such vast collections of video data for useful information requires radically different approaches, calling for algorithms with sub-linear time complexity.

One application of a search in a large data set is query-by-example. A video clip is used as a query for an algorithm to find a set of similar clips from the collection. A naive solution to such problem would specify some sort of a similarity metric and exhaustively compute this similarity between the query and all other video clips in the collection. Then the clips with the highest similarity values can be returned as the answer-set. However, as the number of the videos in the collection grows, such computation becomes prohibitively expensive. In order to show sub-linear growth any large-scale algorithm needs to exploit some properties of the data that does away with the need to compute explicit distances between a query point and any other point in the set. To this end, Approximate Nearest Neighbor methods have recently become popular. These algorithms provide a trade-off between the accuracy of finding nearest-neighbors and the corresponding computational complexity. As a result, searches in very large datasets can be performed very quickly albeit at the cost of very few incorrect matches.

Most of the recent work in developing ANN methods has been done for data points that lie in a Euclidean space. However, several applications in computer vision such as object and human activity recognition use non-Euclidean data. State-of-the-art Euclidean ANN methods do not perform well when applied to these datasets. In this chapter, we present algorithms for performing ANN on manifolds 1) by explicitly considering the Riemannian geometry of the non-Euclidean manifold and 2) by taking advantage of the kernel trick in non-Euclidean spaces where performing Riemannian computations is expensive. For a data set with

N

samples, the proposed methods are able to retrieve similar objects in as low as

O

(

K

) time complexity, where

K

 ≪ 

N

. We test and evaluate our methods on both synthetic and real datasets and get better than state-of-the-art results.