M.Sc Thesis

M.Sc StudentEdelstein Michal
SubjectA Genetic Algorithm for Fully Automatic Non-Isometric Shape
DepartmentDepartment of Electrical and Computers Engineering
Supervisor ASSOCIATE PROF. Mirela Ben-Chen
Full Thesis textFull thesis text - English Version


Shape correspondence is a challenging task in geometry processing and computer graphics with various applications including texture transfer, shape interpolation and statistical modeling. The goal is to find a meaningful relation between two or more shapes. The correspondence can be either sparse, where a small number of meaningful landmarks are matched, or dense, where a full map between the shapes is retrieved. Finding such a map between non-isometric shapes is difficult since the shapes can differ greatly from one another and the matching needs to be semantic.

We propose a fully automatic method for shape correspondence that is widely applicable, and especially effective for non-isometric shapes and shapes of different topology. We observe that fully automatic shape correspondence can be decomposed as a hybrid discrete-continuous optimization problem, and we find the best sparse landmark correspondence, whose sparse-to-dense extension minimizes a local metric distortion. To tackle the combinatorial task of landmark correspondence we use an evolutionary genetic algorithm, where the local distortion of the sparse-to-dense extension is used as the objective function.

We design novel geometrically guided genetic operators, which, when combined with our objective, are highly effective for non-isometric shape matching. Our method outperforms state of the art methods for automatic shape correspondence both quantitatively and qualitatively on challenging datasets.