Adaptive tree-search vector quantization in MPEG2 decoder

• US 6,320,907 B1
• Filed: 11/19/1998
• Issued: 11/20/2001
• Est. Priority Date: 11/24/1997
• Status: Expired due to Term

• Current Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Original Assignee: STMicroelectronics SRL (STMicroelectronics NV)
• Inventors: Bruni, Roberta, Pau, Danilo
• Primary Examiner(s): Kelley, Chris
• Assistant Examiner(s): PHILIPPE, GIMS S
• Application Number:
  US09/195,800
• Time in Patent Office: 1,097 Days
• Field of Search: 375/240.02, 375/240.03, 375/240.18, 375/240.22, 375/240.04, 341/51, 341/79, 382/253, 382/239, 382/232, 382/236, 348/414.01, 348/417.1, 348/418.1, 348/415.1, 348/400-402, 348/405.1, 348/409.1, 348/453, 348/459
• US Class Current: 375/240.22
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/428 Recompression, e.g. by spatial or temporal decimation
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

The memory requirement of MPEG decoders and SQTV/IQTV systems may be reduced by recompressing the MPEG decoded data stream before storing pixels in an external RAM. An efficient compression method for recompressing video picture data based on the tree-search vector quantization (TSVQ) is made more effective by optimizing the way the quantizer is chosen for quantizing the differences among adjacent pel vectors. This method is based on premultiplying a read-only table using quantized complexity measures relative to the centroids of the tree-like scheme used in the TSVQ processing. A plurality of precalculated tables of quantization of the prediction error of a physical parameter of blocks of digital data are produced. For each one of the regions in which a block is divided, the calculated and quantized complexity measure provides an address that selects the most appropriate precalculated table for quantizing the prediction error. The adaptive tree-search vector quantization method is implemented in a corresponding hardware architecture.

Claims

1. A method for reducing a memory requirement for temporarily storing a stream of digital data blocks in a coding/decoding system of information transferable by blocks, such data being compressed and coded by blocks through a tree-search vector quantization (TSVQ) and stored in a memory, where a subsequent reading phase decompresses the data by reconstructing the coded and compressed digital data blocks, the method comprising the steps of:

a) fixing a certain scan path of each data block R (rows)×

C (columns) of the stream of digital data blocks to be separated into vectors of preestablished dimensions;

b) coding a first vector of a scan of a digital data block in an unmodified manner;

c) partitioning in one or more regions the scanning of a generated R×

C data block;

d) selecting and calculating a complexity measure for each region as a mean value of a sum of absolute values of differences among corresponding components of adjacent vectors of the scanning, and belonging to the region;

e) quantizing according to a binary tree-search in a table of quantized values of the complexity measure by coding a corresponding address and using the address for controlling a multiplexer selecting a plurality of tables of quantized vectors, sending the address to the multiplexer that conveys a properly compressed value to the memory;

f) generating a predictor vector of the current one to be quantized, as a replica of a last decoded vector according to scanning and calculating of a prediction error vector;

g) quantizing according to a binary tree-search in a read only table of quantized vectors the prediction error vector, the table being selected among the plurality of tables of quantized vectors by the address of the quantized measure, coding the address of the table and sending it to a multiplexer that subsequently conveys a compressed value to the memory;

h) adding components of a vector read from the selected table of quantized vectors to the vector replica of the vector previously decoded, generating a prediction vector for a next vector to be coded according to the scanning path and the selected region;

i) repeating steps d) through h) following the scanning path for all the regions that make up the R×

C data block, and for all the scanning vectors of each input data block;

j) premultiplying a read-only table using quantized complexity measures relative to centroids of a tree-like scheme used for the search, and producing as many precalculated tables for quantizing a prediction error of a physical parameter (luma, chroma) of the digital data block; and

k) quantizing the prediction error using one of the precalculated tables selected by an address generated by estimating and quantizing a complexity measure of each one of the regions in which the R×

C block is divided.

2. The method according to claim 1, wherein the block of input data is an R×

C block of pixels of a video picture and physical parameters are the luminance (luma) and the chrominance (chroma).

3. The method according to claim 1, wherein the memory comprises a random access memory (RAM).

4. An MPEG-2 video decoder, interfacing with a control bus and a memory data bus through which video data are written on and read off respective memory buffers external to a core of the MPEG-2 video decoder, the MPEG-2 video decoder comprising:

a memory having one or more buffers for video bits;

a first-in-first-out (FIFO) buffer for data acquisition and writing of compressed data in a respective buffer of said memory;

a picture starting code detecting circuit;

a control circuit for synchronizing said picture starting code detecting circuit;

a bi-directional buffer for on-screen-data-display;

a variable length decoder for a compressed input data stream;

an MPEG-2 decompression pipeline for data decoded by said variable length decoder, and comprising a run length decoding stage, an inverse quantizer circuit, an inverse discrete cosine transform processor, and a predictor value generating circuit;

a conversion circuit for a current B-Picture upstream of a display unit;

a coding and recompressing circuit functioning according to a tree-search vector quantization algorithm for recompressing decompressed I and P pictures, and coding the respective data to be stored in respective buffers of said memory;

a decoding and decompressing circuit for stored data read from respective buffers of said memory generating a stream of decoded and decompressed data relative to the I and P pictures;

means for motion compensation of B-pictures and for conversion;

said coding and recompressing circuit further comprising a buffer for the acquisition of blocks of input data, separating the block of input data in decomposition vectors of predefined dimensions (J×

K) and in an initial vector;

a differentiating stage receiving through a first input the decomposition vectors of the block of input data and through a second input prediction vectors, and outputting prediction error vectors;

a vector quantizing and coding circuit receiving through an input the prediction error vectors output by said differentiating stage and using at least two distinct tables of quantized vectors, respectively optimized for luma and chroma compression;

a circuit for automatically selecting the at least two distinct tables of quantized vectors, said circuit comprising a first multiplexer, a limiting circuit, a generator circuit of a predictor vector receiving through a first input a quantized vector whose components are limited by the limiting circuit, and through a second input a first decomposition vector of an R*C block scan present at an output of the input buffer and generating the prediction vector that is sent to a second input of said differentiating stage;

said vector quantizing and coding circuit further comprising two distinct sets of tables of quantized prediction errors, each obtained by multiplying a relative table of quantized prediction errors by each one of a plurality of predefined quantized measures of complexity;

a second multiplexer;

a stage for measuring a complexity or gain of each region and quantizing the measure through a binary tree-search scheme producing an address of a respective table containing a quantized vector to store through said second multiplexer in a respective buffer of external memory with an address of the quantized value of the local complexity measure together with the first scanning vector, and driving the selection of precalculated tables through said first multiplexer; and

an adder stage receiving through a first input the prediction vector produced by the generator circuit of a predictor vector, and receiving through a second input the vector output by the first multiplexer, which is fed by the plurality of vectors selectively read from the tables, and having an output coupled to the input of the limiting circuit;

the output of the limiting circuit feeding a pixel stream through the buffer, said MPEG2 decompression pipeline, and said converting block.

5. An MPEG-2 video decoder according to claim 4, wherein said recompression and coding circuits comprise multiplexer means for enabling and disabling said recompression and coding circuits for a dynamic management of a compression rate of the digital data stream to be stored in said memory.

6. An MPEG-2 video decoder according to claim 4, wherein said decoding and decompression circuits comprises multiplexer means for enabling and disabling said decoding and decompression circuits for a dynamic management of a compression rate of the digital data stream to be stored in said memory.

7. An MPEG-2 video decoder according to claim 4, wherein said memory is external.

8. An MPEG-2 video decoder according to claim 4, wherein said memory comprises a dynamic random access memory (DRAM) device.