An image processing apparatus performs color conversion processing on an input image. The image processing apparatus includes a block pallet conversion unit, a first color converting unit and a restoration unit. The block pallet conversion unit converts the input image in units of blocks into (i) pallet color information including pallet colors number of which is less than pixels included in one of the blocks and (ii) selection information used to select one of the pallet colors for each pixel. The first color converting unit performs color conversion on the pallet color information obtained by the block pallet conversion unit. The restoration unit selects for each pixel, based on the selection information, one of the pallet colors of the pallet color information, which is color-converted by the first color converting unit, to restores an image.