L 1 Generalized Procrustes 2D Shape Alignment

This paper describes a new method for resistant and robust alignment of sets of 2D shapes wrt. position, rotation, and iso-tropical scaling. Apart from robustness a major advantage of the method is that it is formulated as a linear programming (LP) problem, thus enabling the use of well known and thoroughly tested standard numerical software. The problem is formulated as the minimization of the norm of a linear vector function with a contraint of non-zero size. This is achieved by using the city block distance between points in the plane. Unfortunately the city block distance is dependent on the orientation of the coordinate system, i.e. it is not rotationally invariant. However, by simultaneously minimizing the city block distances in a series of rotated coordinate systems we are able to approximate the circular equidistance curves of Euclidean distances with a regular polygonal equidistance curve to the precision needed. Using 3 coordinate systems rotated 30 degrees we get a 12 sided regular polygon, with which we achieve deviations from Euclidean distances less than 2 % over all directions. This new formulation allows for minimization in the L1-norm using LP. We demonstrate that the use of the L1-norm results in resistance towards object as well as landmark outliers. Examples that illustrate the properties of the robust norm are given on simulated as well as medical data sets.