SCAN CONVERSION APPARATUS, IMAGE ENCODING APPARATUS, AND METHODS OF CONTROLLING THE SAME

• US 20110243467A1
• Filed: 02/01/2010
• Published: 10/06/2011
• Est. Priority Date: 02/17/2009
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Igarashi, Susumu
• Granted Patent: US 8,478,079 B2
• Time in Patent Office: Days
• US Class Current: 382/234
• CPC Class Codes: H04N 1/41 Bandwidth or redundancy reduction by scanning H04N1/17 ; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements
• CPC Class Codes: H04N 19/50 using predictive coding H04N19/61 takes precedence

Abstract

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.

Claims

1. 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;

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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.