Vector quantization method employing mirrored input vectors to search codebook

• US 5,204,899 A
• Filed: 11/19/1991
• Issued: 04/20/1993
• Est. Priority Date: 11/19/1991
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Scientific-Atlanta Incorporated (Cisco Systems, Inc.)
• Inventors: Lucas, Keith, Israelsen, Paul D.
• Primary Examiner(s): Swann, Tod R.
• Application Number:
  US07/794,563
• Time in Patent Office: 518 Days
• Field of Search: 380/10, 380/14, 381/30, 381/35, 358/133, 358/135, 358/136, 341/200
• US Class Current: 348/405.1
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 7/20 Adaptations for transmission via a GHz frequency band, e.g. via satellite

Abstract

A vector quantization me employs mirrored input vectors to increase the reproduction quality of transmitted vector quantized data. A codevector is selected from a vector quantization codebook for each possible orientation of an input vector. The codevector having the smallest distortion relative to the input vector is selected for transmission. An identification code identifying the selected orientation is also transmitted.

Claims

1. In a data compression system employing a vector quantization codebook having a plurality of codevectors each representative of a possible input vector, each codevector having an associated address, a method comprising the steps of:

a) receiving data to be compressed, and converting the data to a multi-dimensional input vector having a plurality of possible orientations, and assigning an identifying code to each orientation;

b) selecting one of the orientations;

c) comparing the input vector with the selected orientation to the codevectors of the codebook and selecting the codevector that most closely resembles the input vector with the selected orientation;

d) obtaining a measure of difference, if any, between the input vector with the selected orientation and the selected codevector;

e) selecting other ones of the remaining orientations of the input vector and, for each other selected orientation, repeating steps (c) and (d);

f) selecting the orientation and associated codevector that provided the least measure of difference in step (d); and

g) transmitting an indication of at least the address of the codevector and the identifying code of the orientation selected in step (f).

2. Method according to claim 1 wherein the multi-dimensional input vector is a two-dimensional vector and there are 4 possible orientations.

3. Method according to claim 1 wherein the received data to be compressed is image data comprising a two dimensional matrix of pixels having an x-axis and a y-axis, and wherein the two dimensional matrix of pixels is converted to a two-dimensional vector having four possible orientations, a first orientation being representative of the matrix of pixels substantially as received, a second orientation being representative of the matrix of pixels mirrored about the x-axis, a third orientation being representative of the matrix of pixels mirrored about the y-axis, and a fourth orientation being representative of the matrix of pixels mirrored about both the x-axis and the y-axis.

4. Method according to claim 1 wherein the multi-dimensional input vector is a three-dimensional vector and there are 32 possible orientations, and wherein 8 of the 32 possible orientations are selected in steps (c) through (e).

5. Method according to claim 1 wherein the received data to be compressed is image data comprising temporally spaced image frames representing moving images, and each image frame is defined by a plurality of pixels, and wherein step (a) comprises:

(a'"'"') receiving a plurality of temporally spaced image frames to be compressed;

(b'"'"') selecting pixels from a substantially identical portion of each of the temporally spaced image frames; and

(c'"'"') constructing the multi-dimensional input vector from the pixels selected from said portions.

6. Method according to claim 5 wherein each temporally spaced image frame comprises a two-dimensional matrix of pixels having an x-axis and a y-axis, and wherein the plurality of temporally spaced image frames comprises two temporally adjacent image frames, and wherein the pixels selected from the portions of the temporally adjacent image frames define a three-dimensional substantially cubic arrangement of pixels having an x-axis and a y-axis and a z-axis, the z-axis being defined by the temporal spacing between the adjacent image frames, and further wherein a three-dimensional input vector is constructed from the three-dimensional cubic arrangement of pixels and has 32 possible orientations, and still further wherein steps (c) through (e) are performed with 8 of the 32 possible orientations;

a first orientation being representative of the cubic arrangement of pixels formed by the portions of the image frames substantially as received, a second orientation being representative of the cubic arrangement of pixels mirrored about the x-axis, a third orientation being representative of the cubic arrangement of pixels mirrored about the y-axis, a fourth orientation being representative of the cubic arrangement of pixels mirrored about the z-axis, a fifth orientation being representative of the cubic arrangement of pixels mirrored about the x-axis and the y-axis, a sixth orientation being representative of the cubic arrangement of pixels mirrored about the x-axis and the z-axis, a seventh orientation being representative of the cubic arrangement of pixels mirrored about the y-axis and the z-axis, and an eighth orientation being representative of the cubic arrangement of pixels mirrored about the x-axis and the y-axis and the z-axis.

7. Method according to claim 1 wherein the data comprises image data, and wherein the image data comprises temporally spaced image frames representing moving images to be displayed on a television set, each image frame being defined by a plurality of pixels, and wherein step (a) comprises:

(a'"'"') receiving data indicative of image frames to be compressed;

(b'"'"') organizing each image frame into a plurality of blocks of pixels; and

(c'"'"') converting each block of pixels to a multi-dimensional input vector,

and wherein steps (b) through (g) are performed for each input vector.

8. Method according to claim 7 wherein each pixel has at least an associated intensity value and the received data is digital data indicative of at least the intensity value of each pixel, and further wherein at least ones of the input vectors comprise digital intensity data for a rectangular block of pixels in the image frame.

9. Method according to claim 7 wherein each image frame represents a color image, each pixel within each image frame having at least associated luminance and chrominance values, at least ones of the input vectors being representative of the luminance and chrominance values for a rectangular block of pixels in the image frame.

10. Method according to claim 7 wherein steps (a) through (g) are performed at a transmitter location and the television set is remote from the transmitter location, and the following additional steps are performed at the location of the television set:

(a'"'"') providing a substantially identical vector quantization codebook;

(b'"'"') receiving each indication transmitted from the transmitter location, obtaining therefrom the identifying code of the orientation and the address of the codevector, and retrieving from the substantially identical codebook the codevector residing at the obtained address to substantially reproduce the codevector selected in step (f); and

(c'"'"') employing the identifying code of the orientation and the reproduced codevector to substantially re-orient the reproduced codevector, if necessary, so as to substantially re-create each block of image frame data for display of the moving images on the television set.

11. Method according to claim 1 wherein the vector quantization codebook is a tree-search vector quantization codebook.

12. Method according to claim 1 wherein the codevectors of the codebook are transformed to a transform domain before being provided in the codebook and the codevectors are stored in the codebook in the transform domain, and wherein each input vector is transformed to the transform domain for selecting one of the codevectors from the codebook.

19. Method according to claim 12 or 18 wherein the transform domain is the frequency domain and the codevectors and input vectors are transformed to the frequency domain by a Fourier transform.

13. Method of transmitting image data from a first location to a second location wherein the image data comprises temporally spaced image frames representing moving images, each image frame being defined by a plurality of pixels, comprising the steps of:

(a) receiving data indicative of image frames to be transmitted, and organizing each image frame into a plurality of blocks of pixels, and converting each block of pixels to a multi-dimensional input vector, each input vector having a plurality of possible orientations, and assigning an identifying code to each orientation;

b) providing, in a memory at the first location, a first vector quantization codebook having a plurality of codevectors each representative of a possible input vector, each codevector having an associated address;

c) performing the following steps for each input vector;

i) selecting one of the orientations of the input vector;

ii) comparing the input vector with the selected orientation to the codevectors of the codebook and selecting the codevector that most closely resembles the input vector with the selected orientation;

iii) obtaining a measure of difference, if any, between the input vector with the selected orientation and the selected codevector;

iv) selecting other ones of the remaining orientations of the input vector and, for each other selected orientation, repeating steps (ii) and (iii);

v) selecting the orientation and codevector that provided the least measure of difference in step (iii);

vi) transmitting from the first location an indication of at least the address of the codevector and the identifying code of the orientation selected in step (v);

d) performing the following additional steps at the second location;

i) providing, in a memory at the second location, a second vector quantization codebook substantially identical to the first codebook;

(ii) receiving each indication transmitted from the first location, obtaining therefrom the identifying code of the orientation and the address of the codevector selected in step (c)(v), and retrieving from the second codebook the codevector residing at the obtained address to substantially reproduce the codevector selected in step (c)(v); and

(iii) employing the identifying code of the orientation and the reproduced codevector to substantially re-orient the reproduced codevector, if necessary, so as to substantially re-create each block of image frame data.

14. Method according to claim 13 wherein the first location is a transmitter location of television signals, and wherein the second location is a reception site in a cable television distribution network.

15. Method according to claim 14 wherein the re-created blocks of image frame data are encoded in NTSC format and the NTSC encoded data is distributed to a plurality of cable television subscriber locations via the cable television distribution network for display of the moving images on a television set at each subscriber location.

16. Method according to claim 14 wherein the first location is a transmitter location of pay television signals, and wherein the second location is the location of a pay television subscriber, and wherein the blocks of image frame data are re-created for display on a television at the locale of the pay television subscriber.

17. Method according to claim 14 or 16 wherein the indications are transmitted from the first location to the second location via satellite.

18. Method according to claim 13 or 14 wherein the codevectors of the first codebook are transformed to a transform domain before being provided in the first codebook, and the codevectors are stored in the first codebook in the transform domain, and wherein each input vector is transformed to the transform domain for selecting one of the codevectors from the first codebook.

20. In a pay television system, a method of transmitting image data from a transmitter location of pay television signals to a plurality of receiving locations of pay television signals wherein the image data comprises temporally spaced image frames representing moving images to be displayed on a television set, each image frame being defined by a two-dimensional matrix of pixels having an x-axis and a y-axis, comprising the steps of:

(a) receiving data indicative of image frames to be transmitted, and organizing each image frame into a plurality of two-dimensional blocks of pixels, and converting each block of pixels to a two-dimensional input vector, each input vector having four possible orientations, a first orientation being representative of the block of pixels substantially as received, a second orientation being representative of the block of pixels mirrored about the x-axis, a third orientation being representative of the block of pixels mirrored about the y-axis, and a fourth orientation being representative of the block of pixels mirrored about both the x-axis and the y-axis;

b) assigning an identifying code to each of the possible orientations;

c) providing, in a memory at the transmitter location, a first vector quantization codebook having a plurality of codevectors each representative of a possible input vector, each codevector having an associated address;

d) performing the following steps for each input vector;

i) selecting one of the orientations of the input vector;

ii) comparing the input vector with the selected orientation to the codevectors of the codebook and selecting the codevector that most closely resembles the input vector with the selected orientation;

iii) obtaining a measure of difference, if any, between the input vector with the selected orientation and the selected codevector;

iv) selecting other ones of the remaining orientations of the input vector and, for each other selected orientation, repeating steps (ii) and (iii);

v) selecting the orientation and associated codevector that provided the least measure of difference in step (iii);

vi) transmitting an indication of at least the identifying code of the orientation and the address of the associated codevector selected in step (v);

d) performing the following additional steps at each receiving location;

i) providing, in a memory at the receiving location, a second vector quantization codebook substantially identical to the first codebook;

ii) receiving each transmitted indication, obtaining therefrom the identifying code of the orientation and the address of the codevector selected in step (c)(v), and retrieving from the second codebook the codevector residing at each obtained address to substantially reproduce each codevector selected in step (c)(v);

(iii) employing each identifying code and reproduced codevector to substantially re-orient each reproduced codevector, if necessary, so as to substantially re-create each block of pixels; and

(iv) reconstructing each image frame from the re-created blocks of pixels for display on a television set at the receiver location.