This invention generates, from multi-value image data, encoded data having a fixed length of L bits for each block including m×n pixels. An extraction unit extracts representative two colors C0 and C1 from an input block. A detection unit generates binary identification information, which indicates one of the colors C0 and C1 to which each pixel in the block is approximate. A generating unit determines, according to a deletion pattern, which of identification data elements indicating the color C0 and those indicating the color C1 are deleted more, and outputs the determination result as interpolated-identification data. A replacing unit replaces identification data which is the same as non-interpolated-identification data near the pixel position by the interpolated-identification data. A deletion unit deletes identification data according to the deletion pattern. A packing unit couples and outputs the colors C0 and C1, interpolated-identification data, and identification data after deletion.