A method of encoding a video stream comprising: for each of a plurality of first image portions to be encoded in an outgoing video stream, selecting a preferred one of a set of potential encoding modes using a first process comprising an estimation of distortion of the first image portion and a measure of bit rate required to encode the first image portion for each of the first image portion's potential encoding modes; encoding each of the first image portions of the outgoing stream using the respective selected encoding mode; for each of a plurality of second image portions of a video stream, applying a second process comprising at least an estimation of distortion of the second image portion; and using an output of the second process resulting from the second image portions to bias the first process in said selection of the encoding modes for the first portions.