Motion estimation processor for a digital video encoder

[0002] This is a continuation-in-part of our commonly assigned, copending U.S. application Ser. No. 08/605,559, filed Feb. 22, 1996, now U.S. Pat. No. 5,768,537, for SCALABLE MPEG-2 COMPLIANT VIDEO ENCODER.

[0003] The invention relates to apparatus for encoding digital visual images, including spatial (Intra-picture) and temporal (inter-picture) compression, that is redundancy within a picture and redundancy between pictures. Redundancy within pictures is reduced, or even eliminated, by the use of the discrete cosine transform, quantization, and variable length encoding. Redundancy between pictures is reduced, or even eliminated, through the use of motion vectors. Specifically, the invention relates to an encoder, as a scalable encoder system, having a motion estimation processor (MEPROC). That is, a scalable architecture MPEG-2 compliant digital video encoder system having an I-frame only video encoder module with a Discrete Cosine Transform processor, a quantization unit, a variable length encoder, a FIFO buffer, and a compressed store interface, for generating an I-frame containing bitstream. For IPB bitstreams the system includes a second processor element with a motion estimation processor (MEPROC), reference memory interface, motion estimation and compensation capability, inverse quantization, and inverse discrete cosine transformation, and motion compensation means; and at least one third processor element motion estimation. The system can be in the form of a single integrated circuit chip, or a plurality of integrated circuit chips, that is one for each processor, the I-frame video encoder module, the second processor element, and the third processor element. There can be one or more of the third processor units.

[0004] Within the past decade, the advent of world-wide electronic communications systems has enhanced the way in which people can send and receive information. In particular, the capabilities of real-time video and audio systems have greatly improved in recent years. In order to provide services such as video-on-demand and videoconferencing to subscribers, an enormous amount of network bandwidth is required. In fact, network bandwidth is often the main inhibitor to the effectiveness of such systems.

[0005] In order to overcome the constraints imposed by networks, compression systems have emerged. These systems reduce the amount of video and audio data which must be transmitted by removing redundancy in the picture sequence. At the receiving end, the picture sequence is uncompressed and may be displayed in real-time.

[0006] One example of an emerging video compression standard is the Moving Picture Experts Group (“MPEG-2”) standard. Within the MPEG-2 standard, video compression is defined both within a given picture and between pictures. Video compression within a picture is accomplished by conversion of the digital image from the time domain to the frequency domain by a discrete cosine transform, quantization, and variable length coding, such as Huffman coding. Video compression between pictures is accomplished via a process referred to as motion estimation and compensation, in which a motion vector plus difference data is used to describe the translation of a set of picture elements (pels) from one picture to another.

[0007] The ISO MPEG-2 standard specifies only the syntax of bitstream and semantics of the decoding process. The choice of coding parameters and trade-offs in performance versus complexity is left to the encoder developers. Since MPEG-2 encoder development is complex and expensive, an encoder solution that is flexible for different applications and that can expand as the customer's needs evolve, that is, a scalable encoder, is desirable.

[0008] One computation intensive aspect of MPEG-2 encoding is motion estimation and compensation. This involves such computation intensive steps as memory fetches and stores, searches, comparisons, matches, and motion vector calculations. A need exists for a fast search for a best-match macroblock in a search window on downsampled full pixel values.

[0009] A further need exists for a fast search on non-downsampled reconstructed data around the best match macroblock to find a more precise match to use for motion vector coding.

[0010] It is a primary object of the invention to provide a fast search for a best-match macroblock in a search window on downsampled full pixel values.

[0011] It is a further object of the invention to provide a processor for a fast search on non-downsampled reconstructed data around the best match macroblock to find a more precise match to use for motion vector coding.

[0012] It is a still further object of the invention to provide a processor that performs a hierarchal search motion estimation or a full search motion estimation based, for example, on host commands.

[0013] It is a still further object of the invention to provide for a motion estimation processor to determine the best-match of the motion estimation search, with hand-shaking for pipeline control of coprocessors and with determination of the memory addresses used to search the picture.

[0014] It is a still further object of the invention to provide for calculation of the motion vector and to send the motion vector data to the Variable Length Encoder for entropy coding.

[0015] It is a still further object of the invention to weight best-match motion vectors in order to bias motion vectors as close to the current macroblock as possible.

[0016] These and other objectives of the invention are achieved by the digital video encoder of the invention. The digital video encoder processor system has a video encoder module with a Discrete Cosine Transform processor, a quantization unit, a variable length encoder, a FIFO buffer, and a compressed store interface, for generating an I-frame containing bitstream. For encoding bitstreams with temporal compression, that is, IP and IPB bitstreams, the encoder system includes a motion estimation processor (MEPROC) element with a reference memory interface, motion estimation and compensation capability, inverse quantization, inverse discrete cosine transformation, and motion compensation means. The system can be in the form of a single integrated circuit chip, or a plurality of integrated circuit chips.

[0017] The invention may be more clearly understood by reference to the Figures appended hereto.

[0018] FIG. 1 shows a flow diagram of a generalized MPEG-2 compliant encoder 11, including a discrete cosine transformer 21, a quantizer 23, a variable length coder 25, an inverse quantizer 29, an inverse discrete cosine transformer 31, motion compensation 41, frame memory 42, and motion estimation 43. The data paths include the i^thpicture input 111, difference data 112, motion vectors 113, the picture output 121, the feedback picture for motion estimation and compensation 131, and the motion compensated picture 101. This FIGURE has the assumptions that the i^thpictures exists in Frame Memory or Frame Store 42, and that the i+1^thpicture is being encoded with motion estimation.

[0019] FIG. 2 illustrates the I, P, and B pictures, examples of their display and transmission orders, and forward, and backward motion prediction.

[0020] FIG. 3 illustrates the search from the motion estimation block in the current frame or picture to the best matching block in subsequent or previous frame or picture. Elements 211 and 211′ represent the same location in both pictures.

[0021] FIG. 4 illustrates the movement of blocks in accordance with the motion vectors from their position in a previous picture to a new picture, and the previous picture's blocks adjusted after using motion vectors.

[0022] FIG. 5 shows the combination of three encoder chips of the invention. These are the Intra-chip or Intra-processor 601, the Reference-chip or Reference-processor 901, also referred to equivalently herein as a Reconstruction-chip or Reconstruction-processor 901, the Search-chip, Search-processor, or hierarchal search processor 801, and associated RAM chips 531, 533, and 535, including DRAM chips, 531 and 533, and SRAM chip 535. The Intra-chip or Intra-processor, 601, contains the host processor interface, 541. The intra-chip processor 601 receives digitized filtered video input 542, and produces a compressed video output 543.

[0023] FIG. 6 shows an I-frame video encoder module 601 with a host interface 611, an internal RISC processor 621, an interface to motion estimation means 631, a pixel interface 641 for receiving pixel data from a pixel bus 542, a frame memory interface 651 receiving frame data from and sending frame data to an external DRAM 653, a Discrete Cosine Transform (DCT) processor or coprocessor 671, a quantization unit 673, a variable length encoder 675, a FIFO buffer 677, and a compressed store interface 679.

[0024] FIG. 7 shows a frame memory map 701, with processor private storage 711 and five memory segments 721, 723, 725, 727, and 729.

[0025] FIG. 8 shows an S chip or processor 801, with a search memory interface 811, a Search-input buffer 821, Search-motion estimation 803, and an X-chip interface 831.

[0026] FIG. 9 shows a Reference-chip or processor 901 with a motion estimation processor (MEPROC) 900, a reference memory interface 911, a Reference-input buffer 921, Reference-motion estimation 903, an IR chip or processor interface 931, a Reference-chip or processor element 901, inverse quantization (IQ) 941, an inverse discrete cosine transform unit (IDCT) 943, and error prediction and motion compensation 945.

[0027] FIG. 10 shows the Motion Estimation Processor (MEPROC) 900 of the invention, including the hierarchal search unit 801, the variable length encoder 675, and a dynamically partitionable digital video encoder processor 621. A search unit communication digital video encoder processor 621. A search unit communication bus 911 provides best match difference/offset communication between the hierarchal search unit 801 and the Motion Estimation Processor 900, while a processor communication bus 913 provides communication between the Motion Estimation Processor (MEPROC) 900 and the dynamically partitionable digital video encoder processor 621. The motion estimation unit further includes a full resolution search unit 921 and a half pel search unit 923, as well as a dual prime search unit 925, and a frame difference unit 927, both of which receive inputs from the memory controller 931. Also shown is an inverse quantization unit 941, and an inverse discrete cosine transform unit 943, as well as a motion adjustment unit 951.

[0028] FIG. 11 shows the number and types of search vectors that the motion estimation processor of the invention can process. To be noted is that as used in FIG. 11, interlaced and field are equivalent terms, and, as also used in FIG. 11, progressive and frame are equivalent terms.

[0029] The invention relates to MPEG and HDTV compliant encoders, including scalable MPEG and HDTV compliant encoders, and encoding processes. The encoding functions performed by the encoder include data input, spatial compression, motion estimation and compensation, macroblock type generation, data reconstruction, entropy coding, and data output. Spatial compression includes discrete cosine transformation (DCT), quantization, and entropy encoding. Temporal compression includes intensive reconstructive processing, such as inverse discrete cosine transformation, inverse quantization, and motion compensation. Motion estimation and compensation are the temporal compression functions. Spatial and temporal compression are repetitive functions, including memory fetching and writing, searching, comparing, and basic logic and arithmetic functions, all with or cumulatively resulting in high computational requirements.

[0030] More particularly the invention relates to a processor, for example, a scalable processor, for performing spatial and temporal compression including discrete cosine transformation, quantization, entropy encoding, motion estimation, motion compensation, and prediction, and even more particularly to a motion estimation processor within the system for accomplishing temporal compression.

[0031] The processor system of the invention has an I-frame only video encoder module with a Discrete Cosine Transform processor, a quantization unit, a variable length encoder, a FIFO buffer, and a compressed store interface, for generating an I-frame containing bitstream. For IPB bitstreams the system further includes the motion estimation processor (MEPROC) of the invention with a reference memory interface, motion estimation and compensation capability, inverse quantization, and inverse discrete cosine transformation, and motion compensation means. The system can be in the form of a single integrated circuit chip, or a plurality of integrated circuit chips.

[0032] The first compression step is the elimination of spatial redundancy, for example, the elimination of spatial redundancy in a still picture, that is, an “I” frame picture. Spatial redundancy is the redundancy within a picture. Because of the block based nature of the motion compensation process, described below, it was desirable for the MPEG-2 Draft Standard to use a block based method of reducing spatial redundancy. The method of choice is the Discrete Cosine Transformation, and Discrete Cosine Transform coding of the picture. Discrete Cosine Transform coding is combined with weighted scalar quantization and run length coding to achieve still further levels of compression.

[0033] The Discrete Cosine Transformation is an orthogonal transformation. Orthogonal transformations, because they have a frequency domain interpretation, are filter bank oriented. The Discrete Cosine Transformation is also localized. That is, the encoding process samples on an 8×8 spatial window which is sufficient to compute 64 transform coefficients or sub-bands.

[0034] Another advantage of the Discrete Cosine Transformation is that fast encoding and decoding algorithms are available. Additionally, the sub-band decomposition of the Discrete Cosine Transformation is sufficiently well behaved to allow effective use of psychovisual criteria.

[0035] After discrete cosine transformation, many of the frequency coefficients are small or even zero, especially the coefficients for high spatial frequencies. The amplitudes for these terms can be disregarded. These coefficients are organized into a zig-zag pattern, and converted into run-amplitude (run-level) pairs. Each pair indicates the number of zero coefficients and the amplitude of the non-zero coefficient. This is coded in a Variable Length Code.

[0036] Motion compensation is used to reduce or even eliminate redundancy between pictures. Motion compensation exploits temporal redundancy by dividing the current picture into blocks, for example, macroblocks, and then searching in previously transmitted pictures for a nearby block with similar content. Only the difference between the current block pels and the predicted block pels extracted from the reference picture is actually compressed for transmission and thereafter transmitted.

[0037] The simplest method of motion compensation and prediction is to record the luminance and chrominance, i.e., intensity and color, of every pixel in an “I” picture, then record changes of luminance and chrominance, i.e., intensity and color for every specific pixel in the subsequent picture. However, this is uneconomical in transmission medium bandwidth, memory, processor capacity, and processing time because objects move between pictures, that is, pixel contents move from one location in one picture to a different location in a subsequent picture. A more advanced idea is to use a previous or subsequent picture to predict where a block of pixels will be in a subsequent or previous picture or pictures, for example, with motion vectors, and to write the result as “predicted pictures” or “P” pictures. More particularly, this involves making a best estimate or prediction of where the pixels or macroblocks of pixels of the i^thpicture will be in the i−1^thor i+1^thpicture. It is one step further to use both subsequent and previous pictures to predict where a block of pixels will be in an intermediate or “B” picture.

[0038] To be noted is that the picture encoding order and the picture transmission order do not necessarily match the picture display order. See FIG. 2. For I-P-B systems the input picture transmission order is different from the encoding order, and the input pictures must be temporarily stored until used for encoding. A buffer stores this input until it is used.

[0039] For purposes of illustration, a generalized flow chart of MPEG compliant encoding is shown in FIG. 1. In the flow chart the images of the i^thpicture and the i+1^thpicture are processed to generate motion vectors. The motion vectors predict where a macroblock of pixels will be in a prior and/or subsequent picture. The use of the motion vectors instead of full images is a key aspect of temporal compression in the MPEG and HDTV standards. As shown in FIG. 1 the motion vectors, once generated, are used for the translation of the macroblocks of pixels, from the i^thpicture to the i+1^thpicture.

[0040] As shown in FIG. 1, in the encoding process, the images of the i^thpicture and the i+1^thpicture are processed in the encoder 11 to generate motion vectors which are the form in which, for example, the i+1^thand subsequent pictures are encoded and transmitted. An input image 111 of a subsequent picture goes to the Motion Estimation unit 43 of the encoder. Motion vectors 113 are formed as the output of the Motion Estimation unit 43. These vectors are used by the Motion Compensation Unit 41 to retrieve macroblock data from previous and/or future pictures, referred to as “reference” data, for output by this unit. One output of the Motion Compensation Unit 41 is negatively summed with the output from the Motion Estimation unit 43 and goes to the input of the Discrete Cosine Transformer 21. The output of the Discrete Cosine Transformer 21 is quantized in a Quantizer 23. The output of the Quantizer 23 is split into two outputs, 121 and 131; one output 121 goes to a downstream element 25 for further compression and processing before transmission, such as to a run length encoder; the other output 131 goes through reconstruction of the encoded macroblock of pixels for storage in Frame Memory 42. In the encoder shown for purposes of illustration, this second output 131 goes through an inverse quantization 29 and an inverse discrete cosine transform 31 to return a lossy version of the difference macroblock. This data is summed with the output of the Motion Compensation unit 41 and returns a lossy version of the original picture to the Frame Memory 42.

[0041] As shown in FIG. 2, there are three types of pictures.

[0042] There are “Intra pictures” or “I” pictures which are encoded and transmitted whole, and do not require motion vectors to be defined. These “I” pictures serve as a source of motion vectors. There are “Predicted pictures” or “P” pictures which are formed by motion vectors from a previous picture and can serve as a source of motion vectors for further pictures. Finally, there are “Bidirectional pictures” or “B” pictures which are formed by motion vectors from two other pictures, one past and one future, and can not serve as a source of motion vectors. Motion vectors are generated from “I” and “P” pictures, and are used to form “P” and “B” pictures.

[0043] One method by which motion estimation is carried out, shown in FIG. 3, is by a search from a macroblock 211 of an i^thpicture throughout a region of the next picture to find the best match macroblock 213. Translating the macroblocks in this way yields a pattern of macroblocks for the i+1^thpicture, as shown in FIG. 4.

[0044] In this way the i^thpicture is changed a small amount, e.g., by motion vectors and difference data, to generate the i+1^thpicture. What is encoded are the motion vectors and difference data, and not the i+1^thpicture itself. Motion vectors translate position of an image from picture to picture, while difference data carries changes in chrominance, luminance, and saturation, that is, changes in shading and illumination.

[0045] Returning to FIG. 3, we look for a good match by starting from the same location in the i^thpicture as in the i+1^thpicture.

[0046] A search window is created in the i^thpicture. We search for a best match within this search window. Once found, the best match motion vectors for the macroblock are coded. The coding of the best match macroblock includes a motion vector, that is, how many pixels in the y direction and how many pixels in the x direction is the best match displaced in the next picture. Also encoded is difference data, also referred to as the “prediction error”, which is the difference in chrominance and luminance between the current macroblock and the best match reference macroblock.

[0047] The operational functions of an MPEG-2 encoder are implemented in three basic elements or devices: an I or Intra element or device, an R or Reconstruction or Reference element or device, and an S or Search element or device. The functions are partitioned according to application needs, silicon size, tools and design complexity, and performance.

[0048] As shown in FIG. 6 all external communications including it pixel interface 641, host interface 611, and output data interface 679 are done in a single I device 601. The I device 601 is the master interface of the encoder, and is a basic requirement in any video compression application using the chip set of the invention, as shown in FIG. 5. A programmable processor 621 along with the entropy coding functions, that is the Discrete Cosine Transform processor unit 671, the quantization unit 673, and the variable length encoder unit 675, are incorporated in this chip. As a result, this device could be used in an application requiring encoding of I-only pictures. A reconstruction interface is also added to allow functional expansions. The processing functions applied prior to encoding are also included in this device.

[0049] Reconstructive processing of the macroblock is needed for all non I-picture coding, that is P picture and B picture encoding. Functions such as Inverse Discrete Cosine Transformation 943 (IDCT), Inverse Quantization 941 (IQ), and Motion Compensation 945 (MC) are consolidated in a single chip, the R chip or R processor, 901, as shown in FIG. 9. A small motion estimation function capability with a programmable processor is also added to handle low motion applications. A search result interface is installed for higher motion applications. As a result, the I and R-chips together could be used in applications with less motion such as distance learning, video conferencing, surveillance, etc.

[0050] Motion estimation is a repetitive function and has high computational requirements. Hardware, including the Search-chip or processor 801 shown in FIG. 8, and the R-chip shown in FIG. 9, including the Motion Estimation Processor (MEPROC) 900, also shown in FIG. 9, is dedicated to this function. An expansion interface is installed to attain a larger search range.

[0051] Chip Partition

[0052] The connections of the three encoder chips is shown in FIG. 5. FIG. 5 shows the combination of three encoder chips in one embodiment of the invention. These are the Intra-chip or Intra-processor 601, the Reference-chip or Reference-processor 901, the Search-chip or Search-processor 801, and associated RAM chips 531, 533, and 535, including DRAM chips and SRAM chips. The Intra-chip or Intra-processor is the host processor interface, it receives digitized filtered video input 542, and it produces a compressed video output 543.

[0053] I-chip

[0054] The I-chip 501, shown in greater detail in FIG. 6 handles the input data 542 and output bitstream 543 of the encoder system. Incoming pixel data is stored in frame format in an external DRAM, referred to as a frame store. This chip performs the core functions necessary for I frame encoding. Pixel data is converted from the RGB format to the YCbCr format, if needed. Pixel data is monitored for scene changes and for repeat fields created by 3:2 pulldown. Incoming pixel data is also adjusted to create HHR output format. The encoder can receive interleaved (field) or progressive (frame) input format and output field or frame encoded data, regardless of how it was input. Input 4:2:2 data can be encoded as 4:2:2 or 4:2:0 output. The on-chip RISC processor 621 is responsible for adaptive DCT, adaptive quantization, and rate control. The processor has a dynamically partitionable structure that allows it to operate as a 4 byte engine or four 1 byte engines. This is described in our commonly assigned, copending U.S. application Ser. No. 08/411,239 filed Mar. 27, 1995 by Charles Boice, John M. Kaczmarczyk, Agnes Ngai, and Robert C. Woodard for DYNAMICALLY PARTITIONABLE DIGITAL VIDEO PROCESSOR, now U.S. Pat. No. 5,644,504, the disclosure of which is incorporated herein by reference.

[0055] The encoded macroblock is merged with header information as described in our commonly assigned, copending U.S. application Ser. No. 08/410,951, filed Mar. 27, 1995 by James D. Greenfield, Diane M. Mauersberg, and Agnes Ngai, for APPARATUS FOR HEADER GENERATION, now U.S. Pat. No. 5,526,054, the disclosure of which is hereby incorporated herein by reference. This creates the final MPEG-2 or MPEG-1 output bitstream which the encoder can store to an external DRAM or ship to a FIFO, for example, through compressed store interface 679. When the picture is stored to DRAM it can be read out by the user through the host interface in non-real time.

[0056] R-chip

[0057] The R chip 901, also referred to as the Refinement chip or processor or the Reconstruction chip or processor, shown in FIG. 9, including the Motion Estimation Processor (MEPROC) 900, shown in FIG. 10, is responsible for search motion estimation refinement and reconstruction of pictures for motion compensation. External DRAM is used to support the motion estimation function. The R chip or processor functional units perform all the base functions required for reconstruction of pictures and motion estimation.

[0058] The primary functions of the processor are macroblock type decisions, adjusting search range per picture, and motion estimation assists. Both quantizer data and Search chip search results are received through a common chip interface. Quantized data is then dequantized using up to four matrix tables. The IDCT converts the coefficients to pixel data via a two dimensional inverse transform. This reconstructed picture data is saved as reference data by the memory interface for subsequent picture coding. The motion estimation can support field, frame, dual prime, bidirectional motion types to half pel resolution along with I, P and B pictures.

[0059] The two chip configuration (Intra- & Refinement/Reconstruction-chips) can support up to +/−8H and +/− 7V search range and the 3 chip configuration (Intra-, Refinement/Reconstruction, & Search chips) can support up to +/−64H and +/−56V. As motion estimation results are needed, the search window size and best match results are determined, and frame difference data is generated.

[0060] Search-chip

[0061] The Search-chip 801, shown in FIG. 8, including some of the functions of the Motion Estimation Processor 900, shown in FIG. 10, is responsible for the bulk of the motion estimation. The purpose of motion estimation is to find the location of a macroblock from the current picture (current picture macroblock or “CMB”) in the reference picture. This location is determined by finding the best match, which is determined by comparing the CMB data to the reference pictures data and factoring in a bias, which may be based on the motion of previous pictures.

[0062] The entire reference picture cannot be searched in real time. Therefore, a subset of the reference picture is searched. This subset is called the Search Window. See FIG. 3. The larger the search window, the higher the chance of finding an exact match for the CMB. The search window can be significantly increased by employing additional Search-chips 801. Effective motion estimation produces higher quality video and highly compressed bit streams. The Search-chip receives the search window parameters from the motion estimation processor 900 on the Refinement/Reconstruction-chip 901 and receives luminance picture data in either frame or field format from the Intra-chip 601, based on the picture structure.

[0063] The reference pictures are stored in off-chip SRAM in frame format. The motion estimation unit performs field searches on the CMB and the reference picture. Four field results are calculated along with a frame result for frame structured pictures. The results are in the form of difference data and are biased, based, for example, on previous pictures motion characteristics. The biased difference data along with motion vectors are sent to the R-chip 901.

[0064] Processing flow

[0065] The I-chip 601 contains both the pre-processing and entropy coding functions. The pre-processing functions are performed prior to any coding functions. The entropy coding is one of the last portions of picture processing. Its block diagram is shown in FIG. 6.

[0066] Host interface

[0067] A host interface 541 is installed on the Intra-chip 601, and serves as the main control channel between the encoder chip set and its external world. This interface is a generic 16 bit data and 8 bit address RAM-type protocol. Registers defined at this interface include commands, configuration parameters, encoding parameters, initialization data, mailbox, etc. Host commands include start encode, stop encode, retrieve compressed picture from output DRAM, etc. Configuration parameters include memory size, memory type, number of chips installed in the encoder system, etc.

[0068] Encoding parameters can be set at power on or can be modified at a picture boundary to guide the encoding process. These parameters include video input format versus video output format, users matrix tables, intra VLC table, ZZ scan pattern, field/frame picture coding, number of pictures in a sequence, number of pictures in a GOP, number of B pictures, number of reference fields, and user specific data, among others. This interface is also used to initialize the chip set. There are two internal processors in the encoder chip set. Both processors' instructions are downloaded through this interface. In addition there are buffers that require specific contents in order to function properly are also initialized via this interface.

[0069] Mailbox is a communication mechanism between the on-chip processor and external processor. When a command or new information is sent to the on-chip processor via the mailbox register, with the correct level of processor code, the new command is implemented. These registers provide flexibility. The defined functions could be selected or de-selected during the coding process by host writes. A stack is also installed at this interface to allow register changes during coding process. The stack is, for example, twelve deep. Host writes will only be written into the stack if the encoder is busy in a picture encoding. Information written into the stack will be processed at the end of current picture processing. The encoder appears busy to the external processor until the stack is empty. This design reduces the communication time between picture processings and allows maximum coding time.

[0070] Pixel interface

[0071] The pixel interface is a 24 bit pixel interface that is used to receive RGB digital input. It can also handle 16 or 24 bit YCbCr input data. A color conversion circuitry, scene change detection logic, and 3/2 pulldown inversion functions are also installed at this interface.

[0072] The color conversion, a form of data reduction, is ready to convert the input data to 4:2:2 or 4:2:0 chrominance encoding format.

[0073] Every location in a picture is represented by luminance and chrominance pixel data. As specified in the MPEG-2 standard, YCbCr data is the input data format for compression and output of decompression. For RGB input data, the input must first be converted into 4:2:2 format prior to any encoding process. If the input data is in 4:2:2 YCbCr format, this means every location in a picture is represented by 8 bits of luminance data and 8 bits of alternative color Cb and Cr data. If the input is in 4:2:0 YCbCr format, this means every location in a picture is presented by 8 bits of luminance data and horizontally and vertically subsampled color Cb and Cr data. The unnecessary and redundant information is removed by the color conversion process and/or 4:2:2 to 4:2:0 decimation at the input stage to achieve one step of compression and to minimize the amount of data flowing through the remaining encoder. This reduces the performance requirement in the remaining devices.

[0074] To cover a wide range of applications, the MPEG-2 standard documents many coding tools and options for the compression process. However, the trade-offs between quality/performance versus complexity for a given application is left for the encoder developers. Many of the coding options are adaptive within a picture, either at the picture level or at the macroblock level. This flexibility allows increased bitrate controls. Dynamic and adaptive changes of coding options could be applied to future coding based on the present information or it could also be applied to present data based on future information. Scene change detection, a look-ahead mechanism that collects picture information prior to the encoding process, provides much more efficient control. Scene change detection indicates large variances between pictures and also complexity differences. The scene change detection calculation is performed on the input data; there are no extra data flows or bandwidth requirements on the remaining functions. Since the input picture order is different from the encoding order, up to three pictures of information are pre-processed, through the scene change detection logic. The scene change detection logic can be used to regulate the quality of the picture being processed. This level of look ahead allows the encoder to dynamically change coding options at both the beginning it and the middle of picture processing.

[0075] If 3/2 pulldown inversion is enabled, the input data contains redundant or repeat fields. To be more efficient, the redundant data must be removed prior to encoding. Repeat field detection requires at least one field data be saved. The on-chip storage space requirement for repeat field detection makes it more economical to save the field data in external memory. The input data is first saved in frame store DRAM and has to be retrieved for repeat field detection and picture encoding. The detection scheme is based on a 3/2 pattern. With effective 3/2 PDI logic, for every thirty input pictures, only twenty-four pictures would be encoded after the 3/2 pulldown inversion is applied. The remaining memory bandwidth could then be used for repeat field data fetch. To minimize memory traffic, the following scheme is used: if the input data is odd field first, then the detection is performed on odd field data first, and even field data detection will be performed after a repeat odd field is detected. If the input data is even field first, then the reverse takes place. As a byte of data is received at the pixel interface, the same byte location in the previous field of the same parity is retrieved from frame store memory. A repeat field is determined at the end of field picture input. If the field is a repeat field, then its memory location will be used for input of the next field of the same parity. This eliminates memory fetch complexity during picture encoding.

[0076] Frame memory interface

[0077] The frame memory interface is shown in FIG. 7. At the output of the pixel interface, the input data is ready to be stored into an external DRAM attached to the Intra-chip, frame memory. This frame memory is only used to save the input picture (current data) until it is ready for encoding. Traffic at this interface is roughly two times the input data transmission rate. A 32 bit data bus is used to support the DRAM, e.g., a 70 ns DRAM. For I and IP coding format, the input picture order is the same as the picture encoding order. For this reason, encoding starts when one macroblock of data is available. In this configuration, the frame memory is divided into six segments, five for input picture data and one for on-chip processor use. A segment of frame memory is selected for each input picture. Data in the picture is stored sequentially as offset of the beginning address as specified by the chosen segment. Each segment is one-quarter of a picture size. Four consecutive segments are used for each input picture. The five segments are used in rotation. The memory partition is shown in FIG. 7.

[0078] When the first input picture is received, it is stored into segment 4. Since each segment size is only one-quarter of a picture, the first picture uses segment 4, 3, 2, and 1. The second input picture is stored in segment 0, 4, 3, and 2. The third picture is stored in segment 1, 0, 4, and 3. The fourth picture is stored in segment 2, 1, 0, and 4. The fifth picture uses segment 3, 2, 1, and 0. Then the segment usage repeats again. This scheme allows a minimal memory requirement, 1 MB DRAM, for I and IP configurations. For IPB coding format, the input picture order is different from the encoding order, as shown in FIG. 2. Thus, an input picture must be saved entirely until it is ready to be used. In this case, the memory size is 2 MB for NTSC, and 4 MB for PAL. The frame memory is divided into five segments, four for input picture and one for on-chip processor use. Each segment is equal to the picture size. It is used in similar fashion to the non-IPB format. This scheme allows scalable memory requirements based on the coding formats.

[0079] The main traffic of the frame memory is comprised of input data store, 3/2 pulldown inversion data fetch, and encode data fetch. A priority scheme is employed at the frame memory interface with input data store having the highest priority and pulldown inversion data fetch the lowest priority. Input data store is issued when 32B or more data is accumulated in the pixel interface. Data is stored continuously into DRAM, 4 bytes at a time, until there is less than 32B data in the pixel interface, and a pending memory data fetch will then be serviced. The encode data fetch is a 16 by 16 byte macroblock. This fetch is dynamically interruptive at any DRAM row address by an input data store request. The interruptive fetch prevents data overrun at the pixel interface.

[0080] Macroblock data is pre-fetched to prevent coding pipeline stall. When the macroblock data is available, the coding process begins. The macroblock data flow depends on the picture type being processed. A predictive picture processing is assumed for the purpose of this description. For a P picture, the current macroblock data is delivered to all three devices simultaneously. The data usage in each chip is different, and the time when the data is used, is also different. The logical flow of this macroblock data, when it is received by all receiving devices, is from the S-chip 801 to the R-chip 901, and then back to the I-chip 601.

[0081] Processing in the Search-chip

[0082] Search-input buffer

[0083] In the Search-chip 801, shown in FIG. 8 the current macroblock data is primarily used in motion estimation. Depending on the search format selected by the user, the macroblock data is either downsampled 4 to 1, 2 to 1, or remain as 1 to 1 in the input buffer. A single Search-chip 801 provides the largest search range in the 4 to 1 format, and the least in the 1 to 1 format. The downsampled data in both the 4 to 1 and 2 to 1 format are carried out horizontally. This scheme eliminates the complexity of frame and field motion search with the same downsampled data. The downsampled data is saved in search memory, the external memory attached to the Search-chip, where it is to be used as reference data on the subsequent picture coding process. Input data is used in the motion estimation, and provides a more precise difference between the two picture data. At the same time, the data of the previously encoded reference picture in search memory is fetched for motion estimation. The amount of reference data to be fetched for each macroblock processing depends on the macroblock location and the search range.

[0084] S-motion estimation

[0085] To conserve chip real estate (silicon area), the on-chip reference data buffers in the motion estimation unit can contain 20 out of the 128 lines in the search window at a time. The reference data is fetched as the search process continues. The reference data buffers are comprised of two equal sized units. One of these units is used for odd line data and the other one is for even line data. The two buffers are separate entities. Thus, odd data search and even data search processes can take place simultaneously.

[0086] The biggest challenge in motion estimation is the computational power requirement. To minimize search circuitry, field searches are performed together, and the field search results are combined to form frame searches. For example, let Cf1 be the odd lines of current macroblock data, Cf2 be the even lines of current macroblock data, Rf1 be the odd lines of reference data, and Rf2 be the even lines of reference data.

[0087] Four field searches, Cf1 versus Rf1, Cf1 versus Rf2, Cf2 versus Rf1, and Cf2 versus Rf2 are performed concurrently. The results of Cf1 versus Rf1 and Cf2 versus Rf2, and Cf2 versus Rf1 and Cf1 versus Rf2 are combined to form the frame search results. The scheme eliminates the frame search circuitry.

[0088] Search-chip Result

[0089] The five full pixel refinement results are generated for each frame structured macroblock, and two refinement results are generated for a field structured macroblock.

[0090] Xchip interface

[0091] The xchip interface 831 supports communications between the Search-chip 801 and Refinement-chip or Reconstruction-chip 901 as well as among the Search-chips 801 in the configuration. For every macroblock, up to five search results, one frame and four fields, are passed to the R-chip 901 via this interface. This interface is also used for Search-chip 801 to Search-chip 801 communications. For multi-search chip configurations, each Search-chip 801 has a chip ID. A pre-defined wiring pattern at each set of Search-chip 801 pins is used as the chip ID or address. Address 0 identifies the Search-chip 801 that has the main communication with the R-chip 901. The encoder structure can support one, two or four Search-chips 801. Address 3 identifies the last Search-chip 801 in the chain. In a four Search-chip 801 configuration, the search window is divided into four quarters. Address 0 handles the upper left quarter, address 1 handles the upper right quarter, address 2 handles the lower left quarter and address 3 handles the lower right quarter. Search-chip 3 forwards the search result to Search-chip 2 when it is available. Similarly, for Search-chip 2 to 1 and Search-chip 1 to 0. The best match result obtained from the higher address Search-chip is compared with the result obtained in the receiving chip. The best of the two is then forwarded to the next Search-chip. The best match from all Search-chips is finally selected and returned to the R-chip 901.

[0092] Processing in R-chip

[0093] R-input buffer

[0094] The current macroblock data that was previously received from the Intra-chip 601 and is buffered on this chip, is used in the refinement process.

[0095] In IPB mode, the R-chip 901 processing may lag the Search-chip 801. To ensure the pipeline is constantly full, the buffer is large enough for two macroblocks of data. The next current macroblock data is fetched when there is space in both the Search-input and R-input buffers.

[0096] R-motion estimation

[0097] The reference data has previously been saved in the external memory, i.e., reconstructed memory, connected to the R-chip 901, i.e., the Refinement- or Reconstruction-chip. The reference data, as the name implies, is composed of reconstructed data. When this data is used in motion refinement, it produces a prediction difference that matches the one reconstructed by the decoder. This scheme minimizes the difference between compression and decompression processes.

[0098] The R-chip 901 also receives the search format selected by the user. Depending on the search format, the search results received from the Search-chip 801 are upscaled accordingly back to the full picture resolution. A search refinement is performed based on the search result, including result from the 1 to 1 format. A maximum refinement search range of +/−4H and +/−1V is used.

[0099] Another big challenge of motion estimation is memory bandwidth. The reference data retrieved from reconstructed memory, once per macroblock, is buffered on-chip until the frame difference data is generated. This scheme minimizes external memory traffic. Each search result is first refined on a full pixel boundary. At most three full pixel results continue to the next refinement process, half pixel refinement. Up to eight half pixel macroblocks around each full pixel refinement result can be identified for further half pixel refinement search. All the full and half pixel refinement results are transferred to the on-chip processor, that is, the motion estimation processor.

[0100] IR-chip interface

[0101] Depending on the search type, the R-processor 901 determines the macroblock type and the motion vector for every macroblock processed. Selectable search types may include frame only, field only, full pixel only, half pixel only, and adaptive field/frame motion estimation. If adaptive frame/field motion estimation is selected, the best matched macroblock is used to continue the coding process. Based on the best matched decision, the matching chrominance data is retrieved from reconstructed memory. Both the luminance and chrominance frame difference data are generated and buffered in the Intra-chip 601 and R-chip 901 interface. The luminance difference data is transferred to the Intra-chip 601 first. When the quantized luminance data is returned to the R-chip 901, the chrominance difference data is then transferred to the Intra-chip 601. Both the difference data and the quantized data share the same bi-directional data bus between the Intra-chip 601 and R-chip 901. The data transfers are staged to avoid bus collision.

[0102] The quantized data is first passed through the inverse quantizer 941, then the inverse DCT unit 943, and then finally the motion compensation unit 945. The IDCT data is added to the current macroblock data, the one used in the macroblock search, as motion adjust in the Motion Compensation (MC) unit 945. The MC unit 945 produces the reconstructed data. It is buffered and ready to be stored into the reconstructed memory and be used as refinement reference data for subsequent picture coding.

[0103] In IP coding format the search refinement circuits on the R-chip 901 are used as a small motion estimator. The center of the search window is the location of the current macroblock. The R chip 901 can support up to +/−8H and +/−7V search ranges in the IP mode. Similarly to the IPB coding format, the reference data is fetched once per macroblock. This data is buffered on-chip until the frame difference data is created. A motion estimation on full pel is first performed. A refinement search is then performed on the best matched full pel macroblock data. Two refinements are carried out, dual prime and half pel search.

[0104] A best matched full pel macroblock data is split into odd and even field data. For each field data, the opposite parity data, with +/−½ delta, is retrieved from external memory by extending the origin field data address as specified in the standard. The field data is interpolated with its associated opposite parity data to form the reference data to be used in dual prime motion estimation.

[0105] Half pel refinement is performed by a process similar to the process used in IPB coding. All results including full pel, dual prime, and half pel searches are collected by the motion estimation processor. The remaining processes are similar to the IPB mode.

[0106] Reference memory interface

[0107] For every macroblock process, there is a reference data fetch, a dual prime data fetch, a best matched chrominance data fetch, a reconstructed luminance data store, and a reconstructed chrominance data store. To reduce the memory bandwidth requirement, the reference data is only fetched once per macroblock. To ensure the pipeline is consistently full, the memory operations are handled in a specific order per the macroblock location in the picture. Since motion estimation is performed on just the luminance data, to improve the memory read rate for a specific operation, the luminance and chrominance data are stored in different regions in reconstructed memory.

[0108] Entropy processing in Intra-chip

[0109] Intra-processor

[0110] The Intra-processor 601 is shown in detail in FIG. 6. When the current macroblock data is made available from frame memory, the energy content of the macroblock, which is used to determine a quantization level for the best rate control, is calculated by the dynamically partitionable processor 621. A frame or field DCT decision is made by the dynamically partitionable processor 621 on the frame difference data when it is returned from the R-chip 901. The dynamically partitionable processor 621 operates as either four 1 byte units or as one 4 byte entity. Both the quantization and field/frame DCT calculations are performed in partitioned mode which provides a four fold performance gain.

[0111] Depending on the input picture and the specified output bitrate, overflow or underflow conditions may occur. It is the rate control's responsibility to avoid either of these conditions. Use of DC only and external FIFO feedback are installed to avoid the overflow case. Padding is put in place to control or even eliminate the underflow case.

[0112] Picture coding time depends on the input format and coding format. Picture rate is specified by the application. Picture gap is the time the encoder is not busy in picture coding. Picture gap is determined by picture rate and picture coding time. Padding, if needed, is performed in picture gap. This limits the maximum bits the encoder can pad per gap. The encoder keeps track of the number of bits generated per picture and bits allocated per picture. If the bits generated is less than bits allocated, padding will be used to fill the unused bits. The unused bits from a picture may be padded across several picture gaps. This mechanism ensures the bitstream complies with the application without performance violation.

[0113] Quantizer

[0114] A coefficient clipping feature is present in the quantizer unit. The coefficient clipping register, written by microcode, is used to contain the position of the last non-zero amplitude coefficient in a block. When the rate control detects a near overflow condition, the code can write a value into the coefficient clipping register. This value is calculated based on overflow closeness. All coefficients after the location specified in the coefficient clipping register are made zero. This scheme is also used to produce a constrained bitstream. A constrained bitstream is defined in the MPEG-2 Main Profile at Main Level standard as all macroblocks in a slice, except two macroblocks, must contain less than 4608 bits each. The encoder keeps track of the bits generated per macroblock and the number of macroblocks in a slice that have over 4608 bits. When two macroblocks having over 4600 bits are encountered, the coefficient clipping register is set to 31 for the remaining of the slice. In this case, the chip will use the first 31 coefficients to form the bitstream. The number of bits used per coefficient depends on the coefficient value. Twenty-four bits are used to code a maximum value. Assuming all 31 coefficients contain the maximum number, 4464 bits will be produced per macroblock in 4:2:0 format. This mechanism ensures that the output bitstream is constrained and also curbs the bits generated to avoid overflows.

[0115] Variable Length Encoder

[0116] The output of quantization, prior to ZZ scan processing, is returned to R-chip 901 for reconstruction of the picture. This eliminates some design complexity and an inverse ZZ function is not required on the R-chip 901. The scan format is selectable at the host interface. Microcode can also select the scan format based on picture format. Alternate scan is used for interlaced coding and traditional scan for progressive pictures.

[0117] ZZ scan is applied to the quantized data, which is variable length coded with the Huffman table. The variable length data is saved in a buffer. Coded block pattern, as defined in the MPEG-2 standard, is used to indicate which block contains non zero data in the macroblock. When all blocks are coded, headers are attached to the VLC data.

[0118] Compressed store interface

[0119] Headers are generated in a flexible manner. The header definitions are stored in a programmable table. The microcode also has the capability to modify the content of the header table when changes occur in the standard. Depending on the application needs, the microcode selects which header to generate. The elementary stream is formed from the coefficient data along with the headers.

[0120] Motion Estimation and Compensation in the Refinement Search Unit including the Motion Estimation Processor (MEPROC)

[0121] Motion Estimation and Compensation is provided in the refinement search unit including the Motion Estimation Processor (MEPROC) 900. FIG. 10 shows the Motion Estimation Processor (MEPROC) 900 of the invention with associated interfaces. FIG. 10 shows the hierarchal search unit 801, the variable length encoder 675, and a dynamically partitionable digital video encoder processor 621. A search unit communication bus 911 provides best match difference/offset communications between the hierarchal search unit 801 and the Motion Estimation Processor 900, while a processor communication bus 913 provides communication between the Motion Estimation Processor (MEPROC) 900 and the dynamically partitionable digital video encoder processor 621. The motion estimation unit further includes a full resolution search unit 921, as well as a dual prime search unit 925, and a frame difference unit 927, both of which receive inputs from the memory controller 931.

[0122] Communications between the Hierarchal Search Unit 801 and the Refinement Search Unit are made through the search unit communication bus. Moreover, the Motion Estimation Processor 900 can work with or without the Hierarchal Search Unit 801. When the processor works with the Hierarchal Search Unit 801, the motion estimation processor receives initial search result information to use a starting point for searches. However, without the hierarchal search unit 801, the motion estimation processor 900 always sets searches with the current macroblock in the center of the search window.

[0123] When the motion estimation processor 900 works with the hierarchal search unit 801 the motion estimation processor 900 receives a set of search vectors and associated difference data from the hierarchal search unit 801 for each macroblock. The number of search vectors depends on the encoded picture type, that is, intra, predicted, or bidirectional, and the picture structure, that is, frame or field. When working without the hierarchal search unit the motion estimation processor initiates searches once a macroblock is available. FIG. 11 shows the number and type of search vectors that the motion estimation processor can process.

[0124] The refinement search unit uses three coprocessors to perform refinement searches, as shown in FIG. 10. These three coprocessors are the full resolution search unit 921, the half resolution search unit 923, and the dual prime search unit 925. The full resolution search unit 921 searches on full pixel boundaries for best match searches. The half resolution search unit 923 searches on half pixel boundaries for best matches. The dual prime search unit 925 uses a dual prime search to find the best match.

[0125] The three search coprocessors search a macroblock from the current picture against a search window from either a single previous picture, or from a previous picture and a future picture. The coprocessors need not keep track of the current location within the picture. Therefore, the coprocessors are assisted to retrieve the proper data in DRAM by the motion estimation processor. The motion estimation processor 900 tracks the current macroblock location within the picture, and insures that the boundary conditions are handled properly by the coprocessors. Each of the search co-processors receive their search instructions from the motion estimation processor and return their search results to the motion estimation processor for processing.

[0126] The three search coprocessors work together to generate a set of one, two, or three search result motion vectors and associated difference values depending on the picture type, that is, frame or field, with one or two reference pictures, and dual prime or non-dual prime. The coprocessors work in staged pipeline fashion, where the current macroblock is always forwarded to the next co-processor. The reference search window data is also sent to the next co-processor. Refinement takes place as the reference data propagates from co-processor to co-processor based on best match search results and on control from the motion estimation processor.

[0127] After the best match macroblock is determined, the proper reference data is forwarded to the frame difference unit 927 which sends either the difference data or the original macro-block data to the Intra Chip or processor 601 for further coding. The decision of which data to send to the intra chip or processor is made by the motion estimation processor based on whether Intra or non-Intra macroblock coding was selected.

[0128] For refinement searching, the refinement search begins when the motion estimation processor passes to the full resolution search unit 921 the information that the full resolution search unit 921 requires to begin searching. These inputs include the starting memory address location, the search window size in number of pixel rows and number of pixel columns, and the top of picture or left of picture edge conditions. The number of searches done is based on the mode listed in FIG. 11.

[0129] When the full resolution search unit completes its searches, the current macroblock data and a set of reference data for each best match completed by the unit are sent to the half resolution search unit. The half resolution search unit 923 begins a half pixel resolution search for each set of reference data sent by the full resolution search unit 921. Completed search results are returned to the motion estimation processor 900. The motion estimation processor 900 compares the full resolution search results with the half pixel resolution search results and selects the results with the smaller difference. An indicator is sent to the half resolution search unit to forward either the full resolution search result pixel data or the half resolution result pixel data to the dual prime unit.

[0130] The dual prime search unit 925 is only enabled for Predicted pictures and only when requested through the host interface.

[0131] The motion estimation processor compares the best difference value determined from the searches with data received from the dynamically partitionable digital video encoder processor 621 over processor communication bus 913.

[0132] After the best match is determined, the motion estimation processor 900 determines the motion vector based on the best match, for example, considering biasing, such as weighting to the center of the macroblock, and sends the information back to the Variable Length Encoder.

[0133] Integrated System

[0134] In one embodiment there is provided according to our invention an MPEG-2 compliant digital video encoder system having an I-frame video encoder module 601 with (1) a host interface 611, (2) a pixel interface 641 for receiving pixel data from a pixel bus 542, (3) a frame memory interface 651 for receiving and sending frame data, (4) a Discrete Cosine Transform processor 671, (5) a quantization unit 673, (6) a variable length encoder 675, (7) a FIFO buffer 677, and (8) a compressed store interface 679, for generating an I-frame containing bitstream.

[0135] In a further exemplification the scalable architecture MPEG-2 compliant digital video encoder system the I-frame video encoder module includes (9) an interface to motion estimation means, and the system further includes a second processor, i.e., an R-processor element 901 with (10) a reference memory interface 911, (11) motion estimation means 903, (12) inverse quantization means 941, (13) inverse discrete cosine transform means 943, and motion compensation means 945. The system also includes at least one third processor element or Search processor element 801 with (14) a search memory interface and (15) motion estimation means 801. This embodiment provides an I-P-B datastream.

[0136] According to an alternative embodiment of our invention there is provided a digital video encoder system where the I-frame video encoder module 601 includes (9) an interface to motion estimation means, and the system further includes only a second or R-processor element with (10) a reference memory interface 911, (11) motion estimation means 903, (12) inverse quantization means 941, (13) inverse discrete cosine transform means 943, and motion compensation means 945. This embodiment is useful for generating an I-P datastream.

[0137] While the invention has been described with respect to certain preferred embodiments and exemplifications, it is not intended to limit the scope of the invention thereby, but solely by the claims appended hereto.