HK1252983B - Method and system for determining and displaying contextual targeted content - Google Patents

Description

Method and system for determining and displaying contextually targeted content

This application is a divisional application of the invention patent application with application number 201080064471.9, application date November 18, 2010, international application number PCT/US2010/057153, and invention name "Video clip recognition method and context-oriented content display method for networked TV".

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of U.S. Provisional Patent Application No. 61/182,334, filed May 29, 2009, and U.S. Provisional Patent Application No. 61/290,714, filed December 29, 2009, under 35 U.S.C. § 119(e).

Background Art

The present invention generally relates to systems and methods for identifying a video clip being displayed by a television system, and systems and methods for providing contextually targeted content to the television system based on the identification of the video clip. As used herein, a "television system" includes, but is not limited to, televisions such as network televisions, connected televisions, and devices used with or incorporated into a television, such as set-top boxes (STBs), DVD players, and video recorders. As used herein, a "television signal" includes a signal representing video data and audio data that are broadcast together (with or without metadata) to form the image and sound components of a television program or advertisement. As used herein, "metadata" refers to data related to the audio/video data of a television signal.

Recent advances in fiber optics and digital transmission technology have enabled the television industry to increase channel capacity and offer a degree of interactive television services. This technological advancement is primarily due to the television industry's ability to combine powerful computer processing power (in the form of set-top boxes) with the high data capacity of optical fiber cables. The television industry has successfully used set-top boxes to expand channel selection and achieve a degree of interactivity.

Interactive television (ITV) technology was developed to transform televisions into two-way information delivery devices. ITV, with its various marketing, entertainment, and educational features (for example, allowing users to subscribe to advertised products or services), competes with competing programs such as game shows. Interactive features are typically controlled by a set-top box, which executes interactive programs written for the television broadcast. These features are typically displayed on the TV screen as icons or menus, which the user can select using a remote control or keyboard.

According to one prior art, interactive content can be added to the playback stream (also referred to herein as "channel/network input"). In the present invention, "playback stream" refers to the playback signal (analog or digital signal) received by the television, regardless of the signal transmission method, for example, antenna, satellite, cable and other analog or digital signal transmission methods. One prior art method for actually adding interactive content to the playback stream is to insert a trigger program into the playback stream of a specific program. Sometimes the program content with the inserted trigger program is called enhanced program content or enhanced television program or video signal. The trigger program can alert the set-top box to the presence of interactive content. The trigger program contains information about the available content and the memory location information of the content. The trigger program can also include user-aware text displayed at a location such as the bottom of the screen, prompting the user to take an action or make a choice among multiple options.

Connected TV is a television that is connected to the Internet through the viewer's home network (wired or wireless). Connected TV runs interactive web-based applications. There are several competing connected TV platforms, with Yahoo being the leading one (see "http://connectedtv.yahoo.com/"). The basic common features of connected TV platforms include (1) connectivity to the Internet; and (2) the ability to run software on top of the TV display. There are already several TVs on the market that support these features (for example, LG, Samsung, and RTX have some models available). More such TVs will enter the market in the near future. Industry observers predict that in a few years, all new TVs will have these features.

Connected TVs can run application platforms such as the Yahoo Widget Engine, Flash Lite (see http://www.adobe.com/products/flashlite/), Google Android, or proprietary platforms. A community of developers builds widgets that run on these platforms. Widgets are elements of a graphical user interface that display an arrangement of information that can be modified by the user, such as windows and text boxes. The widget engine is the operating system that runs widgets. In this article, "widget" refers to the code that runs on the widget engine. Each widget runs its own system process, so closing one widget does not affect the operation of other widgets. The widget engine may include a feature called a "dock," which displays icons for each available widget. TV widgets allow viewers to interact with the TV in a way that allows them to, for example, request additional information about the subject being viewed, without having to switch their context from watching a TV program to accessing an application. In response to these requests, the requested information is displayed on the TV screen as part of the visual representation of the widget.

Currently, almost all televisions (connected or otherwise) have no metadata about the content a viewer is watching. While the content delivery pipeline has some information in the form of bits and pieces, by the time a program reaches the screen, only the video and audio information remains. Specifically, the TV has no idea which channel or program the viewer is watching, nor does it know the content of that program. (The channel and program information that viewers see on the screen is sometimes grafted onto the set-top box from incomplete information.) This barrier, stemming from the fundamental structure of the television content distribution industry, limits the capabilities of interactive TV and is a serious problem for interactive TV.

Therefore, there is a need for improved systems and methods for identifying the video segment that a viewer is currently watching. There is also a need for improved systems and methods for providing contextually targeted content to a networked television system.

Summary of the Invention

The present invention relates to a system and method for identifying a video segment currently being displayed on a television system screen. Specifically, identification data of the video segment currently being viewed can be used to extract the viewer's reaction (e.g., changing the channel) to a particular video segment (e.g., an advertisement), and the extracted information can be reported as an indicator.

In some embodiments, a video segment is identified by first sampling a subset of pixel data (or associated audio data) displayed on the screen and then searching a content database for similar pixels (or audio). In other embodiments, a video segment is identified by first extracting video or image data associated with the video segment and then searching a content database for similar audio or image data. In some alternative embodiments, a video segment is identified by processing the audio data associated with the video segment using existing automatic speech recognition technology. In other alternative embodiments, a video segment is identified by processing metadata associated with the video segment.

The present invention further relates to systems and methods for providing contextually targeted content to an interactive television system. Contextual targeting requires not only identifying a displayed video clip but also determining the play time or time offset of a specific portion of the currently displayed video clip. "Play time" and "time offset" refer to a time offset from a fixed point in time, such as the start time of a specific television program or advertisement, and are used interchangeably herein.

More specifically, the present invention includes a technology that can detect the content currently being played on an Internet-connected television, infer the theme of the content being played, and interact with the viewer accordingly. Specifically, the technology disclosed herein addresses the capacity limitations of interactive television to fully utilize the server's functions through the Internet, thereby realizing a variety of business models, including the following applications: (1) providing additional content (director's commentary, character biographies, etc.) to enable viewers to participate more deeply in the program they are watching; (2) providing "buy now" functions based on specific content (product placement, "buy this song" function, etc.); and (3) providing viewers with access to network-based promotional functions (games, competitions, etc.).

In some embodiments, the method for identifying a video segment and determining a time offset is to sample a subset of pixel data (or audio data) displayed on the screen and then search for similar pixel (or audio) data in a content database. In other embodiments, the method for identifying a video segment and determining a time offset is to extract audio or image data associated with the video segment and then search for similar audio or image data in a content database. In some alternative embodiments, the method for identifying a video segment and determining a time offset is to process the audio data associated with the video segment using existing automatic speech recognition technology. In other alternative embodiments, the video segment is identified and the time offset is determined by processing metadata associated with the video segment.

As described below, the video segment identification software for the networked TV can optionally be located in a TV system that includes the networked TV. In some alternative embodiments, a portion of the video segment identification software is located in the TV system and another portion is located in a server connected to the TV system via the Internet.

Other aspects of the invention are described below and in the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic diagram of an Internet-connected TV according to an embodiment of the present invention.

2-4 show corresponding exemplary widgets that can be displayed on a connected TV based on the detection of video clips associated with a theme.

FIG. 5 shows an exemplary pop-up window, which can be displayed by clicking on a relevant field (displayed on the widget shown in FIG. 4 ).

6-10 are block diagrams showing systems according to other embodiments of the present invention.

11-16 are diagrams described in the appendix, disclosing an algorithm for tracking video transmissions using fuzzy clues.

The following description is made with reference to the accompanying drawings, in which the same numerals represent similar elements in different drawings.

DETAILED DESCRIPTION

In a first embodiment of the present invention, shown in FIG1 , system 100 includes a networked television 10. Networked television 10 is typically connected to a global computer network 20 via a processor 12. While processor 12 is shown as being external to networked television 10, those skilled in the art will appreciate that processor 12 may also be located within the television. In this context, "global computer network" includes the Internet. While FIG1 does not illustrate a television signal source, it should be understood that networked television 10 receives a television signal carrying a program stream.

The content widget running on the processor 12 includes computer software that identifies the video clip being displayed on the networked TV 10 in real time. Optionally, the content widget may also include computer software that determines the time offset of the clip's start. The clip and offset are collectively referred to as the "position." In response to identifying the video clip being viewed and optionally determining the time offset, the widget provides the television viewer with a widget in the form of a pop-up window 110 that displays categories related to the most relevant topics for the video clip being viewed. The viewer can select a topic in window 110, and the widget running on the processor 12 can retrieve more information related to the selected topic from the global computer network 20 based on the viewer's selection. Retrieval methods include, for example, entering the selected topic into a search engine, an online encyclopedia, or a customized search algorithm. Alternatively, the location can be entered into a customized algorithm that displays specific content based on the location of the program.

There are several content detection methods available. In one embodiment, the widget examines metadata provided with the program stream that describes the subject matter described by the program stream. For example, the widget examines closed caption data sent with a television signal. In another embodiment, the widget uses speech recognition software to maintain a statistical table of the number of times the measured language is used over a period of time. In another embodiment, the widget can use speech feature detection or image detection software to identify displayed images in the program stream. In another embodiment, the widget sends video or audio cues to a server that performs detection and contextual targeting (one embodiment of suitable video pixel cue processing software is described in detail below in conjunction with Figure 10). There are several methods for determining topic relevance.

In response to identifying the video segment being viewed and optionally determining a time offset, the TV widget retrieves additional information determined to be relevant to the thematic context of the video segment being viewed. The process of retrieving additional information or advertisements determined to be relevant to the thematic context of the video segment being viewed is hereinafter referred to as "contextual targeting." The contextually targeted TV widget will now be described with reference to Figures 2-5.

A contextually targeted TV widget is software that runs on top of the connected TV 10. The software extracts enough information to identify the content the viewer is currently watching and then, based on that information, determines additional information on topics that may be of interest to the viewer. The additional information is displayed on top of the currently displayed program on the TV screen. The additional information is accessed from a network (typically the internet) via aggregation or internet aggregators (Wikipedia or Google). Some of this additional information is provided to users as free value-added content, while other information is paid advertising or promotional offers.

To illustrate the audience experience provided by the system of the present invention, several scenarios are described below.

In the first scenario shown in Figure 2, the system implements conventional integration by acquiring keywords, targeted general information, and advertising slogans. In this scenario, the viewer is watching the hit TV series "Gossip Girl". At some point during the viewing, the characters discuss going to the Hamptons for the summer vacation. The context-targeted TV widget detects the keyword "Hamptons". In response to the keyword detection, the widget base flashes or highlights the new keyword, as shown in the light shading of Figure 2. If the viewer opens the widget base (i.e., the viewer is interested in interacting with the widget), the viewer can expand the widget. If the viewer does not open the widget base and wants to watch it later, the keyword is saved. The TV viewer can always scroll through the last N keywords, where N is an integer such as 50. When the viewer sees content that interests them, they can click on the highlighted keyword, and the widget expands to sidebar mode, and the TV program continues to run in the background. The expanded widget (as shown in FIG2 ) displays targeted information about the Hamptons, such as: (1) an overview of the Hamptons: “The Hamptons are a popular seaside resort. For wealthy individuals who own local vacation homes, many areas of the Hamptons are a haven for them…”; and (2) a Google map showing the location of the Hamptons. In this embodiment, the expanded widget also displays some news about the Hamptons, such as, “While Madonna’s assistant claims that pesky paparazzi ruined her weekend at her Hamptons vacation home, police officers responded that…”. If the viewer clicks on other displayed fields, the expanded widget also displays targeted advertisements, such as Hamptons real estate, New York City tours, and vacation packages to other beach destinations where wealthy individuals (like the Hamptons) gather.

In the second scenario shown in Figure 3, the system achieves a more complex integration by acquiring popular keywords and leveraging relationships and promotions with one-click merchants such as Amazon. In the second scenario, viewers are watching live programs such as Entertainment Tonight and The Daily Show. During the program, some people are discussing the behavior of a celebrity, such as Britney Spears. The context-targeted TV widget acquires the keyword "Britney". In response to the detection of these keywords, the widget base flashes or highlights the new keyword, as shown in Figure 3. If the viewer opens the widget base, the widget sidebar displays targeted information, such as (1) a brief introduction to Britney: "...Britney Jean Spears, born on December 2, 1981, is an American singer and entertainer. Britney ranks 8th among the best-selling female singers..."; (2) albums with "Buy Now" buttons, including "...Baby One More Time" in 1999, "Oops! ...I Did It Again” in 2001, “Britney” in 2003, “In the Zone” in 2007, “Blackout” in 2008, and “Circus” in 2008; (3) some news about Britney (considering the previous keyword “Hamptons” whenever possible); (4) images or YouTube search results related to Britney’s photos or music videos; and (5) a promotional advertisement for Britney’s latest concert, with an interactive calendar showing the viewer’s geographic area and a “Buy Now” button. After the viewer clicks the “Buy Now” button, a screen opens for the viewer to complete the transaction in the fewest possible steps (using an Amazon ID/password combination, etc.). After completing a purchase, the viewer does not need to re-enter personal information for future purchases.

In the third scenario, shown in Figure 4, the system implements customized integration by acquiring keywords or video/audio clips purchased by specific partners to enrich media campaigns. In this third scenario, a viewer is viewing an advertisement, such as a car commercial. In this instance, the advertisement offers the viewer the option to activate the widget base to "continue viewing." Contextually targeted widgets acquire advertisements based on predetermined tags or phrases, making them a priority event during a set time period. The widget sidebar displays a microsite that encourages users to further engage with the brand, such as additional web ads that expand on the characters and themes of the advertisement; additional information such as specs or feature comparisons; and interactive features such as games, lotteries, or customization tools. For example, a viewer clicking the "Drive a MINI with Jason Bourne" field displays the Bourne Conspiracy-MINI microsite (see Figure 5).

In some embodiments, the method for identifying a video segment and determining a time offset is to sample a subset of pixel data (or related audio data) displayed on the screen and then search for similar pixel (or audio) data in a content database. In other embodiments, the method for identifying a video segment and determining a time offset is to extract audio or image data related to the video segment and then search for similar audio or image data in a content database. In alternative embodiments, the method for identifying a video segment and determining a time offset is to process the audio data related to the video segment using existing automatic speech recognition technology. In other alternative embodiments, the video segment is identified and the time offset is determined by processing metadata related to the video segment.

In other embodiments, there is no need to determine the time offset, and the system only needs to react to the occurrence of a keyword or phrase. For example, FIG1 shows a software program that can be executed on processor 12 and includes four basic modules: (1) a metadata collection module that collects metadata for any viewed content; (2) a topic/keyword extraction module that analyzes the collected metadata to extract relevant content from the program; (3) a useful information context targeting module that collects additional information based on the extracted topics/keywords and provides such information to the user; and (4) an advertising context targeting module that collects revenue-generating information based on the extracted topics/keywords and provides such information to the user (including a "buy now" button and keyword advertising and promotional campaigns).

There are many sources of metadata about the content a viewer is watching, including (1) program information provided by the network/station or third parties (TV guide, etc.); (2) closed captioning input; (3) audio input of the program being watched (run through voice recognition); (4) video feed of the program being watched (run through image recognition); (5) additional channels on top of the audio or video feed of the program being watched; and (6) customized content that is manually added to specific programs and program segments.

In one embodiment, processor 12 collects metadata from a combination of video transmissions and closed captioning information, where available, for the program being viewed. A speech recognition engine processes the video stream and extracts keywords. Care is taken to maintain a dictionary language model for the speech recognition algorithm to effectively extract keywords or phrases worth targeting. For example, the dictionary is weighted to search for correct nouns such as "Britney" and "Yankees" while discouraging searches for words such as "green" and "hot." For the captioning data, a keyword/topic analysis engine performs stream (text stream) processing.

Four possible configurations for the metadata collection component will now be described. In the embodiment shown in FIG6 , metadata collection and data processing required for contextual targeting are performed on a central server (which is connected to a remote TV via a wide area network, such as the Internet). In the embodiment shown in FIG7 , data required for metadata collection is processed on the TV, and data required for contextual targeting is processed on the central server (which is connected to the remote TV via a wide area network). In the embodiment shown in FIG8 , data required for contextual targeting is processed on the central server (which is connected to the remote TV via a wide area network), and data required for metadata collection is processed on an offline server (which is connected to the contextual targeting server via a local area network, etc.). Note that in this embodiment, the TV client 18 sends a clue to the server's channel identification component 26 to determine the program being watched and, therefore, the metadata applicable to that TV. It should also be noted that while FIG8 uses an audio stream as the input to the TV client 18, a video input could also be used. Alternatively, a hybrid approach combining the two aforementioned approaches could be used, where possible.

Now, referring to FIG6 , the system 200 includes a remote TV 10 connected to a central server 220 via a wide area network (not shown). The TV 10 includes a multi-pixel screen, a processor, and a TV signal receiving interface. The TV processor is programmed with software comprising a widget platform or engine 14 and a TV client 18 that communicates with the server 220. The widget engine can display any one of a plurality of widgets 16 on the TV screen. The server 220 has one or more processors and software, including a speech recognition module 22 and a contextual orientation module 24. In this embodiment, the client 18 receives an audio stream of a TV program or a program being watched, compresses the audio stream, and sends the compressed audio stream to the server 220. The information sent by the TV client 18 to the server 220 may also include a subtitle stream (if any) or other metadata and/or channel information. The speech recognition module 22 processes the compressed audio stream to determine the channel being watched.

In the setup shown in FIG6 , a lightweight client needs to be built for the television operating system (typically Linux), which captures the audio stream from the television 10, compresses the signal, and streams it over the network to a waiting server 220. A token is attached to the audio stream so that the server can associate the data stream with a specific user and/or television. The server then runs a real-time speech recognition algorithm 22 on the stream, or determines a subtitle search to extract keywords/phrases. Several suitable speech recognition packages are available, such as the open source package called Sphinx-4 ( http://cmusphinx.sourceforge.net/sphinx4/ ), which is a speech recognition program written entirely in the JAVA ^™ programming language. Keywords/phrases can be attached to the relevant user/television for use by the contextual targeting module 24 in delivering content (third-party content input, etc.) to the widget 16. The server 220 stores user information in a permanent user database 30, including the television ID number, programs watched on that television, and selections made using the widget 16 displayed on the television.

Referring now to FIG. 7 , system 300 includes a remote TV 10 connected to a central server 320 via a wide area network (not shown). In this setup, a heavier (but still essentially lightweight) client 18 is built for the TV operating system. The TV operating system collects metadata (including subtitle data) or the TV's audio stream, runs a relatively limited algorithm to determine relevant topics, and sends only the extracted keywords/phrases to server 320. In one embodiment, the speech recognition client 18 monitors server 320 and periodically updates its dictionary language module. Several packages are available that provide lightweight speech recognition for mobile and embedded devices (which lack powerful CPUs, similar to TVs). An example includes PocketSphinx (http://cmusphinx.sourceforge.net/html/compare.php), a mobile version of the aforementioned open source Sphinx-4 package. Keywords/phrases are attached to the relevant user/TV and used by the contextual targeting module 24 to deliver content (third-party content input, etc.) to the widget 16. Likewise, the server 320 stores user information in the permanent user database 30, including the TV ID number, the programs viewed on the TV, and the selections made using the widgets 16 displayed on the TV.

Referring now to FIG8 , system 400 includes a remote television 10 (connected to a central server 420 via a wide area network (not shown)) and one or more offline servers 410 connected to server 420 via a local area network (not shown). The software in server 420 includes a contextual targeting module 24 and a channel identification module 26. In the configuration shown in FIG8 , offline server 410 continuously receives input corresponding to a set of television channels and runs a more complex and robust algorithm to assign metadata tags to each channel. A lightweight television client 18 (part of the television operating system) only transmits enough information to server 420 to enable server 420 to identify the channel being viewed. As shown in FIG8 , the television client receives the audio stream of the television program being viewed and extracts the audio data to be sent to server 420, enabling server 420 to identify the channel being viewed using audio feature detection or other methods. Alternatively, the television client 18 can send pixels or audio cues (including batches of pixel or audio data samples) to server 420, which can then process the blurred pixels or audio cues using the techniques disclosed in the appendix to this document to identify the channel being viewed. For example, the television client 18 may send pixel cues to the server 420, in which case the channel identification module 26 may include appropriate audio pixel cue processing software, such as is described below in conjunction with FIG10. In another alternative embodiment, the television client 18 may receive the video stream and extract image data to be sent to the server 420, enabling the channel identification module 26 to identify the channel being viewed using image recognition software.

Based on the information received from the TV client, server 420 can conveniently identify the video clip being watched and the time offset relative to the program start time. Online server 420 matches the channel currently being watched with the channels tagged by offline server 410 and transmits the corresponding keywords/phrases previously provided by the offline server to contextual targeting module 24. The keywords/phrases are attached to the relevant user/TV and used by contextual targeting module 24 to deliver content (third-party content input, etc.) to widget 16. The offline server does not necessarily run in real time. The offline server periodically (hourly or daily) loads metadata (including the aforementioned keywords/phrases) into server 420's memory. Furthermore, while offline server 410 captures live webcast feeds, viewers may be delayed for hours or days watching the same content. Online server 420 matches the channels and corresponding time indicators to programs (both live and past). Offline server 410 and channel identification component 26 are configured to store program leads and metadata for a specified period (typically several days to a week).

Continuing with reference to FIG. 8 , another configuration is to periodically batch program transmissions to the offline server 410 in addition to (or instead of) transmitting to the offline server 410. The offline server 410 stores clues and metadata for a specified period of time, allowing this configuration to form a database of program clues and metadata, which is particularly beneficial for users who view content on DVRs or DVDs. Note that batch loading can also be used, which is not available with network input.

In another aspect of the present invention, a hybrid solution can be used. A reasonable setup must be a hybrid solution that can use each of the above methods in the most appropriate situation. Since TV configurations vary greatly, one solution cannot meet the requirements of all users. For viewers with available channels/network data (for example, users watching TV online or downloading content from on-demand services) or when the audio input is identified as a known channel, offline calculation methods can be preferred (as shown in Figure 8). If there is no broadband and an audio stream cannot be formed, the most popular keywords can be processed by the TV's voice recognition client (see Figure 7). For viewers watching DVDs or using DVRs, streaming to the server (see Figure 6) will provide better/deeper analysis. If channel detection or specific program settings are feasible, the clues will only be sent to the server for matching (see Figure 8). The system selects a method in each case based on criteria such as the success rate of each method, customer records and advertiser value, available bandwidth or computing power.

In another embodiment of the present invention shown in FIG9 , the system 500 includes a server 520 that maintains a user-specific database 30 that communicates with an offline contextual targeting server 510. The offline contextual targeting server 510 receives input from the database 30 as well as channel or network input and content input, and provides information to the server 520, which then transmits processed information to the network-connected TV 10.

Specifically, system 500 includes a television 10 (with a widget platform 14 and client 18), an offline server 510 (on which a contextual targeting engine runs), a server 520 (including an audio input channel matching module 530 and a speech recognition contextual targeting engine 540), and a viewer database 30. System 500 is programmed to determine what the viewer is watching, using the audio stream entering the television 10. Televisions have a variety of possible configurations, most of which "lose" the most valuable metadata, such as subtitles, channel information, and program descriptions. Specifically, most cable box configurations that connect to the television via an HDMI cable have poor metadata performance. Audio and video inputs are the lowest common denominator and are ubiquitous in all configurations. Figure 9 shows the television client 18 and audio input channel matching module 530 (which uses the audio stream to detect the currently viewed channel, using audio feature detection or other means). Alternatively, the television client 18 can send pixel cues (including batches of pixel data samples) to server 520. Channel matching module 530 uses the techniques disclosed in Appendix 1 herein to process the blurred pixel cues and identify the currently viewed channel. In the specific embodiment shown in FIG9 , the TV client module 18 is a lightweight client of the TV operating system, which collects the TV's audio stream, compresses the signal, and sends the signal to the server 52 via a global computer network (not shown in FIG9 ). The audio stream is attached with a token, allowing the server 520 to associate the audio stream with a specific TV/viewer.

Server 520 receives the audio stream from TV 10, associates it with a specific TV/viewer, and sends the audio stream to audio incoming channel matching module 530. If the audio stream cannot be sent to module 530, it is sent to speech recognition context targeting engine 540 for tagging. After tagging the targeted content, server 540 returns the targeted content to TV 10 widget 16.

Server 520 includes an audio incoming channel matching module 530, which attempts to match the audio stream of TV 10 with hundreds of known live feeds of the most popular cable TV channels nationwide. If the viewer is watching a known channel, it is tagged using metadata collected by the contextual targeting engine running on the offline server 510. If the viewer is not watching a known channel, it is processed by the speech recognition contextual targeting engine 540. The speech recognition contextual targeting engine 540 serves as a backup option, eliminating the need to monitor all channels nationwide. In addition, in this continuous process, channel changes are detected, and the number of tags is increased by adding topics/keywords for multiple channels.

The contextual targeting engine is software running on an offline server 510. Alternatively, multiple offline servers can be used. The offline server 510 connects to live feeds of popular cable and network channels across the country. The dynamic content can be configured to display useful metadata that is missing from the client TV. Specifically, closed caption data, program descriptions, and channel type activate the contextual targeting engine, which tags real-time topic/keyword information on the channel. Since each channel only needs to be processed once (rather than once per client TV), more powerful algorithms can be run in real time. The metadata dictionary is generated by a continuous improvement process of actual responses from viewers using the widget. Viewer responses are sent from the widget 16 to the server 520, stored in the user database 30, and sent to the offline server 510, as shown by the arrow titled "User Widget Feedback" in Figure 9. The contextual targeting engine prioritizes the interactive keywords of the widget viewer and demotes ignored content. This results in a more accurate metadata dictionary for the current TV 10 content.

As previously mentioned, server 520 includes a speech recognition contextual targeting engine 540. For viewers tuning into unrecognized channels, playing DVDs, or using DVRs, a real-time speech recognition solution extracts topics/keywords. Speech recognition systems can only use a limited dictionary, so the key to the feasibility of this solution is the concise topic/keyword dictionary maintained by the offline server 510—a dictionary of keywords that are currently popular in current television programs and that widget viewers have already engaged with. Because the content is recorded recently (in many cases just hours later), marked offline, and its metadata improved using widget feedback, the system is particularly beneficial for viewers using DVRs. Still referring to FIG. 9 , the targeting performed by the TV 10 widget 16 using all of the aforementioned components is only part of the viewer's actual viewing system. Unlike conventional Konfabulator widgets, which must be periodically updated to achieve a fresh feel and appearance, the contextual targeting widget 16 can change its presentation at any given time based on the targeted content.

A preferred embodiment of the present invention will now be described. While the networked television system of the disclosed system includes a content widget engine and client software (generating pixel cue points, etc.), within the scope of the present invention, the widget engine and client software reside in a device such as a STB, DVR, or DVD player that provides television signals to the networked television. Furthermore, while the disclosed system samples and processes pixel values, the sampled and processed values can also be audio values or metadata such as closed captions.

10 , the system comprises a television system 52 and a first server 54 communicating via a network such as the Internet. Additionally, the system comprises a second server 56 (hereinafter referred to as the "offline server") communicating with the first server 54 via a network, preferably a local area network (LAN).

FIG10 illustrates the functional components of a television system 52, a first server 54, and an offline server 56. The television system 52 includes a television comprising a multi-pixel screen (not shown in FIG10 ) and at least one other component (not shown) that provides a television signal to the television. For example, the other television component may include a STB, a DVR, or a DVD player. The television system 52 also includes a processor (not shown in FIG10 ). The processor may be incorporated into the television or into at least one other component of the television system.

10 , the television system's processor is programmed with software and includes a widget engine 58 and a client 60. As previously described regarding the location of the television system's processor, the widget engine and client software may be located on the television or at least one other component of the television system. It should be understood that the widget engine and client software may also run on different processors within the television system 52.

In any case, the client module 60 is programmed to sample pixel data and generate an HTTP request based on the sampled pixel data to be sent to the server 54. The HTTP request includes a time stamp and a plurality of RGB (or hexadecimal) value strings, which are called "pixel clue points." Each pixel clue point includes a corresponding subset of RGB (or hexadecimal) values that constitute a corresponding "frame" of the video clip being displayed on the television screen, as described in detail below. [In fact, digital video does not have frames. The system disclosed herein samples at a certain time, for example, at each time amount T.]

It is important to note that the server 54 includes a processor and memory (neither of which is shown in FIG10 ). However, FIG10 shows that the server 54 includes at least the following software components: a channel identification module 62, a contextual targeting module 64, and a database 66 comprising an indexed content library. The channel identification module and the contextual targeting module run on the server processor. The library data itself requires a consistent, usable, and rapidly searchable storage format. The simplest approach is to load the library into a data structure in the server's memory. Another approach is to save the majority of the library's contents to disk.

The channel identification module 62 includes a point management submodule and a user management submodule (not shown in FIG10 ). The point management submodule searches the database 66 in two ways: (1) searching the entire database for a given set of points and returning all possible matches; and (2) searching a given set of points and a given possible location and returning whether the user is actually at the location indicated by the currently stored data. [A “user” is a unique device, such as a television, identified by a globally unique ID.]

The user management submodule maintains user sessions and uses the results from the point management submodule to match locations (located in the video clip being viewed) to specific users. The user management submodule also maintains configurations and tolerances for determining the format and timing of matches. The user management submodule also includes a session manager. The user management submodule matches user locations based on HTTP requests received from the TV client module 60. If the user ID already includes session data, the HTTP request is routed to the user management submodule attached to the session (session persistence). The user management submodule reviews the user's history and determines the type of search request (if any) to submit to the point management submodule. If the user's location is a possible context, the point management submodule is called to perform a brute force search around that location. If the user's location is unknown, the point management submodule is called to perform a probabilistic global search. The user management submodule stores the updated location in the user session.

10, the client module 60 sends periodic updates containing pixel clue information to the user management submodule of the channel identification module 62. This communication is accomplished via the aforementioned HTTP request, with the pixel clue information being sent via the "get" parameter.

Example of the above HTTP request:

http://SERVER_NAME/index? token=TV_ID&time=5799&cueData=8-l-0,7- 0-0,170-158-51,134-21-16,3-0-6,210-210-212,255-253-251,3-2-0,255-255- 244,13-0-0,182-30-25,106-106-40,198-110-103,|28-5-0,3-0-2,100-79-2,147- 31-41,3-0-6,209-209-209,175-29-19,0-0-0,252-249-237,167-168-165,176-25- 17,113-113-24,171-27-32,|38-7-0,2-2-2,99-70-0,116-21-31,6-0-9,210-210-210, 179-31-22,31-31-33,162-65-64,10-10-10,184-33-25,105-108-32,169-28-28, |104-86-15,4-4-4,46-18-0,178-112-116,0-0-1,213-213-213,178-31-22,211-211- 211,164-62-72,0-0-0,183-32-24,150-149-42,153-27-19,|188-192-43,2-1-6,67- 49-0,156-92-95,3-1-2,215-215-215,177-28-19,226-233-53,249-247-247,207- 211-21,182-31-23,136-153-47,152-25-18,|192-118-109,176-181-84,201-201- 201,218-172-162,201-200-39,226-226-226,244-244-244,221-214-212,166- 165-170,209-209-209,191-26-36,154-28-20,150-21-15,|0-3-0,0-0-0,156-27-22, 161-28-19,192-192-26,157-26-22,174-29-23,149-23-18,190-34-25,156-27-20, 176-27-18,0-0-0,184-30-25,|159-29-19,9-3-0,161-26-22,137-22-15,0-4-9,167- 26-26,159-28-25,165-27-24,65-21-13,154-22-19,99-24-11,153-24-20,185-34- 28,|153-26-21,0-0-0,165-25-15,141-24-13,1-1-1,165-25-17,154-27-24,182- 32-26,180-31-25,149-25-17,155-21-19,36-12-4,171-29-22,|153-26-21,0-0-0, 165-25-15,141-24-13,1-1-1,165-25-17,154-27-24,182-32-26,180-31-25,149- 25-17,155-21-19,36-12-4,171-29-22,|

The HTTP request contains the following parameters:

The parameter "token" is a unique identifier of the TV (or other device). The manufacturer assigns a globally unique ID to each TV, which is sent to the user management submodule of the channel identification module 62, as shown in FIG10 .

The parameter "time" is an arbitrary time stamp used to maintain the order of requests and to assist in calculating the "most likely position" described below. This parameter is typically provided by the TV's built-in clock.

The parameter "cueData" is a list of RGB values, for example, a sample of pixel values comprising RGB combinations. Its format includes R1-G1-B1, R2-G2-G2, ...|R3-G3-B3, R4-G4-B4, ...|, etc., where each RX-GX-BX indicates a corresponding RGB position. RGB position 1, RGB position 2, and RGB position 3 constitute a sample. Sample 1 | Sample 2 | Sample 3 |, etc. constitute an HTTP request. [The claims appended hereto refer to samples as "pixel cue points."] "RGB position" should be interpreted as broadly as possible to include a set of RGB values for a single pixel identified by an X-coordinate and a Y-coordinate, as well as a set of RGB values that is a function of the RGB values of multiple single pixels within an array (a square array, etc.). In the second case, the collection of sets of single RGB values for all pixels of the array is called "patch data (PatchData)". The pixel array is located in a given area (a square area, etc.) of the TV screen.

In the above embodiment, the cueData parameter of the HTTP request has 10 samples, one sample per video frame, and each sample contains the RGB values of 13 pixels or a 13-pixel array, with the same pixels or pixel arrays sampled for each of the ten frames. However, the number of pixel values per frame, the locations of the sampled pixels, and the number of samples in the HTTP request may vary depending on the point sampling instructions received by the television client component.

In the embodiment shown in FIG10 , the television system 52 includes a system-level function for extracting pixel information. The function “wakes up” periodically, for example, every 0.1 seconds, and extracts N slices of pixel data for each “frame” of pixel data, where N is a positive integer (for example, 13). The pixel data for each slice is reduced to a single pixel sample, i.e., a single set of RGB values, which is a function of the pixel data for the corresponding slice. The function can be an average, a weighted average, or any other suitable function. A series of “frames” (e.g., 10) of pixel samples are accumulated and sent to the server. For example, the television client sends batches of pixel samples to the server periodically (e.g., once every 1.0 second).

The following is an exemplary API specification document (written in C computer language). The API is part of the TV client module 60, and the software runs in the chipset of the TV system. The chipset implements the specific functions defined in the following API specification.

The API file includes three data structure declarations related to "Patch", "PatchData" and "Pixel". The pixels of the TV screen are arranged in the X, Y plane, and each pixel is identified by an X coordinate and a Y coordinate. "Pixel" consists of three integers (RGB values, etc.). [Alternatively, the declaration can be made using hexadecimal values]. "Patch" is the square coordinates of the TV screen, and each square contains an array of pixels. "PatchData" is a collection of "pixels" in a given square of the screen. Syntax note: In C language, "Pixel*" refers to a collection of "pixels". Therefore, "Pixel*pixelData;" refers to a collection of "pixels" of an arbitrarily named "pixelData". Function:

PatchData*getPatchesFromVideo(Patch*requestedPatches,int numOfPatches);

Implemented by the TV system chipset, it refers to the function "getPatchesFromVideo" that returns the "PatchData" collection.

10 , in a preferred embodiment, the TV client module 60 is programmed to obtain the RGB values for each pixel within each array (i.e., slice). The set of RGB values for each pixel array or slice is then processed to generate a corresponding set of RGB values for each pixel array or slice. In other words, for a 3x3 pixel array, nine sets of RGB values are reduced to a single set of RGB values. This operation can be performed using various mathematical functions, such as an average or a weighted average. The HTTP request sent by the TV client 60 to the channel identification module 62 of the server 54 includes the set of RGB values for each slice (e.g., three integers), rather than the complete slice data for each slice.

The TV client module 60, an embedded code segment baked into a device such as a TV chip, sends collected points to the user management submodule of the channel identification module 62. The TV client module can be updated in the field with firmware updates. In one embodiment, the TV client module 60 periodically requests instructions from the server 54 to determine the number, frequency, and location of sampled points. The TV client module does not need to send points to the server at a constant sampling rate. In one embodiment, the TV client module samples approximately 10 times per second, batches the resulting points, and sends them to the server at a fixed interval, such as once per second. The TV client module requires knowledge of the user management submodule components associated with the session. During initialization (and periodically thereafter), the TV client module calls the user management session manager to obtain the address of the user management component. The user management component assigned to a given device, such as a TV, maintains the user's session information. If the assigned user management component is no longer available (e.g., due to a crash), the session manager assigns a new user management component. The TV client module also requires arbitrary timestamps to maintain request order and send location information to the relevant components of the point management submodule.

In response to an HTTP request received from client module 60, channel identification module 62 identifies, in real time, the video segment from which the cueData in the HTTP request is taken, as well as its time offset relative to the start time of the segment. As previously mentioned, the segment and offset are collectively referred to as a "position." The point management submodule of channel identification module 62 uses a path tracing algorithm to search database 66 for the pixel cue point stored in the database that is closest to the pixel cue point received in the HTTP request. This is accomplished by referring to the appendix "Path Tracing Problem: Tracking Video Transmission with Arbitrary Clues," which is incorporated herein by reference in its entirety. The double PPLEB arrows shown in Figure 10 indicate that the point management submodule of the channel identification module communicates with database 16 while executing the path tracing algorithm, which includes the Probability Point Location of the Mean Sphere (PPLEB) and the Efficient Likelihood Update algorithm. The appendix details the method for identifying the most likely "position," including the mathematical equations. The search method is described more briefly below.

The path tracing algorithm described in the appendix uses a mathematical construct called locality sensitive hashing. A known method in the prior art is to map each point in each data set to a word, which is a list of hash values. These words are placed in a sorted dictionary (much like a common English dictionary). After searching for a point, the algorithm first constructs the word and then returns the closest edited match in the dictionary. This requires calculating each letter of the word independently and performing a dictionary search. In the version disclosed in the appendix, a fixed-length word is first constructed (which depends entirely on the point vector noun), and then the point management submodule of the channel identification module only searches the dictionary for the exact matching word. The advantages are that 1) the words corresponding to the points are calculated in batches, which is much faster than calculating them letter by letter; and 2) using a traditional hash function instead of a dictionary for the dictionary search can increase the speed and simplify the process.

It is important to understand that a location search (i.e., video clip plus time offset) searches for the most likely content. The path tracing algorithm first finds possible locations and then calculates a probability distribution for these possible locations. More specifically, a probability is assigned to each possible location, representing the likelihood of it matching the video clip currently being displayed on the television screen. If the probability of the possible location with the highest probability exceeds a predetermined threshold, a decision is made that the possible location corresponds to the video clip currently being displayed. Otherwise, the path tracing algorithm continues to update the list of possible locations and their probability distributions as successively received pixel clue points are processed.

The path-following algorithm is a probabilistic approach: it doesn't always need to perfectly match pixel clues; instead, it determines the result as true based on the overall evidence. The algorithm tracks in real time and can handle intermittent pixel clues that deviate from other pixel data points in the same sequence. For example, while the algorithm may only identify 7 out of 10 frames in a video clip, it can still identify the majority of possible locations. The algorithm also responds quickly to actions such as pauses and channel changes by viewers.

Upon receiving the first pixel cue point from a TV system, the server calculates a probability distribution for all possible locations. Upon receiving each subsequent pixel cue point from the same TV system, the list of possible locations is updated, and an updated summary distribution is calculated for each updated possible location. This iterative process is always performed in real time, closely monitoring the user's viewing habits. Each pixel cue point received from the TV is processed and discarded. A record of possible locations and their probability distributions is stored in memory for each user session. However, if the likelihood of a particular possible location decreases (for example, the probability falls below a predetermined threshold), the possible location can be ignored, i.e., deleted from the stored record.

It's also important to note that searching the entire pixel cue database for each TV system is inefficient. To improve search efficiency, the pixel cue data in the database is divided into several sections. Only the most recent content is searched in one section. See the attached document for detailed instructions.

After identifying the most likely location in the database, the contextual targeting module 64 can retrieve the database-stored content associated with that location (see FIG. 10 ). In a preferred embodiment, the contextual targeting module 64 receives the program ID and the time offset of the most likely location (i.e., the most likely location, but with a probability exceeding a preset success threshold) from the channel identification module 62 and then uses this information to retrieve relevant enhanced content from the database 66. The database contains closed captions for video clips, with the video clip identifiers and pixel cue points stored in the database. The database also contains a content encyclopedia consisting of triggers extracted from the files (i.e., single words or short sequences of words and proper nouns that indicate relatively specific topics) and corresponding content associated with each trigger. The encyclopedia is an index of structured content data, preferably organized by category. The contextual targeting module includes a search engine that searches the database for closed captions associated with the identified location and identifies the triggers in the associated closed captions. See the arrow labeled "Trigger Search" in FIG. 10 . The contextual targeting module then searches the database for content associated with the triggers identified in the encyclopedia. The trigger set and search configuration are customized based on the specific content (specific TV shows, commercials, movies, etc.). For example, to identify basketball games, the contextual targeting module uses a trigger set that includes the names of players/coaches, etc. In another example, news and current affairs programs are configured with a trigger set that emphasizes the names of politicians and current buzzwords ("medical," etc.). In another example, TV series and sitcoms are configured with a trigger set that includes any combination of words and time stamps that trigger activities at specific locations in the region without having to look at the topic of the conversation (for example, activities corresponding to singing songs are displayed after a specific point in the region).

The offline server 56 (see FIG10 ) receives channel/network input and content input and builds a database 66. The offline server continuously updates the database as it receives input content.

In a preferred embodiment, the offline server 56 extracts the time stamps, pixel cue points, and closed captions of the channel/network input. The extracted information is stored as part of a database 66. More specifically, the database contains the following information for each television program, commercial, etc. broadcast or video clip: (a) a list of pixel cue points for each video clip; (b) offsets relative to certain fixed time points, the offsets being associated with the aforementioned pixel cue points to indicate the timing when the pixel cue points occur; and (3) related metadata (closed captions, etc.). Preferably, the offline server samples the pixel data at the same rate as the television system client. However, when sampling the same video clip, the two devices may not necessarily sample at exactly the same rate.

The offline server 56 also extracts the triggers and content of the content input. When stored in memory, the extracted information constitutes the above-mentioned encyclopedia, which is also an integral part of the database 16. The offline server also creates a customized index for a specific television program.

The offline server 56 may include a master source module that indexes content and adds it to a library (database 66, etc.) that is searched by the point management submodule. The master source module is composed of a collection of emulators that are identical to the TV client components except that they can operate in master mode. In master mode, the method of sending points to the point management submodule is the same as in standard mode, but the points in master mode are accompanied by metadata and instructions for the point management submodule to add the points to the library rather than searching for them. The master source module has four operating modes: (1) batch; (2) live; (3) channel; and (4) UGC. In batch mode, content arrives in the form of complete video files well in advance of the "broadcast date". The TV client emulator plays the video file in master mode and sends the points to the point management submodule to be added to the library. In live mode, a specific live event is configured to be indexed (basketball game, etc.). The stream is scheduled before the content retrieval time and attached to a emulator running in master mode. In channel mode, the emulator is set to continuously watch and retrieve the given channel status. Content typically enters the public distribution network through a set-top box. A server with a capture card is set up to retrieve content from the set-top box and run an emulator. To identify the program being retrieved, the electronic program guide must also be accessed. In UGC mode, devices such as the TV client module for a given TV can operate in master mode to add content to the library of the device currently being viewed. The master source module also contains a simple database that identifies basic content metadata (title, channel, etc.) based on a unique content ID. The database only lists the content being retrieved.

10 , the contextual targeting module 64 is a user-facing application that determines content based on a predefined library of closed caption streams for the current segment of content being viewed. The contextual targeting module 64 relies entirely on accurate content detection to retrieve relevant closed caption information, and therefore operates in conjunction with the user management submodule, the point management submodule, and the primary source module.

More specifically, the contextual targeting module 64 sends the retrieved content to a specific widget running on the widget engine 58 of the television system 52 in response to that widget's request. More specifically, a widget running on the television widget engine (or other GUI on the television) periodically sends program information, metadata, and contextually targeted content requests to the server 54. The details of the request depend on the specific functionality required by the television application software. Some examples of server responses are described below.

The first response is an example of a server response to a request for context-targeted content based on closed captioning:

The first exemplary response to the HTTP request includes the following parameters:

The parameter "createdOn" is a timestamp of the creation date/time of the user session and is used to track the time the user has watched TV.

The parameter "token" is the same as the TV unique identifier mentioned above. This ID number is used to connect the channel identification component and the contextual targeting component.

The parameter "channel" identifies the program being watched by name and air date.

The parameter "channelTime" is the playback time (in milliseconds) of the identified content segment. "Playback time" and "time offset" have the same meaning and are used interchangeably in this document.

The parameter "myContent" is a list of content that is targeted at the corresponding position of the program according to the closed caption. This parameter includes three exemplary content items. The parameters of each content item are as follows:

"searchKey" is a unique identifier for a specific content item; "displayName" is the title of the specific content item; "founding" is the closed caption line that matches the specific content item; "engineName" is the internal search engine used (one of multiple search engines with different algorithms and optimized for different programs can be selected); "matchedText" is the specific text in the closed caption stream that triggered the search engine to match the specific content item.

The following is an example server response to a context-targeted content request for a customized index of a specific program:

The second exemplary response to the HTTP request includes the following parameters:

The parameter "widget" is the ID of the custom application that uses this data source.

The parameter "myContent" is a list of contents targeted at the corresponding position of the program based on metadata such as closed captions.

The parameter "searchKey" is a unique identifier for the content.

The parameters "startTime" and "endTime" restrict a specific content item to a specific area of the program.

The parameter "engineName" is the internal search engine to use (in this case a CNN-specific search engine that contains an index of Anderson Cooper's blog entries).

The parameters "byline", "images", "abstract", and "publishDate" are displayed to the user.

According to a method for providing context-targeted content to a television system 52 of the system shown in Figure 10, a server 54 performs the following steps: (a) storing a corresponding data set for each video segment in a plurality of video segments, each data set including data identifying the corresponding video segment, data points extracted from the corresponding video segment television signal, and corresponding time offset data, the time offset data indicating the corresponding timing of the data points extracted from the television signal of the corresponding video segment; (b) receiving data points from the television system 52 when the video segment is displayed on the screen; (c) retrieving identification data and time offset data associated with the data point that most closely matches the received data point from a database, wherein the identification data and time offset data are combined to identify the portion of the video segment being displayed on the screen; (d) when a critical probability of successful identification is reached or exceeded, retrieving content associated with the identified portion of the video segment being displayed on the screen from a database; and (e) sending the retrieved content to the television system 52.

In the embodiment shown in Figure 10, the database 66 stores pixel clue points and the content of multiple video clips, and the server 54 is programmed to perform the following steps: (a) determine the pixel clue points in the database 66 that are likely to match the pixel clue points received from the television system 52 via the network; (b) calculate the probability distribution for the pixel clue points determined in step (a); (c) retrieve the program identifier and broadcast time associated with the pixel clue point (determined to be most likely to match the pixel clue point received from the television system via the network) from the database; (d) retrieve the content associated with the program identifier and broadcast time retrieved in step (c) from the database; and (e) send the content to the television system via the network.

In addition, according to another aspect of the embodiment shown in Figure 10, the television system 52 includes a multi-pixel screen and a processor system, the processor system includes a widget engine and an independent client, the client is programmed to generate requests including pixel clue points, each pixel clue point includes a set of pixel values, and the pixel value set is displayed in a predetermined set of pixels on the screen at a corresponding time, and the predetermined set of pixels is a subset of the total number of pixels on the screen.

According to another aspect of the embodiment shown in FIG10 , a system includes a network, a server 54 connected to the network, and a television system 52 connected to the network. The television system 52 includes a multi-pixel screen and a processor system, the processor system including a widget engine and a client, the client being programmed to send a request to the server, including a pixel cue point. The server 54 includes a database 66 for storing pixel cue points and content of a plurality of video clips, and a processor system programmed to perform the following steps: (a) determining pixel cue points in the database 66 that are likely to match pixel cue points received from the television system 52 via the network; (b) calculating a probability distribution for the pixel cue points determined in step (a); (c) retrieving from the database 66 a program identifier and a play time associated with the pixel cue point determined to be most likely to match the pixel cue point received from the television system 52 via the network; (d) retrieving from the database 66 content associated with the program identifier and play time retrieved in step (c); and (e) transmitting the content to the television system 52 via the network.

According to another automatic processing method for pixel values of a video clip displayed on a multi-pixel screen of a television system 52 of the system shown in FIG10 , the server 54 performs the following steps: (a) storing a corresponding data set for each video clip in a plurality of video clips, each data set including data identifying the corresponding video clip and data points extracted from the corresponding video clip, each pixel clue point including a corresponding subset of a corresponding set of pixel values constituting a corresponding frame of the corresponding video clip; (b) receiving pixel clue points from the television system 52 when displaying the video clip on the multi-pixel screen; (c) determining pixel clue points in a database that are likely to match the received pixel clue points; (d) calculating a probability distribution of the pixel clue points determined in step (c); and (e) retrieving identification data associated with the pixel clue point determined to be most likely to match the received pixel clue point from the database 66, wherein the identification data identifies the video clip displayed on the multi-pixel screen of the television system 52.

To implement the method described in the preceding paragraph, server 54 may further include a metrics software module (not shown in FIG. 10 ) that collects matching information from the user management module and stores the matching information in database 66 for later report generation. The metrics module not only provides useful information about the system's operation but also creates value-added reports that can be sold to companies interested in understanding audience viewing habits. In one embodiment, the metrics data is sent to an aggregator/forwarder for asynchronous storage and unloading of the data into and out of the database. The raw metrics data is first stored in the database and then processed to be incorporated into various reports, such as reports on the number of users who viewed a specific program, reports on the number of users who time-shifted a specific program (via DVR, etc.), and reports on the number of users who viewed a specific advertisement.

While the present invention has been described in conjunction with various embodiments, those skilled in the art will appreciate that various variations of the present invention are possible without departing from the spirit of the invention, and that equivalent elements may be substituted for the elements of the present invention. Furthermore, various modifications may be made to the present invention to accommodate the specific circumstances of the invention without departing from the scope of the invention. Therefore, the specific embodiments disclosed herein should be considered the best modes for carrying out the invention and should not be construed as limitations of the invention.

In the claims, "processor system" should be interpreted broadly to include one or more processors. In addition, the use of alphabetical symbols to describe method steps does not necessarily mean that the corresponding method steps must be performed in alphabetical order.

appendix

The path tracking problem: tracking video transmissions with fuzzy cues

summary

An efficient video tracking method. Due to the large number of video segments, the system must be able to identify in real time the segment from which a given query video input was taken, as well as the time offset. The segment and offset are collectively referred to as the position. The method is called a video tracking method because it must be able to effectively detect and adapt to pauses, fast-forwards, rewinds, sudden switches to other segments, and switches to unknown segments. Tracking live video requires processing a database. Video clues (a small number of pixel values) are acquired for each frame every fraction of a second and placed into a dedicated data structure. ^Video tracking takes the form of continuously receiving clues from the input video and updating a set of confidence values for the current position. Each clue is either consistent with the confidence value or inconsistent with the confidence value and is adjusted to reflect the new evidence. A video position is considered correct if we believe it to be true and have sufficient confidence in it. This can be done efficiently by tracking a small set of possible positions.

introduction

This article presents a video tracking method, explained and investigated using abstract mathematical constructs. The introduction aims to introduce the reader to the necessary transformation tools in both fields. A video signal consists of a series of frames. Each frame can be considered a still image. A frame is a raster of pixels. Each pixel consists of three intensity values, corresponding to the red, green, and blue (RGB) colors of the pixel. In this article, a clue is a list of RGB values for a subset of pixels within a frame and the corresponding time stamp. The number of pixels in a clue is much smaller than the number of pixels in a frame, typically 5-15 pixels. A clue is an ordered list of scalar values, effectively a vector. This vector is also called a point.

While points have a large dimension, typically between 15 and 150, it's possible to think of them as points between two dimensions. In fact, we'll provide illustrations in the form of two-dimensional graphs. Imagine the evolution of a video and its corresponding clue points. Small changes in time result in small changes in pixel value. This pixel can be thought of as "moving" between two frames. Following this tiny shift between frames, the clue follows a spatial path, like a bead on a curved wire.

In this analogy, we receive the spatial position of a bead (a clue point) in video tracking and search for the wire (the path) that the bead follows. However, this process is difficult for two reasons: 1) the bead does not follow the wire's path perfectly, but rather maintains a varying, unknown distance from it; and 2) the wires are all twisted together. See Chapter 2 for a detailed description. The algorithm described below is implemented in two conceptual steps. Upon receiving the clue, all points on the known path that are very close to the clue point are searched; these points are called possible points. This process can be efficiently performed using the PPLEB algorithm. Possible points are added to a history data structure, and the probability of each possible point representing the true position is calculated. This step also involves deleting possible positions that are unlikely. The record update process ensures that only a small number of records are kept, while also ensuring that possible positions are never deleted. The general algorithm is shown in Algorithm 1 and Figure 11.

Chapter 1 introduces the Probability Points of the Average Ball (PPLEB) function. The PPLEB function is used to efficiently execute Line 5 of Algorithm 1. The ability to quickly find possible content is crucial for the applicability of this method. Chapter 2 introduces the statistical model used to execute Lines 6 and 7. This model was a natural choice during the setup process. We also describe how to effectively use it.

1. Average ball probability point

The following describes a simple algorithm for performing Probability Point Location in the Average Sphere (PPLEB). In traditional PLEB, we first set n points x _i in R ^d and specify a sphere of radius r. The algorithm is given O(poly(n)) time preprocessing to produce an efficient data structure. Next, given a query point x, the algorithm returns all points x _i such that ||xx _i || ≤ r. Point sets such as ||xx _i || ≤ r lie geometrically within the sphere of radius r surrounding the query x (see Figure 12). We call this relationship x _i close to x, or x _i and x adjacent.

The PPLEB problem and the nearest neighbor search problem are two similar problems that have attracted widespread attention in academia. In fact, these are also some of the problems encountered in the early research in the field of computational geometry. There are many different methods that adapt to the situation where the environment dimension d is small or constant. These methods divide the space in different ways and recursively search each part, including KD-trees[2] and cover-trees[1]. These methods are very effective in low dimensions, but perform poorly in high environment dimensions. People call it the "curse of dimensionality". Methods that can solve the problem and overcome the curse of dimensionality include the research work of Gionis et al.[3], Lv et al.[5], and Kushilevitz et al.[4]. The algorithm we use is a simplified and fast version of the algorithm described in [3], which mainly relies on locality sensitive hashing.

1.1 Locality Sensitive Hashing

In our locality-sensitive hashing scheme, someone designed a series of hash functions H, such as:

That is, when the probabilities of x and y are close to each other, the probability of x and y being mapped to the same value by h becomes significantly larger.

For clarity, we first deal with a simple scenario where all input vectors have the same length. Detailed explanation follows. First, we set a random function u ∈ U that separates x and y according to the angle between them. Let be a random function vector uniformly selected over the unit sphere, and let (see Figure 13). It is easy to verify that Pr _u～U (u(x))≠u(y))＝θ _x，y /π. In addition, for any point x, y, x', y' on the circle, ||x'- y'||>2||x–y||, such that θ _{x′, y′} ≥ 20 _x，y· . Let p be:

Let the family function H be the vector product of u replicas, independent of t, that is, h(x) = [u ₁ (x), ..., _ui (x)]. Intuitively, when h(x) = h(y), x and y are likely to be close to each other. Let's quantify this. First, calculate the expected value of false positives, n _fp . This is the case where h(x) = h(y) but ||xy|| > 2r. We find that for values t, n _fp does not exceed 1, meaning we are unlikely to make a mistake.

E[n _ft ]≤n(1-2p) ^t ≤1 (5)

→t≥log(1/n)/log(1-2p) (6)

Next, h(x)=h(y) is calculated, provided that the two are adjacent.

Pr(h(x)＝h(y)|||xy||≤r)≥(1-p) ^{log(1/n)/log(1-2p)} (7)

=(1/n) ^{log(1-p)/log(1-2p)} (8)

Note that we must ensure that 2p < 1, which means that the probability of success is not very high. In fact, it is much less than 1/2. The following describes how we can increase this probability to 1/2.

1.2 Point Search Algorithm

Each function h maps each point in space to a bucket. The bucket function for a point x is defined as B _h (x) ≡ { _xi |h( _xi ) = h(x)} relative to the hash function h. The data structure we maintain is an instance of the bucket function, which we return when someone searches for x. Based on the explanation in the previous section, we obtain the two desired results:

Pr(x _i ∈B(x)|||x _i -x||≤r)≥1/2 (10)

In other words, when the probability is not less than 1/2, we can find all the neighboring points of x and basically cannot find non-neighboring points.

1.3 Processing of input vectors with different radii

The previous section only introduced searches within vectors of the same length r′. Now we will introduce how to use structures as building blocks to support searches within different radii. As shown in Figure 14, we divide the space into rings of exponentially increasing width. The i-ring, denoted by R _i, includes all points x _i such that ||x _i ||∈[2r(1+ε) ⁱ , 2r(1+ε) ⁱ⁺¹ ). This achieves two goals. First, if x _i and x _j belong to the same ring, then ||x _j ||/(1+ε)≤||x _i ||≤||x _j ||(1+ε). Second, any search can be performed within a circle no larger than 1/ε. In addition, if the maximum length vector in the data set is r′, the total number of system rings is O(log(r′/r)).

2. Path tracking problem

In the path-following problem, a fixed path in space is known, along with the positions of particles as a time series. The terms particle, clue, and point are used interchangeably. The algorithm must output the position of the particle along the path, but several factors complicate this task.

The particles only roughly follow the path.

The path itself breaks and intersects multiple times.

The particle and path positions are given as a time series of points (different for each point).

Note that this problem can simulate particle tracking on any number of paths. Simply connect the paths together to form a longer path and treat the resulting positions as positions on a single path.

More precisely, let path P be a parametric curve. The curve parameter is called time. A known point on the path is any point in time t _i , meaning we have n known pairs (t _i , P(t _i )). The particle moves along the path, but its known position is at different points in time, as shown in Figure 15 . This gives us m pairs (t ' _j , x(t ' _j )), where x(t ' _j ) is the particle's position expressed in time at t ' _j .

2.1 Likelihood Estimation

Because particles do not follow paths perfectly and paths often intersect each other, it is often impossible to definitively identify a particle's actual position along the path. Therefore, we compute a probability distribution over all possible path positions. If the probability of a position is clearly possible, the particle's position is assumed to be known. The next section describes an efficient implementation.

If the particle follows our path, the particle's time stamp should be fixed relative to the corresponding point in P. In other words, if x(t') is currently offset by t on the path, it should be near P(t). Furthermore, a few seconds ago, τ, should be offset by t-τ. Therefore, x(t'-τ) should be near P(t-τ). ² Define the relative offset as Δ≡tt'. Note that as long as the particle follows the path, the relative offset Δ should remain constant. That is, x(t') should be near P(t'+Δ).

The maximum likelihood relative shift is obtained by calculation.

In short, the most likely relative shift is the most likely relative shift in the particle's history. However, a statistical model must be used to solve this equation. The statistical model must quantify:

x follows a strict procedure for the path.

The probability of x "jumping" between two positions.

Measure the smoothness of path curves and particle curves between points.

2.2 Time Discount Pixel

Now let's introduce a simple statistical model for estimating the likelihood function. The model assumes that particle deviations from the path are normally distributed with a standard deviation αr. Furthermore, it assumes that at any given point in time, the probability of a particle suddenly switching to another path is non-zero. This is represented by an exponential time discount with respect to past points. Besides its reasonable modeling, another advantage of the model is its ability to be efficiently updated. For some constant time unit τ, let the likelihood function be proportional to f defined below:

Here, α<<1 is the proportionality coefficient and ζ>0 is the probability that a particle will turn to a random position in a given time unit.

The function f can be updated efficiently using the following simple observation method.

In addition, since α<<1, if ||x(t′ _m )-P(t _i )||≥r, then:

Now we can only update the neighboring points of x(t′ _j ) instead of the sum of the entire path, so this is an important property of the likelihood function. Let S represent the set (t _i , P(t _i )) such that ||x(t′ _m )-P(t _i )||≤τ, then:

See Algorithm 2.2 for a detailed description. Let f be a sparse vector that also accepts negative integer indices. Set S is the set of all neighbors of x(t _i ) on the path, which can be quickly computed using the PPLEB algorithm. It's easy to first verify that the neighbors of x(t _i ) are bounded by a constant n _near , and then verify that the number of nonzeros in the vector f is bounded by a larger constant. The final step of the algorithm is to output the ratio of δ when f([δ/τ”) is greater than a critical value.

3. Description of the Figures

Figure 11 shows the three connected point locations and the path points surrounding them. Note that using only the bottom point or the middle point alone is not enough to identify the correct portion of the path. However, both the bottom and middle points can be used for identification. The addition of the top point helps us confirm that the particle is actually the final (left) curve of the path.

Figure 12 shows a set of n (gray) points. The algorithm is given a query point (black) and returns the set of points within a distance τ from it (the points in the circle). In the traditional setting, the algorithm must return all points. In the probabilistic setting, the points returned must have a constant probability.

Figure 13 shows the values of u(x ₁ ), u(x ₂ ), and u(x). Intuitively, if the dashed line passes between x ₁ and x ₂ , function u assigns different values to x ₁ and x ₂ , while if it does not, it assigns the same value. The probability of the dashed line passing in a random direction is proportional to the angle between x 1 and x 2 .

In Figure 14, the space is divided into different circles, and R _i is between the radius 2r(1+ε) ⁱ and 2r(1+ε) ⁱ⁺¹ . It is ensured that the lengths of any two vectors in the circle are the same and do not exceed the (1+ε) coefficient. At most 1/ε circles are searched.

A self-intersecting path and query point (black) are shown in Figure 15. Figure 15 shows that it is impossible to learn the position of a particle on the path without its position history.

Figure 16 shows three consecutive points and the path points surrounding them. Note that neither x(t ₁ ) nor x(t ₂ ) alone is sufficient to identify the correct portion of the path. Only the combination of x(t ₁ ) and x(t ₂ ) allows proper identification. The addition of x(t ₃ ) helps us confirm that the particle is actually the final (left-hand) curve of the path.

References

[l]Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In ICML, pages 97-104, 2006.

[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd revised edition, September 2001.

[3] Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In VLDB, pages 518-529, 1999.

[4] Eyal Kushilevitz, Rafaii Ostrovsky, and Yuval Rabani. Efficientsearch for approximate nearest neighbor in high dimensional spaces. SI AMJ. Comput., 30(2):457-474,2000.

[5] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe Ish: Efficient indexing for high-dimensional similarity search. In VLDB, pages 950-961, 2007.

Claims (17)

1. A method for determining context-oriented content, comprising: The server determines the point sampling instructions to be sent to the media system; The server sends the point sampling command to the media system; The server receives a message including pixel clues, wherein the message is associated with the point sampling instruction, and wherein the pixel clues include the average of the pixel values of a plurality of individual pixels in a two-dimensional pixel array in a frame of a video clip displayed by the media system. The server uses the pixel clues to determine the content to be sent to the media system, wherein the content is associated with the video segment; and The content is sent by the server, and the content is sent to the media system to be displayed together with one or more frames that are being displayed by the media system. 2. The method of claim 1, wherein the pixel cue point is associated with the point sampling instruction, and/or the two-dimensional pixel array is each of a plurality of different two-dimensional pixel arrays sampled from a frame of the video segment displayed by the media system. 3. The method of claim 1, wherein the content is determined by matching the pixel cue points with stored pixel cue points. 4. The method of claim 1, wherein the point sampling instruction indicates a plurality of pixel values to be used for pixel cue points. 5. The method of claim 1, wherein the point sampling instruction indicates the frequency at which the media system samples pixel clue points. 6. The method of claim 1, further comprising: The video segment being displayed by the media system is identified based on the pixel cues. 7. A system for determining context-oriented content, comprising: One or more processors; and A non-transitory computer-readable medium comprising instructions that, when executed by the one or more processors, cause the one or more processors to: Determine the point sampling command to be sent to the media system; Send the point sampling command to the media system; Receive a message including pixel clues, wherein the message is associated with the point sampling instruction, and wherein the pixel clues include the average of the pixel values of a plurality of individual pixels in a two-dimensional pixel array in a frame of a video clip displayed by the media system; The pixel cues are used to determine the content to be sent to the media system, wherein the content is associated with the video segment; and The content is sent to the media system for display along with one or more frames that are being displayed by the media system. 8. The system of claim 7, wherein the pixel cue point is associated with the point sampling instruction, and/or the two-dimensional pixel array is each of a plurality of different two-dimensional pixel arrays sampled from a frame of the video segment displayed by the media system. 9. The system of claim 7, wherein the content is determined by matching the pixel cue points with stored pixel cue points. 10. The system of claim 7, wherein the point sampling instruction indicates a plurality of pixel values to be used for pixel cue points. 11. The system of claim 7, wherein the point sampling instruction indicates the frequency at which the media system samples pixel cue points. 12. The system of claim 7, wherein when the one or more processors execute the instructions, the instructions further cause the one or more processors to: The video segment being displayed by the media system is identified based on the pixel cues. 13. A method for displaying context-oriented content, comprising: Receives signals containing video data, including video clips; The media system displays frames of the video segment based on the video data. The media system receives point sampling instructions from a remote server; The media system generates a request based on the point sampling instruction. The request includes the media system's identification, time stamp, and pixel cue points. The request is sent to the remote server, and the pixel cue points are generated by mathematically transforming the pixel values of multiple individual pixels in a two-dimensional pixel array in the frame. The request is sent by the media system, wherein the request is sent to the remote server; The media system receives content data from the remote server in response to sending the request, wherein the content data represents content associated with frames of the video segment being displayed by the media system; and The content associated with the frame is displayed while one or more other frames of the video segment are being displayed by the media system. 14. The method of claim 13, wherein the request is sent to the server based on the point sampling instruction, and/or the two-dimensional pixel array is each of a plurality of different two-dimensional pixel arrays sampled from a frame of the video segment displayed by the media system. 15. The method of claim 13, wherein the pixel cue points are generated based on the point sampling instructions. 16. The method of claim 13, wherein the number of pixel values used for the mathematical transformation is based on the point sampling instruction. 17. The method of claim 13, wherein the frequency at which the media system samples the pixel cue points is based on the cue point sampling instruction.