Frame or sub-frame rate adaptive vector quantizer for moving images

• US 5,068,723 A
• Filed: 07/24/1990
• Issued: 11/26/1991
• Est. Priority Date: 05/19/1989
• Status: Expired due to Term

• Current Assignee: GTE Laboratories Incorporated (Lumen Technologies, Inc.)
• Original Assignee: GTE Laboratories Incorporated (Lumen Technologies, Inc.)
• Inventors: Feng, Yushu, Dixit, Sudhir S.
• Primary Examiner(s): Peng, John K.
• Application Number:
  US07/557,268
• Time in Patent Office: 490 Days
• Field of Search: 358/133, 358/135, 358/136, 358/105, 375/122
• US Class Current: 348/420.1
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 21/236 Assembling of a multiplex stream, e.g. transport stream, by combining a video stream with other content or additional data, e.g. inserting a URL [Uniform Resource Locator] into a video stream, multiplexing software data into a video stream; Remultiplexing of multiplex streams; Insertion of stuffing bits into the multiplex stream, e.g. to obtain a constant bit-rate; Assembling of a packetised elementary stream multiplexing of data packets for data networks, e.g. RTP/UDP H04L65/00
• CPC Class Codes: H04N 21/434 Disassembling of a multiplex stream, e.g. demultiplexing audio and video streams, extraction of additional data from a video stream; Remultiplexing of multiplex streams; Extraction or processing of SI; Disassembling of packetised elementary stream demultiplexing of data packets for data networks, e.g. RTP/UDP H04L65/00

Abstract

An adaptive vector quantization scheme suitable for packet video adapts to the varying characteristics of the actual images sequence being compressed. A large code book is divided into two sections, having higher and lower priority, representing common characteristics and specific characteristics of images. Each new image to be coded is first compared to the common characteristics section of the code book. If a match of acceptable quality is not found, then it is compared to the specific characteristics section. The best match of the two sections is utilized. Entries in the two sections are reorganized and/or exchanged as a function of the usage of the code vectors therein. The rate and extent of adaptation is dictated by the update interval and the desired level of quality, respectively, without requiring any transmission of the vectors themselves or the side information.

Claims

1. A method of compressing and reconstructing a sequence of image signals by adaptive vector quantization comprising the steps of:

constructing a code book having a plurality of addressable entries representing combinations of elements which have appeared frequently in previously coded images;

dividing said code book into two sections, wherein a first of said sections contains addressable entries for common characteristics of a large plurality of images, has a higher priority than a second section;

a second of said sections contains addressable entries for specific characteristics of a sequence of images, having less frequently occurring vectors and having a lower priority;

said first section containing vectors having the highest probability of occurrence;

storing said code book such that it may be used for both compression and reconstruction of the same image signals;

each of said sections being initialized to predefined sizes and states at the beginning of each coding process;

selecting a quality index which is a function of squared error distortion;

dividing each newly arriving image into blocks having N×

N picture elements;

comparing each block of each newly arriving image in said sequence with entries in said first section of said code book to find a best match vector based on a distance measure;

computing a first quality measure for said block;

if said first quality measure is smaller or equal to said quality index, sending the address of said best matching vector to a receiver;

if said first quality measure is larger than said quality index, searching for a best matching vector in said second section of said code book;

computing a second quality measure for said matching vector in said second section;

if said second quality measure is larger than said first quality measure, then sending the address of said best matched vector of said first section;

else

sending a special flag followed by the address of said best matched vector in said second section;

maintaining a record of frequency of usage of each vector in each section of said code book;

incrementing usage records for matched vectors in said first and second sections; and

periodically reordering said code book by swapping code vectors between said sections so that the most frequently used vectors appear in said first section.

2. The method of claim 1 wherein said quality index comprises:

a user selectable quality index K, such that ##EQU3## wherein x_i is the i^th component of the actual image vector, y_i is the i^th component of a vector in the code table, D is the Euclidean distance between vectors x_i and y_i, and N is the dimension of the vectors.

3. The method of claim 1 wherein said maintaining a record of frequency of usage comprises:

providing a set of counters, one for each vector in said code book;

initializing said counters at the start of a coding process by assigning high count values to vector counters in said first section; and

clearing to zero vector counters in said second section;

thereby biasing the ordering of common characteristic vectors to said first section to avoid reordering solely in response to transient characteristics.

4. A method of compressing and reconstructing image signals by vector quantization, comprising the steps of:

selecting a quality index representing the maximum distortion acceptable for a reconstructed image;

dividing two-dimensional image signals to be compressed into blocks, each block comprising a fixed number of elements;

selecting a first vector which best matches but does not exceed a maximum distortion quality index to a set of image signals in each of said blocks from a first section of a code book comprising a plurality of vectors, said code book having been prepared in advance by defining a fixed number of vector elements representing common characteristics of images previously analyzed with a high probability of occurrence;

if a match is found;

sending the address of said selected first matching vector to a receiver for reconstruction of said image using vectors from a copy of said code book;

if a match is not found;

selecting a second vector which best matches the set of image signals in each of said blocks from a second section of said code book comprising a plurality of vectors representing specific characteristics of sequences of images having a low probability of occurrence;

comparing said second matching vector with said first matching vector;

if said second matching vector has a distortion greater than that of said first matching vector, then;

sending the address of said first matching vector to receiver;

if said second matching vector has a distortion less than said first matching vector, then;

sending the address of said second matching vector to said receiver;

incrementing a counter associated with each vector address transmitted to a receiver;

comparing the values of said counters for all vectors in said first and second sections; and

interchanging periodically vectors from said first and second sections so that vectors in said first section are those most frequently accessed and those in said second section are accessed less frequently.

5. The method of claim 4 wherein said quality index comprises:

a user selectable quality index K, such that ##EQU4## wherein x_i is the i^th component of the actual image vector, y_i is the i^th component of a vector in the code table, D is the Euclidean distance between vectors x_i and y_i, and N is the dimension of the vectors.

6. The method of claim 5 further comprises:

maintaining a record of frequency of usage, comprising the steps of

providing a set of counters, one for each vector in said code book;

initializing said counters at the start of a coding process by assigning high count values to vector counters in said first section; and

clearing to zero vector counters in said second section;

thereby biasing the ordering of common characteristic vectors to said first section to avoid reordering solely in response to transient characteristics.

7. A system for compressing sequences of moving images at a transmitter for transmission over a network and for reconstructing said images at a receiver, comprising:

a code book prepared in advance having two sections;

a first section of said code book comprising a limited number of vectors representing common characteristics of an ensemble of images, said characteristics having a high probability of occurring frequently;

a second section of said code book comprising a greater number of vectors representing specific characteristics of sequences of images, said specific characteristics occurring less frequently than said common characteristics;

identical copies of said code book being stored in said transmitter and in said receiver;

means to initialize said code book prior to processing a sequence of images;

means to select a quality index wherein said quality index specifies the maximum acceptable distortion in a reconstructed image;

means to divide each incoming image into blocks of image pixels;

means to derive a new vector for each of said blocks;

means to compare said new vector with stored vectors in said first section of said code book to find a first matching vector which best matches said new vector;

means to compute a quality measure for said first matching vector;

if said quality measure for said first matching vector indicates less distortion than said quality index, then a transmission means transmits the address of said first matching vector to said receiver as a compressed image block;

if not, then means to compare said new vector with stored vectors in said second section of said code book to find a second vector which best matches said new vector;

means to compute a quality measure for said second matching vector;

means to compare the quality measure of said second matching vector with the quality measure of said first matching vector;

if the quality measure of said second matching vector indicates a distortion greater than that of said first matching vector, then;

sending the address of said first matching vector to receiver as a compressed image block;

if said second matching vector indicates a distortion less than that of said first matching vector, then;

sending the address of said second matching vector to said receiver as a compressed image block;

means to retrieve vectors having said transmitter addresses at said receiver and to reconstruct an image corresponding to an original image before compression;

means for incrementing a counter associated with each vector address transmitted to a receiver;

means for comparing the values of said counters for all vectors in said first and second sections; and

means for interchanging periodically vectors from said first and second sections so that vectors in said first section are those most frequently accessed and those in said second section are accessed less frequently.

8. The system of claim 7 wherein said quality index comprises:

a user selectable quality index K, such that ##EQU5## wherein x_i is the i^th component of the actual image vector, y_i is the i^th component of a vector in the code table, D is the Euclidean distance between vectors x_i and y_i, and N is the dimension of the vectors.

9. The system of claim 7 further comprises:

means for maintaining a record of frequency of usage, comprising

means for providing a set of counters, one for each vector in said code book;

means for initializing said counters at the start of a coding process by assigning high count values to vector counters in said first section, and clearing to zero vector counters in said second section;

thereby biasing the ordering of common characteristic vectors to said first section to avoid reordering solely in response to transient characteristics.