New graph distance for deformable 3D objects recognition based on triangle-stars decomposition

Highlights：

• We propose a new decomposition of triangular tessellations into triangle-stars, allowing the creation of a set of descriptors which are invariant or at least oblivious under most common deformations.

• The proposed approach, called TSM, offers an improved dissimilarity with a reduced time complexity and we proved that TSM is a pseudo-metric.

• Our approach defines a metric space using graph embedding and graph kernel techniques. Classification is performed with supervised machine learning techniques.

• We experimentally evaluate our approach, under different evaluation criteria, on various benchmark databases for deformable shapes.

摘要

•We propose a new graph matching algorithm to measure the distance between deformable 3D objects, based on approximation of Graph Edit Distance which is fault-tolerant to noise and distortion, making our approach suitable for comparing deformable objects.•We propose a new decomposition of triangular tessellations into triangle-stars, allowing the creation of a set of descriptors which are invariant or at least oblivious under most common deformations.•The proposed approach, called TSM, offers an improved dissimilarity with a reduced time complexity and we proved that TSM is a pseudo-metric.•Our approach defines a metric space using graph embedding and graph kernel techniques. Classification is performed with supervised machine learning techniques.•We experimentally evaluate our approach, under different evaluation criteria, on various benchmark databases for deformable shapes.

论文关键词：Graph matching,Graph edit distance,Graph decomposition,Graph embedding,Graph metric,Graph classification,Pattern recognition,3D object recognition,Deformable object recognition,Metric learning