The invention relates to a video encoder (201) for encoding a video signal. The video encoder comprises a segmentation processor (207) which divides the picture into picture regions. Preferably, picture regions having a high degree of flatness or uniformity are determined in this way. A characteristics processor (209) determine a spatial frequency characteristic for each picture region, and a coding controller (211) selects an encoding block size, such as a prediction block size for motion estimation, in response to the spatial frequency characteristic. An encode processor (213) encodes the picture using the selected encoding block size. Specifically, increasing block sizes are selected for increasing degrees of uniformity or flatness indicated by the spatial frequency characteristic. Thereby, an increasing proportion of high frequency components and a consistent choice of encoding block sizes are maintained, and thus the coding artefacts from many encoders having variable prediction block sizes is reduced. The invention is particularly suitable for H.264 and similar encoders.