\magnification=1200
\baselineskip=20pt
\nopagenumbers
\font\big=cmr12 scaled \magstep2

\centerline{\bf STANFORD UNIVERSITY}
\centerline{\bf DEPARTMENT OF STATISTICS}
\centerline{\big SPECIAL DEPARTMENTAL SEMINAR}
\bigskip

\baselineskip=12pt
\centerline{4:15 p.m., Thursday, April 20, 2000}
\centerline{Sequoia Hall Rm. 200}

\bigskip
\baselineskip=15pt
\centerline{\sl A. L. Yuille and James M. Coughlan}
\centerline{\sl mith-Kettlewell Eye Research Institute}
\centerline{\sl 2318 Fillmore Street}
\centerline{\sl San Francisco, CA 94115, USA}
\bigskip
\centerline{\bf Fundamental Limits of Bayesian Inference: }
\centerline{\bf Order Parameters and Phase Transitions for Road Tracking}
\bigskip


There is a growing interest in formulating vision problems in terms of Bayesian
inference and, in particular, the maximum a posteriori (MAP) estimator. This
approach involves putting prior 
probability distributions, P(X), on the variables X to be inferred and a
conditional distribution P(Y|X) for the measurements Y. For example, X could
denote the position and configuration of a road in an aerial image and Y can be
the aerial image itself (or a filtered version). We observe that these
distributions define a probability distribution P(X,Y) on the ensemble of
problem instances. In this paper we consider the special case of detecting
roads from aerial images (Gemand and Jedynak 1996) and demonstrate that
analysis of this ensemble enables us to determine fundamental bounds on the
performance of the MAP estimate (independent of the inference algorithm
employed).  

We demonstrate that performance measures -- such as the accuracy of the
estimate and whether the road can be detected at all -- depend on the
probabilities P(Y|X), P(X) only by an order parameter
K. Intuitively, K summarizes the strength of local cues (as provided by local
edge filters) together with prior information (i.e. the probable shapes of
roads). We demonstrate that there is a phase transition at a critical value of
the order parameter K -- below this phase transition it is impossible to detect
the road by any algorithm. In related work (Yuille and Coughlan 1999), we
derive closely related order parameters which determine the time and memory
complexity of search and the accuracy of the solution using the A* search
strategy. Our approach can be applied to other vision problems and we briefly
summarize results when the model uses the ``wrong prior'' . We comment on how
our work relates to studies of the complexity of visual search (Tsotsos 1991)
and to critical behaviour (i.e.  phase transitions) in the computational cost
of solving NP-complete problems (Selman and Kirkpatrick).

\bye