New Graph Distance based on Stable Marriage formulation for Deformable 3D Objects Recognition

We propose a novel fast graph matching approach based on a new formulation of the stable marriage problem, to measure the distance between graphs. The proposed approach is optimal in terms of execution time, i.e. quadratic time complexity O(n(2)). Our technique is based on the decomposition of graphs into a set of substructures which are subsequently matched with the stable marriage algorithm. In this paper, we address the problem of comparing deformable 3D objects represented by graphs, we use a triangle-stars decomposition for triangular tessellations (graphs of 3D shapes). The proposed approach is based on computing an approximation of Graph Edit Distance which is fault-tolerant to noise and distortion which makes our method especially relevant for deformable 3D shapes comparison. We analyze and determine its time complexity. The proposed method is evaluated against benchmark databases under different evaluation criteria. Our experimental results consistently demonstrate the effectiveness and the high performances of our approach.