Exemplar-based inpainting methods involve three critical steps: finding the patch processing order, searching for best matching patches, and estimating the unknown pixels from the best matching patches. The paper addresses each step and first introduces a new patch priority term taking into account the presence of edges in the patch to be filled-in. The paper then presents a method using linear regression based local learning of subspace mapping functions to enhance the search for the nearest neighbors (K-NN) to the input patch in the particular case of inpainting. Several neighbor embedding (NE) methods are then considered for estimating the unknown pixels. The performances of the resulting inpainting algorithms are assessed in two application contexts: object removal and loss concealment. In the loss concealment application, the ground truth is known, hence objective measures (e.g., PSNR) can be used to assess the performances of the different methods. The inpainting results are compared against those obtained with various state-of-the-art solutions for both application contexts.