In encoding input image data including first and second images, the first image is divided into blocks. A second block corresponding to a first block that is one of the blocks is detected from the second image. Pixels forming the first and second blocks are sorted in order according to pixel values. Block difference data indicating the amount of change in the pixel values of the sorted pixels between the first and second blocks is determined and encoded. In decoding, block information identifying the second block, sort-order information indicating the sorted pixels forming the first block, and the encoded block difference data are obtained. The encoded block difference data is decoded. The decoded block difference data and the second block identified by the block information are used to generate pixel values of the first block. The generated pixel values are reverse-sorted according to the sort-order information.