title: Object matching using a locally affine invariant and linear programming techniques.
abstract: 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.
authors.affiliation: Computer Science Department, Southwestern University of Finance and Economics, 555 Liutai Ave., Chengdu, Sichuan 610000, China. lihongsheng@gmail.com
authors.forename: Hongsheng
authors.initials: H
authors.lastname: Li
authors.forename: Xiaolei
authors.initials: X
authors.lastname: Huang
authors.forename: Lei
authors.initials: L
authors.lastname: He
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D007089:Image Enhancement / Q000379:methods; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*; D011382:Programming, Linear; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D012815:Signal Processing, Computer-Assisted; D013382:Subtraction Technique