Method for selecting reproduction quality of transmitted vector quantized data

• US 5,247,348 A
• Filed: 11/19/1991
• Issued: 09/21/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: Israelsen, Paul D., Lucas, Keith
• Primary Examiner(s): Eisenzopf, Reinhard J.
• Assistant Examiner(s): Charouel, Lisa
• Application Number:
  US07/794,585
• Time in Patent Office: 672 Days
• Field of Search: 358/86, 358/133, 358/135, 358/136, 375/26, 375/27, 381/31, 381/36, 381/32
• US Class Current: 725/67
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 21/2383 Channel coding or modulation of digital bit-stream, e.g. QPSK modulation arrangements for detecting or preventing errors in the information received by adapting the channel coding H04L1/0009; analogue front ends or means for connecting modulators, demodulators or transceivers to a transmission line H04L27/0002
• CPC Class Codes: H04N 21/4382 Demodulation or channel decoding, e.g. QPSK demodulation analog front ends or means for connecting modulators, demodulators or transceivers to a transmission line H04L27/0002
• CPC Class Codes: H04N 7/10 Adaptations for transmission by electrical cable H04N7/12 takes precedence

Abstract

A method of communicating data from a first location to a second location employing a vector quantization data compression technique that allows users to select the reproduction quality of the transmitted vector quantized data. According to the method, data is encoded (compressed) from the last level of a first tree search vector quantization codebook at the first location. A second tree search vector quantization codebook is provided at the second location having a number of levels equal to or less than the number of levels in the first codebook. The reproduction quality of the transmitted vector quantized data is a function of the number of levels in the second codebook.

Claims

1. A method of communicating image data from a first location to a second location, comprising the steps of:

(a) receiving image data to be transmitted, and converting the image data to an input vector;

(b) defining a first codebook having a plurality N of levels of codevectors, the codevectors at each succeeding level of the first codebook representing a possible input vector with generally greater accuracy than the codevectors at a preceding level, each of the codevectors having an address associated therewith, and utilizing up to at least a selected level of the codevectors for comparison to the input vector;

(c) selecting from the selected level the codevector that most closely resembles the input vector;

(d) transmitting from the first location an indication of at least the address associated with the selected codevector; and

(e) performing the following steps at the second location;

(i) providing a second codebook having a plurality L of levels of codevectors, where L is a user selectable number between 1 and N inclusive, the codevectors of the L levels of the second codebook being substantially identical to the codevectors of a corresponding L levels of the first codebook, and identifying a selected level of the codevectors of the second codebook;

(ii) receiving the transmitted indication from the first location, obtaining the address therefrom, and placing the obtained address in a form for addressing up to the selected level of the codevectors of the second codebook;

(iii) retrieving from the second codebook the codevector residing at the obtained address to obtain a representation of the codevector selected in step (c);

(iv) employing the codevector retrieved in step (iii) to substantially re-create the image data at the second location.

2. Method according to claim 1 wherein the selected level of the first codebook is the Nth level.

3. Method according to claim 1 wherein the first and second codebooks are tree search vector quantization codebooks.

4. Method according to claim 1 wherein the codevectors of the L levels of the second codebook correspond to the codevectors of the first L levels of the first codebook on a one to one basis, and wherein the codevectors of the second codebook are substantially identical to corresponding codevectors of the first codebook.

5. Method according to claim 1 wherein the re-created image data has an accuracy , and the accuracy is a function of the number L of levels in the second codebook, the re-created image data being most accurate when L is equal to N.

6. Method according to claim 1 wherein the address of each codevector in the first codebook has a length corresponding to the level at which that codevector resides such that the addresses of the codevectors at a same level have a same length and the lengths increase with each successive level.

7. Method according to claim 6 wherein the selected level of the first codebook is the Nth level thereof, and the selected level of the second codebook is the Lth level thereof, and L is less than N, and the obtained address is capable of addressing up to an Nth level of codevectors, and wherein step (e)(ii) and (e)(iii) comprise the steps of:

(i'"'"') truncating the obtained address for addressing only up to the Lth level of codevectors in the second codebook; and

(ii'"'"') retrieving from the Lth level of the second codebook the codevector residing at the truncated address to obtain the representation of the codevector selected in step (c).

8. Method according to claim 1 wherein the first location is a transmitter location of cable television signals, and wherein the second location is a reception site in a cable television distribution network, and wherein the number L of levels provided in the second codebook is selected by a cable operator.

10. Method according to claim 1 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 number L of levels provided in the second codebook is selected by the pay television subscriber.

11. Method according to claim 8 or 10 wherein the indication is transmitted from the first location to the second location via satellite.

12. Method according to claim 1 wherein the image data comprises 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 transmitted;

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

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

13. Method according to claim 12 wherein the pixels are selected from a substantially identical portion of each of the temporally spaced image frames.

14. Method according to claim 1 wherein input vector has P possible orientations, and wherein steps (c) and (d) further comprise the steps of:

(a'"'"') assigning an identifying code to each of the orientations;

(b'"'"') defining a codebook search technique wherein at least one of the orientations is compared to the codevectors of the first codebook in accordance with a pre-selected criterion;

(c'"'"') applying the defined technique to select one of the codevectors of the first codebook; and

(d'"'"') transmitting an indication of the identifying code of the selected orientation and the address of the selected corresponding codevector,

and wherein step (e) further comprises obtaining the identifying code from the transmitted indication and employing the identifying code and the representation of the codevector selected in step (c) to re-orient, if necessary, the representation of the codevector so as to substantially re-create the image data.

15. Method according to claim 1 wherein the image data comprises 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 data indicative of each image frame to be transmitted;

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

(c'"'"') converting each block of pixels into the input vector.

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

17. Method according to claim 15 wherein each image frame is a color image frame, and each pixel within each image frame has at least associated luminance and chrominance values, at least some of the input vectors being representative of the luminance and chrominance values of a block of pixels in the image frame.

32. Method according to claim 1, 18, or 27 wherein the codevectors of ht 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.

33. Method according to claim 32 wherein the transform domain is the frequency domain and the codevectors and input vectors are transformed to the frequency domain by a Fourier transform.

9. Method according to claim 9 wherein the re-created image data is encoded in NTSC format and retransmitted from the reception site to a plurality of cable television subscribers over the cable television distribution network.

18. A method of communicating image data from a first location to a second location, comprising the steps of:

(a) receiving image data to be transmitted, and converting the image data to an input vector;

(b) providing a first codebook having a plurality N of levels of codevectors, the codevectors at each succeeding level of the first codebook representing a possible input vector with generally greater accuracy than the codevectors at a preceding level, there being an address associated with each of said codevectors, the address of each of said codevectors having a length corresponding to the level at which that codevector resides such that the addresses of codevectors at a same level have a same length and the lengths increase with each successive level;

(c) comparing the input vector tot he codevectors at each level of the first codebook until the Nth level has been reached and selecting from the Nth level the codevector that most closely resembles the input vector;

(d) transmitting from the first location an indication of at least the address associated with the selected codevector; and

(e) performing the following steps at the second location;

(i) providing a second codebook having a plurality L of levels of codevectors, where L is a user selectable number between 1 and N inclusive, the codevectors of the L levels of the second codebook being substantially identical to the codevectors of a corresponding L levels of the first codebook;

(ii) receiving the transmitted indication from the first location, and obtaining the address therefrom, the obtained address being capable of addressing up to an Nth level of codevectors in the second codebook;

(iii) performing the following steps (1) and (2) when the number L of levels in the second codebook is less than the number N of levels in the first codebook, but preceeding to step (iv) below when the number of levels L in the second codebook is equal to the number of levels N in the first codebook;

(1) truncating the obtained address for addressing only up to the Lth level of codevectors in the second codebook; and

(2) retrieving from the Lth level of the second codebook the codevector residing at the truncated address to obtain a representation of the codevector selected in step (c), and proceeding to step (v);

(iv) employing the obtained address in a non-truncated form to retrieve from the Lth level of the second codebook the codevector residing at the obtained address to substantially reproduce the codevector selected in step (c);

(v) employing the codevector obtained in step (iii) (2) or (iv) to substantially re-create the image data at the second location.

19. Method according to claim 18 wherein the first and second codebooks are tree search vector quantization codebooks.

20. Method according to claim 18 wherein the re-created image data has an accuracy, the accuracy being a function of the number of levels L in the second codebook, the re-created image data being most accurate when L is equal to N.

21. Method according to claim 18 wherein the first location is a transmitter location of cable television signals and wherein the second location is a reception site in a cable television distribution network, and wherein the number L of levels provided in the second codebook is selected by a cable operator.

22. Method according to claim 21 wherein the re-created image data is encoded in NTSC format and retransmitted from the reception site to a plurality of cable television subscribers over the cable television distribution network.

23. Method according to claim 18 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 number L of levels provided in the second codebook is selected by the pay television subscriber.

24. Method according to claim 21 or 23 wherein the indication is transmitted from the first location to the second location via satellite.

25. Method according to claim 18 wherein the image data comprises 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 transmitted;

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

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

26. Method according to claim 18 wherein the input vector has P possible orientations, and wherein steps (c) and (d) further comprise the steps of:

(a'"'"') assigning an identifying code to each of the orientations;

(b'"'"') defining a codebook search technique wherein at least one of the orientations is compared to the codevectors of the first codebook in accordance with a pre-selected criterion;

(c'"'"') applying the defined technique to select one of the codevectors of the first codebook; and

(d'"'"') transmitting an indication of the identifying code of the selected orientation and the address of the selected corresponding codevector,

and wherein step (e) further comprises obtaining the identifying code from the transmitted indication and employing the identifying code and the codevector obtained in step (iii)(2) or (iv) to re-orient, if necessary, the obtained codevector so as to substantially re-create the image data.

27. In a cable television system, a method of communicating image data to receiving locations of pay television signals, comprising the steps of:

(a) receiving image data to be transmitted, and converting the image data to an input vector;

(b) providing, in a memory located at a transmitter location of pay television signals, a first tree-search vector quantization codebook having a plurality N of levels of codevectors, the codevectors at each succeeding level of the first codebook representing possible input vectors with generally greater accuracy than the codevectors at a preceding level, there being a memory address associated with each of said codevectors, the address associated with each codevector having a length corresponding to the level at which that codevector resides such that the addresses of codevectors at a same level have a same length and the lengths of the addresses increase with each successive level;

(c) comparing the input vector to the codevectors at each level of the first codebook until the Nth level is reached, and selecting from the Nth level the codevector that most closely resembles the input vector;

(d) transmitting an indication of at least the address associated with the selected codevector to the receiving locations of the pay television signals; and

(e) performing the following additional steps at each receiving location;

(i) providing, in a memory at each receiving location, a second tree search vector quantization codebook having a plurality L of levels of codevectors, where L is a user selectable number between 1 and N inclusive, the codevectors of the L levels of the second codebook corresponding to th codevectors of the first L levels of the first codebook on a one to one basis, each of the codevectors of the second codebook being substantially identical to the corresponding codevector of the first codebook;

(ii) receiving the transmitted indication at each receiving location, obtaining the address therefrom, the obtained address being capable of addressing up to an Nth level of codevectors;

(iii) performing the following steps (1) and (2) when the number L of levels in the second codebook is less than the number N of levels in the first codebook, but proceeding to step (iv) below when the number L of levels in the second codebook is equal to the number N of levels in the first codebook;

(1) truncating the obtained address for addressing only up to the Lth level of codevectors in the second codebook; and

(2) retrieving from the Lth level of the second codebook the codevector residing at the truncated address to obtain a representation of the codevector selected in step (c), and proceeding to step (v);

(iv) employing the obtained address in a non-truncated form to retrieve from the Lth level of the second codebook the codevector residing at the obtained address to substantially reproduce the codevector selected in step (c);

(v) employing the codevector obtained in step (iii)(2) or (iv) to substantially re-create the image data at the second location, the re-created image data having an accuracy that is a function of the number L of levels in the second codebook, the re-created image data being most accurate when L is equal to N.

28. Method according to claim 27 wherein the receiving locations are locations of direct broadcast satellite pay television subscribers, and wherein the indication is transmitted directly to the receiving locations via satellite.

29. Method according to claim 27 wherein the receiving locations are locations of a cable head-end and wherein the indication is transmitted via satellite to each cable-head end and then television signals are transmitted from each cable-head end to cable television subscribers via a cable distribution network.

30. Method according to claim 29 wherein the television signals transmitted from the cable-head end to the cable television subscribers are a retransmitted form of the indications received at the cable head-end.

31. Method according to claim 27 wherein the indications received at the receiving locations are converted to NTSC format signals and then transmitted over a cable television distribution network to a plurality of cable television subscribers.

34. A pay television system for transmitting data indicative of temporally spaced image frames representing moving pictures to a plurality of receivers of pay television signals, wherein each image frame comprises a plurality of blocks of image data, the pay television system comprising:

a transmitter of pay television signals comprising;

a means for receiving the blocks of image data to be transmitted, and for converting each block of image data to an input vector;

a vector quantization encoder employing a first tree search codebook having N levels of codevectors, each codevector representing a possible input vector and having an address associated therewith, the encoder comparing each input vector to the codevectors of the first codebook and selecting for each input vector the codevector that most closely resembles the input vector; and

a means for transmitting indications of at least the addresses of the selected codevectors;

each of the plurality of pay television receivers comprising;

a means for receiving each of the indications transmitted from the transmitter of pay television signals and for each indication obtaining the address therefrom;

a vector quantization decoder employing a second tree search codebook having L levels of codevectors, where L is a subscriber selectable number between 1 and N inclusive, the codevectors of the L levels of the second codebook being substantially identical to the codevectors of a corresponding first L levels of the first codebook, the decoder placing the obtained addresses in a form for addressing up to the Lth level of codevectors in the second codebook and obtaining a representation of the codevectors selected at the transmitter by retrieving from the second codebook the codevectors residing at the obtained addresses, different ones of the receivers having a different number of levels L in their respective codebooks; and

means for employing the retrieved codevectors to substantially re-create the blocks of image data for display on a television set at a locale of the receiver.

35. Apparatus according to claim 34 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 the encoder is further operative to transform each input vector to the transform domain prior to comparing the input vector to the codevectors of the first codebook.

36. Apparatus according to claim 35 wherein the transform domain is the frequency domain and the codevectors and input vectors are transformed to the frequency domain by a Fourier transform technique.