An encoded bit stream is processed by a lossless decoding unit (52), an inverse quantization unit (53), and an inverse orthogonal transform unit (54) in this order, to obtain orthogonally transformed coefficient data and encoding parameter information. The inverse orthogonal transform unit (54) performs an inverse orthogonal transform on the coefficient data by using bases that are set beforehand in accordance with the locations of transform blocks in a macroblock indicated by the encoding parameter information. In this manner, prediction error data is obtained. An intra prediction unit (62) generates predicted image data. An addition unit (55) adds the predicted image data to the prediction error data, to decode image data. By using bases that are set in accordance with the locations of transform blocks, an optimum inverse orthogonal transform can be performed, and encoding efficiency can be increased.