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

Frame sampling design for video scanning in the program subscription (VOD) system

<u style="single">I. Background of the invention</u>

The present invention discloses the support of video frame retrieval and scanning in a disk array video server.

In a program subscription (hereinafter referred to as VOD) system, multimedia streams (movies) are stored on a storage server, and upon request, they are played to a final user (received) stand. The multimedia stream consists of compressed video and audio. The main standard used for video is MPEG (moving image compression technology). Inter-frame compression techniques, such as MPEG, provide excellent advantages in data storage and transmission. Therefore, they can be widely used in VOD applications.

During normal playback, the data block belonging to the multimedia stream is retrieved from the storage system, and the data block is transmitted to the receiving station. The receiving station decodes the input stream and plays it. Generally, it is best to provide users with a search function (also called "forward scanning") similar to a video recorder (VCR) such as "fast forward" in a VOD system. There are several conventional methods for implementing this "Fast Forward" (hereinafter referred to as FF) function, some of which simulate the scanning function of an analog VCR or movie player. However, these methods each force the system to increase additional resource requirements. For the convenience of explanation, as described below, it is assumed that the movie must be scanned at 3 times the normal playback rate.

The multimedia stream is retrieved and transmitted at 3 times the normal playback rate, and the terminal filters and plays the data. This solution requires additional resources (3 times the normal rate) in storage systems, memory buffers, and networks. It also requires additional resources to process the input data at the terminal.

The storage system retrieves and transmits every third frame to the terminal. This solution requires a significant amount of additional system resources. Multimedia files must now be indexed to retrieve individual frames, and because of the inter-frame coding structure, the amount of retrieved data is higher than the normal amount.

The system switches to separate encoded FF streams to provide scanning jobs. Although this solution eliminates any additional reading bandwidth or network bandwidth, it is extremely expensive due to storage costs.

The purpose of the present invention is to support fast forward and fast reverse (scanning) video frame retrieval of a disk array video server.

A further object of the present invention is to support variable speed scanning of a video server.

In order to avoid the above-mentioned disadvantages, the present invention provides a system and method for implementing variable-speed scanning or viewing, in which the user controls the movie playback speed without additional disk or network bandwidth resources.

In a preferred embodiment, the method provides variable speed scanning operations for MPEG video streams. This method satisfies the constraints of the MPEG decoder (in the user's set-top box), and requires minimal additional system resources. The embodiments of the present invention include (a) a storage method, (b1) a section sampling method, (b2) a section placement method, and (c) a playback method, where (b1) and (b2) are used for section Two alternatives for segment selection. Therefore, two sets of solutions are provided to support variable speed scanning of disk array video servers: one set uses (a), (b1) and (c), and the other uses (a), (b2) and ( c).

The MPEG video stream is composed of three types of frames: intra frames (I), predictive frames (P) and interpolation frames (B). The storage method distinguishes the MPEG video frame data stream into the media section. Each section includes a continuous frame that starts with one I frame and ends before another I frame. The distribution and retrieval of multimedia data streams are based on segments. The consecutive segments are stored on different disks in the disk array.

During normal playback, a media segment is retrieved from each disk in a disk array having, for example, n disks. These n segments are buffered in memory and transmitted to the receiving station at a fixed rate. In order to maintain smooth operation during the FF mode, n consecutive sections forming a scan sequence are placed on n different disks.

The section sampling method is to selectively retrieve sections from a disk array in which sections are arranged in a round-robin manner. This method supports FF retrieval at any FF rate expected by the viewer Segment sampling. The sampled sections of this method are evenly distributed in the number of sections between every two consecutive retrievals with the smallest change.

The section placement method is an alternative to the section sampling method for section selection. In contrast to the section sampling method (which is used in disk array video servers where sections are arranged in a ring method), the section placement method wisely allocates sections to disks so that the sampling does not require special regulations and some predetermined scanning speeds The section can be sampled completely uniformly in the scanning mode.

The playing method makes the receiving station work to play the retrieved video stream for scanning and retrieval. This method selectively analyzes the input media stream and adjusts the appearance timestamp, thereby reducing the buffer space and transmission frequency bandwidth required by the server and the terminal. These and other objects, features, and advantages of the present invention will become apparent in the following detailed description in conjunction with the accompanying drawings.

Figure 1 shows a disk array multimedia video server on the network; Figure 2 shows a block diagram of the fast forward retrieval procedure using the section sampling method; Figure 3 shows the fast forward retrieval procedure using the section placement method Block diagram; Fig. 4 shows a sequence of MPEG frames; Fig. 5 shows a disk array storing video segments in a circular manner; Fig. 6 shows a detailed flowchart of a section sampling method program; Fig. 7 shows one of the section sampling methods Example; Figure 8 shows a detailed flowchart of the section arrangement method program; Figure 9 shows an example of the section arrangement method; and Figure 10 shows a block diagram of the playback program.

FIG. 1 shows a disk array video server 100, in which video data is stored in the disk array 102, and upon request, is transmitted to the station 103 of the end customer via the network 104. Movies (videos, etc.) are stored on the magnetic disk 102. The video server 100 includes a processor (cpu) 101 which executes tasks under the control of a loop scheduler 106. These tasks include: a retrieval task 150, which retrieves videos from the disk 102, etc.; a storage task 152, which temporarily stores videos, etc. in the buffer memory 105; and a transmission task 154, which passes through a network interface 107 transmits video to the client station 107 via the communication network 104.

Each of the client stations 103 includes a network interface, which provides two-way communication between the client station 103 and the video server via the communication network. The client stations also each include a processor (cpu) 109. The cpu receives video and the like via a client station network interface 108 and stores them in the playback buffer 110. Each clients station 103 also includes a decoder 111, which receives the movie in the play buffer and decodes it and plays it on the clients display device (such as a TV); and a control interface 112 through which The remote control 114 receives user control commands (including scanning speed control commands). These commands are sent to the video server via the network interface 108 and the network 104.

The video server 100 can be implemented using a processor with sufficient performance for the number of video streams. 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 (the two systems are Armenk, New York, USA) International Affairs Machine Co., Ltd. Company (manufactured and sold by International Business Machines Corporation). The disk array 102 may be a RAID LEVEL5 type. For example, the communication network can be an optical fiber network or a conventional two-way cable network. The client station 103 can be implemented by a set-top box. The remote control 114 and the control logic device can be conventionally coupled with an infrared interface. The client sends commands to the server 103 via the network 104. According to an embodiment of the present invention, the customer can press a specific button on the remote control 114 to control the scanning speed of the video (along a continuous frequency spectrum).

For the sake of clarity, this description will use the implementation of fast forward operations. However, of course the principles described are also applicable to fast reverse (FB) operations.

FIG. 2 shows a scheme for obtaining FF retrieval of a disk array video server by using a storage method 10, a section sampling method 15 and a playback method 20 according to an embodiment of the present invention. The storage method 10 distinguishes the MPEG video frame stream into a media segment. Each section includes consecutive frames starting with one I frame and ending before another I frame. The distribution and retrieval of the multimedia stream is based on the section as a unit. The section sampling method 15 selectively retrieves a section from a disk array in which sections are arranged in a circular manner, and performs fast forward (FF) retrieval at any fast forward speed desired by the viewer. The playback method 20 enables the terminal to play the retrieved video stream quickly and forwardly, and maintain the same buffer space and transmission frequency bandwidth as required by the normal playback operation.

FIG. 3 shows another scheme for obtaining the FF retrieval of the disk array video server by using the storage method 10, the section arrangement method 35, and the playback method 20 according to another embodiment of the present invention. The storing method 10 and the playing method 20 are the same as the method in FIG. 2. The sector placement method 35 wisely allocates sectors to the disk so that some predetermined FF speed can sample the sector completely uniformly in the FF mode.

Now, various tasks and programs for controlling scanning will be described with reference to FIGS. 4-10.

Figure 4 shows a sequence of MPEG video frames 1-8, which are composed of an inner frame (I), a predictive frame (P), and an interpolation frame (B). The storage order of the frames is different from the temporary storage order, and the response frames must be transmitted to the decoder in the order. In an MPEG stream, the P-box depends on the I-box, and the B-box depends on both the I and P-boxes. Therefore, frame B cannot be played without corresponding I and P frames. Because this subset includes B boxes without corresponding anchor I or P boxes, it is impossible to play every third box to obtain 3 times the playback speed.

For the above reasons, this storage method distinguishes MPEG streams into media segments. Each section includes a continuous frame that starts with an I frame and ends before another I frame. The distribution and retrieval of the multimedia data stream is based on the section. The consecutive segments are stored on different disks of the disk array 102.

The section sampling method of the retrieval task 150 will now be explained. The type of disk array video server shown in Figure 1 has n disks. During the normal operation period (standard playback speed) the maximum amount of work, the video segments S0-S29 are stored in the disk array 102 in a ring manner, so that n consecutive segments can be retrieved in one round. Roughly, when there are n disks, segment g is stored in disk k=fl(g, n), where fl(g, n)=g mod n(g takes n as the modulus and the remainder is fl(g, n)). Figure 5 shows an example of the placement of round-robin segments when n=10.

In order to obtain the FF feature, it is necessary to sample only some sections appropriately, and skip other sections. The sampling rate depends on the desired FF speed. If the FF speed is m times the normal speed, one section will be sampled from the m sections on average. For example, if the FF speed m is equal to 3, segment s0, segment s3, segment s6, and s9 will be retrieved from disk 0, disk 3, disk 6, and disk 9 respectively in Figure 5. At the same time, Skip sections s1, s2, s4, s5, s7, and s8. In the following, the complete sampling procedure will be explained in more detail with reference to the section sampling method.

In order to provide the best output during FF, the sampled segments must be distributed as evenly as possible. For example, in order to double the speed, only the even-numbered sections can be selected and the odd-numbered sections can be skipped. However, it can be verified that although this method samples the sectors uniformly, when there is an even number of disks in the array (such as the situation where n=10 as shown in FIG. 5), the maximum workload will not be obtained. In particular, when only even-numbered segments are selected, only half of the disks (ie, disk segments with an even number) participate in the segment retrieval, while the other half of the disks (ie, disks with an odd number) remain idle. Therefore, in order to generate an FF video segment retrieval method in a disk array that stores segments in a circular manner, it is not only necessary to sample as uniformly as possible, but also to ensure that the maximum amount of work is obtained. This procedure is explained below.

FIG. 6 shows a flowchart of the procedure in the retrieval task 150, which is used to determine which video section of each disk is retrieved in the FF mode. Assume that the number of disks in the array is n, and the expected FF speed is m times that of normal operation. Use 1 cm (n,m) to represent the least common multiple of m and n. For example, 1 cm (3,9)=9. For symbolic simplification, set z=nm/1 cm (n,m). For ease of description, FIG. 7 shows the retrieval of FF segments with n=9 and m=3, and the retrieved segments are marked with *'s.

Referring now to Fig. 6, the number of laps of segment retrieval r is equal to 1 at the beginning (step 60). Depending on whether r is an odd number or an even number, each disk will use an appropriate formula to determine the retrieved segment ( Step 70). When r is an odd number, it corresponds to the first half zigzag curve obtained from the retrieved section, such as the line formed in the first circle of FIG. 7 with sections 0*, 10*, and 20*. On the other hand, when r is an even number, it corresponds to the second half zigzag curve, such as the line formed in the second circle of FIG. 7 with segments 29*, 37*, and 45*. In particular, if r is an odd number, segment g will be retrieved from disk k, where g can only be determined by steps 80 and 85. If r is an even number, section g is retrieved from disk k, where g can only be determined by steps 90 and 95. After retrieving from disk k in step 100 and retrieving segment g, if more video segments are needed (step 105), proceed to step 110 and increment the number r by one revolution. Otherwise, the procedure ends in step 120.

Referring again to FIG. 7, it provides an example of n=9 and m=3, and the retrieved section is marked with *'s. Instead of the number of retrieved sections being a multiple of 3 (which makes disks 1, 2, 4, 5, 7 and 8 idle), the section sampling scheme described in Figure 6 makes the video sections retrieved in some retrievals Shift. For example, section 10 is extracted instead of section 9 and section 20 is extracted instead of section 19. Although this shift makes the retrieved sections not perfectly evenly distributed, it guarantees the maximum amount of work. The segment group retrieved in the first round of retrieval shown in Figure 7 is composed of segments 0, 10, 20, 3, 13, 23, 6, 16 and 26, and then the group is divided into 0, 3, 6 , 10#, 13, 16, 20#, 23, 26, where # indicates the shift of the retrieved section number. Under this scheme, the sections retrieved in the second round of retrieval shown in Figure 7 are 45, 37, 29, 48, 40, 32, 51, 43, and 35. #, 40, 43, 45#, 48, 51 order to display. It can be seen from Fig. 7 that the retrieved section forms a zigzag curve. The shift number of the zigzag curve is 2nm/lcm (n,m)-2, which is the smallest among all FF schemes that can obtain the maximum workload of the disk array video server. store.

The section placement method will now be explained. As shown in Figure 2 and Figure 3, the block placement method is an alternative to the block sampling method described above. In contrast to the section sampling method (this method selectively retrieves sections stored in a ring in the disk array), the section placement method wisely allocates sections to disks so that sampling does not require specific requirements, and Some predetermined FF speeds can sample the segment completely uniformly in the FF mode. Consider an FF job whose playback rate is m times the normal playback rate. In this FF mode, the order of retrieving sections from the given starting section i is {i, i+m, i+2m, i+3m...}. Because n media segments are retrieved in each circle, the retrieved segments are {(r-1)nm, (r-1)nm+m, (r-1)nm+2m,..., ( r-1)nm+(n-1)m}, where r is the number of turns of segment retrieval. It must ensure that these segments are mapped to different disks in order to have the maximum amount of work. The section placement function f2(g,n) defines the mapping from the media section g to disk k, where k is a number in the range from 0 to n-1 in a disk array with n disks.

Assuming that m is a multiple of the number of disks n, the mapping function can be defined as follows: f2(g,n)=(g+[g/n])mod n. The first term (g) represents the regular distribution of sectors on n disks, and the second term (g/n) represents a skew coefficient. It can be proved that f2(g,n) maps any segment of r {(r-1)nm, (r-1)nm+m, (r-1)nm+2m,..., (r-1)nm+(n -1)m} to a different disk.

Referring now to FIG. 8 (which shows a flowchart of the section placement program in the retrieval task 150), the number of section retrieval laps r is equal to 1 at the beginning (step 200). In the rth circle, the disk k will locate the i-th disk it retrieved (ie, the number of sectors g), where the numbers i and g can only be determined by steps 210 and 220, respectively. After the section g is retrieved from the disk k in step 230, if more video sections are needed (step 240), then go to step 250 and increment the number r by one turn. Otherwise, the procedure ends in step 260.

Referring now to FIG. 9, it shows that when the required FF speed is 3 times the normal operation, the video section is arranged in a disk array with 6 disks. This media section is arranged on the entire n disks. If the FF acceleration m is a multiple of the number of disks n, it is guaranteed to be retrieved for playback at different FF speeds smoothly. This arrangement ensures that different disks are all placed in the media section to be retrieved in a circle, so that the load imposed on the storage system during the retrieval process in the FF mode is the same as the load under normal operation.

The playback method will now be explained. During normal speed playback, the video data is retrieved from disk round by round. In each circle, retrieve a media segment from each disk in the disk array. The data is temporarily buffered and stored in the server, and sent to the terminal at a certain rate. In the FF mode, the server retrieves the segment according to any of the procedures in Figure 2 or Figure 3. Referring now to FIG. 10, which shows the processing steps of the receiving station, it has the functions of parsing the input stream and generating a valid input stream for the decoder. In step 300, the receiving terminal 103 receives the input section stream from the video server 100, and in step 310, the middle frame that does not have an associated anchor frame is discarded. Note that although the media section starts with an I box, it contains a B box with an anchor box on the outside of the media section. As shown in Fig. 4, the B box is located directly after the I box, because its dependency is ignored because the last P box of the previous media section is not retrieved. In step 320, the receiving station adjusts the occurrence timestamp embedded in the stream. The appearance timestamp determines the time when the video frame will appear. The time stamp must be adjusted to compensate for the skipped section and the discarded B box to reflect the correct playback time. Then, in step 330, the video frame is played.

This layout guideline obtains the sequential playback sequence of segments. Allow the viewer to review the scene in order to quickly locate the scene of interest. Because the segment size is fixed, the stream does not require additional buffering or transmission bandwidth. The segment maintains the average data stream rate, so the end-station decoder can receive the broadcast.

Although the present invention has been described with preferred embodiments, various modifications and improvements will be made to those skilled in the art. Therefore, it should be understood that the preferred embodiment is provided as an example, not a limitation. The scope of the present invention is defined by the appended patent application items.