Fundamental limits of Bayesian inference: Order parameters and phase transitions for road tracking

There is a growing interest in formulating vision problems in terms of Baye sian inference and, in particular, the maximimum a posteriori (MAP) estimat or. This approach involves putting prior probability distributions, P(X), o n 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 configurat ion 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 probabilit y distribution P(X, Y) on the ensemble of problem instances. In this paper, we consider the special case of detecting roads from aerial images [9] and demonstrate that analysis of this ensemble enables us to determine fundame ntal bounds on the performance of the MAP estimate (independent of the infe rence algorithm employed). We demonstrate that performance measures-such as the accuracy of the estimate and whether the road can be detected at all-d epend on the probabilities P(Y\X), P(X) only by an order parameter K. Intui tively, K summarizes the strength of local cues (as provided by local edge filters) together with prior information (i.e., the probable shapes of road s). 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 dete ct the road by any algorithm. In related work [25], [5], 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 a pproach can be applied to other vision problems and we briefly summarize re sults when the model uses the "wrong prior" [26]. We comment on how our wor k relates to studies of the complexity of visual search [21] and to critica l behaviour(i.e., phase transitions) in the computational cost of solving N P-complete problems [19].