Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
2000-02-11
2002-05-28
Johns, Andrew W. (Department: 2621)
Image analysis
Image compression or coding
Adaptive coding
Reexamination Certificate
active
06396956
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to encoding digital images and video in low bit rate and low delay communication environments and more specifically to selecting which video frames and image regions should be skipped before encoding the digital images and video.
In low bit rate and low delay video communications, such as in a video phone, video conferencing, broadcast, etc., a large percentage of the video data cannot be encoded and transmitted to the receiver. In fact, entire video frames or large regions of pixels within a frame must often be skipped (not encoded) when the bit rate of the communication is too low or when the encoder buffer is approaching overflow. If the data to be skipped is not selected intelligently, the quality of the encoded video decreases dramatically.
Some compression techniques do not determine before hand that blocks are going to be skipped and as a result waste computation resources. At very low bit rates, the compression is so high that over 90 per cent of the blocks may not produce any bits. Hence, these types of encoders waste time and computational resources by unnecessarily processing blocks that do not produce bits by the encoder. This waste is fairly dramatic in advanced video codecs, since block encoding usually requires complex transformation of the pixel values typically using a Discrete Cosine Transform (DCT) and some quantization of the transform coefficients.
Rate control methods generally use the energy of the pixels in a frame to determine bit allocations. The energy of the blocks that do not produce bits is also considered in the bit allocation. This procedure is not effective in intelligently distributing the bits throughout the frame and adversely affects the quality of the encoded image.
A system incorporating block skipping is described by A. Yu, R. Lee, and M.
Flynn, “Early detection of all-zero coefficients in H.263”, in Proceedings of the Picture Coding Symposium, pp. 159-164, Berlin, September 1997. In Yu, Lee, and Flynn, image blocks having DC coefficients below a threshold are skipped. This approach is simple to implement but skips important blocks that have high energy frequency components and a small DC value.
Another block skipping approach is described by A. Eleftheriadis and D. Anastassiou, “Constrained and general dynamic rate shaping of compressed digital video,” in Proceedings of the International Conference on Image Processing, vol. 3, pp. 396-399, October 1995 and by R. J. Safranek, C. R. Kalmanek Jr., and R. Garg, “Methods for matching compressed video to ATM networks,” in Proceedings of the International Conference on Image Processing, vol. 1, pp. 13-16, October 1995. This block skipping technique first encodes the image blocks and then drops encoded image blocks from the encoded bit stream to hit a target bit rate. The problem with this method is that all the blocks need to be encoded in advance and organized in order of importance. This technique defeats the purpose of saving computational complexity at the encoder.
In video communications, the encoding bits are usually stored in a buffer before they are transmitted through the channel. If there is high motion activity or a scene change, the video frames occupy many bits and the buffer fills up quickly. When the buffer is close to overflow, the encoder must produce fewer bits and even skip coding frames. Typically, during high motion and scene changes, one or several frames are skipped and the remaining, non-skipped frames are encoded with low image quality.
A smart encoder should decide when and how many frames should be skipped, so that enough bits are left for encoding the non-skipped frames with good quality. Forcing the encoder to operate on a smaller range of quantization values can prevent the drop in image quality in the non-skipped frames during high motion and scene changes. However, the number of bits produced per frame can not be controlled using this technique and presents the serious danger of buffer overflow. Some recent encoding techniques detect scene changes using ad hoc mechanisms and improve the image quality during the changes, but these methods are not robust and the video quality still drops occasionally. For example, U.S. Pat. No. 4,999,074 issued Mar. 12, 1991 to Ando entitled “System for efficiently coding a moving-picture signal, capable of selecting several different coding systems,” and U.S. Pat. No. 5,099,322 issued Mar. 24, 1994 to R. J. Gove, entitled “Scene change detection system and method” use simple frame difference and threshold-based mechanisms to detect the scene changes. The thresholds in these techniques are heuristically determined and easily fail.
Thus, a need remains for intelligently deciding which blocks in a video frame and which video frames should be skipped, when there is a limited number of available bits.
SUMMARY OF THE INVENTION
A block and frame skipping technique decides which image regions, blocks or frames in a video frame or series of frames should be skipped. Many of the blocks in a given video frame are very similar to blocks in previous frames and after motion compensation the pixel energy remaining in the blocks is very small. As a result, either few or no bits are generated when encoding these low energy blocks. Block skipping detects in advance which of the regions in a video frame will not produce any bits, so that the encoder can skip the encoding process for these blocks.
The energy threshold is dynamically adapted for every image frame according to the energy in the frame, a number of bits available for encoding the frame and the efficiency of the encoder. The block skipping technique uses an iterative procedure to determine the optimal energy threshold. Block skipping repeatedly discards the image block with the lowest energy and then recomputes the energy threshold. The process is repeated until the energy threshold is less than that of the block with lowest energy among the remaining nondiscarded blocks. The threshold at this point is referred to as the optimal energy threshold. All image blocks whose pixel energy is below the optimal energy threshold are skipped.
Frame skipping predicts the distortion quality of an entire frame before encoding. If the predicted frame quality is below a distortion threshold, more bits are assigned to that frame while other frames are skipped.
Block skipping and frame skipping provide more efficient bit rate control by not allocating bits to blocks or frames that should not be encoded. Block and frame skipping reduce up to 90 percent of the computational complexity of the DCT/quantization procedure at the encoder.
Another benefit of the invention from previous decoding techniques is that the quality of the encoded video is guaranteed not to drop below a minimum pixel signal to noise ratio (PSNR), even throughout scene changes and high-motion video frames. The number of bits produced per frame is well controlled and hence there is no danger of buffer overflow. Sophisticated scene change detectors or other complexity indicators are not required providing a computationally simple encoding technique. A typical block-based image coder is used to explain the invention. However, the block and frame skipping technique can be used for any image or video encoder.
The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment of the invention, which proceeds with reference to the accompanying drawings.
REFERENCES:
patent: 4999074 (1991-03-01), Afeyan
patent: 5099322 (1992-03-01), Gove
patent: 5103307 (1992-04-01), Sugiyama
patent: 5159447 (1992-10-01), Haskell et al.
patent: 5241383 (1993-08-01), Chen et al.
patent: 5274443 (1993-12-01), Dachiku et al.
patent: 5283646 (1994-02-01), Bruder
patent: 5323187 (1994-06-01), Park
patent: 5426463 (1995-06-01), Reininger et al.
patent: 5532746 (1996-07-01), Chang
patent: 5613004 (1997-03-01), Cooperman et al.
patent: 5617150 (1997-04-01), Nam et al.
patent: 5966465 (1999-10-01), Keith et al.
pate
Lei Shaw-Min
Ribas-Corbera Jordi
Azarian Seyed
Johns Andrew W.
Marger & Johnson & McCollom, P.C.
Sharp Laboratories of America Inc.
LandOfFree
Method and apparatus for selecting image data to skip when... 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 and apparatus for selecting image data to skip when..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for selecting image data to skip when... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2908602