Computer Science Department, Southwestern University of Finance and Economics, 555 Liutai Ave., Chengdu, Sichuan 610000, China.
IEEE Trans Pattern Anal Mach Intell. 2013 Feb;35(2):411-24. doi: 10.1109/TPAMI.2012.99.
In this paper, we introduce a new matching method based on a novel locally affine-invariant geometric constraint and linear programming techniques. To model and solve the matching problem in a linear programming formulation, all geometric constraints should be able to be exactly or approximately reformulated into a linear form. This is a major difficulty for this kind of matching algorithm. We propose a novel locally affine-invariant constraint which can be exactly linearized and requires a lot fewer auxiliary variables than other linear programming-based methods do. The key idea behind it is that each point in the template point set can be exactly represented by an affine combination of its neighboring points, whose weights can be solved easily by least squares. Errors of reconstructing each matched point using such weights are used to penalize the disagreement of geometric relationships between the template points and the matched points. The resulting overall objective function can be solved efficiently by linear programming techniques. Our experimental results on both rigid and nonrigid object matching show the effectiveness of the proposed algorithm.
在本文中，我们提出了一种新的匹配方法，该方法基于一种新颖的局部仿射不变几何约束和线性规划技术。为了在线性规划公式中对匹配问题进行建模和求解，所有几何约束都应该能够被精确或近似地重新表述为线性形式。这对于这种匹配算法来说是一个主要的难点。我们提出了一种新颖的局部仿射不变约束，它可以被精确地线性化，并且需要比其他基于线性规划的方法少得多的辅助变量。其核心思想是模板点集中的每个点都可以通过其邻域点的仿射组合来精确表示，其权重可以通过最小二乘法轻松求解。使用这种权重重建每个匹配点的误差用于惩罚模板点和匹配点之间的几何关系的不一致性。通过线性规划技术可以有效地解决由此产生的整体目标函数。我们在刚性和非刚性物体匹配上的实验结果表明了所提出算法的有效性。
