Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1996-06-21
2001-09-18
Chang, Jon (Department: 2623)
Image analysis
Image compression or coding
Adaptive coding
C382S250000, C382S251000, C382S238000, C348S416100
Reexamination Certificate
active
06292589
ABSTRACT:
FIELD OF THE INVENTION
This invention relates in general to video compression and more particularly to determination of quantization values used during compression of video images.
BACKGROUND OF THE INVENTION
With the convergence of computers, communications and media, video compression techniques have become increasingly important. Video compression is typically used to translate video images (from camera, VCR, laser discs, etc.) into digitally encoded frames. The digitally encoded frames may then be easily transferred over a network, or stored in a memory. When desired, the compressed images may then be decompressed for viewing on a computer monitor or other such device.
The three most common video compression standards are MPEG (Moving Picture Experts Group), Motion-JPEG (Joint Photographic Experts Group), and H.261. These standards partition incoming frames into small tiles and perform either spatial or temporal compression on the tiles. Spatial compression involves removing redundant data in the horizontal and vertical picture dimensions; i.e. data within a frame that is similar in picture areas which are close to each other. Temporal compression involves removing redundant data occurring over a given time; i.e. data that repeats from frame to frame. The amount of each type of compression which may be performed on each frame depends on several factors: frame type (discussed below), image classification (e.g., smooth, texture, edge), and resources (number of available resultant bits). Each standard has a defined order of incoming frames.
Encoded frames are classified as either Intra-coded (I-frames), Predictive frames (P-frames), or Bi-directional frames (B-frames). An ‘I’ frame is an frame in which spatial redundancies are removed using spatial compression techniques. A ‘P’ frame is a frame in which temporal redundancies have been removed by matching tiles through motion estimation in the current frame to a previous reference frame, then spatially compressing the temporal difference coefficients. A ‘B’ frame is a frame in which temporal redundancies are removed by matching tiles in the current frame to a previous and a future reference frame, then compressing the difference coefficients with the spatial transform.
To perform spatial compression alone, such as in the ‘I’ frame, only the individual frame is required for the compression. However, to perform the temporal compressions, which are required for both the ‘P’ and ‘B’ frames, the compression of other frames must first be performed. Each ‘P’ frame is encoded based on the previous ‘I’ or ‘P’ reference frame. Encoding of ‘B’ frames require the results of both past and future frame calculations, thus the processing of the B frame is an out-of order function, in which future reference frames must be analyzed prior to the intervening B frames.
Two recognized forms of video compression techniques are real-time compression and high-quality n-pass compression, where n>1. Each form has known advantages. Real-time video compression only spatial compression techniques (I frames) to allow images to be compressed at the rate at which they are input. Thus real-time compression processes require less buffering of the input image and consequently less hardware complexity.
To provide real-time compression, a ‘peephole’ approach is typically implemented whereby each tile in each frame is encoded as it is processed. One drawback of this scheme arises from the fact that only a fixed number of bits are allocated for encoding a frame. If bits are used to encode portions of the frame as they are received, bits may be ‘used up’ encoding low priority components of the tile, leaving fewer bits available for encoding higher priority blocks which may appear later in the frame.
Two-pass compression alleviates the above encoding problem by processing each frame in two steps. First, each frame undergoes a Motion Estimation (ME) calculation. During the ME phase, for P and B frames, the possible motion of each macroblock in the frame is characterized relative to a past and/or future reference frame as described above. In addition, for I, P and B frames, energy statistics are generated for the frame to profile the visual complexity of the frame. Providing energy statistics allows for allocation of bits for encoding purposes throughout the frame.
Compression of video images includes quantizing the energy coefficients such that a large range of data may be represented by a smaller discrete number of values. Judicious choice of quantization values is critical to achieving a balance between achieved compression and image quality after decompression. Assigning quantization values to every macroblock of an image may result in poor image quality since a single formula can not take into account the relative importance of particular macroblocks to the human visual system. It would be advantageous therefore to provide a method which assigns a quantization value during compression which affords the highest level of compression while taking into consideration the relative importance of the macroblocks within an image.
SUMMARY OF THE INVENTION
In accordance with one aspect of the present invention, a method for choosing quantization values used during compression of image data includes the step of constructing a non-parametric model of relationships between required bit resource for compression, image characteristics, and quantization values for a plurality of sample images. The contents of a macroblock are characterized as being one of a plurality of image types. The characterization may be represented as a scalar value. Once characterized, a subset of the bit resources associated with the entire image are allocated to the macroblock. Once characterized, the non-parametric model receives the associated characterization and bit resource allocation for the particular macroblock. The model is then searched to find a match between the input characterization and resource allocation with a stored characterization and resource allocation. A quantization value stored with the associated matching characterization and resource allocation values is then assigned to the macroblock from the model.
With such an arrangement, quantization values may be assigned during a compression scheme which are based on learned relationships between images and their various visual characteristics. This provides a more accurate method of assigning quantization levels as the model is not represented as a formula indiscreetly applied to each part of an image regardless of the image characteristics.
In accordance with a further aspect of the present invention, a method of providing quantization values for use in during compression of images includes the above mentioned non-parametric model and is further able to adapt to incoming image data to provide for efficient use of available coding resources. The method includes compressing, using the assigned quantization values, a macroblock such that a resultant compressed macroblock is represented by a subset of bits used to represent said macroblock. Then the quantization assigning and compression steps are performed for several macroblocks or even the entire frame. Once done, the total number of resultant bits (due to compression) for the macroblocks or frame are totalled and compared the number of bits allocated to the several macroblocks or frame. Based on the comparison, future frames or macroblocks will have their bit allocations scaled up or down depending on the whether there was a surplus or deficiency of bits as a result of the compression. With such an arrangement, all of the allocated bits will be used resulting in a high quality of compression and resulting image upon decompression.
REFERENCES:
patent: 4984076 (1991-01-01), Watanabe
patent: 5067015 (1991-11-01), Combridge et al.
patent: 5136377 (1992-08-01), Johnston
patent: 5231484 (1993-07-01), Gonzalez
patent: 5323187 (1994-06-01), Park
patent: 5440344 (1995-08-01), Asamura et al.
patent: 5530478 (1996-06-01), Sasaki
patent: 5956426 (1999-09-01), Matsuura et al.
Chow King-Wai
Rose Robert C.
Chang Jon
Compaq Computer Corporation
Hamilton Brook Smith & Reynolds P.C.
LandOfFree
Method for choosing rate control parameters in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for choosing rate control parameters in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for choosing rate control parameters in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2444158