Scan conversion apparatus, image encoding apparatus, and control method therefor

• US 8,509,547 B2
• Filed: 04/13/2010
• Issued: 08/13/2013
• Est. Priority Date: 05/14/2009
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Fujino, Reiko
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US13/203,719
• Publication Number:
  US 20120177298A1
• Time in Patent Office: 1,218 Days
• Field of Search: 382/232, 382/240, 382/248, 382/250, 375/240.19, 375/240.2, 375/240.24
• US Class Current: 382/232
• 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/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/64 characterised by ordering of coefficients or of bits for transmission

Abstract

This invention enables parallelly sorting data in substantially M blocks though statistical information is updated. In the first scan conversion, (15) input transform coefficients of a two-dimensional array are read out and output in accordance with scan order information ScanOrder[ ], thereby outputting sorted one-dimensional array data. At this time, a significant coefficient detection unit determines whether the sorted data is a significant coefficient. Upon receiving a notification that the sorted data is a significant coefficient, a statistical information update unit updates statistical information ScanTotals[x] at a corresponding position. When the relationship between statistical information ScanTotals[x] and immediately preceding statistical information ScanTotals[x−1] is an ascending order, ScanOrder[x−1] and ScanOrder[x], and ScanTotals[x−1] and ScanTotals[x] are swapped respectively. A second scan conversion unit starts scan conversion of transform coefficients with a delay of at least two transform coefficients from a first scan conversion unit.

Claims

1. A scan conversion apparatus which scans a block formed from N data of a two-dimensional array and sorts the data into one-dimensional array data, the apparatus comprising:

a holding unit which holds scan order information which is determined based on an appearance frequency of significant data at each position in a block scanned in the past and indicates a scan order in the block;

a first scan conversion unit which scans N data which form a first block, in an order indicated by the scan order information, and outputs the N data as one-dimensional array data;

an update unit which, when data at a position A in a block is significant data during scanning by said first scan conversion unit, updates an appearance frequency corresponding to the position A;

a swapping unit which, when an appearance frequency (of significant data) at a position B (in the block) corresponding to a scan turn immediately before the position A is smaller than the appearance frequency (of significant data) at the position A after update by said update unit, swaps the scan orders of the position A and position B that are indicated by the scan order information; and

a second scan conversion unit which reads out N data which form a second block following the first block, in an order indicated by the scan order information, and outputs the N data as one-dimensional array data,

wherein said second scan conversion unit starts scanning the second block before completion of scanning the first block by said first scan conversion unit, and

when said first scan conversion unit scans I-th data of the first block, said second scan conversion unit scans (I-K)th (K is at least

     2) data of the second block at earliest in order to reflect a swapping result by said swapping unit along with scanning of the first block by said first scan conversion unit.

4. An image encoding apparatus which encodes image data, the apparatus comprising:

an image division unit which divides an image into blocks each formed from n rows and m columns;

an orthogonal transform unit which performs an orthogonal transform for each block output from said image division unit, and outputs transform coefficients;

a scan conversion apparatus defined in claim 1 which parallelly sorts transform coefficients of M blocks output from said orthogonal transform unit; and

an entropy encoding unit which entropyencodes the transform coefficients of the M blocks output from said scan conversion apparatus, and outputs an encoded stream.

2. A method of controlling a scan conversion apparatus which scans a block formed from N data of a two-dimensional array and sorts the data into one-dimensional array data, the method comprising:

a holding step of holding scan order information which is determined based on an appearance frequency of significant data at each position in a block scanned in the past and indicates a scan order in the block;

a first scan conversion step of scanning N data which form a first block, in an order indicated by the scan order information, and outputting the N data as one-dimensional array data;

an update step of, when data at a position A in a block is significant data during scanning in the first scan conversion step, updating an appearance frequency corresponding to the position A;

a swapping step of, when an appearance frequency (of significant data) at a position B (in the block) corresponding to a scan turn immediately before the position A is smaller than the appearance frequency (of significant data) at the position A after update in the update step, swapping the scan orders of the position A and position B that are indicated by the scan order information; and

a second scan conversion step of reading out N data which form a second block following the first block, in an order indicated by the scan order information, and outputting the N data as one-dimensional array data,

wherein in the second scan conversion step, scanning of the second block starts before completion of scanning the first block in the first scan conversion step, and

when I-th data of the first block is scanned in the first scan conversion step, (I-K)th (K is at least

     2) data of the second block is scanned at earliest (in the second scan conversion step) in order to reflect a swapping result in the swapping step along with scanning of the first block in the first scan conversion step.

8. A method of controlling an image encoding apparatus which encodes image data, the method comprising:

an image division step of dividing an image into blocks each formed from n rows and m columns;

an orthogonal transform step of performing orthogonal transform for each block output in the image division step, and outputting transform coefficients;

a processing step of performing steps defined in the method according to claim 2 which parallelly sorts the transform coefficients of M blocks output in the orthogonal transform step; and

an entropy encoding step of entropy-encoding the transform coefficients of the M blocks output from the scan conversion apparatus, and outputting an encoded stream.

3. A scan conversion apparatus which scans a block formed from N data of a two-dimensional array and sorts the data into one-dimensional array data so as to collect significant data first and then collect insignificant data after the significant data, the apparatus comprising:

a setting unit which pairs position information indicating a position of each data in the block and statistical information indicating an appearance frequency of significant data at the position of each data, and sets sorted information by sorting pieces of statistical information in a descending order;

M (2≦

M≦

N/2) scan conversion units, each of which reads out N data which form a supplied block, in an order based on the position information in the sorted information, outputs the N data as one-dimensional array data, and outputs information indicating whether readout data is significant data, said M scan conversion units being capable of parallelly running;

a statistical information update unit which, when one of said M scan conversion units outputs information indicating that ith data is significant data, updates statistical information corresponding to a position of the ith data;

a swapping unit which, when a relationship between statistical information to be updated and immediately preceding statistical information becomes an ascending order relationship as a result of update by said statistical information update unit, swaps two pieces of sorted information containing the pieces of statistical information having the ascending order relationship; and

a control unit which assigns priority levels to said M scan conversion units as first to Mth scan conversion units, and causing causes each scan conversion unit to start scanning data at a timing delayed by at least two data from scan conversion unit higher in priority level by one than said each scan conversion unit.

5. A scan conversion apparatus which scans a block formed from N data of a two-dimensional array and sorts the data into one-dimensional array data so as to collect significant data first and then collect insignificant data after the significant data, the apparatus comprising:

a setting unit which pairs position information indicating a position of each data in the block and statistical information indicating an appearance frequency of significant data at the position of each data, and sets sorted information by sorting pieces of statistical information in a descending order;

M (2≦

M) scan conversion units, each of which reads out N data which form a supplied block, in an order based on the position information in the sorted information, outputs the N data as one-dimensional array data, and outputs information indicating whether readout data is significant data, said M scan conversion units being capable of parallelly running;

a statistical information update unit which, when said M scan conversion units parallelly sorts ith data, updates statistical information corresponding to a position of the ith data in accordance with the number of scan conversion units that have output information indicating that the ith data is significant data; and

a swapping unit which, when a relationship between statistical information to be updated and immediately preceding statistical information becomes an ascending order relationship as a result of update by said statistical information update unit, swaps two pieces of sorted information containing the pieces of statistical information having the ascending order relationship,

wherein priority levels are assigned to said M scan conversion units as first to Mth scan conversion units, and

each scan conversion unit includes

a holding unit which holds data sorted at a timing immediately before sorting ith data,

a determination unit which determines whether a relation “

ScanTotals[i−

1]≧

ScanTotals[i]+L”

is satisfied, where L is the number of scan conversion units which have output information indicating that the ith data is significant data and are higher in priority level than said each scan conversion unit, and ScanTotals[i] is ith statistical information, and

a selection unit which, when a determination result of said determination unit represents that the relation “

ScanTotals[i−

1]≧

ScanTotals[i]+L”

is satisfied, outputs data held by said holding unit and then holds currently sorted data in said holding unit, and when the determination result of said determination unit represents “

ScanTotals[i−

1]<

ScanTotals[i]+L”

, outputs currently sorted data.

6. An image encoding apparatus which encodes image data, the apparatus comprising:

an image division unit which divides an image into blocks each formed from n rows and m columns;

an orthogonal transform unit which performs orthogonal transform for each block output from said image division unit, and outputs transform coefficients;

a scan conversion apparatus defined in claim 5 which parallelly sorts transform coefficients of M blocks output from said orthogonal transform unit; and

an entropy encoding unit which entropy-encodes the transform coefficients of the M blocks output from said scan conversion apparatus, and outputs an encoded stream.

10. A method of controlling an image encoding apparatus which encodes image data, the method comprising:

an image division step of dividing an image into blocks each formed from n rows and m columns;

an orthogonal transform step of performing orthogonal transform for each block output in the image division step, and outputting transform coefficients;

a processing step of defined in the method according to claim 6 which parallelly sorts the transform coefficients of M blocks output in the orthogonal transform step; and

an entropy encoding step of entropy-encoding the transform coefficients of the M blocks output from the scan conversion apparatus, and outputting an encoded stream.

7. A method of controlling a scan conversion apparatus which parallelly sorts M blocks each formed from N data of a two-dimensional array into one-dimensional array data so as to collect significant data first and then collect insignificant data after the significant data, the method comprising:

a setting step of pairing position information indicating a position of each data in the block and statistical information indicating an appearance frequency of significant data at the position of each data, and setting sorted information by sorting pieces of statistical information in a descending order;

M (2≦

M≦

N/2) scan conversion steps each of reading out N data which form the block, in an order based on the position information in the sorted information, outputting the N data as one-dimensional array data, and outputting information indicating whether readout data is significant data, the M scan conversion steps being capable of parallelly running;

a statistical information update step of, when information indicating that ith data is significant data is output in one of the M scan conversion steps, updating statistical information corresponding to a position of the ith data;

a swapping step of, when a relationship between statistical information to be updated and immediately preceding statistical information becomes an ascending order relationship as a result of update in the statistical information update step, swapping two pieces of sorted information containing the pieces of statistical information having the ascending order relationship; and

a control step of assigning priority levels to the M scan conversion steps as first to Mth scan conversion steps, and starting scanning data in each scan conversion step at a timing delayed by at least two data from a scan conversion step higher in priority level by one than each scan conversion step.

9. A method of controlling a scan conversion apparatus which parallelly sorts M blocks each formed from N data of a two-dimensional array into one-dimensional array data so as to collect significant data first and then collect insignificant data after the significant data, the method comprising:

a setting step of pairing position information indicating a position of each data in the block and statistical information indicating an appearance frequency of significant data at the position of each data, and setting sorted information by sorting pieces of statistical information in a descending order;

M (2≦

M) scan conversion steps each of reading out N data which form the block, in an order based on the position information in the sorted information, outputting the N data as one-dimensional array data, and outputting information indicating whether readout data is significant data, the M scan conversion steps being capable of parallelly running;

a statistical information update step of, when ith data are parallelly sorted in the M scan conversion steps, updating statistical information corresponding to a position of the ith data in accordance with the number of scan conversion steps in which information indicating that the ith data is significant data have been output; and

a swapping step of, when a relationship between statistical information to be updated and immediately preceding statistical information is an ascending order relationship as a result of update in the statistical information update step, swapping two pieces of sorted information containing the pieces of statistical information having the ascending order relationship,

wherein priority levels are assigned to the M scan conversion steps as first to Mth scan conversion steps, and

each scan conversion step includes

a holding step of holding data sorted at a timing immediately before sorting ith data,

a determination step of determining whether a relation “

ScanTotals[i−

1]≧

ScanTotals[i]+L”

is satisfied, where L is the number of scan conversion steps in which information indicating that the ith data is significant data have been output and which are higher in priority level than each scan conversion step, and ScanTotals[i] is ith statistical information, and

a selection step of, when a determination result in the determination step represents that the relation “

ScanTotals[i−

1]≧

ScanTotals[i]+L”

is satisfied, outputting data held in the holding step and then holding currently sorted data in the holding step, and when the determination result in the determination step represents “

ScanTotals[i−

1]<

ScanTotals[i]+L”

, outputting currently sorted data.