Method and apparatus for vector coding of video transform coefficients

• US 5,295,203 A
• Filed: 03/26/1992
• Issued: 03/15/1994
• Est. Priority Date: 03/26/1992
• Status: Expired due to Term

• Current Assignee: General Instrument Corporation (CommScope Holding Company, Inc.)
• Original Assignee: General Instrument Corporation (CommScope Holding Company, Inc.)
• Inventors: Tom, Adam, Krause, Edward A., Liu, Vincent
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/858,102
• Time in Patent Office: 719 Days
• Field of Search: 382/56, 382/41, 382/27, 382/43, 382/21, 358/133, 358/433, 358/432, 364/826, 364/725
• US Class Current: 382/248
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

A vector coding scheme for video transform coefficients is provided. A vector is generated to identify a group of coefficients from a block of transform coefficients that qualify for transmission according to predetermined criteria. In an illustrated embodiment, only coefficients having nonzero amplitudes are transmitted. The vector is encoded to provide a vector code word for transmission. The coefficients from the group qualifying for transmission are encoded to provide coefficient code words for transmission. The vector code word correlates the coefficient code words to coefficient locations in the block. In a preferred embodiment, the block is divided into a plurality of regions containing subsets of coefficients. A separate vector is transmitted for each region, correlating the coefficient code words to coefficient locations in the corresponding region of the block.

Claims

1. A method for coding video transform coefficients for communication comprising the steps of:

providing a block of transform coefficients;

generating a vector to identify locations of a group of coefficients from said block that qualify for transmission according to predetermined criteria;

encoding said vector to provide a vector code word for transmission; and

encoding the coefficients from said group to provide coefficient code words for transmission;

wherein said vector code word correlates the coefficient code words to coefficient locations in said block.

2. A coding method in accordance with claim 1 comprising the further step of:

dividing said block into a plurality of regions containing subsets of coefficients, said vector identifying a group of coefficients that qualify for transmission in a first one of said regions; and

generating additional vectors for encoding to identify locations of groups of coefficients that qualify for transmission in other regions of said block.

3. A coding method in accordance with claim 2 comprising the further steps of:

analyzing the vectors produced for said regions in a predetermined order to determine if a set of said vectors meets an end of block criterion;

encoding the vector from said block that immediately precedes said set as an end of block vector if said criterion is met for said set; and

terminating said vector encoding step without encoding the vectors in said set.

4. A coding method in accordance with claim 3 wherein said end of block criterion is met when there are no coefficients qualified for transmission in said set.

5. A coding method in accordance with claim 4 wherein:

said predetermined order progresses from vectors for regions that are least likely to contain coefficients qualified for transmission to vectors for regions that are successively more likely to contain coefficients qualified for transmission.

6. A coding method in accordance with claim 2 wherein:

said regions each contain a substantially equal number of coefficients;

said first region comprises an area of said block that is likely to contain more coefficients qualified for transmission than any other region; and

the other regions of said block are successively less likely to contain coefficients qualified for transmission.

7. A coding method in accordance with claim 6 wherein:

the vectors representative of regions that contain coefficients qualified for transmission are transmitted with the coefficients for said region; and

no vectors are transmitted for regions that have no coefficients qualified for transmission unless followed by a vector for a region that does contain coefficients qualified for transmission.

8. A coding method in accordance with claim 1 wherein said vector generating step comprises the steps of:

comparing the locations of said group of coefficients qualifying for transmission to locations designated by a limited number of vectors contained in a vector library; and

choosing a vector from said library to identify said group based on predetermined matching criteria.

9. A coding method in accordance with claim 8 comprising the further step of dividing said block into a plurality of regions containing different subsets of the coefficients contained in the block;

wherein;

said regions each contain a substantially equal number of coefficients;

a first region comprises an area of said block that is likely to contain more coefficients qualified for transmission than any other region; and

the other regions of said block are successively less likely to contain coefficients qualified for transmission.

10. A coding method in accordance with claim 9 wherein:

said vector identifies the locations of a group of coefficients that qualify for transmission in said first region;

additional vectors are generated to identify the locations of groups of coefficients that qualify for transmission in the other regions of said block;

vectors representative of regions that contain coefficients qualified for transmission are transmitted with the coefficients for said region; and

no vectors are transmitted for regions that have no coefficients qualified for transmission unless followed by a vector for a region that does contain coefficients qualified for transmission.

11. Encoder apparatus for coding video transform coefficients for communication comprising:

means for converting a portion of video data to a block of transform coefficients;

means for generating a vector to identify locations of a group of coefficients from said block that qualify for transmission according to predetermined criteria;

means for encoding said vector to provide a vector code word for transmission; and

means for encoding the coefficients from said group to provide coefficient code words for transmission;

wherein said vector code word correlates the coefficient code words to coefficient locations in said block.

12. Encoder apparatus in accordance with claim 11 further comprising:

memory means for storing a plurality of code words that identify all of the different possible combinations of coefficients qualified for transmission in said block;

wherein said vector encoding means select the code word from said memory that identifies the combination of coefficients qualified for transmission which matches the locations of the group of coefficients identified by said vector.

13. Encoder apparatus in accordance with claim 11 further comprising:

memory means for storing a plurality of code words that identify a limited number of the different possible combinations of coefficients qualified for transmission in said block;

wherein said vector encoding means select the code word that identifies the combination of coefficients qualified for transmission represented in said memory which best matches the locations of the group of coefficients identified by said vector, in accordance with a best match criterion.

14. Encoder apparatus in accordance with claim 11 further comprising:

means for dividing said block into a plurality of regions containing subsets of said coefficients, said vector identifying locations of a group of coefficients that qualify for transmission in a first one of said regions; and

means for generating additional vectors for encoding to identify the locations of groups of coefficients that qualify for transmission in other regions of said block.

15. Encoder apparatus in accordance with claim 14 further comprising:

means for analyzing the vectors produced for said regions to determine if one of said vectors meets an end of block criterion; and

means for encoding a vector meeting said end of block criterion to identify it as an end of block vector.

16. Encoder apparatus in accordance with claim 15 wherein said end of block criterion is met when there are no subsequent vectors in said block that identify locations for coefficients which are qualified for transmission.

17. Encoder apparatus in accordance with claim 16 wherein said analyzing means search for vectors that meet the end of block criterion by testing said vectors in a predetermined order that progresses from vectors for regions that are least likely to contain coefficients qualified for transmission to vectors for regions that are successively more likely to contain coefficients qualified for transmission.

18. Encoder apparatus in accordance with claim 14 wherein:

said regions each contain a substantially equal number of coefficients;

said first region comprises an area of said block that is likely to contain more coefficients qualified for transmission than any other region; and

the other regions of said block are successively less likely to contain coefficients qualified for transmission.

19. Encoder apparatus in accordance with claim 14 further comprising:

memory means for storing a plurality of code words that identify all of the different possible combinations of coefficients qualified for transmission in said block;

wherein said vector encoding means select the code word from said memory that identifies the combination of coefficients qualified for transmission which matches the locations of the group of coefficients identified by a vector to be encoded.

20. Encoder apparatus in accordance with claim 14 further comprising:

memory means for storing a plurality of code words that identify a limited number of the different possible combinations of coefficients qualified for transmission in said block;

wherein said vector encoding means select the code word that identifies the combination of coefficients qualified for transmission represented in said memory which best matches the locations of the group of coefficients identified by a vector to be encoded, in accordance with a best match criterion.

21. Decoder apparatus for decoding video transform coefficients comprising:

means for receiving encoded coefficients representing video data from a block of a video image area;

means for receiving an encoded vector corresponding to a group of said encoded coefficients;

means for decoding said encoded vector to recover a vector that identifies locations for said coefficients in said block; and

means responsive to said vector for decoding the encoded coefficients from said group to recover said block with said coefficients in substantially proper locations thereof.

22. Decoder apparatus in accordance with claim 21 wherein said encoded vector is received as a code word, said apparatus further comprising:

memory means for storing a plurality of vectors that identify different possible combinations of transmitted coefficient locations in said block;

wherein said code word is used to address the memory means to output a vector that best identifies the actual locations of the transmitted coefficients in said block.

23. Decoder apparatus in accordance with claim 21 wherein:

said encoded vector is received as a code word; and

said means for decoding said encoded vector comprise a state machine responsive to said code word.

24. Decoder apparatus in accordance with claim 21 wherein:

said block comprises a plurality of regions containing different groups of said coefficients;

separate encoded vectors are received and decoded for the different regions; and

said coefficient decoding means are responsive to the separate vectors for assembling the different groups of coefficients into substantially proper locations in said block.

25. Decoder apparatus in accordance with claim 24 wherein said encoded vectors include overhead data, said apparatus further comprising:

means for detecting a region tag from said overhead data, said tag identifying the region of said block to which a current vector corresponds;

wherein said vector decoding means are responsive to said tag for decoding the current vector.

26. Decoder apparatus in accordance with claim 25 further comprising:

means for detecting an end of block signal from said overhead data; and

means, operatively associated with said coefficient decoding means and responsive to said end of block signal, for filling subsequent regions of said block with predetermined filler coefficients.

27. Decoder apparatus in accordance with claim 24 further comprising:

means for detecting if one of said received vectors is encoded as an end of block vector; and

means, operatively associated with said coefficient decoding means and responsive to said detecting means, for filling regions of said block following the region defined by said end of block vector with predetermined filler coefficients.