In this paper, we first introduce a general approach for context-aware patch-based image inpainting, where textural descriptors are used to guide and accelerate the search for well-matching (candidate) patches. A novel top-down splitting procedure divides the image into variable size blocks according to their context, constraining thereby the search for candidate patches to non-local image regions with matching context. This approach can be employed to improve the speed and performance of virtually any (patch-based) inpainting method. We apply this approach to the so-called global image inpainting with the Markov random field (MRF) prior, where MRF encodes a priori knowledge about consistency of neighbouring image patches. We solve the resulting optimization problem with an efficient low-complexity inference method. Experimental results demonstrate the potential of the proposed approach in inpainting applications like scratch, text and object removal. Improvement and significant acceleration of a related global MRF-based inpainting method is also evident