Multimedia compression system with adaptive block sizes

• US 6,233,017 B1
• Filed: 06/30/1997
• Issued: 05/15/2001
• Est. Priority Date: 09/16/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaddha, Navin
• Primary Examiner(s): BRITTON, HOWARD W
• Application Number:
  US08/885,011
• Time in Patent Office: 1,415 Days
• Field of Search: 348/420, 348/409, 348/412, 348/414, 348/415, 348/417
• US Class Current: 375/240.12
• CPC Class Codes: H04N 19/507 using conditional replenishment
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 21/234327 by decomposing into layers, e.g. base layer and one or more enhancement layers
• CPC Class Codes: H04N 21/234363 by altering the spatial resolution, e.g. for clients with a lower screen resolution
• CPC Class Codes: H04N 21/234381 by altering the temporal resolution, e.g. decreasing the frame rate by frame skipping
• CPC Class Codes: H04N 21/2402 Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• CPC Class Codes: H04N 21/25808 Management of client data terminal profiles in network data switching protocols H04L67/303
• CPC Class Codes: H04N 21/2662 Controlling the complexity of the video stream, e.g. by scaling the resolution or bitrate of the video stream based on the client capabilities
• CPC Class Codes: H04N 21/440227 by decomposing into layers, e.g. base layer and one or more enhancement layers
• CPC Class Codes: H04N 21/4621 Controlling the complexity of the content stream or additional data, e.g. lowering the resolution or bit-rate of the video stream for a mobile client with a small screen arrangements for using the results of monitoring on user's side in broadcast systems H04H60/65; flow control in packet networks H04L47/10
• CPC Class Codes: H04N 21/6405 Multicasting data broadcast and multicast in packet switching networks H04L12/18

Abstract

A multimedia compression system for generating frame rate scalable data in the case of video, and, more generally, universally scalable data. Universally scalable data is scalable across all of the relevant characteristics of the data. In the case of video, these characteristics include frame rate, resolution, and quality. The scalable data generated by the compression system is comprised of multiple additive layers for each characteristic across which the data is scalable. In the case of video, the frame rate layers are additive temporal layers, the resolution layers are additive base and enhancement layers, and the quality layers are additive index planes of embedded codes. Various techniques can be used for generating each of these layers (e.g., Laplacian pyramid decomposition or wavelet decomposition for generating the resolution layers; tree structured vector quantization or tree structured scalar quantization for generating the quality layers). The compression system further provides for embedded inter-frame compression in the context of frame rate scalability, and non-redundant layered multicast network delivery of the scalable data.

Claims

1. A method for encoding a motion video image which includes two or more frames, the method comprising performing the following steps for each subject one of one or more of the frames to encode the subject frame to form an encoded frame:

(i) selecting a temporally displaced one of the frames other than the subject frame;

(ii) selecting one or more blocks of the subject frame;

(iii) for each of the blocks of the subject frame,

(a) forming a motion compensated block of the block with reference to a corresponding block of the temporally displaced frame;

(b) measuring a block distortion between the block and the motion compensated block;

(c) measuring a block rate of the motion compensated block in terms of an amount of data required to represent the motion compensated block;

(d) for each of two or more sub-blocks of the block, performing the following steps;

(1) forming a motion compensated sub-block with reference to a corresponding sub-block of the temporally displaced frame;

(2) measuring a sub-block distortion between the sub-block and the motion compensated sub-block; and

(3) measuring a sub-block rate of the motion compensated sub-block in terms of an amount of data required to represent the motion compensated sub-block;

(e) constructing a composite sub-block distortion from the sub-block distortions;

(f) constructing a composite sub-block rate from the sub-block rates;

(g) measuring a relative distortion between the block distortion and the composite sub-block distortion;

(h) measuring a relative rate between the block rate and the composite sub-block rate;

(i) comparing the relative distortion to the relative weight according to a predetermined ratio of distortion and rate priorities to determine whether the motion compensated block or the motion compensated sub-blocks provide a better combination of distortion and rate;

(j) including the motion compensated block in the encoded frame if the motion compensated block provides a better combination of distortion and rate as determined in the step of comparing; and

(k) including the motion compensated sub-blocks in the encoded frame if the motion compensated sub-blocks provide a better combination of distortion and rate as determined in the step of comparing.

2. The method of claim 1 further comprising performing the following steps for each subject one of the sub-blocks:

(l) for each of two or more sub-sub-blocks of the sub-block, performing the following steps;

(1) forming a motion compensated sub-sub-block with reference to a corresponding sub-sub-block of the temporally displaced frame;

(2) measuring a sub-sub-block distortion between the sub-sub-block and the motion compensated sub-sub-block; and

(3) measuring a sub-sub-block rate of the motion compensated sub-sub-block in terms of an amount of data required to represent the motion compensated sub-sub-block;

(m) constructing a composite sub-sub-block distortion from the sub-sub-block distortions;

(n) constructing a composite sub-sub-block rate from the sub-sub-block rates;

(o) measuring a sub-block relative distortion between the sub-block distortion of the subject sub-block and the composite sub-sub-block distortion;

(p) measuring a sub-block relative rate between the sub-block rate of the subject sub-block and the composite sub-sub-block rate;

(q) comparing the sub-block relative distortion to the sub-block relative weight according to the predetermined ratio of distortion and rate priorities to determine whether the motion compensated sub-block or the motion compensated sub-sub-blocks provide a better combination of distortion and rate;

(s) including the motion compensated sub-block in the encoded frame if the motion compensated sub-block provides a better combination of distortion and rate as determined in step (q); and

(t) including the motion compensated sub-sub-blocks in the encoded frame if the motion compensated sub-sub-blocks provide a better combination of distortion and rate as determined in step (q).

3. A computer readable medium useful in association with a computer which includes a processor and a memory, the computer readable medium including computer instructions which are configured to cause the computer to encode a motion video image which includes two or more frames by performing the following steps for each subject one of one or more of the frames to encode the subject frame to form an encoded frame:

(i) selecting a temporally displaced one of the frames other than the subject frame;

(ii) selecting one or more blocks of the subject frame;

(iii) for each of the blocks of the subject frame,

(a) forming a motion compensated block of the block with reference to a corresponding block of the temporally displaced frame;

(b) measuring a block distortion between the block and the motion compensated block;

(c) measuring a block rate of the motion compensated block in terms of an amount of data required to represent the motion compensated block;

(d) for each of two or more sub-blocks of the block, performing the following steps;

(1) forming a motion compensated sub-block with reference to a corresponding sub-block of the temporally displaced frame;

(2) measuring a sub-block distortion between the sub-block and the motion compensated sub-block; and

(3) measuring a sub-block rate of the motion compensated sub-block in terms of an amount of data required to represent the motion compensated sub-block;

(e) constructing a composite sub-block distortion from the sub-block distortions;

(f) constructing a composite sub-block rate from the sub-block rates;

(g) measuring a relative distortion between the block distortion and the composite sub-block distortion;

(h) measuring a relative rate between the block rate and the composite sub-block rate;

(i) comparing the relative distortion to the relative weight according to a predetermined ratio of distortion and rate priorities to determine whether the motion compensated block or the motion compensated sub-blocks provide a better combination of distortion and rate;

(j) including the motion compensated block in the encoded frame if the motion compensated block provides a better combination of distortion and rate as determined in the step of comparing; and

(k) including the motion compensated sub-blocks in the encoded frame if the motion compensated sub-blocks provide a better combination of distortion and rate as determined in the step of comparing.

4. The computer readable medium of claim 3 wherein the computer instructions are further configured to cause the computer to cause the computer to perform the following steps for each subject one of the sub-blocks:

(l) for each of two or more sub-sub-blocks of the sub-block, performing the following steps;

(1) forming a motion compensated sub-sub-block with reference to a corresponding sub-sub-block of the temporally displaced frame;

(2) measuring a sub-sub-block distortion between the sub-sub-block and the motion compensated sub-sub-block; and

(3) measuring a sub-sub-block rate of the motion compensated sub-sub-block in terms of an amount of data required to represent the motion compensated sub-sub-block;

(m) constructing a composite sub-sub-block distortion from the sub-sub-block distortions;

(n) constructing a composite sub-sub-block rate from the sub-sub-block rates;

(o) measuring a sub-block relative distortion between the sub-block distortion of the subject sub-block and the composite sub-sub-block distortion;

(p) measuring a sub-block relative rate between the sub-block rate of the subject sub-block and the composite sub-sub-block rate;

(q) comparing the sub-block relative distortion to the sub-block relative weight according to the predetermined ratio of distortion and rate priorities to determine whether the motion compensated sub-block or the motion compensated sub-sub-blocks provide a better combination of distortion and rate;

(s) including the motion compensated sub-block in the encoded frame if the motion compensated sub-block provides a better combination of distortion and rate as determined in step (q); and

(t) including the motion compensated sub-sub-blocks in the encoded frame if the motion compensated sub-sub-blocks provide a better combination of distortion and rate as determined in step (q).

5. A computer system comprising:

a processor;

a memory operatively coupled to the processor; and

a motion video signal encoder which executes in the processor from the memory and which, when executed by the processor, encodes a motion video image which includes two or more frames by performing the following steps for each subject one of one or more of the frames to encode the subject frame to form an encoded frame;

(i) selecting a temporally displaced one of the frames other than the subject frame;

(ii) selecting one or more blocks of the subject frame;

(iii) for each of the blocks of the subject frame,

(a) forming a motion compensated block of the block with reference to a corresponding block of the temporally displaced frame;

(b) measuring a block distortion between the block and the motion compensated block;

(c) measuring a block rate of the motion compensated block in terms of an amount of data required to represent the motion compensated block;

(d) for each of two or more sub-blocks of the block, performing the following steps;

(1) forming a motion compensated sub-block with reference to a corresponding sub-block of the temporally displaced frame;

(2) measuring a sub-block distortion between the sub-block and the motion compensated sub-block; and

(3) measuring a sub-block rate of the motion compensated sub-block in terms of an amount of data required to represent the motion compensated sub-block;

(e) constructing a composite sub-block distortion from the sub-block distortions;

(f) constructing a composite sub-block rate from the sub-block rates;

(g) measuring a relative distortion between the block distortion and the composite sub-block distortion;

(h) measuring a relative rate between the block rate and the composite sub-block rate;

(i) comparing the relative distortion to the relative weight according to a predetermined ratio of distortion and rate priorities to determine whether the motion compensated block or the motion compensated sub-blocks provide a better combination of distortion and rate;

(j) including the motion compensated block in the encoded frame if the motion compensated block provides a better combination of distortion and rate as determined in the step of comparing; and

(k) including the motion compensated sub-blocks in the encoded frame if the motion compensated sub-blocks provide a better combination of distortion and rate as determined in the step of comparing.

6. The computer system of claim 5 wherein the motion video signal encoder, when executed by the processor, further performs the following steps for each subject one of the sub-blocks:

(l) for each of two or more sub-sub-blocks of the sub-block, performing the following steps;

(1) forming a motion compensated sub-sub-block with reference to a corresponding sub-sub-block of the temporally displaced frame;

(2) measuring a sub-sub-block distortion between the sub-sub-block and the motion compensated sub-sub-block; and

(3) measuring a sub-sub-block rate of the motion compensated sub-sub-block in terms of an amount of data required to represent the motion compensated sub-sub-block;

(m) constructing a composite sub-sub-block distortion from the sub-sub-block distortions;

(n) constructing a composite sub-sub-block rate from the sub-sub-block rates;

(o) measuring a sub-block relative distortion between the sub-block distortion of the subject sub-block and the composite sub-sub-block distortion;

(p) measuring a sub-block relative rate between the sub-block rate of the subject sub-block and the composite sub-sub-block rate;

(q) comparing the sub-block relative distortion to the sub-block relative weight according to the predetermined ratio of distortion and rate priorities to determine whether the motion compensated sub-block or the motion compensated sub-sub-blocks provide a better combination of distortion and rate;

(s) including the motion compensated sub-block in the encoded frame if the motion compensated sub-block provides a better combination of distortion and rate as determined in step (q); and

(t) including the motion compensated sub-sub-blocks in the encoded frame if the motion compensated sub-sub-blocks provide a better combination of distortion and rate as determined in step (q).