DOI | Resolve DOI: https://doi.org/10.1109/AICCSA47632.2019.9035320 |
---|
Author | Search for: Madi, Kamel; Search for: Paquet, Eric1; Search for: Kheddouci, Hamamache |
---|
Affiliation | - National Research Council of Canada. Digital Technologies
|
---|
Format | Text, Article |
---|
Conference | 2019 IEEE/ACS 16th International Conference on Computer Systems and Applications (AICCSA), November 3-7, 2019, Abu Dhabi, United Arab Emirates |
---|
Subject | Graph matching; Graph edit distance; Graph decomposition; Stable Marriage; Pattern recognition; 3D object recognition; Deformable object recognition |
---|
Abstract | 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²). 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. |
---|
Publication date | 2020-03-16 |
---|
Publisher | IEEE |
---|
In | |
---|
Language | English |
---|
Peer reviewed | Yes |
---|
Export citation | Export as RIS |
---|
Report a correction | Report a correction (opens in a new tab) |
---|
Record identifier | 8f7c7bbb-e989-4abf-9e2d-6d4d12b22e98 |
---|
Record created | 2021-04-07 |
---|
Record modified | 2021-04-07 |
---|