Probabilistic approaches to high order assignment problems

Yosi Keller (Bar Ilan University, Isreal)


A gamut of computer vision and engineering problems can be cast as high order matching problems, where one considers the affinity/probability of two or more assignments simultaneously. The spectral matching approach of Leordeanu and Hebert (2005) was shown to provide an approximate solution of this np-hard problem.

It this talk we present recent results on the probabilistic interpretation of spectral matching. We extend the results of Zass and Shashua (2008) and provide a probabilistic interpretation to the spectral matching and graduated assignment algorithms. We then derive a new probabilistic matching scheme, and show that it can be extended to high order matching scheme, via a dual marginalization-decomposition scheme. Last, we exemplify our approach by applying to image segmentation.