Image frames of a video stream are encoded with the aim of reducing flicker in the video stream when displayed. In one embodiment, the quantization parameter used to quantize an image frame is capped to be not greater than a quantization parameter used to quantize an immediately previous image frame. In another embodiment, the quantization step size used to quantize a macro-block of an image frame is computed based on the value of a quantization error of a co-located macro-block in an immediately previous image frame. In yet another embodiment, macro-block transform coefficients corresponding to high-frequency components are quantized using relatively higher quantization parameter values if the image frame is deemed to contain high activity. In yet another embodiment, flicker-prone macro-blocks of a source frame are replaced by corresponding best-match macro-blocks of a previous reconstructed frame, prior to being encoded.