Adaptive spatio-temporal compression/decompression of video image signals

• US 5,228,098 A
• Filed: 06/14/1991
• Issued: 07/13/1993
• Est. Priority Date: 06/14/1991
• Status: Expired due to Term

• Current Assignee: American Video Graphics LP
• Original Assignee: Tektronix Incorporated (Fortive Corp.)
• Inventors: Crinon, Regis J., Luthra, Ajay, Edwards, Stanley C., May, Peter M.
• Primary Examiner(s): Razavi, Michael T.
• Assistant Examiner(s): COUSO, YON JUNG
• Application Number:
  US07/715,288
• Time in Patent Office: 760 Days
• Field of Search: 382/56, 382/37, 358/133, 358/433, 358/261.3, 358/136
• US Class Current: 382/240
• CPC Class Codes: G06T 9/40 Tree coding, e.g. quadtree, octree
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/507 using conditional replenishment
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding
• CPC Class Codes: H04N 19/98 Adaptive-dynamic-range coding [ADRC]

Abstract

An adaptive spatio-temporal compression/decompression algorithm for a video image uses a quadtree hierarchy to represent each frame of the image, the quadtree hierarchy including intermediary nodes and leaves. For each leaf a temporal bit is added indicative of whether a significant intensity change occurred between two frames of the video image. If the temporal bit indicates the significant intensity change occurred between frames, then a new intensity value also is added to that leaf. A decoder using a state machine extracts from the resulting compressed data stream a start address, a block size and the new intensity value for each leaf having the significant intensity change between frames to update a display memory with the new intensity value at each pixel within the area defined by the start address and block size.

Claims

1. A method of adaptive spatio-temporally compressing/decompressing an image defined as an array of picture elements comprises the steps of:

defining blocks of the picture elements as intermediate nodes and leaves according to a spatial quadtree hierarchy until all intermediary nodes are resolved into leaves, each leaf having an associated intensity value;

assigning for each leaf a temporal bit indicative of whether a significant change in the intensity value has occurred between successive frames of the image; and

encoding the intermediary nodes and leaves into a compressed data stream representative of the image having a first bit value for each intermediary node starting from the highest level of the spatial quadtree hierarchy and a second bit value for each leaf, each leaf where the temporal bit indicates the significant change being followed by a plurality of bits representing a new intensity value for that leaf.

2. A method as recited in claim 1 further comprising the step of decoding the compressed data stream by detecting each leaf where the temporal bit indicates the significant change and determining the corresponding range of addresses in a memory for updating the intensity values of the image with the new intensity value.

3. A method as recited in claim 2 wherein the decoding step comprises the steps of:

initializing a decoder algorithm at the beginning of each frame of the image within the compressed data stream;

testing each bit of the compressed data stream in sequence until a bit indicating a leaf is found;

determining from the temporal bit of the leaf whether the new intensity value is present;

specifying a block size indicating the number of pixels in the leaf and an address representing a starting location in the memory for the leaf;

replacing the intensity values for the pixels of the leaf specified by the block size and address with the new intensity value; and

repeating the testing and replacing steps until the image frame is complete.

4. A method as recited in claim 3 wherein the testing step comprises the steps of:

checking the bit from the sequence to determine if it represents an intermediary node;

decreasing the block size by a factor of two when the checked bit represents the intermediary node; and

going on to the determining step when the checked bit represents the leaf.

5. An apparatus for adaptive spatio-temporal compressing/decompressing of an image comprising:

means for converting a signal representing the image into a digital data stream representing intensity values for each pixel of the image;

means for storing a sequential portion of the digital data stream representing a frame of the image;

means for determining temporal difference values for the pixels between two frames of the image;

means for encoding the digital data stream into a compressed data stream as a function of the temporal difference values using a quadtree hierarchy of intermediary nodes and leaves, each leaf including a temporal bit indicative of a significant change in the intensity values for that leaf between the two frames, the compressed data stream having a single bit for each intermediary node of the quadtree of a first value, two bits for each leaf with the first bit being of a second value and the second bit being the temporal bit, and a plurality of bits representing a new intensity value for the leaf after each pair of leaf bits where the temporal bit has a specified value.

6. An apparatus as recited in claim 5 further comprising means for decoding the compressed data stream to update a display memory at those locations representative of a leaf having the new intensity value.

7. An apparatus as recited in claim 6 wherein the decoding means comprises:

means for identifying the leaf having the new intensity value from the compressed data stream;

means for generating a start address for the display memory for the identified leaf;

means for generating a block size from the identified leaf; and

means for extracting the new intensity value from the identified leaf for storage in the display memory in locations determined by the start address and the block size.