Method for determining to skip macroblocks in encoding video

[0002] The present application pertains to encoding video.

[0003] Several standards are available for encoding and decoding video to reduce the bandwidth of the video such as H.261, H.262, H.263, MPEG-1 and MPEG-2. These standards typically utilize both temporal and spatial compression. A to be encoded video picture (field or frame) is divided into non-overlapping macroblocks, where each macroblock is a two dimensional array of luminance blocks and each chrominance block overlapping thereon. Each luminance or chrominance block, in turn, is an 8×8 array of (luminance or chrominance) pixel data. In temporal encoding, one or more reference pictures are designated for each to be encoded video picture. For each macroblock of the to be temporally encoded video picture, a search is carried out, e.g., using a block matching technique, to identify a prediction macroblock in a reference picture which best matches the macroblock of the to be encoded picture. This is referred to as motion estimation. The prediction macroblock is identified by a motion vector which indicates a spatial (pixel row and column) and temporal (picture of the sequence) offset from the macroblock of the to be encoded picture to the prediction macroblock. A prediction error macroblock is then formed by subtracting the macroblock of the to be temporally encoded picture from the prediction macroblock. The individual blocks of the prediction error macroblock are then spatially encoded.

[0004] Spatial encoding involves the steps of discrete cosine transforming (orthogonally transforming) a block, quantizing the transformed block, and entropy encoding the quantized block (e.g., run-level encoding the quantized block and variable length encoding the run-level encoded block). The encoded data thus produced is formatted into a bitstream including other header, flag and parameter data.

[0005] According to the MPEG-2 standard, it is not strictly necessary to encode each macroblock. Rather, if a prediction error macroblock has a zero spatial offset motion vector, and only zero valued quantized block data, no data need be provided in the bitstream for the macroblock. Instead, indicator information is placed in the bitstream to indicate that a macroblock has been skipped.

[0006] It is an object of the present invention to provide an improved determination process for determining whether or not to skip a macroblock.

[0007] This and other objects is achieved by the present invention. According to one embodiment, a method is provided for encoding video pictures according to the following steps: (a) A sequence of video pictures is obtained. (b) Certain ones of the pictures of the sequence are designated for predictive encoding and one or more of the pictures of the sequence are designated as reference pictures for each picture designated for predictive encoding. (c) A picture designated for predictive encoding is divided into macroblocks. (d) The following steps are then iterated once for each i^thmacroblock of the picture designated for encoding: (e) The i^thmacroblock is motion estimated using only the luminance blocks of the i^thmacroblock. This produces a motion vector, indicating the temporal and spatial offset from the i^thmacroblock to a prediction macroblock in a designated reference picture, and the mean absolute difference of the luminance blocks of the i^thmacroblock and the luminance pixels of the prediction macroblock. The mean absolute difference is generated by evaluating: $\sum _{x=l}^j\sum _{y=l}^k\left|P_i^Y\left[x,y\right]-{\mathrm{MB}}_i^Y\left[x,y\right]\right|$

[0008] where P^Y_iis the luminance pixel data of the prediction macroblock for the i^thmacroblock, MB^Y_iis the luminance pixel data of the i^thmacroblock and j and k are the number of rows and columns of luminance pixel data in a macroblock, respectively. (f) If the motion vector is zero and the mean absolute difference is below a first threshold, then the following steps (g), (h) and (i) are performed. Otherwise, only steps (j), (k), (l), (m) and (n) are performed. (g) The chrominance mean absolute difference between the chrominance blocks of the i^thmacroblock and the prediction macroblock is generated by evaluating: $\sum _{x=l}^a\sum _{y=l}^b\left|P_i^{\mathrm{Cr}}\left[x,y\right]-{\mathrm{MB}}_i^{\mathrm{Cr}}\left[x,y\right]\right|+\sum _{x=l}^a\sum _{y=l}^b\left|P_i^{\mathrm{Cb}}\left[x,y\right]-{\mathrm{MB}}_i^{\mathrm{Cb}}\left[x,y\right]\right|$

[0009] where P^Cr_iis the red chrominance pixel data of the prediction macroblock for the i^thmacroblock, MB^Cr_iis the red chrominance pixel data of the i^thmacroblock, P^Cb_iis the blue chrominance pixel data of the prediction macroblock for the i^thmacroblock, MB^Cb_iis the blue chrominance pixel data of the i^thmacroblock and a and b are the number of rows and columns of red and blue chrominance pixel data in a macroblock, respectively. (h) If the chrominance mean absolute difference is less than a second threshold, then the following step (i) is performed. Otherwise, steps (j), (k), (l), (m) and (n) are performed. (i) An indication is inserted into the bitstream indicating that the i^thmacroblock is skipped. No further steps (namely, (j), (k), (l), (m) and (n)) are performed for the i^thmacroblock. On the other hand, if step (i) is not performed for the i^thmacroblock, the following steps (j), (k), (l), (m) and (n) are performed for the i^thmacroblock: (j) The luminance and chrominance blocks of the i^thmacroblock are subtracted from the prediction macroblock to form the prediction error macroblock for the i^thmacroblock. (k) Each block of the prediction error macroblock for the i^thmacroblock is then orthogonally transformed. (l) Each transformed block of the prediction error macroblock for the i^thmacroblock is quantized. (m) Each quantized block of the prediction error macroblock for the i^thmacroblock and the motion vector are entropy encoded. (n) The entropy encoded blocks of the prediction error macroblock and motion vector for the i^thmacroblock are then inserted into the encoded bitstream. Thus steps (j), (k), (l), (m) and (n) are not performed for the i^thmacroblock if step (i) is performed for the i^thmacroblock.

[0010] According to another embodiment, an encoding system is provided including a memory for temporarily storing pictures pending encoding and reference pictures, and a processor for performing the above steps.

[0011] The technique according to the invention is amenable for an encoder implemented as software executing on one or more processors. Specifically, the decision of whether or not to skip a macroblock is performed prior to the spatial encoding steps of orthogonally transforming, quantizing and entropy encoding. As orthogonal transforms are highly computationally intensive, a dramatic savings in processing time is achieved for a processor implementation, which additional time can be used to perform other encoding or non-encoding processing tasks.

[0012] FIG. 1 shows an encoder according to an embodiment of the present invention.

[0013] FIG. 2 shows a flowchart illustrating an encoding process executed by the encoder according to an embodiment of the present invention.

[0014] This invention is illustrated herein for an H.263 compatible video encoder. However, those skilled in the art will appreciate the applicability of the invention to other types of predictive encoders, such as H.261, H.262, MPEG-1 and MPEG-2 video encoders.

[0015] FIG. 1 shows an encoding system 10 according to the present invention. The system 10 includes an encoder processor 12, such as the W9960CF Video Conferencing Video Codec™ distributed by Winbond Electronics Corporation, N.A., located in San Jose, Calif. This system 10 also includes a memory 14 which may be implemented using multiple high speed SDRAM circuits, such as the W986408AH-10 SDRAMs distributed by Winbond Electronics Corporation, N.A. Video pictures of a sequence are sequentially inputted to the processor 12 for encoding. These video pictures may be initially generated by a camera (having a photo tube, CCD or CMOS photo sensor). During encoding, one or more pictures may be stored in the memory 14. An encoded bitstream containing the encoded video pictures is outputted from the encoder processor 12. Encoded pictures may be transferred to a (storage or transmission) medium such as a magnetic or optical disk, memory, local area network, telephone network, cable network, satellite network, etc. Illustratively, the encoding system 10 is designed for use with a personal computer that communicates two way video via a modem connected to a telephone network. In such a case, the encoding system 10 may be contained in the same housing as the camera attached to the computer. The encoding system 10 can communicate the encoded video via a USB (universal serial bus) to a USB port of the computer.

[0016] FIG. 2 illustrates a flow chart of a an encoding process carried out by the encoding system 10. Again, the process illustratively is an H.263 compatible encoding process, although other encoding process may be carried out by the encoding system 10 through suitable substitution of program instructions executed by the processor 12. Some of the well known encoding steps have been omitted for sake of brevity.

[0017] In a first step 102, the processor 12 determines if there is another picture of the sequence of pictures to be received. If not, the processor 12 may stop execution. If another picture is available, the processor 12 executes step 104 according to which the next picture (in presentation order) is inputted to the processor 12. This picture may be stored in a buffer of the memory 14 pending processing.

[0018] Next, in step 106, the processor 12 determines the picture coding type for the picture. Illustratively, there are three types of pictures, namely, I, P and B. All of the macroblocks in I pictures are only spatially encoded-no macroblocks of an I picture are temporally encoded. Rather, each block of each macroblock in an I picture is merely discrete cosine transformed, quantized and entropy encoded. The processing steps for selecting spatial only encoding for certain macroblocks, and for performing such encoding by the processor 12, have been omitted for sake of brevity. Macroblocks in P pictures are preferably both temporally and spatially encoded. The reference picture for a P picture is the immediately preceding I or P picture in the sequence of pictures. Occasionally, a macroblock in a P picture is only spatially encoded, if an adequate prediction cannot be found therefor. Macroblocks in B pictures are also preferably both temporally and spatially encoded. Unlike P pictures, each B picture has a reference picture which precedes the B picture and a reference picture which follows the B picture (in presentation order). A prediction macroblock can selectively originate in the preceding reference picture, the following reference picture or may be an interpolation of a prediction macroblock in the preceding reference picture and a prediction macroblock in the following reference picture. The reference picture(s) from which each prediction macroblock originates may be determined on a macroblock-by-macroblock basis. The reference pictures for B pictures are the immediately preceding I or P picture and the immediately following I or P picture, in presentation order. (Other, well known and more complex predictions may be available, such as dual prime, field prediction of frame pictures, 16×8 prediction, etc., depending on the encoding standard with which the encoding system 10 complies.) In designating picture coding types, the processor 12 may select a predetermined pattern, such as an I picture for the very first picture of the sequence and then alternating P and B pictures. As noted above, the designation of the reference picture is typically fixed by the encoding standard with which the encoding system 10 complies.

[0019] In step 108, the processor 12 divides the inputted picture into macroblocks. Typically, inputted video pictures include R (red), G (green) B (blue) pixel data which must be converted to Y (luminance), C_r(red chrominance) and C_b(blue chrominance) data. This can be achieved by a simple filtering operation. The luminance and chrominance data is then organized into macroblocks. For example, the macroblocks can include a 2×2 array of Y luminance blocks, one C_rred chrominance block and one C_bblue chrominance block, which C_rand C_bblocks have a lower sampling density than the Y blocks.

[0020] Steps 110-130 are then performed for each macroblock of each temporally encoded (P or B) picture. Each iteration is preferably completed for each macroblock, one at a time and in sequence before continuing to the next macroblock. In step 110, the processor 12 determines if there is another macroblock to be encoded for the current picture. If not, the processor 12 returns to step 102. If there is another macroblock to be processed, the processor 12 obtains the next macroblock (hereinafter referred to as the current macroblock) and performs a motion estimation thereon in step 112. Motion estimation may be performed using a block matching technique. However, only the luminance blocks Y are used in the motion estimation. Motion estimation can be achieved by extracting a search window of luminance pixel data from a reference picture that is spatially centered about the spatial coordinates of the current macroblock. (Preferably, the reference pictures have been previously encoded, decoded and stored in a picture buffer of the memory 14. This is so that predictions are formed using the same decoded pictures available at the decoder.) The processor 12 forms candidate prediction macroblocks identified by motion vectors at increments of ½ pixel row and column offsets and compares them to the current macroblock. This comparison is achieved by the processor 12 calculating the luminance mean absolute difference (MAD) for the current (i^th) macroblock as follows: $\sum _{x=l}^j\sum _{y=l}^k\left|P_i^Y\left[x,y\right]-{\mathrm{MB}}_i^Y\left[x,y\right]\right|$

[0021] where P^Y_iis the luminance pixel data of a candidate prediction macroblock for the current i^thmacroblock, MB^Y_iis the luminance pixel data of the current i^thmacroblock and j and k are the number of rows and columns of luminance pixel data in a macroblock, respectively. (This value may optionally be divided by j*k.) For 4:2:0 color format video, the luminance data Y of a macroblock is an array of 2×2 blocks of 8×8 luminance pixel data each and thus j=k=16. The candidate prediction macroblock with the smallest MAD is selected as the prediction macroblock and is identified by a motion vector having spatial offset coordinates and a temporal coordinate (indicating which reference picture from which the prediction macroblock originated). (Note, if an interpolated prediction is formed, two motion vectors are generated, namely, one for the prediction macroblock in the preceding reference picture and one for the macroblock in the following reference picture.)

[0022] In step 114, the processor 12 determines if the motion vector has zero spatial offset coordinates and if the luminance MAD generated for the prediction macroblock is below a first threshold. (Illustratively, this determination is made only when the prediction macroblock is selected from only a preceding reference picture. If the prediction macroblock is interpolated, or selected from a following reference picture, the processor 12 proceeds directly to step 122.) This would indicate that the luminance of the current macroblock of the current picture is nearly identical to the luminance of the prediction macroblock in the previous picture at the same spatial row and column coordinates. In such a case, it is possible that the current macroblock has not changed from the previous picture. This typically happens if the macroblock contains a portion of the image that is static. The first threshold is set fairly low, e.g., close to zero. Due to introduction of noise in the inputted video pictures, the first threshold is preferably greater than zero. If the motion vector has zero spatial coordinates and the luminance MAD is zero, the processor 12 executes step 116 through path A. If either the motion vector has nonzero spatial coordinates, or the luminance MAD is greater than or equal to the first threshold, or both, the processor 12 executes step 122 through path B.

[0023] Assume first that both the motion vector has zero spatial coordinates and that the luminance MAD is below the first threshold. In such a case, in step 116, the processor 12 generates the MAD for the chrominance of the current macroblock and the prediction macroblock by evaluating: $\sum _{x=l}^a\sum _{y=l}^b\left|P_i^{\mathrm{Cr}}\left[x,y\right]-{\mathrm{MB}}_i^{\mathrm{Cr}}\left[x,y\right]\right|+\sum _{x=l}^a\sum _{y=l}^b\left|P_i^{\mathrm{Cb}}\left[x,y\right]{\mathrm{MB}}_i^{\mathrm{Cb}}\left[x,y\right]\right|$

[0024] where P^Cr_iis the red chrominance pixel data of the prediction macroblock for the current i^thmacroblock, MB^Cr_iis the red chrominance pixel data of the current i^thmacroblock, P^Cb_iis the blue chrominance pixel data of the prediction macroblock for the current i^thmacroblock, MB^Cb_iis the blue chrominance pixel data of the current i^thmacroblock and a and b are the number of rows and columns of red and blue chrominance pixel data in a macroblock, respectively. (This value may optionally be divided by 2*a*b.) For 4:2:0 color format video pictures, each macroblock has exactly one 8×8 block of C_rred chrominance pixel data one 8×8 block of C_bblue chrominance data and thus a=b=8. Then, in step 118, the processor 12 determines if the chrominance MAD is less than a second threshold. If so, this indicates that the current macroblock is basically unchanged from the previous picture and therefore can be skipped. Thus, if the chrominance MAD is less than a second threshold, the processor 12 skips the current macroblock in step 120 by inserting an indication into the bitstream that indicates that the macroblock is skipped. For example, each macroblock in the encoded bitstream may be preceded by a header in which is contained a macroblock address increment. The macroblock address increment indicates the increase of the address of the macroblock (the data of which immediately follows the header) in relation to the address of the macroblock which immediately precedes it in the bitstream. Macroblocks are preferably numbered sequentially. Thus, if the macroblock address increment is greater than one, then one or more intervening macroblocks have been skipped. Afterwards, the processor 12 executes step 110 via execution path C. If, in step 118, the processor 12 determines that the chrominance MAD is greater than or equal to the second threshold, the processor 12 executes step 122 via execution path B.

[0025] The processor 12 may have proceeded to step 122 from step 114 or 118. Either is an indication that the current macroblock is not substantially the same as the macroblock at the same coordinates in the previous picture. As such, the macroblock is encoded and placed in the encoded video bitstream. In step 122, the processor 12 forms the prediction error macroblock by subtracting the current macroblock from its prediction macroblock. Next, in step 124, the processor 12 discrete cosine transforms (a kind of orthogonal transform) each luminance and chrominance block of the prediction error macroblock. Next, in step 126, the processor 12 quantizes each transformed luminance and chrominance block of the macroblock. The quantizer scale factor is preferably varied to produce fewer or more bits per encoded macroblock in the encoded video bitstream. This may be done to ensure that the decoder buffer neither underflows nor overflows. In step 128, the processor 12 entropy encodes each quantized luminance and chrominance block of the prediction error macroblock data. The quantized data of each block may be scanned out into a sequence according to a zig-zag pattern. This tends to produce long runs of zeros separated by nonzero values. The entropy encoding may include (zero) run-level encoding followed by variable length encoding each run-level pair. In step 130, the processor 12 inserts the variable length encoded prediction error macroblock data into the bitstream. The processor 12 then returns to step 110 via execution path C.

[0026] According to the invention, the determination of whether or not to skip macroblocks is made before forming the prediction error macroblock, discrete cosine transforming, quantizing and entropy encoding, in steps 122, 124, 126 and 128. Prior art systems use discrete hardware for performing each of these steps and thus no savings would be achieved by their omission. However, the invention is particularly suitable for a processor implementation because processing intensive steps 122-128, in particular, step 124 which requires two floating point matrix multiplications on each block of the prediction error macroblock, are avoided for skipped macroblocks. A real time video conferencing application requires a very low latency, is not intended to have unpredictable scene cuts and will have a static background. Thus, many skipped macroblocks are anticipated each frame. The average saved time for skipped macroblocks can be allocated to other processing by the processor, such as increasing the search windows for motion vectors, better statistical allocation of bits per encoded macroblock, or other non-encoding processes performed by the processor. Thus, the invention provides a particular savings for processor encoding implementations.

[0027] The above discussion is merely illustrative of the invention. Those skilled in the art may devise numerous alternative embodiments without departing from the spirit and scope of the following claims.