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

What is claimed is:

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.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to the provision of video programming on-demand, and more particularly to a method and apparatus that encodes, formats, stores and retrieves data representing a video program as a plurality of concurrent, overlapping presentations of the video program to facilitate virtual on-demand access to a single copy of the video program by virtually any number of subscribing viewers.

2. Description of the Related Art

People in the United States spend roughly $7.5 billion annually to rent movies and other pre-recorded video programming for private playback at their convenience. Such video programming can be rented in many forms, such as video cassette tapes for playback using a video cassette recorder (VCR), video disks for playback on video disk players, or as CD ROM's for playback using personal computers and other forms of CD ROM players.

Renting video programming in this manner is desirable because it permits the user to view the programming at any time and in any manner. For example, the user may view some portion of the program at one time and the remainder of the program at some different time. Further, the user may replay certain portions of the program or view the program in its entirety several times. The user may access the program from any point in the program by simply fast-forwarding or reversing through the program. The user is thereby freed from the constraints of available network or cable television programming.

Cable television and direct broadcast satellite (DBS) companies would like to compete in this arena by providing users with the same freedom of use enjoyed through video rental. This service would be known as "video-on-demand." Such companies would clearly enjoy an advantage over video rental establishments in providing such a service because users would not be required to leave the comfort of their own homes to rent a copy of the video program (nor would they have to return it when finished). These companies have been heretofore constrained, however, by existing playback and distribution technology.

It would be prohibitively expensive for a cable television company to provide true video-on-demand using currently known technology. To duplicate the advantages of video rental and in-home playback, the company would have to provide a dedicated playback resource to each cable subscriber, along with an expensive memory array containing a library of video programs from which the subscriber could select programs for playback through the dedicated resource. Further, the cable distribution infrastructure would be required to have sufficient bandwidth to distribute a different video program, or at least a different playback of a video program, to each subscriber connected to the network. Of course this would be impossible without a leap in technology and replacement of the current distribution infrastructure.

One possible compromise would be to produce multiple, overlapping playbacks (i.e. presentations) of the same video program, such that a new presentation of the program would begin, for example, every five minutes. For a two hour video program, a total of twenty-four overlapping presentations of the program would be made available to subscribers. Each subscriber would then have a receiver capable of selectively receiving any one of the twenty-four presentations. Although a subscriber would not enjoy full video-on-demand, the subscriber would have to wait at most five minutes to begin viewing the program in its entirety (or to access any point within the program). Further, the subscriber could fast-forward or reverse through the program by accessing a different one of the overlapping presentations, although he would be constrained to do so over the five minute intervals.

Although such a compromise would decrease both the requisite number of playback resources and the necessary bandwidth, the costs of implementing such a system in currently known technology would still be prohibitive. For the above example, twenty-four playback resources would be required to produce twenty-four separate presentations, each being transmitted over one of a limited number of channels comprising the distribution medium. Further, without sophisticated server technology, such a system might require twenty-four separate copies of the program.

Complex disk-drive arrays or video servers have been recently proposed, each having thousands of video programs stored in their memory and each capable of serving up to two hundred subscribers. The cost of implementing a video-on-demand system for the 57 million current cable subscribers, assuming that such advanced technology could be implemented, would still require an estimated $20 billion in capital investments (about $350.00 per subscriber). Further, full implementation of a service based on such proposed server technology would require that the current cable and telephone distribution network infrastructure be restructured and upgraded over the next several years at a cost of an additional $2 billion per year to increase its bandwidth. Implementing VCR-like functions, such as fast-forward and reverse, would not only increase the complexity of the servers, but it would also impinge on available bandwidth because each subscriber must be able to communicate commands back to his or her dedicated server. Such "back channels" are not even available in the context of existing DBS systems, and most existing cable distribution systems.

The best service that cable television and DBS companies have been able to offer thus far is a pay-perview service that permits users to request (either over the telephone or directly through the cable network) an offered video program for a fee. The company then permits the subscriber to receive the selected transmission of the video program. These services are far from video-on-demand, however, as the number of available programs and the number of starting times for the programs are severely limited. Thus, the subscriber must still wait for a scheduled start time at which a desired program will be transmitted over the distribution network. Further, the subscriber does not have the freedom provided by an in-home playback resource such as a VCR; the program is still just passively received.

Thus, there is a need in the art for technology that can provide virtually an unlimited number of viewers with virtually random access to as few as one copy of a video program through as few as one playback resource and that is operable with the existing telephone and cable distribution infrastructure.

SUMMARY OF THE INVENTION

The present invention provides a method and apparatus for encoding and formatting data representing a single presentation of a video program for storage and for transmission that simulates multiple overlapping presentations of the video program using a single playback resource. Put another way, the video program is transmitted as a digital data stream that has been formatted in such a way that it appears to a subscriber that a number of segments of the same program are being continuously distributed over a plurality of subchannels concurrently. By selecting successive segments for presentation over the receiver (e.g. by advancing the subchannel to which the receiver is tuned), an entire presentation of the video program can be assembled. Further, the subscriber can fast-forward or reverse through the program by advancing or decrementing the selected subchannel and thus receive a later or earlier segment of the program.

Thus, a one-hour program formatted in accordance with the present invention could be made to simulate, for example, twenty overlapping presentations of the program with each presentation (i.e. program segment) being three minutes ahead of the previous one. A subscriber would have to wait only a maximum of three minutes to begin receiving the program in its entirety (i.e. until the segments begin again), and would be able to fast forward or reverse through the program at three-minute intervals. Thus, the maximum delay that a subscriber would have to experience to randomly access any point in the program (i.e. the access time) would be three minutes. The present invention resides in its ability to provide this functionality with a single playback resource producing a single formatted data stream that represents a single presentation of the video program.

It is well-known in the art that a video program can be converted to a digital data stream for purposes of transmitting the program over a digital distribution medium to subscribers. Video programs are typically organized as a series of scenes or frames, each frame comprising a two-dimensional array of picture elements or pixels. Each pixel has characteristics such as color and brightness which can be quantified as binary data. Audio information associated with the video program can also be converted to a binary representation. In accordance with the present invention, the image and audio portions of a video program are converted to digital data streams using known techniques and standards.

It is also well-known that much of the information contained in a video program is redundant (i.e. pixels in certain regions of the pixel matrix may not change over considerable numbers of frames). Further, areas where changes occur rapidly can often tolerate artifacts that result from truncation of data representing pixel characteristics. Accordingly, the binary data generated to represent a video program can often be compressed considerably, thereby minimizing requisite memory storage and transmission bandwidth. Thus, the video data streams are preferably compressed (i.e encoded) using any known video data compression technique to produce compressed video data streams. The binary data comprising these data streams (both before and after compression) are grouped into arbitrary units called elements; an element can refer to one or more bits of video data where video data refers to all data required to represent a video program, compressed or not, and including but not limited to image, audio and other associated information.

The video data streams (compressed or not) are partitioned into n subsequences of elements representing segments of the video program, with each segment comprising an ordered sequence of m elements. The ordered sequence of elements making up each subsequence are interleaved to produce a single interleaved data stream that preferably begins with the first element of each of the n segments, then the second element of each segment and so on in segment order until it ends with the m'th element of the n'th segment. This interleaved data stream is continuously transmitted over the distribution medium from beginning to end.

A subscriber with an appropriate receiver can reconstruct the entire program, starting when the transmission is at the beginning of the interleaved data stream, by sequentially selecting and assembling the m elements of the first segment as the receiver serially parses through the interleaved data stream. The receiver reconverts the selected and assembled elements back into image and/or audio in real time for presentation of the first segment to the subscriber. As transmission of the interleaved data stream begins again, the receiver selects and assembles all of the elements of the second segment for reconstruction, and repeats this process until it completes its n'th pass through the data stream to select and assemble the m elements comprising the n'th segment. The receiver continuously decompresses (i.e. decodes) and reconverts the assembled segments in real time to reconstruct the video program in segment order for viewing by the subscriber.

As long as the rate of transmission of the interleaved data stream is at least "n" times the average data rate "r" of the individual segments, the system will operate properly. Thus, for a given value of r, the throughput of the resource used to transmit the interleaved data stream defines the number of possible segments into which the program may be divided. The viewing time of one of the n segments defines the access time "T" of the system, which is the minimum time interval between accessible points in the program. Further, the time necessary to transmit the entire interleaved data stream once must be less than or equal to T.

Thus, a subscriber receives access to an ordered sequence of n segments of the video program concurrently over n subchannels, which means any number of subscribers can be concurrently reconstructing n overlapping presentations of the video program, each presentation running ahead of its predecessor by an amount of time T required to reconstruct one video segment. The formatting of the data stream representing the video program operates analogously to the process of time-division multiplexing information received from a plurality of communications channels. In the context of communications, however, each channel carries a different conversation or program, whereas the present invention exploits similar principles to break up and transmit a single program over separate subchannels of the same channel. It is this unique application of TDM principles to the context of video-on-demand which forms the basis for the instant invention.

An alternate preferred embodiment of the invention adapts the idea of statistical encoding to the interleaving process so that video segments that require more data to maintain desired picture quality are allocated more data while other segments of the program requiring less data are allocated less data such that the overall allocated bandwidth remains the same. In this embodiment, the video data streams are partitioned into subsequences representative of the segments first and then each subsequence is compressed and interleaved through a statistical multiplexer. This embodiment, although more complex in implementation, provides more uniform picture quality throughout the program.

In the preferred embodiment of the invention, the compression and interleaving processes are performed interactively through a combination of software and hardware, a