Scan conversion apparatus, image encoding apparatus, and methods of controlling the same

An apparatus for sorting data in a block having n rows×m columns based on a predetermined scan order, comprising:

• scan status holding means for updating and holding a current scan status in accordance with a status of the data in the block;
• scan order holding means for updating and holding a scan order in accordance with the scan status;
• significant data position information generation means for generating position information of significant data that exists in the block;
• parallel number determination means for instructing to perform scan conversion processing of N blocks (N is an integer:
• N≧2) as M-parallel processing (M is an integer:
• 1≦M≦N) in accordance with the scan status held by said scan status holding means and the position information output from said significant data position information generation means;
• and
• scan conversion means for sorting, in accordance with the instruction from said parallel number determination means, the data in the block based on the scan order held by said scan order holding means.

A method of sorting data in a block having n rows×m columns based on a predetermined scan order, comprising:

• a scan status holding step of updating and holding a current scan status in accordance with a status of the data in the block;
• a scan order holding step of updating and holding a scan order in accordance with the scan status;
• a parallel number determination step of instructing to perform scan conversion processing of N blocks (N is an integer:
• N≧2) as M-parallel processing (M is an integer:
• 1≦M≦N) in accordance with the scan status held in the scan status holding step;
• and
• a scan conversion step of sorting, in accordance with the instruction in the parallel number determination step, the data in the block based on the scan order held in the scan order holding step.

A method of sorting data in a block having n rows×m columns based on a predetermined scan order, comprising:

• a scan status holding step of updating and holding a current scan status in accordance with a status of the data in the block;
• a scan order holding step of updating and holding a scan order in accordance with the scan status;
• a significant data position information generation step of generating position information of significant data that exists in the block;
• a parallel number determination step of instructing to perform scan conversion processing of N blocks (N is an integer:
• N≧2) as M-parallel processing (M is an integer:
• 1≦M≦N) in accordance with the scan status held in the scan status holding step and the position information output in the significant data position information generation step;
• and
• a scan conversion step of sorting, in accordance with the instruction in the parallel number determination step, the data in the block based on the scan order held in the scan order holding step.

An image encoding apparatus comprising:

• image dividing means for dividing an image into unit blocks each having n rows×m columns;
• orthogonal transform means for performing orthogonal transform of each unit block output from said image dividing means and outputting transform coefficients;
• quantization means for quantizing the transform coefficients output from said orthogonal transform means and outputting quantized transform coefficients;
• scan conversion means for sorting the quantized transform coefficients output from said quantization means in each unit block and outputting the quantized transform coefficients;
• and
• entropy encoding means for entropy-encoding the quantized transform coefficients output from said scan conversion means and outputting a code stream,
• said scan conversion means comprising:
• scan status holding means for updating and holding a current scan status in accordance with a status of data in the block;
• scan order holding means for updating and holding a scan order in accordance with the scan status;
• parallel number determination means for instructing to perform scan conversion processing of N blocks (N is an integer:
• N≧2) as M-parallel processing (M is an integer:
• 1≦M≦N) in accordance with the scan status held by said scan status holding means;
• and
• scan conversion means for sorting, in accordance with the instruction from said parallel number determination means, the data in the block based on the scan order held by said scan order holding means.

An image encoding apparatus comprising:

• image dividing means for dividing an image into unit blocks each having n rows×m columns;
• orthogonal transform means for performing orthogonal transform of each unit block output from said image dividing means and outputting transform coefficients;
• quantization means for quantizing the transform coefficients output from said orthogonal transform means and outputting quantized transform coefficients;
• scan conversion means for sorting the quantized transform coefficients output from said quantization means in each unit block and outputting the quantized transform coefficients;
• and
• entropy encoding means for entropy-encoding the quantized transform coefficients output from said scan conversion means and outputting a code stream,
• said scan conversion means comprising:
• scan status holding means for updating and holding a current scan status in accordance with a status of data in the block;
• scan order holding means for updating and holding a scan order in accordance with the scan status;
• significant data position information generation means for generating position information of significant data that exists in the block;
• parallel number determination means for instructing to perform scan conversion processing of N blocks (N is an integer:
• N≧2) as M-parallel processing (M is an integer:
• 1≦M≦N) in accordance with the scan status held by said scan status holding means and the position information output from said significant data position information generation means;
• and
• scan conversion means for sorting, in accordance with the instruction from said parallel number determination means, the data in the block based on the scan order held by said scan order holding means.

A method of controlling an image encoding apparatus, comprising:

• an image dividing step of dividing an image into unit blocks each having n rows×m columns;
• an orthogonal transform step of performing orthogonal transform of each unit block output in the image dividing step and outputting transform coefficients;
• a quantization step of quantizing the transform coefficients output in the orthogonal transform step and outputting quantized transform coefficients;
• a scan conversion step of sorting the quantized transform coefficients output in the quantization step in each unit block and outputting the quantized transform coefficients;
• and
• an entropy encoding step of entropy-encoding the quantized transform coefficients output in the scan conversion step and outputting a code stream,
• the scan conversion step comprising:
• a scan status holding step of updating and holding a current scan status in accordance with a status of data in the block;
• a scan order holding step of updating and holding a scan order in accordance with the scan status;
• a parallel number determination step of instructing to perform scan conversion processing of N blocks (N is an integer:
• N≧2) as M-parallel processing (M is an integer:
• 1≦M≦N) in accordance with the scan status held in the scan status holding step;
• and
• a scan conversion step of sorting, in accordance with the instruction in the parallel number determination step, the data in the block based on the scan order held in the scan order holding step.

A method of controlling an image encoding apparatus, comprising:

• an image dividing step of dividing an image into unit blocks each having n rows×m columns;
• an orthogonal transform step of performing orthogonal transform of each unit block output in the image dividing step and outputting transform coefficients;
• a quantization step of quantizing the transform coefficients output in the orthogonal transform step and outputting quantized transform coefficients;
• a scan conversion step of sorting the quantized transform coefficients output in the quantization step in each unit block and outputting the quantized transform coefficients;
• and
• an entropy encoding step of entropy-encoding the quantized transform coefficients output in the scan conversion step and outputting a code stream,
• the scan conversion step comprising:
• a scan status holding step of updating and holding a current scan status in accordance with a status of data in the block;
• a scan order holding step of updating and holding a scan order in accordance with the scan status;
• a significant data position information generation step of generating position information of significant data that exists in the block;
• a parallel number determination step of instructing to perform scan conversion processing of N blocks (N is an integer:
• N≧2) as M-parallel processing (M is an integer:
• 1≦M≦N) in accordance with the scan status held in the scan status holding step and the position information output in the significant data position information generation step and
• a scan conversion step of sorting, in accordance with the instruction in the parallel number determination step, the data in the block based on the scan order held in the scan order holding step.

A scan conversion apparatus which repeatedly executes, for run-length encoding, scanning N data in two-dimensionally arrayed blocks each having m×n data to convert the N data into one-dimensionally arrayed data and outputting the data, comprising:

• setting means for setting initial sorting information in which positions of scan target data in the m×n data and statistical appearance frequency values of nonzero at the positions are paired and arranged in descending order of the appearance frequency values of the scan target data;
• a plurality of scan conversion means executable in parallel,
• each scan conversion means sequentially reading out and outputting data in a block of interest in an order of data positions based on the sorting information, and if the readout data is nonzero, increasing the appearance frequency value at the position of the data;
• update means for, if a portion where the appearance frequency values are arranged in ascending order exists in the sorting information, updating the sorting information to attain the descending order by replacing two pairs determined to be arranged in the ascending order;
• determination means for determining, by analyzing the sorting information, the minimum number P (p≧1) of blocks until execution of replacement processing by said update means;
• and
• scan control means for causing P of said plurality of scan conversion means to convert P consecutive block data into a one-dimensional array in parallel.

A method of controlling a scan conversion apparatus which includes a plurality of scan conversion means executable in parallel, each scan conversion means sequentially reading out and outputting data in a block of interest in an order of data positions based on sorting information, and if the readout data is nonzero, increasing an appearance frequency value at a position of the data, and repeatedly executes, for run-length encoding, causing at least one scan conversion means to scan two-dimensionally arrayed blocks each having m×n data to convert the data into one-dimensionally arrayed data and outputting the data, comprising:

• a setting step of setting initial sorting information in which positions of scan target data in the m×n data and statistical appearance frequency values of nonzero at the positions are paired and arranged in descending order of the appearance frequency values of the scan target data;
• and
• an update step of updating, if a portion where the appearance frequency values are arranged in ascending order exists in the sorting information, the sorting information to attain the descending order by replacing two pairs determined to be arranged in the ascending order;
• a determination step of determining, by analyzing the sorting information, the minimum number P (p≧1) of blocks until execution of replacement processing in the update step;
• and
• a scan control step of causing P of the plurality of scan conversion means to convert P consecutive block data into a one-dimensional array in parallel.