An array of texture data elements (texels) is subdivided into a plurality of 8×4 texture element blocks, each of which 8×4 texture element blocks encodes two 4×4 texture element sub-blocks 3, 4. Each encoded texture data block includes data indicating a method to be used to generate a set of colour values to be used for the texture elements that the encoded data block represents, and data indicating a method to be used for generating the colours of the individual texture elements using that generated set of colours. As well as the individual texture data blocks, a header data block encoding a base set of colours is generated. This base colour set defines a set of colours that is used to generate the colours to be used when reproducing each individual encoded texture data block.