MPI-I-91-110
Approximate decision algorithms for point set congruence
Heffernan, Paul J. and Schirra, Stefan
August 1991, 25 pages.
.
Status: available - back from printing
This paper considers the computer vision problem of testing whether
two equal cardinality point sets $A$ and $B$ in the plane are
$\varepsilon$-congruent.
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.
-
- Attachement: MPI-I-91-110.pdf (14040 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-110
BibTeX
@TECHREPORT{HeffernanSchirra91,
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},
}