The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1159-1170

- Publication Date
- 2019/09/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E102.A.1159

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category
- Optimization

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.

Copy

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

Copy

@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},}

Copy

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 -