In this paper, we propose a novel global Markov Random Field based image inpainting method with context-aware label selection. Context is determined based on the texture and color features in fixed image regions and is used to distinguish areas of similar content to which the search for candidate patches is limited. Furthermore, we introduce a novel optimization approach, as an alternative to priority belief propagation framework, which further reduces the number of candidates and performs efficient inference to obtain final inpainting result. Experimental results show improvement over related state-of-the-art methods. Moreover, global optimization is significantly accelerated with the proposed inference approach.