Group-theoretic algorithms for matching problems with applications to computer vision.

Add to your list(s) Download to your calendar using vCal

• Deepti Pachauri, University of Wisconsin Madison.
• Wednesday 11 March 2015, 10:00-11:00
• Auditorium, Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

This talk has been canceled/deleted

Matching one set of objects to another is a fundamental problem in computer science. In computer vision it arises in the context of finding the correspondences between multiple images of the same scene taken from different viewpoint. In machine learning one often needs to align examples before a meaningful similarity measure can be computed between them. These problems often reduce to some form of combinatorial search problem, various classes of which are polynomial time solvable whereas many others are NP-hard. Therefore, most successful methods take heuristic approach with no optimality guaranteed. The fundamental difficulty in solving matching problems is that the solution space is exponential in size. In my research, I consider a different approach for these intractable problems. I am interested in exploiting the algebraic structure of the solution of a matching problem i.e., a permutation. A permutation of order n is a candidate in the Sn, called the Symmetric Group of degree n. The high degree of regularity of the symmetric group allows me to unleash a wide range of mathematical tools on matching problems. My dissertation studies matching problems from the following perspectives: 1) How to take advantage of the fact that any finite group supports a notion of Fourier transformation, and hence Harmonic Analysis; 2) How to extend the notion of regularity in output space of matching problems to solve multi-way matching problem; 3) How to organize matching instances and construct meaningful metric for such data. To make my exposition concrete, I will restrict my attention to the matching problems in computer vision domain. However, my approach is fully general and equally applicable to matching problems in domains other than computer vision such as social networks.

This talk is part of the Microsoft Research Cambridge, public talks series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.