An example embodiment may involve obtaining an m×n pixel cell from an input image. Each of the m×n pixels in the m×n pixel cell may be associated with at least one color value. An m×n attribute cell may be determined, elements of which may be associated in a one-to-one fashion with respective pixels in the m×n pixel cell. The m×n pixel cell may be compressed in a lossy fashion, and the m×n attribute cell may be compressed in a lossless fashion. Compression of the m×n pixel cell may be based on at least part of the m×n attribute cell. An interleaved representation of the compressed m×n pixel cell and the compressed m×n attribute cell may be written to an output medium.