Method and apparatus implementing random access and time-based functions on a continuous stream of formatted digital data

• US 6,327,418 B1
• Filed: 04/03/1998
• Issued: 12/04/2001
• Est. Priority Date: 10/10/1997
• Status: Expired due to Term

• Current Assignee: TiVo Solutions Inc. (Adeia Inc.)
• Original Assignee: TiVo Inc. (Adeia Inc.)
• Inventors: Barton, James M.
• Primary Examiner(s): Chevalier, Robert
• Application Number:
  US09/054,604
• Time in Patent Office: 1,341 Days
• Field of Search: H04/N.57613, H04/N.57617, 386/46, 386/83, 386/92, 386/109, 386/111, 386/112, 386/1, 386/52, 386/4, 386/68, 386/69, 360/32, 348/7, 348/12, 725/86, 725/87, 725/88, 725/101, 725/102
• US Class Current: 386/201
• CPC Class Codes: H04N 21/4331 Caching operations, e.g. of an advertisement for later insertion during playback
• CPC Class Codes: H04N 21/4334 Recording operations recording of a television signal H04N5/76; arrangements for recording or accumulating broadcast information or broadcast-related information H04H60/27
• CPC Class Codes: H04N 21/47202 for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 5/783 Adaptations for reproducing at a rate different from the recording rate

Abstract

A continuous stream of formatted digital data, such as a video segment, audio segment, or information stream, appears to be a fixed length segment under certain circumstances, defining a virtual segment within the continuous stream which moves forward in time in synchrony with the continuous stream. The virtual segment thus defined can be explored in a non-linear fashion at arbitrary playback rates. For instance, concepts such as rewind, pause, frame advance, and fast forward become meaningful even though the continuous stream never ceases.

Claims

1. A method for providing pass through or capture of continuous linear streams of digital information represented in various formats while providing the appearance of a locally stored stream, comprising the steps of:

providing at least one media cache for copying blocks of data from said information stream, wherein data in said media cache can be viewed as a snapshot of said continuous stream of digital information;

providing a playback pointer, wherein a playback pointer position selects a portion of said media cache that is to be accessed to provide functions including any of pause, rewind, fast forward, play, play faster, play slower, and play in reverse;

providing a stream clock;

providing a buffer controller that is responsible for controlling a clock rate of said stream clock;

wherein the rate at which said stream clock delivers clock events to said media cache is based on a rate specified by said buffer controller; and

wherein said buffer controller can speed up or slow down playback of a stream or an entire collection of streams by requesting said stream clock to adjust its clock rate.

2. The method of claim 1, wherein said underlying information stream is composed of a plurality of discrete blocks of data.

3. The method of claim 1, further comprising the step of:

providing a buffer controller that accepts external requests for operations on said information stream and that, in turn, generates appropriate control messages.

4. The method of claim 1, wherein said stream clock synchronizes operations on said more than one media cache, wherein multiple streams of data which must be presented in a synchronized fashion are correctly positioned, and wherein said multiple streams of data present their data at consistent delivery rates.

5. The method of claim 1, further comprising the step of:

providing a clip capture module for capturing all or part of a cached set of information streams and presenting resulting data as an organized stream of data to a data sink.

6. The method of claim 3, wherein said buffer controller instantiates methods that provide for system operation in connection with any particular stream of information.

7. The method of claim 4, further comprising the step of:

designating one of said multiple streams as a key stream;

wherein all positioning of playback from each media cache is based on first positioning said key stream, and then using a final position of that stream to position all other streams properly.

8. The method of claim 7, wherein said key stream is an MPEG video stream;

wherein positioning is based on aligning a current block pointer to the beginning of an MPEG Group Of Pictures; and

wherein said buffer controller repositions all other streams to be synchronized with said key stream once said key stream is positioned.

9. The method of claim 1, wherein said stream clock provides a central synchronization facility that distributes time based events to a number of media caches.

10. The method of claim 9, wherein events are queued with a relative offset from a previously queued event;

wherein a first event in said queue is marked with a time which is an offset from a current time;

wherein said stream clock requests that an underlying operating system invoke a call out when that amount of time has passed; and

wherein said stream clock dispatches a first clock event and then each succeeding event whose offset is zero when said call out is invoked.

11. The method of claim 10, wherein each event in said queue is marked with a time interval and the absolute time of said data stream that a next event should occur;

wherein the absolute time of a next event is composed by adding the time interval to the previous absolute time after a queued event is dispatched, such that the difference between this time and a current absolute time determines the delay before this event should be repeated;

wherein said event is then added to said queue at an appropriate position for the event'"'"'s next occurrence; and

wherein said stream clock queues a new timer event at the offset to the first waiting event after all events with a offset of zero have been processed, after which the above process steps are repeated.

12. The method of claim 1, wherein said stream clock records a rate multiplier value, which is initially set to one, when said stream clock is initially created;

wherein the actual time delay requested is multiplied by said rate multiplier whenever said stream clock requests an underlying operating system to queue a timer event; and

wherein a rate multiplier greater than one results in faster playback of said stream, and a rate multiplier of less than one results in a slower playback of said stream.

13. The method of claim 1, wherein said media cache maintains sad stream as a list of the digital blocks that make up said stream, and assumes that each block in said steam has a unique size and attributes.

14. The method of claim 13, wherein each block within said stream is marked with a Presentation Time Stamp (PTS) which indicates when that block should be presented to a decoding process;

and

wherein said PTS is a monotonically increasing value initialized to zero when said media cache first begins operation on a stream and is not related to any time stamps defined by an underlying stream encoding technique, except that there is a constant offset between said PTS stored in said media cache and any time stamps stored within said encoded digital blocks once said media cache begins operation.

15. The method of claim 14, wherein a capture mechanism for a particular stream type gives each encoded digital block to said media cache as it arrives;

wherein said media cache marks said block with a current PTS for said stream;

wherein said media cache maintains a window which is the maximum time, based on PTS values, between the time when a newest block in said media cache has arrived and an oldest block which said media cache may hold, such that said window represents a time-span into a past history of said stream; and

wherein said media cache discards blocks which fall outside said window, such that said window allows one to look a fixed distance into said past history of said stream.

16. The method of claim 13, wherein a capture mechanism is responsible for providing certain attributes along with each new block;

and

wherein said attributes include any of a key frame attribute which indicates that said block begins a sequence of inter-related blocks such that said media cache only allows positioning of said stream to a block marked as a key frame when performing random access operations on said stream; and

an End Of Segment (EOS) attribute which indicates that said stream has ended and that no more data are to be presented.

17. The method of claim 13, wherein said media cache maintains an indication of a next block to be presented to a decoding process;

and

wherein said block is a block last added to said media cache by a capture mechanism, such that said stream is presented live with at most a one-frame time delay between capture and presentation.

18. The method of claim 13, wherein random access to said stream is achieved by moving a current block indicator to another block in said media cache;

and

wherein said media cache instructs a decoding process to reset its decoding state, thus purging any partially constructed presentation data, if said media cache is requested to move said block indicator, and a current block indicated is not a key frame.

19. The method of claim 13, further comprising the step of:

providing a buffer controller that requests repositioning of a media cache by specifying a PTS value;

wherein said media cache finds a block containing a PTS which is closest to that requested by said buffer controller.

20. The method of claim 19, wherein said media cache scans blocks of data in said media cache to find a key frame which is nearest to a requested PTS value, searching both before and after a desired value, if said media cache is marked as a key stream, wherein said media cache returns PTS of said key frame block which was identified to said buffer controller, once said media cache is properly positioned;

instructing each remaining stream to position itself to said PTS returned by said key stream, wherein key frames in other media caches may not align with those in said key stream, in which event each media cache requests a decoding process to purge any decoding state, and then stores an indication that suppresses each other media cache from actually presenting blocks to said decoding process;

said media cache accepting clock events and advancing a current block indicator to match, except that said blocks are not actually presented to said decoding process; and

deleting an indication suppressing presentation of blocks; and

presenting a current block to said decoding process when said media cache encounters a key frame.

21. The method of claim 1, wherein a forward/reverse function is implemented by moving a current block indicator forward/reverse through said media cache by one block for each event generated by a stream clock;

wherein each successive block in said media cache is given to an optional decoding process for presentation as clock events are dispatched by said stream clock;

wherein a rate multiplier causes a current block indicator to move forward/reverse within said media cache at a selected rate as new blocks are added to said media cache by a capture process, resulting in play out at a fixed delay from real time.

22. The method of claim 21, wherein said media cache reverts to a key frame based method in which intermediate blocks are skipped and only key frames are presented to said decoder if said decoder can not keep up with a playback rate requested.

23. The method of claim 21, wherein a buffer controller resets said stream clock rate multiplier to one, and each media cache positions a current block indicator to a latest cached block if said current block indicator moves to a front of said media cache where no more blocks are present in said media cache.

24. The method of claim 21, wherein said current block indicator is set to an earliest block in said media cache if a clock event would result in moving a current block indicator past said earliest block;

and

wherein play out thereafter continues said that it appears as if said stream is playing in a forward direction again.

25. The method of claim 1, further comprising the step of:

providing a buffer controller for implementing a pause function by locking a current block indicator in a key stream media cache to a key frame block nearest a currently indicated block;

searching forward for said key frame block in said media cache if said current block is not a key frame block;

storing an indication that a lock has been requested if no key frame is present; and

locking said current block indicator to a key frame when a capture process presents a key frame.

26. The method of claim 25, wherein said indicator is unlocked and left pointing at an earliest block in said media cache if a stream window moves past a block to which said indicator is locked, thereby providing automatic release of said pause.

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

extracting a range of blocks from said media cache in either of a relative mode and an absolute mode by returning a pointer to a cached block plus a count of the number of blocks that make up an extract range; and

providing an indicator in said media cache that suppresses discarding blocks within said extract which fall outside a window.

28. The method of claim 27, wherein said relative mode specifies a clip to be captured as two numbers, wherein a first number represents an offset from said current block indicator into previous blocks in said media cache, and a second number represents an offset from said current block indicator into subsequent blocks in said media cache.

29. The method of claim 27, wherein said absolute mode specifies a clip to be captured as two numbers, wherein a first number represents an absolute time stamp based on when said media cache began operation, and a second number represents a time offset from that value, which may be a negative offset that indicates a distance backwards in said media cache or a positive value that indicates distance forwards in said media cache.

30. The method of claim 1, further comprising the step of:

providing a clip capture module for selecting ranges of blocks from a set of media caches, bringing said blocks together into an appropriate storage or transmission format, and saving or sending said blocks as needed.

31. The method of claim 30, wherein a buffer controller indicates that capture should occur based on a current block indicator in a key stream media cache.

32. The method of claim 30, wherein a buffer controller indicates an absolute range in which only blocks marked with a presentation time stamp (PTS) inclusive in that range are captured.

33. An apparatus for providing pass through or capture of continuous linear streams of digital information represented in various formats while providing the appearance of a locally stored stream, comprising:

at least one media cache for copying blocks of data from said information stream, wherein data in said media cache can be viewed as a snapshot of said continuous stream of digital information; and

a playback pointer, wherein a playback pointer position selects a portion of said media cache that is to be accessed to provide functions including any of pause, rewind, fast forward, play, play faster, play slower, and play in reverse;

providing a stream clock;

a buffer controller that is responsible for controlling a clock rate of said stream clock;

wherein the rate at which said stream clock delivers clock events to said media cache is based on a rate specified by said buffer controller; and

wherein said buffer controller can speed up or slow down playback of a stream or an entire collection of streams by requesting said stream clock to adjust its clock rate.

34. The apparatus of claim 33, wherein said underlying information stream is composed of a plurality of discrete blocks of data.

35. The apparatus of claim 33, further comprising:

a buffer controller that accepts external requests for operations on said information stream and that, in turn, generates appropriate control messages.

36. The apparatus of claim 33, wherein said stream clock synchronizes operations on said more than one media cache, wherein multiple streams of data which must be presented in a synchronized fashion are correctly positioned, and wherein said multiple streams of data present their data at consistent delivery rates.

37. The apparatus of claim 33, further comprising:

a clip capture module for capturing all or part of a cached set of information streams and presenting resulting data as an organized stream of data to a data sink.

38. The apparatus of claim 35, wherein said buffer controller instantiates methods that provide for system operation in connection with any particular stream of information.

39. The apparatus of claim 36, further comprising:

a key stream;

wherein all positioning of playback from each media cache is based on first positioning said key stream, and then using a final position of that stream to position all other streams properly.

40. The apparatus of claim 39, wherein said key stream is an MPEG video stream;

wherein positioning is based on aligning a current block pointer to the beginning of an MPEG Group Of Pictures; and

wherein said buffer controller repositions all other streams to be synchronized with said key stream once said key stream is positioned.

41. The apparatus of claim 33, wherein said stream clock provides a central synchronization facility that distributes time based events to a number of media caches.

42. The apparatus of claim 41, wherein events are queued with a relative offset from a previously queued event;

wherein a first event in said queue is marked with a time which is an offset from a current time;

wherein said stream clock requests that an underlying operating system invoke a call out when that amount of time has passed; and

wherein said stream clock dispatches a first clock event and then each succeeding event whose offset is zero when said call out is invoked.

43. The apparatus of claim 42, wherein each event in said queue is marked with a time interval and the absolute time of said data stream that a next event should occur;

wherein the absolute time of a next event is composed by adding the time interval to the previous absolute time after a queued event is dispatched, such that the difference between this time and a current absolute time determines the delay before this event should be repeated;

wherein said event is then added to said queue at an appropriate position for the event'"'"'s next occurrence; and

wherein said stream clock queues a new timer event at the offset to the first waiting event after all events with a offset of zero have been processed, after which the above process steps are repeated.

44. The apparatus of claim 33, wherein said stream clock records a rate multiplier value, which is initially set to one, when said stream clock is initially created;

wherein the actual time delay requested is multiplied by said rate multiplier whenever said stream clock requests an underlying operating system to queue a timer event; and

wherein a rate multiplier greater than one results in faster playback of said stream, and a rate multiplier of less than one results in a slower playback of said stream.

45. The apparatus of claim 33, wherein said media cache maintains said stream as a list of the digital blocks that make up said stream, and assumes that each block in said steam has a unique size and attributes.

46. The apparatus of claim 45, wherein each block within said stream is marked with a Presentation Time Stamp (PTS) which indicates when that block should be presented to a decoding process;

and

wherein said PTS is a monotonically increasing value initialized to zero when said media cache first begins operation on a stream and is not related to any time stamps defined by an underlying stream encoding technique, except that there is a constant offset between said PTS stored in said media cache and any time stamps stored within said encoded digital blocks once said media cache begins operation.

47. The apparatus of claim 46, wherein a capture mechanism for a particular stream type gives each encoded digital block to said media cache as it arrives;

wherein said media cache marks said block with a current PTS for said stream;

wherein said media cache maintains a window which is the maximum time, based on PTS values, between the time when a newest block in said media cache has arrived and an oldest block which said media cache may hold, such that said window represents a time-span into a past history of said stream; and

wherein said media cache discards blocks which fall outside said window, such that said window allows one to look a fixed distance into said past history of said stream.

48. The apparatus of claim 46, wherein a capture mechanism is responsible for providing certain attributes along with each new block;

and

wherein said attributes include any of a key frame attribute which indicates that said block begins a sequence of inter-related blocks such that said media cache only allows positioning of said stream to a block marked as a key frame when performing random access operations on said stream; and

an End Of Segment (EOS) attribute which indicates that said stream has ended and that no more data are to be presented.

49. The apparatus of claim 46, wherein said media cache maintains an indication of a next block to be presented to a decoding process;

and

wherein said block is a block last added to said media cache by a capture mechanism, such that said stream is presented live with at most a one-frame time delay between capture and presentation.

50. The apparatus of claim 46, wherein random access to said stream is achieved by moving a current block indicator to another block in said media cache;

and

wherein said media cache instructs a decoding process to reset its decoding state, thus purging any partially constructed presentation data, if said media cache is requested to move said block indicator, and a current block indicated is not a key frame.

51. The apparatus of claim 46, further comprising:

a buffer controller that requests repositioning of a media cache by specifying a PTS value;

wherein said media cache finds a block containing a PTS which is closest to that requested by said buffer controller.

52. The apparatus of claim 51, wherein said media cache scans blocks of data in said media cache to find a key frame which is nearest to a requested PTS value, searching both before and after a desired value, if said media cache is marked as a key stream, wherein said media cache returns PTS of said key frame block which was identified to said buffer controller, once said media cache is properly positioned;

instructing each remaining stream to position itself to said PTS returned by said key stream, wherein key frames in other media caches may not align with those in said key stream, in which event each media cache requests a decoding process to purge any decoding state, and then stores an indication that suppresses each other media cache from actually presenting blocks to said decoding process;

said media cache accepting clock events and advancing a current block indicator to match, except that said blocks are not actually presented to said decoding process; and

deleting an indication suppressing presentation of blocks; and

presenting a current block to said decoding process when said media cache encounters a key frame.

53. The apparatus of claim 33, wherein a forward/reverse function is implemented by moving a current block indicator forward/reverse through said media cache by one block for each event generated by a stream clock;

wherein each successive block in said media cache is given to an optional decoding process for presentation as clock events are dispatched by said stream clock;

wherein a rate multiplier causes a current block indicator to move forward/reverse within said media cache at a selected rate as new blocks are added to said media cache by a capture process, resulting in play out at a fixed delay from real time.

54. The apparatus of claim 53, wherein said media cache reverts to a key frame based method in which intermediate blocks are skipped and only key frames are presented to said decoder if said decoder can not keep up with a playback rate requested.

55. The apparatus of claim 53, wherein a buffer controller resets said stream clock rate multiplier to one, and each media cache positions a current block indicator to a latest cached block if said current block indicator moves to a front of said media cache where no more blocks are present in said media cache.

56. The apparatus of claim 53, wherein said current block indicator is set to an earliest block in said media cache if a clock event would result in moving a current block indicator past said earliest block;

and

wherein play out thereafter continues said that it appears as if said stream is playing in a forward direction again.

57. The apparatus of claim 33, further comprising:

a buffer controller for implementing a pause function by locking a current block indicator in a key stream media cache to a key frame block nearest a currently indicated block;

searching forward for said key frame block in said media cache if said current block is not a key frame block;

storing an indication that a lock has been requested if no key frame is present; and

locking said current block indicator to a key frame when a capture process presents a key frame.

58. The apparatus of claim 57, wherein said indicator is unlocked and left pointing at an earliest block in said media cache if a stream window moves past a block to which said indicator is locked, thereby providing automatic release of said pause.

59. The apparatus of claim 33, further comprising:

means for extracting a range of blocks from said media cache in either of a relative mode and an absolute mode by returning a pointer to a cached block plus a count of the number of blocks that make up an extract range; and

an indicator in said media cache that suppresses discarding blocks within said extract which fall outside a window.

60. The apparatus of claim 59, wherein said relative mode specifies a clip to be captured as two numbers, wherein a first number represents an offset from said current block indicator into previous blocks in said media cache, and a second number represents an offset from said current block indicator into subsequent blocks in said media cache.

61. The apparatus of claim 59, wherein said absolute mode specifies a clip to be captured as two numbers, wherein a first number represents an absolute time stamp based on when said media cache began operation, and a second number represents a time offset from that value, which may be a negative offset that indicates a distance backwards in said media cache or a positive value that indicates distance forwards in said media cache.

62. The apparatus of claim 33, further comprising:

a clip capture module for selecting ranges of blocks from a set of media caches, bringing said blocks together into an appropriate storage or transmission format, and saving or sending said blocks as needed.

63. The apparatus of claim 62, wherein a buffer controller indicates that capture should occur based on a current block indicator in a key stream media cache.

64. The apparatus of claim 62, wherein a buffer controller indicates an absolute range in which only blocks marked with a presentation time stamp (PTS) inclusive in that range are captured.