tmb@ai.mit.edu (Thomas M. Breuel) (05/04/91)
In-reply-to: ibarroda@csr's message of 2 May 91 15:44:47 GMT Newsgroups: comp.ai.neural-nets, comp.ai, comp.ai.vision Subject: Re: matching sets of points in 2 space References: <ibarroda.673199087@csr> Distribution: FCC: /homes/tmb/mail/nout --text follows this line-- > Point Set Matching > ------------------ > (Barrodale Computing Services Ltd, May 1991). > > Problem Definition: > We are given two sets of points in the plane. These points could represent > two `simplified' images or output from some sensors. The first set > contains M points. The second set is similar to the first set, except > that some of the points from the first set are missing and some new > points, not in the first set, are present. The second set contains N > points. The positions of the points in the second set are, within a > given tolerance, the same as common points in the first set. However, > within this tolerance fairly large local distortions can occur. > > The problem has three parts: > 1. Find all the points in the first set which do not have a match in > the second set. > > 2. Find all points in the second set which do not have a match in > the first set. > > 3. For all points in the first set which have a common point in the > second set find the correct match. > > Questions: > We are interested in hearing from anyone who has worked on the above > problem or has worked on related problems. We are also interested in > looking at the possibility of using artificial intelligence > techniques, like neural networks, for solving the problem. [since this question seems to come up from time-to-time, I'm posting this response] The following papers will give you a good start at the literature (Eric Grimson's book has an extensive bibliography of the pre-1990 work on the subject; you should look there for other references): Alt H., Mehlhorn K., Wagener H., Welzl E., 1988, Congruence, Similarity, and Symmetries of Geometric Objects., Discrete and Computational Geometry. Baird H. S., 1985, Model-Based Image Matching Using Location, MIT Press, Cambridge, MA. Breuel T. M., 1991, An Efficient Correspondence Based Algorithm for 2D and 3D Model Based Recognition, In Proceedings IEEE Conf. on Computer Vision and Pattern Recognition. Cass T. A., 1990, Feature Matching for Object Localization in the Presence of Uncertainty, In Proceedings of the International Conference on Computer Vision, Osaka, Japan, IEEE, Washington, DC. Grimson E., 1990, Object Recognition by Computer, MIT Press, Cambridge, MA. State-of-the-art algorithms running on a SparcStation can find optimal solutions (either maximal size of match at given error or minimum error at given size of match) to this kind of bounded error recognition problem on the average in under a minute, for models consisting of hundreds points of and images consisting of 1000-2000 unlabeled, oriented features.