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
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.
Yoichi SASAKI
Hokkaido University
Tetsuo SHIBUYA
University of Tokyo
Kimihito ITO
Hokkaido University
Hiroki ARIMURA
Hokkaido University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Yoichi SASAKI, Tetsuo SHIBUYA, Kimihito ITO, Hiroki ARIMURA, "Efficient Approximate 3-Dimensional Point Set Matching Using Root-Mean-Square Deviation Score" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1159-1170, September 2019, doi: 10.1587/transfun.E102.A.1159.
Abstract: In this paper, we study the approximate point set matching (APSM) problem with minimum RMSD score under translation, rotation, and one-to-one correspondence in d-dimension. Since most of the previous works about APSM problems use similality scores that do not especially care about one-to-one correspondence between points, such as Hausdorff distance, we cannot easily apply previously proposed methods to our APSM problem. So, we focus on speed-up of exhaustive search algorithms that can find all approximate matches. First, we present an efficient branch-and-bound algorithm using a novel lower bound function of the minimum RMSD score for the enumeration version of APSM problem. Then, we modify this algorithm for the optimization version. Next, we present another algorithm that runs fast with high probability when a set of parameters are fixed. Experimental results on both synthetic datasets and real 3-D molecular datasets showed that our branch-and-bound algorithm achieved significant speed-up over the naive algorithm still keeping the advantage of generating all answers.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1159/_p
Copier
@ARTICLE{e102-a_9_1159,
author={Yoichi SASAKI, Tetsuo SHIBUYA, Kimihito ITO, Hiroki ARIMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Approximate 3-Dimensional Point Set Matching Using Root-Mean-Square Deviation Score},
year={2019},
volume={E102-A},
number={9},
pages={1159-1170},
abstract={In this paper, we study the approximate point set matching (APSM) problem with minimum RMSD score under translation, rotation, and one-to-one correspondence in d-dimension. Since most of the previous works about APSM problems use similality scores that do not especially care about one-to-one correspondence between points, such as Hausdorff distance, we cannot easily apply previously proposed methods to our APSM problem. So, we focus on speed-up of exhaustive search algorithms that can find all approximate matches. First, we present an efficient branch-and-bound algorithm using a novel lower bound function of the minimum RMSD score for the enumeration version of APSM problem. Then, we modify this algorithm for the optimization version. Next, we present another algorithm that runs fast with high probability when a set of parameters are fixed. Experimental results on both synthetic datasets and real 3-D molecular datasets showed that our branch-and-bound algorithm achieved significant speed-up over the naive algorithm still keeping the advantage of generating all answers.},
keywords={},
doi={10.1587/transfun.E102.A.1159},
ISSN={1745-1337},
month={September},}
Copier
TY - JOUR
TI - Efficient Approximate 3-Dimensional Point Set Matching Using Root-Mean-Square Deviation Score
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1159
EP - 1170
AU - Yoichi SASAKI
AU - Tetsuo SHIBUYA
AU - Kimihito ITO
AU - Hiroki ARIMURA
PY - 2019
DO - 10.1587/transfun.E102.A.1159
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - In this paper, we study the approximate point set matching (APSM) problem with minimum RMSD score under translation, rotation, and one-to-one correspondence in d-dimension. Since most of the previous works about APSM problems use similality scores that do not especially care about one-to-one correspondence between points, such as Hausdorff distance, we cannot easily apply previously proposed methods to our APSM problem. So, we focus on speed-up of exhaustive search algorithms that can find all approximate matches. First, we present an efficient branch-and-bound algorithm using a novel lower bound function of the minimum RMSD score for the enumeration version of APSM problem. Then, we modify this algorithm for the optimization version. Next, we present another algorithm that runs fast with high probability when a set of parameters are fixed. Experimental results on both synthetic datasets and real 3-D molecular datasets showed that our branch-and-bound algorithm achieved significant speed-up over the naive algorithm still keeping the advantage of generating all answers.
ER -