Data reduction of video streams by selection of frames and partial deletion of transform coefficients

0001This invention relates to a method and apparatus for generating from a first data stream a second data stream with reduced data rate. In particular, the invention relates to encoding video data for trick mode with reduced data rate.

0002Different home network architectures have been developed or are still under development to enable every user a full access to his audio-visual (AV) content available on his home network. Home Audio/Video (HAVi) on IEEE1394 networks or Universal-Plug-And-Play (UpnP) on Internet Protocol (IP) networks are very popular examples.

0003The playback of AV content always requires a connection between a server device and a decoding and presenting renderer device, which are connected to each other, e.g. via a home network. Fig.1 shows a video file server VS and a video renderer VR connected through a network NW. The renderer VR in turn is connected to a video display VD, e.g. in a TV set. The video display VD however could be a separate device that is connected via the network NW. Specific problems arise when trick modes are requested for playback, e.g. if fast forward trick mode shall be viewed on a display VD and the data are coming from a server VS being e.g. a hard-disk drive (HDD) based recorder or a DVD player, and the connection NW between them is bandwidth limited.

0004A simple solution for the fast forward trick mode is the transfer of the data stream by a much higher bitrate to the renderer device, and letting the renderer device downsample the time scale. This solution, however, results in a much higher network load. If e.g. a 12x fast forward mode is requested, meaning that only every 12^th frame is rendered and displayed, then the data rate is increased from e.g. 5 Mbit/sec to 60 Mbit/sec for a video stream. This may overload bandwidth capacity of the home networks, because even when the requested high bitrate is available and can be handled in theory, it may result in the disturbance of other simultaneously running data transfers within the network by data leakage or delays. Further, if the network contains wireless links, these links typically have very limited bandwidth available, so that a fast forward trick mode video data stream may not pass.

0005Another possible solution is to do the downsampling of the time scale on the server side. E.g. in the case of MPEG, a video format being standardized in ISO/IEC 13818-2, this can be done by subsampling data for only the I-frames since they are intracoded, i.e. can be decoded independently from other frames. But as shown in the following, also this solution results in a disadvantageously high bitrate.

0006The problem to be solved by the present invention is to describe a video trick mode with a bitrate that may be close or equal to the original bitrate of the stream as it is without trick mode.

0007Within this disclosure, additional processes are unveiled to adopt the data stream, thus providing an advanced type of fast forward trick mode with a bitrate that may be close or equal to the original bitrate of the stream without trick mode. In principle, the inventive method is also suitable for generating a video trick mode data stream with a bitrate even below the bitrate of the original data stream, but in most applications this is not required.

0008To substantially keep the original bitrate of an MPEG encoded video data stream during a video trick mode application, the inventive method contains different processing steps, as described in the following.

0009In a first processing step, the original data stream is temporally subsampled, thus reducing the number and size of the frames to transmit by selecting only specific frames. In a second processing step, repartitioning the discrete frame data can further reduce the bitrate. In particular, the second processing step comprises reduction of the number of DCT coefficients to be transmitted, and their re-encoding if required.

0010These processing steps are executed on the video server side and lead to an encoded trick mode video data stream that can be transmitted e.g. over the network. It is particularly advantageous that the format of this trick mode video data stream strictly complies with the MPEG standard, i.e. it can be decoded like any other MPEG video data stream. E.g. the order of utilized DCT coefficients remains unchanged. Thus, no special decoder is required. As a further advantage, the trick mode video data stream can be generated on the fly, i.e. it can be decoded and viewed while it is generated, and therefore needs no intermediate storage. The reduction rate can also be modified on the fly, as shown below, and therefore it is possible e.g. to adopt the reduction rate to the currently available bandwidth capacity.

0011To reduce the bitrate during trick modes, a repartitioning of the data stream is performed at the server side by sending only selected frames, e.g. selected I-frames and/or P-frames. P-frames are frames that can be predicted from I-frames, using e.g. motion compensation. But as already mentioned, this repartitioning will not be sufficient. The general idea of the invention is to reduce the bitrate by applying additional processing steps to the transmitted discrete frames. These processing steps further reduce the bit amount of every individual frame by cutting off specific, usually higher order DCT coefficients of macro blocks. Therefore, the additional processing steps applied to the discrete frames reduce also the video picture quality, but still the reduced video picture quality is absolutely acceptable for the user, since due to the reduced human viewing sensibility against picture artifacts during fast forward or fast backward, known as rapid movement masking effect, the cutting off of higher DCT coefficients in a frame lowers bitrate by acceptable picture quality.

0012Advantageous embodiments of the invention are disclosed in the dependent claims, the following description and the figures, which show in <ul id="ul0001" list-style="none" compact="compact"><li>Fig.1 a video data server and a rendering device, connected by a network;</li><li>Fig.2 the structure of a group of pictures (GOP) according to the MPEG standard;</li><li>Fig.3 a reduced MPEG coded group of pictures containing only I- and P-frames;</li><li>Fig.4 a reduced MPEG coded group of pictures containing only I-frames;</li><li>Fig.5 a sequence of I-frames;</li><li>Fig.6 a sequence of every 2^nd I-frames;</li><li>Fig.7 the position of DCT coefficients in an 8x8 macro block according to MPEG-2;</li><li>Fig.8 the zigzag scanning scheme used for sequential transmission of DCT coefficients;</li><li>Fig.9 an exemplary matrix of DCT coefficients and their sequential arrangement;</li><li>Fig.10a a first example for selecting run-length coded DCT coefficients;</li><li>Fig.10b the resulting sequence of DCT coefficients;</li><li>Fig.11a a second example for selecting run-length coded DCT coefficients from a matrix;</li><li>Fig.11b a second example for selecting run-length coded DCT coefficients in sequential order;</li><li>Fig.11c the resulting sequence of DCT coefficients;</li><li>Fig.11d the resulting sequence of DCT coefficients after re-encoding;</li><li>Fig.12a a third example for selecting run-length coded DCT coefficients in sequential order; and</li><li>Fig.12b the resulting sequence of DCT coefficients.</li></ul>

0013In the following, the methods for reducing the data rate are described for MPEG-2 video streams. Similar methods can be applied to similar coding methods. An MPEG-2 video stream consists of I-frames, P-frames and B-frames. While I-frames are intracoded, i.e. can be independently decoded, P-frames are predicted only from preceding I-frames and B-frames are interpolated from preceding and subsequent I-and P-frames, using e.g. motion compensation.

0014One I-frame and several P-frames and B-frames are grouped together to a "Group Of Pictures" (GOP). These GOPs are parameterized by a pair of (M,N) values. While N represents the count of frames in every GOP, M is the number of frames between two anchor frames. Anchor frames are I-frames and P-frames only, so that each M-th frame is an I-frame or a P-frame. Typical parameters used are (N,M) = (12,3). In that case the coding sequence of frames in a GOP is IBBPBBPBBPBB , which corresponds to the displayed sequence of frames shown in Fig.2. Within the 12 frames of the GOP, always after two B-frames comes an I-frame or P-frame, so that every 3^rd frame is an anchor frame.

0015Coding I-, P- and B-frames requires different amounts of data. Let "i" represent the mean value of the amount of data needed for the MPEG encoded I-frame, let "p" represent the mean value of the amount of data needed for the MPEG encoded P-frame, and "b" represent the mean value of the amount of data needed for the MPEG encoded B-frame. Then the relation between the mean values of "i", "p" and "b" can be expressed by the following equations, explaining "p" and "b" as a fraction of "i":<maths id="math0001" num=""><img file="EP1553779A1_D0001.tif" /></maths>

0016Typical values are α=0.4 and β=0.2. So the mean amount of data per frame for a standard MPEG-2 sequence, played back with normal speed or "1x", can be calculated as:<maths id="math0002" num=""><img file="EP1553779A1_D0002.tif" /></maths>

0017And with the typical values N=12, M=3, α=0.4 and β=0.2:<maths id="math0003" num=""><img file="EP1553779A1_D0003.tif" /></maths>

0018If a trick mode is chosen where all B-frames are discarded and only the anchor frames, i.e. the I- and P-frames, are transmitted as shown in Fig.3, the rate can be calculated as:<maths id="math0004" num=""><img file="EP1553779A1_D0004.tif" /></maths>

0019And with the typical values:<maths id="math0005" num=""><img file="EP1553779A1_D0005.tif" /></maths>

0020This shows that a bitrate is nearly doubled for that case.

0021If an 'I-frame only' trick mode is chosen with an n-fold speed (nx, with n ≤ N), the bitrate will increase even more. For 'I-frame only' trick mode, n different I-frames are transmitted during a GOP time period. These are displayed by repeating the I-frames N/n times by preserving the N frames of a GOP and providing equidistant picture subsampling in time for the viewer.

0022Two examples for N=12 follow. First, in the case of 2x 'I-frame only' trick mode, there are n=2 I-frames from different GOPs transmitted to the renderer, which are then displayed for N/n=6 frame periods each, making a total of N=12 frame periods. Second, in the case of 3x 'I-frame only' trick mode, there are n=3 I-frames from different GOPs transmitted to the renderer, which are then displayed for N/n=4 frame periods.

0023The mean amount of data for the 'I-frame only' trick mode is calculated by:<maths id="math0006" num=""><img file="EP1553779A1_D0006.tif" /></maths>

0024For 6x and for 10x fast forward the typical values are:<maths id="math0007" num=""><img file="EP1553779A1_D0007.tif" /></maths><maths id="math0008" num=""><img file="EP1553779A1_D0008.tif" /></maths>

0025The 6x case is shown in Fig.4. Six I-frames, belonging to six GOPs n,...,n+5 are displayed during the time of a single GOP t_GOP. Generally, for n &lt; N the transmitted I-frames are repeated and displayed N/n times each.

0026If a speed is chosen with n = N, as shown in Fig.5, the maximum bitrate is reached, because n I-frames are rendered within the time for N frames, i.e. every frame is displayed for the normal frame display time duration. It cannot be displayed for a shorter duration. Therefore, for n ≥ N, the number of I-frames transmitted keeps constant, while only the GOPs where the I-frames are selected from are varied.

0027This is depicted in Fig.6 for n=24, N=12 and 24x 'I-frame only' trick mode. Only the I-frame of every 2^nd GOP n,n+2,...,n+22 out of 24 GOPs is selected for transmission. Nevertheless, in all cases n > N the bitrate always is<maths id="math0009" num=""><img file="EP1553779A1_D0009.tif" /></maths> which is more than 3 times higher than during standard playback (1x) for (N,M)=(12,3), see Eq.3.

0028One solution for reducing the data rate is to introduce pauses during the transmission, by skipping frames, thus reducing temporal resolution. So e.g. for a 12x fast forward speed there could be used the first I-frame of every 2^nd GOP and be displayed twice, instead of using the first I-frame of every GOP from the original stream. In that case the bitrate would be reduced by one half, as compared to transmitting the I-frames of all GOPs. But this solution has large sampling time distances, i.e. the subsampling in time shows only one frame out of a time of one second of pictures, corresponding to two GOPs, from the original sequence. It will be very difficult for a viewer to recognize anything from the pictures.

0029All the mentioned processing methods for providing trick modes are based on processing a full standard MPEG video data stream. They do not have a large impact to the stream preparation before the data stream is transmitted to a decoder, e.g. via a home network. The processing steps to be executed for the subsampling of frames in time comprise parsing MPEG start codes not deeper than to the picture layer. When detecting a picture header of the adequate picture type, which is I- or P-frame, the picture is extracted and transmitted by re-stamping its presentation time stamps (PTS) within the MPEG system layer accordingly.

0030As seen above, the reduction of the bitrate for trick modes can be achieved by expanding the sampling time periods, so that there are less I-frames transferred, which are then displayed by the renderer for a longer time, namely until the next I-frame is received. This method however results in a degradation of picture quality concerning its resolution in time.

0031This invention aims at a further advantageous reduction of the bitrate, without necessarily expanding the sampling time period. According to the invention, this is achieved by further advanced processing steps that manipulate video stream layers deeper than the picture layer. By reducing the amount of bits needed for a single I-frame, it becomes possible to transfer more I-frames without going beyond the scope of network capacity, and thus reaching a higher resolution in time for the trick modes. Particularly, it is even possible to adjust the transmitted datarate to currently available circumstances, e.g. transmission capabilities.

0032For the inventive advanced processing method applicable e.g. for trick modes, the available MPEG stream is parsed till reaching the macro block layer. This needs not to be done for all frames, but only for those frames that are subsequently being transferred, e.g. every 2^nd I-frame.

0033According to the mentioned MPEG video standard, a macro block consists of single sub-blocks with 8 by 8 pixels each, describing luminance or chrominance information. These sub-blocks of the time domain are transformed by a Discrete Cosine Transform (DCT) into 64 DCT coefficients in the frequency domain, which are usually also depicted as a matrix of 8 by 8 values. Such sub-block, or DCT coefficient matrix respectively, is depicted in Fig.7. Each cross represents a DCT coefficient C. For entropy encoding after quantization, the coefficients within the sub-blocks are zigzag scanned, as depicted in Fig.8, wherein coefficients that are zero are skipped, and the number of skipped coefficients, which is also called run-length, is combined with the following value and encoded together by a variable length coding (VLC). A VLC code word contains a DCT coefficient value and the number of positions in the matrix that are skipped when executing the zigzag scan. In known systems these coefficients are skipped because their respective coefficients are zero.

0034Fig.9a shows an exemplary sub-block SB with coefficients, wherein some coefficients are zero and some are non-zero. Fig.9b shows, in slightly different notation, the corresponding sequence SEQ of non-zero coefficients that results when the zigzag scan shown in Fig.8 is executed on the sub-block SB. The run-length RL, i.e. the number of skipped coefficients, is then coded into each VLC coded value, as defined by the above-mentioned MPEG standard.

0035The inventive advanced processing steps are executed on the quantized and zigzag scanned sub-block information. The zigzag-scanning scheme is kept in order to enable standard MPEG decoding. The invention is based on the idea to cut off some part of the quantized DCT coefficients. This can be done by different criteria, leading to different optimization methods. The result is always data reduction within the single frames.

0036In one embodiment of the invention, a first optimization method is utilized, as shown in Fig.10a and Fig.10b. It is based on ignoring, i.e. cutting off, all quantized DCT coefficients after having parsed a defined number of VLC code words. After e.g. 4 VLC code words an end-of-block (EOB) flag is inserted, as shown in Fig.10b, and the rest of the coefficients IGN of the current sub-block is skipped. These e.g. 4 VLC code words correspond to the first 4 non-zero coefficients according to the zigzag scan described above. Then the next sub-block is processed. As mentioned above, the result of this processing is a standard MPEG coded sub-block with reduced number of coefficients, and therefore reduced amount of data. It is possible to decode the sub-block again using standard MPEG procedures, though the resulting block of pixels has reduced spatial resolution. During fast forward trick mode, however, a user cannot recognize this. It is characteristic for this optimization method that the spatial resolution of the resulting sub-blocks, and therefore the pictures, is variable, while the data rate is almost constant for a given number of transmitted coefficients. As further mentioned above, the number of used VLC code words can be determined for every sub-block independently, and further for luminance and chrominance independently, thus individually changing the spatial resolution of subsequently transmitted sub-blocks and simultaneously changing the data rate, e.g. according to current bandwidth requirements or capabilities.

0037In another embodiment of the invention, a second optimization method is utilized, as shown in Fig.11 a-d. It is based on cutting off all quantized DCT coefficients after having reached a defined vertical and/or horizontal resolution in the frequency pattern. Vertical resolution is given by the row number of a coefficient within the matrix, and horizontal resolution is given by the column number of a coefficient within the matrix. The minimum resolution corresponds to the upper left coefficient, which represents the DC value of the luminance or chrominance of the sub-block. This optimization method can be understood such that the first k positions C_T of the sub-block SB, according to the zigzag scheme, are scanned through. As usual for MPEG, only the non-zero coefficients are transmitted. The other positions C_ICN of the sub-block SB are ignored. Therefore the number of transmitted coefficients per sub-block may vary, depending on the coefficients being zero or not.

0038In Fig.11a a range of nine coefficients C_T is defined within a sub-block that are scanned through according to the zigzag scheme, while the other coefficients C_ICN are ignored. This can be noted as a run-length pattern "1-2-3-4-5-6-7-8-9". Fig.11b shows the resulting sequence for three exemplary sub-blocks with different distributions of zero coefficients. For the first example, 6 out of the first 9 coefficients are non-zero. For the second example, 5 out of the first 9 coefficients are non-zero. For the third example, 4 out of the first 9 coefficients are non-zero. The respective sequences of coefficients used for VLC coding and transmission are shown in Fig.11c.

0039This coding method results in a picture with a limited spatial resolution, but a more variable data rate. A viewer will perceive the limited spatial resolution as a constant spatial resolution within a frame.

0040In a similar embodiment, a pattern of coefficients to be scanned is defined, so that not the common zigzag-scanning scheme is employed, but certain positions are excluded. E.g. the normal zigzag-scanning scheme can be employed with one position C_EX being ignored. Also more than one position can be excluded. Thus, also specified non-zero DCT coefficients can be skipped. In this case, the inventive method comprises re-encoding the run-length for the next value, as described below. The coefficients C_EX to be skipped can be specified by their position, e.g. "column 3, line 2", or they can be specified by their value, e.g. "ignore all coefficients with values below 5% of their possible maximum value", or they can be specified by a combination of both, e.g. "ignore among the first 12 coefficients of the zig-zag scan the 8^th and 9^th coefficient and all those coefficients which have a value of 10 or below".

0041Since this embodiment comprises skipping of coefficients, it requires re-encoding of the next non-zero coefficient. An example that corresponds to the third example from Fig.11c is shown in Fig.11d. It is assumed that the above-described range C_T of coefficients, as shown in Fig.11a, is scanned using the standard zigzag-scanning scheme, and that one position C_EX is excluded. Then this position is set to zero, and therefore the next following non-zero coefficient C_NXT has another number of leading zero coefficients. It must therefore be differently VLC coded. In the example shown in Fig.11d, the run-length to be encoded is 5 instead of 4. In an analogous manner it is easy to skip more than one coefficient.

0042In yet another embodiment of the invention, a third optimization method is utilized, as shown in Fig.12a-b. It is based on cutting off all quantized DCT coefficients after, or immediately before, having reached a defined amount of bits per sub-block. When cutting off straight before having reached a defined amount of bits per sub-block, it is possible to define a strict limit to the amount of data, but the required processing is slightly more complicated. This optimization method actually results in limiting the number of bits to a certain range, and thus comprises the limiting to a maximum value, since VLC coded coefficients have a maximum number of bits. The number of bits per coefficient depends on its amplitude value and the run-length value, i.e. the number of preceding zero coefficients. Therefore, the number of transmitted coefficients depends on both the number of non-zero coefficients and the number of skipped zero coefficients.

0043For all embodiments of the present invention, the bit amount can be defined separately for luminance and chrominance. Typically, a higher amount is chosen for the luminance sub-blocks because human visual perception is less sensitive for color artifacts within rapid motions.

0044Further, it is also possible to combine the above-described skipping of one or more coefficients and re-encoding, with respect to run-length, the next used coefficient with any of the optimization methods described above.

0045Advantageously, with the inventive method the datarate during trick modes remains nearly constant, as cpmpared to normal video data rate. This is particularly useful if the connection between a server and a renderer contains links with strictly limited bandwidth, e.g. wireless links.

0046The described method for generating a fast forward video trick mode can analogously be utilized for generating data streams for any video trick mode with reduced temporal and/or spatial resolution, e.g. fast backward.

0047The invention can be used in any type of devices that read a standard video data stream and generate a trick mode video data stream, e.g. digital video recorders, so-called personal video recorders (PVR), laser disc players for video applications such as DVD players, video encoding units for video-on-demand (VOD) or the like.