17 Computer Vision News Computer Vision News preserving neighborhood relations. “Imagine two organs, like the liver, heart, or lungs, and you match them from different people,” Florian explains. “You take the shapes and want to train a statistical shape model. If you didn’t have this geometric consistency, the deformation from one to the other would lead to self-intersecting sections which aren’t anatomically plausible.” Many existing approaches to 3D shape matching do not enforce geometric consistency as a hard constraint but optimize it as a soft objective, often framed as graph matching or quadratic assignment problems. “This is a problem class well known to be NP-hard, making it extremely challenging to solve for large instances in practice,” Florian tells us. “We find a different representation that makes the problem easier to solve.” Florian and Paul propose a novel path-based formalism, representing one of the 3D shapes (the source shape) as a long, self-intersecting curve (‘SpiderCurve’) that traces the 3D shape surface. This alternative discretization simplifies the 3D shape matching problem to find the shortest path in the product graph of the SpiderCurve and the target 3D shape. “This switch of the discretization is what makes our paper novel,” Paul points out. “We think differently about a problem, making a very complicated task to solve a simpler one.” This formalism leads to an integer linear programming problem, which the team demonstrates can be efficiently solved to global optimality. The result is competitive with recent state-of-the-art shape matching methods and guarantees geometric consistency. “For the first time, we can find geometrically consistent shape matchings while also finding global optima in practice,” Florian reveals. “Within the framework of our optimization formulation, in all the instances that we’ve evaluated, we know that we have the best possible solution among all potential solutions!” SpiderMatch

RkJQdWJsaXNoZXIy NTc3NzU=