In this invention, scan conversion processing of changing the scan order for each block is used. Parallel scan conversion processing is executed if possible, thereby making the number of scan conversion target blocks per unit time larger than before. To do this, a scan status holding unit holds statistical information based on the appearance frequency values of coefficients in a block. A scan order holding unit holds coefficient position information in which the coefficient positions in a block are arranged based on the scan order. A parallel number determination unit determines the number of blocks processable in parallel based on the statistical information held in the scan status holding unit and supplies the result to a scan conversion unit as a control signal. If the control signal from the parallel number determination unit indicates parallel processing, the scan conversion unit executes scan conversion of two input blocks in parallel.