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

PATTERN RECOGNITION

卷:90

Article

Madi, Kamel^1,3  Paquet, Eric²  Kheddouci, Hamamache¹ 

[1] Univ Lyon 1, Univ Lyon, CNRS, LIRIS,UMR5205, F-69622 Villeurbanne, France

[2] Natl Res Council Canada, Ottawa, ON, Canada

[3] Umanis, F-92300 Levallois Perret, France

关键词: Graph matching;    Graph edit distance;    Graph decomposition;    Graph embedding;    Graph metric;    Graph classification;    Pattern recognition;    3D object recognition;    Deformable object recognition;    Metric learning;   

DOI  :  10.1016/j.patcog.2019.01.040

来源: Elsevier

【 摘 要 】

We address the problem of comparing deformable 3D objects represented by graphs such as triangular tessellations. We propose a new graph matching technique to measure the distance between these graphs. The proposed approach is based on a new decomposition of triangular tessellations into triangle-stars. The algorithm ensures a minimum number of disjoint triangle-stars, provides improved dissimilarity by covering larger neighbors and allows the creation of descriptors that are invariant or at least oblivious under the most common deformations. The present approach is based on an approximation of the Graph Edit Distance, which is fault-tolerant to noise and distortion, thus making our technique particularly suitable for the comparison of deformable objects. Classification is performed with supervised machine learning techniques. Our approach defines a metric space using graph embedding and graph kernel techniques. It is proved that the proposed distance is a pseudo-metric. Its time complexity is determined and the method is evaluated against benchmark databases. Our experimental results confirm the performances and the accuracy of our system. (C) 2019 Elsevier Ltd. All rights reserved.

【 授权许可】

Free