An image encoding apparatus generate encoded data having a fixed length L which is less than or equal to m×n bits and an integral multiple of 32 by m×n pixel block, while resolution information and color information are excellently maintained. For this purpose, a block generation unit inputs image data by m×n pixels. A 2-color extraction unit extracts representative colors C0 and C1 from the input block image data. An identification information detection unit generates m×n items of identification information each identifying each pixel in the block as a pixel approximate to one of the colors C0 and C1. An identification information deletion unit deletes the items of identification information in corresponding positions based on a deletion pattern stored in a deletion pattern memory. A packing unit packs the colors C0, C1 and the identification information after deletion, and outputs the data as encoded data.