Elastic geometric shape matching for translations under the Manhattan norm

Abstract The term elastic geometric shape matching (EGSM) refers to geometric optimization problems that are a generalization of many classical and well-studied geometric shape matching problems. In a geometric shape matching problem, one seeks a single transformation that, if applied to a geometric object – the pattern – minimizes the distance of the transformed object to another geometric object – the model. In an EGSM problem, the pattern is partitioned into parts which are transformed by a collection of transformations, called a transformation ensemble , in order to minimize the distance of the individually transformed parts to the model under the constraint that specific pairs of transformations of the ensemble have to be similar . These constraints are defined by an abstract graph on the parts of the model, called the neighborhood graph . We present algorithms for an EGSM problem for point sets under translations where the neighborhood graph is a tree. We measure the similarity of the shapes by the L 1 -Hausdorff distance (and the Hausdorff distance induced by other polygonal metrics).