In some embodiments, a method of determining encoding type and predictive mode(s) selections for a macroblock of a video frame is provided. In some embodiments, a general method 1) selects the encoding type (16×16 or 4×4) that is initially considered for a macroblock using an encoding type selection algorithm (based on an attribute of the macroblock that is easy to compute), 2) if the 16×16 encoding type is selected in step 1, consider the four 16×16 prediction modes that may be used on the macroblock using conventional methods or an improved 16×16 predictive mode search algorithm based on distortion thresholds, and 3) if the 4×4 encoding type is selected in step 1, select the 4×4 prediction mode to be used for each of the sixteen 4×4 blocks of the macroblock using conventional methods or an improved 4×4 predictive mode search algorithm based on the positional relationships between predictive modes.