We present a new algorithm to register 3D pre-operative Magnetic Resonance (MR) images to intra-operative MR images of the brain which have undergone brain shift. This algorithm relies on a robust estimation of the deformation from a sparse noisy set of measured displacements. We propose a new framework to co mpute the displacement field in an iterative process, allowing the solution to gradually move from an approximation formulation (minimizing the sum of a re gularization term and a data error term) to an interpolation formulation (least square minimization of the data error term). An outlier rejection step is i ntroduced in this gradual registration process using a weighted least trimmed squares approach, aiming at improving the robustness of the algorithm. We use a patient-specific model discretized with the finite element method (FEM) in order to ensure a realistic mechanical behavior of the brain tissue. To meet the clinical time constraint, we parallelized the slowest step of the algorithm so that we can perform a full 3D image registration in 35 seconds ( including the image update time) on a heterogeneous cluster of 15 PCs. The algorithm has been tested on six cases of brain tumor resection, presenting a brain shift of up to 14 mm. The results show a good ability to recover la rge displacements, and a limited decrease of accuracy near the tumor resection cavity.