Method and apparatus for compressing a digital signal using vector quantization

• US 5,592,227 A
• Filed: 09/15/1994
• Issued: 01/07/1997
• Est. Priority Date: 09/15/1994
• Status: Expired due to Fees

• Current Assignee: Vcom, Inc.
• Original Assignee: Vcom, Inc.
• Inventors: Feng, Yushu
• Primary Examiner(s): Au, Amelia
• Application Number:
  US08/306,713
• Time in Patent Office: 845 Days
• Field of Search: 348/422, 348/414, 348/417, 348/418, 348/413, 395/2.31, 395/2.3, 395/2.32, 382/253, 382/236
• US Class Current: 375/240.14
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 19/98 Adaptive-dynamic-range coding [ADRC]

Abstract

An improved VQ system for compressing a digital signal produces a compressed signal by dividing the signal to be compressed into a series of signal segments. Each signal segment comprises a plurality of signal values. The improved VQ system uses first and second tables of vector values having different degrees of signal correlation, referred to as a class-1 table and a class-2 table respectively. For a selected signal segment, the VQ system determines a vector Xbar1 representing a difference between the signal values in the selected segment and an average of a selected group of signal values in a preceding segment. For the same signal segment, the method and apparatus determines another vector Xbar2 representing a difference between the signal values in the selected signal segment and an average of a selected group of signal values in the selected signal segment. The vectors Xbar1 and Xbar2 measure different levels of correlation between the signal values of the selected signal segment. The improved VQ system finds an entry in the class-1 table that is a best match for the vector Xbar1, referred to as a class-1 best match entry. The improved VQ system also finds an entry in the class-2 table that is a best match for the vector Xbar2, referred to as a class-2 best match entry. After determining the best match entries, the improved VQ system inserts into a compressed signal stream an identifying code or compressed signal representing a selected one of the class-1 best match entry or the class-2 best match entry.

Claims

1. A method for compressing a digital signal to produce a compressed signal stream, comprising the steps of:

providing a first table of vectors having a first degree of intraframe signal correlation and a second table of vectors having a second degree of intraframe signal correlation, referred to as a class-1 table and a class-2 table respectively;

dividing said digital signal into a series of segments, each segment comprising a plurality of digital signal values;

determining a first vector Xbar1 for a selected segment having said first degree of intraframe signal correlation for the signal values in said selected segment;

determining a second vector Xbar2 for said selected segment having said second degree of intraframe signal correlation for the signal values in said selected segment;

finding an entry in said class-1 table that is a best match for said vector Xbar1, referred to as a class-1 best match entry;

finding an entry in said class-2 table that is a best match for said vector Xbar2, referred to as a class-2 best match entry;

inserting into said compressed signal stream an identifying code, said identifying code representing a selected one of said class-1 best match entry or said class-2 best match entry.

2. The method of claim 1 wherein said step of determining Xbar1 includes taking the difference between the signal values in said selected segment and an average of a selected group of signal values in a preceding segment.

3. The method of claim 1 wherein said step of determining Xbar2 includes taking the difference between the signal values in said selected segment and an average of a selected group of signal values in said selected segment.

4. The method of claim 1, wherein (1) said digital signal is a graphic-image signal, and (2) each digital signal value represents one or more characteristics of a pixel.

5. The method of claim 1, wherein said digital signal is an audio signal.

6. The method of claim 1, wherein said first and second tables of vectors are generated using an LBG method.

7. The method of claim 2, wherein:

(1) each of said selected segment and said preceding segment is a 4×

4 block, and (2) said average of a selected group of signal values in said preceding segment is an average of a column in said preceding segment that is adjacent to said selected segment.

8. The method of claim 3, wherein:

(1) each of said selected segment and said preceding segment is a 4×

4 block, and (2) said average of a selected group of signal values in said selected segment is an average of all signal values in said selected segment.

9. The method of claim 1, wherein said selected one of said best match entries is chosen by:

(1) determining respective error values for each of said class-1 best match entry and said class-2 best match entry, and (2) selecting said class-2 best match entry if (i) the error value for said class-2 best match entry is less than the error value for said class-1 best match entry and (ii) said respective error values differ by more than a specified difference, else selecting said class-1 best match entry.

10. The method of claim 9, wherein said respective error values are determined by computing a least-squares distance between, respectively, (1) said class-1 best match entry and said vector Xbar1, and (2) said class-2 best match entry and said vector Xbar2.

11. The method of claim 1, wherein said identifying code represents an address of said selected best match entry.

12. The method of claim 1, wherein said class-1 table and said class-2 table form respective portions of a single codebook.

13. The method of claim 1, further comprising the step of transmitting said identifying code to a decoder.

14. The method of claim 13, further comprising the step of decompressing said identifying code.

15. A method of compressing a digital graphic-image signal to produce a compressed signal stream, comprising the steps of:

providing a codebook comprising first and second tables of vector entries having different degrees of signal correlation, referred to as a class-1 table and a class-2 table respectively;

dividing said digital signal into a series of 4×

4 blocks, each block comprising a plurality of digital signal values, each said digital signal values representing one or more characteristics of a pixel;

determining a vector Xbar1 for a selected block representing a difference between the signal values in said selected block and an average of a selected group of signal values in a preceding block;

determining a vector Xbar2 for said selected block representing a difference between the signal values in said selected block and an average of all of said signal values in said selected block;

finding an entry in said class-1 table that is a best match for said vector Xbar1, referred to as a class-1 best match entry;

finding an entry in said class-2 table that is a best match for said vector Xbar2, referred to as a class-2 best match entry;

selecting one of said best match entries by;

(1) determining respective error values for each of said class-1 best match entry and said class-2 best match entry, and (2) selecting said class-2 best match entry if (i) the error value of said class-2 best match entry is less than the error value for said class-1 best match entry and (ii) said respective error values differ by more than a specified difference, else selecting said class-1 best match entry;

said respective error values being determined by computing a least-squares distance between, respectively, (1) said class-1 best match entry and said vector Xbar1, and (2) said class-2 best match entry and said vector Xbar2; and

if both of said respective error values exceed a specified quality index, referred to as K, then inserting into said compressed signal stream a lossless compressed signal segment that represents the signal values of said selected block, else inserting into said compressed signal stream an identifying code of said selected best match entry;

transmitting said compressed signal stream to a decoder; and

at said decoder, decompressing said compressed signal stream into a decompressed graphic-image signal.

16. A method of compressing a signal to produce a compressed signal stream, comprising the steps of:

providing first and second tables of vector entries having different degrees of signal correlation, referred to as a class-1 table and a class-2 table respectively;

dividing said digital signal into a series of segments, each segment comprising a plurality of digital signal values, each said segment having a quality index, referred to as K;

designating one or more of said segments as having a K of zero;

determining a vector Xbar1 for a selected segment representing a first degree of signal correlation for the signal values in said selected segment;

determining a vector Xbar2 for said selected segment representing a second degree of signal correlation for the signal values in said selected segment;

finding an entry in said class-1 table that is a best match for said vector Xbar1, referred to as a class-1 best match entry;

finding an entry in said class-2 table that is a best match for said vector Xbar2, referred to as a class-2 best match entry;

selecting one of said best match entries by;

(1) determining respective error values for each of said class-1 best match entry and said class-2 best match entry, and (2) selecting said class-2 best match entry if (i) the error value for said class-2 best match entry is less than the error value for said class-1 best match entry and (ii) said respective error values differ by more than a specified difference, else selecting said class-1 best match entry;

if both of said respective error values exceed the K for said selected segment, then inserting into said compressed signal stream a lossless compressed signal segment that represents all of the signal values of said selected segment, else inserting into said compressed signal stream an address of said selected one of said best match entries.

17. An improved VQ system for compressing a digital signal to produce a compressed signal stream, comprising the steps of:

means for providing a first table of vectors having a first degree of intraframe signal correlation and a second table of vectors having a second degree of intraframe signal correlation, referred to as a class-1 table and a class-2 table respectively;

means for dividing said digital signal into a series of segments, each segment comprising a plurality of digital signal values;

means for determining a first vector Xbar1 for a selected segment having said first degree of intraframe signal correlation for the signal values in said selected segment;

means for determining a second vector Xbar2 for said selected segment having said second degree of intraframe signal correlation for the signal values in said selected segment;

means for finding an entry in said class-1 table that is a best match for said vector Xbar1, referred to as a class-1 best match entry;

means for finding an entry in said class-2 table that is a best match for said vector Xbar2, referred to as a class-2 best match entry;

means for inserting into said compressed signal stream an identifying code, said identifying code representing a selected one of said class-1 best match entry or said class-2 best match entry.

18. An improved VQ system for compressing a digital graphic-image signal to produce a compressed signal stream, said system comprising:

means for providing a codebook comprising first and second tables of vector entries having different degrees of signal correlation, referred to as a class-1 table and a class-2 table respectively;

means for dividing said digital signal into a series of 4×

4 blocks, each block comprising a plurality of digital signal values, each said digital signal values representing one or more characteristics of a pixel;

means for determining a vector Xbar1 for a selected block representing a difference between the signal values in said selected block and an average of a selected group of signal values in a preceding block;

means for determining a vector Xbar2 for said selected block representing a difference between the signal values in said selected block and an average of all of said signal values in said selected block;

means for finding an entry in said class-1 table that is a best match for said vector Xbar1, referred to as a class-1 best match entry;

means for finding an entry in said class-2 table that is a best match for said vector Xbar2, referred to as a class-2 best match entry;

means for selecting one of said best match entries by;

(1) determining respective error values for each of said class-1 best match entry and said class-2 best match entry, and (2) selecting said class-2 best match entry if (i) the error value for said class-2 best match entry is less than the error value for said class-1 best match entry and (ii) said respective error values differ by more than a specified difference, else selecting said class-1 best match entry;

means for determining said respective error values by computing a least-squares distance between, respectively, (1) said class-1 best match entry and said vector Xbar1, and (2) said class-2 best match entry and said vector Xbar2; and

means for determining if both of said respective error values exceed a specified quality index, referred to as K, then inserting into said compressed signal stream a lossless compressed signal segment that represents all of the signal values of said selected block, else inserting into said compressed signal stream an identifying code of said selected best match entry;

means for transmitting said compressed signal stream to a decoder; and

at said decoder, means for decompressing said compressed signal stream into a decompressed graphic-image signal.

19. An improved VQ system for compressing a signal to produce a compressed signal stream, said system comprising:

means for providing first and second tables of vector entries having different degrees of signal correlation, referred to as a class-1 table and a class-2 table respectively;

means for dividing said digital signal into a series of segments, each segment comprising a plurality of digital signal values, each said segment having a quality index, referred to as K;

means for designating one or more of said segments as having a K of zero;

means for determining a vector Xbar1 for a selected segment representing a first degree of signal correlation for the signal values in said selected segment;

means for determining a vector Xbar2 for said selected segment representing a second degree of signal correlation for the signal values in said selected segment;

means for finding an entry in said class-1 table that is a best match for said vector Xbar1, referred to as a class-1 best match entry;

means for finding an entry in said class-2 table that is a best match for said vector Xbar2, referred to as a class-2 best match entry;

means for selecting one of said best match entries by;

(1) determining respective error values for each of said class-1 best match entry and said class-2 best match entry, and (2) selecting said class-2 best match entry if (i) the error value for said class-2 best match entry is less than the error value for said class-1 best match entry and (ii) said respective error values differ by more than a specified difference, else selecting said class-1 best match entry;

means for determining if both of said respective error values exceed the K for said selected segment, then inserting into said compressed signal stream a lossless compressed signal segment that represents all of the signal values of said selected segment, else inserting into said compressed signal stream an address of said selected one of said best match entries.