Modern video codecs such as MPEG2, MPEG4-ASP and H.264 depend on sub-pixel motion estimation to optimise rate-distortion efficiency. Sub-pixel motion estimation is implemented within these standards using interpolated values at 1/2 or 1/4 pixel accuracy. By using these interpolated values, the residual energy for each predicted macroblock is reduced. However this leads to a significant increase in complexity at the encoder, especially for H.264, where the cost of an exhaustive set of macroblock segmentations needs to be estimated for optimal mode selection. This paper presents a novel scheme for sub-pixel motion estimation based on the whole-pixel SAD distribution. Both half-pixel and quarter-pixel searches are guided by a model-free estimation of the SAD surface using a two dimensional kernel method. While giving an equivalent rate distortion performance, this approach approximately halves the number of quarter-pixel search positions giving an overall speed up of approximately 10% compared to the EPZS quarter-pixel method (the state of the art H.264 optimised sub-pixel motion estimator).