Statistical multiplexed video encoding using pre-encoding a priori statistics and a priori and a posteriori statistics

[0002] This application is a Continuation of U.S. application Ser. No. 09/457,427 entitled “STATISTICAL MULTIPLEXED VIDEO ENCODING USING PRE-ENCODING A PRIORI STATISTICS AND A PRIORI AND A POSTERIORI STATISTICS” to Elliot N. Linzer and Aaron Wells, filed Dec. 7, 1999, now U.S. Pat. No. 6,094,457, which is a Continuation of U.S. application Ser. No. 08/775,313, now U.S. Pat. No. 6,038,256, entitled “STATISTICAL MULTIPLEXED VIDEO ENCODING USING PRE-ENCODING A PRIORI STATISTICS AND A PRIORI AND A POSTERIORI STATISTICS” to Elliot N. Linzer and Aaron Wells, filed Dec. 31, 1996.

[0003] The present invention relates generally to digital video encoding and more particularly to video encoding in which statistical multiplexing is used to combine several encoded video bit streams into a single multiplexed bit stream, e.g., for transmission on a single channel.

[0004] Many video encoding applications utilize statistical multiplexing techniques to combine several compressed video bit streams into a single multiplexed bit stream, e.g., for transmission on a single channel. The bit rate of a given compressed stream generally varies with time based on the complexity of the corresponding video signals. A statistical multiplexer attempts to estimate the complexity of the various video frame sequences of a video signal and allocates channel bits among the corresponding compressed video bit streams so as to provide an approximately constant level of video quality across all of the multiplexed streams. For example, a given video frame sequence with a relatively large amount of spatial activity or motion may be more complex than other sequences and therefore allocated more bits than the other sequences.

[0005] An example of a statistical multiplexing encoding system is described in M. Perkins & D. Arnstein, Statistical Multiplexing of Multiple MPEG-2 Video Programs in a Single Channel, SMPTE J., vol. 104, no. 9, p. 596-599, September, 1995. As described in this reference, multiple encoders each receive a respective program, encode the program, and place their compressed picture data of a video signal of the program in a corresponding buffer of fixed size pending submission to a multiplexer. (As per MPEG-2 parlance, a “program” is a collection of one or more related signals. Herein, a program is presumed to include a video signal but may also include one or more associated audio signals, a close caption text signal, etc.) A multiplexer receives the encoded programs from the multiple encoders, in the form of a bit stream. A different bit rate may be assigned to each bit stream depending on a respective estimate of the number of bits needed by the video bit stream of the corresponding program to achieve the same level of quality as the other programs with which it is multiplexed. (Generally speaking, the bit rate of the video bit stream of a program is variable whereas the bit rates of the audio and other associated bit streams of a program are constant. This invention is illustrated in the context of adjusting only the bit rate of the video bit stream portion of a program.) On the receiving end of the communication, a decoder receives the multiplexed multiple program bit stream and discards the data it does not need (e.g., if the decoder is a set top box, only the “tuned” or selected program is retained, whereas the data of each non-selected program is discarded). The retained data is inputted to the decoder's input buffer of a fixed size pending decoding. The removal of data from the decoder buffer for decoding is controlled in a strict fashion to effect a constant end-to-end delay for any selected program. In the statistical multiplexing encoding scheme, the relative timing of each to-be-multiplexed program is independent. A first encoder for a first program may have many pictures of compressed data in its buffer pending submission to the multiplexer while a second encoder for a second bit stream may have only a few pictures in its buffer pending submission to the multiplexer. A decoder that selects the first program for decoding will be receiving “earlier” pictures than a decoder that selects the second program for decoding. Such a variable delay is eliminated by each decoder lengthening or shortening the amount of time the received pictures spend in the decoder buffer pending decoding to effect the above-noted constant end-to-end delay.

[0006] FIG. 1 shows a conventional statistical multiplexer 10. The statistical multiplexer 10 includes a number n of video sources 12-i, i=1, 2, . . . n. Each of the n video sources 12-i supplies a video signal (e.g., a video bit stream) to a corresponding encoder 14-i. The encoders 14-i generate compressed video bit streams which are supplied to a multiplexer 16. The multiplexer 16 combines all of the compressed video bit streams into a single multiplexed bit stream. Each of the encoders 14-i sends statistics about the video bit stream that it is encoding to a statistics computer 18. The statistics computer 18 uses the statistics received from the encoders 14-i to determine a suitable allocation of available channel bits among the n video bit streams. The statistics computer 18 sends information regarding the allocated bit rate of each video bit stream to the corresponding encoders 14-i.

[0007] A significant problem with the conventional statistical multiplexer 10 is that bit allocation decisions are generally made using only a posteriori statistics. The statistics computer 18 therefore only receives information about pictures of the n video bit streams that have already been encoded, and must use this information to allocate bits among those pictures that have yet to be encoded. This reliance on a posteriori statistics can result in periods of poor video quality when the video bit streams are eventually demultiplexed, decoded and displayed. The degradation in video quality is particularly severe if one or more of the n to-be-encoded video signals includes a relatively large number of transitions between very complex pictures and very simple pictures. Such transitions can lead the statistics computer 18 to allocate an excessive number of bits to simple pictures of a given video bit stream, or to allocate an insufficient number of bits to complex pictures of the video bit stream, resulting in substantial degradation in perceived video quality for one or more of the multiplexed video bit streams.

[0008] The Perkins and Arnstein reference suggests an alternative to the a posteriori statistical multiplexing scheme which uses a priori statistics. An a priori statistical multiplexer is shown in FIG. 2. In the system 40, each of n video sources 42-i for i=1, 2, . . . , n outputs a to-be-encoded program to a corresponding statistics gatherer circuit or processor 43-i for i=1, 2, . . . , n, respectively. The statistics gatherers 43-i measure various statistics on the video signal of the program in order to determine the level of difficulty, at that particular instant, in compressing the uncompressed program. A statistics computer 48 receives the statistics gathered by each statistics gatherer 43-i, and allocates a bit rate to each encoder 44-i for i=1, 2, . . . , n based on the gathered statistics. A multiplexer 46 multiplexes, i.e., combines, the compressed program bit stream to form a single multiplexed bit stream for transmission on a single channel.

[0009] As noted by the Perkins and Arnstein reference, it is difficult to find statistic metrics which lead to an appropriate allocation of bit rates. For instance, if the statistic metric employed by a statistics gatherer significantly underestimates the needs of the program for which it gathers statistics, then the video bit stream of that particular program will be encoded at a significantly lower quality level relative to the other programs. This disparity in quality level will only be corrected when the nature of the video bit stream of that program changes such that the statistics gathered for that program more accurately reflect its encoding needs.

[0010] L. Wang & A. Vincent, Joint Rate Control for Multi-Program Video Coding, IEEE TRANS. ONCONS. ELECS., vol. 42, no. 3, August, 1996, proposes an alternative to statistical multiplexing. According to the Wang and Vincent reference, multiple programs are encoded as a single program. A super frame is defined including one frame from the video signal of each to-be-multiplexed program. A bit target is set for each super frame and the bit target may be nearly met by determining a quantization level for the super frame that will generate approximately the correct number of bits for each constituent frame in the super frame. The quantization level is identified by encoding each constituent frame of the super frame several times at different quantization levels, determining the number of bits generated for each encoded frame, and then searching over the encoded frames thus produced using a binary search algorithm. Note that in this encoding technique, each program is synchronized and the timing is controlled for all programs as if a single encoder produced all of the compressed bit streams. This means that the relative frame transmission rates of each program (in compressed form) do not vary relative to each other. This simplifies the rate control and is an appropriate technique to use when the receiver must decode each of the programs multiplexed together.

[0011] Note that the decoder disclosed in this reference is intended to receive and decode each program and must therefore have a large enough buffer to accommodate the frames of each program. However, even if the decoder selects only a single program for decoding and discards data for the other programs, the decoder buffer must still be increased in size relative to a decoder buffer that receives a statistically multiplexed signal. Consider that the synchronization requirement on the encoders causes each super frame to include a frame of each of the programs. However, the size of each frame varies depending on the frame type, its complexity, etc. Suppose a decoder selects a q^thprogram for decoding. The j^thframe for program q might be separated from the (j+1)^thframe by several large frames for other programs 1,2, . . . q−1. Therefore, the decoder buffer must be increased to store more frames (e.g., j−2, j−1, j) to ensure that the decoder does not underflow while waiting for the (j+1)^thframe. Such a problem does not exist in a statistical multiplexer since there is no requirement to multiplex one frame from each of the other programs between frames j and j+1, especially, when such frames are very large. Any increase in decoder buffer size requirements presents a particularly large expense for a video distribution network such as a direct broadcast satellite network or a cable television network wherein a single multiplexer may transmit a multiplexed signal to thousands or even millions of set top box receiver/decoders. As such, the statistical multiplexing technique, wherein the multiplexer allocates bit rates but wherein each program has independent timing, is preferred.

[0012] As is apparent from the above, there is a need for improved statistical multiplexing which is better able to maintain quality across multiple video bit streams.

[0013] The present invention provides a statistical multiplexing apparatus and method for generating and combining a plurality of encoded video bit streams. The statistical multiplexing of the present invention utilizes pre-stored a priori statistics, indicative of the encoding complexity of a video bit stream of an inputted program, which statistics are gathered while encoding the video bit stream a first time. The video bit stream is then re-encoded, i.e., encoded a second time, at an appropriate rate for transmission. The pre-stored a priori statistics gathered during the first encoding may include a number of bits generated for each compressed picture, an average quantization level, picture types, scene change locations and repeat field patterns. These statistics are very accurate predictions of how difficult the video bit stream will be to encode during the final encoding and therefore the quality across all of the compressed programs will be close to constant.

[0014] The present invention also provides a statistical multiplexing apparatus and method for generating and combining a plurality of compressed video bit streams using pre-stored a priori statistics gathered on the inputted video signals and a posteriori statistics gathered during the actual (final) encoding of the video bit streams. The a priori statistic metric may include inter-pixel differences within a picture or between pictures, statistics gathered from a preliminary encoding step (if performed) such as the number of bits generated for each compressed picture, repeat field pattern, average quantization level, scene change locations and picture types.

[0015] A statistics computer in the statistical multiplexer uses the pre-stored a priori statistics in conjunction with conventional a posteriori statistics generated during actual encoding to determine an appropriate bit allocation for the to-be-multiplexed bit streams. A statistical multiplexer in accordance with the present invention thus has access to additional information regarding the encoding complexity of the to-be-encoded and to-be-multiplexed video signals, and can therefore generate more accurate bit allocations and better maintain consistent video quality across multiple compressed video bit streams.

[0016] An exemplary embodiment of the invention includes a video source which generates a plurality of video signals (e.g., a plurality of program signals which each contains a video signal). The video signals are applied to a statistics gatherer which generates the above-noted pre-stored a priori statistics and stores the statistics in a first storage device. The actual video signals are stored in a second storage device. Encoders retrieve the video signals from the second storage device and encode the video signals in accordance with a bit allocation determined by a statistics computer. The statistics computer determines the bit allocation based on pre-stored a priori statistics retrieved from the first storage device in conjunction with conventional a posteriori statistics supplied from the encoders. The resulting encoded video bit streams are supplied to a multiplexer which combines the video bit streams into a single multiplexed bit stream (e.g., for output or transmission on a single channel).

[0017] In a variation on this embodiment, the video signals are pre-encoded and stored as compressed video bit streams in the storage device. The compressed video bit streams are subsequently retrieved, decoded and re-encoded by transcoders according to a bit allocation determined using both the a priori and a posteriori statistics. The transcoders generate the a posteriori statistics during the re-encoding of the video signals.

[0018] Another exemplary embodiment may include a first set of encoders which retrieve and encode stored video signals using a bit allocation determined using both pre-stored a priori statistics and conventional a posteriori statistics, and a second set of encoders which each receive a video signal directly from a video source and encode the video signals using a bit allocation determined using only conventional a posteriori statistics. Such an embodiment is particularly useful in applications in which both stored and live video signals are multiplexed. For example, this exemplary statistical multiplexer may be used in a broadcasting head-end which broadcasts previously-stored programs such as pay-per-view movies as well as live programs such as sporting or news events. (Herein the term “event” means a program with a definite start time and stop time as per MPEG parlance.)

[0019] Another exemplary embodiment of the invention includes an encoder and statistics gatherer, both of which process a number of video signals. The encoder generates corresponding encoded bit streams. The statistics gatherer generates corresponding pre-encoding a priori statistics for the video bit streams during the encoding and stores the pre-encoding a priori statistics in the storage device. The video bit streams are subsequently applied to inputs of corresponding encoders, while the sets of pre-encoding a priori statistics are retrieved from the storage device and applied to a statistics computer. The statistics computer utilizes the pre-encoding a priori statistics to allocate available channel bits between the to-be-multiplexed video bit streams. The encoders re-encode the video bit streams using the bit allocation determined by the statistics computer. The re-encoded video bit streams are then applied to a multiplexer which combines the video bit streams into a single multiplexed bit stream. This exemplary statistical multiplexer generates improved bit allocation decisions in part by utilizing pre-encoding a priori statistics generated from a previous encoding of the to-be-multiplexed video bit streams.

[0020] These and other features and advantages of the present invention will become more apparent from the accompanying drawings and the following detailed description.

[0021] FIG. 1 shows a first conventional statistical multiplexer.

[0022] FIG. 2 shows a second conventional statistical multiplexer.

[0023] FIGS. 3 and 4 show first and second exemplary embodiments of a statistical multiplexer utilizing a priori and a posteriori statistics in accordance with the present invention.

[0024] FIG. 5 shows a third exemplary embodiment of a statistical multiplexer utilizing pre-encoding a priori statistics in accordance with the present invention.

[0025] FIG. 6 shows a fourth exemplary embodiments of a statistical multiplexer utilizing a priori and a posteriori statistics in accordance with the present invention.

[0026] The present invention will be illustrated below using a number of exemplary statistical multiplexers suitable for use in video encoding applications. It should be understood, however, that the invention is more broadly applicable to any application which involves bandwidth allocation between multiple encoded bit streams. Furthermore, although particularly well-suited for use in MPEG-2 applications, the invention may be utilized with encoded bit streams generated using other encoding techniques. The term “pre-stored statistics” should be understood to include any type of information indicative of the encoding complexity of a given signal which is generated before a bit allocation decision is made for that program. This information may be stored in a storage device as in the illustrative embodiments, in an internal random-access memory of a statistics computer, or elsewhere as required in a particular application.

[0027] FIG. 3 shows an exemplary statistical multiplexer 20 in accordance with a first exemplary embodiment of the present invention. The statistical multiplexer 20 includes a video source 22 which generates a number n of video signals. The n video signals are applied to a statistics gatherer 24 which gathers a priori statistics regarding the n video signals. The statistics gatherer 24 stores a set of a priori statistics 27-i, i=1, 2. . . n for each of the n video signals on a first storage device 26. The video source 22 also supplies the video signals to a second storage device 28. The second storage device thus includes n stored video signals 29-i. The first and second storage devices 26, 28 may be optical or magnetic hard drives, disk arrays or electronic memory. The first and second storage devices 26 and 28 can also be combined into a single storage device.

[0028] Optionally, the statistics gatherer 24 may include an encoder for encoding each received video signal. Encoding may be performed according to, for example, the MPEG-2 standard as disclosed in ISO/IEC IS 13818-1,2,3. The contents of these standards documents are incorporated herein by reference. In such a case, the a priori statistics may be generated during this pre-encoding of the video signals. Furthermore, the statistics gatherer 24 may output the compressed video bit streams produced by the encoding for storage in the second storage device 28 instead of the uncompressed video signals outputted from the video source 22. Preferably, however, the uncompressed video signals are stored in the second storage device 28 and certain encoding results, e.g., motion estimation results, such as optimal motion vectors, inter/intra decisions, coded/non-coded macroblock decisions, etc., are stored in the second storage device 28 along with the uncompressed video signals.

[0029] Although the statistical multiplexer 20 is shown in a form suitable for non-real-time encoded video signals, it can easily be adapted for real-time encoding. For instance, one video source 22 and a corresponding statistics gatherer can be provided for each video signal to be encoded in parallel. The second storage device 28 in this embodiment need not store the entire video signal of the event of the corresponding program. Rather, as described in greater detail below, only temporary storage for a limited number of frames need be provided.

[0030] A statistics computer 30 retrieves the pre-stored a priori statistics 27-i from the first storage device 26. The corresponding stored video signals 29-i are retrieved from the second storage device 28 and applied to respective encoders 32-i. The encoders 32-i may be configured to operate in accordance with the MPEG-2 standard. Each encoder 32-i produces a compressed video bit stream.

[0031] Alternatively, the encoders 32-i are transcoders which include decoders. The decoders are for first decoding the retrieved video signals 29-i, in the event the retrieved video signals 29-i are already compressed. The transcoders 32-i then re-encode the video signals 29-i. Preferably, the retrieved video signals 29-i are uncompressed but include encoding information previously determined during pre-encoding by the statistics gatherer 24. The encoders 32-i encode the video signals using such retrieved encoding information.

[0032] The statistic computer 30 also receives additional information in the form of a posteriori statistics from the encoders 32-i regarding the video signals being encoded. The statistics computer 30 utilizes the pre-stored a priori statistics 27-i and the additional a posteriori information from the encoders 32-i to allocate the available channel bits among the n video signals to be encoded. The resulting compressed bit streams are supplied from the encoders 32-i to inputs of a multiplexer 34. The multiplexer 34 combines the multiple compressed bit streams into a single multiplexed bit stream outputted on channel output 35. The statistics computer 30 may be implemented as an application-specific integrated circuit (ASIC), microprocessor or other digital data processor programmed to provide the described processing functions. Some or all of the functions of statistics computer 30 may be provided by an integrated processing device which also provides certain functions of the statistics gatherer 24 as well as one or more of the encoders 32-i.

[0033] The statistics computer 30 in the statistical multiplexer 20 utilizes pre-stored a priori information about the video bit stream that each encoder 32-i is about to encode before allocating bits among the encoders. The statistical multiplexer 30 also operates in a manner similar to the conventional statistical multiplexer 10 of FIG. 1 insofar as it utilizes information supplied from the encoders as the video signals are being encoded. This use of both pre-stored a priori and a posteriori statistics is particularly useful in situations in which a portion of a video bit stream that the statistics computer 30 determined would be simple to encode turns out to be much more difficult to encode at a specific allocated bit rate. The statistics computer 30 of FIG. 3 has more information available to it than a conventional statistics computer, and can therefore make more accurate bit allocation decisions and better maintain video quality across multiple encoded bit streams.

[0034] As per the statistical multiplexing paradigm, the video signals outputted form the video source 22 have mutually independent timing. The encoders 32-i independently encode the received video signals 29-i in an asynchronous fashion—the picture rates of the encoders 32-i are not synchronized. Likewise, in multiplexing the compressed video bit streams, the instantaneous picture rates of each compressed video signal in the multiplexed bit stream are independent and fluctuate with respect to each other.

[0035] FIG. 4 shows another exemplary statistical multiplexer 50 utilizing pre-stored a priori statistics in accordance with the present invention. The statistical multiplexer 50 includes a video source 52, statistics gatherer (and optional encoder) 54, first storage device 56 storing n sets of pre-stored a priori statistics 57-i, second storage device 58 storing n video signals 59-i, a statistics computer 60 and encoders 62-i, all of which are used to provide substantially the same functions as the corresponding elements of the FIG. 3 statistical multiplexer 20. The statistical multiplexer 50 also includes k additional video sources 66-j, j=1, 2, . . . k. The output of each of the k additional video sources is applied to a corresponding video encoder 68-j. The encoders 68-j supply conventional a posteriori statistics to the statistics computer 60. The statistics computer 60 processes the a posteriori statistics from the encoders 68-j in a conventional manner to thereby determine appropriate bit allocations for the k video signals from video sources 66-j.

[0036] The statistics computer 60 uses both pre-stored a priori statistics and a posteriori statistics to determine appropriate bit allocations for the n video signals stored in the second storage device 58, as was previously described in conjunction with FIG. 3 above. The compressed bit streams outputted from the n encoders 62-i and the k encoders 68-j are applied to inputs of a multiplexer 64 which combines the n+k separate encoded bit streams into a single multiplexed bit stream outputted on channel output 65. The statistical multiplexer 50 of FIG. 4 allows certain previously-stored video signals to be encoded using both pre-stored a priori statistics and a posteriori statistics, while other video signals are encoded using conventional a posteriori statistics only. Such an embodiment is particularly useful in applications in which both stored and live video streams are multiplexed. For example, the statistical multiplexer 50 may be used in a broadcasting head-end which broadcasts previously-stored video signals such as pay-per-view movies as well as live video signals such as sporting or news events.

[0037] FIG. 5 shows another exemplary statistical multiplexer 80 utilizing only pre-stored a priori statistics in accordance with the present invention. The statistical multiplexer 80 includes n video sources 82-i, for i=1, 2, . . . , n. Each video source outputs a video signal to a corresponding statistics gatherer/encoder 84-i, for i=1, 2, . . . , n. The encoder portion of the elements 84-i encodes the video signals, but preferably stores the video signals as uncompressed bit streams 85-i, i=1, 2, . . . n in the storage device 86. Illustratively, the storage device 86 may be connected to the statistics computer 90 as shown, connected to, and distributed amongst, each element 84-i or connected in a similar fashion as the storage devices 26,28 (FIG. 3) or 56,58 (FIG. 4). Additionally, certain pre-encoding results 89-i, for i=1, 2, . . . , n, such as motion estimation results (optimal motion vectors, inter/intra decisions, coded/non-coded macroblock decisions), etc. are also stored with the video signal in the corresponding bit stream. Note that it is not necessary to store an entire video signal 85-i in such form in the storage device 86. Rather, it is possible to temporarily store only one or more pictures of a currently encoded video signal. Thus, this solution is amenable to even a real-time or live program event provided a one or more picture delay can be tolerated in the end-to-end feed (which is common place in ordinary live terrestrial broadcasts). The statistics gatherer portion of the elements 84-i generate corresponding pre-encoding a priori statistics for the n video signals being encoded. The n sets of pre-encoding a priori statistics 87-i are stored by the statistics gatherer portion of the elements 84-i in storage device 86.

[0038] The video bit streams 85-i are retrieved from storage device 86 and applied to inputs of corresponding encoders 88-i, while the sets of pre-encoding a priori statistics 87-i are retrieved from storage device 86 and applied to a statistics computer 90. The statistics computer 90 utilizes the n sets of pre-encoding a priori statistics 87-i to allocate available channel bits between the n bit streams to be multiplexed. The encoders 88-i each re-encode the retrieved video bit streams using the bit allocation determined by the statistics computer 90. Illustratively, if pre-encoding information 89-i is stored in the storage device 86, it is retrieved and used by the encoders 88-i in re-encoding the retrieved video bit streams 88-i. The re-compressed bit streams are applied to a multiplexer 94 which combines the re-compressed bit streams into a single channel output 95. The statistical multiplexer 80 of FIG. 5 generates improved bit allocation decisions by utilizing pre-encoding a priori statistics which are generated from a previous encoding of the video bit streams to be multiplexed.

[0039] FIG. 6 shows another statistical multiplexer 70 according to the present invention which uses both a priori and a posteriori statistics in allocating available channel bits. A statistics gatherer and encoder element 72 receives n video signals. An encoder portion of the element 72 encodes each video signal to produce a compressed video bit stream 75-i, for i=1, 2, . . . , n. A statistics gatherer portion of element 72 gathers a priori statistics 77-i, for i=1, 2, . . . , n which may include pre-encoding statistics gathered during the encoding of the respective video signal, or other a priori statistics (e.g., inter-pixel differences). The compressed video bit streams 75-i and a priori statistics 77-i (and optionally, pre-encoding result information) are stored in a storage device 74.

[0040] Each compressed bit stream 75-i (and respective optional pre-encoding results) is retrieved from the storage device 74 by a corresponding transcoder 78-i, for i=1, 2, . . . , n. Likewise, a statistics computer 76 retrieves the a priori statistics 77-i corresponding to the retrieved compressed video bit streams 75-i. Each transcoder 78-i has a decoder portion which decodes the retrieved compressed video bit stream to reproduce the video signal. Each transcoder 78-i also has an encoder which re-encodes the reproduced video signal to produce a re-compressed video signal. The re-encoding of the reproduced video signal in each transcoder 78-i is controlled to achieve a bit rate as per a bit allocation received from the statistics computer 76. In re-encoding the reproduced video signals, the transcoders 78-i gather aposteriori statistics indicating the complexity involved in re-encoding the reproduced video signals. These a posteriori statistics are inputted to the statistics computer 76. The statistics computer 76 uses both the a priori and aposteriori statistics in allocating available channel bits to each transcoder 78-i. The re-compressed video bit streams are outputted to a multiplexer 71 which combines the re-compressed video bit streams into a single multiplexed bit stream which is outputted on channel output 73.

[0041] In the statistical multiplexer 20 of FIG. 3, the statistical multiplexer 50 of FIG. 4 and the statistical multiplexer 70 of FIG. 6, the pre-stored a priori statistical metric 27-i, 57-i or 77-i may be inter-pixel differences within a single picture or between multiple pictures. In the statistical multiplexer 20 of FIG. 3, the statistical multiplexer 50 of FIG. 4, the statistical multiplexer 70 of FIG. 6 or the statistical multiplexer 80 of FIG. 5, the pre-stored a priori statistics 27-i, 57-i, 77-i or 87-i may be pre-encoding gathered statistical metrics such as the number of bits in each picture, repeat field pattern, average quantization level, scene change locations and picture types used. The pre-encoding statistics tend to provide more accurate predictors of the complexity in encoding a video signal. In the statistical multiplexers 20, 50 and 70, the a posteriori statistical information gathered by the encoders 32-i, 62-i or 78-i can be similar to the pre-encoding information, i.e., the number of bits per picture, repeat field pattern, average quantization level, scene change location and picture type information can be used.

[0042] In the statistical multiplexers 20, 50, 70 or 80, the pre-encoding (if performed in the statistical multiplexers 20, 50 or 70 ) in the encoders 24, 54, 72 or 84 may be performed in one of a number of manners. In the first embodiment, pre-encoding is performed so as to achieve a constant bit rate. For example, the channel bit rate is divided by the number n of programs to be pre-transmitted over that channel. Each program is pre-encoded with an equal bit rate allocation. In a second embodiment, the pre-encoding is performed at a constant quantization level. In a third embodiment, the pre-encoding is performed using a constant “base quantization level” that is adjusted upward or downward for each macroblock based on the visual sensitivity of that macroblock to quantization noise.

[0043] In the statistical multiplexer 80 where only pre-encoding a priori statistics are used, the actual setting of final transmission bit rates may be performed as follows:

[0044] (1) The complexity of a given picture is determined form the a priori statistic stored for that picture. In the statistical multiplexer 80, after the picture has been pre-encoded, the complexity is determined as the product of the number of bits generated for that picture during pre-encoding, a measure of the quality distortion caused by quantization noise incurred during pre-encoding, and a constant which depends on the picture coding type. Preferably, the constant is 1.0 for I (intra) and P (forward only predictive) pictures and in the range of 0.7 to 0.9 for B (bidirectionally predictive) pictures.

[0045] (2) The statistics computer 90 determines an estimate of the sum of the complexities of the next K₀pictures to-be-pre-encoded. Illustratively, K₀is a predetermined integer constant that is greater than or equal to 1. Depending on the implementation, the complexities may have been already determined for some or all of the K₀pictures. For instance, if the program is a stored, completely pre-encoded event, then the estimate is an accurate sum. If the program is a live event or a real-time encoded event, then it is possible that less than K₀complexities are pre-stored and available. For those complexities not available, an estimate is formed using the most recent complexity generated for a picture of the same type.

[0046] For example, suppose the program is a live event, K₀=15, the picture 0 is to be re-encoded, but statistics for only 5 pictures (numbered 0,1,2,3 and 4) are pre-encoded and stored. Suppose the picture 0 is an I picture and the group of picture sequence is I₀B₁B_{2 P3 B4}B₅P₆B₇B₈. . . , where the subscript indicates the number (i.e., in encode order) of the picture. Furthermore, suppose that the following complexities are available for pre-encoded pictures I₀, B₁, B₂, P₃, B₄: complexity for I₀=100, complexity for B₁=8, complexity for B₂=12, complexity for P₃=25 and complexity for B₄=10. Then the following complexities are used to generate the sum:

[0047] Thus, the statistics computer 90 estimates the sum complexity as 400 for this program (at this moment).

[0048] (3) The statistics computer 90 sets the bit rate for the program in proportion to the estimate sum produced for that program relative to the sum produced for all to-be-multiplexed programs.

[0049] This process is repeated periodically. The process may be repeated as frequently as once every picture period of each program, less frequently, such as once every Ko picture periods for each program, some frequency in between these two, etc.

[0050] In one embodiment, the average quantization parameter used to encode the picture may be used as the measure of the quality of distortion caused by the quantization noise in producing the complexity product. In a second embodiment, the average quantization parameter is increased if the image is smooth (so that the quantization noise is easily visible) and decreased if the image has a large amount of texture (so that the quantization noise is masked and not easily visible).

[0051] The third step may be further modified to ensure that each program is not allocated an excessively large or small amount of bits. For example, the statistics computer 90 may ensure that the bit rate determined for each program lies between threshold maximum and minimum bit rates. Alternatively, the second step can be modified to ensure that the complexity sum lies between threshold minimum and maximum complexity sums or that any individual complexity product lies between maximum and minimum complexity product thresholds for the corresponding picture type. (In this latter case, the complexity product thresholds for I pictures will be higher than the complexity product thresholds for B pictures.)

[0052] When repeat field detection is used, each encoded picture will contain a variable number of video fields in which it is displayed. For instance, a frame picture without a repeated first field will be displayed for two field periods, whereas a frame picture with a repeated first field will be displayed for three field periods. Repeated fields tend to reduce the number of bits in the compressed bit stream since no data is transmitted for the field that is repeated. Thus, when more repeated fields are present, the rate at which pictures are transmitted decreases as well as the bit rate. Such a situation may be accounted for in the rate allocation scheme by allocating bits to a program in proportion to the product of the sum complexity and the ratio of the number of pre-encoded pictures to the number of displayed fields in the pre-encoded pictures.

[0053] The following technique may be used for allocating bit rates amongst the to-be-multiplexed programs in the statistical multiplexers 20, 50 and 70 using both a priori and a posteriori statistics. A base bit rate is assigned to each encoder 32-i, 62-i and 78-i using any well-known “feed back” or a posteriori statistical multiplexing process, such as the process described in the Perkins & Arnstein reference. This base rate is denoted Ri for the ith to-be-encoded program.

[0054] One or more pre-stored a priori statistics is measured for each program prior to the final encoding which a priori statistics can be gathered during a pre-encoding step or without pre-encoding the program. In the case that pre-encoding is performed, the statistic can be the above-noted complexity sum. In the case that pre-encoding is not performed, the statistic can also be a measure of spatial complexity such as the sum of local intra-picture variances or sum of adjacent pixel absolute differences. The statistic can also be a measure of inter-picture complexity such as the sum of the absolute differences formed by subtracting a pixel in one picture from a corresponding pixel in the following picture. A combination of such statistics may also be used. Note that the pre-encoding statistics tend to produce more accurate results. However, the statistics generated without pre-encoding provide a savings in hardware and/or time.

[0055] Let SFuture_ibe the sum of the a priori statistics for the next K₁pictures for the program i, where K₁is a predetermined constant. Let SPast_ibe the sum of the a posteriori statistics for the previous (already encoded) K₁pictures. The bit rate for program i may be set in proportion to:

[0056] R_i·f(SFuture_i, SPast_i)

[0057] where f(SFuture_i, SPast_i) is a function that equals one if SFuture_i=SPast_i, that is greater than one if SFuture_i>SPast_i, and that is less than one if SFuture_i<SPast_i. For example, the following may used for function f(SFuture_i, SPast_i): $f\left({\mathrm{SFuture}}_i,{\mathrm{SPast}}_i\right)=\frac{K_2+{\mathrm{SFuture}}_i}{K_2+{\mathrm{SPast}}_i}$

[0058] where K₂is a predetermined constant. A large value of K₂makes function f(SFuture_i, SPast_i) less sensitive to a priori statistics whereas a small value of K makes the function f(SFuture_i, SPast_i) more sensitive to a priori statistics.

[0059] When the statistical multiplexer 50 of FIG. 4 is used, the statistics computer 60 uses only a posteriori information for the encoders 68-i and both a priori and a posteriori information for the encoders 62-i. In this statistical multiplexer 50, the function f(SFuture_i, SPast_i) may be defined in the same way for those encoders 62-i for which both a priori and a posteriori information is used in determining the bit allocation. For the encoders 68-i for which only aposteriori information is used to determine the bit allocation, the function f(SFuture_i, SPast_i) may be set to 1.

[0060] It should be understood that the foregoing description is merely illustrative of the invention. Numerous alternative embodiments within the scope of the appended claims will be apparent to those of ordinary skill in the art. For example, although the multiplexers 34, 64, 71 and 94 are illustrated as combining n encoded video bit streams into a single channel, alternative multiplexers could be used to combine subsets of the n encoded bit streams into several different channels.