We present a new algorithm to register 3-D preoperative magnetic resonance (MR) images to intraoperative 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 compute the displacement field in an iterative process, allowing the solution to gradually move from an approximation formulation (minimizing the sum of a regularization term and a data error term) to an interpolation formulation (least square minimization of the data error term). An outlier rejection step is introduced 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 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 3-D image registration in 35 s (including the image update time) on a heterogeneous cluster of 15 personal computers. 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 large displacements, and a limited decrease of accuracy near the tumor resection cavity.