Image compression method and apparatus employing distortion adaptive tree search vector quantization

Claim 2

In a vector quantization data compression system employing a tree search vector quantization codebook having plural levels of codevectors representative of possible input vectors to be processed by the system, each input vector being indicative of a block of data to be compressed, each codevector having an associated identification (ID) code, a method comprising the steps of: a) receiving an input vector and determining a mean value of the received input vector; b) transmitting data indicative of the mean value; c) determining a difference value indicative of a difference between the input vector and the mean value, and comparing the difference value to a threshold value; d) performing the following additional steps when the difference value exceeds the threshold value: (i) selecting a codevector from the codebook based upon a processed version of the input vector and the threshold value; and, ii) transmitting data indicative of the ID code associated with the selected codevector.

Claim 3

Method according to claim 1 wherein the codevectors are stored in a memory and each ID code is a memory address.

Claim 4

Method according to claim 2 wherein the addresses have a variable length that increases with each level of codevectors and wherein, on average, the length of the addresses is shorter than a length of the codevectors, and step (d)(ii) comprises transmitting the variable length address.

Claim 5

Method according to claim 2 wherein a compression code is assigned to each possible address, each compression code having a length that is substantially inversely proportional to a predetermined probability that a particular codevector will be selected in step (d)(i), and step (d)(ii) comprises transmitting the compression code for the address associated with the selected codevector.

Claim 6

Method according to claim 1 further comprising the step of periodically adjusting the threshold value based upon an average length of data transmitted in steps (b) and (d)(ii).

Claim 7

Method according to claim 3 or 4 wherein the data to be transmitted is temporarily stored then transmitted at a substantially fixed data rate.

Claim 8

Method according to claim 1 wherein the system receives input data to be compressed and the input data is representative of a moving image.

Claim 9

Method according to claim 1 wherein, prior to performing step (d), the mean value is removed from the input vector to obtain a residual vector, and the residual vector is employed to select the codevector in step (d)(i), the residual vector being the said processed version of the input vector.

Claim 10

Method according to claim 8 wherein step (d)(i) comprises: a') selecting an initial level of the codebook; b') selecting the codevector at the selected level that most closely resembles the residual vector; c') obtaining a measure of difference, if any, between the selected codevector and the residual vector; d') proceeding to step (d)(ii) only if the measure of difference is less than the threshold value, but otherwise selecting a next level of the codebook and repeating steps (b') and (c') until either the measure of difference is less than the threshold value or a last level of the codebook has been employed, then proceeding to step (d)(ii).

Claim 11

Method according to claim 4 wherein the compression codes are Huffman codes.

Claim 12

In a tree search, variable rate vector quantization data compression system of the type that converts a block of input data to a multi-dimensional input vector, and having a codebook with plural levels of codevectors, each codevector being representative of a possible input vector for converting each input vector to an identification (ID) code associated with each codevector, the codevectors at each successive level representing possible input vectors with greater accuracy than codevectors at a preceding level, a method comprising the steps of: a) processing the input vector and selecting an initial level of the codebook; b) comparing the processed vector to the codevectors at the selected level of the codebook and selecting the codevector that most closely resembles the processed vector; c) obtaining a measure of difference, if any, between the processed vector and the selected codevector; d) transmitting an indication of the ID code associated with the selected codevector only if the measure of difference is less than a threshold value, but otherwise selecting a next level of the codebook and repeating steps (b) and (c) until either the measure of difference is less than the threshold value or a last level of the codebook is reached, then transmitting the indication, each ID code having a length that, on average, is shorter than a length of its associated codevector.

Claim 13

In a tree search, variable rate vector quantization data compression system of the type that converts a block of input data to a multi-dimensional input vector, and having a codebook with plural levels of codevectors, each codevector being representative of a possible input vector for converting each input vector to an identification (ID) code associated with each codevector, the codevectors at each successive level representing possible input vectors with greater accuracy than codevectors at a preceding level, a method comprising the steps of: a) processing the input vector and selecting an initial level of the codebook; b) comparing the processed vector to the codevectors at the selected level of the codebook and selecting the codevector that most closely resembles the processed vector; c) obtaining a measure of difference, if any, between the processed vector and the selected codevector; d) transmitting an indication of the ID code associated with the selected codevector only if the measure of difference is less than a threshold value, but otherwise selecting a next level of the codebook and repeating steps (b) and (c) until either the measure of difference is less than the threshold value or a last level of the codebook is reached, then transmitting the indication, each ID code having a length that, on average, is shorter than a length of its associated codevector.

Claim 14

Method according to claim 11 wherein step (a) comprises determining a mean value of each input vector and removing the mean value from the input vector to obtain a residual vector, the processed vector comprising the residual vector.

Claim 15

Method according to claim 11 wherein the codebook is stored in a memory and each ID code is a memory address and the memory addresses have a variable length wherein the length increases with each successive level of codevectors, the transmitted indication identifying the variable length address of a finally selected codevector and the level of the finally selected codevector.

Claim 16

Method according to claim 11 wherein the codebook is stored in a memory and each ID code is a memory address, and a compression code is assigned to each possible address, each compression code having a length that is substantially inversely proportional to a predetermined probability that a particular codevector will be finally selected, the transmitted indication comprising the compression code for the address associated with the finally selected codevector.

Claim 17

Method according to claim 14 wherein the compression codes are Huffman codes.

Claim 18

Method according to claim 13 or 14 further comprising the step of automatically adjusting the threshold based upon a measure of average length of previously transmitted indications.

Claim 19

Method according to claim 13 or 14 wherein the indications are transmitted at a fixed data rate, further comprising the steps of storing indications to be transmitted in a buffer, periodically obtaining a measure of unused capacity of the buffer, and automatically adjusting the threshold value based upon the measure of unused buffer capacity.

Claim 20

Method according to claim 12 wherein the following steps (i) and (ii) are performed prior to performing steps (b)-(d): i) obtaining a measure of difference between the mean value and the input vector; and, ii) comparing the measure of difference from step (i) to the threshold value; and wherein steps (b)-(d) are performed only if the result of the comparison of step (ii) indicates that the measure of difference from step (i) is greater than the threshold value; and further comprising the step of always transmitting an indication of the mean value of each received input vector.

Claim 21

Method according to claim 18 further comprising the step of compressing both the ID code associated with the finally selected codevector and the mean value according to a lossless compression technique, the transmitted indication comprising both the compressed ID code and the compressed mean value.

Claim 22

Method according to claim 19 wherein the compression technique is a Huffman encoding technique.

Claim 23

Method according to claim 11 wherein the input data comprises image frames representing moving images to be displayed on a television set, each image frame comprising a matrix of pixels and each pixel within each image frame having at least an associated intensity value, and at least ones of the input vectors are representative of the intensity values of a block of pixels in the image.

Claim 24

Method according to claim 11 wherein the input data comprises image frames representing moving images to be displayed on a television set, each image frame comprising a matrix of pixels and each pixel within each image frame having at least associated luminance and chrominance values, and at least ones of the input vectors are representative of the luminance and chrominance values of a block of pixels in the image.

Claim 25

Method according to claim 16 wherein the input data comprises temporally spaced image frames representing a moving image and the threshold is adjusted only between image frames.

Claim 26

Method according to claim 17 wherein the input data comprises temporally spaced image frames representing a moving image and the threshold is adjusted only between image frames.

Claim 27

Method according to claim 16 wherein the input data comprises temporally spaced image frames representing a moving image and the threshold is periodically adjusted within image frames.

Claim 28

Method according to claim 17 wherein the input data comprises temporally spaced image frames representing a moving image and the threshold is periodically adjusted within image frames.

Claim 29

Method according to claim 21 further comprising the steps of: providing another substantially identical tree search vector quantization codebook at a locale of the television set; receiving each transmitted indication at the locale of the television set, obtaining the ID code therefrom, and retrieving from the codebook at the locale of the television set the codevector associated with the obtained ID code to reproduce at least a substantial representation of the finally selected codevector; employing each reproduced finally selected codevector to substantially re-create each image frame at the locale of the television set and display each re-created image frame on the television set.

Claim 30

Method according to claim 27 wherein the data is transmitted via satellite to a reception site then retransmitted at the reception site over a cable television distribution network to a plurality of cable television subscribers.

Claim 31

Method according to claim 27 wherein the data is transmitted via satellite directly to a reception site comprising one of a free television broadcast recipient, a cable head end, a reception location of a cable television distribution system, or a pay television subscriber.

Claim 32

Method according to claim 21 wherein the data is transmitted via satellite to a reception site and the following steps are performed at the reception site: providing another substantially identical tree search vector quantization codebook at a locale of the reception site; receiving each transmitted indication at the locale of the reception site, obtaining the ID code therefrom, and retrieving from the codebook at the locale of the reception site the codevector associated with the obtained ID code to reproduce at least a substantial representation of the finally selected codevector; employing each reproduced finally selected codevector to substantially re-create each image frame at the locale of the reception site and encoding data for each re-created image frame in NTSC format; transmitting the NTSC encoded data from the reception site to a plurality of cable television subscribers over a cable television distribution network.

Claim 33

In a data compression system of the type converting input data to multi-dimensional input vectors each representing a block of data, a method comprising: a) determining a mean value of each input vector and, transmitting data indicative of the mean value; b) providing, in a memory, a tree-search vector quantization codebook having plural levels of codevectors, there being a residual vector defined by each input vector, each codevector being representative of a possible residual vector and each successive level of codevectors representing possible residual vectors with greater accuracy than a preceding level of codevectors, there being a memory address associated with each codevector; c) obtaining a measure of difference between the mean value and the input vector and comparing the measure of difference to a threshold value and performing the following additional steps only if the measure of difference exceeds the threshold value; d) removing the mean value from the vector to obtain the residual vector defined by the input vector and selecting an initial level in the codebook; e) comparing the residual vector to the codevectors at the selected level and selecting the codevector at the selected level that most closely resembles the residual vector; f) calculating a distortion value representative of a difference, if any, between the selected codevector and the residual vector, and comparing the distortion value to the threshold value; g) selecting the next level in the codebook if the distortion value exceeds the threshold value and repeating steps (e) and (f) until either (1) the distortion value does not exceed the threshold value, or (2) a last level of the codebook has been reached, to obtain a finally selected codevector; and, h) transmitting an indication of at least the address associated with the finally selected codevector, each transmitted indication having a length that is on average shorter than a length of the finally selected codevector.

Claim 34

In a data compression system of the type converting input data to multi-dimensional input vectors each representing a block of data, a method comprising: a) determining a mean value of each input vector and, transmitting data indicative of the mean value; b) providing, in a memory, a tree-search vector quantization codebook having plural levels of codevectors, there being a residual vector defined by each input vector, each codevector being representative of a possible residual vector and each successive level of codevectors representing possible residual vectors with greater accuracy than a preceding level of codevectors, there being a memory address associated with each codevector; c) obtaining a measure of difference between the mean value and the input vector and comparing the measure of difference to a threshold value and performing the following additional steps only if the measure of difference exceeds the threshold value; d) removing the mean value from the vector to obtain the residual vector defined by the input vector and selecting an initial level in the codebook; e) comparing the residual vector to the codevectors at the selected level and selecting the codevector at the selected level that most closely resembles the residual vector; f) calculating a distortion value representative of a difference, if any, between the selected codevector and the residual vector, and comparing the distortion value to the threshold value; g) selecting the next level in the codebook if the distortion value exceeds the threshold value and repeating steps (e) and (f) until either (1) the distortion value does not exceed the threshold value, or (2) a last level of the codebook has been reached, to obtain a finally selected codevector; and, h) transmitting an indication of at least the address associated with the finally selected codevector, each transmitted indication having a length that is on average shorter than a length of the finally selected codevector.

Claim 35

Method according to claim 31 wherein the addresses have variable length that increases with each successive level of codevectors, the transmitted indication identifying both the variable length address and level of the finally selected codevector.

Claim 36

Method according to claim 31 wherein step (h) comprises compressing the address associated with the finally selected codevector according to a lossless compression technique then transmitting the compressed address, the transmitted indication comprising the compressed address.

Claim 37

Method according to claim 33 wherein the address is compressed according to a Huffman encoding technique.

Claim 38

Method according to claim 31 wherein step (a) comprises compressing the mean value according to a lossless compression technique then transmitting the compressed mean value, the transmitted data indicative of the mean value comprising the compressed mean value.

Claim 39

Method according to claim 31 wherein both the address associated with the finally selected codevector and the mean value are compressed according to a lossless compression technique, and step (a) comprises transmitting the compressed mean value and step (g) comprises transmitting the compressed address.

Claim 40

Method according to claim 35 wherein the mean value is compressed according to a Huffman encoding technique.

Claim 41

Method according to claim 31 wherein, prior to performing step (h), a compression code is assigned to each possible address, each compression code having a length that is substantially inversely proportional to a predetermined probability that a particular codevector will be finally selected, the transmitted indication comprising the compression code for the address associated with the finally selected codevector.

Claim 42

Method according to claim 38 wherein the compression codes are Huffman codes.

Claim 43

Method according to claim 31, 32 or 38 wherein the indications are transmitted at a substantially fixed data rate.

Claim 44

Method according to claim 40 further comprising the step of storing indications to be transmitted in a buffer, periodically obtaining a measure of unused capacity of the buffer, and periodically and automatically adjusting the threshold value based upon the measure of unused capacity of the buffer.

Claim 45

Method according to claim 41 wherein the threshold value is adjusted by increasing the threshold value when the measure indicates that unused buffer capacity is decreasing and decreasing the threshold value when the measure indicates that unused buffer capacity is increasing, adjustment of the threshold value ensuring that the buffer does not empty or overflow.

Claim 46

Method according to claim 31 wherein the input data comprises image frames representing moving images to be displayed on a television set, each image frame comprising a matrix of pixels and each pixel within each image frame having at least an associated intensity value, and at least ones of the input vectors are representative of the intensity values of a block of pixels in the image.

Claim 47

Method according to claim 31 wherein the input data comprises image frames representing moving images to be displayed on a television set, each image frame comprising a matrix of pixels and each pixel within each image frame having at least associated luminance and chrominance values, and at least ones of the input vectors are representative of the luminance and chrominance values of a block of pixels in the image.

Claim 48

Method according to claim 31 wherein the input data comprises temporally spaced image frames representing a moving image and the threshold is adjusted only between image frames.

Claim 49

Method according to claim 41 wherein the input data comprises temporally spaced image frames representing a moving image and the threshold is adjusted only between image frames.

Claim 50

Method according to claim 41 wherein the input data comprises temporally spaced image frames representing a moving image and the threshold is periodically adjusted within image frames.

Claim 51

Method according to claim 43 further comprising the steps of: providing another substantially identical tree search vector quantization codebook at a locale of the television set; receiving each transmitted indication at the locale of the television set, obtaining the address therefrom, and retrieving from the codebook at the locale of the television set the codevector residing at the obtained address to reproduce at least a substantial representation of the finally selected codevector; employing each reproduced finally selected codevector to substantially re-create each image frame at the locale of the television set and display each recreated image frame on the television set.

Claim 52

Method according to claim 48 wherein the data is transmitted via satellite to a reception site then retransmitted at the reception site over a cable television distribution network to a plurality of cable television subscribers.

Claim 53

Method according to claim 48 wherein the data is transmitted via satellite directly to a pay television subscriber.

Claim 54

Method according to claim 43 wherein the data is transmitted via satellite to a reception site and the following steps are performed at the reception site: providing another substantially identical tree search vector quantization codebook at a locale of the reception site; receiving each transmitted indication at the locale of the reception site, obtaining the address therefrom, and retrieving from the codebook at the locale of the reception site the codevector associated with the obtained address to reproduce at least a substantial representation of the finally selected codevector; employing each reproduced finally selected codevector to substantially re-create each image frame at the locale of the reception site and encoding data for each re-created image frame in NTSC format; transmitting the NTSC encoded data from the reception site to a plurality of cable television subscribers over a cable television distribution network.

Claim 55

Variable rate vector quantization data compression method comprising the steps of: a) receiving data indicative of an image to be compressed, organizing the image data into blocks, and converting each block to a multi-dimensional input vector; b) determining a mean value of the input vector; c) assigning a compression code to the mean value according to a lossless compression technique and storing the compression code in a first-in first-out (FIFO) buffer; d) providing, in a memory, a tree-search vector quantization codebook having plural levels of codevectors, there being a residual vector defined by each input vector, each codevector being representative of a possible residual vector and each successive level of codevectors representing the possible residual vectors in greater detail than a preceding level of codevectors, there being a memory address associated with each codevector; e) assigning a compression code to each possible address, each compression code having a length that is substantially inversely proportional to a predetermined likelihood that the codevector associated with the address corresponding to the compression code will be selected; f) obtaining a measure of difference between the input vector and the mean value and comparing the measure of difference to a threshold value and performing steps (f1) through (f5) below only if the measure of difference exceeds the threshold value; f1) removing the mean value from the input vector to obtain the residual vector defined by the input vector and selecting an initial level in the codebook; f2) comparing the residual vector to the codevectors at the selected level and selecting the codevector that most closely resembles the residual vector; f3) obtaining a measure of difference, if any, between the selected codevector and the residual vector, and comparing the measure of difference between the selected codevector and the residual vector to the threshold value; f4) selecting the next level in the codebook if the measure of difference obtained in step (f3) exceeds the threshold value; f5) repeating steps (f1) through (f4) until either (1) the measure of difference does not exceed the threshold value, or (2) a last level of the codebook has been reached, to obtain a finally selected codevector and storing the compression code for the address of the finally selected codevector in the FIFO buffer; g) repeating steps (b) through (f) for each new input vector while sequentially transmitting each compression code stored in the FIFO buffer at a fixed data rate; and, h) maintaining a measure of unused FIFO buffer capacity and periodically adjusting the threshold value by automatically increasing the threshold value when the measure of unused FIFO buffer capacity indicates that unused capacity is decreasing and automatically decreasing the threshold value when the measure of unused FIFO buffer capacity indicates that unused capacity is increasing, adjustment of the threshold value ensuring that the buffer does not empty or overflow as a result of storing variable length compression codes but transmitting the same at a fixed data rate.

Claim 56

Variable rate vector quantization data compression method comprising the steps of: a) receiving data indicative of an image to be compressed, organizing the image data into blocks, and converting each block to a multi-dimensional input vector; b) determining a mean value of the input vector; c) assigning a compression code to the mean value according to a lossless compression technique and storing the compression code in a first-in first-out (FIFO) buffer; d) providing, in a memory, a tree-search vector quantization codebook having plural levels of codevectors, there being a residual vector defined by each input vector, each codevector being representative of a possible residual vector and each successive level of codevectors representing the possible residual vectors in greater detail than a preceding level of codevectors, there being a memory address associated with each codevector; e) assigning a compression code to each possible address, each compression code having a length that is substantially inversely proportional to a predetermined likelihood that the codevector associated with the address corresponding to the compression code will be selected; f) obtaining a measure of difference between the input vector and the mean value and comparing the measure of difference to a threshold value and performing steps (f1) through (f5) below only if the measure of difference exceeds the threshold value; f1) removing the mean value from the input vector to obtain the residual vector defined by the input vector and selecting an initial level in the codebook; f2) comparing the residual vector to the codevectors at the selected level and selecting the codevector that most closely resembles the residual vector; f3) obtaining a measure of difference, if any, between the selected codevector and the residual vector, and comparing the measure of difference between the selected codevector and the residual vector to the threshold value; f4) selecting the next level in the codebook if the measure of difference obtained in step (f3) exceeds the threshold value; f5) repeating steps (f1) through (f4) until either (1) the measure of difference does not exceed the threshold value, or (2) a last level of the codebook has been reached, to obtain a finally selected codevector and storing the compression code for the address of the finally selected codevector in the FIFO buffer; g) repeating steps (b) through (f) for each new input vector while sequentially transmitting each compression code stored in the FIFO buffer at a fixed data rate; and, h) maintaining a measure of unused FIFO buffer capacity and periodically adjusting the threshold value by automatically increasing the threshold value when the measure of unused FIFO buffer capacity indicates that unused capacity is decreasing and automatically decreasing the threshold value when the measure of unused FIFO buffer capacity indicates that unused capacity is increasing, adjustment of the threshold value ensuring that the buffer does not empty or overflow as a result of storing variable length compression codes but transmitting the same at a fixed data rate.

Claim 57

Method according to claim 52 wherein the compression codes are Huffman codes.

Claim 58

Method according to claim 52 wherein the image is represented by a matrix of pixels each having at least an 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.

Claim 59

Method according to claim 52 wherein the image is represented by a matrix of pixels in an image frame and the images are color images, 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 of a block of pixels in the image.

Claim 60

Method according to claim 52 wherein the image is a moving image represented by sequential image frames and data indicative of sequential frames is captured in frame buffers, and the received data corresponds to data stored in each frame buffer, and wherein the threshold value is adjusted only between receipt of the data for each sequential frame.

Claim 61

Method according to claim 54 wherein the indications are transmitted to a cable television subscriber further comprising the steps of: providing another substantially identical tree search vector quantization codebook at a locale of the cable television subscriber; receiving each transmitted indication at the locale of the cable television subscriber, obtaining the address therefrom, and retrieving from the codebook at the locale of the cable television subscriber the codevector residing at the obtained address to reproduce at least a substantial representation of the finally selected codevector; employing each reproduced finally selected codevector to substantially re-create each image frame at the locale of the cable television subscriber and display each re-created image frame on a television set of the cable television subscriber.

Claim 62

Method according to claim 57 wherein the data is transmitted via satellite to a reception site then retransmitted at the reception site over a cable television distribution network to the cable television subscriber.

Claim 63

Method according to claim 54 wherein the data is transmitted via satellite directly to a pay television subscriber further comprising the steps of: providing another substantially identical tree search vector quantization codebook at a locale of the pay television subscriber; receiving each transmitted indication at the locale of the pay television subscriber, obtaining the address therefrom, and retrieving from the codebook at the locale of the pay television subscriber the codevector residing at the obtained address to reproduce at least a substantial representation of the finally selected codevector; employing each reproduced finally selected codevector to substantially re-create each image frame at the locale of the pay television subscriber and display each re-created image frame on a television set of the pay television subscriber.

Claim 64

Method according to claim 54 wherein the data is transmitted via satellite to a reception site and the following steps are performed at the reception site: providing another substantially identical tree search vector quantization codebook at a locale of the reception site; receiving each transmitted indication at the locale of the reception site, obtaining the address therefrom, and retrieving from the codebook at the locale of the reception site the codevector associated with the obtained address to reproduce at least a substantial representation of the finally selected codevector to reproduce at least a substantial representation of the finally selected codevector; employing each reproduced finally selected codevector to substantially re-create each image frame at the locale of the reception site and encoding data for each re-created image frame in NTSC format; transmitting the NTSC encoded data from the reception site to a plurality of cable television subscribers over a cable television distribution network.

Claim 65

In a cable television system, a method of communicating temporally spaced image frames representing moving images to be displayed on a subscriber set, each image frame comprising a matrix of pixels and each pixel within each image frame having at least an associated intensity value, the method comprising the steps of: a) digitizing the intensity values for the pixels within each image frame and formatting the digital intensity values corresponding to a rectangular block of pixels within the image frame to a multi-dimensional input vector; b) processing the input vector; c) providing, in a memory located at a transmitter location of cable television signals, a first tree-search vector quantization codebook having plural levels of codevectors each representative of a possible processed vector for converting each processed vector to a memory address associated with each codevector, the codevectors at each successive level representing possible processed vectors in greater detail than codevectors at a preceding level; d) selecting an initial level in the codebook; e) comparing each processed vector to the codevectors at the selected level and selecting the codevector at the selected level that most closely resembles the processed vector; f) calculating a measure of difference, if any, between the selected codevector and the processed vector, and comparing the measure of difference to a threshold value; g) selecting the next level in the codebook if the measure of difference exceeds the threshold value and repeating steps (e) and (f) until either (1) the measure of difference does not exceed the threshold value, or (2) a last level of the codebook has been reached, to obtain a finally selected codevector; h) temporarily storing indications of at least addresses associated with finally selected codevectors, the indications having lengths that are variable and on average shorter than lengths of the finally selected codevectors; i) serially transmitting the stored indications at a substantially fixed data rate; and, j) automatically adjusting the threshold value based upon a condition of the stored indications only either (1) between image frames or (2) within image frames to ensure that storage and subsequent transmission of the indications does not result in an empty or overflow storage condition as a result of storing variable length indications and transmitting the same at a fixed data rate.

Claim 66

In a cable television system, a method of communicating temporally spaced image frames representing moving images to be displayed on a subscriber set, each image frame comprising a matrix of pixels and each pixel within each image frame having at least an associated intensity value, the method comprising the steps of: a) digitizing the intensity values for the pixels within each image frame and formatting the digital intensity values corresponding to a rectangular block of pixels within the image frame to a multi-dimensional input vector; b) processing the input vector; c) providing, in a memory located at a transmitter location of cable television signals, a first tree-search vector quantization codebook having plural levels of codevectors each representative of a possible processed vector for converting each processed vector to a memory address associated with each codevector, the codevectors at each successive level representing possible processed vectors in greater detail than codevectors at a preceding level; d) selecting an initial level in the codebook; e) comparing each processed vector to the codevectors at the selected level and selecting the codevector at the selected level that most closely resembles the processed vector; f) calculating a measure of difference, if any, between the selected codevector and the processed vector, and comparing the measure of difference to a threshold value; g) selecting the next level in the codebook if the measure of difference exceeds the threshold value and repeating steps (e) and (f) until either (1) the measure of difference does not exceed the threshold value, or (2) a last level of the codebook has been reached, to obtain a finally selected codevector; h) temporarily storing indications of at least addresses associated with finally selected codevectors, the indications having lengths that are variable and on average shorter than lengths of the finally selected codevectors; i) serially transmitting the stored indications at a substantially fixed data rate; and, j) automatically adjusting the threshold value based upon a condition of the stored indications only either (1) between image frames or (2) within image frames to ensure that storage and subsequent transmission of the indications does not result in an empty or overflow storage condition as a result of storing variable length indications and transmitting the same at a fixed data rate.

Claim 67

Method according to claim 61 wherein the indications are transmitted to a plurality of cable television subscribers, further comprising the steps of: k) providing a second tree search vector quantization codebook at a locale of each cable television subscriber, each second codebook having a structure and content, including codevectors, substantially identical to that of the first codebook; l) receiving each transmitted indication at the locale of each cable television subscriber, obtaining the address therefrom, and retrieving from the second codebook the codevector residing at the obtained address to reproduce at least a substantial representation of the finally selected codevector; m) employing each reproduced finally selected codevector to substantially re-create each image frame at the locale of each cable television subscriber and display each re-created image frame on a television set of each cable television subscriber.

Claim 68

Method according to claim 62 wherein step (b) comprises determining a mean value of each input vector and removing the mean value from each input vector to obtain a residual vector, and the residual vector is employed in carrying out steps (e) and (f), and step (i) further comprises transmitting an indication of the mean value.

Claim 69

Method according to claim 63 wherein the reproduced finally selected codevector is a reproduced residual vector and step (1) further comprises receiving the transmitted indication of the mean value and combining the received indication of mean value and reproduced residual vector to substantially reproduce a representation of the input vector.

Claim 70

Method according to claim 61 wherein the images are color images and each pixel further has associated color data, and step (a) further comprises digitizing the color data for the pixels within each image frame and formatting the digital color data corresponding to the rectangular block of pixels within the image frame to another multi-dimensional input vector.

Claim 71

Method according to claim 61 wherein the memory addresses have a variable length wherein the length increases with each successive level of codevectors, the transmitted indication identifying the variable length address of a finally selected codevector and the level of the finally selected codevector.

Claim 72

Method according to claim 61 wherein a compression code is assigned to each possible address, each compression code having a length that is substantially inversely proportional to a predetermined probability that a particular codevector will be finally selected, the transmitted indication comprising the compression code for the address associated with the finally selected codevector.

Claim 73

Method according to claim 61 wherein the step (h) comprises temporarily storing the indications in a buffer and maintaining a measure of unused buffer capacity, and wherein the condition of the stored indications employed to adjust the threshold value is the measure of unused buffer capacity.

Claim 74

Data compression apparatus comprising: a) first means for receiving a multi-dimensional vector representative of a block of data to be compressed; b) a tree search vector quantization codebook having plural levels of codevectors, each codevector being representative of a possible vector and the codevectors at each successive level representing possible vectors in greater detail than codevectors at a preceding level, each codevector having a unique address associated therewith; c) a controller for selecting one of the codevectors in the codebook based upon the vector and a measure of difference between the vector and a threshold value; and, d) second means for transmitting data indicative of the address of the selected codevector.

Claim 75

Data compression apparatus comprising: a) first means for receiving a multi-dimensional vector representative of a block of data to be compressed; b) a tree search vector quantization codebook having plural levels of codevectors, each codevector being representative of a possible vector and the codevectors at each successive level representing possible vectors in greater detail than codevectors at a preceding level, each codevector having a unique address associated therewith; c) a controller for selecting one of the codevectors in the codebook based upon the vector and a measure of difference between the vector and a threshold value; and, d) second means for transmitting data indicative of the address of the selected codevector.

Claim 76

Apparatus according to claim 69 further comprising third means for temporarily storing data to be transmitted and for periodically adjusting the threshold value based upon a measure of unused capacity of the third means.

Claim 77

Apparatus according to claim 69 further comprising calculator means for determining a mean value of the vector and for removing the mean value from the vector to obtain a residual vector, the controller employing the residual vector to select the codevector, the second means further transmitting data indicative of the mean value.

Claim 78

Apparatus according to claim 70 further comprising a lossless compression encoder for assigning a compression code to the address of the selected codevector, the compression code having a length that is substantially inversely proportional to a probability that the selected address would actually be selected, the transmitted data comprising the compression code.

Claim 79

Apparatus according to claim 70 further comprising a feedback loop coupling the third means to the controller for supplying the threshold value.

Claim 80

Apparatus according to claim 70 wherein the data indicative of the selected address has variable length and wherein the third means comprises a first-in first-out (FIFO) buffer and further wherein the data indicative of the selected address is transmitted from an output of the FIFO at a fixed data rate.

Claim 81

Apparatus according to claim 69 wherein the data compression apparatus is embodied as a portion of a pay television encoder.

Claim 82

A decoder for use by subscribers of a pay television system employing, at an encoding site, a tree search vector quantization data compressor for compressing digital data indicative of at least intensity values of pixels of images to be transmitted to the subscribers by converting input vectors indicative of a block of pixels to addresses of a first codebook in the compressor, the first codebook having plural levels of codevectors representative of possible input vectors and each successive level representing codevectors with a greater accuracy than a preceding level of codevectors, the encoding site transmitting data indicative of addresses of codevectors found to most closely approximate input vectors, the decoder comprising: a) a second codebook being substantially identical in content to the first codebook; b) first means for receiving the transmitted data and for providing the received data in a form suitable for addressing the second codebook at an output thereof; c) second means for selecting codevectors from the second codebook based upon the output of the first means; and, d) third means for converting the selected codevectors to NTSC image data and for providing the NTSC image data at an output thereof for substantially reproducing an image input to the encoding site.

Claim 83

A decoder for use by subscribers of a pay television system employing, at an encoding site, a tree search vector quantization data compressor for compressing digital data indicative of at least intensity values of pixels of images to be transmitted to the subscribers by converting input vectors indicative of a block of pixels to addresses of a first codebook in the compressor, the first codebook having plural levels of codevectors representative of possible input vectors and each successive level representing codevectors with a greater accuracy than a preceding level of codevectors, the encoding site transmitting data indicative of addresses of codevectors found to most closely approximate input vectors, the decoder comprising: a) a second codebook being substantially identical in content to the first codebook; b) first means for receiving the transmitted data and for providing the received data in a form suitable for addressing the second codebook at an output thereof; c) second means for selecting codevectors from the second codebook based upon the output of the first means; and, d) third means for converting the selected codevectors to NTSC image data and for providing the NTSC image data at an output thereof for substantially reproducing an image input to the encoding site.

Claim 84

Method according to claim 1, 11, 31, 52 or 61 wherein the codevectors 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.

Claim 85

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

Claim 86

Method according to claim 11 or 31 wherein the input data comprises image frames and the indications are transmitted at a substantially fixed rate, further comprising the step of selecting a value for the threshold that causes a predetermined number of image frames to produce just a sufficient number of indications to yield the fixed rate over the predetermined number of frames.

Claim 87

Method according to claim 52 wherein the image data is in the form of image frames, further comprising the step of selecting a value for the threshold that causes a predetermined number of image frames to produce just a sufficient amount of compressed data to yield the fixed rate over the predetermined number of frames.

Claim 88

Method according to claim 61 further comprising the step of selecting a value for the threshold that causes a predetermined number of image frames to produce just a sufficient number of indications to yield the fixed rate over the predetermined number of frames.

Claim 89

Apparatus according to claim 69 wherein the input data comprises image frames and the indications are transmitted via the second means at a substantially fixed rate and wherein the threshold value has a magnitude that causes a predetermined number of image frames to produce just a sufficient number of indications to yield the fixed rate over the predetermined number of frames.