La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Efficient Approximate 3-Dimensional Point Set Matching Using Root-Mean-Square Deviation Score Correspondance efficace d'ensembles de points tridimensionnels approximatifs à l'aide du score d'écart quadratique moyen

Yoichi SASAKI, Tetsuo SHIBUYA, Kimihito ITO, Hiroki ARIMURA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Dans cet article, nous étudions le problème d'appariement approximatif d'ensembles de points (APSM) avec un score RMSD minimum sous translation, rotation et correspondance biunivoque dans d-dimension. Étant donné que la plupart des travaux précédents sur les problèmes APSM utilisent des scores de similarité qui ne se soucient pas particulièrement de la correspondance biunivoque entre les points, comme la distance de Hausdorff, nous ne pouvons pas facilement appliquer les méthodes proposées précédemment à notre problème APSM. Nous nous concentrons donc sur l’accélération des algorithmes de recherche exhaustifs capables de trouver toutes les correspondances approximatives. Tout d’abord, nous présentons un algorithme de branchement et de liaison efficace utilisant une nouvelle fonction de limite inférieure du score RMSD minimum pour la version énumération du problème APSM. Ensuite, nous modifions cet algorithme pour la version optimisation. Ensuite, nous présentons un autre algorithme qui s’exécute rapidement avec une forte probabilité lorsqu’un ensemble de paramètres est fixé. Les résultats expérimentaux sur des ensembles de données synthétiques et des ensembles de données moléculaires 3D réels ont montré que notre algorithme de branchement et de liaison a atteint une accélération significative par rapport à l'algorithme naïf, tout en conservant l'avantage de générer toutes les réponses.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1159-1170
Date de publication
2019/09/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E102.A.1159
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories

Auteurs

Yoichi SASAKI
  Hokkaido University
Tetsuo SHIBUYA
  University of Tokyo
Kimihito ITO
  Hokkaido University
Hiroki ARIMURA
  Hokkaido University

Mots-clés

Table des matières