LPSM: Fitting shape model by linear programming

We propose a shape model fitting algorithm that uses linear programming optimization. Most shape model fitting approaches (such as ASM, AAM) are based on gradient-descent-like local search optimization and usually suffer from local minima. In contrast, linear programming (LP) techniques achieve globally optimal solution for linear problems. In [1], a linear programming scheme based on successive convexification was proposed for matching static object shape in images among cluttered background and achieved very good performance. In this paper, we rigorously derive the linear formulation of the shape model fitting problem in the LP scheme and propose an LP shape model fitting algorithm (LPSM). In the experiments, we compared the performance of our LPSM with the LP graph matching algorithm(LPGM), ASM, and a CONDENSATION based ASM algorithm on a test set of PUT database. The experiments show that LPSM can achieve higher shape fitting accuracy. We also evaluated its performance on the fitting of some real world face images collected from internet. The results show that LPSM can handle various appearance outliers and can avoid local minima problem very well, as the fitting is carried out by LP optimization with l₁ norm robust cost function.