Method and apparatus for encoding and formatting data representing a video program to provide multiple overlapping presentations of the video program

• US 5,612,742 A
• Filed: 10/19/1994
• Issued: 03/18/1997
• Est. Priority Date: 10/19/1994
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Imedia Corp. (Motorola Solutions, Inc.)
• Inventors: Shen, Paul, Krause, Edward A., Tom, Adam S.
• Primary Examiner(s): Kostak, Victor R.
• Application Number:
  US08/326,511
• Time in Patent Office: 881 Days
• Field of Search: 348/385, 348/387, 348/388, 348/409, 348/426, 348/469
• US Class Current: 375/240.25
• CPC Class Codes: H04N 21/2315 using interleaving
• CPC Class Codes: H04N 21/23614 Multiplexing of additional data and video streams arrangements for simultaneous broadcast of plural pieces of information H04H20/28
• CPC Class Codes: H04N 21/23655 Statistical multiplexing, e.g. by controlling the encoder to alter its bitrate to optimize the bandwidth utilization
• CPC Class Codes: H04N 21/4347 Demultiplexing of several video streams
• CPC Class Codes: H04N 21/4348 Demultiplexing of additional data and video streams
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

Virtually random and on-demand access is provided to a virtually unlimited number of subscribers by partitioning the video program into an ordered sequence of n segments and providing the subscribers concurrent access to each of the n subsequences. A data stream representative of the video program is partitioned into n subsequences, each representative of one of the n segments. The data of each of the n subsequences is organized as an ordered sequence of elements. The elements of each of the n subsequences are interleaved and the interleaved data stream is continuously transmitted over a video program distribution medium at a rate which renders the data representing each segment concurrently available to any subscriber having a receiver capable of selecting, assembling, and displaying the data of a particular segment. The data stream can be compressed prior to interleaving using one of many known video data compression standards and techniques. Data compression can be performed in real time, or iteratively using software. The interleaved data stream can be transmitted in real time, or it can be stored on a storage device such as a hard disk or optical disk for later retrieval and transmission. The interleaved data stream can be ordered using any known standard by which video data is transmitted for reconstruction and display by a receiver. Data can be inserted into the interleaved data stream to inform the receiver to which of the n segments a portion of the interleaved data stream belongs, as well as the encoding level necessary for decompression of the data and time stamps to indicate order of display.

Claims

1. A method of providing concurrent access to an ordered sequence of a plurality of n segments wherein each of the n segments corresponds to a different temporal portion of the same video program, said method comprising the steps of:

partitioning a data stream comprising an ordered sequence of data representative of the video program into n subsequences, each of the n subsequences comprising a portion of the data stream representative of one of the n segments, the data of each of the n subsequences organized as an ordered sequence of elements, at least two of the elements in at least one of the subsequences corresponding to different temporal portions of the video program; and

interleaving the elements of the n subsequences to produce an interleaved data stream.

2. The method of claim 1 comprising the additional step of compressing the video program, and wherein the elements of each of the n subsequences comprise compressed data.

3. The method of claim 2 wherein said interleaving step is performed by sorting the elements of the n subsequences according to the order in which they would be decoded by respective receivers.

4. The method of claim 3 wherein the ordered sequence of elements of each of the n subsequences comprises a plurality of m elements.

5. The method of claim 4 wherein each of the m elements comprises an equal amount of compressed data.

6. The method of claim 5 wherein said interleaving step further comprises the step of grouping the first elements of each of the n subsequences together in segment order, then likewise grouping the second through mth elements of each of the n subsequences.

7. The method of claim 1, 3 or 6 further comprising the step of repeatedly transmitting the interleaved data stream over a video program distribution medium for a predetermined period of time.

8. The method of claim 1, 3 or 6 further comprising the step of storing the interleaved data stream on a storage device.

9. The method of claim 8 further comprising the steps of:

retrieving the interleaved data stream from the storage device;

transmitting the retrieved interleaved data stream over a video program distribution medium; and

repeating said retrieving and transmitting steps continuously for a predetermined period of time.

10. The method of claim 9 wherein a receiver must receive the ordered sequence of elements of one of the n subsequences at a rate r to present the segment represented by the one of the n subsequences to a viewer in real time without interruption, and wherein said step of transmitting the interleaved data stream is performed at rate equal to or greater than the product of n and r.

11. The method of claim 7 wherein a receiver must receive the ordered sequence of elements of one of the n subsequences at a rate r to present the segment represented by the one of the n subsequences to a viewer in real time without interruption, and wherein said step of repeatedly transmitting is performed at rate equal to or greater than the product of n and r.

12. The method of claim 9 further comprising the steps of:

assigning a unique segment identification number to each of the n subsequences; and

inserting data representative of the unique segment identification numbers into the retrieved interleaved data stream to identify to which of the n subsequences each of the elements belongs.

13. The method of claim 12 wherein the unique segment identification numbers are sequentially increasing with the sequence order of the segments comprising the video program.

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

for each retrieval and transmission of the interleaved data stream, inserting a flag to denote the one of n subsequences representative of the first segment of the video program; and

decrementing the currently assigned segment identification numbers for each of the n subsequences upon completion of each retrieval and transmission of the interleaved data stream.

15. The method of claim 2 wherein said step of compressing the data stream is performed statistically.

16. The method of claim 15 wherein said step of statistically compressing further comprises the step of encoding each of the n subsequences in accordance with a specified error tolerance to produce n encoded subsequences of elements.

17. The method of claim 16 wherein said step of statistically compressing further comprises the steps of:

summing the amount of data in the compressed and interleaved sequence of elements during a fixed time interval;

increasing the specified error tolerance whenever the summed data exceeds a first predetermined throughput; and

decreasing the specified error tolerance whenever the summed data falls below a second predetermined throughput.

18. The method of claim 17 wherein said step of encoding each of the n subsequences is performed on each of the n subsequences concurrently and wherein each of the n encoded subsequences of elements are produced synchronously.

19. The method of claim 18 wherein said interleaving step, said summing step and said steps of increasing and decreasing the error tolerance are performed in real time on said n encoded subsequences of elements.

20. The method of claim 16 wherein said step of statistically compressing further includes the steps of:

summing the amount of data in the compressed and interleaved sequence of elements during a fixed time interval;

increasing the specified error tolerance of one or more elements within the fixed time interval during which the sum of data exceeds a first predetermined throughput;

decreasing the specified error tolerance of one or more elements within the fixed time interval during which the sum of data falls below a second predetermined throughput; and

repeating said steps of encoding, interleaving, summing, increasing the specified error tolerance and decreasing the specified error tolerance until no further increases or decreases in the specified error tolerance are required.

21. The method of claim 1, 3, 5, 13, wherein the step of interleaving further comprises the steps of:

assigning a unique segment identification number to each of the n subsequences; and

inserting data representative of the unique segment identification numbers into the interleaved data stream to identify to which of the n subsequences each of the elements belongs.

22. The method of claim 2 further comprising the steps of:

partitioning the interleaved data stream into two or more portions, each of the portions comprising compressed data representative of an equal number of pixels; and

storing each of the two or more portions on a different storage device.

23. The method of claim 2 further comprising the steps of:

partitioning the interleaved data stream into two or more portions, each of the portions comprising the same amount of data;

storing each of the two or more portions on a different storage device; and

whenever the two or more portions cannot have an equal amount of data, adding filler data to one or more of the two or more portions to render the two or more portions equal in amount of data.

24. The method of claim 22 further comprising the steps of:

concurrently retrieving the two or more portions from the two or more storage devices;

transmitting each of the concurrently retrieved two or more portions simultaneously over separate channels of a video distribution medium; and

repeating said concurrently retrieving and said transmitting steps continuously for a predetermined time.

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

concurrently retrieving the two or more portions from the two or more storage devices;

transmitting each of the concurrently retrieved two or more portions simultaneously over separate channels of a video distribution medium; and

repeating said concurrently retrieving and said transmitting steps continuously for a predetermined time.

26. A method of providing concurrent access to an ordered sequence of a plurality of n segments comprising a video program, said method comprising the steps of:

partitioning a data stream comprising an ordered sequence of data representative of the video program into n subsequences, each of the n subsequences comprising a portion of the data stream representative of one of the n segments, the data of each of the n subsequences organized as an ordered sequence of elements wherein at least two of the elements in at least one of the subsequences correspond to at least part of different frames of the video program; and

interleaving the elements of the n subsequences to produce an interleaved data stream.