Method and apparatus for frame accurate access of digital audio-visual information

• US 5,659,539 A
• Filed: 07/14/1995
• Issued: 08/19/1997
• Est. Priority Date: 07/14/1995
• Status: Expired due to Term

• Current Assignee: ARRIS Solutions, Inc. (CommScope Holding Company, Inc.)
• Original Assignee: Oracle Corporation
• Inventors: Porter, Mark A., Pawson, Dave
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): Assouad, Patrick J.
• Application Number:
  US08/502,480
• Time in Patent Office: 767 Days
• Field of Search: 364/514 A, 364/514 R, 348/7, 348/12, 348/13, 348/17, 348/19, 370/84, 370/108, 455/5.1
• US Class Current: 709/231
• CPC Class Codes: G11B 2020/00072 the compressed signal including a video signal
• CPC Class Codes: G11B 2220/20 Disc-shaped record carriers
• CPC Class Codes: G11B 2220/415 Redundant array of inexpensive disks [RAID] systems
• CPC Class Codes: G11B 27/031 Electronic editing of digitised analogue information signals, e.g. audio or video signals
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/162 User input
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/587 involving temporal sub-sampling or interpolation, e.g. decimation or subsequent interpolation of pictures in a video sequence
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 21/232 Content retrieval operation locally within server, e.g. reading video streams from disk arrays storage management G06F3/0604; details of querying and searching of video data from a database G06F16/739
• CPC Class Codes: H04N 21/23805 Controlling the feeding rate to the network, e.g. by controlling the video pump
• CPC Class Codes: H04N 21/2387 Stream processing in response to a playback request from an end-user, e.g. for trick-play
• CPC Class Codes: H04N 21/2393 involving handling client requests scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 21/2402 Monitoring of the downstream path of the transmission network, e.g. bandwidth available traffic monitoring in data switching networks H04L43/00; monitoring data switching networks utilization H04L43/0876
• CPC Class Codes: H04N 21/4305 : Synchronising client clock from received content stream, e.g. locking decoder clock with encoder clock, extraction of the PCR packets arrangements for synchronising receiver with transmitter by comparing receiver clock with transmitter clock H04L7/0012; arrangements for synchronising receiver with transmitter wherein the receiver takes measures against momentary loss of synchronisation H04L7/0083
• CPC Class Codes: H04N 21/44004 : involving video buffer management, e.g. video decoder buffer or video display buffer
• CPC Class Codes: H04N 21/47202 : for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 21/6377 : directed to server one-way streaming services wherein the source is controlled by the destination H04L65/613
• CPC Class Codes: H04N 21/658 : Transmission by the client directed to the server
• CPC Class Codes: H04N 21/6587 : Control parameters, e.g. trick play commands, viewpoint selection
• CPC Class Codes: H04N 21/8455 : involving pointers to the content, e.g. pointers to the I-frames of the video stream
• CPC Class Codes: H04N 21/8547 : involving timestamps for synchronizing content
• CPC Class Codes: H04N 21/8549 : Creating video summaries, e.g. movie trailer retrieval in video databases by using presentations in form of a video summary G06F16/739
• CPC Class Codes: H04N 7/17336 : Handling of requests in head-ends

Abstract

A method and apparatus for use in a digital video delivery system is provided. A digital representation of an audio-visual work, such as an MPEG file, is parsed to produce a tag file. The tag file includes information about each of the frames in the audio-visual work. During the performance of the audio-visual work, data from the digital representation is sent from a video pump to a decoder. Seek operations are performed by causing the video pump to stop transmitting data from the current position in the digital representation, and to start transmitting data from a new position in the digital representation. The information in the tag file is inspected to determine the new position from which to start transmitting data. To ensure that the data stream transmitted by the video pump maintains compliance with the applicable video format, prefix data that includes appropriate header information is transmitted by said video pump prior to transmitting data from the new position. Fast and slow forward and rewind operations are performed by selecting video frames based on the information contained in the tag file and the desired presentation rate, and generating a data stream containing data that represents the selected video frames. A video editor is provided for generating a new video file from pre-existing video files. The video editor selects frames from the pre-existing video files based on editing commands and the information contained in the tag files of the pre-existing video files. A presentation rate, start position, end position, and source file may be separately specified for each sequence to be created by the video editor.

Claims

1. A method for playing at a second presentation rate an audio-visual work that has been digitally encoded in a digital data stream for playback at a first presentation rate, wherein said digital data stream includes a sequence of video frame data, each video frame data in said sequence of video frame data corresponding to a video frame in said audio-visual work, the method comprising the computer-implemented steps of:

selecting a selected set of video frames from said audio-visual work based on said second presentation rate;

constructing a second digital data stream that includes the video frame data that corresponds to each video frame of said selected set of video flames; and

transmitting said second digital data stream to a decoder;

wherein said step of selecting said selected set of video flames includes repeatedly performing the steps of;

determining a bit budget based on a first time value associated with a most recently selected video frame, a second time value associated with a current frame, said second presentation rate and a data transfer rate;

determining a size of the frame data that corresponds to the current frame;

if the size of the frame data that corresponds to the current frame exceeds said bit budget, then

not selecting said current frame as a video frame in said selected set of video flames, and

selecting a new frame as a new current frame; and

if the size of the frame data that corresponds to the current frame does not exceed said bit budget, then selecting said current frame as a video frame in said selected set of video frames;

wherein said step of selecting said selected set of video flames includes the steps of;

determining whether selection of said current frame would cause said second digital data stream to have a padding rate less than a predetermined padding rate; and

if selection of said current frame would cause said second digital data stream to have a padding rate less than said predetermined padding rate, then not selecting said current frame as a video frame in said selected set of video flames.

2. The method of claim 1, further comprising the steps of:

receiving a query from a user;

determining a response to said query; and

replacing padding data in said second digital data stream with said response to said query.

3. The method of claim 1 wherein said sequence of video frame data includes video frame data from which said corresponding video frame can be constructed without reference to any other video frame data, and video frame data from which said corresponding video frame cannot be constructed without reference to any other video frame data, said step of selecting a selected set of video frames including selecting for said selected set video frames that correspond to video frame data from which said corresponding video frame cannot be constructed without reference to any other video frame data if and only if the video frames that correspond to said other video frame data have also been selected for said selected set of video frames.

6. The method of claim 1 wherein said step of constructing said second digital data stream includes causing said second digital data stream to conform to a predetermined format by inserting prefix data into said second digital data stream prior to each video frame data, and inserting suffix data into said second digital data stream after each video frame data.

7. The method of claim 6 wherein said step of constructing said second digital data stream includes inserting delay data into said second digital data stream when said second presentation rate is slower than said first presentation rate, said delay data causing more time to elapse between decoding successive video frames represented in said second digital data stream than elapses between decoding successive video frames in said digital data stream.

8. The method of claim 7 wherein said step of inserting delay data includes inserting padding data into said second digital data stream between frame data that corresponds to successive video frames.

9. The method of claim 7 wherein said step of inserting delay data includes inserting decode time stamps into said second digital data stream that indicate when corresponding video frames represented in said second digital data stream are to be decoded.

10. The method of claim 1 wherein said steps of selecting is performed by a stream server running on a first computer and said steps of constructing and transmitting are performed by a video pump running on a second computer, the method further comprising the step of said stream server transmitting to said video pump a sequence of instructions that indicate how said video pump is to construct said second digital data stream.

11. The method of claim 1 further comprising the steps of:

parsing the digital data stream to generate tag information, said tag information including for each frame represented in said digital data stream;

a location within said digital data stream of the frame data that represents said frame,

a size of the frame data that represents said frame, and

a time value that indicates when said frame is to be displayed during a performance of said audio-visual work at said first presentation rate; and

selecting said selected set of video frames based on said tag information.

12. The method of claim 11 wherein said digital data stream is divided into a plurality of packets, said step of parsing including the step of generating in said tag information, for each frame represented in said digital data stream, data indicating an offset between a starting boundary of the frame data for said frame and a start of the packet of said plurality of packets in which said starting boundary resides.

13. The method of claim 6 wherein one or more non-video packets are contained within a start boundary and an end boundary of frame data for a given frame in said selected set of video frames, the method further comprising the step of removing at least one of said one or more non-video packets from said frame data for said given frame prior to transmitting said frame data for said given frame in said second digital data stream.

4. A method for playing at a second presentation rate an audio-visual work that has been digitally encoded in a digital data stream for playback at a first presentation rate, wherein said digital data stream includes a sequence of video frame data, each video frame data in said sequence of video frame data corresponding to a video frame in said audio-visual work, the method comprising the computer-implemented steps of:

selecting a selected set of video frames from said audio-visual work based on said second presentation rate;

constructing a second digital data stream that includes the video frame data that corresponds to each video frame of said selected set of video flames; and

transmitting said second digital data stream to a decoder;

wherein said sequence of video frame data includes video frame data from which said corresponding video frame can be constructed without reference to any other video frame data, and video frame data from which said corresponding video frame cannot be constructed without reference to any other video frame data, said step of selecting a selected set of video frames including not selecting for said selected set any video frame that corresponds to video frame data from which said corresponding video frame cannot be constructed without reference to any other video frame data; and

wherein said second presentation rate is negative relative to said first presentation rate.

5. The method of claim 4 wherein said steps of selecting, constructing and transmitting are performed in parallel.

14. The method of claim 4 further comprising the steps of:

transmitting said digital data stream to said decoder prior to receiving a rate change request from a user;

receiving said rate change request from said user; and

in response to said rate change request from said user, ceasing to transmit said digital data stream to said decoder, and performing said steps of selecting said selected set of video flames, constructing said second digital data stream, and transmitting said second digital data stream to said decoder.

15. The method of claim 14 wherein said rate change request includes data identifying said second presentation rate, the method including the step of determining said second presentation rate by reading said data identifying said second presentation rate from said rate change request.

16. The method of claim 14 wherein said step of transmitting said digital data stream includes reading said digital data stream from a plurality of storage devices using redundant array of inexpensive disks (RAID) error correction, and said step of transmitting said second digital data stream includes reading frame data for said selected set of video frames from said plurality of storage devices without using RAID error correction.

17. The method of claim 4 further comprising the steps of:

selecting a selected data stream from a plurality of digital data streams, each of said plurality of digital data streams representing said audio-visual work at a different presentation rate;

if said selected data stream represents said audio-visual work at said presentation rate, then transmitting data from said selected data stream without performing said steps of selecting a selected set of video frames and constructing said second digital data stream;

If said selected data stream does not represent said audio-visual work at said second presentation rate, then

selecting said selected set of video frames from frames represented in said selected data stream and;

constructing said second digital data stream to include frame data from said selected data stream.

18. The method of claim 17 wherein:

said plurality of digital data streams include a plurality of frame types including a first frame type that contains all of the information required to reconstruct a frame; and

said step of selecting said selected data stream is performed based on how many of said video frames in said selected set of video frames would have said first frame type.

21. The method of claim 14 further comprising the steps of:

generating a second digital data stream based on said original digital data stream;

when said second digital data stream reflects data at a first location in said original digital data stream, performing the steps of

receiving a skip control signal that indicates a second location in said original digital data stream;

reading said tag data to determine a boundary of a frame that corresponds to said second location;

causing said second digital data stream to reflect data beginning at the boundary of the frame that corresponds to said second location.

22. The method of claim 21 wherein said skip control signal indicates said second location by specifying an amount of time, said second location being the location of data that would be reflected in said second digital data stream after said amount of time had elapsed dining a normal speed, sequential playback operation.

19. A method of preprocessing an original digital data stream that represents an audio-visual work to create tag information, the audio-visual work including a sequence of frames, the original digital data stream including a sequence of frame data, each frame data corresponding to a frame in said sequence of frames, the method comprising the steps of:

for each frame in said sequence of frames, performing the steps of

determining boundaries within said original digital data stream for the frame data corresponding to said frame;

generating tag data that includes boundary data that indicates said boundaries of said frame data; and

storing said tag data separate from said original digital data stream;

wherein a decoder uses one or more state machines to decode said original digital data stream;

wherein said tag data includes, for each frame in said sequence of frames, state data that represents a state of said one or more state machines, said state data for a given frame indicating a state that said one or more state machines would be in when said decoder receives the frame data corresponding to said given frame during a normal-speed performance of said audio-visual work.

20. The method of claim 19 wherein said sequence of frame data includes multiple types of frame data, the method further comprising, for each frame in said sequence of frames, performing the step of generating frame type data that indicates a frame type for the frame data corresponding to said frame.

23. The method of claim 19 wherein said original digital data stream is an MPEG-2 data stream, said one or more state machines including a program elementary stream state machine, a video state machine and a transport layer state machine.

24. The method of claim 19 wherein said original digital data stream is an MPEG-1 data stream, said one or more state machines including a pack layer state machine and a system state machine.

25. A method for selecting frames for display during a performance at a specified presentation rate of a work represented in a digital video file, wherein the performance is produced by decoding a data stream generated from the digital video file over a channel having a predetermined data transfer rate, the method comprising:

selecting for display a first frame represented by frame data in said digital video file, said first frame being associated with a first time;

inspecting a second frame that is represented by frame data in said digital video file, said second frame being associated with a second time;

determining a bit budget based on said presentation rate, a time difference between said first time and said second time and said predetermined data transfer rate;

comparing the bit budget to the size of the frame data that represents said second frame;

if the size of the frame data exceeds the bit budget, then skipping the second frame;

if the size of the frame data is less than the bit budget, then selecting the second frame for display; and

wherein said method is performed in real time during the performance at the specified presentation rate of the work represented in the digital video file.

26. The method of claim 25 further comprising the steps of:

determining a frame type of said second frame; and

skipping said second frame if said frame type does not correspond to an encoding technique that preserves all of the information required to reproduce said frame.

27. The method of claim 25 wherein said digital video file is an MPEG-1 or MPEG-2 file which includes I-frames, P-frames and B-frames, the method further comprising the steps of:

determining whether said second time is an I-frame, a P-frame or a B-frame;

said second time is a P-frame, then skipping said second time if any I-frames or P-times located between said first time and said second time have been skipped; and

if said second time is a B-frame, then skipping said second time if any I-frames or P-frames located between said first time and said second time have been skipped.

28. A method for selecting frames for display during a performance at a specified presentation rate of a work represented in a digital video file, wherein the performance is produced by decoding a data stream generated from the digital video file over a channel having a predetermined data transfer rate, the method comprising:

selecting for display a first time represented by frame data in said digital video file, said first time being associated with a first time;

inspecting a second time that is represented by frame data in said digital video file, said second frame being associated with a second time;

determining a bit budget based on said presentation rate, a time difference between said first time and said second time and said predetermined data transfer rate;

comparing the bit budget to the size of the frame data that represents said second frame;

if the size of the frame data exceeds the bit budget, then skipping the second frame; and

if the size of the frame data is less than the bit budget, then selecting the second frame for display;

determining whether selection of said second frame would cause said data stream to have a padding rate less than a predetermined padding rate; and

skipping said second frame if selection of said second frame would cause said data stream to have a padding rate less than said predetermined padding rate.

29. A method for selecting frames for display during a performance at a specified presentation rate of a work represented in a digital video file, wherein the performance is produced by decoding a data stream generated from the digital video file over a channel having a predetermined data transfer rate, the method comprising:

selecting for display a first frame represented by frame data in said digital video file, said first frame being associated with a first time;

inspecting a second frame that is represented by frame data in said digital video file, said second frame being associated with a second time;

determining a bit budget based on said presentation rate, a time difference between said first time and said second time and said predetermined data transfer rate;

comparing the bit budget to the size of the frame data that represents said second frame;

if the size of the frame data exceeds the bit budget, then skipping the second frame; and

if the size of the frame data is less than the bit budget, then selecting the second frame for display;

wherein said method is performed in real time during the performance at the specified presentation rate of the work represented in the digital video file.

30. A method for selecting frames for display during a performance at a specified presentation rate of a work represented in a digital video file, wherein the performance is produced by decoding a data stream generated from the digital video file over a channel having a predetermined data transfer rate, the method comprising:

selecting for display a first frame represented by frame data in said digital video file, said first frame being associated with a first time;

inspecting a second frame that is represented by frame data in said digital video file, said second frame being associated with a second time;

determining a bit budget based on said presentation rate, a time difference between said first time and said second time and said predetermined data transfer rate;

comparing the bit budget to the size of the frame data that represents said second frame;

if the size of the frame data exceeds the bit budget, then skipping the second frame; and

if the size of the frame data is less than the bit budget, then selecting the second flame for display;

receiving data representing a rate for skipping a particular type of reference frames;

determining whether said second frame is said particular type of reference frame; and

if the size of the frame data is less than the bit budget, then skipping said second frame if necessary to maintain said rate of skipping said particular type of reference frame.

31. The method of claim 30 wherein said digital video file is an MPEG-1 or MPEG-2 file, wherein:

the step of receiving data representing a rate for skipping said particular type of reference frames includes receiving data representing a rate for skipping I-frames;

the step of determining whether said second frame is said particular type of reference frame includes determining whether said second frame is an I-frame; and

the step of skipping said second frame if necessary to maintain said rate of skipping said particular type of reference frames includes skipping said second frame if necessary to maintain said rate of skipping I-frames.

32. A method for creating a second digital video stream from one or more other digital video streams, the method comprising the computer-implemented steps of:

receiving a series of editing commands, each editing command in said series of editing commands specifying a start position, an end position, and a presentation rate;

for each editing command in said series of editing commands, performing the steps of

selecting a selected set of video flames between said start position and said end position in said one or more other digital video streams based on said presentation rate; and

storing frame data corresponding to said selected set of video flames in said second digital video stream;

wherein said one or more other digital video streams includes a plurality of other digital video streams;

wherein each editing command in said series of editing commands specifies one of said other digital video streams; and

wherein said step of selecting said selected set of video flames includes selecting video flames that are represented by data that is located between said start position and said end position in the digital video stream specified in said editing command.

33. A method for creating a second digital video stream from one or more other digital video streams, the method comprising the computer-implemented steps of:

receiving a series of editing commands, each editing command in said series of editing commands specifying a start position, an end position, and a presentation rate;

for each editing command in said series of editing commands, performing the steps of

selecting a selected set of video frames between said start position and said end position in said one or more other digital video streams based on said presentation rate; and

storing frame data corresponding to said selected set of video frames in said second digital video stream;

wherein said start position indicates a first amount of elapsed time; and

wherein said end position indicates a second amount of elapsed time.

34. A method for creating a second digital video stream from one or more other digital video streams, the method comprising the computer-implemented steps of:

receiving a series of editing commands, each editing command in said series of editing commands specifying a start position, an end position, and a presentation rate;

for each editing command in said series of editing commands, performing the steps of

selecting a selected set of video flames between said start position and said end position in said one or more other digital video streams based on said presentation rate; and

storing frame data corresponding to said selected set of video frames in said second digital video stream;

wherein the step of selecting said selected set of video frames between said start position and said end position in said one or more other digital video streams based on said presentation rate comprises the steps of;

determining a bit budget based on a first time value associated with a most recently selected video frame, a second time value associated with a current frame, said presentation rate and a data transfer rate;

determining a size of the frame data that corresponds to the current frame;

if the size of the frame data that corresponds to the current frame exceeds said bit budget, then

not selecting said current frame as a video frame in said selected set of video frames, and

selecting a new frame as a new current frame; and

if the size of the frame data that corresponds to the current frame does not exceed said bit budget, then selecting said current frame as a video frame in said selected set of video frames.

35. A method for creating a second digital video stream from one or more other digital video streams, the method comprising the computer-implemented steps of:

receiving a series of editing commands, each editing command in said series of editing commands specifying a start position, an end position, and a presentation rate;

for each editing command in said series of editing commands, performing the steps of

selecting a selected set of video frames between said start position and said end position in said one or more other digital video streams based on said presentation rate; and

storing frame data corresponding to said selected set of video frames in said second digital video stream;

storing data between said frame data corresponding to said selected set of video frames to cause said second digital video stream to conform to a predetermined format.

36. The method of claim 35 wherein:

said predetermined format is MPEG-2; and

said step of storing data between said frame data includes storing data to serve as a valid transport packet header and PES packet header.

37. The method of claim 35 wherein:

said predetermined format is MPEG-1; and

said step of storing data between said frame data includes storing data to serve as a valid pack header and system header.

38. The method of claim 35 further comprising the step of removing one or more non-video packets from frame data corresponding to a frame of said selected set of video frames prior to storing said frame data in said second digital video stream.

39. A method for performing a seek operation during a performance of an audio-visual work, said performance being performed by decoding a digital data stream transmitted to a decoder, the method comprising the steps of:

receiving a seek instruction while transmitting to said decoder data from a first position in a digital representation of said audio-visual work;

in response to said seek instruction, performing the steps of;

ceasing to transmit data from said first position;

transmitting data from a second position in said digital representation of said audio-visual work;

generating prefix data that indicates a state of one or more state machines;

transmitting said prefix data after ceasing to transmit data from said first position and prior to transmitting data from said second position.

40. A method for performing a seek operation during a performance of an audio-visual work, said performance being performed by decoding a digital data stream transmitted to a decoder, the method comprising the steps of:

receiving a seek instruction while transmitting to said decoder data from a first position in a digital representation of said audio-visual work;

in response to said seek instruction, performing the steps of;

ceasing to transmit data from said first position;

transmitting data from a second position in said digital representation of said audio-visual work;

wherein said seek instruction indicates a predetermined period of time, the method further comprising the step of;

determining said second position based on said first position and said predetermined period of time.

41. The method of claim 40 wherein said step of determining said second position based comprises the steps of:

inspecting a first time value associated with a first frame that is represented by data located at said first position in said digital representation of said audio-visual work;

calculating a second time value based on said first time value and said predetermined period of time;

determining a second frame associated with said second time value; and

determining said second position to be a position within said digital representation of said audio-visual work of frame data that represents said second frame.

42. The method of claim 41 further comprising the steps of:

parsing said digital representation of said audio-visual work to generate tag data, said tag data including, for each frame in said audio-visual work;

a time value; and

a start position;

said step of inspecting a first time value including reading said first time value from said tag data;

said step of determining said second frame associated with said second time value including

inspecting said tag data to find a time value that corresponds to said second time value; and

selecting the frame associated with the time value that corresponds to said second time value as said second frame.