An improved MPEG-4 to H.264 transcoding algorithm is provided, exploiting residual, coding mode and motion vector information from the MPEG-4 stream. The use of the relative sum of absolute residuals (RSAR) to classify macroblocks (MB) leads to small sets of coding modes (CM) to test, and significantly reduces the computational complexity. In addition, RSAR is used to conditionally refine motion vectors (MV); only those MVs most likely to lead to quality improvements are refined. The average RSAR statistics are obtained from the transcoding of the previous Inter frame to provide adaptive thresholds for coding mode selection as well as conditional MV refinement. A corresponding video transcoder system is also provided.