The Taub Faculty of Computer Science Events and Talks

We will discuss two related works:
1) "Point Registration via Efficient Convex Relaxation" Point cloud registration is a fundamental task in computer graphics, and more specifically, in rigid and non-rigid shape matching. The rigid shape matching problem can be formulated as the problem of simultaneously aligning and labeling two point clouds in 3D so that they are as similar as possible. We name this problem the Procrustes matching (PM) problem. The non-rigid shape matching problem can be formulated as a higher dimensional PM problem using the functional maps method. High dimensional PM problems are difficult non-convex problems which currently can only be solved locally using iterative closest point (ICP) algorithms or similar methods. Good initialization is crucial for obtaining a good solution.

We introduce a novel and efficient convex SDP (semidefinite programming) relaxation for the PM problem. The algorithm is guaranteed to return a correct global solution of the problem when matching two isometric shapes which are either asymmetric or bilaterally symmetric. We show our algorithm gives state of the art results on popular shape matching datasets. We also show that our algorithm gives state of the art results for anatomical classification of shapes. Finally we demonstrate the power of our method in aligning shape collections.

2) "Exact Recovery with Symmetries for Procrustes Matching" In this talk we analyze the PM semi-definite relaxation. We demonstrate some natural theoretical properties of the relaxation. We use the moment interpretation of [Lasserre, 2000] to show that for problems without noise and with (generic) input shapes which are asymmetric or bilaterally symmetric, the relaxation returns a correct solution of PM. For symmetric shapes, PM has multiple solutions. The non-convex set of optimal solutions of PM is strictly contained in the convex set of optimal solutions of PM-SDP, so that solutions of PM-SDP may not be solutions of PM. We deal with this by showing the solution set of PM to be the extreme points of the solution set of PM-SDP, and suggesting a random algorithm which returns a solution of PM with probability one, and returns the solutions of PM with equal probability. To the best of our knowledge there are no previous works on exact recovery in the presence of multiple solutions.

Joint work with Itay Kezurer, Shahar Kovalsky and Yaron Lipman.