Partial Permutation Synchronization via Cycle-Edge Message Passing

Seminar: 
Applied Mathematics
Event time: 
Wednesday, February 23, 2022 - 12:00pm
Location: 
https://yale.zoom.us/j/97458245891
Speaker: 
Gilad Lerman
Speaker affiliation: 
University of Minnesota
Event description: 

Abstract:  The problem of partial permutation synchronization (PPS) provides a global mathematical formulation for the multiple image matching problem. In this matching problem, one is provided with possibly corrupted matches (i.e., partial permutations) between keypoints in pairs of images and the underlying task is to match keypoints in each image to universal 3D scene points (resulting in other partial permutations). For structure from motion (SfM) common datasets, previous PPS algorithms for image matching often become computationally intractable and demand an exceedingly large amount of memory. We address this issue by extending the recent framework of Cycle-Edge Message Passing (CEMP) to the setting of PPS despite the fact that partial permutations do not have a full group structure. We emphasize mathematical difficulties that arise when extending CEMP to PPS and also explain the mathematical guarantees for the performance of the modified CEMP algorithm in the setting of adversarial corruption and sufficiently small noise. If time allows we will demonstrate the state-of-the-art accuracy of our overall product for solving PPS within SfM. This is a joint work with Shaohan Li and Yunpeng Shi.