US9826197B2

Movatterモバイル変換

Info

Publication number: US9826197B2
Application number: US12/651,203
Authority: US
Inventors: Joshua Dahlby; Andrey Marsavin; Charles Lawrence; Lena Y. Pavlovskaia
Original assignee: ActiveVideo Networks Inc
Current assignee: ActiveVideo Networks Inc
Priority date: 2007-01-12
Filing date: 2009-12-31
Publication date: 2017-11-21
Also published as: AU2010339376A1; EP2520090A4; KR20120112683A; CA2787913A1; WO2011082364A2; WO2011082364A3; US20100158109A1; JP2013516847A; EP2520090A2

Abstract

A client device receives a broadcast content signal containing an interactive identifier over a managed network at a client device. The interactive identifier may be a trigger that is included in a header or embedded within the digital video data. The trigger may have a temporal component, wherein the trigger can expire after a certain period of time. In response to identification of the trigger, the client device sends a user request for interactive content over an unmanaged network. For example, the managed network may be a one-way satellite television network, IP-television network or cable television network and the unmanaged network may be the Internet. The client device switches between receiving data from the managed network to receiving data from the unmanaged network.

Description

PRIORITY

This application is a continuation-in-part of U.S. application Ser. No. 12/489,017 filed Jun. 22, 2009 entitled “Providing Television Broadcasts over a Managed Network and Interactive Content over an Unmanaged Network to a Client Device,” the full disclosure of which is incorporated herein by reference.

Application Ser. No. 12/489,017 is a continuation-in-part of U.S. application Ser. No. 12/008,697 filed Jan. 11, 2008 entitled “Interactive Encoded Content System including Object Models for Viewing on a Remote Device” which itself claims priority from Application No. 60/884,773, filed Jan. 12, 2007, Application No. 60/884,744, filed Jan. 12, 2007, and Application No. 60/884,772, filed Jan. 12, 2007, the full disclosures of which are all hereby incorporated herein by reference.

Application Ser. No. 12/489,017 is also a continuation-in-part of U.S. patent application Ser. No. 12/008,722 filed on Jan. 11, 2008 entitled “MPEG Objects and Systems and Methods for Using MPEG Objects”, which itself claims priority from U.S. provisional application Ser. No. 60/884,773, filed Jan. 12, 2007, Ser. No. 60/884,744, filed Jan. 12, 2007, and Ser. No. 60/884,772, filed Jan. 12, 2007, the full disclosures of which are all hereby incorporated herein by reference.

Application Ser. No. 12/489,017 also claims priority from U.S. provisional patent application No. 61/133,102 filed on Jun. 25, 2008 having the title “Providing Television Broadcasts over a Managed Network and Interactive Content over an Unmanaged Network to a Client Device”, which is incorporated by reference herein in its entirety.

TECHNICAL FIELD AND BACKGROUND ART

The present invention relates to systems and methods for providing interactive content to a remote device and more specifically to systems and methods employing both a managed and an unmanaged network, where the unmanaged network has a high latency and high bandwidth variability.

In cable television systems, the cable head-end transmits content to one or more subscribers wherein the content is transmitted in an encoded form. Typically, the content is encoded as digital MPEG video and each subscriber has a set-top box or cable card that is capable of decoding the MPEG video stream. Beyond providing linear content, cable providers can now provide interactive content, such as web pages, walled-garden content, video games, voice-over-IP (VOIP) telephony services that may include video, interactive catalogs and streaming delivery of audiovisual content including movies, and the like. As the Internet has become more dynamic, including video content on web pages and requiring applications or scripts for decoding the video content, cable providers have adapted to allow subscribers the ability to view these dynamic web pages. In order to transmit a dynamic web page to a requesting subscriber in encoded form, the cable head end retrieves the requested web page and renders the web page. Thus, the cable headend must first decode any encoded content that appears within the dynamic webpage. For example, if a video is to be played on the webpage, the headend must retrieve the encoded video and decode each frame of the video. The cable headend then renders each frame to form a sequence of bitmap images of the Internet web page. Thus, the web page can only be composited together if all of the content that forms the web page is first decoded. Once the composite frames are complete, the composited video is sent to an encoder, such as an MPEG encoder to be re-encoded. The compressed MPEG video frames are then sent in an MPEG video stream to the user's set-top box.

Creating such composite encoded video frames in a cable television network requires intensive CPU and memory processing, since all encoded content must first be decoded, then composited, rendered, and re-encoded. In particular, the cable headend must decode and re-encode all of the content in real-time. Thus, allowing users to operate in an interactive environment with dynamic web pages and other dynamic content is quite costly to cable operators because of the required processing. Additionally, such systems have the additional drawback that the image quality is degraded due to re-encoding of the encoded video.

Satellite television systems suffer from the problem that they are limited to one-way transmissions. Thus, satellite television providers can not offer “on-demand” or interactive services. As a result, satellite television networks are limited to providing a managed network for their subscribers and can not provide user requested access to interactive information. Other communication systems cannot provide interactive content, for example, cable subscribers that have one-way cable cards or cable systems that do not support two-way communications.

Methods are known in the prior art to transmit data between computers connected by an unreliable network. One example method uses the User Datagram Protocol (UDP), as first formally defined in Postel, J.,Request for Comments768: User Datagram Protocol(August 1980) (“RFC 768”). UDP provides a procedure for application programs on different computers to send data to each other with a minimum of protocol mechanism. Traditionally, providers of audiovisual content have used UDP for transmitting non-interactive content, such as streaming video, because of the very low latency and low overhead of UDP. However, more recently, security concerns have prompted a large and growing number of television subscribers to place their client devices behind a network firewall. Firewalls may be difficult for subscribers to configure, especially to allow certain UDP connections from a content provider and not other, harmful connections. Further, UDP does not provide reliable data transmission, causing “skips” or other artifacts in transmitted audio or video, and therefore does not meet the requirements for providing an optimal user experience.

The Transmission Control Protocol (TCP), as first formally defined in Information Sciences Institute,Request for Comments793: Transmission Control Protocol(September 1981) (“RFC 793”), does provide reliable data transmission, but providing interactive services over a TCP network to a thin client is problematic. TCP provides a number of high-level services that UDP does not, such as end-to-end connections, and packet reordering and retransmission. These additional services consume valuable computing resources that are in high demand on a thin client device and introduce retransmission latency into the communication channel. Another problem is that transmitting full-motion video, such as that found in a streaming movie, consumes a great deal of network bandwidth. Some special-purpose systems, such as networked3D video games, combat this problem by transmitting only game data to a client device and having the client device render the virtual environment. Such solutions are inapplicable to general video applications. Further, the calculation and rendering processes required on the client device consume even more computing resources than simple video rendering alone, making them unsuitable on a very thin client, even for playing video games. Thus, while TCP has several advantages over UDP for transmission of interactive services to subscribers, the thin client requirement makes the provision of these services difficult.

SUMMARY OF THE INVENTION

Embodiments of the present invention address the limitations of the prior art by enabling computationally simple bitrate detection and adaptive control over transmitted content. These features allow a television system operator to provide interactive services having a high quality of experience to its subscribers who have inexpensive, thin clients.

A first embodiment of the invention includes a method of providing reliable transmission of interactive content over an unmanaged network to a client decoding device associated with a user. The interactive content has both a video component and an audio component. The client decoding device receives broadcast video content over a managed network in addition to receiving the interactive content over the unmanaged network, and is capable of switching between the broadcast video content and the interactive content for output to a display device.

The method begins with receiving a request to provide the interactive content to the client decoding device over the unmanaged network. After the request is received, the method continues with encoding a first plurality of frames of the interactive video content according to a video encoding bitrate, thereby forming a first portion of encoded interactive content, and transmitting the first portion of encoded interactive content to the client decoding device, over the unmanaged network, using a reliable data transmission protocol. Next, the method includes determining a transmission bandwidth of the first portion over the unmanaged network and adjusting the video encoding bitrate according to the transmission bandwidth. Once these adjustments are made, the method continues with encoding a second portion of the interactive content according to the adjusted video encoding bitrate for the video component and the unadjusted audio encoding bitrate for the audio component, thereby forming a second portion of encoded interactive content, and transmitting the second portion of encoded interactive content to the client decoding device, over the unmanaged network, using the reliable data transmission protocol.

Further, when the determined bandwidth becomes less than a minimum bandwidth associated with the interactive content, a related method may include transmitting to the client decoding device, over the unmanaged network, using the reliable data transmission protocol, a service unavailable content instead of the encoded interactive content.

In a second embodiment there is provided a method, complimentary to the first embodiment, of adapting to varying conditions in the reception of interactive content over an unmanaged network in a client decoding device associated with a user. The interactive content has a video component and an audio component, and the client decoding device receives broadcast video content over a managed network, as before. The method includes receiving the interactive content in the client decoding device from the unmanaged network using a reliable data transmission protocol, including determining a receiving bandwidth at which the interactive content is received. Once reception of the interactive content has begun, the method includes demultiplexing the received interactive content into the video component and the audio component, simulating a playback of the audio component based on the receiving bandwidth, and decoding the audio component and the video component in the client decoding device at a bitrate based on the simulation.

Simulating the playback may include determining the quantity of data in an audio buffer as a function of time. The decoding bitrate may be proportional to the receiving bandwidth. The method may further include increasing or decreasing a size of an audio buffer as a function of the receiving bandwidth. In a related embodiment, the method includes receiving a trigger, either in the client decoding device over the managed network, or in a headend, the trigger causing the client decoding device to request the interactive content over the unmanaged network.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing features of the invention will be more readily understood by reference to the following detailed description, taken with reference to the accompanying drawings, in which:

FIG. 1 is a block diagram showing a communications environment for implementing one version of the present invention;

FIG. 1A shows the regional processing offices and the video content distribution network;

FIG. 1B is a sample composite stream presentation and interaction layout file;

FIG. 1C shows the construction of a frame within the authoring environment;

FIG. 1D shows breakdown of a frame by macroblocks into elements;

FIG. 2 is a diagram showing multiple sources composited onto a display;

FIG. 3 is a diagram of a system incorporating grooming;

FIG. 4 is a diagram showing a video frame prior to grooming, after grooming, and with a video overlay in the groomed section;

FIG. 5 is a diagram showing how grooming is done, for example, removal of B-frames;

FIG. 6 is a diagram showing an MPEG frame structure;

FIG. 7 is a flow chart showing the grooming process for I, B, and P frames;

FIG. 8 is a diagram depicting removal of region boundary motion vectors;

FIG. 9 is a diagram showing the reordering of the DCT coefficients;

FIG. 10 shows an alternative groomer;

FIG. 11 is an example of a video frame;

FIG. 12 is a diagram showing video frames starting in random positions relative to each other;

FIG. 13 is a diagram of a display with multiple MPEG elements composited within the picture;

FIG. 14 is a diagram showing the slice breakdown of a picture consisting of multiple elements;

FIG. 15 is a diagram showing slice based encoding in preparation for stitching;

FIG. 16 is a diagram detailing the compositing of a video element into a picture;

FIG. 17 is a diagram detailing compositing of a 16×16 sized macroblock element into a background comprised of 24×24 sized macroblocks;

FIG. 18 is a flow chart showing the steps involved in encoding and building a composited picture;

FIG. 19 is a diagram providing a simple example of grooming;

FIG. 20 is a diagram showing that the composited element does not need to be rectangular nor contiguous;

FIG. 21 shows a diagram of elements on a screen wherein a single element is non-contiguous;

FIG. 22 shows a groomer for grooming linear broadcast content for multicasting to a plurality of processing offices and/or session processors;

FIG. 23 shows an example of a customized mosaic when displayed on a display device;

FIG. 24 is a diagram of an IP based network for providing interactive MPEG content;

FIG. 25 is a diagram of a cable based network for providing interactive MPEG content;

FIG. 26 is a flow-chart of the resource allocation process for a load balancer for use with a cable based network;

FIG. 27 is a system diagram used to show communication between cable network elements for load balancing;

FIG. 28 shows a managed broadcast content satellite network that can provide interactive content to subscribers through an unmanaged IP network;

FIG. 29 shows another environment where a client device receives broadcast content through a managed network and interactive content may be requested and is provided through an unmanaged network;

FIG. 30 shows a server embodiment of the invention in which a stitcher performs adaptive bitrate detection and control;

FIG. 30A shows a flowchart of the relevant processes ofFIG. 30;

FIG. 31 shows an embodiment of the invention in which a client device performs adaptive latency control;

FIG. 32 shows an alternate client embodiment for performing adaptive latency control; and

FIG. 33 shows a server embodiment in which the data gathered from bitrate detection are used to provide a selection of services according to one or more business rules.

DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS

As used in the following detailed description and in the appended claims the term “region” shall mean a logical grouping of MPEG (Motion Picture Expert Group) slices that are either contiguous or non-contiguous. When the term MPEG is used it shall refer to all variants of the MPEG standard including MPEG-2 and MPEG-4. The present invention as described in the embodiments below provides an environment for interactive MPEG content and communications between a processing office and a client device having an associated display, such as a television. Although the present invention specifically references the MPEG specification and encoding, principles of the invention may be employed with other encoding techniques that are based upon block-based transforms. As used in the following specification and appended claims, the terms encode, encoded, and encoding shall refer to the process of compressing a digital data signal and formatting the compressed digital data signal to a protocol or standard. Encoded video data can be in any state other than a spatial representation. For example, encoded video data may be transform coded, quantized, and entropy encoded or any combination thereof. Therefore, data that has been transform coded will be considered to be encoded.

Although the present application refers to the display device as a television, the display device may be a cell phone, a Personal Digital Assistant (PDA) or other device that includes a display. A client device including a decoding device, such as a set-top box that can decode MPEG content, is associated with the display device of the user. In certain embodiments, the decoder may be part of the display device. The interactive MPEG content is created in an authoring environment allowing an application designer to design the interactive MPEG content creating an application having one or more scenes from various elements including video content from content providers and linear broadcasters. An application file is formed in an Active Video Markup Language (AVML). The AVML file produced by the authoring environment is an XML-based file defining the video graphical elements (i.e. MPEG slices) within a single frame/page, the sizes of the video graphical elements, the layout of the video graphical elements within the page/frame for each scene, links to the video graphical elements, and any scripts for the scene. In certain embodiments, an AVML file may be authored directly as opposed to being authored in a text editor or generated by an authoring environment. The video graphical elements may be static graphics, dynamic graphics, or video content. It should be recognized that each element within a scene is really a sequence of images and a static graphic is an image that is repeatedly displayed and does not change over time. Each of the elements may be an MPEG object that can include both MPEG data for graphics and operations associated with the graphics. The interactive MPEG content can include multiple interactive MPEG objects within a scene with which a user can interact. For example, the scene may include a button MPEG object that provides encoded MPEG data forming the video graphic for the object and also includes a procedure for keeping track of the button state. The MPEG objects may work in coordination with the scripts. For example, an MPEG button object may keep track of its state (on/off), but a script within the scene will determine what occurs when that button is pressed. The script may associate the button state with a video program so that the button will indicate whether the video content is playing or stopped. MPEG objects always have an associated action as part of the object. In certain embodiments, the MPEG objects, such as a button MPEG object, may perform actions beyond keeping track of the status of the button. In such, embodiments, the MPEG object may also include a call to an external program, wherein the MPEG object will access the program when the button graphic is engaged. Thus, for a play/pause MPEG object button, the MPEG object may include code that keeps track of the state of the button, provides a graphical overlay based upon a state change, and/or causes a video player object to play or pause the video content depending on the state of the button.

Once an application is created within the authoring environment, and an interactive session is requested by a requesting client device, the processing office assigns a processor for the interactive session.

The assigned processor operational at the processing office runs a virtual machine and accesses and runs the requested application. The processor prepares the graphical part of the scene for transmission in the MPEG format. Upon receipt of the MPEG transmission by the client device and display on the user's display, a user can interact with the displayed content by using an input device in communication with the client device. The client device sends input requests from the user through a communication network to the application running on the assigned processor at the processing office or other remote location. In response, the assigned processor updates the graphical layout based upon the request and the state of the MPEG objects hereinafter referred to in total as the application state. New elements may be added to the scene or replaced within the scene or a completely new scene may be created. The assigned processor collects the elements and the objects for the scene, and either the assigned processor or another processor processes the data and operations according to the object(s) and produces the revised graphical representation in an MPEG format that is transmitted to the transceiver for display on the user's television. Although the above passage indicates that the assigned processor is located at the processing office, the assigned processor may be located at a remote location and need only be in communication with the processing office through a network connection. Similarly, although the assigned processor is described as handling all transactions with the client device, other processors may also be involved with requests and assembly of the content (MPEG objects) of the graphical layout for the application.

FIG. 1 is a block diagram showing acommunications environment100 for implementing one version of the present invention. Thecommunications environment100 allows an applications programmer to create an application for two-way interactivity with an end user. The end user views the application on aclient device110, such as a television, and can interact with the content by sending commands upstream through anupstream network120 wherein upstream and downstream may be part of the same network or a separate network providing the return path link to the processing office. The application programmer creates an application that includes one or more scenes. Each scene is the equivalent of an HTML webpage except that each element within the scene is a video sequence. The application programmer designs the graphical representation of the scene and incorporates links to elements, such as audio and video files and objects, such as buttons and controls for the scene. The application programmer uses agraphical authoring environment130 to graphically select the objects and elements. Theauthoring environment130 may include a graphical interface that allows an application programmer to associate methods with elements creating video objects. The graphics may be MPEG encoded video, groomed MPEG video, still images or video in another format. The application programmer can incorporate content from a number of sources including content providers160 (news sources, movie studios, RSS feeds etc.) and linear broadcast sources (broadcast media and cable, on demand video sources and web-based video sources)170 into an application. The application programmer creates the application as a file in AVML (active video mark-up language) and sends the application file to a proxy/cache140 within a videocontent distribution network150. The AVML file format is an XML format. For example seeFIG. 1B that shows a sample AVML file.

Thecontent provider160 may encode the video content as MPEG video/audio or the content may be in another graphical format (e.g. JPEG, BITMAP, H263, H264, VC-1 etc.). The content may be subsequently groomed and/or scaled in a Groomer/Scaler190 to place the content into a preferable encoded MPEG format that will allow for stitching. If the content is not placed into the preferable MPEG format, the processing office will groom the format when an application that requires the content is requested by a client device.Linear broadcast content170 from broadcast media services, like content from the content providers, will be groomed. The linear broadcast content is preferably groomed and/or scaled in Groomer/Scaler180 that encodes the content in the preferable MPEG format for stitching prior to passing the content to the processing office.

The video content from thecontent producers160 along with the applications created by application programmers are distributed through a videocontent distribution network150 and are stored at distribution points140. These distribution points are represented as the proxy/cache withinFIG. 1. Content providers place their content for use with the interactive processing office in the video content distribution network at a proxy/cache140 location. Thus,content providers160 can provide their content to thecache140 of the videocontent distribution network150 and one or more processing office that implements the present architecture may access the content through the videocontent distribution network150 when needed for an application. The videocontent distribution network150 may be a local network, a regional network or a global network. Thus, when a virtual machine at a processing office requests an application, the application can be retrieved from one of the distribution points and the content as defined within the application's AVML file can be retrieved from the same or a different distribution point.

An end user of the system can request an interactive session by sending a command through theclient device110, such as a set-top box, to aprocessing office105. InFIG. 1, only a single processing office is shown. However, in real-world applications, there may be a plurality of processing offices located in different regions, wherein each of the processing offices is in communication with a video content distribution network as shown inFIG. 1B. Theprocessing office105 assigns a processor for the end user for an interactive session. The processor maintains the session including all addressing and resource allocation. As used in the specification and the appended claims the term “virtual machine”106 shall refer to the assigned processor, as well as, other processors at the processing office that perform functions, such as session management between the processing office and the client device as well as resource allocation (i.e. assignment of a processor for an interactive session).

Thevirtual machine106 communicates its address to theclient device110 and an interactive session is established. The user can then request presentation of an interactive application (AVML) through theclient device110. The request is received by thevirtual machine106 and in response, thevirtual machine106 causes the AVML file to be retrieved from the proxy/cache140 and installed into amemory cache107 that is accessible by thevirtual machine106. It should be recognized that thevirtual machine106 may be in simultaneous communication with a plurality ofclient devices110 and the client devices may be different device types. For example, a first device may be a cellular telephone, a second device may be a set-top box, and a third device may be a personal digital assistant wherein each device access the same or a different application.

In response to a request for an application, thevirtual machine106 processes the application and requests elements and MPEG objects that are part of the scene to be moved from the proxy/cache intomemory107 associated with thevirtual machine106. An MPEG object includes both a visual component and an actionable component. The visual component may be encoded as one or more MPEG slices or provided in another graphical format. The actionable component may be storing the state of the object, may include performing computations, accessing an associated program, or displaying overlay graphics to identify the graphical component as active. An overlay graphic may be produced by a signal being transmitted to a client device wherein the client device creates a graphic in the overlay plane on the display device. It should be recognized that a scene is not a static graphic, but rather includes a plurality of video frames wherein the content of the frames can change over time.

Thevirtual machine106 determines based upon the scene information, including the application state, the size and location of the various elements and objects for a scene. Each graphical element may be formed from contiguous or non-contiguous MPEG slices. The virtual machine keeps track of the location of all of the slices for each graphical element. All of the slices that define a graphical element form a region. Thevirtual machine106 keeps track of each region. Based on the display position information within the AVML file, the slice positions for the elements and background within a video frame are set. If the graphical elements are not already in a groomed format, the virtual machine passes that element to an element renderer. The renderer renders the graphical element as a bitmap and the renderer passes the bitmap to anMPEG element encoder109. The MPEG element encoder encodes the bitmap as an MPEG video sequence. The MPEG encoder processes the bitmap so that it outputs a series of P-frames. An example of content that is not already pre-encoded and pre-groomed is personalized content. For example, if a user has stored music files at the processing office and the graphic element to be presented is a listing of the user's music files, this graphic would be created in real-time as a bitmap by the virtual machine. The virtual machine would pass the bitmap to theelement renderer108 which would render the bitmap and pass the bitmap to theMPEG element encoder109 for grooming.

After the graphical elements are groomed by the MPEG element encoder, theMPEG element encoder109 passes the graphical elements tomemory107 for later retrieval by thevirtual machine106 for other interactive sessions by other users. TheMPEG encoder109 also passes the MPEG encoded graphical elements to thestitcher115. The rendering of an element and MPEG encoding of an element may be accomplished in the same or a separate processor from thevirtual machine106. Thevirtual machine106 also determines if there are any scripts within the application that need to be interpreted. If there are scripts, the scripts are interpreted by thevirtual machine106.

Each scene in an application can include a plurality of elements including static graphics, object graphics that change based upon user interaction, and video content. For example, a scene may include a background (static graphic), along with a media player for playback of audio video and multimedia content (object graphic) having a plurality of buttons, and a video content window (video content) for displaying the streaming video content. Each button of the media player may itself be a separate object graphic that includes its own associated methods.

Thevirtual machine106 acquires each of the graphical elements (background, media player graphic, and video frame) for a frame and determines the location of each element. Once all of the objects and elements (background, video content) are acquired, the elements and graphical objects are passed to the stitcher/compositor115 along with positioning information for the elements and MPEG objects. Thestitcher115 stitches together each of the elements (video content, buttons, graphics, background) according to the mapping provided by thevirtual machine106. Each of the elements is placed on a macroblock boundary and when stitched together the elements form an MPEG video frame. On a periodic basis all of the elements of a scene frame are encoded to form a reference P-frame in order to refresh the sequence and avoid dropped macroblocks. The MPEG video stream is then transmitted to the address of client device through the down stream network. The process continues for each of the video frames. Although the specification refers to MPEG as the encoding process, other encoding processes may also be used with this system.

Thevirtual machine106 or other processor or process at theprocessing office105 maintains information about each of the elements and the location of the elements on the screen. Thevirtual machine106 also has access to the methods for the objects associated with each of the elements. For example, a media player may have a media player object that includes a plurality of routines. The routines can include, play, stop, fast forward, rewind, and pause. Each of the routines includes code and upon a user sending a request to theprocessing office105 for activation of one of the routines, the object is accessed and the routine is run. The routine may be a JAVA-based applet, a script to be interpreted, or a separate computer program capable of being run within the operating system associated with the virtual machine.

Theprocessing office105 may also create a linked data structure for determining the routine to execute or interpret based upon a signal received by the processor from the client device associated with the television. The linked data structure may be formed by an included mapping module. The data structure associates each resource and associated object relative to every other resource and object. For example, if a user has already engaged the play control, a media player object is activated and the video content is displayed. As the video content is playing in a media player window, the user can depress a directional key on the user's remote control. In this example, the depression of the directional key is indicative of pressing a stop button. The transceiver produces a directional signal and the assigned processor receives the directional signal. Thevirtual machine106 or other processor at theprocessing office105 accesses the linked data structure and locates the element in the direction of the directional key press. The database indicates that the element is a stop button that is part of a media player object and the processor implements the routine for stopping the video content. The routine will cause the requested content to stop. The last video content frame will be frozen and a depressed stop button graphic will be interwoven by the stitcher module into the frame. The routine may also include a focus graphic to provide focus around the stop button. For example, the virtual machine can cause the stitcher to enclose the graphic having focus with a boarder that is 1 macroblock wide. Thus, when the video frame is decoded and displayed, the user will be able to identify the graphic/object that the user can interact with. The frame will then be passed to a multiplexor and sent through the downstream network to the client device. The MPEG encoded video frame is decoded by the client device displayed on either the client device (cell phone, PDA) or on a separate display device (monitor, television). This process occurs with a minimal delay. Thus, each scene from an application results in a plurality of video frames each representing a snapshot of the media player application state.

Thevirtual machine106 will repeatedly receive commands from the client device and in response to the commands will either directly or indirectly access the objects and execute or interpret the routines of the objects in response to user interaction and application interaction model. In such a system, the video content material displayed on the television of the user is merely decoded MPEG content and all of the processing for the interactivity occurs at the processing office and is orchestrated by the assigned virtual machine. Thus, the client device only needs a decoder and need not cache or process any of the content.

It should be recognized that through user requests from a client device, the processing office could replace a video element with another video element. For example, a user may select from a list of movies to display and therefore a first video content element would be replaced by a second video content element if the user selects to switch between two movies. The virtual machine, which maintains a listing of the location of each element and region forming an element, can easily replace elements within a scene creating a new MPEG video frame wherein the frame is stitched together including the new element in thestitcher115.

FIG. 1A shows the interoperation between the digitalcontent distribution network100A, the content providers110A and theprocessing offices120A. In this example, thecontent providers130A distribute content into the videocontent distribution network100A. Either thecontent providers130A or processors associated with the video content distribution network convert the content to an MPEG format that is compatible with the processing office's120A creation of interactive MPEG content. Acontent management server140A of the digitalcontent distribution network100A distributes the MPEG-encoded content among proxy/caches150A-154A located in different regions if the content is of a global/national scope. If the content is of a regional/local scope, the content will reside in a regional/local proxy/cache. The content may be mirrored throughout the country or world at different locations in order to increase access times. When an end user, through theirclient device160A, requests an application from a regional processing office, the regional processing office will access the requested application. The requested application may be located within the video content distribution network or the application may reside locally to the regional processing office or within the network of interconnected processing offices. Once the application is retrieved, the virtual machine assigned at the regional processing office will determine the video content that needs to be retrieved. Thecontent management server140A assists the virtual machine in locating the content within the video content distribution network. Thecontent management server140A can determine if the content is located on a regional or local proxy/cache and also locate the nearest proxy/cache. For example, the application may include advertising and the content management server will direct the virtual machine to retrieve the advertising from a local proxy/cache. As shown inFIG. 1A, both the Midwestern and Southeasternregional processing offices120A also have local proxy/

caches

153A,154A. These proxy/caches may contain local news and local advertising. Thus, the scenes presented to an end user in the Southeast may appear different to an end user in the Midwest. Each end user may be presented with different local news stories or different advertising. Once the content and the application are retrieved, the virtual machine processes the content and creates an MPEG video stream. The MPEG video stream is then directed to the requesting client device. The end user may then interact with the content requesting an updated scene with new content and the virtual machine at the processing office will update the scene by requesting the new video content from the proxy/cache of the video content distribution network.

Authoring Environment

The authoring environment includes a graphical editor as shown inFIG. 1C for developing interactive applications. An application includes one or more scenes. As shown inFIG. 1B the application window shows that the application is composed of three scenes (scene1,scene2 and scene3). The graphical editor allows a developer to select elements to be placed into the scene forming a display that will eventually be shown on a display device associated with the user. In some embodiments, the elements are dragged-and-dropped into the application window. For example, a developer may want to include a media player object and media player button objects and will select these elements from a toolbar and drag and drop the elements in the window. Once a graphical element is in the window, the developer can select the element and a property window for the element is provided. The property window includes at least the location of the graphical element (address), and the size of the graphical element. If the graphical element is associated with an object, the property window will include a tab that allows the developer to switch to a bitmap event screen and alter the associated object parameters. For example, a user may change the functionality associated with a button or may define a program associated with the button.

As shown inFIG. 1D, the stitcher of the system creates a series of MPEG frames for the scene based upon the AVML file that is the output of the authoring environment. Each element/graphical object within a scene is composed of different slices defining a region. A region defining an element/object may be contiguous or non-contiguous. The system snaps the slices forming the graphics on a macro-block boundary. Each element need not have contiguous slices. For example, the background has a number of non-contiguous slices each composed of a plurality of macroblocks. The background, if it is static, can be defined by intracoded macroblocks. Similarly, graphics for each of the buttons can be intracoded; however the buttons are associated with a state and have multiple possible graphics. For example, the button may have a first state “off” and a second state “on” wherein the first graphic shows an image of a button in a non-depressed state and the second graphic shows the button in a depressed state.FIG. 1C also shows a third graphical element, which is the window for the movie. The movie slices are encoded with a mix of intracoded and intercoded macroblocks and dynamically changes based upon the content. Similarly if the background is dynamic, the background can be encoded with both intracoded and intercoded macroblocks, subject to the requirements below regarding grooming.

When a user selects an application through a client device, the processing office will stitch together the elements in accordance with the layout from the graphical editor of the authoring environment. The output of the authoring environment includes an Active Video Mark-up Language file (AVML) The AVML file provides state information about multi-state elements such as a button, the address of the associated graphic, and the size of the graphic. The AVML file indicates the locations within the MPEG frame for each element, indicates the objects that are associated with each element, and includes the scripts that define changes to the MPEG frame based upon user's actions. For example, a user may send an instruction signal to the processing office and the processing office will use the AVML file to construct a set of new MPEG frames based upon the received instruction signal. A user may want to switch between various video elements and may send an instruction signal to the processing office. The processing office will remove a video element within the layout for a frame and will select the second video element causing the second video element to be stitched into the MPEG frame at the location of the first video element. This process is described below.

AVML File

The application programming environment outputs an AVML file. The AVML file has an XML-based syntax. The AVML file syntax includes a root object <AVML>. Other top level tags include <initialscene> that specifies the first scene to be loaded when an application starts. The <script> tag identifies a script and a <scene> tag identifies a scene. There may also be lower level tags to each of the top level tags, so that there is a hierarchy for applying the data within the tag. For example, a top level stream tag may include <aspect ratio> for the video stream, <video format>, <bit rate>, <audio format> and <audio bit rate>. Similarly, a scene tag may include each of the elements within the scene. For example, <background> for the background, <button> for a button object, and <static image> for a still graphic. Other tags include <size> and <pos> for the size and position of an element and may be lower level tags for each element within a scene. An example of an AVML file is provided inFIG. 1B.

Groomer

FIG. 2 is a diagram of a representative display that could be provided to a television of a requesting client device. Thedisplay200 shows three separate video content elements appearing on the screen.Element #1211 is the background in whichelement #2215 andelement #3217 are inserted.

FIG. 3 shows a first embodiment of a system that can generate the display ofFIG. 2. In this diagram, the three video content elements come in as encoded video:element #1303,element #2305, andelement #3307. Thegroomers310 each receive an encoded video content element and the groomers process each element before thestitcher340 combines the groomed video content elements into a single compositedvideo380. It should be understood by one of ordinary skill in the art that groomers310 may be a single processor or multiple processors that operate in parallel. The groomers may be located either within the processing office, at content providers' facilities, or linear broadcast provider's facilities. The groomers may not be directly connected to the stitcher, as shown inFIG. 1 wherein the

groomers

190 and180 are not directly coupled tostitcher115.

The process of stitching is described below and can be performed in a much more efficient manner if the elements have been groomed first.

Grooming removes some of the interdependencies present in compressed video. The groomer will convert I and B frames to P frames and will fix any stray motion vectors that reference a section of another frame of video that has been cropped or removed. Thus, a groomed video stream can be used in combination with other groomed video streams and encoded still images to form a composite MPEG video stream. Each groomed video stream includes a plurality of frames and the frames can be can be easily inserted into another groomed frame wherein the composite frames are grouped together to form an MPEG video stream. It should be noted that the groomed frames may be formed from one or more MPEG slices and may be smaller in size than an MPEG video frame in the MPEG video stream.

FIG. 4 is an example of a composite video frame that contains a plurality of

elements

410,420. This composite video frame is provided for illustrative purposes. The groomers as shown inFIG. 1 only receive a single element and groom the element (video sequence), so that the video sequence can be stitched together in the stitcher. The groomers do not receive a plurality of elements simultaneously. In this example, thebackground video frame410 includes 1 row per slice (this is an example only; the row could be composed of any number of slices). As shown inFIG. 1, the layout of the video frame including the location of all of the elements within the scene is defined by the application programmer in the AVML file. For example, the application programmer may design the background element for a scene. Thus, the application programmer may have the background encoded as MPEG video and may groom the background prior to having the background placed into theproxy cache140. Therefore, when an application is requested, each of the elements within the scene of the application may be groomed video and the groomed video can easily be stitched together. It should be noted that although two groomers are shown withinFIG. 1 for the content provider and for the linear broadcasters, groomers may be present in other parts of the system.

As shown,video element420 is inserted within the background video frame410 (also for example only; this element could also consist of multiple slices per row). If a macroblock within theoriginal video frame410 references another macroblock in determining its value and the reference macroblock is removed from the frame because thevideo image420 is inserted in its place, the macroblocks value needs to be recalculated. Similarly, if a macroblock references another macroblock in a subsequent frame and that macroblock is removed and other source material is inserted in its place, the macroblock values need to be recalculated. This is addressed by grooming thevideo430. The video frame is processed so that the rows contain multiple slices some of which are specifically sized and located to match the substitute video content. After this process is complete, it is a simple task to replace some of the current slices with the overlay video resulting in a groomed video withoverlay440. The groomed video stream has been specifically defined to address that particular overlay. A different overlay would dictate different grooming parameters. Thus, this type of grooming addresses the process of segmenting a video frame into slices in preparation for stitching. It should be noted that there is never a need to add slices to the overlay element. Slices are only added to the receiving element, that is, the element into which the overlay will be placed. The groomed video stream can contain information about the stream's groomed characteristics. Characteristics that can be provided include: 1. the locations for the upper left and lower right corners of the groomed window. 2. The location of upper left corner only and then the size of the window. The size of the slice accurate to the pixel level.

There are also two ways to provide the characteristic information in the video stream. The first is to provide that information in the slice header. The second is to provide the information in the extended data slice structure. Either of these options can be used to successfully pass the necessary information to future processing stages, such as the virtual machine and stitcher.

FIG. 5 shows the video sequence for a video graphical element before and after grooming. The original incoming encodedstream500 has a sequence of MPEG I-frames510, B-frames530550, and P-frames570 as are known to those of ordinary skill in the art. In this original stream, the I-frame is used as areference512 for all the other frames, both B and P. This is shown via the arrows from the I-frame to all the other frames. Also, the P-frame is used as a reference frame572 for both B-frames. The groomer processes the stream and replaces all the frames with P-frames. First the original I-frame510 is converted to an intracoded P-frame520. Next the B-

frames

530,550 are converted535 to P-

frames

540 and560 and modified to reference only the frame immediately prior. Also, the P-frames570 are modified to move theirreference574 from the original I-frame510 to the newly created P-frame560 immediately in preceding themselves. The resulting P-frame580 is shown in the output stream of groomed encoded frames590.

FIG. 6 is a diagram of a standard MPEG-2 bitstream syntax. MPEG-2 is used as an example and the invention should not be viewed as limited to this example. The hierarchical structure of the bitstream starts at the sequence level. This contains thesequence header600 followed by group of picture (GOP)data605. The GOP data contains theGOP header620 followed bypicture data625. Thepicture data625 contains thepicture header640 followed by theslice data645. Theslice data645 consists of some slice overhead660 followed bymacroblock data665. Finally, themacroblock data665 consists of some macroblock overhead680 followed by block data685 (the block data is broken down further but that is not required for purposes of this reference). Sequence headers act as normal in the groomer. However, there are no GOP headers output of the groomer since all frames are P-frames. The remainder of the headers may be modified to meet the output parameters required.

FIG. 7 provides a flow for grooming the video sequence. First the frame type is determining700: I-frame703 B-frame705, or P-frame707. I-frames703 as do B-frames705 need to be converted to P-frames. In addition, I-frames need to match the picture information that the stitcher requires. For example, this information may indicate the encoding parameters set in the picture header. Therefore, the first step is to modify thepicture header information730 so that the information in the picture header is consistent for all groomed video sequences. The stitcher settings are system level settings that may be included in the application. These are the parameters that will be used for all levels of the bit stream. The items that require modification are provided in the table below:

TABLE 1

Picture Header Information

#	Name	Value

A	Picture Coding Type	P-Frame
B	Intra DC Precision	Match stitcher setting
C	Picture structure	Frame
D	Frame prediction frame DCT	Match stitcher setting
E	Quant scale type	Match stitcher setting
F	Intra VLC format	Match stitcher setting
G	Alternate scan	Normal scan
H	Progressive frame	Progressive scan

Next, the sliceoverhead information740 must be modified. The parameters to modify are given in the table below.

TABLE 2

Slice Overhead Information

#	Name	Value

A	Quantizer	Will change if there is a “scale type”
	Scale Code	change in the picture header.

Next, the macroblock overhead750 information may require modification. The values to be modified are given in the table below.

TABLE 3

Macroblock Information

#	Name	Value

A	Macroblock type	Change the variable length
		code from that for an I
		frame to that for a P frame)
B	DCT type	Set to frame if not already
C	Concealment	Removed
	motion vectors

Finally, theblock information760 may require modification. The items to modify are given in the table below.

TABLE 4

Block Information

#	Name	Value

A	DCT coefficient values	Require updating if there
		were any quantizer changes
		at the picture or slice level.
B	DCT coefficient ordering	Need to be reordered if
		“alternate scan” was changed
		from what it was before.

Once the block changes are complete, the process can start over with the next frame of video.

If the frame type is a B-frame705, the same steps required for an I-frame are also required for the B-frame. However, in addition, themotion vectors770 need to be modified. There are two scenarios: B-frame immediately following an I-frame or P-frame, or a B-frame following another B-frame. Should the B-frame follow either an I or P frame, the motion vector, using the I or P frame as a reference, can remain the same and only the residual would need to change. This may be as simple as converting the forward looking motion vector to be the residual.

For the B-frames that follow another B-frame, the motion vector and its residual will both need to be modified. The second B-frame must now reference the newly converted B to P frame immediately preceding it. First, the B-frame and its reference are decoded and the motion vector and the residual are recalculated. It must be noted that while the frame is decoded to update the motion vectors, there is no need to re-encode the DCT coefficients. These remain the same. Only the motion vector and residual are calculated and modified.

The last frame type is the P-frame. This frame type also follows the same path as an I-frameFIG. 8 diagrams the motion vector modification for macroblocks adjacent to a region boundary. It should be recognized that motion vectors on a region boundary are most relevant to background elements into which other video elements are being inserted. Therefore, grooming of the background elements may be accomplished by the application creator. Similarly, if a video element is cropped and is being inserted into a “hole” in the background element, the cropped element may include motion vectors that point to locations outside of the “hole”. Grooming motion vectors for a cropped image may be done by the content creator if the content creator knows the size that the video element needs to be cropped, or the grooming may be accomplished by the virtual machine in combination with the element renderer and MPEG encoder if the video element to be inserted is larger than the size of the “hole” in the background.

FIG. 8 graphically shows the problems that occur with motion vectors that surround a region that is being removed from a background element. In the example ofFIG. 8, the scene includes two regions: #1800 and #2820. There are two examples of improper motion vector references. In the first instance,region #2820 that is inserting intoregion #1800 (background), usesregion #1800 (background) as a reference formotion840. Thus, the motion vectors inregion #2 need to be corrected. The second instance of improper motion vector references occurs whereregion #1800 usesregion #2820 as a reference formotion860. The groomer removes these improper motion vector references by either re-encoding them using a frame within the same region or converting the macroblocks to be intracoded blocks.

In addition to updating motion vectors and changing frame types, the groomer may also convert field based encoded macroblocks to frame based encoded macroblocks.FIG. 9 shows the conversion of a field based encoded macroblocks to frame based. For reference, a frame based set ofblocks900 is compressed. The compressed block set910 contains the same information in the same blocks but now it is contained in compressed form. On the other hand, a field based macroblock940 is also compressed. When this is done, all the even rows (0, 2, 4, 6) are placed in the upper blocks (0 & 1) while the odd rows (1, 3, 5, 7) are placed in the lower blocks (2&3). When the compressed field basedmacroblock950 is converted to a frame basedmacroblock970, the coefficients need to be moved from one block to another980. That is, the rows must be reconstructed in numerical order rather than in even odd.Rows 1 & 3, which in the field based encoding were inblocks 2 & 3, are now moved back up to

blocks

0 or 1 respectively. Correspondingly,rows 4 & 6 are moved fromblocks 0 & 1 and placed down inblocks 2 & 3.

FIG. 10 shows a second embodiment of the grooming platform. All the components are the same as the first embodiment: groomers1110A and stitcher1140A. The inputs are also the same:input #11103A,input #21105A, andinput #31107A as well as the compositedoutput1280. The difference in this system is that thestitcher1140A provides feedback, both synchronization and frame type information, to each of thegroomers1110A. With the synchronization and frame type information, thestitcher1140A can define a GOP structure that thegroomers1110A follow. With this feedback and the GOP structure, the output of the groomer is no longer P-frames only but can also include I-frames and B-frames. The limitation to an embodiment without feedback is that no groomer would know what type of frame the stitcher was building. In this second embodiment with the feedback from thestitcher1140A, thegroomers1110A will know what picture type the stitcher is building and so the groomers will provide a matching frame type. This improves the picture quality assuming the same data rate and may decrease the data rate assuming that the quality level is kept constant due to more reference frames and less modification of existing frames while, at the same time, reducing the bit rate since B-frames are allowed.

Stitcher

FIG. 11 shows an environment for implementing a stitcher module, such as the stitcher shown inFIG. 1. Thestitcher1200 receives video elements from different sources.Uncompressed content1210 is encoded in anencoder1215, such as the MPEG element encoder shown inFIG. 1 prior to its arrival at thestitcher1200. Compressed or encodedvideo1220 does not need to be encoded. There is, however, the need to separate the audio1217,1227 from the

video

1219,1229 in both cases. The audio is fed into anaudio selector1230 to be included in the stream. The video is fed into aframe synchronization block1240 before it is put into abuffer1250. Theframe constructor1270 pulls data from thebuffers1250 based on input from thecontroller1275. The video out of theframe constructor1270 is fed into amultiplexer1280 along with the audio after the audio has been delayed1260 to align with the video. Themultiplexer1280 combines the audio and video streams and outputs the composited, encodedoutput streams1290 that can be played on any standard decoder. Multiplexing a data stream into a program or transport stream is well known to those familiar in the art. The encoded video sources can be real-time, from a stored location, or a combination of both. There is no requirement that all of the sources arrive in real-time.

FIG. 12 shows an example of three video content elements that are temporally out of sync. In order to synchronize the three elements,element #11300 is used as an “anchor” or “reference” frame. That is, it is used as the master frame and all other frames will be aligned to it (this is for example only; the system could have its own master frame reference separate from any of the incoming video sources). The

output frame timing

1370,1380 is set to match the frame timing ofelement #11300.Element #21320 andelement #31340 do not align withelement #11300. Therefore, their frame start is located and they are stored in a buffer. For example,element #21320 will be delayed one frame so an entire frame is available before it is composited along with the reference frame.Element #3 is much slower than the reference frame.Element #3 is collected over two frames and presented over two frames. That is, each frame ofelement #31340 is displayed for two consecutive frames in order to match the frame rate of the reference frame. Conversely if a frame, not shown, was running at twice the rate of the reference frame, then every other frame would be dropped (not shown). More than likely all elements are running at almost the same speed so only infrequently would a frame need to be repeated or dropped in order to maintain synchronization.

FIG. 13 shows an example compositedvideo frame1400. In this example, the frame is made up of 40 macroblocks perrow1410 with 30 rows perpicture1420. The size is used as an example and it not intended to restrict the scope of the invention. The frame includes abackground1430 that haselements1440 composited in various locations. Theseelements1440 can be video elements, static elements, etc. That is, the frame is constructed of a full background, which then has particular areas replaced with different elements. This particular example shows four elements composited on a background.

FIG. 14 shows a more detailed version of the screen illustrating the slices within the picture. The diagram depicts a picture consisting of 40 macroblocks per row and 30 rows per picture (non-restrictive, for illustration purposes only). However, it also shows the picture divided up into slices. The size of the slice can be a full row1590 (shown as shaded) or a few macroblocks within a row1580 (shown as rectangle with diagonal lines insideelement #41528). Thebackground1530 has been broken into multiple regions with the slice size matching the width of each region. This can be better seen by looking atelement #11522.Element #11522 has been defined to be twelve macroblocks wide. The slice size for this region for both thebackground1530 andelement #11522 is then defined to be that exact number of macroblocks.Element #11522 is then comprised of six slices, each slice containing 12 macroblocks. In a similar fashion,element #21524 consists of four slices of eight macroblocks per slice;element #31526 is eighteen slices of 23 macroblocks per slice; andelement #41528 is seventeen slices of five macroblocks per slice. It is evident that thebackground1530 and the elements can be defined to be composed of any number of slices which, in turn, can be any number of macroblocks. This gives full flexibility to arrange the picture and the elements in any fashion desired. The process of determining the slice content for each element along with the positioning of the elements within the video frame are determined by the virtual machine ofFIG. 1 using the AVML file.

FIG. 15 shows the preparation of thebackground1600 by the virtual machine in order for stitching to occur in the stitcher. The virtual machine gathers an uncompressed background based upon the AVML file and forwards the background to the element encoder. The virtual machine forwards the locations within the background where elements will be placed in the frame. As shown thebackground1620 has been broken into a particular slice configuration by the virtual machine with a hole(s) that exactly aligns with where the element(s) will (are to) be placed prior to passing the background to the element encoder. The encoder compresses the background leaving a “hole” or “holes” where the element(s) will be placed. The encoder passes the compressed background to memory. The virtual machine then access the memory and retrieves each element for a scene and passes the encoded elements to the stitcher along with a list of the locations for each slice for each of the elements. The stitcher takes each of the slices and places the slices into the proper position.

This particular type of encoding is called “slice based encoding”. A slice based encoder/virtual machine is one that is aware of the desired slice structure of the output frame and performs its encoding appropriately. That is, the encoder knows the size of the slices and where they belong. It knows where to leave holes if that is required. By being aware of the desired output slice configuration, the virtual machine provides an output that is easily stitched.

FIG. 16 shows the compositing process after the background element has been compressed. Thebackground element1700 has been compressed into seven slices with a hole where theelement1740 is to be placed. Thecomposite image1780 shows the result of the combination of thebackground element1700 andelement1740. Thecomposite video frame1780 shows the slices that have been inserted in grey. Although this diagram depicts a single element composited onto a background, it is possible to composite any number of elements that will fit onto a user's display. Furthermore, the number of slices per row for the background or the element can be greater than what is shown. The slice start and slice end points of the background and elements must align.

FIG. 17 is a diagram showing different macroblock sizes between the background element1800 (24 pixels by 24 pixels) and the added video content element1840 (16 pixels by 16 pixels). The compositedvideo frame1880 shows two cases. Horizontally, the pixels align as there are 24 pixels/block×4 blocks=96 pixels wide in thebackground800 and 16 pixels/block*6 blocks=96 pixels wide for thevideo content element1840. However, vertically, there is a difference. Thebackground1800 is 24 pixels/block*3 blocks=72 pixels tall. Theelement1840 is 16 pixels/block*4 blocks=64 pixels tall. This leaves a vertical gap of 8pixels1860. The stitcher is aware of such differences and can extrapolate either the element or the background to fill the gap. It is also possible to leave a gap so that there is a dark or light border region. Any combination of macroblock sizes is acceptable even though this example uses macroblock sizes of 24×24 and 16×16. DCT based compression formats may rely on macroblocks of sizes other than 16×16 without deviating from the intended scope of the invention. Similarly, a DCT based compression format may also rely on variable sized macroblocks for temporal prediction without deviating from the intended scope of the invention Finally, frequency domain representations of content may also be achieved using other Fourier related transforms without deviating from the intended scope of the invention.

It is also possible for there to be an overlap in the composited video frame. Referring back toFIG. 17, theelement1840 consisted of four slices. Should this element actually be five slices, it would overlap with thebackground element1800 in the compositedvideo frame1880. There are multiple ways to resolve this conflict with the easiest being to composite only four slices of the element and drop the fifth. It is also possible to composite the fifth slice into the background row, break the conflicting background row into slices and remove the background slice that conflicts with the fifth element slice (then possibly add a sixth element slice to fill any gap).

The possibility of different slice sizes requires the compositing function to perform a check of the incoming background and video elements to confirm they are proper. That is, make sure each one is complete (e.g., a full frame), there are no sizing conflicts, etc.

FIG. 18 is a diagram depicting elements of a frame. A simple compositedpicture1900 is composed of anelement1910 and abackground element1920. To control the building of the video frame for the requested scene, the stitcher builds adata structure1940 based upon the position information for each element as provided by the virtual machine. Thedata structure1940 contains a linked list describing how many macroblocks and where the macroblocks are located. For example, the data row11943 shows that the stitcher should take 40 macroblocks from buffer B, which is the buffer for the background.Data row21945 should take 12 macroblocks from buffer B, then 8 macroblocks from buffer E (the buffer for element1910), and then another 20 macroblocks from buffer B. This continues down to thelast row1947 wherein the stitcher uses the data structure to take 40 macroblocks from buffer B. Thebuffer structure1970 has separate areas for each background or element. TheB buffer1973 contains all the information for stitching in B macroblocks. TheE buffer1975 has the information for stitching in E macroblocks.

FIG. 19 is a flow chart depicting the process for building a picture from multiple encoded elements. Thesequence2000 begins by starting thevideo frame composition2010. First the frames are synchronized2015 and then eachrow2020 is built up by grabbing theappropriate slice2030. The slice is then inserted2040 and the system checks to see if it is the end of therow2050. If not, the process goes back to “fetch next slice”block2030 until the end ofrow2050 is reached. Once the row is complete, the system checks to see if it is the end offrame2080. If not, the process goes back to the “for each row”2020 block. Once the frame is complete, the system checks if it is the end of thesequence2090 for the scene. If not, it goes back to the “compose frame”2010 step. If it is, the frame or sequence of video frames for the scene is complete2090. If not, it repeats the frame building process. If the end ofsequence2090 has been reached, the scene is complete and the process ends or it can start the construction of another frame.

The performance of the stitcher can be improved (build frames faster with less processor power) by providing the stitcher advance information on the frame format. For example, the virtual machine may provide the stitcher with the start location and size of the areas in the frame to be inserted. Alternatively, the information could be the start location for each slice and the stitcher could then figure out the size (the difference between the two start locations). This information could be provided externally by the virtual machine or the virtual machine could incorporate the information into each element. For instance, part of the slice header could be used to carry this information. The stitcher can use this foreknowledge of the frame structure to begin compositing the elements together well before they are required.

FIG. 20 shows a further improvement on the system. As explained above in the groomer section, the graphical video elements can be groomed thereby providing stitchable elements that are already compressed and do not need to be decoded in order to be stitched together. InFIG. 20, a frame has a number of encodedslices2100. Each slice is a full row (this is used as an example only; the rows could consist of multiple slices prior to grooming). The virtual machine in combination with the AVML file determines that there should be anelement2140 of a particular size placed in a particular location within the composited video frame. The groomer processes theincoming background2100 and converts the full-row encoded slices to smaller slices that match the areas around and in the desiredelement2140 location. The resulting groomedvideo frame2180 has a slice configuration that matches the desiredelement2140. The stitcher then constructs the stream by selecting all the slices except #3 and #6 from the groomedframe2180. Instead of those slices, the stitcher grabs theelement2140 slices and uses those in its place. In this manner, the background never leaves the compressed domain and the system is still able to composite theelement2140 into the frame.

FIG. 21 shows the flexibility available to define the element to be composited. Elements can be of different shapes and sizes. The elements need not reside contiguously and in fact a single element can be formed from multiple images separated by the background. This figure shows a background element2230 (areas colored grey) that has had a single element2210 (areas colored white) composited on it. In this diagram, the compositedelement2210 has areas that are shifted, are different sizes, and even where there are multiple parts of the element on a single row. The stitcher can perform this stitching just as if there were multiple elements used to create the display. The slices for the frame are labeled contiguously S1-S45. These include the slice locations where the element will be placed. The element also has its slice numbering from ES1-ES14. The element slices can be placed in the background where desired even though they are pulled from a single element file.

The source for the element slices can be any one of a number of options. It can come from a real-time encoded source. It can be a complex slice that is built from separate slices, one having a background and the other having text. It can be a pre-encoded element that is fetched from a cache. These examples are for illustrative purposes only and are not intended to limit the options for element sources.

FIG. 22 shows an embodiment using agroomer2340 for grooming linear broadcast content. The content is received by thegroomer2340 in real-time. Each channel is groomed by thegroomer2340 so that the content can be easily stitched together. Thegroomer2340 ofFIG. 22 may include a plurality of groomer modules for grooming all of the linear broadcast channels. The groomed channels may then be multicast to one or

more processing offices

2310,2320,2330 and one or more virtual machines within each of the processing offices for use in applications. As shown, client devices request an application for receipt of amosaic2350 of linear broadcast sources and/or other groomed content that are selected by the client. A mosaic2350 is a scene that includes abackground frame2360 that allows for viewing of a plurality of sources2371-2376 simultaneously as shown inFIG. 23. For example, if there are multiple sporting events that a user wishes to watch, the user can request each of the channels carrying the sporting events for simultaneous viewing within the mosaic. The user can even select an MPEG object (edit)2380 and then edit the desired content sources to be displayed. For example, the groomed content can be selected from linear/live broadcasts and also from other video content (i.e. movies, pre-recorded content etc.). A mosaic may even include both user selected material and material provided by the processing office/session processor, such as, advertisements. As shown inFIG. 22, client devices2301-2305 each request a mosaic that includeschannel1. Thus, the multicast groomed content forchannel1 is used by different virtual machines and different processing offices in the construction of personalized mosaics.

When a client device sends a request for a mosaic application, the processing office associated with the client device assigns a processor/virtual machine for the client device for the requested mosaic application. The assigned virtual machine constructs the personalized mosaic by compositing the groomed content from the desired channels using a stitcher. The virtual machine sends the client device an MPEG stream that has a mosaic of the channels that the client has requested. Thus, by grooming the content first so that the content can be stitched together, the virtual machines that create the mosaics do not need to first decode the desired channels, render the channels within the background as a bitmap and then encode the bitmap.

An application, such as a mosaic, can be requested either directly through a client device or indirectly through another device, such as a PC, for display of the application on a display associated with the client device. The user could log into a website associated with the processing office by providing information about the user's account. The server associated with the processing office would provide the user with a selection screen for selecting an application. If the user selected a mosaic application, the server would allow the user to select the content that the user wishes to view within the mosaic. In response to the selected content for the mosaic and using the user's account information, the processing office server would direct the request to a session processor and establish an interactive session with the client device of the user. The session processor would then be informed by the processing office server of the desired application. The session processor would retrieve the desired application, the mosaic application in this example, and would obtain the required MPEG objects. The processing office server would then inform the session processor of the requested video content and the session processor would operate in conjunction with the stitcher to construct the mosaic and provide the mosaic as an MPEG video stream to the client device. Thus, the processing office server may include scripts or application for performing the functions of the client device in setting up the interactive session, requesting the application, and selecting content for display. While the mosaic elements may be predetermined by the application, they may also be user configurable resulting in a personalized mosaic.

FIG. 24 is a diagram of an IP based content delivery system. In this system, content may come from abroadcast source2400, aproxy cache2415 fed by acontent provider2410, Network Attached Storage (NAS)2425 containing configuration andmanagement files2420, or other sources not shown. For example, the NAS may include asset metadata that provides information about the location of content. This content could be available through aload balancing switch2460. BladeSession processors/virtual machines2460 can perform different processing functions on the content to prepare it for delivery. Content is requested by the user via a client device such as aset top box2490. This request is processed by thecontroller2430 which then configures the resources and path to provide this content. Theclient device2490 receives the content and presents it on the user'sdisplay2495.

FIG. 25 provides a diagram of a cable based content delivery system. Many of the components are the same: a controller2530,broadcast source2500, acontent provider2510 providing their content via aproxy cache2515, configuration andmanagement files2520 via a file server NAS2525,session processors2560, load balancing switch2550, a client device, such as aset top box2590, and adisplay2595. However, there are also a number of additional pieces of equipment required due to the different physical medium. In this case the added resources include:QAM modulators2575, areturn path receiver2570, a combiner anddiplexer2580, and a Session and Resource Manager (SRM)2540.QAM upconverter2575 are required to transmit data (content) downstream to the user. These modulators convert the data into a form that can be carried across the coax that goes to the user. Correspondingly, thereturn path receiver2570 also is used to demodulate the data that comes up the cable from theset top2590. The combiner anddiplexer2580 is a passive device that combines the downstream QAM channels and splits out the upstream return channel. The SRM is the entity that controls how the QAM modulators are configured and assigned and how the streams are routed to the client device.

These additional resources add cost to the system. As a result, the desire is to minimize the number of additional resources that are required to deliver a level of performance to the user that mimics a non-blocking system such as an IP network. Since there is not a one-to-one correspondence between the cable network resources and the users on the network, the resources must be shared. Shared resources must be managed so they can be assigned when a user requires a resource and then freed when the user is finished utilizing that resource. Proper management of these resources is critical to the operator because without it, the resources could be unavailable when needed most. Should this occur, the user either receives a “please wait” message or, in the worst case, a “service unavailable” message.

FIG. 26 is a diagram showing the steps required to configure a new interactive session based on input from a user. This diagram depicts only those items that must be allocated or managed or used to do the allocation or management. A typical request would follow the steps listed below:

(1) TheSet Top2609 requests content2610 from theController2607

(2) TheController2607 requests QAM bandwidth2620 from theSRM2603

(3) TheSRM2603 checks QAM availability2625

(4) TheSRM2603 allocates theQAM modulator2630

(5) The QAM modulator returnsconfirmation2635

(6) TheSRM2603 confirmsQAM allocation success2640 to the Controller

(7) The Controller407 allocates theSession processor2650

(8) The Session processor confirmsallocation success2653

(9) TheController2607 allocates thecontent2655

(10) TheController2607 configures2660 theSet Top2609. This includes:

- a. Frequency to tune
- b. Programs to acquire or alternatively PIDs to decode
- c. IP port to connect to the Session processor for keystroke capture

(11) TheSet Top2609 tunes to the channel2663

(12) TheSet Top2609 confirmssuccess2665 to theController2607

TheController2607 allocates the resources based on a request for service from aset top box2609. It frees these resources when the set top or server sends an “end of session”. While thecontroller2607 can react quickly with minimal delay, theSRM2603 can only allocate a set number of QAM sessions per second i.e. 200. Demand that exceeds this rate results in unacceptable delays for the user. For example, if 500 requests come in at the same time, the last user would have to wait 5 seconds before their request was granted. It is also possible that rather than the request being granted, an error message could be displayed such as “service unavailable”.

While the example above describes the request and response sequence for an AVDN session over a cable TV network, the example below describes a similar sequence over an IPTV network. Note that the sequence in itself is not a claim, but rather illustrates how AVDN would work over an IPTV network.

- (1) Client device requests content from the Controller via a Session Manager (i.e. controller proxy).
- (2) Session Manager forwards request to Controller.
- (3) Controller responds with the requested content via Session Manager (i.e. client proxy).
- (4) Session Manager opens a unicast session and forwards Controller response to client over unicast IP session.
- (5) Client device acquires Controller response sent over unicast IP session.
- (6) Session manager may simultaneously narrowcast response over multicast IP session to share with other clients on node group that request same content simultaneously as a bandwidth usage optimization technique.

FIG. 27 is a simplified system diagram used to break out each area for performance improvement. This diagram focuses only on the data and equipment that will be managed and removes all other non-managed items. Therefore, the switch, return path, combiner, etc. are removed for the sake of clarity. This diagram will be used to step through each item, working from the end user back to the content origination.

A first issue is the assignment ofQAMs2770 andQAM channels2775 by theSRM2720. In particular, the resources must be managed to prevent SRM overload, that is, eliminating the delay the user would see when requests to theSRM2720 exceed its sessions per second rate.

To prevent SRM “overload”, “time based modeling” may be used. For time based modeling, theController2700 monitors the history of past transactions, in particular, high load periods. By using this previous history, theController2700 can predict when a high load period may occur, for example, at the top of an hour. TheController2700 uses this knowledge to pre-allocate resources before the period comes. That is, it uses predictive algorithms to determine future resource requirements. As an example, if theController2700 thinks 475 users are going to join at a particular time, it can start allocating thoseresources 5 seconds early so that when the load hits, the resources have already been allocated and no user sees a delay.

Secondly, the resources could be pre-allocated based on input from an operator. Should the operator know a major event is coming, e.g., a pay per view sporting event, he may want to pre-allocate resources in anticipation. In both cases, theSRM2720 releasesunused QAM2770 resources when not in use and after the event.

Thirdly,QAMs2770 can be allocated based on a “rate of change” which is independent of previous history. For example, if thecontroller2700 recognizes a sudden spike in traffic, it can then request more QAM bandwidth than needed in order to avoid the QAM allocation step when adding additional sessions. An example of a sudden, unexpected spike might be a button as part of the program that indicates a prize could be won if the user selects this button.

Currently, there is one request to theSRM2720 for each session to be added. Instead thecontroller2700 could request thewhole QAM2770 or a large part of a single QAM's bandwidth and allow this invention to handle the data within thatQAM channel2775. Since one aspect of this system is the ability to create a channel that is only 1, 2, or 3 Mb/sec, this could reduce the number of requests to theSRM2720 by replacing up to 27 requests with a single request.

The user will also experience a delay when they request different content even if they are already in an active session. Currently, if aset top2790 is in an active session and requests a new set ofcontent2730, theController2700 has to tell theSRM2720 to de-allocate theQAM2770, then theController2700 must de-allocate thesession processor2750 and thecontent2730, and then request anotherQAM2770 from theSRM2720 and then allocate adifferent session processor2750 andcontent2730. Instead, thecontroller2700 can change thevideo stream2755 feeding theQAM modulator2770 thereby leaving the previously established path intact. There are a couple of ways to accomplish the change. First, since theQAM Modulators2770 are on a network so thecontroller2700 can merely change thesession processor2750 driving theQAM2770. Second, thecontroller2700 can leave thesession processor2750 to set top2790 connection intact but change thecontent2730 feeding thesession processor2750, e.g., “CNN Headline News” to “CNN World Now”. Both of these methods eliminate the QAM initialization and Set Top tuning delays.

Thus, resources are intelligently managed to minimize the amount of equipment required to provide these interactive services. In particular, the Controller can manipulate thevideo streams2755 feeding theQAM2770. By profiling thesestreams2755, theController2700 can maximize the channel usage within aQAM2770. That is, it can maximize the number of programs in eachQAM channel2775 reducing wasted bandwidth and the required number ofQAMs2770. There are three primary means to profile streams: formulaic, pre-profiling, and live feedback.

The first profiling method, formulaic, consists of adding up the bit rates of the various video streams used to fill aQAM channel2775. In particular, there may be many video elements that are used to create asingle video stream2755. The maximum bit rate of each element can be added together to obtain an aggregate bit rate for thevideo stream2755. By monitoring the bit rates of allvideo streams2755, theController2700 can create a combination ofvideo streams2755 that most efficiently uses aQAM channel2775. For example, if there were four video streams2755: two that were 16 Mb/sec and two that were 20 Mb/sec then the controller could best fill a 38.8 Mb/sec QAM channel2775 by allocating one of each bit rate per channel. This would then require twoQAM channels2775 to deliver the video. However, without the formulaic profiling, the result could end up as 3QAM channels2775 as perhaps the two 16 Mb/sec video streams2755 are combined into a single 38.8 Mb/sec QAM channel2775 and then each 20 Mb/sec video stream2755 must have its own 38.8 Mb/sec QAM channel2775.

A second method is pre-profiling. In this method, a profile for thecontent2730 is either received or generated internally. The profile information can be provided in metadata with the stream or in a separate file. The profiling information can be generated from the entire video or from a representative sample. Thecontroller2700 is then aware of the bit rate at various times in the stream and can use this information to effectively combinevideo streams2755 together. For example, if twovideo streams2755 both had a peak rate of 20 Mb/sec, they would need to be allocated to different 38.8 Mb/sec QAM channels2775 if they were allocated bandwidth based on their peaks. However, if the controller knew that the nominal bit rate was 14 Mb/sec and knew their respective profiles so there were no simultaneous peaks, thecontroller2700 could then combine thestreams2755 into a single 38.8 Mb/sec QAM channel2775. The particular QAM bit rate is used for the above examples only and should not be construed as a limitation.

A third method for profiling is via feedback provided by the system. The system can inform thecontroller2700 of the current bit rate for all video elements used to build streams and the aggregate bit rate of the stream after it has been built. Furthermore, it can inform thecontroller2700 of bit rates of stored elements prior to their use. Using this information, thecontroller2700 can combinevideo streams2755 in the most efficient manner to fill aQAM channel2775.

It should be noted that it is also acceptable to use any or all of the three profiling methods in combination. That is, there is no restriction that they must be used independently.

The system can also address the usage of the resources themselves. For example, if asession processor2750 can support 100 users and currently there are 350 users that are active, it requires four session processors. However, when the demand goes down to say 80 users, it would make sense to reallocate those resources to asingle session processor2750, thereby conserving the remaining resources of three session processors. This is also useful in failure situations. Should a resource fail, the invention can reassign sessions to other resources that are available. In this way, disruption to the user is minimized.

The system can also repurpose functions depending on the expected usage. Thesession processors2750 can implement a number of different functions, for example, process video, process audio, etc. Since thecontroller2700 has a history of usage, it can adjust the functions on thesession processors2700 to meet expected demand. For example, if in the early afternoons there is typically a high demand for music, thecontroller2700 can reassignadditional session processors2750 to process music in anticipation of the demand. Correspondingly, if in the early evening there is a high demand for news, thecontroller2700 anticipates the demand and reassigns thesession processors2750 accordingly. The flexibility and anticipation of the system allows it to provide the optimum user experience with the minimum amount of equipment. That is, no equipment is idle because it only has a single purpose and that purpose is not required.

FIG. 28 shows a managed broadcast content satellite network that can provide interactive content to subscribers through an unmanaged IP network. A managed network is a communications network wherein the content that is transmitted is determined solely by the service provider and not by the end-user. Thus, the service provider has administrative control over the presented content. In a managed network, a user may select a channel from a plurality of channels broadcast by the service provider, but the overall content is determined by the service provider and the user can not access any other content outside of the network. A managed network is a closed network. Managed networks may be satellite networks, cable networks and IP television networks for example. An unmanaged network allows a user to request and receive content from a party other than the service provider. For example, the Internet is an unmanaged network, wherein a user that is in communication with the Internet can select to receive content from one of a plurality of sources and is not limited by content that is provided by an Internet Service Provider (ISP). These definitions are independent of the physical interconnections and are logical associations. In fact, both a managed network and an unmanaged network may operate over the same physical communications link.

As shown inFIG. 28, broadcast content is uploaded to asatellite2800 by a managed network office2801 on one or more designated channels. A channel may be a separate frequency or a channel may be an association of data that is related together by a delimiter (i.e. header information). The receivingsatellite2800 retransmits the broadcast content including a plurality of channels that can be selected by a subscriber. Asatellite receiver2802 at the subscriber's home receives the transmission and forwards the transmission to aclient device2803, such as a set-top box. The client device decodes the satellite transmission and provides the selected channel for view on the subscriber'sdisplay device2804.

Within the broadcast content of the broadcast transmission are one or more triggers. A trigger is a designator of possible interactive content. For example, a trigger may accompany an advertisement that is either inserted within the broadcast content or is part of a frame that contains broadcast content. Triggers may be associated with one or more video frames and can be embedded within the header for one or more video frames, may be part of an analog transmission signal, or be part of the digital data depending upon the medium on which the broadcast content is transmitted. In response to the advertisement, a user may use a user input device (not shown), such as a remote control, to request interactive content related to the advertisement. In other embodiments, the trigger may automatically cause an interactive session to begin and the network for receiving content to be switched between a managed and unmanaged network. In response, theclient device2803 switches between receiving thebroadcast content2805 from thesatellite network2800 and receiving and transmitting content via anunmanaged network2806, such as the Internet. The client device may include a single box that receives and decodes transmissions from the managed network and also includes two-way communication with an unmanaged network. Thus, the client device may include two separate receivers and at least one transmitter. The client device may have a single shared processor for both the managed and unmanaged networks or there may be separate processors within the client device. A software module controls the switching between the two networks.

As such, the software module is a central component that communicates with both networks. In alternative embodiments, separate client decoding boxes may be employed for the managed and unmanaged networks wherein the two boxes include a communication channel. For example, the two boxes may communicate via IP or UDP protocols wherein a first box may send an interrupt to the second box or send an output suppression signal. The boxes may be provided with discovery agents that recognize when ports are connected together and all the two boxes to negotiate connection. The communication channel allows the two boxes to communicate so that the output of the boxes may be switched. Thus, each box operates using a common communication protocol that allows for the box to send commands and control at least the output port of the other box. It should be recognized that the description of the present embodiment with respect to satellite-based systems is for exemplary purposes only and that the description may be readily applied to embodiments that include both managed and unmanaged networks.

When the user requests the interactive content by sending a transmission to theclient device2802, theclient device2802 extracts the trigger and transmits the trigger through the unmanaged network to aprocessing office2810. Theprocessing office2810 either looks-up the associated internet address for the interactive content in a look-up table or extracts the internet address from the received transmission from the client device. The processing office forwards the request to theappropriate content server2820 through theInternet2830. The interactive content is returned to theprocessing office2810 and theprocessing office2810 processes the interactive content into a format that is compatible with theclient device2803. For example, theprocessing office2810 may encode transcoding by scaling and stitching the content as an MPEG video stream as discussed above. The video stream can then be transmitted from theprocessing office2810 to theclient device2803 over theunmanaged network2806 as a series of IP packets. In such an embodiment, theclient device2802 includes a satellite decoder and also a port for sending and receiving communications via an unmanaged IP network. When the requested interactive content is received by theclient device2803, the client device can switch between outputting the satellite broadcast channel and outputting the interactive content received via the unmanaged network. In certain embodiments, the audio content may continue to be received by the satellite transmission and only the video is switched between the satellite communications channel and the IP communications channel. The audio channel from the satellite transmission will be mixed with the video received through the unmanaged IP network. In other embodiments, both the audio and video signal are switched between the managed and unmanaged networks.

It should be recognized by one of ordinary skill in the art that the triggers need not be limited to advertisements, but may relate to other forms of interactive content. For example, a broadcast transmission may include a trigger during a sporting event that allows a user to retrieve interactive content regarding statistics for a team playing the sporting event.

In some embodiments, when a trigger is identified within the transmission, an interactive session is automatically established and interactive content from two or more sources is merged together as explained above. The interactive content is then provided to the client device through the communication network and is decoded. Thus, the user does not need to provide input to the client device before an interactive session is established.

In certain embodiments, the client device may receive content from both the managed and unmanaged network and may replace information from one with the other. For example, broadcast content may be transmitted over the managed network with identifiable insertion points (e.g. time codes, header information etc.) for advertisements. The broadcast content may contain an advertisement at the insertion point and the client device can replace the broadcast advertisement with an advertisement transmitted over the managed network wherein the client device switches between the managed and unmanaged networks for the length of the advertisement.

FIG. 29 shows another environment where aclient device2902 receives broadcast content through a managednetwork2900 and interactive content may be requested and is provided through anunmanaged network2901. In this embodiment, aprocessing office2910, delivers broadcast content via acable system2900. The broadcast content being selectable by a user based upon interaction with a set-top box2902 that provides for selection of one of a plurality of broadcasts programs. One or more of the broadcast programs include a trigger within the broadcast (i.e. within a header associated with the broadcast, within the digital data, or within the analog signal). When theclient device2910 receives the broadcast signal and outputs the selected broadcast content, a program running on theclient device2902 identifies the trigger and stores the trigger in a temporary buffer. If the trigger changes as the broadcast program progresses, the client device will update the buffer. For example, the trigger may have a temporal expiration. The trigger may be associated with a number of frames of video from the video content and therefore, is temporally limited. In other embodiments, the trigger may be sent to and stored at the processing office. In such an embodiment, only one copy of the triggers for each broadcast channel need be stored.

In other embodiments, the trigger that causes a request for an interactive session may occur external to the broadcast content. For example, the request may result in response to a user's interaction with an input device, such as a remote control. The signal produced by the remote control is sent to the client device and the client device responds by switching between receiving broadcast content over the managed network to making a request for an interactive session over the unmanaged network. The request for the interactive session is transmitted over a communication network to a processing office. The processing office assigns a processor and a connection is negotiated between the processor and the client device. The client device might be a set-top box, media gateway, consumer electronic device or other device that can transmit through a network, such as the Internet, remote control signals and receive and decode a standard MPEG encoded video stream. The processor at the processing office gathers the interactive content from two or more sources. For example, an AVML template may be used that includes MPEG objects and MPEG video content may be retrieved from a locally stored source or a source that is reachable through a network connection. For example, the network may be an IP network and the MPEG video content may be stored on a server within the Internet. The assigned processor causes the interactive content to be stitched together. The stitched content is then transmitted via the network connection to the client device, which decodes and presents the decoded content to a display device.

As an example, a television that includes an internal or external QAM tuner receives a broadcast cable television signal. The broadcast cable television signal includes one or more triggers or a user uses an input device to create a request signal. The television either parses the trigger during decoding of the broadcast cable television signal or receives the request from the input device and as a result causes a signal to be generated to an IP device that is coupled to the Internet (unmanaged network). The television suppresses output of the broadcast cable television signal to the display. The IP device may be a separate external box or internal to the television that responds to the trigger or request signal by requesting an interactive session with a processing office located over an Internet connection. A processor is assigned by the processing office and a connection is negotiated between the IP device and the assigned processor. The assigned processor generates the interactive content from two or more sources and produces an MPEG elementary stream. The MPEG elementary stream is transmitted to the IP device. The IP device then outputs the MPEG elementary stream to the television that decodes and presents the interactive content to the television display. In response to further interaction by the user with an input device updates to the elementary stream can be achieved by the assigned processor. When the user decides to return to the broadcast television content or the interactive content finishes, the television, suspends suppression of the broadcast television content signal and the television decodes and presents the broadcast television signal to the display. Thus, the system switches between a managed network and an unmanaged network as the result of a trigger or request signal wherein interactive content signal is created from two or more sources at a location remote from the television.

It should be recognized by one of ordinary skill in the art that the foregoing embodiments are not restricted to satellite and cable television systems and the embodiments may be equally applicable to IPTV networks, such as IPTV networks that use the telephone system. In such an embodiment, the IPTV network would be the managed network and the unmanaged network would be a connection to the Internet (e.g. a DSL modem, wireless Internet network connection; Ethernet Internet connection).

Adaptive Bitrate Detection and Control

The embodiments of the invention described above may be used in connection with thin client devices. Thin client devices include hardware, software, or a combination of hardware and software for receiving and decoding encoded audio and video for display on a display device, and for transmitting keystroke and button-press commands to a processing office. Typically, thin clients are designed to be inexpensive for mass production, and to be uncomplicated for use in situations permitting only a basic display of audiovisual content, although more expensive and complicated devices having other functions (for example, smartphones) may be employed in accordance with the methods and systems described herein.

The use of an unmanaged network in a thin client environment includes restrictions that limit the ability of a television broadcaster to provide interactive content. The restriction that most affects the quality of the end user experience is that unmanaged network may experience rapid and unpredictable variations in available channel capacity (bandwidth) between the client device and the interactive service provider. For this reason, it is desirable to provide a system and methods that compensate for these variations to provide an optimal user experience, while using a minimum of algorithmic complexity in the client device.

These restrictions may be addressed using adaptive bitrate control in both the client and server. Generally, an interactive service provider connected with a client device over an unmanaged network takes regular measurements of the connection bandwidth. When changes in this bandwidth occur, the server varies the transmission bitrate of the service. The client device makes corresponding bandwidth measurements using data provided within the received interactive service data, and adjusts its audiovisual output accordingly. Thus, the quality of the interactive service may be dynamically improved or degraded to maintain an optimal user experience according to the variable transmission capabilities of the unmanaged network. If the transmission capabilities become so limited as to prevent an optimal user experience for a particular interactive service, the interactive service provider may provide a “service unavailable” message, or suggest alternate services that the user might wish to use according to business rules that reflect the user's account information or preferences.

In accordance with exemplary embodiments of the invention, adaptive bitrate control is provided on the video portion of an audiovisual service, keeping a constant audio bitrate. Such an approach has several advantages. First, a fixed audio bitrate guarantees a consistent quality of at least a portion of the end user audiovisual experience, even using an unmanaged network. Second, transmission of a fixed audio bitrate a minimum of information must be communicated to the client during user interactivity with the service. Third, the client device may compare the expected, fixed audio bitrate against the received audio data to dynamically measure the actual performance of the unmanaged network. Fourth, varying the bitrate of only the video portion of an audiovisual service requires fewer processing resources by the service provider than would varying both the audio and video portions separately. To embody these advantages, adaptive bitrate control is provided by a stitcher (such asstitcher115,stitcher340, orstitcher1140A) that stitches together the video components of the transmitted interactive service. It will be understood by a person having ordinary skill in the art that other physical or logical components of an interactive service may be used to provide this function.

FIG. 30 shows a server embodiment of the invention in which a stitcher performs adaptive bitrate detection and control. MPEG encodedaudio3010 andvideo3012 are input to the system. In the stitcher, thevideo3012 is stitched and encoded as described above in detail. The encoding process in the stitcher makes use of certain encoding parameters that affect the eventual bitrate of the video stream, such as image data quantization and number of frames per second (frame rate).Encoding bitrate controller3020 varies these parameters according to the available bandwidth, obtained via a process described below, to optimize the end user experience. Once the video has been encoded using the optimal parameters, it is combined with the audio3010 in a hardware orsoftware transport multiplexer3030, thereby forming an audiovisual data stream capable of being decoded by a client device embodiment of the invention. The stream is sent totransmission controller3040 for transmission. Thetransmission controller3040 uses areliable transmission protocol3050, such as TCP, to transmit the audiovisual data to the client device using theunmanaged network3060, as shown.Transmission controller3040 also obtains, fromtransmission protocol3050, data Δ regarding the transmission that permits it to calculate the current bandwidth utilization. This bandwidth is then provided to theencoding bitrate controller3020, as indicated byarrow3070, as an input into the calculation of the optimal video encoding parameters.

Thetransmission controller3040 calculates bandwidth as a function of data Δ regarding the transmission of the audiovisual stream, and time. Thus, bandwidth is given by a formula F(Δ, t). In one embodiment that uses a reliable transmission protocol, data to be sent are buffered in the event retransmission is necessary. As data are added to the buffer by thetransmission controller3040, and removed from the buffer by the transmission protocol, the amount of data in the buffer changes. As an equation, if buf(t) is the size of the buffer at a given time t, then buf(t₂)=buf(t₁)+new(t₁, t₂)−trans(t₁, t₂), where new(t₁, t₂) is the amount of data added to the buffer between times t₁, t₂; and trans(t₁, t₂) is the amount of data transmitted to the client device between times t₁, t₂. Noting that bandwidth is the amount of data transmitted to the client device per unit time, one may rearrange this to obtain a formula for bandwidth: F(Δ, t)=trans(t₁, t₂)/(t₂−t₁)=(new(t₁, t₂)−Δ)/(t₂−t₁), where Δ=buf(t₂)−buf(t₁) is the change in the size of the buffer. As noted above, the value of Δ may be obtained fromtransmission protocol3050. The value of new(t₁, t₂) may be monitored bytransmission controller3040, thereby providing all of the information necessary to calculate bandwidth from successive sampled values of Δ. Thetransmission controller3040 provides bandwidth values F(Δ, t) to theencoding bitrate controller3020 either synchronously or asynchronously.

Theencoding bitrate controller3020 can set encoding parameters by any appropriate algorithm that uses the bandwidth value provided3070 by thetransmission controller3040. In particular, an overall quantization level of video frames may be increased in response to an increased available bandwidth, and quantization decreased when bandwidth decreases. Overall quantization levels that vary in time as bandwidth changes, like those in accordance with embodiments of the invention, may be useful in conjunction with quantization levels that vary in space. One example of space-varying quantization is disclosed in U.S. Pat. No. 6,831,947, which teaches determining optimized quantization values for individual macroblocks within a single video frame, based on the human visual system and an overall quantization level. Theencoding bitrate controller3020 may also change a video frame rate to correspond to a changing channel capacity for video data. Thus, if bandwidth decreases by half, theencoding bitrate controller3020 may reduce the frame rate by half, so that only half as many video frames are transmitted. Alternatively, theencoding bitrate controller3020 may alter the types of frames that are encoded, for example by selectively dropping B-frames or delaying the transmission of I-frames as the available bandwidth decreases, and restoring them as the bandwidth increases.

Further, theencoding bitrate controller3020 may alter the encoding parameters based on not just the actual value of the bandwidth F(Δ, t), but its time derivatives as well. As is well known in the art, a derivative is an instantaneous rate of change of a function with respect to one of its parameters, and derivatives of a function with respect to time can be used to predict the future behavior of the function. In this case, the time derivative of the bandwidth may be used to predict future bandwidth values. Thus, for example, a negative first time derivative F′(t) indicates that available bandwidth is decreasing, while a positive second time derivative F″(t) indicates that the decreasing trend is being reversed. In some embodiments,encoding bitrate controller3020 uses time derivatives of the bandwidth function to form the equation of a curve that best fits past bandwidth values up to some computational limit, according to methods well known in the art such as Taylor polynomials. By tracing the fitted curve forward in time, future bandwidth values are predicted, and theencoding bitrate controller3020 may use this predictive information to determine optimal encoding parameters. Thus, if the available bandwidth is increasing, the encoding bitrate controller may calculate a Taylor polynomial that indicates a future higher encoding bitrate than might otherwise have been indicated by monitoring only the raw bandwidth values. The amount by which the selected bitrate is preemptively increased may itself be based on whether the bandwidth trend is reversing or accelerating, as indicated by the second derivative of the fitted curve.

FIG. 30A shows a flowchart for performing the processes just described. The sequence begins inprocess3002A, in which a server directs a client decoding device to switch reception of broadcast, non-interactive audiovisual data from a managed network to reception of interactive audiovisual data from an unmanaged network. In another process (not shown), the client device receives this command and switches reception. At approximately the same time, or immediately prior to the switch, the client device sends a request for interactive content to the server using the unmanaged network, so that the client does not experience undue delay in receiving the content from the server. Inprocess3010A, the server receives the request for interactive content from the client device. In response, the server encodes a plurality of video frames according to a video encoding bitrate inprocess3020A. At the beginning of the cycle, the server may use a default bitrate or a bitrate determined through other means known in the art, but later encoding processes will use the actual, measured bandwidth. Once the video frames have been encoded, they are transmitted over the unmanaged network to the client device inprocess3030A. The first encoded video frames arrive at the client device without undue delay after the reception switch-over, and as noted before, transmission uses a reliable transmission protocol such as TCP. Inprocess3040A, the server determines whether there are additional video frames to encode as part of the interactive service. If the interactive service has been terminated, for example due to the subscriber navigating to another channel or the interactive session reaching the end of the audiovisual material available for use in the interactive mode, or for another reason, then the sequence terminates as shown byblock3042A. Otherwise, the sequence continues inprocess3050A, where the server determines a transmission bandwidth using data obtained from the transmission protocol. These data include the amount of data stored in a transmission buffer. Once the transmission bandwidth is known, inprocess3060A the server adjusts the video encoding bitrate to optimize the viewing experience of the audiovisual presentation on the client device. This new video encoding bitrate is then used to encode a further plurality of video frames in a feedback loop, as shown. The cycle continues until the interactive service is terminated.

The client process for obtaining audio and video from a multiplexed audiovisual data stream is described with reference toFIG. 31, which shows a preferred embodiment of the invention in which a client device performs adaptive latency control by simulating audio and/or video playback. Such simulation determines an approximate end user experience before audiovisual data are actually presented to the end user. Simulation may be performed, for example, by counting a number of received audio frames per unit of time and comparing this count to the number of frames expected to be received for the given audio bitrate. In the alternate embodiment ofFIG. 32, playback is adjusted based on the actual bitrate of the decoded audio that will be heard by the end user. In this case, simulation of playback is not necessary, although the adjustments made to the rate at which audio and video data are output may be made by similar calculations in both embodiments.

In the client decoding device shown inFIG. 31, the audiovisual data are received fromunmanaged network3110 intransmission protocol3120.Client transmission protocol3120 is complementary toserver transmission protocol3050; for example, ifserver transmission protocol3050 is a TCP server, thenclient transmission protocol3120 is a TCP client. Once the data are received, the audio and video data are separated by a hardware orsoftware transport demultiplexer3130. The audio data of the exemplary embodiment follow the top path of the Figure, while the video data follow the bottom path, and are treated differently. In particular, the audio data are analyzed to determine an actual transmission bitrate, which the client device then uses to control both audio and video output.

Audio data are provided to anaudio stream parser3140, which extracts encoded audio data. These encoded audio data are stored inaudio buffer3150, which enables the client device to provide output audio data at a constant rate. Similarly, video data are provided to avideo stream parser3142, and the parsed, encoded video data are stored in avideo buffer3152. In this embodiment, a playbacksimulation rate controller3160 controls the encodedaudio output3170 and the encodedvideo output3172, as indicated by

arrows

3162,3164. The playbacksimulation rate controller3160 may, in some embodiments, also control the size of theaudio buffer3150, as indicated by the horizontal arrows therein. The encodedaudio3170 and the encodedvideo3172 are then presented to audio and video decoders that produce analog audio and video for output by a display device.

Playbacksimulation rate controller3160 simulates playback of audio and/or video on a real device without requiring the data to be actually rendered on a speaker or display. Playbacksimulation rate controller3160 accomplishes this function by monitoring the number of audio frames in theaudio buffer3150, in a manner that parallels monitoring of data in the transmit buffer described above. By determining the number of audio frames in the buffer as a function of time, the playbacksimulation rate controller3160 can determine the bandwidth at which audio data are being received. By comparing this against the expected audio bandwidth,rate controller3160 can simulate audio and video playback, and increase or decrease the size of the audio buffer as necessary to avoid buffering delays that decrease the quality of user experience. Further,rate controller3160 can use the dynamic simulation to determine how to synchronize the outputs of

buffers

3150,3152. For example, video frames must be synchronized to audio frames in order to provide an enjoyable user experience. By carefully monitoring the simulation,rate controller3160 guarantees that audio data and video data are output at the same rate to ensure synchronization. Becauserate controller3160 does not interact withtransmission protocol3120, each may be embodied as a standalone functional module, including in hardware, providing potential manufacturing advantages and client device design simplicity.

FIG. 32 shows an alternate client embodiment for performing adaptive latency control. In this embodiment, the client device performs bandwidth monitoring at a later stage of audio and video processing. At this later stage, the actual audio and video outputs may be monitored, and simulation is not necessary. Thus, rather than storing encoded audio and video data in buffers, these data are further decoded inaudio decoder3210 andvideo decoder3212, respectively, before being buffered inbuffers3220,32222. In a manner similar to that described above in detail, in this embodiment aplayback rate controller3230 monitors the quantity of decoded audio data inaudio buffer3220, and controls its size and the outputs of the audio and video buffers. These outputs, namely decoded audio3240 and decodedvideo3242, are presented directly to the client display device for the user to hear and see.

Various modifications may be made to the basic client/server system described above in connection withFIGS. 30-32.FIG. 33 shows a server embodiment in which the data gathered from bitrate detection are used to provide a selection of services according to one or more business rules. In this embodiment, aframe assembly controller3310 determines whether an interactive service may be provided over the unmanaged network using the available bandwidth, and selects from a number of interactive video and audio sources based on its determination. Thus, the stitcher includes aframe assembly controller3310 that controls video frame assembly andencoding3320 using a number of different

video content sources

3318A,3318B. The assembled and encoded video frame is then multiplexed with selectedaudio content3330 in the previously describedtransport multiplexer3030, and the rest of the transmission path is the same as inFIG. 30. As before,transmission controller3040 calculates bandwidth F(Δ, t), and provides it3312 to frameassembly controller3310, which performs the function ofencoding bitrate controller3020.

Frame assembly controller

3310 performs additional functions in this embodiment, as now described.Frame assembly controller3310 monitors the available bandwidth values, and provides them tobusiness rules3314. These business rules determine whether the currently available bandwidth is sufficient to provide a selected interactive service to the client device. Based on this determination, thebusiness rules3314 access appropriate video content3318 andaudio content3330 using astorage network3316.

Business rules

3314 are typically embodied in a set of instructions for a computer processor, and may be implemented using techniques known in the art. The business rules3314 may include such information as a client device identifier, a subscriber identifier, a level of service paid for by a subscriber, the current number of subscribers accessing interactive content, the bandwidth of interactive services being provided to all subscribers in a particular subscriber class or geographic grouping, the availability of audio and video content instorage network3316, first publication dates of the same as determined by content producers, or any other pertinent data that may be used in a determination of which interactive services may be provided to the requesting client device given the current bandwidth values. The instructions operate upon these data to generate a list of available interactive services, the audio and video content of which is then provided to frame assembly andencoding3320 andtransport multiplexer3330, as indicated. If a minimum bandwidth requirement is not met for any interactive services otherwise available to a subscriber or client device, thebusiness rules3314 may cause a “service unavailable” content to be transmitted to the client device over the unmanaged network. If a minimum bandwidth requirement is not met for a currently provided interactive service, but the requirement is met for a different interactive service, thebusiness rules3314 may select the alternate service for transmission to the client device, or cause the client device to display a menu of different interactive services whose minimum requirements are met. After a subscriber selects an option in the menu, theframe assembly controller3310 causes the appropriate video content3318 andaudio content3330 to be encoded and transmitted to the client device.

The present invention may be embodied in many different forms, including, but in no way limited to, computer program logic for use with a processor (e.g., a microprocessor, microcontroller, digital signal processor, or general purpose computer), programmable logic for use with a programmable logic device (e.g., a Field Programmable Gate Array (FPGA) or other PLD), discrete components, integrated circuitry (e.g., an Application Specific Integrated Circuit (ASIC)), or any other means including any combination thereof. In an embodiment of the present invention, predominantly all of the reordering logic may be implemented as a set of computer program instructions that is converted into a computer executable form, stored as such in a computer readable medium, and executed by a microprocessor within the array under the control of an operating system.

Computer program logic implementing all or part of the functionality previously described herein may be embodied in various forms, including, but in no way limited to, a source code form, a computer executable form, and various intermediate forms (e.g., forms generated by an assembler, compiler, networker, or locator.) Source code may include a series of computer program instructions implemented in any of various programming languages (e.g., an object code, an assembly language, or a high-level language such as FORTRAN, C, C++, JAVA, or HTML) for use with various operating systems or operating environments. The source code may define and use various data structures and communication messages. The source code may be in a computer executable form (e.g., via an interpreter), or the source code may be converted (e.g., via a translator, assembler, or compiler) into a computer executable form.

The computer program may be fixed in any form (e.g., source code form, computer executable form, or an intermediate form) either permanently or transitorily in a tangible storage medium, such as a semiconductor memory device (e.g., a RAM, ROM, PROM, EEPROM, or Flash-Programmable RAM), a magnetic memory device (e.g., a diskette or fixed disk), an optical memory device (e.g., a CD-ROM), a PC card (e.g., PCMCIA card), or other memory device. The computer program may be fixed in any form in a signal that is transmittable to a computer using any of various communication technologies, including, but in no way limited to, analog technologies, digital technologies, optical technologies, wireless technologies, networking technologies, and internetworking technologies. The computer program may be distributed in any form as a removable storage medium with accompanying printed or electronic documentation (e.g., shrink wrapped software or a magnetic tape), preloaded with a computer system (e.g., on system ROM or fixed disk), or distributed from a server or electronic bulletin board over the communication system (e.g., the Internet or World Wide Web.)

Hardware logic (including programmable logic for use with a programmable logic device) implementing all or part of the functionality previously described herein may be designed using traditional manual methods, or may be designed, captured, simulated, or documented electronically using various tools, such as Computer Aided Design (CAD), a hardware description language (e.g., VHDL or AHDL), or a PLD programming language (e.g., PALASM, ABEL, or CUPL.)

While the invention has been particularly shown and described with reference to specific embodiments, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention as defined by the appended clauses. As will be apparent to those skilled in the art, techniques described above for panoramas may be applied to images that have been captured as non-panoramic images, and vice versa.

Embodiments of the present invention may be described, without limitation, by the following clauses. While these embodiments have been described in the clauses by process steps, an apparatus comprising a computer with associated display capable of executing the process steps in the clauses below is also included in the present invention. Likewise, a computer program product including computer executable instructions for executing the process steps in the clauses below and stored on a computer readable medium is included within the present invention.