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.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS[0001]This application is related to U.S. application Ser. No. 16 / 428,970 filed on Jun. 1, 2019.COPYRIGHT NOTICE[0002]A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.BACKGROUND—PRIOR ART[0003]The following is a tabulation of some prior art that presently appears relevant:U.S. Patents[0004]Pat. No.Kind CodeIssue DatePatentee6,640,201B1Oct. 28, 2003Hahlweg7,373,275B2May 13, 2008Kraft9,020,274B2Apr. 28, 2015Xiong et al.8,811,772B2Aug. 19, 2014Yang8,571,351B2Oct. 19, 2013Yang8,233,722B2Jul. 31, 2012Kletter et al.8,144,947B2Mar. 27, 2012Kletter et al.6,272,245B1Aug. 7, 2001Lin7,010,158B2Mar. 7, 2006Cahill et al.Nonpatent Literature Docum...

AI Technical Summary

Benefits of technology

The patent text describes a method for creating a direct connection between two sets of points in space. It explains how to efficiently determine if two points are compatible with each other. The technical effect of this invention is the ability to quickly and accurately match points in different spatial locations.

Problems solved by technology

Besides, the matching of spatial point sets is an important problem in various computer vision and pattern recognition areas such as motion tracking, localization, shape matching, and industrial inspection.

Often captured signals are extracted to a measurement point set using various interest point or bounding box detectors (e.g. the SIFT, SURF, various corner or blob detectors, various object detection neural networks etc.), and the problem becomes matching the measurement point set with a given point set.

On the other hand, if the number of candidate mappings is large and the energy landscape is rough with lots of local minima (or maxima), then sometimes the practice is to use heuristics.

Also I think if one wants to consider the geometric relationships among key points that are far away from each other using this method, neighborhoods of different sizes may need to be considered, and this may further increases the number of fingerprints.

But since an affine transformation is a mixture of rotation, scaling, displacement and shearing, which are mingled together into the elements of an affine transformation matrix, the significant elements of the matrix do not have much physical meaning.

Thus the Euclidean distance may not accurately capture the differences between affine transformations.

Images