EE Seminar: Visual Nearest Neighbor Search

~~Speaker: Simon Korman
PhD student under the supervision of Prof. Shai Avidan

Monday, July 13th, 2015  at  15:00
Room 011, Kitot Bldg., Faculty of Engineering

Visual Nearest Neighbor Search

Abstract

Many mid-level tasks in computer vision can be formulated as a search for a best configuration in some large search space, whether continuous or discrete. The complexity of a full search typically depends on the size of the image(s) considered as well as on the degrees of freedom of a model that the configurations represent.  This often leads to prohibitive complexity and therefore many heuristics and approximation schemes have been proposed for such problems.
 
The talk will present several different such problems and review some approximation algorithms that we suggested in our work. One such problem is that of computing a dense mapping between the patches of a pair of images. We develop a hashing based scheme that significantly improves over the accuracy-efficiency tradeoffs of existing methods, for both RGB and RGBD images.

Our work also deals with problems in the domain of matching images or 3D shapes, under rigid geometric transformations (e.g. Euclidean, affine or perspective).  We propose here an efficient method for enumerating the entire search space, in a way that provides global bounds on the approximation level of the obtained model.
Within this framework, the talk will focus on the problem of matching between images, given putative pairs of matching interest points. In this setting, one must take into account the presence of outliers in the input data and this is typically done by the RANSAC robust estimation framework. We suggest here an alternative method, which is able to estimate the rate of inliers in the data, without actually identifying them, followed by a globally optimal search, with respect to the specific inlier rate. We show that the combined framework works on challenging cases of 2D-homography estimation, with very few (and possibly noisy) inliers, where RANSAC generally fails.