1. An image encoding apparatus that encodes image data, comprising: pattern image cut-out means for cutting out a plurality of pattern images from the image data, and outputting the plurality of cut-out pattern images and position information associated with the cut-out pattern images; rearrangement means for rearranging the plurality of pattern images that are cut out by the pattern image cut-out means; dictionary generating means for listing the plurality of pattern images that are rearranged by the rearrangement means; pattern image synthesis means for synthesizing the plurality of pattern images that are listed by the dictionary generating means; and encoded data generating means for generating encoded data, using a synthesis image of the pattern images, which is synthesized by the pattern image synthesis means, and the position information of the plurality of pattern images, which is output from the pattern image cut-out means.