To efficiently compress image data, the image data is divided into rectangular blocks of non-equal length in a hierarchal structure in accordance with a brightness change, and is encoded into tree-structure data for each of the divided blocks so that the mean distortion of the image data inside each block does not exceed an allowable value.