Fully connected Markov random fields and conditional random fields have recently been shown to be advantageous in many early vision tasks being formulated as multi-labeling problems, such as stereo matching and image segmentation. The maximum posterior marginal (MPM) inference method in solving fully connected models uses a hybrid framework of mean-field (MF) method and a filtering like approach, and yields excellent results. In this paper, we extend this framework in several aspects. First, we provide an alternative inference method employing fractional belief propagation based method instead of MF. Second, we reformulate the MPM problem into a maximum a posterior (MAP) problem and provide efficient algorithms for solving this. Third, we extend the fully connected model into a multi-resolution approach. Finally, we propose an integral image based approach which makes it possible for efficiently integrating the local linear regression technique into this framework. Comparisons are carried out among different algorithms and different formulations to find the best combination. We demonstrate that the use of our multi-resolution approach with MAP formulation substantially outperforms the ordinary MF-based inference scheme.