Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!VANZETTI.CS.NYU.EDU!rigoutso
From: rigoutso@VANZETTI.CS.NYU.EDU (Isidore  Rigoutsos)
Newsgroups: comp.ai.neural-nets
Subject: Re: matching sets of points in 2 space
Message-ID: <9105062207.AA24284@VANZETTI.CS.NYU.EDU>
Date: 6 May 91 22:07:36 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: New York University
Lines: 48


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


-- 
##