Method and apparatus for performing two pass quality video compression through pipelining and buffer management Number:6,760,478 from the United States Patent and Trademark Office (PTO) owispatent An apparatus and method for performing two-pass real time video compression is provided. Tactical decisions such as encoding and quantization values are determined in software, whereas functional execution steps are performed in hardware. By appropriately apportioning the tasks between software and hardware, the benefits of each type of processing are exploited, while minimizing both hardware complexity and data transfer requirements. One key concept that allows the compression unit to operate in real time is that the architecture and pipelining both allow for B frames to be executed out of order. By buffering B frames, two-pass motion estimation techniques can be performed to tailor bit usage to the requirements of the frame, and therefore provide a more appealing output image.<H compression, management, Method, and, appa, 6760478.html, Patent, pto, 6760478

Title: Method and apparatus for performing two pass quality video compression through pipelining and buffer management

Abstract: An apparatus and method for performing two-pass real time video compression is provided. Tactical decisions such as encoding and quantization values are determined in software, whereas functional execution steps are performed in hardware. By appropriately apportioning the tasks between software and hardware, the benefits of each type of processing are exploited, while minimizing both hardware complexity and data transfer requirements. One key concept that allows the compression unit to operate in real time is that the architecture and pipelining both allow for B frames to be executed out of order. By buffering B frames, two-pass motion estimation techniques can be performed to tailor bit usage to the requirements of the frame, and therefore provide a more appealing output image.

Patent Number: 6,760,478 Issued on 07/06/2004 to Adiletta, et al.

Inventors: Adiletta; Matthew James (Worcester, MA), Chow; King-Wai (Marlboro, MA), Ho; Samuel William (Marlborough, MA), Rose; Robert Clint (Hudson, MA), Wheeler; William Ralph (Southborough, MA), Galbi; Duane E. (Marlborough, MA)
Assignee: Hewlett-Packard Development Company, L.P. (Houston, TX)

Appl. No.: 09/613,359

Filed: July 10, 2000

Related U.S. Patent Documents


Application Number	Filing Date	Patent Number	Issue Date
670199	Jun., 1996	6101276	Aug., 2000

Current U.S. Class: 382/236 ; 375/240.02; 375/240.13; 375/240.16; 382/239

Current International Class: H04N 7/32 (20060101); H04N 7/26 (20060101); H04N 7/50 (20060101); G06T 9/00 (20060101); H04N 7/46 (20060101)

Field of Search: 382/236,232,234,239 348/416,699,402,409,390,415,413,405,384 375/340.02,240.01,240.12,240.13,240.16,240.14

References Cited [Referenced By]

U.S. Patent Documents


4541012	September 1985	Tescher
4646148	February 1987	Lienard et al.
4779131	October 1988	Matsumoto et al.
4809350	February 1989	Shimoni et al.
4868653	September 1989	Golin et al.
5122873	June 1992	Golin
5164819	November 1992	Music
5177608	January 1993	Ohki et al.
5185819	February 1993	Ng et al.
5208673	May 1993	Boyce
5227878	July 1993	Puri et al.
5231484	July 1993	Gonzales et al.
5247357	September 1993	Israelsen
5263100	November 1993	Kim et al.
5265180	November 1993	Golin
5301205	April 1994	Tsutsui et al.
5365272	November 1994	Siracusa
5371547	December 1994	Siracusa et al.
5379122	January 1995	Eschbach
5379355	January 1995	Allen
5384598	January 1995	Rodriguez et al.
5404168	April 1995	Yamada et al.
5412431	May 1995	Vogel
5416604	May 1995	Park
5428567	June 1995	Horvath et al.
5440346	August 1995	Alattar et al.
5448297	September 1995	Alattar et al.
5453799	September 1995	Yang et al.
5457675	October 1995	Suzuki et al.
5461378	October 1995	Shimoyoshi et al.
5483287	January 1996	Siracusa
5491519	February 1996	Kim
5510840	April 1996	Yonemitsu et al.
5544239	August 1996	Golin et al.
5557330	September 1996	Astle
5559557	September 1996	Kato
5574504	November 1996	Yagasaki et al.
5615287	March 1997	Fu et al.
5625759	April 1997	Freeman
5640208	June 1997	Fujinami
5657086	August 1997	Tahara et al.
5684534	November 1997	Harney et al.
5724098	March 1998	Murakami et al.
5731850	March 1998	Maturi et al.
5742346	April 1998	Sievers et al.
5838834	November 1998	Saito
6101276	August 2000	Adiletta et al.
6252991	June 2001	Uchio et al.

Other References

"21230 Video Codec--Product Brief," publication of Digital Equipment Corporation, 1995 (4 pp.). .
Adiletta, M. et al., "Architecture of a flexible real-time video encoder/decoder: The DECchip 21230," SPIE vol. 3021, 1997 (pp. 136-148). .
Liou, M., "Overview of the px64 kbit/s Video Coding Standard," Communications of the ACM: 34(4), Apr. 1991, pp. 60-63. .
Wallace, G.K., "The JPEG Still Picture Compression Standard," Communications of the ACM: 34 (4), Apr. 1991, pp. 31-44. .
LeGall, D., "MPEG:A Video Compression Standard for Mulitmedia Applications," Communications of the ACM: 34 (4), Apr. 1991. pp. 47-58. .
Liou, M.L., "Visual Telephony as an ISDN Application," IEEE Communications Magazine, Feb. 1990, pp. 30-38. .
"Line Transmission of Non-Telephone Signals," ITU-T standard, pp. 1-25..

Primary Examiner: Chen; Wenpeng

Parent Case Text

RELATED APPLICATION

This application is a continuation of U.S. patent application Ser. No. 08/670,199 filed on Jun. 21, 1996, now U.S. Pat. No. 6,101,276, issued Aug. 8, 2000 the entire teachings of which are incorporated herein by reference.

Claims

What is claimed is:

1. A method of providing compression of video data input to a video compression/decompression unit (VCDU) coupled to a central processor unit (CPU), said video data comprising a plurality of frames, including predictive frames and bi-directional frames, each of said frames apportioned into a plurality of macroblocks, each of said macroblocks comprising a plurality of pixels, said method comprising the steps of: said VCDU comparing each of said frames to other ones of said frames to estimate the motion characteristics of each of said macroblocks of each of said frames; determining, by said CPU, a coding type for each of said macroblocks of each of said frames responsive to said motion characteristics provided from said VCDU; said VCDU encoding each of said macroblocks of each of said frames responsive to said coding type determined by said CPU to provide one or more tokens for each of said plurality of frames; buffering, by said CPU, selected ones of said bi-directional frames and processing the buffered frames out of order in which said plurality of frames initially occur; translating, by said CPU, said one or more tokens for each of said plurality of frames into a bit stream for storage in a storage device; and wherein said VCDU and said CPU are connected by an input-output bus and the steps of the VCDU comparing and the CPU determining provide for minimal traffic on the input-output bus while tasks are efficiently apportioned between said VCDU and said CPU.

2. The method according to claim 1, wherein said step of said VCDU comparing each of said frames further comprises the steps of: determining at least one motion vector for each of said macroblocks, said at least one motion vector indicating a motion characteristic between said each macroblock and a similar macroblock in a preceding or succeeding frame.

3. The method according to claim 1, wherein said step of said VCDU comparing each of said frames further comprises the steps of determining energy characteristics of each of said macroblocks.

4. The method according to claim 1, wherein said step of said VCDU comparing each of said frames further comprises the steps of: determining a first and second motion vector for each of said macroblocks, said first and second motion vectors indicating a motion characteristic between said each macroblock and a similar macroblock in a preceding and succeeding frame, respectively; and determining energy characteristics of each of said macroblocks.

5. The method according to claim 2 wherein said step of said determining, by said CPU, a coding type for each of said macroblocks of each of said frames responsive to said motion characteristics further comprises the steps of: designating each of said macroblocks as either spatial or temporal coding type; and assigning a quantization value to each of said macroblocks, said quantization value for controlling the number of bits that are to be used to encode the macroblock.

6. The method according to claim 4 wherein said step of determining, by said CPU, a coding type for each of said macroblocks of each of said frames responsive to said motion characteristics further comprises the steps of: designating each of said macroblocks as either spatial or temporal coding type; and assigning a quantization value to each of said macroblocks, said quantization value for controlling the number of bits that are to be used to encode the macroblock.

7. The method according to claim 6, wherein said quantization value is assigned to each of said macroblocks responsive to the energy characteristics of other macroblocks within said associated frame.

8. The method according to claim 6, wherein the step of said VCDU encoding each of said macroblocks of each of said frames responsive to said coding type comprises the steps of: responsive to said coding type being a temporal coding type and said macroblock being a reference type macroblock, providing an error macroblock by calculating the difference between the value of pixels within said macroblock and the value of pixels within the macroblock indicated by said first motion vector; responsive to said coding type being a temporal coding type and said macroblock being a non-reference type macroblock, providing an error macroblock by calculating the difference between the value of pixels within said macroblock and the average of value of pixels within the macroblock indicated by said first motion vector and the value of pixels within the macroblock indicated by said second motion vector.

9. The method according to claim 8, wherein the step of said VCDU encoding each of said macroblocks further comprises the step of: applying a discrete cosine transform to either said macroblock, or said error macroblock, responsive to said coding type being either a spatial coding type or a temporal coding type, respectively, to provide a transformed macroblock.

10. The method according to claim 9, wherein the step of said VCDU encoding each of said macroblocks further comprises the step of: quantizing each of the macroblocks by multiplying the quantization value provided from said CPU to each of the entries of said transformed macroblock to provide a quantized macroblock.

11. The method according to claim 10, further comprising the step of: generating one or more tokens for each of said macroblocks, said tokens generated by traversing said quantized macroblock and recording the distance between frequency components in said quantized macroblock.

12. The method according to claim 1, wherein the step of translating, by said CPU, said one or more tokens for each of said plurality of frames into a bit stream for storage in a storage device includes the steps of defining, for each unique one of said one or more tokens, a compact code.

13. A method of performing decompression of a bit stream representing video data stored in a storage device of a computer system, said computer system including a central processing unit (CPU) and a video compression/decompression unit (VCDU) coupled to said CPU, said video data comprising a plurality of frames, each of said frames apportioned into a plurality of macroblocks, said method comprising the steps of: translating, by said CPU, said bit stream into one or more tokens for each of said plurality of frames; said VCDU decoding each of said tokens to construct a plurality of macroblocks for each of said frames; decoding, by said CPU, a coding type for each of said macroblocks of each of said frames, said coding type for indicating how each of said macroblocks is compressed; and using at least one stored motion vector for each of said macroblocks, and responsive to said coding type of each of said macroblocks, reconstructing each macroblock to provide a restored video image; wherein said coding types include temporal coding types and spatial coding types, and wherein said step of reconstructing each said macroblock further comprises the step of: responsive to said coding type being a temporal coding type providing said restored macroblock by adding the contents of each entry of said macroblock to the value of pixels within the macroblock indicated by a first motion vector; applying an inverse discrete cosine transform to either said constructed macroblock, or said restored macroblock, responsive to said coding type being either a spatial coding type or a temporal coding type, respectively, to provide a reconstructed macroblock for use in said restored video image; wherein the macroblock is double-buffered between a quantization process and a discrete cosine transform process; and wherein said VCDU and said CPU are connected by an input-output bus and in a compression process the VCDU compares frames to estimate motion characteristics of macroblocks and the CPU determines code types of the macroblocks based on the motion characteristics from the VCDU, said comparing and determining providing minimal traffic on the input-output bus while tasks are efficiently apportioned between said VCDU and said CPU.

14. An apparatus for performing compression and decompression of video data input to a video compression/decompression unit (VCDU) coupled via interface means to a central processor unit (CPU), said video data comprising a plurality of frames, including predictive frames and bi-directional frames, each of said frames apportioned into a plurality of macroblocks, each of said macroblocks comprising a plurality of pixels, said VCDU further comprising: motion estimation means, in said VCDU for comparing each of said frames to other ones of said frames to estimate the motion characteristics of each of said macroblocks of each of said frames; means for encoding each of said macroblocks of each of said frames responsive to a coding type determined by said CPU to provide one or more tokens for each of said plurality of frames; means for buffering, by said CPU, selected ones of said bi-directional frames and for processing the buffered frames out of order in which said plurality of frames initially occur; and wherein said interface means comprise an input-output bus and the motion estimation means and means for encoding provide minimal traffic on the input-output bus while each means efficiently apportions tasks between said VCDU and said CPU.

15. The apparatus of claim 14, wherein said CPU further comprises: means for determining said coding type for each of said macroblocks of each of said frames responsive to said motion characteristics provided from said VCDU via said interface means; and translating means for converting said one or more tokens received via said interface means from said VCDU for each of said plurality of frames into a bit stream for storage in a storage device.

16. The apparatus of claim 14 further comprising: reconstruction means, in said VCDU for translating said bit stream representing said plurality of frames into frame data.

17. The apparatus of claim 16 wherein said motion estimation means is coupled to receive video data from an external device and is further coupled to receive frame data from said reconstruction means.

Description

FIELD OF THE INVENTION

This invention relates in general to computer systems and more specifically to computer video compression and decompression techniques.

BACKGROUND OF THE INVENTION

With the convergence of computers, communications and media, video compression techniques have become increasingly important. Video compression is often used to translate video images (from camera, VCR, laser discs, etc.) into digitally encoded frames. The digitally encoded frames may then be easily transferred over a network, or stored in a memory. When desired, the compressed images are then decompressed for viewing on a computer monitor or other such device.

The three most common video compression standards are MPEG (Moving Pictures Experts Group), JPEG (Joint Photographic Expert Group), and H.261. These standards partition incoming video frames into small tiles and perform either spatial or temporal compression on the tiles. Each standard has a defined compression sequence for the series of incoming frames.

Compressed frames are classified as either Intra-coded (I frames), Predictive frames (P frames), or Bi-directional frames (B-frames). An `I` frame is a frame in which spatial redundancies are removed using spatial compression techniques. A `P` frame is a frame in which temporal redundancies have been removed by matching tiles through motion estimation in the current frame to a previous reference frame, then spatially compressing the temporal difference. A `B` frame is a frame in which temporal redundancies are removed by matching tiles in the current frame to a previous and a future reference frame, then compressing the difference with the spatial transform.

To perform spatial compression alone, such as in the I frame, only the individual frame is required for the compression. However, to perform the temporal compressions, which are required for both the `P` and `B`, frames, the compression of other frames must first be performed. Each P frame is encoded based on the previous I or `P` reference frame. Because `B` frames require the results of both past and future frame calculations, the processing of the B frame is an out-of order function, in which future reference frames must be analyzed prior to the intervening B frames.

Two recognized forms of video compression techniques are real-time compression and high-quality n-pass compression, where n>1. Each form has known advantages. Real-time video compression uses only spatial compression techniques (I frames) to allow images to be compressed at the rate at which they are input. Thus real-time compression processes require less buffering of the input image and consequently less hardware complexity.

To provide real-time compression, a `peephole` approach is typically implemented whereby each tile in each frame is encoded as it is processed. One drawback of this scheme arises from the fact that only a fixed number of bits are allocated for encoding a frame. If bits are used to encode portions of the frame as they are received, bits may be `used up` encoding low priority components of the tile, leaving fewer bits available for encoding higher priority blocks which may appear later in the frame.

Two-pass compression alleviates the above encoding problem by processing each frame in two steps. First, each frame undergoes a Motion Estimation (ME) calculation. During the ME phase, for P and B frames, the possible motion of each macroblock in the frame is characterized relative to a past and/or future reference frame as described above. In addition, for I, P and B frames, energy statistics are generated for the frame to profile the visual complexity of the frame, providing energy statistics allow for proper allocation of bits for encoding purposes throughout the frame.

Following the ME phase, the frame undergoes Motion Compensation (MC), during which the data is actually compressed. Based on the encoding directives, a Discrete Cosine Transform (DCT) is performed on each portion (or block) of each frame, or to the temporal differences between each block and its corresponding reference point in another frame. The resulting data is then quantized and transformed into run-level tokens (RLE) tokens, which are then encoded.

Because the entire frame is evaluated before bits are allocated for encoding the different blocks of the frame, the output image provided is of much higher quality than that provided via the `peephole` compression technique described above. It would be desirable to provide two-pass compression techniques in real-time. However the complexity of the process has precluded it from being a valuable tool for video compression applications which require real-time performance. The main problem with two-pass compression techniques is encountered when analyzing B frames, as will be shown below.

Referring now to FIG. 1, a subset of a typical input stream of MPEG encoded frames, I1, B2, B3, P4, B5, B6, P7 is shown, where numbers designate the temporal order of images to encode and the I, P, and B references designate intra-coded, predictive or bi-directional frames as described above . Each P frame is encoded based on the previous I or P reference frame. Thus, to maintain real-time operation, the compression technique should be able to process P frames and I frames as they are received. Each B frame is encoded based on the previous I or P reference frame, and/or the next I or P reference frame. As seen in FIG. 1, a problem with real-time two pass processing soon develops when encoding B frames.

At time T0 frame I1 is input to ME stage of the compression engine. At time T1, frame I1 is passed to the MC stage of compression where the compression is completed. Although the ME stage is free, the B2 frame may not be input for ME processing, because the data for the next P frame has not yet been calculated. In fact, the next P frame is not even received until time T3, at which time it is input to the ME stage of the compression engine. At time T4, frame P4 is forwarded to the MC stage for compression. Only after this compression step is completed may the B2 frame be input to the ME stage of processing, at time T5. At time T6, the B3 frame may be input to the ME stage of processing, and at the B2 frame moves to the MC stage of processing. However, at time T6, the frame P7 is being input in real time, and must be processed.

If the processing of the P7 frame is extended to time T7, then the compression engine is no longer operating in real time, and thus the prior art solution is ineffective at providing a real-time two-pass compression algorithm. In order to make such a solution work, it would be necessary to accelerate processing of the ME and MC engines by a factor of 4/3 so that the ME and MC engines operate on 4/3 frames during each frame interval. However, such a solution would require more process power than is currently marketable for video compression techniques.

SUMMARY OF THE INVENTION

According to one aspect of the invention, a method of performing real-time compression and decompression of video data input to a video compression/decompression unit is disclosed. The video data is apportioned into a plurality of frames including reference frames, where a subset of the frames are dependent frames having dependencies on one or more of the reference frames for compression purposes. The method includes the steps of compressing the reference frames as they are input, but storing the dependent frames until the associated one or more reference frames have been compressed. After the associated reference frames are compressed, the associated dependent frame is retrieved and compressed.

With such and arrangement, a high quality image may be produced because bits are more optimally allocated across pictures than they are using conventional techniques. Because the reference frame is encoded prior to the dependent frames, such as B frames, more bits are available to encode the reference frame. It is inherently more important for reference frames to be optimally encoded because the reference frame is not only displayed but is used to effect encoding of up to 4 other dependent frames. Accordingly, the present invention, by delaying the compression of dependent frames until all associated reference frames have been compressed, provides a high quality image.

According to a further aspect of the invention, the method of compressing the frames further includes the steps of determining motion characteristics for each of said frames and providing compressed data for each of the frames in response to the motion characteristics. In the present invention, the step of determining motion characteristics operates on a first frame in parallel with the step of providing compressed data operating on a second frame. With such an arrangement, the motion characteristic stage and the data compression stage each can be designed to process a frame in one frame interval. As a result, a fully pipelined operation may be provided that allows for real time two-pass video compression.

According to a further aspect of the invention, the method includes the step of storing the dependent, B frames in a memory of a coupled computer system while they await processing of their associated reference frames. Such an arrangement minimizes the storage requirements of the video compression/decompression unit itself, thereby reducing the overall cost of the system.

BRIEF DESCRIPTION OF THE DRAWINGS

The above-mentioned and other features of the invention will now become more apparent by reference to the following description taken in connection with the accompanying drawings in which:

FIG. 1 is a timing diagram used to illustrate the problems of providing real-time two-pass compression in the prior art;

FIG. 2 is a block diagram of a computer system incorporating the present invention;

FIG. 3 is a functional flow diagram illustrating the apportionment of video compression/decompression tasks between the video compression/decompression unit of FIG. 2;

FIG. 4 is a block diagram of the components of one embodiment of the Video Compression Decompression unit of FIG. 2;

FIG. 5A provides an illustrative example of video frames being provided to the Video Compression Decompression unit of FIG. 2;

FIG. 5B is an illustration of a frame of data apportioned into macroblocks;

FIGS. 6A, 6B and 6C provide an illustrative example and a flow diagram, respectively, of the motion estimation process provided in the flow diagram of FIG. 3;

FIG. 6D is a block diagram showing, in general, the logical flow of video data in the present invention;

FIG. 7 is a block diagram of the process used to determine the perceptual visual weight of an I-coded frame or macroblock;

FIG. 8 is a diagram of the process used to determine the visual classification of a macroblock;

FIG. 9 includes flow charts for the determination of an initial perceptual visual weight for the process of FIG. 7;

FIG. 10 is a flowchart corresponding to the visual classification process of FIG. 8;

FIG. 11 is a flowchart for determining the final perceptual weight for the process of FIG. 7;

FIG. 12 includes flowcharts for the determination of initial perceptual visual weight values for the process of FIG. 15;

FIG. 13 includes flowcharts for the determination of initial visual weight values for the process of FIG. 12;

FIG. 14 includes additional flowcharts for the determination of initial visual weight values for the process of FIG. 12;

FIG. 15 is a block diagram for a process for determining the perceptual visual weight for P and B-type frames and macroblocks;

FIG. 16 is a block diagram of depicting motion vectors associated with various macroblocks of an image;

FIG. 17 is a block diagram of the process used to build a non-parametric model for determining quantization values;

FIG. 18 is block diagram of the usage of the non-parametric model of FIG. 17;

FIGS. 19A and 19B provide an illustrative example and a flow diagram, respectively, of the intra-coding procedure used in the motion compensation process of FIG. 3;

FIG. 20 provides an illustrative example of one step of a differential encoding procedure used in the motion compensation process of FIG. 3;

FIG. 21 is a flow diagram illustrating the entire flow of the motion compensation process of FIG. 3;

FIGS. 22A-22C provide examples of a "synthetic" B frame being inserted into the Group of Pictures to provide for a dropped frame;

FIGS. 23A-23C provide examples of a "synthetic" P frame being inserted into the Group of Pictures to provide for a dropped frame;

FIG. 24 is a timing diagram illustrating the pipelining of the motion estimation and motion compensation process of the present invention;

FIG. 25 is a series of timing diagrams illustrating the buffering of frames input to the VCDU and passed to and from system memory for buffering to support the PAL SIF standard;

FIG. 26 is a series of timing diagrams illustrating the buffering of input frames for supporting IBBBP compression according to the NTSC SIF video standard; and

FIG. 27 is a series of timing diagrams illustrating the buffering of frames input to the VCDU and passed to and from system memory for buffering to support IBBBP compression according to the PAL SIF standard.

FIG. 28 is a block diagram illustrating the components of one embodiment of the Video Compression Decompression Unit of FIG. 2;

FIG. 29 is a block diagram illustrating one embodiment of the Filter and Motion Unit of the Video Compression/Decompression Unit of FIG. 28;

FIGS. 30A-30D include flow diagrams and sequence execution diagrams for providing forward and inverse Discrete Cosine Transforms;

FIGS. 31A and 31B are block diagrams illustrating one embodiment of the data path of the Discrete Cosine Transform unit and Double Buffer of the Video Compression/Decompression Unit of FIG. 28;

FIG. 32 illustrates a partitioning of a block of video data into left and right halves for row transforms, and into top and bottom halves for column transforms, for purposes of the DCT operation of FIGS. 31A and 31B;

FIG. 33 is a table diagram for illustrating an order of operation that allows for compression transform efficiency in the process outlined in FIGS. 31A and B above;

FIG. 34 is a table diagram for illustrating a second order of operations that allows for compression transform efficiency in the process outlined in FIGS. 31A and B above;

FIG. 35 is a block diagram illustrating one embodiment of the quantization unit of the Video Compression/Decompression Unit of FIG. 28;

FIG. 36 is a detailed diagram of the quantization divider of FIG. 32;

FIG. 37 is a flow diagram illustrating the steps used by a video decoder for decompression of a video image;

FIG. 38 is a detailed block diagram of a decoder portion of FIG. 2;

FIG. 38a is a detailed logic diagram of a comparator in FIG. 38;

FIG. 38b is an alternate detailed logic diagram of a comparator in FIG. 38;

FIG. 39 is an example of an encoded bitstream shown in FIG. 38;

FIGS. 39a-39d is an example of a codeword table as shown in FIG. 38;

FIG. 40 is an alternate embodiment of the variable length decoder of FIG. 38 using a pair codeword tables and one compare mask;

FIG. 40a is an example of a decomposition of a pair of codeword tables as shown in FIG. 40;

FIG. 41 is another alternate embodiment of the variable length decoder of FIG. 38;

FIG. 42 is an exploded diagram of the PCI controller logic of FIG. 28;

FIGS. 43a-43c is a series of diagrams illustrating the layout of data forwarded over the PCI bus to buffers in the PCI controller of FIG. 42;

FIG. 44 is a block diagram of one of the buffers of FIG. 42;

FIG. 45 is a schematic diagram of the buffer of FIG. 44;

FIG. 46 is a block diagram illustrating the control paths for the buffers of FIG. 44;

FIG. 47 is a schematic diagram illustrating the control logic used to control the writing and reading of the buffers of FIG. 44;

FIG. 48 is a timing diagram illustrating the operation of the control logic of FIG. 47;

FIG. 49 is a block diagram illustrating a de-interleaving buffer for use in the computer system of FIG. 28; and

FIGS. 50, 50a and 50b are a schematic diagram of the de-interleaving buffer of FIG. 49.

DESCRIPTION OF THE PREFERRED EMBODIMENT

Referring now to FIG. 2, a computer system 10 for use with the present invention is shown to include a central processing unit (CPU) 12 for processing an instruction stream. The instruction stream as well as data which is used by the CPU is stored in a memory 14. The CPU 12 and the memory 14 are coupled together via a system bus 16.

Also coupled to system bus 16 is Input/Output (I/O) interface 18. The I/O interface enables the CPU to communicate with a number of external devices via an I/O bus 20. The I/O bus 20 of the present invention is operated according to the Peripheral Connect Interface (PCI.TM.) protocol, and is capable of transferring data at 133 Mbyte/sec, although it is understood that the present invention could be modified for use with other I/O protocols by one of ordinary skill in the art.

A network interface 22 is coupled to I/O bus 20 for interfacing the CPU with other CPU's in a network. Also coupled to the PCI bus is a graphics controller 26, which is used to control the display of images on a CRT 28. In addition, a video compression/decompression unit (VCDU) 24 is coupled to the I/O bus for providing compression and decompression of the video images received from external devices via external ports.

The VCDU has three ports; an option port 30, a video port 32, and a memory port 34. The option port provides an interface between the PCI bus and audio signal processing devices 31 such as Analog Devices.RTM. 2171 and 2181 family of digital signal processors. The video port 32 provides an interface to any one of a number of digital video decoder devices 33 from Philips.RTM. and Brooktree.RTM., such as the Philips.RTM. SAA717x family of devices or the Brooktree.RTM. Bt81x family of devices. The memory port 34 couples the VCDU to an external DRAM device 35 which is used for temporary storage of data during the compression/decompression process.

The raw, analog video is input to the video port 36 of the VCDU and converted into luminance and chrominance data types, where the luminance roughly corresponds to the intensity at that point, and the chrominance corresponds to the color. The digital data consists of eight bits of luminance (Y), eight bits of chrominance-blue (Cb) and eight bits of chrominance-red (Cr). Raw, analog video data are received by the color decoder 33 and translated to digital YUV format according to the CCIR601 standard at either an NTSC format of 720 pixels.times.480 scan lines at 29.97 frames/second, or PAL format of 720 pixels.times.576 lines at 25 frames per second. The pixel data arrives as a stream of horizontal scan lines. The scan lines arrive in interlaced order (first all consecutive even lines from top to bottom followed by all consecutive odd lines from top to bottom).

Once the input pixels are digitized, the VCDU works in concert with the CPU to compress the input SIF (Standard Interchange Format) frames. There are three types of compression standards, including the MPEG standard developed by the Moving Pictures Experts Group, the JPEG standard developed by the Joint Picture Experts Group, or the H.26x video teleconferencing standard. Each type of compression standard uses a variety of encoding techniques for encoding incoming frames. For example, the MPEG standard and the H.26x teleconferencing standard use a combination of spatial encoding, temporal encoding and entropy encoding techniques, while the JPEG standard uses only spatial encoding techniques and entropy encoding techniques. The various types of encoding techniques will be described later herein.

For purposes of simplification, compression of an input video frame stream using the MPEG standard will be described, although it will become apparent as to how the described system could be modified to perform compression according to the other compression standards.

The MPEG standard was developed to reduce the high cost of video compression codes and resolve the critical problem of interoperability of equipment from different manufacturers. Some requirements of the MPEG standard were a targeted rate of between 1.5 and 3.0 Mbits/sec, the ability to randomly access any frame in a series of images, and the production of a high quality image.

According to the MPEG standard each video input frame is compressed into one of three types of frames: either an Intra-coded frame (I), a Predicted frame (P) or a Bi-directional Frame (B). Intra-coded frames provide access points for random access with moderate, spatial compression of the image. Predicted frames are coded with reference to a past Intra-coded or Predicted frames, and are in general used as a reference for future predicted frames. Bi-directional frames provide the highest amount of compression, but require both a past and a future reference for prediction. Bi-directional frames are never used as a reference.

A typical MPEG compression sequence of the raw frame data into the three frame types is shown below, where the letters I, P, and B are used to designate the type of MPEG frame, and the numerical designators are used to indicate the order of receipt of the frames:

I1 B2 B3 P4 B5 B6 P7 B8 B9 P10 B11 B12 I13

In the above sequence, it can be seen that every 3rd input frame is identified and compressed as a reference frame. This frame sequence is described as having an M=3 reference distance.

As mentioned above, the I frames and the P frames are both reference frames for both P frames and B frames. The I frames differ from the P and B frames in that they do not reference any other frame, and are therefore compressed using spatial compression techniques. The P and B frames are compressed using temporal compression techniques, as will be described in more detail below.

Referring now to FIG. 3, a functional block diagram will be used to describe the processes undertaken by the CPU and the VCDU to provide real-time MPEG compression. Each functional block includes a designator, either CPU or VCDU for indicating which portion of the computer system 10 operates to perform the respective function.

The digitized YUV data video signal is fed to a decimate and filter functional unit (DFU) 42 which performs the first step of compression through resolution reduction. The DFU is responsible for reducing the amount of video data by means of sub-sampling and decimation of horizontal scan lines as they arrive by optionally keeping only half the scan lines, either even or odd. Pixels output from the DFU are generated as a weighted average of the incoming ones, in effect filtering out high frequency components. In addition, the pixel data may additionally be filtered using a low pass filter to remove extraneous noise which would greedily use up compression bits, although this is not a requirement. The result is SIF (Standard Interchange Format) frames, 352 pixels.times.240 lines for rectangular systems (320.times.240 for square).

Thus the color decoder 33 reduces the raw pixel data via subsampling and decimation to conform to the Standard Interchange Format (SIF). NTSC SIF frames comprise 352 pixels by 240 scan lines transmitted at 29.97 frames/second. PAL SIF frames comprise 352 pixels by 288 scan lines transmitted at approximately 25 frames/second. The pixels are in YUV 4:2:0 format, meaning for every two chrominance pixels, one byte of blue (U) and one byte of red (V), there are 4 pixels (or bytes) of luminance (Y) data. The frames are forwarded to the VCDU off-chip memory 34 (FIG. 2) for temporary buffering.

Referring now to FIG. 4, a block diagram of a first embodiment of a VCDU 24 is shown. The VCDU 24 includes a DFU 42 coupled to the video port 32 which, as discussed above, performs the first step of compression of the video input stream through resolution reduction. The DFU 42 is coupled to a memory controller 134. The memory controller 134 is coupled to external VCDU memory 35 through the memory port 34, for controlling transmission of data to and from various units in the VCDU 24. The VCDU 24 further includes an encoder 37 which here, converts the digitized video input into a compressed MPEG video stream. The preferred embodiment of an encoder 37 includes a co-processor architecture as described in FIG. 3. Details of this embodiment will be discussed later herein.

As described above, a SIF frame is sent from the DFU 42 to the memory controller 134 which temporarily stores the frames of digitized pixel data in the VCDU memory 35. When the encoder 37 is ready for a frame, it retrieves the frame from the VCDU memory 35. As the frame is retrieved from the VCDU memory 35, this operation frees space in the VCDU memory 35 allowing subsequent frames to be stored.

At times during the processing of the incoming video stream however, the system, for various reasons, is unable to keep up with the video stream. In the preferred embodiment of the invention described in FIG. 3, typical reasons for the system being unable to keep up with the incoming video stream are because the CPU 12 (FIG. 1) has been delayed or because the co-processor hardware has taken too much time.

In either case where the system is unable to keep up with the incoming video stream, the VCDU memory 35 becomes full and therefore is unable to store any additional frames as it has not yet been relieved by the encoder 37 of the data from previous frames in the video stream. Accordingly, the memory controller 134, unable to store the incoming frame in VCDU memory 35, drops the frame allowing the system time to process the data already stored in the VCDU memory 35. A mechanism for determining which frame to drop and how to later recreate this frame is described below.

I.) Frame Dropping

Referring now to FIG. 5A, a series of frames 54 in a video stream is shown to include a succession of frames as they are received by the video port 32. The series of frames is provided in increasing temporal order, with frame A 55a being the frame received at time t=0 and frame F 55f being the frame received at time t=5. Included in each of the frames is a frame image element 56, which corresponds to an object, such as a ball, appearing in an actual video segment. The frame image element 56 is designated at different (x,y) coordinates in each frame, thus indicating motion of the frame image element 56.

At time t=0, data corresponding to frame A 55a is received at the video port 32 and passed through the DFU 42 to the memory controller 134. The memory controller 134 assigns an index value to frame A 55a and stores the frame in VCDU memory 35. The index value assigned by the memory controller 134 indicates the order in which frame A 55a was received by the VCDU 24 in relation to the remaining frames in the frame series 54. At time t=1, data corresponding to frame B 55b is received at the video port 32, partially compressed by the DFU 42, assigned an index value by the memory controller 134, and stored in VCDU memory 35 by the memory controller 134. At time t=2, data corresponding to frame C 55c is received at the video port 32, assigned an index value, and eventually stored in VCDU memory 35 by the memory controller 134. Also at time t=2, 10 the data corresponding to frame A 55a is retrieved from VCDU memory 35 by the encoder 37.

Here, for illustrative purposes, it will be assumed that VCDU memory 35 has sufficient storage space to retain data corresponding to three video frames. At time t=3, data corresponding to frame D 55d is received at the video port 32, partially compressed, assigned an index value and eventually stored in VCDU memory 35.

At time t=4, data corresponding to frame E 55e appears at the video port 32. At this point in time however, the data corresponding to frame A 55a is still being encoded by encoder 37 while the data corresponding to frames B 55b, C 55c and D 55d are stored in VCDU memory 35. VCDU memory 35 therefore, is currently full as frame E 55e is received at the video port 32. Frame E 55e is partially compressed by the DFU 42 and assigned an index value by the memory controller 134. Having nowhere to store frame E 55e, Memory controller 134 "drops" the frame.

At time t=4+, encoder 37 has completed encoding frame A 55a, and retrieves frame B 55b from VCDU memory 35. At time t=5, video port 32 receives data corresponding to frame F 55f which is partially compressed by the DFU 42 and assigned an index value by memory controller 134. As frame B 55b has been retrieved by the encoder 37, VCDU memory 35 is no longer full and memory controller 134 is able to store the data corresponding to frame F 55f in VCDU memory 35.

It should be noted that by dropping the frame at the input to the encoding process, the encoder 37 will encode the input video stream, minus the dropped frame, in the previously dictated GOP pattern, i.e. IBBPBBP. In this way the process by which the video stream is encoded is not varied for a sequence in which a frame was dropped.

Because frame E was dropped from the video stream, problems may occur when the encoded video is decompressed and viewed. One method in which the dropped frame may be handled is to insert accurate time stamp information into the resulting MPEG stream and simply not encode the missing frame. In a decoder which references the time stamps in the video stream, the missing frame would be handled correctly. At the time in the video during which the frame would be viewed, no frame would be displayed. In this way, the audio would remain synchronized with the video.

In a decoder which does not reference time stamp information or on a decoder which requires the audio and video clocks to be locked together, such as those decoders conforming to the VideoCD standard, however, the time stamp information would be nominal. The encoded video would be a single frame shorter and since the time stamp information would not be referenced, the video will not be synchronized with the audio. Accordingly, a synthetic frame should be inserted into the video stream to synchronize the video with the corresponding audio.

Synthetic frames may be B frames or P frames. A synthetic B frame is defined as being identical to the reference frame nearest to where in the video stream the original frame was dropped. A synthetic P frame is identical to the reference frame which precedes it in the video stream. Insertion of the synthetic frame into the MPEG video stream will be discussed later herein.

The frames that are stored in VCDU memory 35 are partitioned into a 20 matrix of groups of pixels, referred to as macroblocks. Referring to FIG. 5B, a frame of M.times.N pixels 43 illustrating a head and shoulders, which is typical of a teleconferencing application, is shown partitioned into such a matrix of macroblocks 45 each comprising L.times.W pixels.

II). Motion Estimation

Suffice it to say that once the video frame data that can `fit` in VCDU memory has been subdivided into macroblocks, the CPU 12 signals the motion estimation unit 44 of the VCDU to begin motion estimation on the frame data. Macroblock based motion estimation is performed by comparing a particular macroblock in a current frame, sampled at a first time, with similarly sized macroblocks in a reference frame, sampled at a second time. In the preferred embodiment, the second sample time is prior to the sample time of the current frame.

Motion estimation covers a set of techniques used to extract the motion information from a video sequence. The MPEG standard represents motion information by providing one or two motion vectors per macroblock, depending upon the type of motion compensation; forward predicted, backward predicted, or average. The present invention implements motion estimation in the manner described below.

Each pixel in a particular frame can be modeled as a moving object in the three dimensional, horizontal, vertical and time space. A correlation procedure, performed at consecutive discrete time instances, or frames, provides information about the flow of the pixel between successive frames. Even the most efficient flow computation requires a significantly complex hardware implementation.

Motion estimation is performed on P and B frames. I frames are always intra-coded and thus never reference other frames. Motion estimation is performed by comparing an original reference image to the current input image. Motion estimation is accomplished by performing block match operations on square pixel regions of the input image. The idea is to find the block position within a larger region for a P or B frame which best minimizes error in luminance data from the reference frame.

Referring briefly to FIGS. 6A and 6B, the motion estimation process will be described with reference to a series of frames 60. Each frame of the series 60 includes pixels designated via (x,y) coordinates. The series of frames is provided in increasing temporal order, with frame 61 being the frame input at time t=0. Each frame is apportioned into 16 pixel.times.16 pixel macroblocks. Each pixel comprises 8 bits of luminance data, and 8 bits of C.sub.b and C.sub.r data, where, as mentioned above, the chrominance data is shared between 4 luminance pixel values.

A given macroblock on which motion estimation is to be performed is shown shaded as macroblock 63. As mentioned above, I frames and P frames are the only frames which serve as reference frames. When the best match is found, its location is stored for the purposes of motion compensation. As shown in FIG. 6A, the B-frame in which macroblock 63 resides uses I frame 61 for purposes of calculating motion estimation.

As seen in FIG. 6B, motion estimation is shown to include 3 discrete steps; a block matching step 66, a motion vector generation step 67 and an energy calculation step 68. Block-matching techniques are used to identify macroblocks in the preceding (and/or succeeding) frames which have the best match of pixel values to the macroblock of interest in the current frame. Typically, in block-matching techniques, the motion vector is obtained by minimizing a cost function measuring the mismatch between a block and each candidate block in the other frames. The macroblock matching procedure may be performed using a series of adder circuits or other methods apparent to those in the art.

During block matching, as mentioned above, the basic premise is to find the block position within a larger region for a P