Described herein are techniques related to motion estimation for video encoding. In particular, integer estimation is performed on a reference video frame, and a best size macro block is determined. A fractional estimation is performed on that best size macro block. Based on the fractional estimation, a determination is made if an improvement occurs over the macro block from the integer estimation. If such an improvement occurs, then all sub shapes of the best size macro block from the integer search/estimation are updated. Furthermore, the new sub macro block is chosen as the final macro block to be used for video encoding.