Method and apparatus for effecting seamless data rate changes in a video compression system

[0002] The present invention relates generally to the fields of digital television and video compression, and more particularly relates to methods and apparatus for effecting seamless rate changes in a video compression system employing buffers.

[0003] The background of the present invention is described herein in the context of pay television systems, such as cable television and direct broadcast satellite (DBS) systems. However, the invention is by no means limited thereto except as may be expressly set forth in the accompanying claims.

[0004] In the pay television industry, programmers produce programs for distribution to various remote locations. A “program” may consist of video, audio, and/or other related services, such as closed-captioning and teletext services. A programmer supplies these services, e.g., via satellite, to individual subscribers and/or cable television operators. Typically, many separately encoded, compressed programs are multiplexed together and sent over a data channel to cable television operators. The cable operators receive the multiplex and select the programs/services they wish to distribute to their subscribers. The selected programs are then transmitted to the individual subscribers via a coaxial cable distribution network.

[0005] In the past, pay television systems have operated in the analog domain. Recently, however, the pay television industry has begun to move toward all digital systems wherein, prior to transmission, the analog program signals are converted to digital signals. Digital signal transmission offers the advantage that digital data can be processed at both the transmission and reception ends to improve picture quality. In addition, digital data compression techniques can achieve high signal compression ratios. Digital compression allows a larger number of individual services to be transmitted within a fixed bandwidth. Bandwidth limitations are imposed by both satellite transponders and coaxial cable distribution networks, and therefore digital compression is extremely advantageous.

[0006] FIG. 1 depicts an exemplary application of a vector quantization image compression system wherein image data is communicated from a point of origin 12 to receiving locations 14, 16. (It should be noted that the invention is not limited to use in a vector quantization system, or any other particular type of encoding system. For example, the invention may be employed in a system using discrete cosine transform (DCT) encoding, such as an MPEG system.) The point of origin 12 might include a source 20 of program material that supplies movies and the like in analog form to an encoder 22 for digitization and data compression by vector quantization. Compressed digital data is transmitted to a satellite 18 via transmitter 24 for reception by a plurality of earth stations 14, 16. The earth stations 14, 16 may be the head-end of a cable television distribution system of the type which receives signals from the satellite 18 and distributes them to a plurality of subscribers via coaxial cable or optical fiber. Alternatively, one or more of the earth stations may be DBS (direct broadcast satellite) subscribers who receive signals directly from the satellite 18. The cable head-end installation 14 may receive the data transmitted by the station 12 via a receiver 26 and then employ an on-site decoder 28 for decompressing the received data and converting the same back to analog form. Another on-site apparatus 30 may convert the analog data to conventional NTSC signals for transmission over cable to subscribers in conventional form. Thus, in the case of cable head-end installation 14, the cable head-end operator distributes analog NTSC cable television signals to subscribers in conventional form. Further background on digital television can be found in U.S. patent application Ser. No. 968,846, Oct. 30, 1992, titled System and Method for Transmitting a Plurality of Digital Services, and U.S. Patent No. __ (application Ser. No. 794,516, issued Dec. 15, 1992), titled Image Compression Method and Apparatus Employing Distortion Adaptive Tree Search Vector Quantization.

[0007] A problem with the prior art is caused by the fact that, when the program provider decides to change the data rate at which a given program is encoded and provided to cable operators, there is often a noticeable interruption in the picture received by the viewers that are watching that program. One reason for effecting such a rate change would be to increase the amount of data received by the cable operators and to thereby improve the quality of the television pictures received by the viewers. Typically, the program multiplex is provided to the data channel at a fixed rate, although the individual programs composing the multiplex are compressed with a variable rate coding scheme. This means that buffers are required at the encoder(s) and decoder(s). If the encoding rate R_iof one program is changed in a system with a fixed rate data channel, the encoding rates of all other programs must be adjusted such that the total data rate R is fixed (where R equals the sum of the data rates of the individual program channels). As programs are encoded by a program provider prior to being sent to a cable operator, the encoding rate for each program must be controlled to avoid decoder buffer overflows and underflows, which, if allowed to occur, would produce a noticeable interruption in the viewers' television pictures.

[0008] Accordingly, a primary goal of the present invention is to provide methods and apparatus whereby the encoding rate is adjusted automatically to avoid any overflows or underflows in the viewers' decoder buffers.

[0009] The present invention provides methods and apparatus especially suited for video compression systems (e.g., pay television systems) comprising at least one encoder for compressing program data, an encoder buffer, and one or more decoders connected to associated decoder buffers. An example of such a system is described below in connection with a detailed description of one prefer red embodiment of the invention. The present invention will most often be employed by program providers th at send compressed digital program data to cable operators. The cable operators select the particular programs to provide to their viewers. The present invention allows the program provider to change the rate at which program data is encoded and transmitted to cable operators such that the rate change is seamless, i.e., such that the decoder buffers neither overflow nor underflow.

[0010] A method for operating a video compression system in accordance with the present invention comprises the steps of (a) changing the rate at which an encoder provides data to an encoder buffer from a first rate R to a second rate R′; and (b) maintaining the encoder buffer occupancy b_e(t) such that the following conditions are maintained: (1) prior to time T_O−T_d, max{0, RT_d−B_d}≦b_e(t)≦min{B_e, RT_d}; and (2) after time T_O, max{0, R′T_d−B_d}≦b_e(t) ≦min{B₃, R′T_d}; and (3) during the time T_O−T_d≦t≦T_O, max{0, RT_O−Rt+R′t+R′T_d−R′T_O−B_d}≦b_e(t)≦min{B_e, RT_O−Rt+R′t+R′T_dR′T_O}; wherein t represents time, T_Orepresents the time at which the data rate changes from R to R′, B_drepresents the maximum capacity of the decoder buffer, and T_drepresents the delay caused by the encoder and decoder buffers. The value of T_dwill typically be determined by the startup strategy used by the system; it is the delay between the time a compressed picture enters the decoder and the time the picture is removed from the decoder buffer for decompression and display.

[0011] A presently preferred implementation of the present invention further comprises the steps of multiplexing the data from the encoder buffer with data from at least one other encoder buffer, and transmitting a multiplex comprising the multiplexed data over a data channel to the decoder buffer. The invention may be used in connection with vector quantization and DCT encoding schemes. Other schemes may be used as well.

[0012] The present invention also provides means for carrying out the inventive method summarized above.

[0013] In addition, the present invention provides a system for providing a plurality of programs to a cable operator or individual subscriber having means for selecting a desired program for viewing, a decoder and a decoder buffer providing the selected program to the decoder. The system comprises first and second encoders (although more than two encoders may be employed) each receiving program data; first and second encoder buffers respectively coupled to the first and second encoders; a multiplexor receiving data from the first and second encoders and outputting a multiplex to a data channel for reception by the cable operator or subscriber; and a control computer coupled to the first and second encoders and to the multiplexor, the controller comprising program means for changing the rates at which the encoders provide data to their encoder buffers and the encoder buffers provide data to the multiplexor. According to the invention, the control computer controls the occupancies of the encoder buffers such that the decoder buffer neither overflows nor underflows when the rate at which either encoder provides data to its buffer is changed from a first rate R to a second rate R′.

[0014] Other features of the present invention are described below.

[0015] FIG. 1 is a block diagram of a pay television system.

[0016] FIG. 2 is a block diagram of one embodiment of a video compression system in accordance with the present invention.

[0017] FIG. 3 depicts the constraints the system of FIG. 2 places on the encoder buffer occupancy as the compression rate is increased from 4 Mbps to 6 Mbps.

[0018] FIG. 4 depicts the constraints placed on the encoder buffer occupancy as the compression rate is decreased from 8 Mbps to 4 Mbps and to 1.2 Mbps.

[0019] FIG. 2 is a block diagram of a video compression system in accordance with the present invention. The system includes a control computer 52; plurality of encoders 54, 56, 58; a plurality of encoder buffers 60, 62, 64; a multiplexor 66; a data channel 70; a demultiplexor 80; a decoder buffer 82; a decoder 84; and display 86. Of course, although only one is shown, there would normally be many additional multiplexor-decoder buffer-decoder-display combinations. In addition, the decoder 84 and display 86 may be contained in a television set, while the demultiplexor 80 and decoder buffer 82 may be located at the site of the cable operator or in a separate set top unit. As indicated in FIG. 2, the multiplexor 66 transmits data at a prescribed rate R to the data channel 70 and the demultiplexor 80 provides data to the decoder buffer 82 at the rate R_j, where the index i (i=1, 2, . . . N) represents the selected channel. The present invention relates to the manner in which the control computer controls the encoders and multiplexor 66 to avoid overflows and underflows of data provided to the decoder buffer 82. Such control is particularly important when the rates R₁, R₂, . . . R_Nat which the encoders provide data to their buffers (which are the same as the rates at which the buffers provide data to the multiplexor 66) are changed. Accordingly, this specification describes in detail the manner in which such overflows and underflows may be avoided. The other components are known in the art and thus are not described in detail herein.

[0020] Assume a variable-rate compression scheme and a variable-rate data channel are employed. In a representative case, the encoder buffer occupancy is given by: $\begin{array}{c}{b}_e\left(0\right)=0\\ b_e\left(t\right)={\int }_0^{t}e\left(\tau \right)d\tau ,\mathrm{for}0\le t\le T_e\\ b_e\left(T_e\right)=\frac{B_e}{2}\\ b_e\left(t\right)=\frac{B_e}{2}+{\int }_{T_e}^{t}e\left(\tau \right)d\tau -{\int }_{T_e}^{t}R\left(\tau \right)d\tau ,\mathrm{for}t\ge T_e\end{array}$

[0021] In the above equations, e(τ) is the instantaneous bit rate out of the encoder, where τ is a time variable used in the integration; T_eis the time at which the multiplexor 66 starts reading data out of the buffer; B_eis the maximum capacity of the encoder buffer, in bits; and R(τ) is the rate at which the multiplexor 66 reads data from the buffer for output to the data channel 70 (this is preferably a constant). Similarly, the decoder buffer occupancy equations are: $\begin{array}{c}{b}_d\left(0\right)=0,\mathrm{for}t\le T_e\\ b_d\left(t\right)={\int }_{T_e}^{t}R\left(\tau \right)d\tau ,\mathrm{for}{T}_e\le t\le T_d\\ b_d\left(T_e\right)=\frac{B_d}{2}\\ b_d\left(t\right)=\frac{B_d}{2}+{\int }_{T_d}^{t}R\left(\tau \right)d\tau -{\int }_0^{t-T_d}e\left(\tau \right)d\tau ,\mathrm{for}t\ge T_d\end{array}$

[0022] In the decoder equations, the terms have meanings similar to their counterparts in the encoder equations. The decoder equations are based on the premise that the first bits removed from the buffer at the decoder are the first bits added to the buffer at the encoder, and that the bits are removed at the same rate as they are added, taking into account the delay.

[0023] The present inventor has determined that the sum of the encoder and decoder buffer occupancies is a constant when the encoder is operating at a fixed rate and the effects of encoder and decoder startup have disappeared, i.e., when the encoder-decoder pair is in its “steady-state” mode. Of course, for this condition to be true, one must take into account the delay through the system. That is, if we take the decoder buffer occupancy at some arbitrary time t_O, we must take the encoder buffer occupancy at t_O−T_d, where T_dis the delay experienced by the data as it travels from the encoder buffer to the decoder buffer. Accordingly, we are interested in the sum of the decoder and encoder occupancies, b_d(t)+b_e(t−T_d), at t≧T_dand t−T_d≧T_e, or t≧T_d+T_e.

[0024] It is apparent from the above equations that this sum is given by: $\begin{array}{c}{b}_d\left(t\right)+b_e\left(t-T_d\right)=\frac{B_d}{2}+{\int }_{T_d}^{t}R\left(\tau \right)d\tau -{\int }_0^{t-T_d}e\left(\tau \right)d\tau +\\ \frac{B_e}{2}+{\int }_{T_e}^{t-T_d}e\left(\tau \right)d\tau -{\int }_{T_e}^{t-T_d}R\left(\tau \right)d\tau \\ =\frac{B_d}{2}+\frac{B_e}{2}-{\int }_0^{T_e}e\left(\tau \right)d\tau +\\ {\int }_{T_d}^{t}R\left(\tau \right)d\tau -{\int }_{T_e}^{t-T_d}R\left(\tau \right)d\tau \\ =\frac{B_d}{2}+{\int }_{T_d}^{t}R\left(\tau \right)d\tau -{\int }_{T_e}^{t-T_d}R\left(\tau \right)d\tau \\ =\frac{B_d}{2}+{\int }_{T_d}^{t-T_d}R\left(\tau \right)d\tau +{\int }_{t-T_d}^{t}R\left(\tau \right)d\tau -\\ {\int }_{T_e}^{T_d}R\left(\tau \right)d\tau -{\int }_{T_d}^{t-T_d}R\left(\tau \right)d\tau \end{array}$

[0025] From these equations, it follows that the sum of the encoder and decoder buffer occupancies can be expressed as $\begin{array}{c}{b}_d\left(t\right)+b_e\left(t-T_d\right)=\frac{B_d}{2}+{\int }_{t-T_d}^{t}R\left(\tau \right)d\tau -{\int }_{T_e}^{T_d}R\left(\tau \right)d\tau \\ ={\int }_{t-T_d}^{t}R\left(\tau \right)d\tau \end{array}$

[0026] When R(τ) is a constant R, this equation becomes: b_d(t)+b_e(t−T_d)=RT_d, where RT_dis a constant. The decoder buffer occupancy can thus be expressed in terms of the encoder buffer occupancy and the instantaneous rate at which data is read from the encoder R(τ): $b_d\left(t\right)={\int }_{t-T_d}^{t}R\left(\tau \right)d\tau -b_e\left(t-T_d\right),\mathrm{for}t\ge T_d+T_e$

[0027] To prevent overflows and underflows, i.e., to ensure seamless rate changes, we require $0\le {\int }_{t-T_d}^{t}R\left(\tau \right)d\tau -b_e\left(t-T_d\right)\le B_d$

[0028] From the above inequality, the encoder buffer occupancy should be constrained as follows: $b_e\left(t-T_d\right)\le {\int }_{t-T_d}^{t}R\left(\tau \right)d\tau$ $b_e\left(t-T_d\right)\ge {\int }_{t-T_d}^{t}R\left(\tau \right)d\tau -B_d$

[0029] The top constraint prevents underflows, i.e., the situation where b_d(t) is less than or equal to zero, and the lower constraint prevents overflows, wherein b_d(t) is greater than or equal to B_d.

[0030] By a change in variable (t=t−T_d) , the above inequalities can be rewritten as $b_e\left(t\right)\le {\int }_t^{t+T_d}R\left(\tau \right)d\tau$ $b_e\left(t\right)\ge {\int }_t^{t+T_d}R\left(\tau \right)d\tau -B_d$

[0031] In a constant bit rate operation, i.e., where R(τ) is a constant R, we have

[0032] b_e(t)≦RT_d

[0033] b_e(t)≧RT_d−B_d

[0034] We also have the practical constraint

[0035] 0≦b_e(t)≦B_e

[0036] Therefore, the encoder buffer occupancy constraint may be expressed as

[0037] max (0, RT_d−B_d)≦b_e(t)≦min (B_e,RT_d)

[0038] Assume now that the data rate changes from R to R′ at time t =T_O. For t≦T_O−T_d, we have

[0039] max(0RT_d−B_d)≦b_e(t)≦min (B_e,RT_d)

[0040] For t≧T_O, we have

[0041] max(0,R′T_d−B_d)≦b_e(t)≦min(B_e, R′T_d)

[0042] For T_O−T_d≦t≦T_O, we have $b_e\left(t\right)\le \min \left(B_e,{\int }_t^{T_0}Rd\tau +{\int }_{T_0}^{t+T_d}{R}^{\prime }d\tau \right)$ $b_e\left(t\right)\ge \max \left(0,{\int }_t^{T_0}Rd\tau +{\int }_{T_0}^{t+T_d}{R}^{\prime }d\tau -B_d\right)$

[0043] These inequalities may be reduced to the following:

[0044] b_e(t)≦min(B_e, RT_O−Rt+R′t+R′T_d−R′T_O)

[0045] b_e(t)≧max(0, RT_O−Rt+R′t+R′T_d−R′T_O−B_d)

[0046] The encoder buffer occupancy constraint expressed above is graphically represented by FIGS. 3 and 4. In the example of FIG. 3, the data rate is changed from R=4 Mbps to R′=6 Mbps, with T_d=½ sec. For t≧T_O, we have R′T_d−B_d=1 Mb, or R′T_d=3 Mb. Therefore, the encoder buffer occupancy must be controlled to lie between the broken lines to ensure that the rate change is seamless.

[0047] FIG. 4 represents examples in which the rate changes from R=8 Mbps to R′=4 Mbps and R′=1.2 Mbps, with B_e=B_d=2Mb and T_d=¼ sec. For the change to R′=4 Mbps, we have RT_d=2 Mb, RT_d−B_d=0, R′T_d=1 Mb, and R′T_d−B_d=−1 Mb. For the change to R′=1.2 Mbps, we have R′T_d=300,000 bits, and R′T_d−B_d=−1.7 Mb.

[0048] These examples show that the buffer size employed should be a function of the data rate. Smaller buffers are required at low rates. This allows the video delay through the system to be held constant at all data rates.

[0049] It should be understood that the scope of protection of the following claims is not intended to be limited to the specific embodiment described above, except where the claims are expressly so limited. For example, the invention may be applied in non-digital television systems wherein data is sent from an encoder to a decoder via buffers and where it is important to maintain the decoder buffer occupancy within predetermined limits. Such applications will become apparent to those skilled in the art after reading this specification.