标题： 通过线性规划的高效联合对象匹配 显示英文标题

标题： Efficient Joint Object Matching via Linear Programming

摘要： 联合物体匹配，也称为多图像匹配，即在一组物体的所有物体对中寻找一致的部分映射的问题，是计算机视觉许多领域中的关键任务。 这个问题包括二分图匹配和图划分作为特殊情况，并且在一般情况下是NP难的。 我们为联合物体匹配开发了可扩展的线性规划（LP）松弛方法，并具有理论性能保证。 我们首先提出了一种对一致部分映射的新表征；这进而使我们能够将联合物体匹配表述为一个整数线性规划（ILP）问题。 为了构建强大的LP松弛，我们研究了这个ILP可行区域凸包的面结构，我们称之为联合匹配多面体。 我们提出了一类指数级的面定义不等式，这些不等式可以在强多项式时间内分离，从而得到了一个既紧密又计算成本低廉的联合匹配多面体的部分表征。 为了分析所提出的LP松弛的理论性能，我们关注排列群同步，这是联合物体匹配的一个重要特殊情况。 我们证明，在输入映射的随机损坏模型下，一个简单的LP松弛，即一个仅包含我们提出的面定义不等式非常小一部分的LP，在损坏水平低于$40\%$时，以高概率恢复真实情况。 最后，通过在合成数据上的初步计算研究，我们展示了所提出的LP松弛在恢复和紧密性方面都优于一种流行的SDP松弛方法。 显示英文摘要

摘要： Joint object matching, also known as multi-image matching, namely, the problem of finding consistent partial maps among all pairs of objects within a collection, is a crucial task in many areas of computer vision. This problem subsumes bipartite graph matching and graph partitioning as special cases and is NP-hard, in general. We develop scalable linear programming (LP) relaxations with theoretical performance guarantees for joint object matching. We start by proposing a new characterization of consistent partial maps; this in turn enables us to formulate joint object matching as an integer linear programming (ILP) problem. To construct strong LP relaxations, we study the facial structure of the convex hull of the feasible region of this ILP, which we refer to as the joint matching polytope. We present an exponential family of facet-defining inequalities that can be separated in strongly polynomial time, hence obtaining a partial characterization of the joint matching polytope that is both tight and cheap to compute. To analyze the theoretical performance of the proposed LP relaxations, we focus on permutation group synchronization, an important special case of joint object matching. We show that under the random corruption model for the input maps, a simple LP relaxation, that is, an LP containing only a very small fraction of the proposed facet-defining inequalities, recovers the ground truth with high probability if the corruption level is below $40\%$. Finally, via a preliminary computational study on synthetic data, we show that the proposed LP relaxations outperform a popular SDP relaxation both in terms of recovery and tightness.