A NEW APPROACH TO POINT-PATTERN MATCHING

被引:46
作者
MURTAGH, F
机构
关键词
D O I
10.1086/132993
中图分类号
P1 [天文学];
学科分类号
0704 ;
摘要
We describe a new algorithm for matching star lists, given by their two-dimensional coordinates. Such matching should be unaffected by translation, rotation, rescaling, random perturbations, and some random additions and deletions of coordinate couples in one list relative to another. The first phase of the algorithm is based on a characterization of a set of coordinate couples, relative to each individual coordinate couple. In the second phase of the algorithm, the matching of stars in different lists is based on proximity of feature vectors associated with coordinate couples in the two lists. The order of magnitude computational complexity of the overall algorithm is n2 for O(n) coordinate couples in the coordinate lists.
引用
收藏
页码:301 / 307
页数:7
相关论文
共 17 条
[1]   OPTIMAL EXPECTED-TIME ALGORITHMS FOR CLOSEST POINT PROBLEMS [J].
BENTLEY, JL ;
WEIDE, BW ;
YAO, AC .
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1980, 6 (04) :563-580
[2]   USING MOTION FROM ORTHOGRAPHIC VIEWS TO VERIFY 3-D POINT MATCHES [J].
CHEN, HH ;
HUANG, TS .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1991, 13 (09) :872-878
[3]  
Domenges D., 1979, ANN INSEE, V35, P3
[4]   POINT PATTERN-MATCHING USING CENTROID BOUNDING [J].
GRIFFIN, PM ;
ALEXOPOULOS, C .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1989, 19 (05) :1274-1276
[5]   A PATTERN-MATCHING ALGORITHM FOR TWO-DIMENSIONAL COORDINATE LISTS [J].
GROTH, EJ .
ASTRONOMICAL JOURNAL, 1986, 91 (05) :1244-1248
[6]   APPROXIMATE STRING MATCHING [J].
HALL, PAV ;
DOWLING, GR .
COMPUTING SURVEYS, 1980, 12 (04) :381-402
[7]  
JOHNSTON MD, 1991, IN PRESS J COMPUT OP
[8]   AN OVERVIEW OF SEQUENCE COMPARISON - TIME WARPS, STRING EDITS, AND MACROMOLECULES [J].
KRUSKAL, JB .
SIAM REVIEW, 1983, 25 (02) :201-237
[9]  
Murtagh F., 1985, MULTIDIMENSIONAL CLU
[10]   HOPFIELD NETWORK FOR STEREO VISION CORRESPONDENCE [J].
NASRABADI, NM ;
CHOO, CY .
IEEE TRANSACTIONS ON NEURAL NETWORKS, 1992, 3 (01) :5-13