Abstract: A rate-distortion computation model is established for approximately estimating the total quantization distortion of one frame, and a new real time Intra-update criterion is proposed. Through comparing the increased quantization distortion and reduced propagation distortion by intra-updating, the encoder can quickly decide which macroblock need to be intra-updated. Simulation results show that the performance of proposed algorithm, which reduces the computational complexity significantly, achieves the same or even better gains over traditional rate-distortion based Intra-update methods.