We introduce an approach to feature-based object recognition, using maximum a posteriori (MAP) estimation under a Markov random field (MRF) model. Our approach assumes that both the location of the model and a configuration of matching features are not directly observable and have to be estimated. We consider a wide class of priors that explicitly model dependencies between individual features of an object. These priors capture phenomena such as the fact that unmatched features due to partial occlusion are generally spatially correlated rather than independent. Our algorithm uses an efficient graph cut technique to resolve technical difficulties introduced by dependencies between the features. The method allows hierarchical search space pruning to find the location of the model. A special case of our framework yields a particularly efficient approximation method. We call this special case {\em spatially coherent matching} (SCM). The SCM method operates directly on the image feature map, rather than relying on the graph-based methods used in the general framework. Interestingly, in the extreme case of completely independent features our general Bayesian framework reduces to Hausdorff matching. We present some Monte Carlo experiments showing that models accounting for dependencies between the features can yield substantial improvements over Hausdorff matching for cluttered scenes and partially occluded objects.