When image data to which attribute bits indicating attribute information of each pixel of an image has been attached is compressed, replacement bits for replacing the attribute bits are determined in accordance with the attribute bits. If total size of the attribute bits and image data exceeds a predetermined value, the attribute bits are replaced with the replacement bits and the replacement bits and image data are compressed. A bit string having a compression rate higher than that of the attribute bits before the replacement thereof is used as the replacement bits.