Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Approximate decision algorithms for point set congruence

Heffernan, Paul J. and Schirra, Stefan

MPI-I-91-110. August 1991, 25 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
This paper considers the computer vision problem of testing whether
two equal cardinality point sets $A$ and $B$ in the plane are
We say that $A$ and $B$ are $\varepsilon$-congruent if there exists
an isometry $I$ and bijection $\ell : A \rightarrow B$ such that
$dist(\ell(a),I(a)) \leq \varepsilon$, for all $a
\in A$. Since known methods for this problem are expensive, we develop
approximate decision algorithms that are considerably faster
than the known decision algorithms, and have bounds on their
imprecision. Our approach reduces the problem to that of computing
maximum flows on a series of graphs with integral capacities.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-91-110.pdf14040 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Heffernan, Paul J. and Schirra, Stefan},
  TITLE = {Approximate decision algorithms for point set congruence},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-91-110},
  MONTH = {August},
  YEAR = {1991},
  ISSN = {0946-011X},