Bit allocation for sequence image compression

• US 5,909,513 A
• Filed: 09/13/1996
• Issued: 06/01/1999
• Est. Priority Date: 11/09/1995
• Status: Expired due to Term

• Current Assignee: Utah State University
• Original Assignee: Utah State University
• Inventors: Huang, Chien-Min, Budge, Scott E., Israelsen, Paul D., Liang, Kyminh
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/713,400
• Time in Patent Office: 991 Days
• Field of Search: 382/253, 382/232-233, 382/239-240, 382/250-251, 348/405, 348/414-415, 348/417-419, 348/420-422
• US Class Current: 382/253
• 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 11/042 Codec means
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/19 using optimisation based on Lagrange multipliers
• CPC Class Codes: H04N 19/23 with coding of regions that are present throughout a whole video segment, e.g. sprites, background or mosaic
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/39 involving multiple description coding [MDC], i.e. with separate layers being structured as independently decodable descriptions of input picture data
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream
• CPC Class Codes: H04N 19/587 involving temporal sub-sampling or interpolation, e.g. decimation or subsequent interpolation of pictures in a video sequence
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 7/147 Communication arrangements, e.g. identifying the communication as a video-communication, intermediate storage of the signals selecting H04Q

Abstract

The invention relates to a method and system for allocating bits for representing blocks that are transmitted in an image compression system. In a preferred embodiment, a video telephone communications system includes a video transmitting/receiving (transceiving) system including local and remote processing systems separated by a communications link. The local processing system determines indices to be sent to a remote processing system to represent the image. Under one aspect of the invention, the local processing system determines an optimal bit allocation in which the following relationship may be minimized DR=D+λR, where D is the total distortion Σd_i for a frame; λ is a value determined as described below; R=Σr_i ≈R_d which is the desired total number of bits for the frame. The optimal bit allocation may determine λ for an entire frame. Under other aspects of the invention a lambda feedback technique, with or without predecision, may be used. The lambda feedback techniques may determine λ block by block. Conditional update preselection and mode preselection are other reduced complexity procedures.

Claims

1. An image processing system comprising:

at least one conductor to conduct data to be processed;

local processing circuitry coupled to the at least one conductor to receive and process blocks of the data, to select indices in a compression process to represent each of said blocks of the data and to determine distortion between a first block and a second block of said data, the local processing circuitry being constructed to employ lambda feedback in which distortion associated with at least one previously processed block and the total data size of indices previously selected to represent blocks are used in selecting indices to represent unprocessed blocks; and

output circuitry coupled to the local processing circuitry to output the selected indices.

2. The system of claim 1, wherein the local processing circuitry includes circuitry for determining a lambda (λ

) for each block and for selecting indices for the block according to which indices minimize (d+λ

r), where d is a distortion caused by compression of the block, and r is a bit rate associated with the index representing the block.

3. The system of claim 1, wherein the lambda feedback includes using buffer fullness in selecting indices to represent unprocessed blocks.

4. The system of claim 1, wherein the local processing circuitry is constructed to perform a hierarchical vector quantization in selecting the indices.

5. The system of claim 1, further comprising:

a communications link coupled to the output circuitry; and

remote processing circuitry coupled to the communications link to receive the selected indices and perform a decompression process thereon.

6. The system of claim 1, wherein the local processing circuitry is constructed to select the indices to represent images at a fixed frame rate.

7. The system of claim 1, wherein the local processing circuitry calculates DR=D+λ

R, where D is a distortion for a frame of the group of data and R is approximately equal to a desired bit rate, and DR is computed through an examination of an intra block mode, a motion compensation mode, and a conditional update mode.

8. An image processing system comprising:

local memory storage to store a group of data to be processed;

local processing circuitry coupled to the local memory storage to receive blocks of the group of data and to select indices in a compression process to represent the blocks, the local processing circuitry being constructed to select the indices so that DR=D+λ

R is essentially a minimum, where D is a distortion for an unprocessed block of the group of data and R is approximately equal to a desired bit rate for the block, the local processing circuitry also being constructed to select indices to represent an unprocessed block according to a lambda (λ

) determined in accordance with a distortion associated with the most recently processed block and the total data size of indices previously selected to represent blocks; and

output circuitry coupled to the local processing circuitry to output the selected indices.

9. The system of claim 8, wherein the minimum DR is computed through a hierarchical vector quantization technique.

10. The system of claim 8, wherein the minimum DR is computed through a bisection technique.

11. The system of claim 8, wherein the minimum DR is computed through a parallel bisection technique.

12. The system of claim 8, wherein the minimum DR is computed through an examination of an intra block mode, a motion compensation mode, and a conditional update mode.

13. The system of claim 8, further comprising:

a communications link coupled to the output circuitry; and

remote circuitry coupled to the communications link to interface with the output circuitry.

14. The system of claim 8, wherein the local processing circuitry is constructed to obtain λ

by comprising all the blocks of a frame of the group of data.

15. The system of claim 8, wherein the local processing circuitry includes a microprocessor.

16. The system of claim 8, further comprising:

a communications link coupled to the output circuitry;

remote processing circuitry coupled to the communications link to receive the indices and process the indices; and

a remote display coupled to the remote processing circuitry to produce images in accordance with the processed indices and to simultaneously produce other images.

17. The system of claim 16, wherein the other images are produced as part of a conference call.

18. An image compression process comprising:

receiving a plurality of image blocks; and

for each block,

determining one or more indices suitable for representing said block;

calculating a block distortion d_i and a block bit rate r_i associated with each of the one or more indices;

determining a lambda λ

for said block in accordance with an actual distortion associated with the block preceding said block through the compression process and the total data size of previously compressed blocks; and

selecting an index from among the one or more indices that has the minimum d_i +λ

r_i for said block.

19. The image compression process of claim 18, wherein the act of determining one or more indices suitable for representing said block comprises determining the one or more indices in accordance with at least one of an intra block mode and a motion compensation mode.

20. The image compression process of claim 18, wherein the act of calculating a block distortion d_i comprises calculating an L1 norm distortion.

21. The image compression process of claim 18, further comprising outputting the selected indices through an output buffer, wherein the act of determining a lambda λ

for said block comprises determining the lambda λ

for said block in accordance with an actual distortion fdist associated with the block preceding said block through the compression process and the total data size of data stored in the output buffer.

22. An image compression system comprising:

circuitry for receiving a plurality of image blocks and, for each block, determining one or more indices suitable for representing said block and calculating a block distortion d_i and a block bit rate r_i associated with each of the one or more indices;

circuitry for determining, for each block, a lambda λ

for said block in accordance with an actual distortion associated with the block preceding said block through the compression system and the total data size of previously compressed blocks; and

circuitry coupled to the image block receiving circuitry and the lambda determining circuitry for selecting, for each block, an index from among the one or more indices determined suitable for said block that has the minimum d_i +λ

r_i for said block.

23. The image compression system of claim 22, wherein the image block receiving circuitry includes motion estimation circuitry and vector quantization circuitry.

24. The image compression system of claim 22, further comprising an output buffer coupled to the index selecting circuitry for outputting the selected indices.

25. An image processing system comprising:

circuitry for receiving a plurality of image blocks and, for each block, determining one or more indices suitable for representing said block and calculating a block distortion d_i and a block bit rate r_i associated with each of the one or more indices;

circuitry for determining, for each block, a lambda λ

for said block in accordance with an actual distortion associated with the block preceding said block through the compression system and the total data size of previously compressed blocks;

circuitry coupled to the image block receiving circuitry and the lambda determining circuitry for selecting, for each block, an index from among the one or more indices determined suitable for said block that has the minimum d_i +λ

r_i for said block;

a communications link coupled to the index selecting circuitry for receiving and conducting the selected indices; and

decompression circuitry coupled to the communications link for converting the selected indices to image blocks.