Hierarchical Motion Estimation for Interlaced Video

a. Field of the Invention

The present invention relates to the field of data compression and, more particularly, to a system and method for compressing digital motion video signals.

b. Related Art

Technological advances in digital transmission networks, digital storage media, Very Large Scale Integration devices, and digital processing of video and audio signals are converging to make the transmission and storage of digital video economical in a wide variety of applications. Because the storage and transmission of digital video signals is central to many applications, and because an uncompressed representation of a video signal requires a large amount of storage, the use of digital video compression techniques is vital to this advancing art. In this regard, several international standards for the compression of digital video signals have emerged over the past decade, with more currently under development. These standards apply to algorithms for the transmission and storage of compressed digital video in a variety of applications, including: video-telephony and teleconferencing; high quality digital television transmission on coaxial and fiberoptic networks as well as broadcast terrestrially and over direct broadcast satellites; and in interactive multimedia products on CDROM, Digital Audio Tape, and Winchester disk drives.

Several of these standards involve algorithms based on a common core of compression techniques, e.g., the CCITT (Consultative Committee on International Telegraphy and Telephony) Recommendation H.120, the CCITT Recommendation H.261, and the ISO/IEC MPEG-1 and MPEG-2 standards. The MPEG algorithms have been developed by the Moving Picture Experts Group (MPEG), part of a joint technical committee of the International Standards Organization (ISO) and the International Electrotechnical Commission (IEC). The MPEG committee has been developing standards for the multiplexed, compressed representation of video and associated audio signals. The standard specifies the syntax of the compressed bit stream and the method of decoding, but leave considerable latitude for novelty and variety in the algorithm employed in the encoder.

Both the MPEG-1 and MPEG-2 algorithms can be described as hybrid transform encoding/motion compensation encoders. For an encoder to efficiently use motion compensation, it typically must perform a task called motion estimation.

Motion estimation can be described in general terms as deciding where a particular region in a picture "came from" in a picture or pictures that occur temporally earlier or later in time and deciding how accurately a region of the current picture can be said to "come from" other pictures.

Motion estimation is one of the most computationally intensive tasks that an MPEG-2 encoder performs. Thus, an important consideration in building an MPEG-2 encoder is to use an economical motion estimation scheme.

The present invention involves a system and method for performing motion estimation. Interlaced frames are reduced in resolution by using field based scaling, and a first search is performed on the reduced resolution frames. This first search is performed by computing motion errors between the fields of a current frame and the fields of a reference frame to obtain vectors that approximately describe inter-field motion. These same motion errors are used to compute frame errors, which are used to obtain vectors that approximately describe inter-frame motion. The approximate field and frame vectors are then refined to get more precise vectors.

Advantageously, the present invention can be implemented an encoder suitable for use with the ISO/IEC MPEG-2 standard.

FIG. 1: Exemplary pair of Groups of Pictures (GOP's);

FIG. 2: Exemplary macroblock (MB) subdivision of a picture (for 4:2:0 format);

FIG. 3: Block subdivision of a macroblock (for 4:2:0 format);

FIG. 4: Block diagram of a video encoder;

FIG. 5: Block diagram of the hierarchical field/frame computing engine of FIG. 11;

FIG. 6: Flow chart describing the method of motion estimation in accordance with the principles of the present invention;

FIGS. 7a and 7b: Example of horizontal image scaling in accordance with the principles of the present invention;

FIGS. 8a and 8b: Example of vertical image scaling in accordance with the principles of the present invention;

FIGS. 9a and 9b: Example of reduced resolution frame and macroblock in accordance with the principles of the present invention, shown in frame form;

FIGS. 10a, 10b, 10c and 10d: Example of reduced resolution frame and macroblock in accordance with the principles of the present invention, shown in field form;

FIG. 11: Block diagram of a motion estimation unit according to an embodiment of the present invention;

FIG. 12: Block diagram of an encoder and decoder pair according to an embodiment of the present invention.

a. THE MPEG-2 ENVIRONMENT

As the present invention may be applied in connection with an MPEG-2 encoder, in order to facilitate the understanding of the invention, some pertinent aspects of the MPEG-2 compression algorithm will be reviewed. It is to be noted, however, that the invention can also be applied to other video coding algorithms which share some of the features of the MPEG algorithms.

To begin with, it will be understood that the compression of any data object, such as a page of text, an image, a segment of speech, or a video sequence, can be thought of as a series of steps, including: 1) a decomposition of that object into a collection of tokens; 2) the representation of those tokens by binary strings which have minimal length in some sense; and 3) the concatenation of the strings in a well-defined order. Steps 2 and 3 are lossless, i.e., the original data is faithfully recoverable upon reversal, and Step 2 is known as entropy coding. Step 1 can be either lossless or lossy in general. Most video compression algorithms are lossy because of stringent bit-rate requirements. A successful lossy compression algorithm eliminates redundant and irrelevant information, allowing relatively large errors where they are not likely to be visually significant and carefully representing aspects of a sequence to which the human observer is very sensitive. The techniques employed in the MPEG-2 algorithm for Step 1 can be described as predictive/interpolative motion-compensated hybrid DCT/DPCM coding. Huffman coding, also known as variable length coding, is used in Step 2. Although, as mentioned, the MPEG-2 standard is really a specification of the decoder and the compressed bit stream syntax, the following description of the MPEG-2 specification is, for ease of presentation, primarily from an encoder point of view.

The MPEG-2 video standard specifies a coded representation of video for transmission as set forth in ISO-IEC JTC1/SC29/WG11, Generic Coding of Moving Pictures and Associated Audio Information: Video, International Standard, 1994. The algorithm is designed to operate on interlaced or noninterlaced component video. Each picture has three components: luminance (Y), red color difference (C.sub.r), and blue color difference (C.sub.b). The video data may be coded in 4:4:4 format, in which case there is one C.sub.r and one C.sub.b sample for each Y sample, in 4:2:2 format, in which case there are half as many C.sub.r and C.sub.b samples as luminance samples in the horizontal direction, or in 4:2:0 format, in which case there are half as many C.sub.r and C.sub.b samples as luminance samples in both the horizontal and vertical directions.

An MPEG-2 data stream consists of a video stream and an audio stream which are packed, together with systems information and possibly other bitstreams, into a systems data stream that can be regarded as layered. Within the video layer of the MPEG-2 data stream, the compressed data is further layered. A description of the organization of the layers will aid in understanding the invention. These layers of the MPEG-2 Video Layered Structure are shown in FIGS. 1-3. The layers pertain to the operation of the compression algorithm as well as the composition of a compressed bit stream. The highest layer is the video Sequence Layer, containing control information and parameters for the entire sequence. At the next layer, a sequence is subdivided into sets of consecutive pictures, each known as a "Group of Pictures" (GOP). A general illustration of this layer is shown in FIG. 1. Decoding may begin at the start of any GOP, essentially independent of the preceding GOP's. There is no limit to the number of pictures which may be in a GOP, nor do there have to be equal numbers of pictures in all GOP's.

The third or Picture layer is a single picture. A general illustration of this layer is shown in FIG. 2. The luminance component of each picture is subdivided into 16.times.16 regions; the color difference components are subdivided into appropriately sized blocks spatially co-sited with the 16.times.16 luminance regions; for 4:4:4 video, the color difference components are 16.times.16, for 4:2:2 video, the color difference components are 8.times.16, and for 4:2:0 video, the color difference components are 8.times.8. Taken together, these co-sited luminance region and color difference regions make up the fifth layer, known as a "macroblock" (MB). Macroblocks in a picture are numbered consecutively in lexicographic order, starting with Macroblock 1.

Between the Picture and MB layers is the fourth or "slice" layer. Each slice consists of some number of consecutive MB's. Finally, each MB consists of four 8.times.8 luminance blocks and 8, 4, or 2 (for 4:4:4, 4:2:2 and 4:2:0 video) chrominance blocks. The Sequence, GOP, Picture, and slice layers all have headers associated with them. The headers begin with byte-aligned Start Codes and contain information pertinent to the data contained in the corresponding layer.

A picture can be either field-structured or frame-structured. A frame-structured picture contains information to reconstruct an entire frame, i.e., the combination of one field containing the odd lines and the other field containing the even lines. A field-structured picture contains information to reconstruct one field. If the width of each luminance frame (in picture elements or pixels) is denoted as C and the height as R (C is for columns, R is for rows), a frame-structured picture contains information for C.times.R pixels and a field-structured picture contains information for C.times.R/2 pixels.

A macroblock in a field-structured picture contains a 16.times.16 pixel segment from a single field. A macroblock in a frame-structured picture contains a 16.times.16 pixel segment from the frame that both fields compose; each macroblock contains a 16.times.8 region from each of the two fields.

Within a GOP, three types of pictures can appear. The distinguishing difference among the picture types is the compression method used. The first type, Intramode pictures or I-pictures, are compressed independently of any other picture. Although there is no fixed upper bound on the distance between I-pictures, it is expected that they will be interspersed frequently throughout a sequence to facilitate random access and other special modes of operation. Predictively motion-compensated pictures (P pictures) are reconstructed from the compressed data in that picture plus two reconstructed fields from previously displayed I or P pictures. Bidirectionally motion-compensated pictures (B pictures) are reconstructed from the compressed data in that picture plus two reconstructed fields from previously displayed I or P pictures and two reconstructed fields from I or P pictures that will be displayed in the future. Because reconstructed I or P pictures can be used to reconstruct other pictures, they are called anchor pictures.

A common compression technique is transform coding. In MPEG-2 and several other compression standards, the discrete cosine transform (DCT) is the transform of choice. The compression of an I-picture is achieved by the steps of 1) taking the DCT of blocks of pixels, 2) quantising the DCT coefficients, and 3) Huffman coding the result. In MPEG-2, the DCT operation converts a block of n.times.n pixels into an n.times.n set of transform coefficients. Like several of the international compression standards, the MPEG-2 algorithm uses a DCT block size of 8.times.8. The DCT transformation by itself is a lossless operation, which can be inverted to within the precision of the computing device and the algorithm with which it is performed.

The second step, quantisation of the DCT coefficients, is the primary source of lossiness in the MPEG-2 algorithm. Denoting the elements of the two-dimensional array of DCT coefficients by c.sub.mn, where m and n can range from 0 to 7, aside from truncation or rounding corrections, quantisation is achieved by dividing each DCT coefficient c.sub.mn by w.sub.mn times QP, with w.sub.mn being a weighting factor and QP being the quantiser parameter. The weighting factor w.sub.mn allows coarser quantisation to be applied to the less visually significant coefficients. The quantiser parameter QP is the primary means of trading off quality vs. bit-rate in MPEG-2. It is important to note that QP can vary from MB to MB within a picture.

Following quantisation, the DCT coefficient information for each MB is organized and coded, using a set of Huffman codes. As the details of this step are not essential to an understanding of the invention and are generally understood in the art, no further description will be offered here.

Most video sequences exhibit a high degree of correlation between consecutive pictures. A useful method to remove this redundancy prior to coding a picture is "motion compensation". MPEG-2 provides tools for several methods of motion compensation (described below).

Many methods of motion compensation have the following in common. For each macroblock, one or more motion vectors are encoded in the bit stream. These motion vectors allow the decoder to reconstruct a macroblock, called the predictive macroblock. The encoder subtracts the "predictive" macroblock from the macroblock to be encoded to form the "difference" macroblock. The encoder uses tools to compress the difference macroblock that are essentially similar to the tools used to compress an intra macroblock.

The type (I, P, or B) and structure (field or frame) of a picture determine the methods of motion compensation that can be used. The encoder chooses from among these methods for each macroblock in the picture. The encoder also selects which motion vectors to use with the selected motion compensation method for each macroblock. This process is referred to as motion estimation. In its preferred embodiment, the present invention deals with motion estimation for frame-structured pictures. The motion compensation methods for frame-structured pictures are now described.

A method of motion compensation is described by the macroblock mode and motion compensation mode used. There are four macroblock modes, intra (I) mode, forward (F) mode, backward (B) mode, and interpolative forward-backward (FB) mode. For I mode, no motion compensation is used. For the other macroblock modes, frame (FR) or field (FI) motion compensation modes can be used. (In some cases, another mode (dual prime) can also be used. Motion estimation methods for dual prime are not an object of the present invention, so we do not describe dual prime motion compensation). We refer to the combination of macroblock mode and motion compensation mode used by a macroblock as the motion compensation "method"; there are six such methods: F/FR, B/FR, FB/FR, F/FI, B/FI, FB/FI. These methods will all be described below.

A macroblock in any picture can be compressed with I macroblock mode. This is the only macroblock mode available in an I picture, and does not use motion compensation.

F macroblock mode can be used in a P or B picture but not in an I picture. When F macroblock mode is used, the predictive macroblock is formed from the most recently decoded top and bottom fields from anchor pictures that are to be displayed before the current picture (the previous anchor frame).

B or FB macroblock mode can be used in a B picture but not in I or P pictures. When B macroblock mode is used, the predictive macroblock is formed from the two most recently decoded anchor fields that are to be displayed after the current picture (the future anchor frame). When FB macroblock mode is used, the predictive macroblock is formed from the future anchor frame and the previous anchor frame.

The method of motion compensation that uses F macroblock mode and FR motion compensation mode (F/FR) can be described as follows. The encoder sends a single vector in the bit stream. This vector is used to generate a set of indices in the previous frame, and the predictive macroblock is the 16.times.16 region located at those indices. When this method of motion compensation is used, no distinction is made between the two fields; the previous frame and current macroblock are viewed as being single images (not two fields), and the predictive macroblock can start anywhere in the previous frame.

The B/FR method of motion compensation is the same as the F/FR method, except that the future frame, rather than the previous frame, is used in generating the predictive macroblock.

The method of motion compensation that uses F macroblock mode and FI motion compensation mode (F/FI) can be described as follows. The encoder sends two vectors in the bit stream. Each vector is used to form a 16.times.8 array of pixels from one of the fields in the previous frame. Two bits are sent to indicate which field of the reference frame is to be used with each vector. The predictive macroblock is formed by interleaving these two arrays; the first array provides the odd lines of the predictive macroblock and the second array provides the even lines. (Each array is used for different fields in the predictive macroblock).

The B/FI method of motion compensation is the same as the F/FI method, except that the future frame, rather than the previous frame, is used in generating the predictive macroblock.

The FB/FR method of motion compensation works as follows. The encoder sends two motion vectors, a forward vector and a backward vector. The forward vector is used to construct a macroblock from the previous frame the same way a vector is used to form the predictive macroblock for the F/FR method of motion compensation, and the backward vector is used to construct a macroblock from the future frame the same way a vector is used to form the predictive macroblock for the B/FR method of motion compensation. These two macroblocks are averaged to form the predictive macroblock.

The FB/FI method of motion compensation works as follows. The encoder sends four motion vectors, two forward vectors and two backward vectors. The forward vectors are used to construct a macroblock from the previous frame the same way two vectors are used to form the predictive macroblock for the F/FI method of motion compensation, and the backward vectors are used to construct a macroblock from the future frame the same way two vectors are used to form the predictive macroblock for the B/FI method of motion compensation. These two macroblocks are averaged to form the predictive macroblock.

The vectors sent for any mode of motion compensation can be in half-pixel units. In the case of the F/FR, F/FI, B/FR and B/FI methods of motion compensation, spatial interpolation is used to generate the predictive macroblock when the vectors used are in half-pixel units. In the case of the FB/FR and FB/FI methods, spatial interpolation is used to generate the macroblocks that are averaged to make the predictive macroblock when the vectors used are in half-pixel units.

The encoder performs motion estimation to determine the method of motion compensation and motion vectors to be used. One method that an encoder may use is to examine all legal combinations of vectors and motion compensation methods, calculate an error for each combination, and choose the combination with the smallest error. An example of an error measure is the norm of the difference macroblock that would be used by a particular combination of motion compensation method and motion vectors. Because this method (exhaustive search) is computationally intensive, it is rarely used in practice.

Aside from the need to code side information relating to the MB mode used to code each MB and any motion vectors associated with that mode, the coding of motion-compensated macroblocks is very similar to that of intramode MBs. Although there is a small difference in the quantisation, the model of division by w.sub.mn times QP still holds.

The MPEG-2 algorithm can be used with fixed bit-rate transmission media. However, the number of bits in each picture will not be exactly constant, due to the different types of picture processing, as well as the inherent variation with time of the spatio-temporal complexity of the scene being coded. The MPEG-2 algorithm uses a buffer-based rate control strategy to put meaningful bounds on the variation allowed in the bit-rate. A Video Buffer Verifier (VBV) is devised in the form of a virtual buffer, whose sole task is to place bounds on the number of bits used to code each picture so that the overall bit-rate equals the target allocation and the short-term deviation from the target is bounded. This rate control scheme can be explained as follows. Consider a system consisting of a buffer followed by a hypothetical decoder. The buffer is filled at a constant bit-rate with compressed data in a bit stream from the storage medium. Both the buffer size and the bit-rate are parameters which are transmitted in the compressed bit stream. After an initial delay, which is also derived from information in the bit stream, the hypothetical decoder instantaneously removes from the buffer all of the data associated with the first picture. Thereafter, at intervals equal to the picture rate of the sequence, the decoder removes all data associated with the earliest picture in the buffer.

In order that the bit stream satisfy the MPEG-2 rate control requirements, all the data for each picture is made available within the buffer at the instant it is needed by the decoder and the buffer never overflows. This availability requirement usually translates to upper and lower bounds on the number of bits allowed in each picture. The upper and lower bounds for a given picture depend on the number of bits used in all the pictures preceding it. It is the function of the encoder to produce bit streams which satisfy this requirement.

FIG. 4 is a block diagram of a simplified view of a conventional MPEG-2 encoder. Because MPEG-2 encoding is generally known in the art, we have not drawn all of the components of an MPEG-2 encoder, but instead concentrated on the major components and those that are needed to understand the aspects of this invention. In particular, we show the following components of an MPEG-2 encoder: frame memory 401, motion estimation unit 402, rate control unit 403, motion compensation unit 413, transformation unit 414, quantisation unit 415, variable length encoder unit 419, and output buffer 421. The input to the video encoder of FIG. 4 is the signal 409, containing the Y, Cb and Cr pixel data. The output is the compressed bit stream 422.

For the encoder of FIG. 4, the input pixel data is stored in the frame memory. The motion estimation unit 402 does motion estimation for each macroblock. In particular, for each macroblock the motion estimation unit decides which motion compensation method will be used and motion vector(s) will be used.

The motion estimation unit sends the motion compensation method and motion vector(s) as signal 412 to the motion compensation unit. This signal, together with pixel data retrieved from the frame memory as signal 411, is used by the motion compensation unit to compute the difference macroblock, which is sent as the signal 426 to the transform unit.

The transform unit segments the difference macroblock (signal 426) into 8.times.8 blocks and computes the DCT of each block. These are sent as the signal 425 to the quantisation unit 415.

The quantisation unit 415 quantises each DCT coefficient based on the quantisation parameter Qp sent as signal 417 from the rate control unit (described later). These quantised DCT coefficients are sent as the signal 424 to the variable length encoder unit.

For each macroblock, the variable length encoder unit produces a compressed representation of the quantised DCT coefficients (signal 424 from the quantisation unit) the macroblock mode, motion compensation mode and motion vectors (signal 416 from the motion estimation unit) and Qp (signal 418 from the rate control unit). The compressed macroblock is sent as the signal 420 to the output buffer 421.

The output buffer receives the compressed representation of each macroblock from the variable length encoder as signal 420. It then sends out the bits that it has received on a first come, first serve basis as the signal 422. A signal indicating the fullness of the output buffer is sent as signal 423 to the rate control unit.

The rate control decides the value of Qp for each macroblock. It will in general respectively increase or decrease the value of Qp for future macroblocks if the output buffer is respectively nearly full or nearly empty.

In "ISO-IEC/JTC1/SC29/WG11 Coded Representation of Picture and Audio Information: Test Model 5, Draft, 1993", a conventional motion estimation unit is described. We will now describe a motion estimation method similar to the method described in that reference. For each method of motion compensation (F/FR, F/FI, B/FR, B/FI, FB/FR, FB/FI), a candidate vector (or vector set) is chosen. The method that has the smallest "prediction error" is chosen as the method to use for that macroblock, and the candidate vector (or vector set) previously chosen for that method is the vector (or vector set) that will be used. A prediction error is a number that indicates the degree to which the predictive macroblock does not match the current macroblock (the macroblock being encoded). By way of example, a conventional motion estimation unit that always uses the "one-norm" of the difference macroblock as the prediction error is described. The one norm of a set of numbers is the sum of the absolute value of those numbers. Thus if we denote the pixel in row i and column j of a predictive macroblock as a(i,j) and the pixel in row i and column j of the current macroblock as c(i,j), then the one-norm of the difference macroblock, .DELTA..sub.a, is: ##EQU1##

For each method that does not use temporal interpolation (F/FR, F/FI, B/FR and B/FI), each vector (or vectors) in a given range are examined. For each vector (or vectors) the prediction error is computed. For each method, the vector or vector set that give the smallest prediction error is chosen as the candidate vector or vector set. For the FB/FR method, candidate vectors are the same vectors chosen as candidates for the F/FR and B/FR method. A separate computation is done to compute the prediction error for the FB/FR method with the given candidate vectors. For the FB/FI method, candidate vectors are the same vectors chosen as candidates for the F/FI and B/FI method. A separate computation is done to compute the prediction error for the FB/FI method with the given candidate vectors.

After a vector (or vector set) has been chosen for each method, the method and candidate vector (or set) with the smallest one-norm is chosen.

b. PREFERRED EMBODIMENT OF AN ENCODER

The present video encoder is an encoder of the form shown in FIG. 4 with a motion estimation unit as shown in FIG. 11. The operation of the motion estimation unit of FIG. 11 can be described as follows.

The video data is sent as signal 1102 to the memory 1104. The hierarchical field/frame computing engine 1108 reads video data stored in the memory as signal 1106 and, for each macroblock, computes the candidate vectors for F/FR, F/FI, B/FR and B/FI motion compensation methods, which are sent as signal 1101 to the interpolator and final decision maker 1114. The interpolator and final decision maker computes candidate motion vectors for the FB/FR and FB/FI methods and decides which motion compensation method to use.

The operation of an interpolator and final decision maker are conventional; e.g., the motion estimator in "ISO-IEC/JTC1/SC29/WG11 Coded Representation of Picture and Audio Information: Test Model 5, Draft, 1993" has an interpolator and final decision maker suitable for use with the motion estimation unit of FIG. 11.

The difference between the motion estimator shown in FIG. 11 and a conventional motion estimator, for example, the motion estimator in "ISO-IEC/JTC1/SC29/WG11 Coded Representation of Picture and Audio Information: Test Model 5, Draft, 1993", is that the motion estimator in FIG. 11 computes candidate motion vectors with a hierarchical field/frame computing engine (1108).

FIG. 5 is a more detailed block diagram of the hierarchical field/frame computing engine 1108. The video data (at full resolution) enters as signal 502, and goes to a memory device 504 (which stores the full resolution video data) and a scaler 506. The scaler performs field-based scaling of the input video to reduce its resolution, and outputs the resulting reduced resolution video data as signal 508. The reduced resolution video data provided by way of signal 508 is stored in a memory 510. (Field-based scaling means that each field is scaled to reduce its horizontal and/or vertical resolution, and the scaled fields are rearranged back into a frame of lower resolution.)

The field error computation unit 514 reads the reduced resolution video as the signal 512 from memory 510 and computes errors for different coarse vectors for field motion compensation mode and backward or forward macroblock mode (F/FI and B/FI motion compensation methods) for each macroblock. The vectors are referred to as coarse vectors because they are computed from reduced resolution data, so they do not describe the motion with as much precision or accuracy as vectors computed from the full resolution data. These errors and vectors are read as signal 516 by the field errors to frame errors unit 518, which computes, from the field errors, errors for different coarse motion vectors for frame motion compensation mode and backward or forward macroblock mode (F/FI and B/FI motion compensation methods) for each macroblock. In the preferred embodiment, the field errors to frame errors unit computes each frame error as the sum of the two field errors that are computed with data that correspond to the frame error. These errors and vectors (signal 520) as well as the field errors and vectors (signal 516) are read by the refine decision unit 522.

The refine decision unit 522 decides which coarse motion vectors to refine. For example, in one embodiment, the refine decision unit decides that, for each direction (forward for a P picture, forward and backward for a B picture), the coarse frame vector with the smallest error and for each of the top and bottom fields of each macroblock that coarse field vector with the smallest error will be refined. Data identifying the vectors to be refined are generated by the refine decision unit and then sent as signal 523 to the refine unit 525, which, by reading the full resolution pixel data from the memory 504 as signal 524 refines the coarse vectors, to produce the final candidate vectors as signal 526.

A first example of how the scaler works to perform field-based scaling can be seen by looking at FIGS. 7A and 7B. For this example, only horizontal scaling is performed. FIG. 7A shows a full resolution frame, and FIG. 7B shows the same frame scaled 4:1 horizontally. In this example, the scaling is done by averaging four pixels. The full resolution frame (7A) has 20 columns (A-X), whereas the reduced resolution frame (7B) has only five: the first is the average of columns A, B, C and D from FIG. 7A, the second is the average of columns E, F, G, H, and so on.

A second example of how the scaler performs field-based scaling can be seen by looking at FIGS. 8A and 8B. For this example, only vertical scaling is performed. FIG. 8A shows a full resolution frame, and FIG. 8B shows the same frame scaled 2:1 vertically. In this example, the scaling is done by averaging two pixels. The full resolution frame (8A) has 20 rows (A-X), whereas the reduced resolution frame (8B) has only ten: the first is the average of rows A and C from FIG. 8A, the second is the average of rows B and D, the third is the average of rows E and G, the fourth is the average of rows F and H, and so on. Note that in the reduced resolution frame (8B) the top field (odd rows) is formed by scaling data from the top field (odd rows) of the full resolution frame (8A). Similarly, in the reduced resolution frame (8B) the bottom field (even rows) is formed by scaling data from the bottom field (even rows) of the full resolution frame (8A).

FIGS. 9A and 9B show a reduced resolution reference frame and current macroblock where the scaling is done 2:1 horizontally and 2:1 vertically. FIG. 9A shows a reduced resolution reference frame of size 10.times.10 pixels (which means that the original frame was 20.times.20 pixels). FIG. 9B shows a reduced resolution current macroblock. Because full-resolution macroblocks are 16.times.16, the reduced resolution macroblock is 8.times.8. FIGS. 10A and 10B show the frame of FIG. 9A as two fields; FIG. 10A shows the top field, FIG. 10B shows the bottom field. FIGS. 10C and 10D show the macroblock of FIG. 9B as two fields of a macroblock; FIG. 10C shows the top field, and FIG. 10D shows the bottom field. FIGS. 9A, 9B, 10A, 10B, 10C and 10D will be used to give examples of the operation of the field error computation unit (514) and the field errors to frame errors unit (518).

Consider FIG. 10C, the top field of the macroblock. This region can be compared to eight similarly sized regions in the top field shown in FIG. 10A. The field error computation unit computes errors for each of these cases:

The field error computation unit also computes errors between the top macroblock field and the bottom reference field:

the bottom macroblock field and the top reference field:

and the bottom macroblock field and the bottom reference field:

For example, the error BT.sub.-- 0.sub.-- 1 is a measure of the difference between

If, for example, errors are computed with the one norm, then BT.sub.-- 0.sub.-- 1 would be the sum of the absolute values of the corresponding values in the above blocks. The error TB.sub.-- 1.sub.-- 1 is a measure of the difference between

These two errors can be combined to compute the error between the frame block (in the frame shown in FIG. 9A) that begins at location A1.sub.-- 1 and the (entire) macroblock (FIG. 9B). Indeed, the sum of the absolute pixels differences between is equal to the sum of BT.sub.-- 0.sub.-- 1 and TB.sub.-- 1.sub.-- 1. As mentioned, in the preferred embodiment, the field errors to frame errors unit computes each frame error as the sum of the two field errors that are computed with data that correspond to the frame error.

So for frame block above the frame error is computed as BT.sub.-- 0.sub.-- 1+TB.sub.-- 1.sub.-- 1. A comprehensive list of how the frame errors for all matches in FIGS. 9A and 9B are computed follows:

In the preferred embodiment, the field errors to frame errors unit computes frame errors following the pattern evident from the above listing; the coarse field error for the top field of the reference frame predicting the top field of the current macroblock with an offset of x pixels horizontally and y pixels vertically is added to the coarse field error for the bottom field of the reference frame predicting the bottom field of the current macroblock with an offset of x pixels horizontally and y pixels vertically to get a frame error corresponding to an offset of x pixels horizontally and 2y pixels vertically, and the coarse field error for the bottom field of the reference frame predicting the top field of the current macroblock with an offset of x pixels horizontally and y pixels vertically is added to the coarse field error for the top field of the reference frame predicting the bottom field of the current macroblock with an offset of x pixels horizontally and y+1 pixels vertically to get a frame error corresponding to an offset of x pixels horizontally and 2y+1 pixels vertically.

As previously discussed, in one embodiment the refine decision unit decides that, for each direction (forward for a P picture, forward and backward for a B picture), the coarse frame vector with the smallest error and for each of the top and bottom fields of each macroblock that coarse field vector with the smallest error will be refined. In another embodiment, for each macroblock and each direction the refine decision unit refines only the frame vector or the field vector; the former is done if the field errors are substantially larger than the frame error (for example, they sum to 1.5 times the frame error or more) and the later is done otherwise.

The refine unit (525) works as follows. A coarse (field or frame) vector is refined by scaling the coarse vector to compensate for the fact that it was computed from scaled video data. For example, suppose the scaler (506) scales the video by a factor of 4:1 horizontally and 2:1 vertically. A coarse vector of x horizontal pixels and y vertical pixels is scaled to a vector of 4x horizontal pixels and 2y vertical pixels. Then the errors for vectors in a rectangular region centered at the scaled vector are computed; for the previous example, the refine unit could look at all vectors with horizontal component in the interval ›4x-7, 4x+7! and vertical components in the interval ›4y-3, 4y+3!. The vector with the smallest error is then chosen.

A block diagram for the encoder of the present invention connected to a decoder is shown in FIG. 12. The video encoder 1202 contains a motion estimation unit 1204 which contains a hierarchical field/frame computing engine 1206. The video encoder produces a compressed video stream 1208 which is sent to the video decoder 1210. The video decoder decompresses the video, and send the decompressed video as signal 1212 to the display or storage device 1214.

An overview of the motion estimation method used in the present invention is shown in FIG. 6. In step 602, the current and reference frame are input. In step 604, the reference frame is scaled to a smaller frame, and in step 606 the current frame is scaled to a smaller frame; in both cases, field-based scaling is used. In step 608 field-based errors are computed by comparing data in each field of each macroblock in the current frame to similarly sized regions in reference frames. In step 610 frame-based errors are computed from the field-based errors. In step 612, field vectors are chosen as refine candidates. In step 614, frame vectors are chosen as refine candidates. In step 616, decisions are made as to which of the refine candidates will be refined. In step 618, the refine candidates are refined.

The present invention can be embodied in an application specific integrated circuit (ASIC) or as program code executing on a general purpose computer.

Now that the invention has been described by way of the preferred embodiment, various modifications and improvements will occur to those of skill in the art. Thus, it should be understood that the preferred embodiment has been provided as an example and not as a limitation. The scope of the invention is defined by the appended claims.