1. A computer-readable medium storing computer-executable instructions for causing a processor programmed thereby to perform a method, wherein the computer-readable medium is selected from the group consisting of only a non-volatile memory, magnetic disk storage, CD ROM and DVD, the method comprising: encoding a first video frame of a video sequence using intraframe coding, including: computing a spatial extrapolation for a current block of pixel values in the first video frame; computing a spatial-extrapolation residual based upon the current block in the first video frame and the spatial extrapolation; and applying a re-oriented frequency transform to the spatial-extrapolation residual, wherein the re-oriented frequency transform addresses non-stationarity in pixel values of the spatial-extrapolation residual due to the spatial extrapolation; outputting encoded video data for the first video frame in a bitstream; encoding a second video frame of the video sequence, including: computing a motion-compensated prediction for a current block in the second video frame; computing a motion-compensated prediction residual based upon the current block in the second video frame and the motion-compensated prediction; encoding the motion-compensated prediction residual using a variable-block-size frequency transform with support for switching of transform size at varying levels within the second video frame; and outputting encoded video data for the second video frame in the bitstream, wherein the bitstream includes switching information that indicates the transform size used for the motion-compensated prediction residual, and wherein format of the bitstream allows signaling of the switching information within the bitstream at frame level for the second video frame or at macroblock level.