Frame sampling scheme for video scanning in a video-on-demand system

Description: TECHNICAL FIELD [Detailed description of the invention]

【0001】

[Industrial application field]

The present invention relates to support for searching and scanning video frames in a disk array based video server.

【0002】

[Conventional technology]

In a video-on-demand (hereinafter referred to as VOD) system, a multimedia stream (movie) is stored in a storage server and played back and output to an end user (receiver) station at the time of request. A multimedia stream consists of compressed video and audio. The leading standard for video is MPEG (Moving Picture Experts Group). Interframe compression techniques, such as those provided by MPEG, have considerable advantages in storage and transmission, and as a result are accepted worldwide for VOD applications.

【0003】

During normal playback output, data blocks belonging to the multimedia stream are retrieved from the storage system and transmitted to the receiving station. The receiving station decodes the incoming stream and plays it back. In general, VOD systems preferably provide users with video cassette deck-like search functions such as "fast forward" (also referred to as "forward scanning"). There are several conventional methods for implementing this fast-forward (hereinafter referred to as FF) function, some of which mimic the scanning behavior of analog video cassette decks and movie projectors. Is. However, each of these methods imposes additional resource requirements on the system, as explained below. Below, for the sake of simplicity, we assume that the movie must be scanned three times faster than the normal playback output.

【0004】

The multimedia stream is searched and transmitted at three times the normal playback output speed, and the terminal station filters the data and plays it back. This solution requires additional resources in the storage system, storage buffers and network (three times normal speed). Also, the terminal station needs additional resources to process incoming data.

【0005】

The storage system searches every three frames and transmits them to the terminal station. This solution requires a significant amount of additional system resources. In this case, the multimedia file needs to be indexed in order to retrieve individual frames, and the amount of data retrieved will be higher than usual due to the structure of the interframe coding.

【0006】

The system switches to a separately coded FF stream to provide scanning behavior. This solution does not require additional read or network bandwidth, but is extremely expensive in terms of storage costs.

【0007】

[Problems to be Solved by the Invention]

An object of the present invention is to support fast forward and rewind (scan) video frame retrieval in a disk array based video server.

【0008】

Another object of the present invention is to support variable speed scanning in a video server.

【0009】

To avoid the drawbacks mentioned earlier, the present invention allows the user to control the playback output speed of a movie and perform variable speed scanning or browsing without the need for additional discs or additional network bandwidth resources. Provide systems and methods.

【0010】

[Means for solving problems]

In a preferred embodiment, the method of the invention provides a variable speed scanning operation for an MPEG video stream. This method satisfies the constraints of the MPEG decoder (in the user's set-top box) and requires minimal additional system resources. Examples of the present invention include (a) storage method, (b1) segment sampling method, (b2) segment arrangement method and (c) reproduction output method, and (b1) and (b2) are segment selection methods. There are two alternatives for. Therefore, two solutions are provided to support variable speed scanning in disk array based video servers. That is, a method using (a), (b1) and (c) and a method using (a), (b2) and (c).

【0011】

MPEG video streams are composed of three types of frames: intra frames (intra-frame coded frames, hereinafter referred to as I frames), predictive frames (forward predictive coded frames, hereinafter referred to as P frames) and interpolated. It consists of frames (bidirectional predictive coding frames, hereinafter referred to as B frames). In this storage method, a stream of MPEG video frames is divided into medium segments. Each segment contains a series of frames that start with an I frame and end before another I frame. Allocation and retrieval of multimedia streams is done on a segment-by-segment basis. Consecutive segments are stored on different disks in the disk array.

【0012】

During normal playback output, one medium segment is retrieved from each disc in a disk array with, for example, n discs. These n segments are buffered and stored in memory and transmitted to the receiving station at a fixed speed. To maintain smooth operation during FF mode, n contiguous segments in the scan sequence reside on n different disks.

【0013】

A segment sampling method that selectively retrieves segments from a disk array in which the segments are arranged in a round-robin manner supports segment sampling for FF search at all FF speeds desired by the viewer. .. The segments sampled by this method are evenly distributed so that there is minimal variation in the number of segments skipped between all two consecutive searches.

【0014】

The segment placement method is an alternative to the segment sampling method for segment selection. Unlike the segment sampling method (used for disk array-based video servers where segments are arranged in a round-robin manner), the segment placement method eliminates the need for special preparation for sampling. Allocate the segments to disk wisely so that the segments can be sampled perfectly evenly in several predefined scan speed scan modes.

【0015】

In the playback output method, the receiving station is operated to play back and output the video stream searched for the scanning search. In this method, the incoming media stream is selectively analyzed and the presentation time stamp is adjusted to minimize the buffer space and transmission bandwidth required by the server and the terminal station. The other object, features and advantages of the present invention will become apparent by reading the following detailed description of the invention along with the accompanying drawings.

【0016】

[Example]

FIG. 1 is a diagram showing a disk array-based video server 100 in which video data is stored in a disk array 102 and transmitted to a terminal client station 103 via a network 104 on request. The movie (video) is stored in the disk array 102. The video server 100 includes a processor (CPU) 101 that performs tasks under the control of the cyclic scheduler 106. These tasks include a search task 150 that retrieves video from the disk array 102, a storage task 152 that temporarily stores the video in memory buffer 105, and a client station for video via network 104 over network interface 107. Includes transmission task 154 to be transmitted to 103.

【0017】

Each of the client stations 103 includes a network interface that provides bidirectional communication between the client station 103 and the video server over a communication network. Each of the client stations also includes a processor (CPU) 109 that receives video to the playback output buffer 110 via the client station network interface 108. Each client station 103 is controlled by the user via a decoder 111 that receives the movie from the playback output buffer and decodes the movie for operation on a client display device (such as a television set) and a remote controller 114. It also includes a control interface 112 that receives commands (including scanning speed control commands). These commands are communicated to the video server over the client station network interface 108 and network 104.

【0018】

The video server 100 can be implemented using a processor with sufficient performance for the number of video streams it intends to support. For example, a small-capacity video server can be implemented using the RISC System / 6000 TM system, and a large-capacity server can be implemented using the ES / 9000 TM system (both systems are Armonk, NY, USA). International Business Machines Available from Corporation). The disk array 102 can be of RAID level 5 type. The network 104 can be, for example, an optical fiber network or a normal bidirectional cable network. Client station 103 can be implemented as a set-top box. The remote controller 114 and the control logic mechanism can be coupled by a normal infrared interface. The client sends a command to the video server 100 over network 104. According to the embodiments of the present invention, the client can control the scanning speed of the video within a continuous width by pressing a specific button on the remote controller 114.

【0019】

For clarity, this description uses an example of fast-forwarding behavior. However, it should be understood that the principles described apply to the rewind (FB) operation as well.

【0020】

FIG. 2 shows one method of achieving FF search on a disk array-based video server using storage method 10, segment sampling method 15, and playback output method 20, according to an embodiment of the present invention. It is a figure. Storage method 10 divides the stream of MPEG video frames into media segments. Each segment contains a series of frames that start with an I frame and end before another I frame. Allocation and retrieval of multimedia streams is done on a segment-by-segment basis. In the segment sampling method 15, a segment is selectively searched from a disk array in which the segments are arranged in a round-robin manner, and a fast-forward (FF) search is performed at a fast-forward speed desired by the viewer. In the reproduction output method 20, the video stream searched by the fast-forward search is reproduced and output to the terminal station, and the same buffer space and transmission bandwidth requirements as in the normal reproduction operation are maintained.

【0021】

FIG. 3 is another for achieving FF search on a disk array-based video server using storage method 10, segment placement method 35, and playback output method 20, according to another embodiment of the present invention. It is a figure which shows one method. The storage method 10 and the reproduction output method 20 are the same as those used for the method of FIG. Segment placement method 35 wisely allocates segments to disk so that the segments can be sampled perfectly uniformly in FF mode for some given FF speed.

【0022】

The various tasks and programs used to control the scan are described below with reference to FIGS. 4-10.

【0023】

FIG. 4 is a diagram showing a sequence of MPEG video frames 1 to 8 consisting of an I frame, a P frame, and a B frame. The storage order of the frames is different from the temporal order and reflects the order in which the frames must be supplied to the decoder. In an MPEG stream, the P frame depends on the I frame, and the B frame depends on both the I frame and the P frame. Therefore, it is impossible to reproduce and output the B frame without the corresponding I frame and P frame. Therefore, a subset of every three frames should contain a corresponding anchor I frame or a B frame without an anchor P frame, so playing every three frames achieves 3x playback output. That is impossible.

【0024】

For the reasons described above, the storage method of the present invention divides the MPEG video stream into media segments. Each segment contains a series of frames that start with an I frame and end before another I frame. Allocation and retrieval of multimedia streams is done on a segment-by-segment basis. Consecutive segments are stored on different disks in the disk array 102.

【0025】

The segment sampling method of the search task 150 will be described below. Consider the type of disk array-based video server shown in Figure 1, which is n disks. To maximize throughput during normal (standard playback speed) operation, video segments s0-s29 are stored in disk array 102 in a round-robin manner, resulting in n contiguous segments. You will be able to search in one round. Formally, when there are n disks, the segment g is stored on disk k = f1 (g, n) and f1 (g, n) = g mod n. Figure 5 shows an example of round robin segment placement when n = 10.

【0026】

In order to achieve the FF function, only some segments must be sampled appropriately and other segments must be skipped. The sampling rate depends on the desired FF rate. If the FF speed is m times the normal speed, one segment will be sampled from the m segment on average. For example, if the FF velocity m is equal to 3, in Figure 5, the segments s0, s3, s6 and s9 are retrieved from disk 0, disk 3, disk 6 and disk 9, respectively, and the segments s1, s2, s4, s5, respectively. s7 and s8 are skipped. The complete sampling procedure will be described in detail later with reference to segment sampling methods.

【0027】

In order to provide the best output during FF, the sampled segments must be distributed as evenly as possible. For example, to double the speed, you only need to select even segments while skipping odd segments. However, although this method samples the segments uniformly, it can prove that the maximum throughput cannot be obtained when there are an even number of disks in the array (for example, the situation of n = 10 in Fig. 5). .. Specifically, if you select only even segments, only half of the discs (ie, even numbered discs) will participate in the segment search and the other half discs (ie odd numbered discs) will be idle. Will remain. As a result, in order to develop an FF video segment search method on a disk array in which segments are stored in a round-robin manner, not only the segments are sampled as uniformly as possible, but also the maximum throughput is achieved. You also need to guarantee that. Such a procedure will be described below.

【0028】

FIG. 6 is a flow diagram of the program of the search task 150 for determining which video segment to search in FF mode for each disk. Assume that the number of disks in the array is n and the desired FF speed is m times normal operation. lcm (n, m) shall be the least common multiple of m and n. For example, lcm (3,9) = 9. To simplify the notation, it is assumed that z = nm / lcm (n, m). To simplify the explanation, Fig. 7 shows the FF segment search when n = 9 and m = 3. In Figure 7, the searched segments are marked with *.

【0029】

Now referring to FIG. 6, the round number r of the segment search is equal to 1 at the start (step 60). For each disk, use the appropriate formula to determine which segments to search for, depending on whether r is odd or even (step 70). If r is odd, it corresponds to the first half of the zigzag curve resulting from the segment being searched, such as the line formed by the segments 0 *, 10 * and 20 * in the first round of Figure 7. On the other hand, if r is even, it corresponds to the second half of the zigzag curve, such as the line formed by the segments 29 *, 37 * and 45 * in the second round of Figure 7. Specifically, if r is odd, the segment g is retrieved from disk k, which g is uniquely determined by steps 80 and 85. If r is even, the segment g is retrieved from disk k, which g is uniquely determined by steps 90 and 95. In step 100, if the video segment is still needed after the segment g has been retrieved from the disk k search (step 105), proceed to step 110 and increment the round number r by one. If not, this procedure ends at step 120.

【0030】

Seeing Figure 7 again, an example is shown for n = 9 and m = 3, and the segments searched are marked with *. Rather than searching for segments with numbers that are multiples of 3 (disks 1, 2, 4, 5, 7 and 8 should be idle), the segment sampling scheme shown in Figure 6 is partly Shift the video segments found in the search. For example, segment 10 is fetched in place of segment 9 and segment 20 is fetched in place of segment 19. Such a shift does not ensure that the segments retrieved are perfectly evenly distributed, but that maximum throughput is achieved. The group of segments searched in the first round of the search in Figure 7 consists of segments 0, 10, 20, 3, 13, 23, 6, 16, and 26, which are then 0, 3, 6, 10. It is displayed in the order of #, 13, 16, 20 #, 23, 26 (# represents the shift of the searched segment number). Under this scheme, the segments searched in the second round of the search in Figure 7 are segments 45, 37, 29, 48, 40, 32, 51, 43 and 35, which are then 29, 32, It is displayed in the order of 35, 37 #, 40, 43, 45 #, 48, 51. From FIG. 7, it can be seen that the searched segments form a zigzag curve. The number of zigzag shifts is 2 nm / lcm (n, m) -2, which means that maximum throughput can be achieved with disk array-based video servers where segments are stored in a round-robin fashion. It is the smallest among all possible FF methods.

【0031】

The segment placement method will be described below. As can be seen from FIGS. 2 and 3, the segment placement method is an alternative to the segment sampling method described earlier. Unlike the segment sampling method (selectively searching for segments from a disk array in which the segments are stored in a round-robin manner), the segment placement method does not require any special preparation for sampling, and some Allocate the segments to disk wisely so that the segments can be sampled perfectly uniformly in FF mode with respect to the predefined FF speeds of. Consider FF operation, where the playback output speed is m times the normal playback output speed. In this FF mode, the sequence of segments retrieved from a given start segment i is {i, i + m, i + 2m, i + 3m, ...}. Since n media segments are searched in each round, the searched segments are {(r-1) nm, (r-1) nm + m, (r-1), where r is the segment search round number. ) nm + 2m, ..., (r-1) nm + (n-1) m}. You need to ensure that these segments are mapped to different disks for maximum throughput. The segment placement function f2 (g, n) defines the mapping from the medium segment g to the disk k. Where k is a number in the range 0 to n-1 in a disk array with n disks.

【0032】

Assuming m is a partial multiple of the number of disks n, the mapping function can be defined as f2 (g, n) = (g + [g / n]) mod n. The first term (g) represents the regular scattering of segments on n disks, and the second term (g / n) represents the skew coefficient. By f2 (g, n), for any r segment {(r-1) nm, (r-1) nm + m, (r-1) nm + 2m, ..., (r-1) nm + It can be seen that (n-1) m} is mapped to different disks.

【0033】

Here, referring to FIG. 8 (flow diagram of the segment placement program in the search task 150), the number of rounds r of the segment search is equal to 1 at the start (step 200). In the r-round, disk k locates the i-th disk to be searched (ie, segment number g). Here, the numbers i and g are uniquely determined in steps 210 and 220, respectively. If, after searching for segment g from disk k in step 230, the video segment is still needed (step 240), proceed to step 250 and increase the number of rounds r by one. If not, this procedure ends at step 260.

【0034】

With reference to FIG. 9, the placement of the video segment in a disk array with 6 disks is shown when the required FF speed is 3 times normal operation. This placement of the media segment across n discs ensures a smooth search for playback output at different FF speeds when the FF speed m is a partial multiple of the number of discs n. This arrangement ensures that all of the media segments that must be searched for in one round are on different disks, and as a result, the load imposed on the storage system by the FF mode search process is the load under normal operation. Becomes the same as.

【0035】

The reproduction output method will be described below. During normal speed playback output, video data is retrieved from the disc on a round-by-round basis. In each round, one medium segment is searched for each disk in the disk array. This data is temporarily buffered in the server and transmitted to the terminal station at a fixed speed. In FF mode, the server searches for a segment based on either the procedure in Figure 2 or the procedure in Figure 3. With reference to FIG. 10, the processing steps of the receiving station responsible for parsing the incoming stream and creating a valid input stream for the decoder are shown. Client station 103 receives an incoming segment stream from video server 100 in step 300 and discards intermediate frames that do not have associated anchor frames in step 310. Note that the media segment starts with an I frame, but the media segment contains a B frame with an anchor frame outside that segment. These B-frames are placed immediately after the I-frame, as can be seen in Figure 4, but are ignored because they depend on the last P-frame of the previous media segment that is not searched. At step 320, the receiving station adjusts the presentation timestamp embedded in the stream. The presentation time stamp determines when the video frame is displayed. The presentation timestamp must be adjusted to reflect the correct playback output time to compensate for skipped segments and ignored B-frames. Then, in step 330, the video frame is played back and output.

【0036】

This reproduction output policy results in a piecewise continuous reproduction output sequence. This allows viewers to explore scenes to quickly find the scene they are interested in. The segment size is fixed, so no additional buffer or transmission bandwidth for the stream is needed. The segment maintains the average data rate of the stream so that the decoder at the end station can accept it.

【0037】

Having described the present invention by preferred embodiments, one of ordinary skill in the art will assume various modifications and improvements. Therefore, it should be understood that this preferred embodiment is presented as an example and not as a limitation. The scope of the present invention is defined by the claims.

【0038】

【0039】

[0040) [Effect of the invention]

As described above, the present invention provides a system and method capable of performing variable speed scanning and browsing in a disk array based video server without the need for additional disks or additional network bandwidth resources. ..

[Simple explanation of drawings]

[Figure 1]

FIG. 5 shows a disk array-based multimedia video server in a network.

[Figure 2]

It is a block diagram of the procedure of the fast-forward search using the segment sampling method.

[Fig. 3]

It is a block diagram of the procedure of the fast forward search using the segment arrangement method.

[Fig. 4]

It is a figure which shows the sequence of the MPEG frame.

[Fig. 5]

FIG. 5 shows a disk array in which video segments are stored in a round robin fashion.

[Fig. 6]

It is a detailed flow chart of the program of the segment sampling method.

[Fig. 7]

It is a figure which shows the example of the segment sampling method.

[Fig. 8]

It is a detailed flow chart of the program of the segment arrangement method.

[Fig. 9]

It is a figure which shows the example of the segment arrangement method.

[Fig. 10]

It is a block diagram of a reproduction output procedure.

[Explanation of symbols]

10 Memory method 15 segment sampling method 20 Playback output method 35 Segment placement method 100 video server 101 processor (CPU) 102 disk array 103 Client Station 104 network 105 memory buffer 106 Cyclic Scheduler 107 Network interface 108 Client Station Network Interface 109 processor (CPU) 110 Playout output buffer 111 Decoder 112 Control interface 114 remote controller 150 search task 152 Memory task 154 Transmission task