The use of BP removes a serious restriction imposed in related earlier work, in which the matching is performed by dynamic programming and thus requires the graphical model to be tree-shaped (i.e. without loops). Although BP is not guaranteed to converge when applied to inference on non-tree-shaped graphs, we find empirically that it does converge even for deformable template models with one or more loops. To speed up the BP algorithm, we augment it by a pruning procedure and a novel technique, inspired by the 20 Questions (divide-and-conquer) search strategy, called ”focused message updating.” These modifications boost the speed of convergence by over an order of magnitude, resulting in an algorithm that detects and localizes shapes in grayscale images in as little as several seconds on an 850 MHz AMD processor.