An encoding method generates an encoded image according to a predetermined encoding format. The method includes the step of, for each block of pixels, determining an average color of colors of the block of pixels in the predetermined color space; selecting at least one luminance line in dependence on an offset in the color space of the average color from the at least one luminance line; identifying a set of candidate base colors lying on the at least one luminance line; and determining, using the set of candidate base colors and the luminance offset values, the set of encoded pixel colors. The base color and the set of luminance offsets are selected in dependence on an encoding error indicative of a sum distance in the color space between the set of encoded pixel colors and the colors of the block of pixels.