Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
2000-04-19
2004-02-03
Philippe, Gims (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240030, C382S236000, C348S404100
Reexamination Certificate
active
06687304
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a system for encoding digital video data wherein selection of a compression strategy and identification and retrieval of specific elements of the video frame, are efficiently accomplished. The invention has particular utility in connection with digital television decoder design that utilizes the Adaptive Dynamic Range Coding methodology.
2. Description of the Related Art
Adaptive Dynamic Range Coding (ADRC) refers to a coding technique described in U.S. Pat. No. 4,703,352 entitled “High efficiency technique for coding a digital video signal,” to Kondo, the contents of which are hereby incorporated by reference into the subject application as if set forth herein in full. In accordance with this technique, the differences between successive image points are calculated and characterized according to a scale. This scale is then used to select a quantization strategy for the data, the purpose of which is to effect further compression without degrading the image. Quantization discards information which is not visually significant by dividing video data by a quantizer step size appropriate for the range of the data.
The ADRC method segments each frame of a video sequence into many bands as shown in FIG.
1
. Assuming each frame of video consists of 720 columns and 480 lines and the video format is 4:2:0 interlaced, then the Y field is 720×240 and the U,V fields are 360×120. Each frame has 2 fields. Each band occupies four lines of the frame including Y components
22
and, U and V components
26
. Inside each band, the image is further segmented into many blocks 20 which are 4 pixels by 4 pixels or 16 pixels each.
Within each band, each block is encoded using a strategy that depends upon the dynamic range of the block, that is, the difference between the maximum and minimum values of the digital video data representing the picture elements. Blocks with smaller dynamic ranges are encoded with fewer bits, and the converse is also true, some blocks need a greater number of bits. Accordingly, each encoded block has a different bit length. However, following this encoding, the ADRC method also compresses each entire band with a fixed compression ratio. In order to achieve that ratio, all blocks within the same band trade bits with each other, making location of a particular block difficult.
Moreover, using the band as a coding unit adds a level of complexity and difficulty to the real-time decoding process, because motion compensation is based on a predictive technique, that requires being able to locate reference macroblocks within what is termed anchor frames. Using the ADRC method, calculating the location of a macroblock is not straight-forward, given that blocks within a band are not compressed with a fixed bit rate. In some cases, as many as five bands, a very large amount of data, must be searched to locate a particular macroblock. This is time-consuming and affects performance.
In addition, by providing seven different block encoding strategies, the ADRC method introduces further inefficiency. Any given band may require application of all seven encoding/decoding strategies depending on the data. Because data within a band is not compressed with a fixed bit rate, an entire band must be decoded before even a single line can be displayed.
Other patents which use the ADRC method do not address the inefficiencies of the method in the same manner as the present invention. These patents include Japanese patent publication number 09139941 A, published Feb. 27, 1997, entitled “Encoding/decoding device for picture signal” and U.S. Pat. No. 5,734,433 ('433) entitled “Picture encoding apparatus, picture encoding method, picture encoding and transmitting method, and picture record medium.” The Japanese patent 09139941A pertains to the reduction of the amount of required calculations by normalizing a picture element value in a level direction by ADRC encoding in fractal encoding. The '433 patent uses a least square optimization method to determine the minimum values of the encoded data.
OBJECT AND SUMMARY OF THE INVENTION
The present invention addresses the foregoing needs by providing a system, (i.e., a method, an apparatus, and computer-executable process steps), for organization and retrieval of coded input digital video data, such that any particular segment of the data can easily be identified and retrieved. This is accomplished by two innovations. Firstly, the band is no longer the unit for encoding the digital video data. Instead, a smaller unit, a coding block, is used as the coding unit for a frame. A coding block is a small number, for example 6, 4 by 4, horizontally adjunct blocks compressed to a fixed length. Secondly, within each coding block, only two quantization strategies are employed, so that the start and end position of any coding block is easily ascertained, as well as the location of any individual block within the coding block.
It is a further object of this invention to provide a quantization selection strategy that is efficient and economical, ensuring the required compression ratio by sacrificing the quality of the frame when necessary. Moreover, the quantization selection strategy of the present invention also enhances overall encoding and decoding efficiency while producing a video output that is of a predetermined picture quality acceptable to the consumer, since only visually insignificant data is discarded. The strategy ensures that the subjective visual quality of the picture produced remains satisfactory in that it will contain no annoying artifacts.
In the present invention, the seven quantization strategies available under the ADRC method are replaced with two strategies, fine and coarse quantization. In selecting a quantization strategy, the data is first encoded using the number of bits specified by a modified dynamic range table. However, if this fine quantization strategy does not guarantee a degree of compression which will generate the needed bit transmission rate, a coarse strategy, using greater compression, and therefore fewer bits, is immediately selected.
More than one strategy is used because the dynamic range does not precisely reflect the distribution of the data. For example, the following set of data, {0, 20, 22, 21, 24, 25, 200} has a dynamic range of 200. However, most of the data is concentrated around value 22. A coarse quantization step such as 32 would guarantee the whole coding block will have a fixed compression ratio of 2. However, this would more severely degrade the image quality than a smaller quantization step such as 8. The finer quantization step would provide a more accurate result for the data range 20-25, although level 200 would need more bits. The extra needed bits can be provided from other blocks within the same coding block, that have smaller dynamic ranges. Accordingly, the present invention uses more than one strategy to code blocks but avoids the complexity resulting from the 7 strategies provided by the ADRC method.
It is a further object of the present invention to provide a system for reducing the number of bits that must be transmitted, to represent the minimum values of a particular coding block. In one embodiment of the invention, instead of transmitting a minimum value for each block of data, which requires 8 bits in accordance with the ADRC method, the present invention utilizes a 3-bit code representing the range the minimum value falls into, and only the number of bits that are required to represent each minimum value. Because some minimum values within a given coding block may have relatively small differences due to the continuity of part of the image, these minimum values can be represented in less than 8 bits; the minimum value for many blocks is 0. So statistically, this coding system reduces the number of bits required to encode an image.
REFERENCES:
patent: 4703352 (1987-10-01), Kondo
patent: 5734433 (1998-03-01), Kondo et al.
patent: 6125146 (2000-09-01), Frencken et al.
patent
Koninklijke Philips Electronics , N.V.
Philippe Gims
LandOfFree
Efficient video data data access using fixed ratio compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient video data data access using fixed ratio compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient video data data access using fixed ratio compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3336447