| |
Abstract:
This paper develops a theory for the convergence rates of
algorithms for performing visual search tasks (formulated in a
Bayesian framework). Our approach makes use of the A* search
strategy and mathematical results from the theory of types in
information theory. In particular, we formulate the problem of the
detection of visual contours in noise/clutter by optimizing a
global criterion for combining local intensity and geometry
information. We analyze the convergence rates of A* search
algorithms for detecting the target contour. This analysis
determines characteristics of the domain, which we call order
parameters, which determine the convergence rates. In particular,
we present a specific admissible A* algorithm with pruning which
converges, with high probability, with expected time in the size of
the problem. In addition, we briefly summarize extensions of this
work which address fundamental limits of target contour
detectability (i.e. algorithm independent results) and the use of
non-admissible heuristics.
|
