Method and apparatus for MPEG encoding

• US 5,844,594 A
• Filed: 10/05/1995
• Issued: 12/01/1998
• Est. Priority Date: 10/05/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ferguson, Robert
• Primary Examiner(s): GRANT, CHRISTOPHER C
• Application Number:
  US08/539,417
• Time in Patent Office: 1,153 Days
• Field of Search: 348/10, 348/12, 348/13, 348/6, 348/7, 348/390, 348/385, 348/384, 348/388, 348/400, 348/401, 348/402, 348/409, 348/415, 348/416, 455/4.2, 455/5.1, 455/6.1, 455/6.2, 455/6.3
• US Class Current: 725/131
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements
• CPC Class Codes: H04N 19/439 using cascaded computational arrangements for performing a single operation, e.g. filtering
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 21/40 Client devices specifically adapted for the reception of or interaction with content, e.g. set-top-box [STB]; Operations thereof
• CPC Class Codes: H04N 7/083 with signal insertion during the vertical and the horizontal blanking interval , e.g. MAC data signals
• CPC Class Codes: H04N 7/17318 Direct or substantially direct transmission and handling of requests
• CPC Class Codes: H04N 7/24 Systems for the transmission of television signals using pulse code modulation H04N21/00 takes precedence

Abstract

MPEG compression for video/audio data is completed in real- or better than real-time by using computer processors in thousands of television receiver set-top boxes interconnected to a cable television network. The set-top boxes form a massively parallel, distributed computer network. MPEG compression for video/audio services is completed by partitioning the processing of video/audio frames into subtasks, and distributing these subtasks to set-top boxes which are not being used for subscriber services. After compression, the compressed video/audio frames are collected from the set-top boxes and are reconstructed into a compressed video/audio stream in the proper temporal order.

Claims

1. A method of MPEG encoding a series of input image data provided from a digital source using an apparatus including a plurality of cable television receivers, each television receiver including a processing unit, each television receiver having a first state in which the processing unit therein is performing a subscriber function such as display of video to a user, and a second state in which said processing unit is not performing a subscriber function, the receiver including means for changing between the first and second states, the apparatus further including a central facility coupled to each of said television receivers, the central facility including mass storage means, a control processor, and the digital source, the method comprising:

at the central facility, identifying television receivers that are in the second state;

partitioning the series of input image data from the digital source into a plurality of subparts to be processed in a plurality of subtasks;

allocating said subtasks among processing units in said television receivers that have been discerned to be in the second state as a plurality of subtasks;

at the television receivers, performing an MPEG encoding process on each of the subparts as part of execution of each of said subtasks;

collecting MPEG processed data from said receivers into said mass storage to form a composite set of MPEG processed data;

sensing a subtask interruption caused by a television receiver being changed from the second state before completing the subtask allocated thereto; and

automatically recovering from said subtask interruption and completing the MPEG encoding.

2. The method of claim 1 which includes consulting a database in determining how to allocate subtasks among said units, the database including data related to patterns of cable television receiver usage by cable subscribers.

3. The method of claim 1 in which the automatically recovering step includes allocating a given subtask to a plurality of different processing units for redundant processing, wherein interruption of a subtask does not unduly interrupt the MPEG encoding.

4. The method of claim 3 which includes comparing MPEG processed data returned from at least two different of said processing units.

5. The method of claim 3 which includes consulting a database in determining how many different processing units to use in redundantly processing a given subtask, the database including data related to patterns of cable television receiver usage by cable subscribers.

6. The method of claim 1 which includes setting a time-out timer at the central facility for each television receiver allocated a subtask, and sensing a subtask interruption by failure of a television receiver to return data to the central facility before the expiry of the time-out timer corresponding thereto.

7. The method of claim 1 which further includes JPEG encoding and decoding the series of input image data prior to MPEG encoding.

8. The method of claim 7 which includes performing the JPEG decoding by the processing units in the television receivers.

9. The method of claim 1 which includes using a processing unit in a television receiver to produce exactly one I frame, and one or more B and P frames, for each of the subparts allocated to said unit.

10. The method of claim 1 which includes using a processing unit in a television receiver to produce one or more I, B and P frames for each of the subparts allocated to said unit, and transmitting said frames from the processing unit in the television receiver back to the central facility before processing of the subtask by the processing unit is completed.

11. The method of claim 1 in which the automatically recovering step includes reallocating said interrupted subtask to a different, substitute television receiver.

12. The method of claim 11 in which the reallocating includes providing restoration data from the central facility to the substitute television receiver to allow it to resume processing of the interrupted subtask from an intermediate state, rather than starting over.

13. The method of claim 11 in which the reallocating includes reinitializing the substitute processing unit to start the interrupted subtask from the beginning thereof.

14. The method of claim 1 in which data transfers related to the MPEG encoding process occur exclusively between the central facility and the television processing units, rather than also between different television receiver processing units.

15. In a computer programmed with MPEG compression software to process input moving image data to produce MPEG-encoded output data corresponding thereto, an improvement comprising means for achieving a compression ratio in excess of 100 to one with an ongoing delay of less than thirty minutes irrespective of the duration of the input moving image data, using a processor that, at other times, is used to perform functions unrelated to MPEG encoding.

16. The computer of claim 15 which includes means for providing input moving image data to the computer at a rate in excess of 400 megabits per second, and for providing MPEG-encoded output data corresponding thereto at a rate below 4 megabits per second.

17. In a method of MPEG compression that includes partitioning a video program into a plurality of clips for processing by a plurality of compression processors, an improvement comprising providing a plurality of different video programs that together total N hours of programming, and MPEG compressing all of said programs, simultaneously, to produce a corresponding plurality of MPEG-compressed programs, and completing said simultaneous compression in less than N hours.

18. The method of claim 17 which includes partitioning, at a control station, said N hours of programming into plural compression subtasks, and allocating said subtasks among plural processors.

19. The method of claim 18 which further includes automatically recovering from an interruption of subtask processing by one of said plural processors.

20. The method of claim 19 which includes allocating a given subtask to two or more different processors for redundant processing, wherein interruption of the subtask does not unduly interrupt the MPEG encoding.

21. The method of claim 20 which includes comparing MPEG processed data from at least two of said different processors.

22. The method of claim 19 which includes setting a time-out timer at the control station for each processor allocated a subtask, and sensing a subtask interruption by failure of a processor to return data to the control station before the expiry of the time-out timer corresponding thereto.

23. The method of claim 19 which includes reallocating said interrupted subtask to a different, substitute processor.

24. The method of claim 23 which includes providing restoration data from the control station to the substitute processor to allow it to resume processing of the interrupted subtask from an intermediate state, rather than starting over.

25. The method of claim 23 which includes reinitializing the substitute processor to start the interrupted subtask from the beginning thereof.

26. The method of claim 18 which includes coupling each of the plural processors only to the control station, and not to any other of said plural processors.

27. The method of claim 18 which further includes JPEG encoding and decoding the video program prior to MPEG encoding.

28. The method of claim 27 which includes performing the JPEG decoding at said plural processors.

29. The method of claim 18 which includes generating exactly one I-frame, and one or more B and P frames, as an output from each subtask.

30. The method of claim 17 which includes using said compression processors for non-compression functions at other times, wherein the compression processors do not comprise dedicated hardware.

31. In a computer programmed with MPEG compression software to process input moving image data to produce MPEG-encoded output data corresponding thereto, an improvement including plural processors receiving compression subtasks from a control station, said plural processors and control station collectively achieving a compression ratio in excess of 100 to one with an ongoing delay of less than thirty minutes irrespective of the duration of the input moving image data, at least some of said plural processors, at other times, being used to perform functions unrelated to MPEG encoding.

32. The method of claim 31 which further includes consulting a database to determine how to allocate subtasks among said plural processors, the database including data related to patterns of usage of said processors for said functions unrelated to MPEG encoding.

33. The method of claim 31 which further includes automatically recovering from an interruption of subtask processing by one of said plural processors.

34. The method of claim 33 which includes allocating a given subtask to two or more different processors for redundant processing, wherein interruption of the subtask does not unduly interrupt the MPEG encoding.

35. The method of claim 34 which includes comparing MPEG processed data from at least two of said different processors.

36. The method of claim 33 which includes setting a time-out timer at the control station for each processor allocated a subtask, and sensing a subtask interruption by failure of a processor to return data to the control station before the expiry of the time-out timer corresponding thereto.

37. The method of claim 33 which includes reallocating said interrupted subtask to a different, substitute processor.

38. The method of claim 37 which includes providing restoration data from the control station to the substitute processor to allow it to resume processing of the interrupted subtask from an intermediate state, rather than starting over.

39. The method of claim 37 which includes reinitializing the substitute processor to start the interrupted subtask from the beginning thereof.

40. The method of claim 31 which includes coupling each of the plural processors only to the control station, and not to any other of said plural processors.

41. The method of claim 31 which further includes JPEG encoding and decoding the moving image data prior to MPEG encoding.

42. The method of claim 41 which includes performing the JPEG decoding at said plural processors.

43. The method of claim 41 which includes generating exactly one I-frame, and one or more B and P frames, as an output from each subtask.