A novel multi-pass encoding method that encodes several images (e.g., several frames of a video sequence) is described. The method iteratively performs an encoding operation that encodes these images. The encoding operation is based on a nominal quantization parameter, which the method uses to compute quantization parameter for the images. During several different iterations of the encoding operation, the method uses several different nominal quantization parameters. The method stops its iterations when it reaches a terminating criterion (e.g., it identifies an acceptable encoding of the images).