
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Efficient Approximate 3Dimensional Point Set Matching Using RootMeanSquare Deviation Score
Yoichi SASAKI Tetsuo SHIBUYA Kimihito ITO Hiroki ARIMURA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E102A
No.9
pp.11591170 Publication Date: 2019/09/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E102.A.1159
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Optimization Keyword: 3D point set matching, RMSD, geometric transformation, onetoone correspondence, branch and bound, probabilistic analysis,
Full Text: PDF(2.2MB)>>
Summary:
In this paper, we study the approximate point set matching (APSM) problem with minimum RMSD score under translation, rotation, and onetoone correspondence in ddimension. Since most of the previous works about APSM problems use similality scores that do not especially care about onetoone correspondence between points, such as Hausdorff distance, we cannot easily apply previously proposed methods to our APSM problem. So, we focus on speedup of exhaustive search algorithms that can find all approximate matches. First, we present an efficient branchandbound 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 3D molecular datasets showed that our branchandbound algorithm achieved significant speedup over the naive algorithm still keeping the advantage of generating all answers.

