Efficient Approximate 3-Dimensional Point Set Matching Using Root-Mean-Square Deviation Score

この論文にアクセスする

著者

    • SASAKI Yoichi
    • Graduate School of Information Science and Technology, Hokkaido University
    • ITO Kimihito
    • Research Center for Zoonosis Control, Hokkaido University
    • ARIMURA Hiroki
    • Graduate School of Information Science and Technology, Hokkaido University

抄録

<p>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 <i>d</i>-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.</p>

収録刊行物

  • IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E102.A(9), 1159-1170, 2019

    一般社団法人 電子情報通信学会

各種コード

ページトップへ