Combinatorial and experimental results for randomized point matching algorithms

Publisher Website
Google Scholar
Abstract
The subject of this paper is the design and analysis of Monte Carlo algorithms for two basic mat thing techniques used in model-based recognition: alignment, and geometric hashing. We first give analyses of our Monte Carlo algorithms, showing that they are asymptotically faster than their deterministic counterparts while allowing failure probabilities that are provably very small. We then describe experiment al results that bear out this speed-up, suggesting that randomization results in significant improvements in running time. Our theoretical analyses are not the best possible; as a step to remedying this we define a combinatorial measure of self-similarity for point sets, and give an example of its power. 1 Overview Model-based recognition is an important component of comput er vision. We study Monte Carlo algorithms for two basic approaches to model-based object recognition: alignment, and geometric hashing. We present analyses and experimental data

This publication has 0 references indexed in Scilit: