1. A method for sub-pixel motion estimation in video encoding comprising: in a design phase performed off-line before runtime motion estimation has begun, generating a plurality of non-linear design-phase building surfaces in an iterative process using sets of input frames as statistical data, wherein the iterative process of the design phase comprises: for each iteration: calculating an actual design-phase matching criterion surface according to a received source frame and a reference frame; generating an estimated design-phase matching criterion surface based on samples of the actual design-phase matching criterion surface in chosen displacement points and current design-phase building surfaces; and comparing an error between the estimated design-phase matching criterion surface and the actual design-phase matching criterion surface to a predetermined threshold; generating, in real time, an estimated matching criterion surface representing a matching criterion between a first real-time image and a second real-time image based on the design-phase building surfaces and a plurality of sample points of an actual real-time matching criterion surface; and selecting, in real time, a location on the estimated matching criterion surface, wherein the location represents a best match between the first image and the second image.