We describe a new approach to feature-based object recognition, using maximum a posteriori (MAP) estimation under a Markov random field (MRF) model. The main advantage of this approach is that it allows explicit modeling of dependencies between individual features of an object. For instance, we use the approach to model the fact that mismatched features due to partial occlusions tend to form spatially coherent groups rather than being independent. Efficient computation of the MAP estimate in our framework can be accomplished by finding a minimum cut on an appropriately defined graph. An even more efficient approximation, that does not use graph cuts, is also presented. This approximation technique, which we call spatially coherent matching (SCM), is closely related to generalized Hausdorff matching. We report some Monte Carlo experiments showing that the SCM technique improves substantially on the tradeoff between correct detection and false alarms compared with previous feature matching methods such as the Hausdorff distance.