US 2020/0394444 A1 · ASSOCIATING SPATIAL POINT SETS WITH CANDIDATE CORRESPONDENCES

Abstract

A computer implemented method for generating a one-to-one mapping between a first spatial point set and a second spatial point set in nD comprising receiving a first and a second spatial point sets in nD and a plurality of candidate correspondences; computing conflict lists for the candidate correspondences; generating one or more MatchPairs between the first and the second point sets using the Cartesian Products of the plurality of candidate correspondences; computing local distance measures for the MatchPairs; converting the local distance measures to weights; computing conflict lists for pairs of the MatchPairs by taking the bitwise UNIONs of their candidate correspondences' unit conflict lists; computing correspondence lists for the MatchPairs; computing compatibilities between pairs of the MatchPairs by examining for each pair of said pairs the bitwise AND of one's correspondence list and the other's conflict list; constructing an undirected graph with its nodes corresponding to the MatchPairs, its edges representing the compatibilities, and its graph vertices assigned the weights; computing a maximum-weight clique of the graph; and merging the maximum-weight clique to generate the one-to-one mapping.

Claims20

Dependent claims

A system for generating a one-to-one mapping between a first spatial point set and a second spatial point set in nD, the system comprising:

(a) a programmable processor;
and
(b) a memory coupled with the programmable processor and embodying information indicative of instructions that cause the programmable processor to perform operations comprising:
receiving a first and a second spatial point sets in nD, and a plurality of candidate correspondences;
computing unit conflict lists for said candidate correspondences;
generating one or more MatchPairs between said first and second point sets using the Cartesian Products of said plurality of candidate correspondences;
computing local distance measures for said MatchPairs;
converting said local distance measures to weights;
computing conflict lists for said MatchPairs by computing the bitwise UNIONs of their candidate correspondences' unit conflict lists;
computing correspondence lists for said MatchPairs;
computing the compatibilities between pairs of said MatchPairs by examining for each pair of said pairs the bitwise AND of one's correspondence list and the other's conflict list;
constructing an undirected graph with its vertices corresponding to said MatchPairs, its edges representing said compatibilities, and its graph vertices assigned said weights;
computing a maximum-weight clique of said graph;
merging said maximum-weight clique to generate the one-to-one mapping.

11 more elements

A method of using a computing device to generate a one-to-one mapping between a first spatial point set and a second spatial point set in nD, the method comprising:

(a) providing a computing device with a Matching Unit;
(b) using said computing device to receive a first and a second spatial point sets in nD, and a plurality of candidate correspondences;
(c) using said computing device to compute unit conflict lists for said candidate correspondences;
(d) using said computing device to generate one or more MatchPairs between said first and second point sets using the Cartesian Products of said plurality of candidate correspondences;
(e) using said computing device to compute local distance measures for said MatchPairs;
(f) using said computing device to convert said local distance measures to weights;
(g) using said computing device to compute conflict lists for said MatchPairs by computing the bitwise UNIONs of their candidate correspondences' unit conflict lists;
(h) using said computing device to compute correspondence lists for said MatchPairs;
(i) using said computing device to compute the compatibilities between pairs of said MatchPairs by examining for each pair of said pairs the bitwise AND of one's correspondence list and the other's conflict list;
(j) using said computing device to construct an undirected graph with its vertices corresponding to said MatchPairs, its edges representing said compatibilities, and its graph vertices assigned said weights;
(k) using said computing device to compute a maximum-weight clique of said graph;
(l) using said computing device to merge said maximum-weight clique to generate the one-to-one mapping.

9 more elements

Dependencies are inferred from the claim text.

Associating spatial point sets with candidate correspondences

Life of this patent

Associating spatial point sets with candidate correspondences

Life of this patent

Abstract

Claims20