Method and apparatus for low frequency removal in vector quantization

• US 5,235,418 A
• Filed: 11/19/1991
• Issued: 08/10/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
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US07/794,487
• Time in Patent Office: 630 Days
• Field of Search: 358/105, 358/133, 358/135, 358/136, 358/138, 375/27
• US Class Current: 375/240.22
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 7/10 Adaptations for transmission by electrical cable H04N7/12 takes precedence

Abstract

A method and apparatus for low-frequency removal in vector quantization of an image frame. An image frame is converted to plurality of input vectors. A mean value of each input vector is determined and transmitted to a plurality of reception sites. A low-frequency component of each input vector is then determined and removed from the input vector. A scalar mean value of each low-frequency removed vector is then determined and subtracted therefrom to produce a residual vector. The residual vectors are then vector quantized and the vector quantized data is transmitted to the reception sites. At a reception site, the transmitted mean values and vector quantized data are received and each input vector is reproduced therefrom. From the reproduced input vectors, the image frame is recreated for display at the reception site.

Claims

1. In a vector quantization data compression system employing a first vector quantization codebook for compressing an image frame for transmission to a plurality of reception sites, said codebook having a plurality of codevectors, each codevector being representative of a possible residual vector, there being an identification (ID) code associated with each codevector, a method comprising the steps of:

a) receiving an image frame to be transmitted, organizing the image frame into a plurality of blocks of data, and converting each block to a multi-dimensional input vector;

b) determining a mean value of each input vector and transmitting at least an indication of each mean value to at least one reception site;

c) performing the following additional steps for each input vector;

i) processing at least a portion of said means values to produce a low-frequency component vector representative of a low-pass version of the input vector;

ii) subtracting the low-frequency component vector produced in step (c)(i) from the input vector to obtain a low-frequency removed vector;

iii) determining a mean value of the low-frequency removed vector and subtracting the mean value of the low-frequency removed vector therefrom to obtain a residual vector;

iv) selecting from the first codebook the codevector that most closely resembles the residual vector; and

v) transmitting at least an indication of the ID code associated with the selected codevector to at least one reception site, said indication representing vector quantized data.

2. Method according to claim 1 wherein the first vector quantization codebook is provided in a memory, and wherein each ID code is a memory address of its associated codevector.

3. Method according to claim 1 wherein step (c)(i) comprises applying a two-dimensional interpolating low-pass filter to said portion of said means values.

4. Method according to claim 1 wherein said portion of said mean values comprises the mean value for the input vector under consideration and at least a portion of the input vectors adjacent the input vector under consideration.

5. Method according to claim 1 wherein the first codebook is a tree-structured codebook having plural levels of codevectors, the codevectors at each successive level representing possible residual vectors with greater accuracy than codevectors at a preceding level.

6. Method according to claim 5 wherein the codevectors are selected from the first codebook according to a distortion adaptive vector quantization algorithm.

7. Method according to claim 1 wherein a second vector quantization codebook, substantially identical to the first vector quantization codebook, is provided at least one reception site, and wherein the following additional steps are performed at the reception site:

a'"'"') receiving the transmitted indications for each input vector and obtaining the mean values and the ID codes therefrom;

b'"'"') performing the following steps to reproduce each input vector at the reception site;

i) selecting the obtained ID code that was transmitted in step (c)(v) for the input vector;

ii) retrieving from the second codebook the codevector associated with the obtained ID code to reproduce at least a substantial representation of the codevector selected in step (c) (iv);

iii) processing at least a first portion of the obtained mean values to produce a low-frequency component vector substantially identical to the low-frequency component vector produced in step (c)(i) for the input vector;

iv) determining a mean value of the low-frequency component vector produced in step (b'"'"')(iii);

v) subtracting the mean value of the low-frequency component vector produced in step (b'"'"') (iii) therefrom to obtain a zero-mean low-frequency component vector; and

vi) adding the zero-mean low-frequency vector and the obtained mean value for the input vector under consideration to the codevector retrieved in step (b'"'"') (ii) to reproduce a substantial representation of the input vector;

c'"'"') employing the input vectors reproduced in step (b'"'"') (vi) to substantially re-create the image frame for display on a television set at the reception site.

8. Method according to claim 7 wherein said first portion of said obtained mean values comprises the mean value for the input vector under consideration and the mean values of at least a portion of the input vectors adjacent the input vector under consideration.

9. Method according to claim 7 wherein step (b'"'"') (iii) comprises applying a two-dimensional interpolating low-pass filter to said first portion of said obtained mean values.

10. Method according to claim 9 wherein the two-dimensional interpolating low-pass filter applied in step (b'"'"') (iii) is substantially identical to the two-dimensional interpolating low-pass filter applied in step (c) (i).

11. Method according to claim 7 wherein step (b'"'"') (iv) comprises applying a two-dimensional interpolator to at least a second portion of the obtained mean values, whereby the mean value of the low-frequency component vector produced in step (b'"'"') (iii) may be determined without first producing the low-frequency component vector.

12. Method according to claim 11 wherein the second portion of the obtained mean values is substantially identical to the first portion of the obtained mean values.

13. Method according to claim 7 wherein the image frame comprises a matrix of image samples, and wherein each input vector represents a sub-matrix of said matrix of samples, and wherein each input vector is reproduced sample-by-sample, and wherein the image frame is re-created sample-by-sample.

14. Method according to claim 13 wherein the image samples represent pixel values.

15. In a vector quantization data compression system employing a first vector quantization codebook for compressing an image frame for transmission to a plurality of reception sites, said codebook having a plurality of codevectors, each codevector being representative of a possible residual vector, there being an identification (ID) code associated with each codevector, a method comprising the steps of:

a) receiving an image frame to be transmitted, organizing the image frame into a plurality of blocks of data, and converting each block to a multi-dimensional input vector;

b) determining a mean value of each input and transmitting each mean value to the reception sites;

c) performing the following additional steps for each input vector;

i) processing at least a portion of said mean values to produce a low-frequency component vector representative of a low-pass version of the input vector;

ii) obtaining a measure of difference between the low-frequency component vector produced in step (i) and the input vector;

iii) transmitting an instruction to the reception sites to indicate that no further data will be transmitted for the input vector when the measure of difference is less than a threshold value, but otherwise performing the following additional steps (iv) through (vii) for the input vector;

iv) subtracting the low-frequency component vector produced in step (c) (i) from the input vector to obtain a low-frequency removed vector;

v) determining a mean value of the low-frequency removed vector and subtracting the mean value of the low-frequency removed vector therefrom to obtain a residual vector;

vi) selecting from the first codebook the codevector that most closely resembles the residual vector; and

vii) transmitting at least an indication of the ID code associated with the selected codevector to the reception sites;

the indication of the ID code representing vector quantized data;

whereby vector quantized data for the input vector is not transmitted to the reception sites when the measure of difference obtained in step (c) (ii) is less than the threshold value.

16. Method according to claim 15 wherein the first vector quantization codebook is provided in a memory, and wherein each ID code is a memory address of its associated codevector.

17. Method according to claim 15 wherein the residual codevectors are transformed to a transform domain before being provided in the first codebook, and the codevectors are stored in the codebook in the transform domain, and wherein each residual vector is transformed to the transform domain for selecting one of the codevector from the first codebook.

18. Method according to claim 17 wherein the transform domain is the frequency domain and the codevectors and residual vectors are transformed to the frequency domain by a Fourier transform.

19. Method according to claim 15 wherein the first codebook is a tree-structured codebook having plural levels of codevectors, the codevectors at each successive level representing possible residual vectors with greater accuracy than codevectors at a preceding level.

20. Method according to claim 19 wherein the codevectors are selected from the first codebook according to a distortion adaptive vector quantization algorithm.

21. Method according to claim 15 wherein step (c) (i) comprises applying a two-dimensional interpolating low-pass filter to said portion of said mean values.

22. Method according to claim 21 wherein said portion of said mean values comprises the mean value for the input vector under consideration and the mean values of at least a portion of the input vectors adjacent the input vector under consideration.

23. Method according to claim 15 wherein a second vector quantization codebook, substantially identical to the first vector quantization codebook, is provided at at least one reception site, and wherein the following additional steps are performed at the reception site:

a'"'"') receiving the mean value of each input vector transmitted in step (b) and storing the received mean values of each input vector;

b'"'"') for each indication received at the reception site, obtaining the ID code therefrom and performing the following steps to reproduce, at the reception site, a representation of the input vector that caused the transmission of the indication of the ID code;

i) retrieving from the second codebook the codevector associated with the obtained ID code to reproduce at least a substantial representation of the codevector selected in step (c) (vi);

ii) processing at least a first portion of the received mean values to produce a low-frequency component vector substantially identical to the low-frequency component vector produced in step (c) (i) for the input vector;

iii) determining a mean value of the low-frequency component vector produced in step (b'"'"') (ii);

iv) subtracting the mean value of the low-frequency component vector produced in step (b'"'"') (ii) therefrom to obtain a zero-mean low-frequency component vector; and

v) adding the zero-mean low-frequency component vector and the received mean value for the input vector under consideration to the codevector retrieved in step (b'"'"') (i) to reproduce a substantial representation of the input vector;

c'"'"') for each instruction received at the reception site, performing the following step to reproduce, at the reception site, a representation of the input vector that caused the transmission of the instruction;

processing at least a first portion of the received mean values to produce a low-frequency component vector substantially identical to the low-frequency component vector produced in step (c) (i) for the input vector, said low-frequency component vector representing the input vector;

d'"'"') employing the reproduced representations of the input vectors to substantially re-create the image frame for display on a television set at the reception site.

24. Method according to claim 23 wherein said first portion of said received mean values comprises the mean value for the input vector under consideration and the mean values of at least a portion of the input vectors adjacent the input vector under consideration.

25. Method according to claim 23 wherein steps (b'"'"') (ii) and (c'"'"') are substantially identical to step (c) (i).

26. Method according to claim 23 wherein step (b'"'"') (ii) comprises applying a two-dimensional interpolating low-pass filter to said first portion of said received mean values.

27. Method according to claim 26 wherein step (c'"'"') is substantially identical to step (b'"'"') (ii).

28. Method according to claim 23 wherein step (b'"'"') (iii) comprises applying a two-dimensional interpolator to at least a second portion of the received mean values, whereby step (b'"'"') (iii) is not dependent upon step (b'"'"') (ii).

29. Method according to claim 28 wherein the second portion of the received mean values is substantially identical to the first portion of the received mean values.

30. Method according to claim 23 wherein the image frame comprises a matrix of image samples, and wherein each input vector represents a sub-matrix of said matrix of samples, and wherein each input vector is reproduced sample-by-sample, and wherein the image frame is re-created sample-by-sample.

31. Method according to claim 30 wherein the image samples represent pixel values.

32. Image compression apparatus comprising:

means for receiving a plurality of multi-dimensional input vectors representative of an image to be compressed;

a first mean value calculator for calculating a scalar mean value of each input vector;

an interpolating low-pass filter for interpolating a low-frequency component vector representative of a low-pass version of a current input vector, the low-frequency component vector being interpolated from the scalar mean values of at least a portion of the input vectors;

a first subtracting circuit for subtracting the low-frequency component vector from the current input vector to produce a low-frequency removed vector;

a second mean value calculator for calculating the scalar mean value of the low-frequency removed vector;

a second subtracting circuit for subtracting the scalar mean value of the low-frequency removed vector therefrom to produce a residual vector;

a codebook having a plurality of codevectors, each codevector being representative of a possible residual vector, each codevector having an associated identification (ID) code;

a controller for selecting one of the codevectors in the codebook that most closely resembles the residual vector; and

a transmitter for transmitting data indicative of the ID code of the selected codevector.

33. Data compression apparatus according to claim 32 further comprising means for transmitting the scalar mean value of each input vector.

34. Data compression apparatus according to claim 32 further comprising a memory for storing the scalar mean value of each input vector.

35. Data compression apparatus according to claim 32 wherein the codebook has a tree-structure and the controller employs a distortion adaptive vector quantization technique to select one of the codevectors.

36. Data compression apparatus according to claim 32 wherein the interpolating low-pass filter interpolates the low-frequency component vector from the scalar mean value of the current input vector and the scalar mean values of at least a portion of the input vectors adjacent the current input vector.

37. Data compression apparatus according to claim 32 further comprising a difference calculator for calculating a measure of difference between the low-frequency component vector and the current input vector.

38. Data compression apparatus according to claim 37 wherein the controller does not select a codevector from the codebook when the measure of difference calculated by the difference calculator is less than a threshold value, but instead provides an instruction indicating that the current input vector is substantially similar to the low-frequency component vector, and wherein in such instance, the transmitter transmits the instruction.

39. A decoder for use at a reception site of vector quantization data, wherein the vector quantization data originates from an encoding site employing a vector quantization encoder to compress input vectors indicative of blocks of data defining an image frame, the encoder transmitting a scalar mean value of each input vector and additionally transmitting, for each input vector, data indicative of an identification (ID) code associated with a residual codevector selected from a first vector quantization codebook, the decoder comprising:

a second codebook being substantially identical in content to the first codebook;

a first memory for storing at least the scalar mean values, transmitted from the encoding site, of input vectors for a current image frame;

a second memory for storing the ID code transmitted from the encoding site for each input vector of the current image frame;

an interpolating low-pass filter coupled to the first memory for interpolating a low-frequency component vector representative of a low-pass version of an input vector to be reconstructed and for providing the low-frequency component vector on an output thereof, the low-frequency component vector being interpolated from the scalar mean value of the input vector to be reconstructed and the scalar mean values of adjacent input vectors;

a mean value calculator for calculating the scalar mean value of the low-frequency component vector and for providing the scalar mean value of the low-frequency component vector on an output thereof;

a subtractor circuit having a first input coupled to the output of the interpolating low-pass filter and a second input coupled to the output of the mean value calculator for subtracting the scalar mean value of the low-frequency component vector therefrom to produce a zero-mean low-frequency component vector and for providing the zero-mean low-frequency component vector on an output thereof;

a controller for accessing the second memory to obtain the ID code transmitted for the input vector to be reconstructed and for retrieving from the second codebook, the residual codevector having the ID code associated therewith and for providing the residual codevector on an output of the controller;

a summing circuit having a first input coupled to the output of the subtractor circuit, a second input coupled to the first memory, and a third input coupled to the input of the controller for adding the zero-mean low-frequency component vector for the input vector to be reconstructed, the scalar mean value stored in the second memory for the input vector to be reconstructed, and the residual codevector retrieved from the second codebook for the input vector to be reconstructed, and for providing the sum on an output thereof, the sum being a substantial representation of the input vector;

at least one converter coupled to the output of the summing circuit for converting the substantial representation of the input vector to NTSC format image data and for providing the NTSC format image data at an output thereof for display on a display device at the locale of the reception site.

40. Decoder according to claim 39 wherein the mean value calculator comprises an interpolator and wherein the scalar mean value of the low-frequency component vector is interpolated from the scalar mean value of the input vector under reconstruction and from the scalar mean values of adjacent input vectors, whereby the scalar mean value of the low-frequency component vector may be calculated without first obtaining the low-frequency component vector.

41. Decoder according to claim 39 wherein all vectors comprise a plurality of individual samples, and wherein the low-frequency component vectors are interpolated sample-by-sample and the input vectors are reconstructed and converted to NTSC format data sample-by-sample.

42. Decoder according to claim 41 wherein storage of real-time image data prior to display is not required.

43. A decoder for use at a reception site of vector quantization data, wherein the vector quantization data originates from an encoding site employing a vector quantization encoder to compress input vector indicative of blocks of data defining an image frame, the encoder transmitting a scalar mean value of each input vector and additionally transmitting, for each input vector, either (i) data indicative of an identification (ID) code associated with a residual codevector selected from a first vector quantization codebook, or (ii) an instruction to approximate the input vector by a low-frequency component vector interpolated from the scalar mean value of the input vector and the scalar mean values of adjacent input vectors, the decoder comprising:

a second codebook being substantially identical in content to the first codebook;

a first memory for storing at least the scalar mean values, transmitted from the encoding site, of input vectors for a current image frame;

a second memory for storing (i) the ID code or (ii) the instruction transmitted from the encoding site for each input vector of the current image frame;

an interpolating low-pass filter coupled to the first memory for interpolating a low-frequency component vector representative of a low-pass version of an input version to be reconstructed and for providing the low-frequency component vector on an output thereof, the low-frequency component vector being interpolated from the scalar mean value of the input vector to be reconstructed and the scalar mean values of adjacent input vectors;

a mean value calculator for calculating the scalar mean value of the low-frequency component vector and for providing the scalar mean value of the low-frequency component vector on an output thereof;

a subtractor circuit having a first input coupled to the output of the interpolating low-pass filter and a second input coupled to the output of the mean value calculator for subtracting the scalar mean value of the low-frequency component vector therefrom to produce a zero-mean low-frequency component vector and for providing the zero-mean low-frequency component vector on an output thereof;

a controller for accessing the second memory to determine whether an ID code or an instruction was transmitted for the input vector to be reconstructed, and where an ID code was transmitted for the input vector to be reconstructed, retrieving from the second codebook, the residual codevector having the ID code associated therewith and for providing the residual codevector on a first output thereof and a control signal on a second output thereof;

a summing circuit having a first input coupled to the output of the subtractor circuit, a second input coupled to the second memory, and a third input coupled to the first output of the controller for adding the zero-mean low-frequency component vector for the input vector to be reconstructed, the scalar mean value stored in the second memory for the input vector to be reconstructed, and the residual codevector retrieved from the second codebook for the input vector to be reconstructed, and for providing the sum on an output thereof, the sum being a substantial representation of the input vector;

a multiplexor having first and second data inputs and a data selector input, the first data input being coupled to the output of the summing circuit, the second data input being coupled to the output of the interpolating low-pass filter, and the data selector input being coupled to the second output of the controller for providing on an output of the multiplexor, in accordance with the control signal from the controller, either (i) the substantial representation of the input vector, or (ii) the low-frequency component vector which represents a low-pass version of the input vector; and

at least one converter coupled to the output of the multiplexor for converting the multiplexor output to NTSC format image data and for providing the NTSC format image data at an output thereof for substantially reproducing the image frame that was input to the encoding site,

whereby if the controller determines that an ID code was transmitted for the input vector to be reconstructed, then the controller selects the first data input of the multiplexor and the substantial representation of the input vector is converted to NTSC format image data, but if the controller determines that an instruction was transmitted for the input vector to be reconstructed then the controller selects the second data input of the multiplexor and the low-frequency component vector, which represents a low-pass version of the input vector, is converted to NTSC format image data as an approximation of the input vector.

44. Decoder according to claim 43 wherein the mean value calculator comprises an interpolator and wherein the scalar mean value of the low-frequency component vector is interpolated from the scalar mean value of the input vector under reconstruction and from the scalar mean values of adjacent input vectors, whereby the scalar mean value of the low-frequency component vector may be calculated without first obtaining the low-frequency component vector.

45. Decoder according to claim 43 wherein all vectors comprise a plurality of individual samples, and wherein the low-frequency component vectors are interpolated sample-by-sample and the input vectors are reconstructed and converted to NTSC format data sample-by-sample.

46. Decoder according to claim 43 wherein storage of real-time image data prior to display is not required.