Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1995-10-26
2001-02-20
Britton, Howard (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240050
Reexamination Certificate
active
06192081
ABSTRACT:
The present invention relates to an apparatus and concomitant method for optimizing the coding of motion video. More particularly, this invention relates to an apparatus and method that selects a macroblock coding mode based upon the quantization scale selected for the macroblock.
BACKGROUND OF THE INVENTION
The increasing development of digital video technology presents an ever increasing problem of reducing the high cost of video compression codecs and resolving the inter-operability of equipment of different manufacturers. To achieve these goals, the Moving Picture Experts Group (MPEG) created the ISO/IEC international Standards 13818-1 (1994) (generally referred to as MPEG-1) and 13818-2 (Jan. 20, 1995 draft) (generally referred to as MPEG-2), which are incorporated herein in their entirety by reference. One goal of these standards is to establish a standard coding/decoding strategy with sufficient flexibility to accommodate a plurality of different applications and services such as desktop video publishing, video conferencing, digital storage media and television broadcast.
Although the MPEG standards specify a general coding methodology and syntax for generating a MPEG compliant bitstream, many variations are permitted in the values assigned to many of the parameters, thereby supporting a broad range of applications and interoperability. In effect, MPEG does not define a specific algorithm needed to produce a valid bitstream. Furthermore, MPEG encoder designers are accorded great flexibility in developing and implementing their own MPEG-specific algorithms in areas such as image pre-processing, motion estimation, coding mode decisions, scalability, and rate control. This flexibility fosters development and implementation of different MPEG-specific algorithms, thereby resulting in product differentiation in the marketplace. However, a common goal of MPEG encoder designers is to minimize subjective distortion for a prescribed bit rate and operating delay constraint.
In the area of coding mode decision, MPEG provides a plurality of different macroblock coding modes. Generally, these coding modes are grouped into two broad classifications, inter mode coding and intra mode coding. Intra mode coding involves the coding of a macroblock or picture that uses information only from that macroblock or picture. Conversely, inter mode coding involves the coding of a macroblock or picture that uses information both from itself and from macroblocks and pictures occurring at different times. Specifically, MPEG-2 provides macroblock coding modes which include intra mode, no motion compensation mode (No MC), frame/field/dual-prime motion compensation inter mode, forward/backward/average inter mode and field/frame DCT mode. For a detailed description of each coding mode, see the ISO/IEC international Standards for MPEG-1 and MPEG-2.
These coding modes provide different coding strategies (predictions) which produce different efficiencies in the number of bits necessary to code a macroblock. Thus, each mode is more efficient than another depending upon a number of different factors such as the coarseness of the quantization scale, picture type, and nature of the signal within the macroblock. To achieve optimal coding performance, it is necessary to select the most efficient coding mode by calculating and comparing the number of bits necessary to code a particular macroblock for each separate mode. The most efficient coding mode should code the macroblock with the least amount of bits. However, the determination of the optimal solution is further complicated by the MPEG differential encoding of motion vectors and discrete cosine transform (DCT) coefficients, which introduces dependencies that carry over from macroblock to macroblock for a duration equal to the slice length. A slice is a sequence of macroblocks which are located in the same horizontal row in raster scan order. Due to such dependencies, a “full-search” calculation must now compare the efficiencies of various combinations of different modes in coding a slice where each individual macroblock can be coded in a different mode.
To illustrate, if a slice has a length of ten (10) macroblocks and there are five (5) different coding modes, then there are 5
10
available coding combinations for each slice. The computation for a full-search is exponentially proportional to the slice size based on the number of modes. Thus, the dependency results in an exponentially growing function, thereby increasing the complexity of the above calculation by many folds. In fact, the time delay associated with the above calculation is unacceptable for many MPEG applications. Thus, due to the long time delay and severe computational overhead, it is impractical to select a coding mode based upon the result of a full-search calculation.
In the current MPEG coding strategies (e.g., Test Models 4 and 5 (TM4 and TM5)), the coding mode for each macroblock is selected by comparing the energy of the predictive residuals (error signal). Namely, the intra mode/inter mode decision is determined by a comparison of the variance (&sgr;
2
) of the macroblock pixels against the variance of the predictive residuals for each coding mode. However, the coding mode selected by this criterion may not achieve optimal coding performance, since a high variance may not necessarily translate to an increase in the number of bits necessary to code a macroblock. Thus, a coding strategy based solely on such variance may not necessarily reduce the final compression bit count.
Therefore, a need exists in the art for an apparatus and method for selecting a coding mode which approaches the optimal solution and is relatively simple to facilitate practical implementation.
SUMMARY OF THE INVENTION
The present invention is an apparatus and method for selecting a macroblock coding mode based upon the quantization scale selected for the macroblock. The efficiency of a particular coding mode is affected by the operating point for distortion (i.e., for a particular quantization scale). For example, a coding mode that produces low distortion in encoding a macroblock may in fact perform poorly where high distortion in encoding a macroblock is acceptable. Thus, the current invention selects an appropriate coding mode in accordance with the quantization scale selected for the macroblock.
Specifically, the total number of bits needed to code each macroblock consists of two parts, bits needed for coding motion vectors and bits for coding the predictive residual. The number of bits for coding the motion vectors is generally obtained from a look-up table. The number of bits for coding the predictive residual is obtained by an estimation which assumes that the number of bits for encoding the predictive residuals is directly proportional to the value of its variance and inversely proportional to the value of quantizer steps (quantization scale). Using this estimation, the total number of bits necessary to code a macroblock is calculated and compared for each coding mode. By selecting the coding mode with the least number of bits, the invention attains a near-optimal solution of low complexity for practical implementation.
REFERENCES:
patent: 4218704 (1980-08-01), Netravall et al.
patent: 4958226 (1990-09-01), Haskell et al.
patent: 4972260 (1990-11-01), Fujikawa
patent: 5091782 (1992-02-01), Krause
patent: 5134476 (1992-07-01), Aravind et al.
patent: 5231484 (1993-07-01), Gonzales et al.
patent: 5253059 (1993-10-01), Ansari et al.
patent: 5365271 (1994-11-01), Asano
patent: 5440345 (1995-08-01), Shimoda
patent: 5491513 (1996-02-01), Wickstrom et al.
patent: 5576767 (1996-11-01), Lee et al.
patent: 5594504 (1997-01-01), Ebrahimi
T. Weigand et al., “Efficient Mode Selection for Block-Based Motion Compensated Video Coding”, distributed at International Conference on Image Processing held at Washington D.C.(Oct. 22-24, 1995).
Chiang Tihao
Chien Max
Kwok Wilson
Sun Huifang
Britton Howard
Burke William J.
Sarnoff Corporation
LandOfFree
Apparatus and method for selecting a coding mode in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for selecting a coding mode in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for selecting a coding mode in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2593019