ibarroda@csr (Ian Barrodale) (05/02/91)
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. The
following is a list of questions that we have at this time:
1. Should we try to emulate human vision in solving the above problem
or use only simple geometric considerations?
2. If the solution emulates human vision (i.e. does not directly use
coordinate information), what type of feature or point relationships
should it use?
3. If the solution uses coordinate information, what type of geometric
feature or geometric relationship would it be based on?
4. Can the given data be transformed such that the problem becomes
simpler? For example, can the problem be restate as the solution of
two one dimensional comparisons?
5. Can this problem be formulated such that it can be solved using a
Hough transform approach?
6. Can this problem be formulated such that it can be solved using a
neural network approach?
7. Can this problem be formulated such that it can be solved using
genetic algorithms?
8. What other types of approach may lead to a solution of the above
problem.
Thank you.
Ian Barrodale.
ibarroda@csr.uvic.ca
(604) 721-2206
Suite 8 - 1560 Church Avenue,
Victoria, B.C,
Canada, V8P 2Hitmb@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.
rigoutso@VANZETTI.CS.NYU.EDU (Isidore Rigoutsos) (05/07/91)
In-reply-to: ibarroda@csr's message of 2 May 91 15:44:47 GMT
One could use geometric constraints to solve the stated problem. The
geometric hashing method takes such an approach. The following are some
references:
Hummel, R. and H. Wolfson. ``Affine Invariant Match-
ing''. In "Proceedings of the Darpa Image Understanding
Workshop, April 1988.
Lamdan, Y. and H. Wolfson. ``Geometric Hashing: A Gen-
eral and Efficient Model-Based Recognition Scheme''. In
"Proceedings of the 2nd International Conference on Computer
Vision, Ann Arbor, Michigan, June 1988.
Rigoutsos, I. and R. Hummel. ``Scalable Parallel
Geometric Hashing for Hypercube SIMD Architectures''. Techn-
ical Report 553, Courant Institute of Mathematical Sciences,
New York University.
Rigoutsos, I. and R. Hummel. ``Scalable Implementation
of Geometric Hashing on the Connection Machine''. In
Proceedings "Workshop on Direction in Automated CAD-Based
Vision Systems", Maui, Hawaii, June 1991. Also Technical
Report 554, Courant Institute of Mathematical Sciences, New
York University.
Rigoutsos, I. and R. Hummel. ``Robust Similarity/Affine
Invariant Matching in the Presence of Noise''. Submitted to
8'th Israeli Conference on Artificial Intelligence and Com-
puter Vision. Tel-Aviv, 1991.
We currently have a working system on the Connection Machine. The database
contains 1024 models each consisting of 16 points. With scenes of 200 points
and one embedded model, one can achieve recognition times of ~10 seconds on a
64-K model. A new approach allows robust recognition in the presence of high
levels of noise: assuming a Gaussian distributed positional error of standard
deviation sigma, robust recognition is achieved for values of sigma >= 3.5
pixels.
Isidore Rigoutsos
--
##sfb@NCoast.ORG (Stephen F. Bush) (05/09/91)
I am interested in any information/conferences/seminars on AI applied to computer networking. I would imagine there should be applications of expert systems, neural networks, and genetic algorithms towards network network management. Any information would be appreciated. Thank You, Steve Bush GE Information Systems