A method of compressing video data, the method comprising: providing image data for each of a plurality of image portions, wherein the provision of the image data comprises transforming each of said image portions from a spatial and/or temporal domain representation into a transform domain representation, thereby generating a respective set of transform domain coefficients for each image portion; for a target image portion to be encoded, identifying a matching image portion; and generating difference data for the target image portion relative to the matching image portion, and including the difference data in an encoded video signal; characterised by: determining an index value for each of said image portions based on the respective set of transform domain coefficients for each image portion, wherein the index value is an aggregate combination of transform domain coefficients of the respective image portion, the aggregate combination of transform domain coefficients of the respective image portion comprising one of: a number of zero or non-zero coefficients in each of said image portions, or an average or total of the moduli of coefficients of the respective image portion; for the target image portion to be encoded, identifying a matching image portion having an index value within a search threshold of the index value of the target image portion, wherein the identification of the matching image portion comprises: sorting a list of said image portions based on the index values so as to generate a sorted list; determining a group of candidate image portions each having a proximity to the target image portion being within the search threshold in the sorted list; and identifying a best matching image portion from amongst the group of candidate image portions. providing image data for each of a plurality of image portions, wherein the provision of the image data comprises transforming each of said image portions from a spatial and/or temporal domain representation into a transform domain representation, thereby generating a respective set of transform domain coefficients for each image portion; for a target image portion to be encoded, identifying a matching image portion; and generating difference data for the target image portion relative to the matching image portion, and including the difference data in an encoded video signal; a number of zero or non-zero coefficients in each of said image portions, or an average or total of the moduli of coefficients of the respective image portion; for the target image portion to be encoded, identifying a matching image portion having an index value within a search threshold of the index value of the target image portion, wherein the identification of the matching image portion comprises: sorting a list of said image portions based on the index values so as to generate a sorted list; determining a group of candidate image portions each having a proximity to the target image portion being within the search threshold in the sorted list; and identifying a best matching image portion from amongst the group of candidate image portions. sorting a list of said image portions based on the index values so as to generate a sorted list; determining a group of candidate image portions each having a proximity to the target image portion being within the search threshold in the sorted list; and identifying a best matching image portion from amongst the group of candidate image portions.