There are provided video encoders and corresponding methods for encoding video data for an image that is divisible into macroblocks. A video encoder includes an encoder for performing into mode selection when encoding a current macroblock by testing a first subset of intra modes to compute a rate distortion cost, and utilizing the rate distortion cost to determine whether to terminate the intra mode selection and which additional intra modes, if any, are to be examined with respect to the current macroblock.