Variable Speed Playback of Digital Video Stored in a Non-Tape Media

1. Field of the Invention

This invention relates generally to the field of playback of digital video as in a digital video tape recorder (VTR) or virtual digital VTR. More particularly, this invention relates to performing variable speed playback and shuttle of compressed digital video material in a manner which emulates the performance of a video tape recorder's variable speed playback and shuttle. The present invention is also useful in instances where temporal compression is needed (i.e. judicious merging elements of video frames to compensate for smaller display interval of a rapid video frame display).

2. Background of the Invention

In video tape recorders, variable speed playback of the video material is generally accomplished by increasing the tape speed during playback and providing dynamic tracking. In video tape editing application, such variable speed playback has a distinctive look which editors are accustomed to.

When a moving video image is stored digitally and retrieved at a higher than normal playback rate, this is generally accomplished by simply deleting (or not retrieving) frames of information. For example, with reference to FIG. 1, if the ten sequential frames F.sub.1 through F.sub.10 which are shown in FIG. 1 are to be played back at twice the normal playback rate, only alternate frames might be displayed. For example, frames F.sub.1, F.sub.3, F.sub.5, F.sub.7 and F.sub.9 would be displayed at the normal frame rate while frames F.sub.2, F.sub.4, F.sub.6, F.sub.8 and F.sub.10 would be omitted entirely. Consequently, only five frames of information would be displayed at a standard frame rate requiring only half the display time. Thus, the illusion that the image has been displayed at twice normal speed is created.

Unfortunately, when non-contiguous frames of digital video are consecutively displayed to produce a high speed image, a rough jumpy display results resembling a montage or a teleconferencing-type image in which updates are slower than real time resulting in discontinuous video. This type of implementation thus diverges substantially from the look of a video tape recorder's variable speed playback. In a video tape recorder, the motion is smooth and continuous but occurs at a higher rate. At high speed shuttle rates wherein discontinuous frames of video are consecutively displayed, the human brain has difficulty tracking the movement and little information is thus conveyed to the user.

It is desirable to create a simulation of this variable speed playback such as appears in analog VTR equipment for use in technology such as optical, magneto optical, magnetic and other storage media wherein, in general, the video frames are randomly accessible and not necessarily temporally ordered (e.g., frame 1 of a video sequence could be adjacent to frame 20 in a video sequence). Applications such as disk based non-linear editors for digital video are appropriate candidates for such technology.

It is an object of the present invention to provide an improved variable speed playback system for playing back compressed digital video.

It is another object of the invention to emulate the performance of a video tape recorder's variable speed playback and shuttle in a digital video environment, i.e. retaining the look of dynamic tracking.

These and other objects, advantages and features of the invention will become apparent to those skilled in the art upon consideration of the following description of the invention.

The present invention provides for mixing or proportional merging of two or more video frames to occupy proportionately less of a normal display time to yield a smooth update of the video image.

For variable speed play (approximately -1.times. to +3.times.), a video mix is performed on adjacent video frames. Since no more than 3.times. speed is required, no more than three frames of video need to be mixed. The mix is accomplished by adding the respective pixel values of the respective frames and dividing by the number of frames. Thus, when two frames are mixed, each frame contributes a 50% weighting to the resulting frame. For fractional speeds (e.g. 2.5.times.) alternating "mixed frames" constructed of two frames and three frames respectively are generated to produce a long term average of 2.5.times. in speed.

For shuttle operation (e.g. .+-.3.times. to .+-.30.times.) a different technique is used. In this technique, non-contiguous frames are combined with consecutive resulting frames ("shuttle frames" or "bridge frames") using a common frame to produce the mix. This creates an image which is much smoother and easier for the user to understand. In instances where the system holds bursts of data from a storage media in a buffer until processing can occur or until new data is loaded (in this case compressed video frames), and where the buffers cannot hold contiguous frames, the shuttle frame is constructed in a slightly different manner. Assuming a maximum buffer fill rate of one non-contiguous frame per eight frame time intervals, only one new frame per eight frames of video can be output. This is handled by holding a given frame long enough to compensate for this temporal limiting factor.

According to the present invention, a method for high speed playback of digital video data (e.g. D1 or D2 data) in which, at lower speeds, the frames of data to be played back are made of a mixture of consecutive frames of data. The frames of data are mixed by averaging the pixel values over consecutive frames to make up the output frames. For high speed shuttle operation, non-consecutive frames are averaged on a pixel by pixel basis to create bridging frames (referred to herein as shuttle frames). In order to improve the appearance of the output, consecutive shuttle frames contain a common original frame so that a component of the original data spans two output frames.

One method of the present invention for playback of video data at a speed greater than normal playback speed, includes the steps of: generating a sequence of output frames including a mixed frame where the mixed frame has a component of two or more frames of the original video data; and displaying the sequence of output frames.

Another method for playback of video data at a speed greater than normal playback speed, includes the steps of: looking up a first number of frames in a look-up table; creating a first mixed frame by averaging the first number of consecutive frames of data on a pixel by pixel basis; looking up a second number of frames in a look-up table; creating a second mixed frame by averaging the second number of consecutive frames of data on a pixel by pixel basis; generating a sequence of output frames including a sequence of the mixed frames; displaying the sequence of output frames at a frame rate equal to a normal playback speed frame rate.

A method for high speed shuttle playback of video data according to the invention includes the steps of: generating a sequence of output frames including a plurality of mixed frames, the mixed frames having a component of two or more frames of said video data; each mixed frame including a component of a previous output frame; and displaying the sequence of output frames. The shuttle frames are generated at a rate of 1 shuttle frame for each M video frames, where M is generally an integer.

According to one embodiment of the invention, an apparatus for high speed playback of digital video data includes a mass storage device for storing frames of video data. An input device is used to select a playback speed. Frames of video data are retrieved from the storage device and a computer generates a sequence of output frames including a mixed frame, the mixed frame having a component of at least two frames of the video data. A display displays the sequence of output frames.

The features of the invention believed to be novel are set forth with particularity in the appended claims. The invention itself, however, both as to organization and method of operation, together with further objects and advantages thereof, may be best understood by reference to the following description taken in conjunction with the accompanying drawing.

FIG. 1 is an illustration of ten sequential video frames as they would be played back at normal speed.

FIG. 2 is an illustration of five mixed frames which would display the information from FIG. 1 at two times the normal playback rate.

FIG. 3 illustrates four mixed frames which would be played back to produce 2.5 times the normal playback rate of FIG. 1.

FIG. 4 is a flow chart describing the operation of the present invention for variable playback speeds.

FIG. 5 is an illustration of a sequence of video frames as they would be played back at normal speed.

FIG. 6 is an illustration of five consecutive shuttle frames representing a shuttle speed of 8.times..

FIG. 7 is an illustration of four consecutive shuttle frames representing a shuttle speed of 16.times..

FIG. 8 is a flow chart describing the operation of the present invention at shuttle playback speeds.

FIG. 9 is an illustration of buffer operation in the present invention.

FIG. 10 is an illustration of the hardware configuration of the present invention.

While this invention is susceptible to embodiment in many different forms, there is shown in the drawings that will herein be described in detail specific embodiments, with the understanding that the present disclosure is to be considered as an example of the principles of the invention and not intended to limit the invention to the specific embodiment shown and described.

Referring to FIG. 1, a sequence of ten sequential frames of video is shown labeled F.sub.1 through F.sub.10. At standard video speeds, frames 1 through 10 would be sequentially displayed at a fixed frame rate (e.g. 1 frame every 33.33 ms for NTSC) to produce normal speed video. If it is desired to show this video at faster than normal rate, the present invention utilizes the following technique for generating the higher rate video. Consider first, the example shown in FIG. 2 wherein the speed selected is twice the normal video rate. In this example, it is desirable to produce five sequential frames of video which represent the ten original frames of FIG. 1 but which can be viewed in half the time. Thus, the current invention generates five "mixed frames" (MF) shown in FIG. 2 as MF.sub.1 through MF.sub.5. In examples lower in speed than approximately three times the normal video rate (that is, at variable speed play rates) each mixed frame is generated as a combination of two or more of the original frames F.sub.1 through F.sub.10. In FIG. 2 for example, MF.sub.1 would be generated by summing the pixel values of frames F.sub.1 and F.sub.2 and dividing the sum by two. That is:

For D1 video, each pixel is represented as 2 eight bit bytes containing (YC.sub.R or YC.sub.B) where Y is luminance, C.sub.R is Red chrominance and C.sub.B is Blue chrominance (in PAL, Y, U and V) In this instance, the individual values of Y, C.sub.R, and C.sub.B are determined for each frame and then individually averaged and converted back to (YC.sub.R or YC.sub.B). While the present invention is illustrated in terms of D1 data, similar pixel by pixel combining of video frames can be accomplished using RGB images (as in 3 byte per pixel data representing high definition video) by separating each pixel into R, G and B components. The R, G and B component of each pixel is then averaged to produce the mixed frame. Similar techniques can be used for other formats.

In the case where a fractional speed increase is desired, a modification of the process is used. Consider for example the generation of mixed frames for a video rate of 2.5 times normal. In this instance, the mixed frame data is generated in a manner which produces a long term average of about 2.5 frames of original video data for each mixed frame of video data. In the example of FIG. 3, MF.sub.1 may be created by mixing together the information from F.sub.1, F.sub.2 and F.sub.3 as follows:

MF.sub.2 is then generated as

In this manner, alternating mixed frames are generated as combinations of two and three original data frames.

A similar scheme can be derived for virtually any fractional speed. For example, if a rate of 2.7 times normal is desired, seven out of ten frames of mixed frame data are generated as a combination of three original frames. The remaining frames are generated as a combination of two original frames. In order to retain as smooth an image as possible, the distribution of mixed frames created as a mixture of two and three original frames should be a relatively even distribution in time to the extent possible.

In the case of the preferred embodiment, as previously described, this mixing process is carried out on a pixel by pixel basis for D1 format video which is represented by two bytes per pixel. These two bytes represent Y, C.sub.R and C.sub.B data so, the Y data is added and divided by two, the C.sub.R data is added and divided by 2, and the C.sub.B data is added and divided by two to produce each pixel of the mixed frame MF.sub.1. Thus, in general, a mixed frame of data can be represented by the equation: ##EQU1## where i, j and k are integers with i representing a counter for an original data frame, j representing a counter for a mixed frame (MF) and k representing a number of original frames to be averaged. In one embodiment of the present invention, the original frames are processed in sequences of 10 frames so that the pattern repeats after ten mixed frames are generated. In this embodiment, the value of k can be read from a look-up table such as the following TABLE 1:

In TABLE 1, as shown in abbreviated form, all desired speeds in 0.1.times. increments between 1.1 and 3.0 are listed along with a number of original frames to be combined. When mixed frame number 10 is reached (N=10) the sequence starts over again. When coupled with a motion vector, a different distribution of frame weighting can be implemented in order to achieve an even more efficient use of frames with a more intelligent distribution.

The process for variable speed operation at forward speeds between 1.1 and 3 times normal is described by the flow chart of FIG. 4. Those skilled in the art will appreciate that the analogous process for reverse speeds is also within the scope of the present invention. The process starts at step 20. When the user selects a playback speed, it is received at step 24 as a speed value M. Counters i, N and j are initialized to 1, 1 and 0 respectively at step 26. Counter j is a mixed frame counter, counter i is an original frame counter and N is a counter used to enter the look-up table. At step 30, j and N are incremented by 1. If N=11 at step 32, the look-up table counter N is reset to 1 at step 36. In either event, at step 40, the look-up table is entered on the values of M and N to retrieve the value of k (the number of original frames to be mixed). Note that k may vary in value each time it is retrieved from the distribution table (i.e. each time step 40 is carried out).

When the value of k has been retrieved, the mixed frame is computed on a pixel by pixel basis as described by Equation 1 at step 44. The value of i is then incremented by the number of original frames processed (k) in step 48. The frame is then output at step 50 and the process loops back to step 30.

Those skilled in the art will recognize that the frame combinations described in TABLE 1 can be changed considerably without departing from the invention. For example, column 2.5 could equally be 2,3,2,3,2,3,2,3,2,3 (top to bottom). Also, the table can be restricted to the fractional part of the speed (0.0 to 0.9) with a similar algorithm wherein the integer part is added to the value looked up to arrive at k. Rather than use of a look-up table, various algorithms could be developed to provide the frame distribution and averaging. It is also noted, that for speeds between 1.0 and 2.0, the values of N will sometimes be equal to one, indicating that no mixing of frames occurs for that particular "mixed frame". Rather, that frame is simply equal to the original frame.

For reverse speeds, the present invention works in essentially the same manner. Since the video frames are randomly accessible, the only difference is that the frame numbers for the original data are renumbered in reverse order, or equivalently, the algorithm of FIG. 4 can be modified suitably to accomplish the reverse process.

When high speed shuttle operation is desired in the context of the present invention, an additional problem surfaces. At higher speeds, the human brain finds it difficult to process sequential images which represent frames of information too far separated in time. For example, using conventional shuttling techniques at eight times normal speed, only every eighth frame would be displayed. Due to the generally significant differences in the image of frames separated this far in time, the resulting sequence of frames is difficult for an observer to follow and understand. In order to improve the ability to track such information, a variation of the present process is used. In FIG. 5 an extended representation of the original data of FIG. 1 is shown. The reader will understand that additional frames of original data follow frame 25 when viewing the data at normal speed.

In shuttle operation as illustrated in FIG. 6 mixed frames of data, which will be referred to herein as shuttle frames, are generated as represented by SF.sub.1 through SF.sub.4 in FIG. 6. Consider the example of playback at eight times normal speed for the example of FIG. 6. In this example, shuttle frame SF.sub.1 is made identical to frame F.sub.1. It is generally better to begin (and end) with an unaltered frame to give the user a clear starting (and ending) image. Frame SF.sub.2 is generated by mixing the pixel values of frame 1 and frame 9 so that SF.sub.2 is given by the following equation:

In a similar manner, SF.sub.3 and SF.sub.4 are generated as:

Thus, to the extent possible, each shuttle frame contains a component from the previous frame (after the very first frame). That is, SF.sub.2 and SF.sub.1 both include frame F.sub.1 as a component. In a like manner, SF.sub.3 and SF.sub.2 both contain the component F.sub.9, and SF.sub.4 and SF.sub.3 both contain the component F.sub.17. Due to the common subject matter contained in each adjacent shuttle frame, the human brain is more readily able to understand the high speed video action which is presented, and the video image more closely resembles that of shuttle on a VTR. Subsequent frames are generated in a similar manner, except that it is preferrable to end with an unaltered frame taken from the original collection of frames to provide a clear image at the end point.

In a similar manner, FIG. 7 illustrates a shuttle speed of 16 times normal. Here once again SF.sub.1 equals F.sub.1. SF.sub.2 is made up of pixel values created from F.sub.1 and F.sub.17 as:

SF.sub.3 is given by:

Each consecutive frame is thus constructed using a common component from the previous frame and a component which will become part of the following frame. While this example uses the 17th, 33rd, 49th, etc. frame, other suitable representative frames could be selected. At the end point, it is once again desirable to end with an unaltered frame to provide a clear end point image.

Turning now to FIG. 8, a flow chart describing the process of shuttle speed playback as illustrated in FIGS. 5 through 7 is shown starting at 80. Once again, the user enters the shuttle playback speed at 82 as a value M. In shuttle mode, the value of M is an integer between 3 and 30. The value of j (the shuttle frame counter) is initialized at step 86 to a value of 0 and incremented at step 90 by 1. For the first shuttle frame (SF.sub.1, j=1), the value of the shuttle frame is simply that of original frame 1 (F.sub.1). Thus, at step 92, the value of j is inspected. If j=1 at 92, SF.sub.j =F.sub.1 at step 94 and the frame is output at step 96. If j>1 at step 92, the process goes to step 98 where SF.sub.j is computed as: ##EQU2## Finally, at step 96, the computed frame SF.sub.j is output and the process returns to step 90 where j is incremented and the next frame is computed.

In the above shuttle play process, there is no provision for presenting an end point image having no mixed frame component. In general, as previously mentioned, it is desirable, but not required, to present an image which is unaltered as the last frame. Depending upon the number of frames to be presented, this generally leads to an additional frame presented at the beginning and end of the shuttle. Thus, to display e.g., 57 frames of video at 8.times., one would expect a total of 57.div.8=7.125.apprxeq.7 shuttle frames to be produced. In fact, 7 shuttle frames are produced, but if it is desired to produce a clear image at the start and end, two additional frames, one at the beginning and one at the end, are presented for display (F.sub.1 and F.sub.57). For short sequences of shuttle frames, this obviously leads to an actual shuttle rate less than the selected value (in this example 8.times. is selected, but the actual effective rate is 57 frames.div.9 frames=6.33.times.). As the length of the sequence increases, the number of additional frames remains two, so the effect is minimal. For example, if 1000 original frames are shuttled at 8.times., 125 shuttle frames plus 2 frames (beginning and end) would be displayed resulting in an actual shuttle rate of 1000 frames.div.127 frames=7.87.times..

When the end point does not lie exactly at a multiple of the shuttle rate plus 1, (e.g. for 8.times.: 9, 17, 25, 33 . . . ), an adjustment of the algorithm is needed to complete the shuttle frame sequence. This can be accomplished in several ways, any of which are acceptable. For example, consider an 8.times. sequence of frames ending at frame F.sub.30. Any of the following sequences produce an acceptable shuttle frame sequence:

In sequence 1, the last frame is not incorporated as part of the SF.sub.4, but is simply presented as the last frame. In Sequence 2, the spacing between frames which are averaged is adjusted throughout the sequence so that the last frame is incorporated in SF.sub.4. In sequence 3, the spacing between frames averaged to produce SF.sub.4 is adjusted to be 13 frames (rather than 8) to compensate for the end point. In sequence 4, the spacing between the last two averaged frames is adjusted to be 5 and an additional frame is presented to compensate for the end point. Sequence 5 compensates for the end point by spacing the last two frames averaged by 5 and omits use of an un-mixed frame for SF.sub.1. Sequence 6, also spaces the last two mixed frames by 5 to compensate for the end point, but omits use of un-mixed frames at both beginning and end. Each of these sequences are within the scope of the invention. Those skilled in the art will appreciate that many variations of this process are possible for compensating for the end point utilizing the present invention.

The present shuttle process can be used as long as the system's buffer can fill rapidly enough to hold all of the frames needed to construct the shuttle frames. However, when the buffer fill rate is too slow for high speed shuttle operation, a different process is used. Consider, for example, a system with a maximum buffer fill rate of one non-contiguous frame per eight frame time intervals as shown in FIG. 9. Only one new frame per eight frames of video can be created. This problem is handled by holding a given frame long enough to compensate for this temporal limiting factor.

It is generally preferrable, as described above, for the starting and ending frames to not be mixed frames. For example, if frames F.sub.1 through F.sub.57 are to be displayed in 16.times. shuttle, the following sequence of frames are displayed:

In this example, the frame spacing between frames which are averaged is adjusted at the last mixed frame SF.sub.5 to 8 so that the sequence ends on a frame which is not a mixed frame. In this instance, the shuttle frames (after SF.sub.1 and before SF.sub.6 are generated as: ##EQU3## where p.sub.n =1, 9, 17, 33, 49, 57. For different rates M and end points, the series P.sub.n would, of course, differ with the ultimate goal being a long term average number of mixed frames of approximately 1/M of the total original frames being used and end points having no mixed frames. The methods of FIGS. 4 and 8 account for not having a mixed frame as the first frame and can easily be modified to provide for having no mixed frame at the end point.

The shuttle play mode could also be implemented using a combination of more than two original frames to create the shuttle frames without departing from the invention.

Once again, for reverse shuttle speeds (e.g. -3 to -30), the present invention works in essentially the same manner. Since the video frames are randomly accessible, the only difference is that the frame numbers for the original data are renumbered in reverse order, or equivalently, the algorithm of FIG. 8 can be suitably modified to accomplish the reverse process.

Referring now to FIG. 10, a hardware embodiment of the present invention is shown. In the preferred embodiment, the present invention is implemented using a programmed digital computer such as CPU/controller 110 as both a central processor and as a control device. The computer includes memory such as random access memory (RAM) and read only memory (ROM) (not shown) in a conventional arrangement. An input device 114, which may be a general purpose input device such as a mouse or a computer keyboard, is used to select playback speed and other operational parameters. In other embodiments, dedicated input hardware can be devised to simulate the operation and feel of VTR controls, if desired.

The frames of original video data are stored on a mass storage device 120 such as, for example, a magneto-optical (MO) disk drive or an array of such drives operating in conjunction with conventional high speed hard disk drives. Access to the mass storage device 120 is through a buffer 126 which may include a high speed disk drive or RAM memory or a combination thereof.

In operation, compressed video frames are retrieved from mass storage device 120 in a burst transfer and stored in buffer 126 until needed. If a look-up table is used, it may also be stored in the mass storage device until needed. The compressed video frames are retrieved from the buffer 126 in accordance with the frame selection algorithm, as described previously, depending upon the operational mode (shuttle or high speed playback) and the speed selected via the input device 114. These frames are then decompressed by decompressor 130 and converted into their Y, C.sub.R and C.sub.B components (or other basic components such as RGB) and stored in a frame memory 136 with pixels at an address determined by address generator 140. The frames stored in frame memory 136 are then averaged on a pixel by pixel basis in a high speed arithmatic logic unit 145. The average values of each pixel is output to an output frame memory 150. The output of output frame memory 150 is provided, along with the frames stored in frame memory 136, to a multiplexer 158 for display on a display 162 at the predetermined frame rate of the system. The multiplexer 158 is controlled by CPU/controller 110 to select one of the four inputs for display.

The operation of the system may be enhanced by use of a motion vector detector 170. Motion vector detector 170 can be used to determine a more intelligent frame distribution for averaging to produce an enhanced image. Motion vector detector 170 receives frames from the CPU/controller 110 and determines which frames to combine and how to combine them to produce shuttle frames or mixed frames.

In the embodiment described above, the present invention is implemented using a dedicated ALU for performing the mixing function. However, those skilled in the art will recognize that a programmed general purpose processor operating at an adequately high speed could also be used. To compensate for the relatively low speed of MO disk drives, the data in the embodiment above is buffered in a high speed hard disk drive for display on a conventional video monitor. Those skilled in the art will appreciate that the present invention could also be implemented using dedicated hardware rather than the programmed control CPU without departing from the invention. Numerous other variations will occur to those skilled in the art upon consideration of the present invention.

Thus it is apparent that in accordance with the present invention, an apparatus that fully satisfies the objectives, aims and advantages is set forth above. While the invention has been described in conjunction with specific embodiments, it is evident that many alternatives, modifications, permutations and variations will become apparent to those skilled in the art in light of the foregoing description. Accordingly, it is intended that the present invention embrace all such alternatives, modifications and variations as fall within the scope of the appended claims.