A method for sub-pixel motion estimation in video encoding comprising: - in a design phase, performed by a pre-processing unit off-line before runtime motion estimation has begun, generating a plurality of pre-processed non-linear surfaces in an iterative process, wherein the iterative process comprises for each iteration: - calculating an actual matching surface for a set of frames that includes a source frame and a reference frame using a matching criterion; - generating an estimated matching surface based on samples of the actual matching surface in chosen displacement points and the pre-processed surfaces; and - updating the plurality of pre-processed surfaces to minimize an error between the estimated matching surface and the actual matching surface; and - in a real-time processing phase in order to find a best match between a first image and a second image: - calculating a plurality of sample points being the differences according to the matching criterion between the first image and the second image at the same locations as the chosen displacement points; - generating an estimated matching criterion surface representing the matching criterion between the first image and the second image based on the pre-processed surfaces and a plurality of sample points; and - selecting a location on the estimated matching criterion surface, wherein the selected location represents the best match between the first image and the second image. - in a design phase, performed by a pre-processing unit off-line before runtime motion estimation has begun, generating a plurality of pre-processed non-linear surfaces in an iterative process, wherein the iterative process comprises for each iteration: - calculating an actual matching surface for a set of frames that includes a source frame and a reference frame using a matching criterion; - generating an estimated matching surface based on samples of the actual matching surface in chosen displacement points and the pre-processed surfaces; and - updating the plurality of pre-processed surfaces to minimize an error between the estimated matching surface and the actual matching surface; and - calculating an actual matching surface for a set of frames that includes a source frame and a reference frame using a matching criterion; - generating an estimated matching surface based on samples of the actual matching surface in chosen displacement points and the pre-processed surfaces; and - updating the plurality of pre-processed surfaces to minimize an error between the estimated matching surface and the actual matching surface; - in a real-time processing phase in order to find a best match between a first image and a second image: - calculating a plurality of sample points being the differences according to the matching criterion between the first image and the second image at the same locations as the chosen displacement points; - generating an estimated matching criterion surface representing the matching criterion between the first image and the second image based on the pre-processed surfaces and a plurality of sample points; and - selecting a location on the estimated matching criterion surface, wherein the selected location represents the best match between the first image and the second image. - calculating a plurality of sample points being the differences according to the matching criterion between the first image and the second image at the same locations as the chosen displacement points; - generating an estimated matching criterion surface representing the matching criterion between the first image and the second image based on the pre-processed surfaces and a plurality of sample points; and - selecting a location on the estimated matching criterion surface, wherein the selected location represents the best match between the first image and the second image.