Convergence Rates of Algorithms for Visual Search: Detecting Visual Contours

Abstract

This paper formulates the problem of visual search as Bayesian inference and defines a Bayesian ensemble of problem instances . In particular, we address the problem of the detection of visual contours in noise/clutter by optimizing a global criterion which combines local intensity and geometry information. We analyze the convergence rates of A * search algorithms using results from information theory to bound the probability of rare events within the Bayesian ensemble. This analysis determines characteristics of the domain , which we call order parameters, that determine the convergence rates. In particular, we present a specific admissible A * algorithm with pruning which converges, with high probability, with expected time O(N) in the size of the problem. In addi(cid:173) tion, we briefly summarize extensions of this work which address fundamental limits of target contour detectability (Le. algorithm independent results) and the use of non-admissible heuristics.