A method of compressing a video signal, comprising: receiving a video signal comprising a plurality of video frames, each frame representing an image at a different respective time, and each frame comprising a plurality of constituent blocks of the respective image, wherein the plurality of constituent blocks are arranged in intervals of whole blocks; for each of a plurality of current blocks to be encoded out of the plurality of constituent blocks within a frame of the video signal, selecting a respective reference block from the plurality of constituent blocks within one or more of said plurality of frames, and generating difference data for the current block relative to the respective reference block; and generating an encoded bitstream comprising the difference data together with side information identifying the selected reference blocks, and outputting the bitstream to one of a transmission medium and a storage medium for supply to a decoder; wherein each of said reference blocks is selected by: sorting a set of blocks including the current block, from said plurality of constituent blocks within the one or more of said plurality of frames, into an order according to a first metric other than spatial proximity to the current block, wherein the first metric is at least one of: a measure of block energy relative to that of the current block or a measure of the structural similarity with the current block; determining a group of candidate blocks from the sorted set of blocks by searching the sorted set of blocks to select a subset of candidate blocks based on the first metric comprising at least some candidate blocks other than immediately adjacent spatial neighbours of the current block; and selecting one of said candidate blocks as the reference block based on a second metric different from the first metric, the second metric relating to a number of bits that would be required in the encoded bitstream to encode both the difference data and the side information identifying the candidate as the reference block. receiving a video signal comprising a plurality of video frames, each frame representing an image at a different respective time, and each frame comprising a plurality of constituent blocks of the respective image, wherein the plurality of constituent blocks are arranged in intervals of whole blocks; for each of a plurality of current blocks to be encoded out of the plurality of constituent blocks within a frame of the video signal, selecting a respective reference block from the plurality of constituent blocks within one or more of said plurality of frames, and generating difference data for the current block relative to the respective reference block; and generating an encoded bitstream comprising the difference data together with side information identifying the selected reference blocks, and outputting the bitstream to one of a transmission medium and a storage medium for supply to a decoder; wherein each of said reference blocks is selected by: sorting a set of blocks including the current block, from said plurality of constituent blocks within the one or more of said plurality of frames, into an order according to a first metric other than spatial proximity to the current block, wherein the first metric is at least one of: a measure of block energy relative to that of the current block or a measure of the structural similarity with the current block; determining a group of candidate blocks from the sorted set of blocks by searching the sorted set of blocks to select a subset of candidate blocks based on the first metric comprising at least some candidate blocks other than immediately adjacent spatial neighbours of the current block; and selecting one of said candidate blocks as the reference block based on a second metric different from the first metric, the second metric relating to a number of bits that would be required in the encoded bitstream to encode both the difference data and the side information identifying the candidate as the reference block. sorting a set of blocks including the current block, from said plurality of constituent blocks within the one or more of said plurality of frames, into an order according to a first metric other than spatial proximity to the current block, wherein the first metric is at least one of: a measure of block energy relative to that of the current block or a measure of the structural similarity with the current block; determining a group of candidate blocks from the sorted set of blocks by searching the sorted set of blocks to select a subset of candidate blocks based on the first metric comprising at least some candidate blocks other than immediately adjacent spatial neighbours of the current block; and selecting one of said candidate blocks as the reference block based on a second metric different from the first metric, the second metric relating to a number of bits that would be required in the encoded bitstream to encode both the difference data and the side information identifying the candidate as the reference block.