System and method for scheduling and processing image and sound data

• US 5,951,646 A
• Filed: 11/25/1996
• Issued: 09/14/1999
• Est. Priority Date: 11/25/1996
• Status: Expired due to Term

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: America Online Inc. (Warner Bros. Discovery, Inc.)
• Inventors: Brandon, Dalbert L.
• Primary Examiner(s): Rinehart, Mark H.
• Application Number:
  US08/755,586
• Time in Patent Office: 1,023 Days
• Field of Search: 395/200.61, 395/200.49, 395/200.66, 395/200.77, 395/114, 395/850, 395/888, 345/202, 345/302, 345/327, 345/328, 370/477, 370/510, 370/521, 348/7, 375/240, 379/93.08, 341/60, 382/232, 382/233, 382/244, 382/245, 382/246, 382/247, 709/231, 709/219, 709/236, 709/247, 710/68, 710/30
• US Class Current: 709/231
• CPC Class Codes: G10H 1/0066 using a MIDI interface
• CPC Class Codes: H04N 21/2368 Multiplexing of audio and video streams
• CPC Class Codes: H04N 21/26258 for generating a list of items to be played back in a given order, e.g. playlist, or scheduling item distribution according to such list retrieval of multimedia data based on playlists G06F16/40
• CPC Class Codes: H04N 21/2662 Controlling the complexity of the video stream, e.g. by scaling the resolution or bitrate of the video stream based on the client capabilities
• CPC Class Codes: H04N 21/4341 Demultiplexing of audio and video streams
• CPC Class Codes: H04N 21/4392 involving audio buffer management
• CPC Class Codes: H04N 21/44004 involving video buffer management, e.g. video decoder buffer or video display buffer
• CPC Class Codes: H04N 21/8113 comprising music, e.g. song in MP3 format
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments
• CPC Class Codes: H04N 21/85406 involving a specific file format, e.g. MP4 format
• CPC Class Codes: H04S 1/007 in which the audio signals are in digital form data reduction aspects thereof based on psychoacoustics G10L19/02

Abstract

A system and method for scheduling temporal data and non-temporal data to create a unified stream of data that includes both the temporal and non-temporal data and for processing the unified data stream. The temporal and non-temporal data is preferably in a compressed format. The system preferably includes a scheduler that takes temporal data (e.g., sound data) and non-temporal data (e.g., image data) and interleaves them together to form the unified data stream. The system also includes a processor that decompresses the compressed image data and produces an output image from both the decompressed image data and any uncompressed image data. The processor also plays the temporal data while it concurrently decompresses the compressed temporal data. The system can handle temporal data in any format, including voice data and MIDI files, as well as any type of image data, including videos and still images. Also disclosed is a method for scheduling and playing video data and sound data (including MIDI and voice) forming a computer slide-show, in which the video and sound data are interleaved into a unified data stream.

Claims

1. A system operating over a limited bandwidth channel, comprising:

(a) a receiver for receiving a sequence of temporal audio data to be encoded and transmitted over the limited bandwidth channel; and

(b) a processor for determining a shortage of audio data that could lead to a possible stall on the limited bandwidth channel, the processor including a system look-ahead that uses the determined shortage of sound data to analyze the sequence of temporal audio data to detect a stall condition in the temporal audio data, and if a stall condition is detected, finds a breakpoint in the sequence of temporal audio data and stops the sequence of temporal audio data at the breakpoint.

2. A method for scheduling and processing temporal data and non-temporal data in a unified data stream, comprising:

(a) interleaving temporal data and non-temporal data to form a unified data stream, at least some of the temporal data being audio data in a temporal compressed format and at least some of the non-temporal data being in a non-temporal compressed format; and

(b) processing the unified data stream, including;

(1) decompressing the non-temporal data in the non-temporal compressed format and producing an output image from at least some of the decompressed non-temporal data and any uncompressed non-temporal data, and

(2) concurrently playing the temporal audio data while decompressing the temporal audio data in the temporal compressed format by (A) searching for a breakpoint in an amount of the temporal audio data, (B) if a breakpoint is found, playing the amount of the temporal audio data to the breakpoint, (c) if no breakpoint is found, determining if the amount of temporal audio data is greater than a predetermined minimum amount of the temporal audio data, and (D) if the amount of the temporal audio data is greater than the predetermined amount of the temporal audio data, playing the amount of the temporal audio data.

3. The method of claim 2 wherein the step of concurrently playing the temporal audio data while decompressing the temporal audio data includes:

(a) inputting the amount of the temporal audio data from the unified data stream into an input buffer;

(b) decompressing the temporal audio data in the input buffer to obtain decompressed temporal data;

(c) inputting the decompressed temporal audio data into an output buffer;

(d) inputting additional temporal audio data from the unified data stream into the input buffer; and

(e) playing the decompressed temporal audio data held in the output buffer while decoding the additional temporal audio data.

4. The method of claim 3 wherein the step of playing the decompressed temporal data includes:

(a) determining if the temporal audio data held in the output buffer is equal to or greater than the predetermined minimum amount of the temporal audio data, the predetermined minimum amount of temporal audio data known as a prestart backlog, or if an end of file ("EOF") flag is held in the output buffer, the EOF flag indicating the end of the temporal audio data contained in the unified data stream;

(b) if the prestart backlog or the EOF indication is in the output buffer, looking for a breakpoint in the temporal audio data contained in the output buffer;

(c) if a breakpoint is found, playing the temporal audio data in the output buffer until reaching the breakpoint;

(d) if no breakpoint is found, determining if the amount of temporal audio data in the output buffer is greater than a maximum backlog, the maximum backlog representing a minimum amount of temporal audio data required to be in the output buffer for playing when no breakpoint is found; and

(e) if the amount of temporal audio data in the output buffer is greater than the maximum backlog, playing the temporal audio data in the output buffer.

5. The method of claim 4 wherein the step of playing the decompressed temporal audio data further includes:

(a) detecting if a stall has occurred during playing of the temporal audio data; and

(b) if a stall condition has occurred, replacing the maximum backlog with a restart backlog, the restart backlog increasing the amount of temporal audio data required to be in the output buffer for playing when no breakpoint is found.

6. The method of claim 2, further comprising:

(a) setting a plurality of markers in the temporal data at various times in the unified data stream;

(b) checking the unified data stream to determine a time when each of the plurality of markers is received by a player; and

(c) dividing an actual playing time between selected markers by the time between receipt of the selected markers to determine a baud rate for the temporal data.

7. The method of claim 5, further comprising:

(a) setting the maximum backlog, the restart backlog, and the prestart backlog;

(b) inserting the set maximum backlog, the set restart backlog, and the set prestart backlog into a startup header; and

(c) placing the input header at the beginning of the unified data stream.

8. The method of claim 2 wherein at least a portion of the temporal audio data is a MIDI file, the MIDI file including a plurality of tracks, each track having a plurality of messages, each message including time data, the method further comprising sorting the MIDI file using the time data to group together messages to form a plurality of MIDI file portions, each MIDI file portion representing a specific time.

9. The method of claim 8, further comprising:

(a) placing each MIDI file portion into a respective audio segment in the unified data stream, each audio segment having a download time and a play time;

(b) placing at least one non-temporal data segment between a first audio segment and a second audio segment;

(c) locating a backlog data gap after the end of the play time of the first audio segment and the end of the download time of the second audio segment; and

(d) locating at least one non-temporal data segment after the backlog data gap.

10. The method of claim 9, further comprising:

(a) splitting an audio segment at a breakpoint in the audio segment to form a first split audio segment and a second split audio segment; and

(b) locating at least one non-temporal segment between the first split audio segment and the second split audio segment.

11. The method of claim 2 wherein the interleaving step includes:

(a) dividing the temporal audio data into a plurality of audio segments;

(b) plotting a download time and a play time of a selected audio segment and a next audio segment to determine a latest possible start time ("st") for the next audio segment;

(c) placing all the audio segments in a latest possible location within the unified data stream to form an initial map that includes the temporal audio data; and

(d) fitting at least one segment of non-temporal data into any gaps that exist between adjacent audio segments in the initial map and that are sufficiently large to accommodate a segment of non-temporal data.

12. The method of claim 11 wherein the interleaving step further includes:

(a) detecting whether any overlaps exist between any adjacent audio segments or between any audio segment and any non-temporal segment or between any adjacent non-temporal segments; and

(b) if any such overlap is detected, moving at least one audio segment to eliminate the overlap.

13. The method of claim 12 wherein the interleaving step further includes:

(a) after eliminating any overlaps, determining if any adjacent audio segments can be placed next to one another without any gap between the adjacent audio segments; and

(b) relocating such non-gap audio segments to eliminate the gap in order to conserve space in a header located in the unified data stream.

14. The method of claim 13 wherein the interleaving step further includes eliminating any gaps between adjacent audio and non-temporal segments.

15. The method of claim 2 wherein at least some of the non-temporal data is image data, the method further comprising:

(a) sending a low resolution version of the image data in the unified data stream before sending additional resolution of the image data;

(b) displaying the low resolution version; and

(c) sending the additional resolution of the image data after displaying the low resolution version.

16. The method of claim 15, further comprising sending temporal data while the low resolution version of the image data is being sent and displayed.

17. The method of claim 2 wherein the temporal data includes video data, and wherein the step of decompressing the non-temporal data and producing the output image includes:

(a) separating the video data into a plurality of data blocks including a set of commands and a set of compressed data;

(b) forming an event table from the set of commands, the event table having a plurality of entries, each entry having a time and a list of events that occur at the time;

(c) storing a block of compressed information from the set of compressed data;

(d) decompressing the compressed block of information in response to a command from the event table, thereby obtaining output pixel data; and

(e) decoding the output pixel data.

18. The method of claim 17 and wherein the step of decompressing the non-temporal data and producing the output image further includes changing the output pixel data in response to a command from the event table.

19. A system for scheduling and processing non-temporal data and temporal data in a unified data stream, comprising:

(a) a scheduler, configured to interleave non-temporal data and temporal data to form a unified data stream, at least some of the non-temporal data being in an image compressed format and at least some of the temporal data being audio data in a temporal compressed format; and

(b) a processor that decompresses the non-temporal data in the non-temporal compressed format, produces an output image from at least some of the decompressed non-temporal data and uncompressed non-temporal data, if any, and concurrently plays the temporal audio data while decompressing the temporal audio data in the temporal compressed format by;

(1) searching for a breakpoint in an amount of the temporal audio data,

(2) if a breakpoint is found, playing the amount of the temporal audio data to the breakpoint,

(3) if no breakpoint is found, determining if the amount of temporal audio data is greater than a predetermined minimum amount of the temporal audio data, and

(4) if the amount of the temporal audio data is greater than the predetermined amount of the temporal audio data, playing the amount of the temporal audio data.

20. The system of claim 19 wherein the processor includes:

(a) an input buffer that receives at least some of the temporal audio data from the unified data stream;

(b) an element that decompresses the temporal audio data in the input buffer to obtain decompressed temporal audio data;

(c) an output buffer, receiving the decompressed temporal audio data;

(d) the input buffer receiving additional temporal audio data from the unified data stream;

(e) a player, playing the decompressed temporal audio data held in the output buffer while the additional temporal audio data is decoded.

21. The system of claim 20 wherein the processor is configured to:

(a) determine if the temporal audio data held in the output buffer is equal to or greater than the predetermined minimum amount of the temporal audio data, the predetermined minimum amount of temporal audio data known as a prestart backlog, or if an end of file ("EOF") flag is held in the output buffer, the EOF flag indicating the end of the temporal audio data contained in the unified data stream;

(b) if the prestart backlog or the EOF indication is in the output buffer, look for a breakpoint in the temporal audio data contained in the output buffer;

(c) if a breakpoint is found, play the temporal audio data in the output buffer until reaching the breakpoint;

(d) if no breakpoint is found, determine if the amount of temporal audio data in the output buffer is greater than maximum backlog, the maximum backlog representing a minimum amount of temporal audio data required to be in the output buffer for playing when no breakpoint is found; and

(e) if the amount of temporal audio data in the output buffer is greater than the maximum backlog, play the temporal audio data in the output buffer.

22. The system of claim 21 wherein the processor is further configured to:

(a) detect if a stall has occurred during playing of the temporal audio data; and

(b) if a stall condition has occurred, replace the maximum backlog with a restart backlog, the restart backlog increasing the amount of temporal audio data required to be in the output buffer for playing when no breakpoint is found.

23. The system of claim 19 wherein the scheduler is configured to:

(a) set a plurality of markers in the temporal data at various times in the unified data stream;

(b) check the unified data stream to determine a time when each of the plurality of markers is received by a player; and

(c) divide an actual playing time between selected markers by the time between receipt of the selected markers to determine a baud rate for the temporal data.

24. The system of claim 22 wherein the scheduler is further configured to:

(a) set the maximum backlog, the restart backlog, and the prestart backlog;

(b) insert the set maximum backlog, the set restart backlog, and the set prestart backlog into a startup header; and

(c) place the input header at the beginning of the unified data stream.

25. The system of claim 19 wherein at least a portion of the temporal audio data is a MIDI file, the MIDI file including a plurality of tracks, each track having a plurality of messages, each message including time data, and wherein the scheduler is configured to sort the MIDI file using the time data to group together messages to form a plurality of MIDI file portions, each MIDI file portion representing a specific time.

26. The system of claim 25 wherein the scheduler is further configured to:

(a) place each MIDI file portion into a respective audio segment in the unified data stream, each audio segment having a download time and a play time;

(b) place at least one image data segment between a first audio segment and a second audio segment;

(c) locate a backlog data gap after the end of the play time of the first audio segment and the end of the download time of the second audio segment; and

(d) locate at least one image data segment after the backlog data gap.

27. The system of claim 19 wherein the scheduler is configured to:

(a) divide the temporal audio data into a plurality of audio segments;

(b) plot a download time and a play time of a selected audio segment and a next audio segment to determine a latest possible start time ("st") for the next audio segment;

(c) place all the audio segments in a latest possible location within the unified data stream to form an initial map that includes the temporal audio data; and

(d) fit at least one segment of non-temporal data into any gaps that exist between adjacent audio segments in the initial map and that are sufficiently large to accommodate a segment of non-temporal data.

28. The system of claim 27 wherein the scheduler is further configured to:

(a) detect whether any overlaps exist between any adjacent audio segments or between any audio segment and any non-temporal segment or between any adjacent non-temporal segments; and

(b) if any such overlap is detected, move at least one audio segment to eliminate the overlap.

29. The system of claim 28 wherein the scheduler is further configured to:

(a) after eliminating any overlaps, determine if any adjacent audio segments can be placed next to one another without any gap between the adjacent audio segments; and

(b) relocate such non-gap audio segments to eliminate the gap in order to conserve space in a header located in the unified data stream.

30. The system of claim 29 wherein the scheduler is further configured to eliminate any gaps between adjacent audio and non-temporal segments.

31. The system of claim 19 wherein the non-temporal data includes image data, the method further comprising:

(a) an transmission element that allows sending of a low resolution version of the image data in the unified data stream before sending additional resolution of the image data;

(b) a display, displaying the low resolution version; and

(c) the transmission element sending the additional resolution of the image data after the low resolution version is displayed.

32. The system of claim 31 wherein the transmission element sends temporal data while the low resolution version of the image data is being sent and displayed.

33. The system of claim 19 wherein the temporal data includes video data, and wherein the processor is configured to:

(a) separate the video data into a plurality of data blocks including a set of commands and a set of compressed data;

(b) form an event table from the set of commands, the event table having a plurality of entries, each entry having a time and a list of events that occur at the time;

(c) store a block of compressed information from the set of compressed data;

(d) decompress the compressed block of information in response to a command from the event table, thereby obtaining output pixel data; and

(e) decode the output pixel data.

34. The system of claim 33 wherein the processor is further configured to change the output pixel data in response to a command from the event table.

41. The system of claim 26 wherein the scheduler is further configured to:

(a) split an audio segment at a breakpoint in the audio segment to form a first split audio segment and a second split audio segment; and

(b) locate at least one non-temporal segment between the first split audio segment and the second split audio segment.

35. A method for determining a baud rate for temporal data in a unified data stream that includes temporal and non-temporal data, the method comprising:

(a) interleaving temporal data and non-temporal data to form the unified data stream;

(a) setting a plurality of markers in the temporal data at various times in the unified data stream;

(b) checking the unified data stream to determine a time when each of the plurality of markers is received by a player; and

(c) dividing an actual playing time between selected markers by the time between receipt of the selected markers to determine a baud rate for the temporal data.

36. A method for reducing stalls in images displayed in a computer animated slide-show, comprising:

(a) interleaving temporal data and non-temporal data to create a computer slide-show embodied in a unified data stream, the unified data stream including a plurality of image packets and a plurality of non-temporal data packets;

(b) assigning a playtime to each of the image packets;

(c) sorting the image packets by playtime;

(c) sequentially sorting the image packets that are assigned the same playtime;

(d) calculating a download time for each image packet;

(e) locating a latest image packet having a download time that is completed the longest time after the playtime for that image data;

(f) calculating a data gap, the data gap being the difference between the download time and the playtime of the latest image packet; and

(g) playing the unified data stream only when an amount of data from the unified data stream that is at least a great as the data gap has been received.

37. A method for scheduling and processing a computer slide-show, the slide-show including image data and audio data in a unified data stream, the method comprising:

(a) interleaving image data, audio data, and command data to form a slide-show embodied in a unified data stream; and

(b) processing the unified data stream, including;

(1) separating the image data, the audio data, and the command data,

(2) generating a plurality of time-event commands from the command data, each time-event command including a time indicator and an event of the slide-show that occurs at the time corresponding to the time indicator,

(3) separating the image data into a plurality of image elements, each element including at least one image data packet, each image data packet having a corresponding time-event command,

(4) separating the audio data into a plurality of sound elements, each element including at least one audio data packet, each audio data packet having a corresponding time-event command,

(5) decoding each of the image data packets in response to the corresponding time-event command, and

(6) decoding each of the audio data packets in response to the corresponding time-event command.

38. The method of claim 37 wherein the processing step further includes:

(a) image processing each of the image data packets in response to a corresponding time-event command, if any; and

(b) audio processing each of the audio data packets in response to a corresponding time-event command, if any.

39. The method of claim 38 wherein the processing step further includes:

(a) storing at least one of the decoded image packets so that the stored image packet can be processed at essentially any time,

(b) storing at least one of the decoded audio packets so that the stored audio packet can be processed at essentially any time.

40. The method of claim 38, further comprising concurrently performing steps (1) through (6) of the processing step.

42. The method of claim 38 wherein the step of separating the image data, the audio data, and the command data includes programmably controlling separation of the image data, the audio data, and the command data by an author command.

43. The method of claim 38 wherein the processing step further includes the step of progressively displaying the decoded image data packets so that an image formed by the image data packets is rendered over time in progressively greater resolution until the image is essentially completely displayed.

44. The method of claim 38 wherein the processing step further includes the steps of separating the image data packets into a plurality of image asset groups and processing each of the plurality of image asset groups by a corresponding image asset processor.

45. A method for scheduling and processing temporal data and non-temporal data in a unified data stream, comprising:

(a) interleaving temporal data and non-temporal data to form a unified data stream, at least some of the temporal data being a MIDI audio file in a temporal compressed format, at least some of the non-temporal data being in a non-temporal compressed format, the MIDI audio file including at least one track having a plurality of messages, each message including time data;

(b) sorting the MIDI audio file using the time data to group together messages to form a plurality of MIDI audio file portions, each MIDI audio file portion representing a specific time; and

(c) processing the unified data stream, including;

(1) decompressing the non-temporal data in the non-temporal compressed format and producing an output image from at least some of the decompressed non-temporal data and any uncompressed non-temporal data, and

(2) concurrently playing and decompressing the sorted MIDI audio file in the temporal compressed format.

46. The method of claim 45, further comprising:

(a) placing each MIDI audio file portion into a respective audio segment in the unified data stream, each audio segment having a download time and a play time;

(b) placing at least one non-temporal data segment between a first audio segment and a second audio segment;

(c) locating a backlog data gap after the end of the play time of the first audio segment and the end of the download time of the second audio segment; and

(d) locating at least one non-temporal data segment after the backlog data gap.

47. The method of claim 46, further comprising:

(a) splitting an audio segment at a breakpoint in the audio segment to form a first split audio segment and a second split audio segment; and

(b) locating at least one non-temporal segment between the first split audio segment and the second split audio segment.

48. A method for transmitting data over a limited bandwidth channel, comprising:

(a) receiving a sequence of temporal audio data to be encoded;

(b) determining a shortage of audio data that could lead to a possible system stall on the limited bandwidth channel;

(c) using the determined shortage of sound data to analyze the sequence of temporal audio data to detect a stall condition in the temporal audio data; and

(d) if a stall condition is detected, finding a breakpoint in the sequence of temporal audio data and stopping transmission of the sequence of temporal audio data at the breakpoint.