HK1254819B - Detection of common media segments - Google Patents

Description

Detection of public media segments

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit under 35 U.S.C. §119(e) of U.S. Provisional Application No. 62/193,322, filed on July 16, 2015, the entire contents of which are incorporated herein by reference.

This application is related to U.S. Patent Application No. 14/089,003, filed November 25, 2013, now U.S. Patent No. 8,898,714, issued November 25, 2014; U.S. Patent Application No. 14/217,075, filed June 9, 2015 (now U.S. Patent No. 9,055,309); U.S. Provisional Application No. 61/182,334, filed May 29, 2009; and U.S. Provisional Application No. 61/182,334, filed May 29, 2009. U.S. Provisional Application No. 61/290,714, filed December 29, 2009; U.S. Patent Application No. 12/788,748, issued July 1, 2014 (now U.S. Patent No. 8,769,584); U.S. Patent Application No. 12/788,721, issued November 26, 2013 (now U.S. Patent No. 595,781), all of which are incorporated herein by reference in their entirety.

Summary of the Invention

An automatic content recognition (ACR) system provides information about the content displayed by a specific media display device at a specific point in time. The ACR system can be implemented as a video matching system. Typically, a video matching system can operate by the following steps: obtaining data samples from a known video data source, generating identification information from these samples, and storing the identification information in a database together with known information about the video. A specific media device can obtain data samples from an unknown video being displayed, generate identification information from the samples, and attempt to match the identification information with the identification information stored in the database. When a match is found, the specific media device can receive the known information about the video from the database. Typically, the matching operation performed by the media device can be performed in real time, that is, when the video is being displayed on the device.

Systems, methods, and computer program products are provided for identifying a media content stream when the media content stream is currently playing an unscheduled common media segment. In various embodiments, a computing device may be configured to identify media content currently being played by a media display device at a specific time. The computing device may be configured to implement a video matching system. The computing device may receive multiple media content streams, wherein at least two of the multiple media content streams simultaneously include the same unscheduled media segment. The computing device may be configured to determine that the media display device is currently playing an unscheduled media segment. To make this determination, the computing device may examine each of the multiple media content streams for media content available at the current time. The computing device may be further configured to determine identification information from the media content included in the media content stream currently being played by the media display device. The identification information may identify the media content stream. The computing device may further determine context-related content. When the unscheduled media segment is currently being played by the media display device, the context-related content may be disabled. The computing device may be further configured to display the media content stream and the context-related content after the unscheduled media segment has been played.

In various implementations, identification information identifying a media content stream is used to select context-relevant content.The context-relevant content can be provided to a media display device.

In various implementations, identifying the media content stream may include detecting a graphic superimposed on the unscheduled media segment while the unscheduled media segment is being played by the media display device. The graphic may provide additional identification information for the media content stream.

In various implementations, the media content used to determine the identification information may include media content included in the media content stream before or after the unscheduled media segment.

In various embodiments, the computing device may be configured to determine that the media display device has been playing the unscheduled media segment since starting from the unscheduled media segment. In these embodiments, the computing device may identify the media content stream using identification information determined for media content included in the media content stream prior to the unscheduled media segment.

In various embodiments, the computing device may be configured to determine that the media display device has been playing the unscheduled media segment since a time point after the start of the unscheduled media segment. In these embodiments, the computing device may identify the media content stream using identification information of media content included in the media content stream after the unscheduled media segment.

BRIEF DESCRIPTION OF THE DRAWINGS

Illustrative embodiments are described in detail below with reference to the following drawings:

Figure 1 shows a matching system that can identify unknown content;

FIG2 illustrates components of a matching system for identifying unknown data;

FIG3 shows an example of a video excerpt capture system including a memory buffer 302 of a decoder;

FIG4 shows a video excerpt capture system including a memory buffer of a decoder;

FIG5 shows an example of a video matching system for an interactive television system;

FIG6 shows an example in which multiple content streams simultaneously carry the same media segment;

FIG7 shows another example, where multiple media streams, here shown as television channels, simultaneously display the same media content;

FIG8 shows an example in which multiple media content streams carry the same common media segments almost simultaneously;

FIG9 shows an example of a graphic that has been superimposed onto a common media segment being played by a media display device;

FIG10 illustrates an example of a process that may be implemented when multiple media content streams include the same unscheduled media segments;

FIG11 is a diagram illustrating a point location and waypoints around the point location;

FIG. 12 is a graph showing the set of points that are within a radius “r” distance from a query point “x”.

FIG13 is a chart showing possible point values where angles in “n” dimensional space are calculated as part of candidate point qualification;

FIG14 is a diagram illustrating the combination of FIG12 and FIG13, wherein the distance and angle from the query point "x" are applied to determine candidate "suspects" for submission to the further matching system step of path tracing;

FIG15 is a diagram showing self-intersecting paths and query points; and

FIG. 16 is a diagram showing three consecutive point positions and waypoints around the point positions.

DETAILED DESCRIPTION

Automatic content recognition (ACR) systems provide information about the content displayed by a specific media display device at a specific point in time. For example, the ACR system can provide information such as the channel being watched, the title of the video, some text identifying the video or video content, the portion of the video being watched, one or more categories of the video, the author and/or producer of the video, etc. This information can then be used, for example, to provide viewing statistics for the video (e.g., how many people watched the video, at what time, and how frequently, etc.) and/or suggest targeted content to the viewer, such as advertisements or interactive content.

The ACR system can be implemented as a video matching system. Generally, a video matching system can operate by obtaining data samples from a known video data source, generating identification information from these samples, and storing the identification information together with the known information about the video in a database. A specific media device can use a similar process to identify unknown video content. Specifically, the media device can obtain data samples from an unknown video being displayed, generate identification information from the samples, and attempt to match the identification information with the identification information stored in the database. When a match is found, the specific media device can receive the known information about the video from the database. Generally, the matching operation performed by the media device can be performed in real time, that is, while the video is being displayed on the device.

However, when the same content is displayed on multiple channels at the same time, the video matching system described above may have difficulty identifying the media content being displayed by the media device. In addition, the system may not be able to determine, for example, which channel the viewer is watching, or what context-related information to provide.

One example of multiple channels showing the same content simultaneously occurs when multiple local television stations provide syndicated content to support a "breaking news" story. For example, a national broadcaster (e.g., ABC, CBS, NBC, CNN, etc.) may provide a video feed during a political speech, natural disaster, or man-made event. In this example, multiple national and/or local broadcast channels may pick up the video feed while the national broadcaster is broadcasting and may rebroadcast the feed to local viewers. As a result, multiple channels may be showing the same video content simultaneously. The same situation may occur in other situations, such as when multiple channels are showing the same commercial or sporting event simultaneously.

As described above, the video matching system can rely on data samples collected from known video sources (such as local and national channels), where program information can provide information such as the title or other identification string of the video content and other information about the video content. However, when multiple channels display the same content, the video matching system may not be able to uniquely identify the video content. For example, the video matching system may associate a video with two or more channels. Subsequently, if the media device is tuned to one of the channels carrying the same content, the video matching system may not be able to determine which channel his media device has been tuned to.

In various embodiments, the video matching system can be configured to improve the accuracy of automatic content recognition in the presence of ambiguity caused by common video segments appearing simultaneously on multiple channels. Without the accuracy improvement, the presence of common video segments displayed simultaneously on multiple channels being monitored can cause ambiguity in identifying the content being displayed by the media device. In various embodiments, the video matching system can use information from the media content displayed on the media display device before and/or after the media device begins displaying the common video segments. Using this information, the video matching system can attach identification information to samples obtained from the common video segments.

On national and local channels that may display a common video segment at a certain point in time, the channel may provide some uniquely identifiable content before displaying the common video segment. In various embodiments, this unique content may be used to help identify the common video segment. For example, in some broadcast news, portions of the news program are known to be from a local channel. For example, the news program may introduce and/or comment on the common video segment before it is displayed. The introductory segment may be referred to as a "talk head" segment, that is, a segment where two or more people sit behind a table and are framed in the video from center chest up. When a "talk head" segment is detected, the video matching system may, for example, add a new timeline signal or event that may be used to help identify the common video segment.

In various embodiments, a media display device configured to use a video matching system can obtain and track timeline signals or events, such as timeline signals or events that can be generated for a "talk head" segment. In these embodiments, when a media device encounters an unknown and possibly public video segment, the media device can check the timeline event. In one case, the media device may not find a timeline event that can indicate to the media device that the device has just turned on or tuned to a channel displaying public video content. In this case, the data collection process of the media device can be configured to avoid using public video segments for identification. In other cases, the media device can use timeline events received before and/or after the public video segment to generate identification information for the public video segment.

In various implementations, video matching can also use timeline events to more quickly identify commercials. Generally, the amount of time it takes for a video matching system to acquire enough samples to match a known commercial with a high probability can be referred to as the "commercial confidence interval." Using the techniques described herein, the commercial confidence interval can be reduced when a media device uses timeline events within a specified past time window.

I. Audio-Visual Content

In various embodiments, the video content matching system can be configured to identify media content being displayed by a media display device. In various embodiments, the video content system can be used to provide contextually directed content to the media display device, wherein the directed content is selected based on the identified media content.

Media content includes video, audio, text, graphics, tactile representations of visual and/or audible data, and various combinations of visual, auditory, or tactile information. For example, media content may include synchronized audio and video, such as a movie or television program. As another example, media content may include text and graphics, such as a web page. As another example, media content may include photos and music, such as a photo slideshow with a movie soundtrack.

A media display device may be a device capable of displaying various media content. A media display device may include, for example, a television system. A television (TV) system includes, for example, a network television and a connected television (also known as a "smart TV"), and optionally, devices integrated into or coexisting with the television, such as a set-top box (STB), a digital video disc (DVD) player, and/or a digital video recorder (DVR).

A wired TV is a TV that is connected to a network, such as the Internet. In various embodiments, a network-connected TV can be connected to a local wired or wireless network, such as, for example, in a private home or business office. A wired TV can run an application platform such as Google's Android, or some other platform configured to provide interactive smartphone or tablet-like software applications (which may also be referred to as "apps").

In various embodiments, a media display device may receive a signal such as a television signal. A television signal, for example, includes a signal representing video and audio data that are broadcast together and synchronized for simultaneous display. For example, a television signal may include television programs and/or commercials. In some cases, a television signal may include additional information related to the audio-video content in the television signal. This additional data may be referred to as "metadata." The term "metadata" may also be used to describe information related to other video or audio-video content transmitted in addition to the television signal (e.g., transmitted over a network in the form of digitized and/or packetized data). Metadata may include information about the content, such as information identifying the content, a description of the content, one or more categories of the content, the author and/or publisher of the content, and the like. Because metadata is sent together with the content associated with the metadata, metadata can be used to provide information about the content while the content is being viewed or played.

Not all media display devices have access to metadata. Therefore, not all media display devices can determine the content they are displaying or playing at any given moment. Without this information, media display devices may not be able to provide customized or personalized content or advertisements to specific viewers. Although some information about the content being provided to the media display device may be available in the distribution channel, this information may be lost or removed before the content reaches the media display device.

In some embodiments, various methods can be used to provide metadata for audio-video content. For example, in some embodiments, identifying information can be encoded into the content using watermarks. In these embodiments, the identifying information can be encoded so that it is not lost when the content is compressed for transmission and decompressed for display. However, this approach may require that the receiving media display device be able to extract the identifying information from the content. Furthermore, these approaches may not be able to achieve instant identification of the specific video being played using fraction-of-a-second identification capabilities.

In various embodiments, advances in fiber optic and digital transmission technology have enabled the media industry to offer large channel capacities, where a "channel" includes traditional broadcast channels, satellite signals, digital channels, streaming content, and/or user-generated content. In some cases, a media provider such as a satellite system may be referred to as a multi-channel video programming distributor (MVPD). In some embodiments, media providers may also be able to use the increased data capacity of modern transmission systems to offer some interactive content, such as interactive television (ITV). Increased processing power in smart TVs, set-top boxes, and similar devices may further facilitate interactive content.

Interactive television can make television system be used as two-way information distribution mechanism in the mode similar to the World Wide Web.Interactive television can provide various marketing, entertainment and educational capabilities, such as for example making it possible for viewers to order products or services displayed on advertisements, compete with contestants in game shows, participate in live classroom sessions, etc. In some embodiments, interactive functions can be controlled by a set-top box. In these embodiments, the set-top box can perform interactive programs associated with video content, such as television broadcasts. Interactive functions can be displayed on the screen of the television and can include icons or menus to allow viewers to select via the remote control or keyboard of the television.

In various embodiments, interactive content can be incorporated into audio-video content. In some embodiments, the audio-video content can consist of a broadcast stream. A broadcast stream can also be referred to as a "channel" or "network feed." The term "broadcast stream" can refer to a broadcast signal received by a television via, for example, an antenna, satellite, coaxial cable, digital subscriber line (DSL) cable, fiber optic cable, or some other transmission medium. In various embodiments, interactive content can be incorporated into the audio-video content using "triggers." Triggers can be inserted into the content of a particular program. Content that includes triggers can be referred to as "enhanced program content," "enhanced television programs," or "enhanced video signals." Triggers can be used (e.g., at a processor in a set-top box or smart TV) to alert a media display device that interactive content is available. Triggers can include information about the available content and where to find the interactive content (e.g., a memory address, a network address, and/or a website address). Triggers can also include information that can be displayed to the viewer on the media display device. For example, the information provided by the trigger can be displayed at the bottom of a screen provided by the media display device. The displayed information can prompt the viewer to perform some action or select from multiple options.

II. Video Matching

In various embodiments, the video content system can be configured to identify media content being displayed or played by a media display device. In various embodiments, information identifying the content being viewed at a particular moment can be used to capture specific reactions from the viewer and respond appropriately, such as requesting that the content be rewound or that the video be replayed from the beginning. Alternatively or additionally, the identification information can be used to trigger targeted content, such as advertisements, that can be provided by content providers or advertisers. Information identifying audio-video content can therefore be used to provide viewer-customized video-on-demand (VoD) capabilities to devices that do not otherwise have smart TV capabilities.

In various embodiments, video segments can be identified by sampling a subset of pixel data being displayed on a screen of a media display device at regular intervals and then searching for similar pixel data in a content database. In some embodiments, video segments can be identified by extracting audio data associated with the video segments and searching for similar audio data in a content database. In some embodiments, video segments can be identified by processing the audio data associated with the video segments using automatic speech recognition technology and searching text transcripts from known video content to locate matching text phrases. In some embodiments, video segments can be identified by processing metadata associated with the video segments.

In various embodiments, the video matching system can be used to provide context-specific content to the interactive media display system. The context-specific content can be based on the identity of the video segment being displayed, the time of day or night, 3 p.m., etc., and/or the portion of the video segment currently being displayed (e.g., the current offset from the start of the video). Here, "play time" and "offset time" can be used interchangeably to describe the portion of the video currently being displayed.

In various embodiments, a media display device equipped with a content matching system having identified content currently being displayed or played by the media display device may be able to infer the subject matter of the content and interact accordingly with the viewer. For example, the media display device may be able to provide instant access to a video-on-demand version of the content and/or a higher resolution or 3D format of the content. In addition, the media display device may provide the ability to restart, fast-forward, pause, and rewind the content. In various embodiments, advertisements may be included in the content. In these embodiments, some or all of the advertising messages may be customized, such as, for example, for the viewer's geographic location, demographic group, or shopping history. Alternatively or additionally, the number or length of advertisements may be reduced, or advertisements may be deleted entirely.

In various embodiments, once a video segment is identified, the offset time can be determined by sampling a subset of the pixel data (or associated audio data) displayed or played by the media display device and searching for similar pixel (or audio) data in a content database. In various embodiments, the offset time can be determined by extracting audio or image data associated with such a video segment and searching for similar audio or image data in a content database. In various embodiments, the offset time can be determined by processing the audio data associated with such a video segment using automatic speech recognition technology. In various embodiments, the offset time can be determined by processing metadata associated with such a video segment.

In various embodiments, a system for video matching may be included in a television system. In various embodiments, the television system includes a wired television. In various embodiments, the video matching system may be included partially in the wired television and partially on a server connected to the wired television via the Internet.

FIG1 illustrates a matching system 100 that can identify unknown content. In some examples, the unknown content may include one or more unknown data points. In such examples, the matching system 100 can match the unknown data points with reference data points to identify unknown video segments associated with the unknown data points. The reference data points may be included in a reference database 116.

Matching system 100 includes a client device 102 and a matching server 104. Client device 102 includes a media client 106, an input device 108, an output device 110, and one or more background applications 126. Media client 106 (which may include a television system, a computer system, or other electronic device capable of connecting to the Internet) can decode data associated with a video program 128 (e.g., a broadcast signal, data packets, or other frame data). Media client 106 can place the decoded content of each frame of the video into a video frame buffer in preparation for display or further processing of the pixel information of the video frame. Client device 102 can be any electronic decoding system that can receive and decode a video signal. Client device 102 can receive video program 128 and store the video information in a video buffer (not shown). Client device 102 can process the video buffer information and generate unknown data points (which may be referred to as "clues"), as described in more detail below with reference to FIG. Media client 106 can send the unknown data points to matching server 104 for comparison with reference data points in reference database 116.

The input device 108 may include any suitable device that allows requests or other information to be input into the media client 106. For example, the input device 108 may include a keyboard, a mouse, a voice recognition input device, a wireless interface for receiving wireless input from a wireless device (e.g., from a remote control, a mobile device, or other suitable wireless device), or any other suitable input device. The output device 110 may include any suitable device that can present or otherwise output information, such as a display, a wireless interface for sending wireless output to a wireless device (e.g., to a mobile device or other suitable wireless device), a printer, or other suitable output device.

The matching system 100 may begin the process of identifying video segments by first collecting data samples from known video data sources 118. For example, the matching server 104 collects data from various video data sources 118 to build and maintain a reference database 116. The video data sources 118 may include media providers of television programs, movies, or any other suitable video sources. The video data from the video data sources 118 may be provided as a streaming source from a radio broadcast, a cable TV channel, from the Internet, or from any other video data source. In some examples, as described below, the matching server 104 may process received video from the video data sources 118 to generate and collect reference video data points in the reference database 116. In some examples, the video programs from the video data sources 118 may be processed by a reference video program excerpt system (not shown), which may generate reference video data points and send them to the reference database 116 for storage. The reference data points may be used as described above to determine information that is subsequently used to analyze unknown data points.

Matching server 104 may store reference video data points for each video program received within a time period (e.g., days, weeks, months, or any other suitable time period) in reference database 116. Matching server 104 may establish and continuously or periodically update reference database 116 of sample television programs (e.g., including reference data points, which may also be referred to as clues or clue values). In some examples, the collected data is a compressed representation of video information sampled from periodic video frames (e.g., every fifth video frame, every tenth video frame, every fifteenth video frame, or another suitable number of frames). In some examples, the number of bytes of data per frame is collected for each program source (e.g., 25 bytes per frame, 50 bytes per frame, 75 bytes per frame, 100 bytes per frame, or any other number of bytes per frame). Any number of program sources may be used to obtain video, such as 25 channels, 50 channels, 75 channels, 100 channels, 200 channels, or any other number of program sources. Using this example amount of data, the total data collected over a three-day, 24-hour period becomes very large. Therefore, reducing the number of actual reference data point sets is beneficial to reducing the storage load of the matching server 104 .

The media client 106 may send a communication 122 to the matching engine 112 of the matching server 104. The communication 122 may include a request for the matching engine 112 to identify unknown content. For example, the unknown content may include one or more unknown data points, and the reference database 116 may include multiple reference data points. The matching engine 112 may identify the unknown content by matching the unknown data points with reference data in the reference database 116. In some examples, the unknown content may include unknown video data presented by a display (for video-based ACR), a search query (for a Map Reduce system, a Bigtable system, or other data storage system), an unknown facial image (for facial recognition), an unknown pattern image (for pattern recognition), or any other unknown data that can be matched against a database of reference data. The reference data points may be derived from data received from the video data source 118. For example, the data points may be extracted from information provided by the video data source 118 and may be indexed and stored in the reference database 116.

Matching engine 112 can send a request to candidate determination engine 114 to determine candidate data points from reference database 116. A candidate data point can be a reference data point that is a certain distance away from the unknown data point. In some examples, the distance between the reference data point and the unknown data point can be determined by comparing one or more pixels of the reference data point (e.g., a single pixel, a value representing a group of pixels (e.g., an average, mean, median, or other value), or other suitable number of pixels) to one or more pixels of the unknown data point. In some examples, the reference data point can be a certain distance away from the unknown data point when the pixels at each sample location are within a specific range of pixel values.

In one illustrative example, the pixel value of a pixel may include a red value, a green value, and a blue value (in a red-green-blue (RGB) color space). In such an example, a first pixel (or a value representing a first group of pixels) may be compared to a second pixel (or a value representing a second group of pixels, where the second group of pixels is located in the same display buffer location as the first group of pixels) by comparing the corresponding red value, green value, and blue value, respectively, and ensuring that the values are within a certain value range (e.g., within a value range of 0-5). For example, a first pixel may be matched to a second pixel when (1) the red value of the first pixel is within 5 values of the 0-255 value range (positive or negative) of the red value of the second pixel, (2) the green value of the first pixel is within 5 values of the 0-255 value range (positive or negative) of the green value of the second pixel, and (3) the blue value of the first pixel is within 5 values of the 0-255 value range (positive or negative) of the blue value of the second pixel. In such an example, a candidate data point is a reference data point that closely matches the unknown data point, thereby resulting in identification of multiple candidate data points (related to different media segments) for the unknown data point.The candidate determination engine 114 can return the candidate data points to the matching engine 112.

For a candidate data point, the matching engine 112 may add a token to a bin associated with the candidate data point and assigned to the identified video segment from which the candidate data point was derived. Corresponding tokens may be added to all bins corresponding to the identified candidate data point. As the matching server 104 receives more unknown data points (corresponding to the unknown content being viewed) from the client device 102, a similar candidate data point determination process may be performed, and tokens may be added to the bins corresponding to the identified candidate data points. Only one of these bins corresponds to the unknown video content segment being viewed, while the other bins correspond to candidate data points that are matched due to similar data point values (e.g., having similar pixel color values) but do not correspond to the actual video content segment being viewed. The bin for the candidate video content segment corresponding to the unknown video segment being viewed will have more tokens assigned to it than other bins for video content segments that do not correspond to the unknown video segment. For example, as more unknown data points are received, a greater number of reference data points corresponding to that bin are identified as candidate data points, resulting in more tokens being added to that bin. Once a bin includes a certain number of tokens, that is, the bin reaches a predetermined threshold, the matching engine 112 can determine that the video segment associated with the bin is currently being displayed on the client device 102. The video segment can include an entire video program or a portion of a video program. For example, a video segment can be a video program, a scene of a video program, one or more frames of a video program, or any other portion of a video program.

FIG2 illustrates components of a matching system 200 for identifying unknown data. For example, a matching engine 212 can use a database of known content (e.g., known media segments, information stored in a database for comparison searches, known faces or patterns, etc.) to perform a matching process for identifying unknown content (e.g., unknown media segments, search queries, images of faces or patterns, etc.). For example, the matching engine 212 receives unknown data content 202 (which can be referred to as a "clue") that matches a reference data point 204 in a reference database. The unknown data content 202 can also be received by or sent from the matching engine 212 to the candidate determination engine 214. The candidate determination engine 214 can perform a search process to identify candidate data points 206 by searching the reference data points 204 in the reference database. In one example, the search process can include a nearest neighbor search process that generates a set of neighboring values (at a certain distance from the unknown value of the unknown data content 202). The nearest neighbor search process is discussed in more detail below. Candidate data points 206 are input to a matching engine 212 for a matching process to generate matching results 208. Matching results 208 may include video data presented by a display, search results, faces determined using facial recognition, patterns determined using pattern recognition, or any other results depending on the application.

When determining candidate data points 206 for an unknown data point (e.g., unknown data content 202), the candidate determination engine 214 determines the distance between the unknown data point and reference data points 204 in the reference database. Reference data points that are a certain distance away from the unknown data point are identified as candidate data points 206. In some examples, the distance between the reference data point and the unknown data point can be determined by comparing one or more pixels of the reference data point to one or more pixels of the unknown data point, as described above with respect to FIG. 1. In some examples, the reference data point can be a certain distance away from the unknown data point when the pixels at each sample location are within a specific value range. As described above, a candidate data point is a reference data point that approximately matches the unknown data point, and due to the approximate match, multiple candidate data points (related to different media segments) are identified for the unknown data point. The candidate determination engine 114 can return the candidate data points to the matching engine 112.

Figure 3 shows an example of a video excerpt capture system 400 including a storage buffer 302 of a decoder. The decoder can be part of the matching server 104 or the media client 106. The decoder can operate without or require a physical television display panel or device. The decoder can decode and, if necessary, decrypt a digital video program into an uncompressed bitmap representation of the television program. In order to establish a reference database of reference video data (e.g., reference database 316), the matching server 104 can obtain one or more arrays of video pixels read from the video frame buffer. The array of video pixels is called a video block. The video block can be any shape or pattern, but for the purposes of this specific example, it is described as a 10×10 pixel array, comprising ten pixels horizontally and ten pixels vertically. Also for the purposes of this example, it is assumed that there are 25 pixel block positions extracted from the video frame buffer that are evenly distributed within the boundaries of the buffer.

An example allocation of pixel blocks (e.g., pixel block 304) is shown in FIG3. As described above, a pixel block can include a pixel array, such as a 10×10 array. For example, pixel block 304 includes a 10×10 pixel array. Pixels can include color values, such as red, green, and blue values. For example, pixel 306 having a red-green-blue (RGB) color value is shown. The color value of a pixel can be represented by an eight-bit binary value for each color. Other suitable color values that can be used to represent the color of a pixel include brightness and chrominance (Y, Cb, Cr, also known as YUV) values or any other suitable color values.

An average (or, in some cases, mean value) is taken for each pixel block, and the resulting data record is created and marked with a time code (or timestamp). For example, the average is found for each 10×10 pixel block array, in which case each of the 25 display buffer locations produces 24 bits of data for a total of 600 bits of pixel information per frame. In one example, the average value for pixel block 304 is calculated and shown by pixel block average 308. In one illustrative example, the time code may include "epoch time," which represents the total elapsed time (in fractions of a second) since midnight on January 1, 1970. For example, the value of pixel block average 308 is combined with time code 412. Epoch time is a recognized convention in computing systems (including, for example, Unix-based systems). Information about the video program (referred to as metadata) is appended to the data record. The metadata may include any information about the program, such as a program identifier, program time, program length, or any other information. The data record including the pixel block average, time code, and metadata forms a "data point" (also referred to as a "thread"). Data point 310 is an example of a reference video data point.

The process of identifying unknown video segments begins with steps similar to those used to create a reference database. For example, FIG4 illustrates a video excerpt capture system 400 including a memory buffer 402 of a decoder. The video excerpt capture system 400 can be part of a client device 102 that processes data presented by a display (e.g., on an Internet-connected television monitor (such as a smart TV), a mobile device, or other television viewing device). The video excerpt capture system 400 can utilize a similar process to generate unknown video data points 410 as used by the system 300 for creating reference video data points 310. In one example, the media client 106 can send the unknown video data point 410 to the matching engine 112 for the matching server 104 to identify video segments associated with the unknown video data point 410.

As shown in Figure 4, video block 404 may comprise a 10×10 pixel array. Video block 404 may be extracted from a video frame presented on a display. A plurality of such pixel blocks may be extracted from a video frame. In an illustrative example, if 25 such pixel blocks are extracted from a video frame, the result will be a point representing a position in a 75-dimensional space. An average (or mean) may be calculated for each color value of the array (e.g., RGB color values, Y, Cr, Cb color values, etc.). A data record (e.g., unknown video data point 410) is formed by the average pixel value, and the current time is appended to the data. The above-described techniques may be used to send one or more unknown video data points to a matching server 104 for matching with data from a reference database 116.

III. Common video segments

FIG5 shows an example of a video matching system 500 for an interactive television (TV) system 501. The interactive television system 501 is given as an example of a media display device. In this example, the interactive television system 501 includes a television client 503 and a background-directed client 502. The television client 503 can receive television programs 505. The television programs 505 can include audio-video content, which can include audio, video and/or video data with synchronized audio data. In some cases, the television programs 505 can include metadata. The television client 503 can be configured to display audio-video content, including displaying video content on a screen and/or playing audio content through speakers. The television programs 505 can be received from various sources including broadcast television providers, satellite television providers, Internet media providers, audio-video playback devices (e.g., DVD players, DVR players, VCR players, etc.).

In various embodiments, the video matching system may include a matching server 509. Matching server 509 may identify media displayed or played by interactive television system 501. To provide video matching services, matching server 509 may receive known media cue data 517 from an excerpt server 520. Excerpt server 520 may obtain data from various known sources, such as video on demand (VoD) content feeds 515a, local channel feeds 515b, and national channel feeds 515c. Each of these known sources may provide media data (e.g., video and/or audio) and information identifying the media data, such as a program guide or metadata. In various embodiments, excerpt server 520 may generate known media cue data 517 from the media data received from the various sources. Excerpt server 520 may provide known media cue data 517 to various recipients, including matching server 509.

In various embodiments, the excerpt server 520 may also provide program identification and time data 514. In various embodiments, the program identification and time data 514 is synchronized with the known media cue data 517, meaning that the program identification and time data 514 identifies the known media cue 517 and/or provides the time at which the media associated with the known media cue is expected to be displayed. The program identification and time data 514 may also be referred to as metadata.

In various embodiments, known media cue data 517 provides a clue or key for identifying video and/or audio data. Known media cue data 517 may have been obtained from known audio-visual media, such that known media cue 517 can be associated with the name and/or some other identifying information of the known audio-visual media. As described in further detail below, known media cue 517 can be compared to similar cues obtained from media displayed or played by interactive television system 501 for matching. Matching server 509 can store known media cue data 517 and program identification data 514 in database 512.

In various embodiments, matching server 509 may include a channel identification system 510. Channel identification system 510 may receive unknown media cues 507a from interactive television system 501. For example, television client 503 may obtain samples of the audio-video data being displayed or played at any given time and may generate cues from the samples. Television client 503 may provide these cues as unknown media cues 507a to channel identification system 510 in matching server 509. Channel identification system 510 may then match unknown media cues 507a with known media cues 517 to identify the media being displayed or played by interactive television system 501.

In various embodiments, channel identification system 510 determines a program identifier for unknown media cue 507a. The program identifier may include a name or description, or some other information that identifies the media content displayed by interactive television system 501. Channel identification system 510 may also provide a time, where the time indicates when the media was played by interactive television system 501.

In various embodiments, channel identification system 510 may provide program identification and time data 513 to contextual manager 511. Using program identification and time data 513, contextual manager 511 may determine contextually relevant content 507b, including, for example, applications and advertisements. Contextual manager 511 may provide contextually relevant content 507b to interactive television system 501. For example, interactive television system 501 may include a contextually relevant engine 502 for managing contextually relevant content 507b. In some embodiments, contextual manager 511 may also provide event trigger 507c to contextual manager 502. Event trigger 507c may instruct contextual manager 502 to play or display contextually relevant content 507b. For example, event trigger 507c may instruct contextual manager 502 to display a contextually relevant information overlay, where the information overlay cooperates with the display of video content associated with the information overlay. Alternatively or additionally, event trigger 507c may cause alternative media, such as a targeted advertisement, to be displayed. In some implementations, the contextually oriented engine 502 may provide an event confirmation 507d to the contextually oriented manager 511, the event confirmation 507d indicating that the instructions provided by the event trigger 507c have been executed.

In various embodiments, the contextual client 502 may alternatively or additionally provide viewing information to the matching server 509. For example, in addition to or in lieu of the event confirmation 507d, the contextual client 502 may provide viewing information. In this embodiment, the viewing information may include, for example, information about how frequently a particular media segment is played, the time of day or day of the week at which the media segment is played, content played before and/or after the media segment, and/or the channel on which the media segment is played. In some cases, the viewing information may also include information about the audience, such as demographic information.

In various embodiments, a media display device may be configured with or connected to a video matching system. The video matching system may be able to identify the media being displayed or played by the media display device at any given moment. As discussed above, the video matching system may sample the video and/or audio of the media being played by the device, generate identifiers or "clues" from the samples, and then match the clues against a database. By identifying the media being displayed or played on the media display device, the video matching system may be able to provide contextually relevant content, including applications, advertisements, and/or alternative media content.

When multiple content streams or channels available to a media display device play the same content (such as "breaking news"), the content may not be uniquely identifiable. For example, without additional information, it may not be clear which channel is being displayed by the media display device.

Figure 6 illustrates an example of multiple content streams simultaneously carrying the same media segment. Figure 6 further illustrates some example methods by which the video matching system can adapt to multiple channels carrying the same media segment. In the illustrated example, three channels are used as an example of multiple content streams. These three channels could be, for example, three broadcast television channels.

In this example, channel 2 601 plays two segments 602, 604 of a regularly scheduled program. Assuming the media display device is playing channel 2 601, during two time intervals t1 603 and t2 605, the media display device sends samples from segment 1 602 and segment 2 604 to the video matching system. At the end of time interval t1 603, the video matching system is able to identify segment 1 602, and at the end of time interval t2 605, the video matching system is able to identify segment 2 604.

During the third segment 606, channel 2 601 is interrupted by a public media segment, here a live pool feed segment 608. The live pool feed segment 608 in this example is a public video segment provided by, for example, a national broadcaster. The live pool feed segment 608 is available to each of its syndicated stations. An example of a live pool feed is "breaking news," that is, national news reports. Other examples of live pool feed segments include sporting events, syndicated programs, and commercials. During time interval t3 607, the media display device can send samples from the live pool feed segment 608 to the video matching system.

The video matching system can determine that the sample provided during time interval t3 607 is for a live pool feed segment 608. In various embodiments, the video matching system can make this determination based on finding matching clues for live pool feed segments associated with multiple channels. Upon determining that channel 2 601 is displaying live pool feed segment 608, in some embodiments, the video matching system can consider live pool segment 608 to be a continuation of the most recently detected program on channel 2 601. In these embodiments, the video matching system can make this determination based on the low probability of a viewer changing channels at the exact moment live pool feed segment 608 begins. In some embodiments, the video matching system can further determine that the unintended live pool feed segment 608 is unlikely to be related to any scheduled interactive or targeted content. Therefore, in these embodiments, the scheduled interactive or targeted content can be suppressed or disabled. Targeted content may not be related to the unscheduled live pool feed segment 608, and therefore, displaying, for example, an interactive overlay may not be beneficial to the viewer.

At the end of live pool feed segment 608, channel 2 601 may display segment 4 609. In some cases, segment 4 609 may be a scheduled program, meaning that live pool feed segment 608 has interrupted segment 3 606, or entered at the end of segment 3 606, and is currently playing, rather than having something scheduled after segment 3 606. For example, segment 4 609 may be a continuation of the program from segment 3 606, playing at the same time that the program would have played if live pool segment 608 had not played. As another example, segment 4 609 may be a new program scheduled to begin after segment 3 606. Segment 4 609 may begin at the beginning of the new program, or some portion of the beginning may have been omitted by the live pool feed.

In some cases, rather than ignoring the program that would have been displayed between segments 3 606 and 4 609, the program in segment 3 606 may be paused. Once the live pool feed segment 608 ends, the program in segment 3 606 may be resumed in segment 4 609, starting over at the point where the program in segment 3 stopped. Alternatively, the program in segment 3 606 may be restarted in segment 4 609. In some embodiments, at the end of the live pool feed segment 608, the viewer may be given the option of resuming the program in segment 3 606 or starting the program over again from the beginning.

Another example in Figure 6 is provided by channel 7 610. On channel 7 610, segments 1 611 and 2 612 are regularly scheduled. Thereafter, channel 7 610 is interrupted by a live pool segment 613. In this example, the media display device can tune into channel 7 610 shortly after live pool segment 613 begins, or while live pool segment 613 is being broadcast. During two time intervals t1 614 and t2 615, the media display device can send samples from live pool feed segment 613 to the video matching system. The video matching system can then determine that channel 7 610 is playing live pool feed segment 613. In various embodiments, the video matching system can make this determination based on, for example, finding matching clues for live pool feed segments 613 associated with multiple channels. In this example, the video matching system may not be able to determine which channel the media display device is currently playing. In some embodiments, the video matching system can avoid providing contextually relevant content while a live pool feed segment is being broadcast.

At the end of the live pool feed segment 613, channel 7 610 reverts to scheduling programming using segment 3 616. During time interval t3 617, the media display device can send samples from segment 3 616 to the video matching system, and at this time, the video matching system can be able to determine that the media display device is tuned to channel 7 610. In some embodiments, the video matching system can associate samples taken during time intervals t1 614 and t2 615 with channel 7 610. The video matching system can further provide the viewer with contextually relevant content related to channel 7 610.

Another example is shown in FIG6 by channel 9 618. In this example, channel 9 618 displays the regularly scheduled segments 1 619, 2 620, 3 622, 4 624, and 5 626. Assuming the media display device is tuned to channel 9 618, during time intervals t1 621, t2 623, and t3 625, the media display device sends samples from segments 620, 622, and 624 to the video matching system. In some embodiments, the video matching system may determine that channel 9 618 does not include a live pool feed segment. The video matching system can further provide contextually relevant content, such as replacing a previous commercial with one of particular interest to the viewer, where the replacement commercial can be based on information previously collected from the media display device.

In some cases, a channel may begin displaying a common pool feed after the common pool feed segment has already begun. FIG. 7 shows another example in which multiple media streams, shown here as television channels, simultaneously display the same media content. In this example, channel 2 (ch 2) 701 displays regularly scheduled segments 1 702, 2 704, and 3 706 before switching to a live pool feed segment 708. If a media display device is tuned to channel 2 701 at approximately the start of the live pool feed segment 708, the media display device may send samples to the video matching system during time intervals t1 703, t2 705, t3 707, and during t4 717 during the subsequent segment 4 709. As discussed above, the video matching system may determine that the media display device is tuned to channel 2 701 upon receiving samples from segment 4 709.

Channel 7 710 of this example displays regularly scheduled segments 1 711 and 2 712. Although live pool feed segment 713 begins at time 721, channel 7 710 delays switching to live pool feed segment 713. This delay may be due to, for example, segment 2 712 timing out, because the scheduler of channel 7 710 determined to allow segment 2 712 to end, and/or because segment 2 712 includes an introduction to live pool feed segment 713. Assuming that the media display device is tuned to channel 7 710 around time 721, the media display device can send samples to the video matching system during time intervals t1 714 and t2 715. The video matching system can determine that channel 7 710 is playing live pool feed segment 713, but may not be able to determine which channel the media display device is playing.

In another example scenario, the media display device may initially be tuned to channel 7 1310 and then switch to channel 2 701 at time 721. At time 721, channel 2 701 may already be playing live pool feed segment 708. Because live pool feed segment 708 is associated with multiple channels, the video matching system may not be able to determine which channel the media display device has changed to during the time interval t2 705 and t3 707. Once segment 4 709 is displayed, the video matching system may determine that the media display device is tuned to channel 2 701. After making this determination, the video matching system may associate the samples from t2 705 and t3 707 with channel 2 701.

Fig. 8 shows the example that multiple media content streams carry identical common media segment 810 almost simultaneously.In this example, two media content streams 804a, 804b are passed to two different media display devices 806a, 806b.In other examples, many different media content streams that carry the same media content separately can be delivered to many different media display devices simultaneously.In this example, two media display devices 806a, 806b can be, for example, in the same family, used by two different people 808a, 808b in the same family.For example, a family member 808a is watching TV program on the TV 806a in the living room, and another family member 808b is watching TV program on the laptop computer in the study.Alternatively, two media display devices 806a, 806b and the people 808a, 808b that use them can be irrelevant and be located at different locations.

At approximately the same time, two people 808a, 808b may tune their display devices 806a, 806b to the same media segment 810. For example, two people 808a, 808b may each decide to watch the same movie. As a result, both media display devices 806a, 806b may be displaying the exact same media segment 810 at a given moment. Alternatively, at a given moment, there may be a time difference of a few seconds or minutes between the content displayed by each device 806a, 806b. For example, during a movie, the television 806a may be several seconds ahead of the laptop 806b.

In this example, media content streams 804a, 804b are digital audio-video streams and/or audio streams transmitted over the Internet 850. For example, media content streams can include movies, television programs, music, text, and/or images provided by a website. Media content streams 804a, 804b can be provided by different content providers (provider A 802a and provider B 802b). Provider A 802a and B 802b can be, for example, Internet movies, music and/or television providers. Alternatively, in some cases, provider A 802a and provider B 802b can be identical content providers.

In the example of Fig. 8, media display device 806a, 806b can be connected to the computing device (not shown) that is configured with video matching system.When video matching system is playing, video matching system can attempt to use the clue that extracts from the media content being played to identify each media content being played in device 806a, 806b.Video matching system can be with these clues and database match, and from database, determine information, such as the identity of the creator, producer and/or publisher of the title of the media content being played, the identity of the people who are watching media content, and/or the identity of audience's equipment.For example, in this example, video matching system can be able to obtain the identity of provider A 802a by checking media content stream 804a.As another example, video matching system can be able to distinguish the smart phone that TV 806a has with same person 808a.In addition, video matching system can be able to determine that TV 806a and smart phone of someone 808a are located in different places. The video matching system may further use this information to provide contextually relevant content, such as interactive information and/or advertisements, to the media display device, which may display the contextually relevant content to the viewer.

As discussed above, when two example media content streams 804a, 804b display the same media segment 810 at approximately the same time, the video matching system may be unable to determine some information. For example, although the video matching system is able to identify that the television 806a and the laptop computer 806b are playing the common media segment 810, this information alone may not be sufficient for the video matching system to determine context-dependent content specifically for each device. For example, if the video matching system is provided with information such as the characteristics or identities of the persons 808a, 808b viewing the two devices, the video matching system may be able to customize context-dependent content for the first person 808a while providing different context-dependent content for the second person 808b.

To determine context-relevant content, the video matching system can use the methods discussed above with respect to Figures 6 and 7. In various embodiments, the video matching system can determine identification information of other media content included in the media content streams 804a and 804b of Figure 8. For example, in one scenario, person 808a watching television 806a may have watched sports news before tuning into the common media segment 810. The video matching system can use the identification information for this previous media content to identify media content stream 804a. For example, the video matching system can be able to identify media content stream 804a as being associated with television 806a and/or person 808a watching television 806a. The video matching system can further be able to provide context-relevant content to television 806a. For example, the video matching system can provide news about person 808a's favorite team and/or advertisements for sporting events or sports equipment.

As another example, person 808b viewing laptop computer 806b may not have used laptop computer 806b to view media content prior to tuning into common media segment 810. Instead, person 808b may view other media content during or after common media segment 810. For example, during a commercial break in common media segment 810, person 808b may use laptop computer 806b to purchase school supplies. The video matching system may use this other media content displayed during or after common media segment 810 to identify media content stream 804b. For example, the video matching system may identify the media content stream as being associated with laptop computer 806b and/or person 808b using laptop computer 806b. The video matching system may further provide contextually relevant content to laptop computer 806b. For example, the video matching system may provide advertisements related to school supplies, suggestions on where to shop, and/or suggestions on where to find merchants.

In various embodiments, when a media content stream is playing a common media segment, the video matching system can use other methods to identify the media content stream. In some cases, the provider of the media content stream can provide a graphic element superimposed on the common media segment. Figure 9 shows an example of a graphic 902 that has been superimposed on the common media segment being played by the media display device 900. In various embodiments, the content provider can use the graphic 902 to identify the content provider, particularly when multiple content providers are playing common media segments. For example, multiple local television channels may play the same national news segment at the same time. Local broadcasters can add graphics 902 to the news segment to identify themselves. The graphic 902 can be, for example, a logo, program information, or other information.

Fig. 9 shows an example of the size and position of some content providers' usable graphics. In other examples, graphics 902 can be the shape of a banner or scroll bar at the bottom or top across the screen, in the hurdle on the left or right side of the screen, or can appear to be superimposed on the center of the screen.

In various embodiments, a method for detecting graphic overlays can examine a video display and locate video image edges. Video image edges can be detected by searching for high contrast differences between portions of a screen of a media display device. The method can further include monitoring whether the detected edge remains stationary. When the detected edge remains in a particular position for longer than a short duration, the video matching system can determine that it has found the graphic on the screen. For example, the video matching system can search for high contrast differences in the bottom area of the screen, which can indicate the presence of an on-screen banner.

In various embodiments, the above-mentioned video matching system may include a method for detecting graphic overlays. For example, as discussed above, pixel blocks can be defined for the screen of a media display device. A "pixel block" can be defined as a pixel block sampled from the screen of a media display device. A pixel block can contain a certain number of pixels, each pixel can have, for example, an RGB color value (or a color value represented by YUV or some other format). For the purpose of graphic overlay detection, a pixel block can be, for example, 32 pixels wide by 32 pixels high or a multiple of 32 pixels, such as 64 pixels wide by 64 pixels high. These example sizes can utilize discrete cosine transform (DCT). The video matching system can perform a discrete cosine transform function. By examining the coefficients in the lower right quadrant of the discrete cosine transform of each pixel block, the edge of the graphic overlay can be detected.

In various embodiments, the detection process may further include detecting whether the high-frequency information from the discrete cosine transform has not changed within a predetermined time period. When the high-frequency information has not changed, a graphic overlay may appear. In these embodiments, some on-screen graphics, such as a scrolling banner, may be identified.

In various embodiments, other on-screen pattern detection methods may use algorithms such as Sobel and Sharr, or algorithms from the perceptual hashing family of image analysis. As with discrete cosine transforms, these algorithms can also be used to detect edges and corners of graphic elements within a video signal. In some cases, a pixel block with an odd number of pixels (e.g., 3 pixels x 3 pixels) may be used for a convolutionally coded progressive scan over the video region of interest to search for edges.

In various embodiments, detecting on-screen graphics can begin by reducing pixel information from a pixel block of 8-bit red-green-blue (RGB) values and 8-bit monochrome values. Next, a Gaussian blur can be applied to reduce noise in the video information. Next, the pixel matrix (i.e., the resulting pixel block) can be transferred to the video region of interest. This matrix can then be used to calculate the first-order differential of the pixel value with respect to the vertical or horizontal axis of the video screen. The calculated differential is retained in the corresponding pixel location. This differential can be checked for a maximum value that indicates an edge.

In various embodiments, another method for detecting graphic overlays is to train a video matching system using various graphics that can be used for graphic overlays. An image matching algorithm can then be used to match the trained or learned graphics with pixels on the screen. For example, the video matching system can use a perceptual hashing (pHash) method to perform matching. Examples of other frame comparison methods include scale-invariant feature transforms (SIFT) and speeded-up robust features (SURF). In an embodiment using pHash, the entire video frame can be processed quickly. The resulting hash value can be compared with a reference video image. These reference video images can also be processed using pHash and can be provided from a central server. One of the advantages of using pHash is that it can reliably match coarse features that have a relatively high insensitivity to contrast, brightness, or color changes (such as large rectangles or other shapes that can be used by graphic overlays). Another advantage of pHash is that it can also match detailed single video frames.

In various embodiments, the video matching system can further maintain a library of different possible graph overlay comparison candidates. Furthermore, the video matching system can utilize this library without increasing the total number of image searches performed per unit time. Specifically, in some embodiments, the video matching system can track successful detections. Graph overlay comparison candidates that are successfully and frequently matched are more likely to match in the future, while candidates that are infrequently matched or unsuccessfully matched are less likely to match in the future.

In various implementations, graphical overlay detection may be interleaved with the process for automatic content recognition.

10 illustrates an example of a process 1000 that may be implemented when multiple media content streams include the same unscheduled media segments. The process 1000 may be implemented by a computing device that has been configured with a video matching system such as described above.

At step 1002, a computing device may receive multiple media content streams. The computing device may be configured to identify media content being played by a specific media display device (e.g., a television, tablet computer, laptop computer, etc.) at a specific time. At least two of the multiple media content streams may simultaneously include the same unscheduled segment. For example, two media content streams may both include a "breaking news" segment, i.e., a national broadcast of a major event. As another example, the media content streams may both include the same streaming movie, where the movie is requested by different people using different media display devices. In this example, the media segment is "unscheduled" because there may be no program schedule associated with the media display device.

At step 1004, the computing device may determine that a particular media display device is currently playing an unscheduled media segment in a media content stream. The computing device may make this determination by examining the media content available at the current time in each of a plurality of media content streams. For example, the plurality of media content streams may include two or more local television channels, and two or more of the local television channels may each receive a breaking news feed.

At step 1006, the computing device may determine identification information from the media content contained in the media content stream being played by the specific media display device at the current time. For example, the computing device may use identification information provided by media content played by the specific media display device before the unscheduled media segment. Alternatively or additionally, the computing device may use identification information provided by media content played after the unscheduled media segment. The identification information may identify the media content stream. For example, the identification information may identify a channel, a service provider, a specific media display device, and/or a person using the specific media display device.

At step 1008, the computing device may determine contextually relevant content. The contextually relevant content may include, for example, interactive information, advertisements, and/or suggestions for additional content. The contextually relevant content may be disabled when an unscheduled media segment is being played by a particular media display device.

At step 1010, the computing device may display the media content stream and context-related content after the unscheduled media segment has been played. For example, the computing device may overlay the context-related information on the media content immediately following the unscheduled media segment. Alternatively or additionally, the computing device may insert the context-related information after the unscheduled media segment and before playing the additional media content.

Various methods related to matching clues from unknown media content to candidates in a reference database will now be discussed in more detail. These methods include the nearest neighbor search process discussed above with respect to FIG.

As discussed above, the video matching system can be configured to identify a media content stream when the media content stream includes unscheduled media segments. As further discussed above, identifying a media content stream can include identifying the media content played by a media display device before or after the unscheduled media segments. The process for identifying media content is discussed above with respect to FIG1 . Specifically, the video content system can use samples (e.g., graphics and/or audio samples) obtained from the display mechanism of the media content device and generate clues from these samples. The video matching system can then match the clues with a reference database, wherein the database contains clues of known media content.

The video matching system may further include various methods for improving the efficiency of finding matches in the database. The database may contain a large number of clues, and therefore the video matching system may include an algorithm for finding potential matches or "candidates" to be matched. The video matching system may further include an algorithm for determining which candidate clues actually match the clues generated from the display mechanism of the media content device. Locating candidate clues may be more efficient than other methods for matching clue values with values in the database (such as matching the clue with each entry in the database).

Nearest neighbor and path tracing are examples of techniques that can be used to match unknown clues to candidate clues in a reference database. Path tracing is a mathematical method for identifying a series of related points from many possible points. Nearest neighbor is a method that can identify candidate points for performing path tracing. Below is an example of using nearest neighbor and path tracing to track video transmissions using ambiguous clues, but the general concepts can be applied to any field where candidate matches are selected from a reference database.

A method for efficient video tracking is presented. Video tracking is the application of path tracing techniques to the problem of locating matching candidates for a given unknown video cue in a video reference database. Given a large number of video segments, the system must be able to identify in real time which segment a given query video input is taken from and at what time offset. The segment and offset together are called a position. The method is called video tracking because it must be able to efficiently detect and adapt to pauses, fast forwards, rewinds, sudden switches to other segments, and switches to unknown segments. Before being able to track live video, the database is processed. Visual cues (a few pixel values) are taken from the frame every fraction of a second and placed into a specialized data structure (note that this can also be done in real time). Video tracking is performed by continuously receiving cues from the input video and updating a set of beliefs or estimates about its current position. Each cue either agrees or disagrees with the estimate, and they are adjusted to reflect the new evidence. If the confidence that this is true is high enough, the video position is assumed to be the correct one. This can be done efficiently by tracking only a small number of possible "suspect" positions.

The method used for video tracking is described, but mathematical structures are used to explain and investigate it. The purpose of introducing the mathematical structures is to provide the reader with the necessary tools to transition between the two fields. A video signal consists of a series of frames. Each frame can be thought of as a still image. Each frame is a raster of pixels. Each pixel is composed of three intensity values corresponding to the red, green, and blue (RGB) colors that make up the color of that pixel. In the terminology used in this article, a clue is a list of RGB values for a subset of the pixels in a frame, along with the corresponding timestamps. The number of pixels in a clue is significantly smaller than the number of pixels in a frame, typically between 5 and 15. As an ordered list of scalar values, the clue values are actually vectors. This vector is also called a point.

Although these points are in high dimensions, typically between 15 and 150, they can be imagined as points in two dimensions. In fact, the illustrations will be presented as two-dimensional plots. Now, consider the progression of the video and its corresponding clue points. Typically, small changes in time will result in small changes in pixel values. The pixels can be thought of as "moving" slightly between frames. Following these tiny shifts from frame to frame, the clue follows a path in space, like beads strung along a curved line.

In the context of this analogy, in video tracking, the position of a bead in space (a clue point) is received, and the part of the line that the bead follows (the path) is found. This is significantly more difficult for two reasons. First, the bead does not follow the line exactly, but rather maintains a varying, unknown distance from it. Second, the lines are all tangled together. These statements are made more precise in Section 2. The algorithm described below accomplishes this task in two conceptual steps. When a clue is received, the algorithm finds all points on all known paths that are close enough to the clue point; these points are called suspects. This is done efficiently using the probabilistic point positions in the equisphere algorithm. These suspects are added to a history data structure, and the probability of each of them indicating the true position is calculated. This step also includes removing unlikely suspect positions. This history update process ensures that only a small piece of history is retained and that possible positions are never deleted. The general algorithm is given in Algorithm 1 and illustrated in Figure 11.

The next section begins by describing the Probability Point Location in Equal Sphere (PPLEB) algorithm from Section 1. The PPLEB algorithm is used to efficiently execute line 5 of Algorithm 1 above. The ability to quickly perform this search for suspects is crucial for the application of this method. In Section 2, a possible statistical model for executing lines 6 and 7 was described. The described model is a natural choice for this setting. It also shows how it can be used very efficiently.

Section 1 - Probability Point Positions in Equal Spheres

The following section describes a simple algorithm for performing Probabilistic Point Location in Equisphere (PPLEB). In traditional PLEB (Point Location in Equisphere), the algorithm begins with a set of n points x in a particular sphere of lR d and radius r. The algorithm is given O(multi(n)) preprocessing time to generate an efficient data structure. Then, given a query point x, the algorithm needs to return all points x such that ||xx _i || ≤ r. The set of points such that ||xx _i || ≤ r is geometrically located within the sphere of radius r surrounding the query x (see Figure 12). This relationship is referred to as x, is near x, or is x, and x is a neighbor.

The PPLEB problem and the nearest neighbor search problem are two similar problems that have received a lot of attention in academia. In fact, these problems are some of the earliest problems studied in the field of computational geometry. Many different methods cater to situations where the environment dimension is small or constant. These divide the space in different ways and recursively search each part. These methods include KD trees, cover trees, and others. Although very effective in low dimensions, they tend to perform poorly when the environment dimension is high. This is known as the "curse of dimensionality". Various methods have tried to solve this problem while overcoming the curse of dimensionality. The algorithm used in this article uses a simpler and faster version of the algorithm and can rely on Local Sensitive Hashing.

Section 1.1 Locality Sensitive Hashing

In the locality-sensitive hashing scheme, a hash function family H is designed such that:

In other words, if x and y are close to each other, the probability that x and y are mapped to the same value h is significantly higher.

For clarity, let us first discuss the simplified case where all incoming vectors have the same length r' and . The reason for the latter condition will become clear later. First define a random function u∈U that splits between x and y according to the angle between them. Let be a random vector uniformly chosen from the unit sphere S ^d-1 and let (see Figure 13). It is easy to verify that Pr _uU (u(x)) ≠ u(y)) = 0 _x,y /π. Furthermore, for any point x,y,x',y' on the circle such that

The family of functions H is defined as the cross product of t independent copies of u, i.e., h(x) = [u1(x),…, _ut (x)]. Intuitively, one would expect that if h(x) = h(y), then x and y are likely close to each other. Let's quantify this. First, calculate the expected number of false positive errors, _nfp . These are cases where h(x) = h(y) but ||xy|| > 2r. Find a value t for which _nfp does not exceed 1, meaning that one is not expected to be wrong.

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

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

Assuming h(x) and h(y) are neighbors, now calculate the probability that h(x) = h(y):

Note that we must have 2p < 1, which requires a probability of success that may not sound very high. In fact, it is significantly less than 1/2. The next section shows how to raise this probability to 1/2.

1.2 Node Search Algorithm

The function h maps each point in space to a bucket. The bucket function for a point x is defined with respect to the hash function h as B _h (x) ≡ { _xi |h( _xi ) = h(x)}. The data structure maintained is an instance of the bucket function [ _Bh1 ,…, _Bhm ]. When searching for a point x, the function returns:

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

In other words, although every neighbor of x is found with probability at least 1/2, it is impossible to find many non-neighbors.

Section 1.3 Handling Different Radius Input Vectors

The previous section dealt only with searching vectors of the same length, namely r'. We now describe how to use this construction as a building block to support searches of different radii. As can be seen in Figure 14, the space is divided into a number of rings with exponentially increasing widths. A ring i, denoted by _Ri , consists of all points x _i such that _‖xi‖∈ [2r(1+∈) ⁱ , 2r(1+∈) ⁱ⁺¹ ]. This achieves two goals. First, if x _i and x _j belong to the same ring, then ||x _j ||/(1+∈) _{≤‖xi‖≤} ||x _j ||(1+∈). Second, any search can be performed in at most 1/∈ such rings. Furthermore, if the maximum length vector in the data set is r', then the total number of rings in the system is O(log(r'/r)).

Section 2 Path Tracing Problem

In the path tracing problem, a fixed path in space is given along with the positions of particles in a sequence of time points. The terms "particle," "clue," and "point" will be used interchangeably. The algorithm needs to output the position of the particle along the path. This is made more difficult by several factors: the particle only approximately follows the path; the path can be discontinuous and intersect itself multiple times; and both the particle and path positions are given as a sequence of time points (different at each time point).

It is important to note that this problem can be simulated by tracking particles along any number of paths. This can be done simply by concatenating the paths into one long path and interpreting the resulting position as a position on a single path.

More precisely, let the path P be a parametric curve. The parameters of the curve will be called time. A point on the path is given at any time t _i , giving n pairs (t _i , P(t _i )). The particle follows the path, but its position is given at different times, as shown in Figure 15. Furthermore, m pairs (t' _j , x(t' _j )) are given, where x(t' _j ) is the position of the particle at time t' _j .

Section 2.1 Likelihood Estimation

Because particles do not follow a path exactly, and because a path can intersect itself multiple times, it is often impossible to unambiguously identify the actual position of a particle on the path. Therefore, a probability distribution is calculated over all possible path positions. If the position probability is significantly likely, the particle position is assumed to be known. The next section describes how to do this efficiently.

If the particle follows the path, the time difference between the particle's timestamp and the offset of the corresponding point on P should be relatively fixed. In other words, if x(t') is currently at offset t on the path, then it should be close to P(t). In addition, τ seconds ago, it should have been at offset t-τ. Therefore, x(t'-τ) should be close to P(t-τ) (note that if the particle intersects the path and x(t') is temporarily close to P(t), then x(t'-τ) and P(t-τ) are unlikely to be close as well). Define the relative offset as Δ = t-t'. Note that as long as the particle follows the path, the relative offset Δ remains unchanged. That is, x(t') is close to P(t'+Δ).

The maximum likelihood relative shift is obtained by calculation:

In other words, the most likely relative shift is the one for which the particle's history is most likely. However, this equation cannot be solved without a statistical model. The model must quantify: how closely x follows the path; how likely x is to jump between locations; and how smoothly the path and particle curves are between measurement points.

Section 2.2 Time Discount Position Building

We now describe the statistical model used to estimate the likelihood function. This model assumes that the deviations of a particle from its path are normally distributed with standard deviation ar. It also assumes that at any given point in time, there is a certain nonzero probability that the particle will suddenly switch to another path. This is reflected in an exponential discount over past points. In addition to being a reasonable choice of modeling perspective, this model has the advantage of being highly updateable. For some constant time unit 1, the likelihood function is set to be proportional to f and is defined as follows:

Here α<<1 is the scaling factor and ξ>0 is the probability that the particle will jump to a random position on the path in a given time unit.

Efficiently updating the function f can be achieved using the following simple observation.

Furthermore, since α<<1, if ||x(t′ _m )-P(t _i )||≥r, then the following occurs:

This is an important property of the likelihood function, since the sum update can now be performed only on the neighbors of x(t' _j ) instead of on the entire path. Let S be the set of (t _i , P(t _i )) such that ||x(t′ _m )-P(t _i )||≤r. The following equation occurs:

This is described in Algorithm 2.2 below. The term f is treated as a sparse vector that also accepts negative integer indices. The set S is the set of all neighbors of x(t _i ) on the path and can be quickly computed using the PPLEB algorithm. It is easy to verify that if the number of neighbors of x(t _i ) is bounded by some constant n _near , then the number of nonzeros in the vector f is bounded by n _near /ξ, which is just a factor of the larger constant. The final stage of the algorithm is to output a specific value δ if some threshold is exceeded.

Figure 11 shows three consecutive point locations and the path points surrounding them. Notice that neither the lowest point nor the middle point alone is sufficient to identify the correct portion of the path. However, together they can be identified. Adding the vertex increases the certainty that the particle is indeed the final (left) curve of the path.

In Figure 12, given a set of n (grey) points, the algorithm is given a query point (black) and returns the set of points within a distance r from the query point (the points inside the circle). In the traditional setting, the algorithm must return all of these points. In the probabilistic setting, each such point should be returned with some constant probability.

Figure 13 shows the values of u( _x1 ), u( _x2 ), and u(x). Intuitively, function u assigns different values to _x1 and _x2 if the dashed line passes between them, and the same value otherwise. The dashed line passing in a random direction ensures that the probability of this happening is proportional to the angle between _x1 and _x2 .

Figure 15 shows that by dividing the space into multiple rings such that the ring R _i is between radius 2r(1+∈) ⁱ and 2r(1+∈) ⁱ⁺¹ , it is ensured that the lengths of any two vectors within the ring are the same up to a multiple of (1+∈) factors, and any search is performed in at most 1/∈ rings.

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

Figure 16 shows three consecutive point locations and the path points around them. Note that neither x(t ₁ ) nor x(t ₂ ) alone is sufficient to identify the correct portion of the path. However, together they do. Adding x(t ₃ ) increases the certainty that the particle is indeed the final (left) curve of the path.

In the foregoing description, for purposes of explanation, specific details have been set forth to provide a thorough understanding of the various examples. However, it will be apparent that the various examples can be practiced without these specific details. For example, circuits, systems, networks, processes, and other components may be represented as components in block diagram form to avoid obscuring the examples with unnecessary detail. In other cases, well-known circuits, processes, algorithms, structures, and techniques may be shown without unnecessary detail to avoid obscuring the examples. The drawings and descriptions are not intended to be limiting.

The foregoing description provides only exemplary illustrations and is not intended to limit the scope, applicability, or configuration of the present disclosure. Rather, the foregoing description of examples will provide those skilled in the art with a description of possibilities for implementing various examples. It should be understood that various changes may be made to the function and arrangement of the various elements without departing from the spirit and scope of the present invention as set forth in the appended claims.

In addition, it should be noted that various examples may be described as processes, which are depicted as flow charts, flowcharts, data flow diagrams, structure diagrams, or block diagrams. Although a flow chart may describe operations as a sequential process, many operations may be performed in parallel or simultaneously. In addition, the order of the operations may be rearranged. A process is terminated when the operations are completed, but may have additional steps not included in the figures. A process may correspond to a method, function, procedure, subroutine, subprogram, etc. When a process corresponds to a function, its termination may correspond to a return of the function to the calling function or the main function.

The term "machine-readable storage medium" or "computer-readable storage medium" includes, but is not limited to, portable or non-portable storage devices, optical storage devices, and various other media capable of storing, containing, or carrying instructions and/or data. A machine-readable storage medium or computer-readable storage medium may include a non-transient medium in which data can be stored and does not include a carrier wave and/or a transient electronic signal transmitted wirelessly or via a wired connection. Examples of non-transient media may include, but are not limited to, a disk or tape, an optical storage medium such as a compact disc (CD) or a digital versatile disc (DVD), flash memory, a memory, or a storage device. A computer program product may include code and/or machine-executable instructions representing any combination of a procedure, function, subroutine, program, routine, subroutine, module, software package, class, or instruction, data structure, or program statement. A code segment may be coupled to another code segment or hardware circuit by passing and/or receiving information, data, independent variables, parameters, or memory contents. Information, independent variables, parameters, data, or other information may be passed, forwarded, or sent using any suitable means including memory sharing, message passing, token passing, network transmission, or other transmission technology.

Furthermore, examples may be implemented by hardware, software, firmware, middleware, microcode, hardware description languages, or any combination thereof. When implemented in software, firmware, middleware, or microcode, program code or code segments (e.g., a computer program product) that perform the necessary tasks may be stored in a machine-readable medium. A processor may perform the necessary tasks.

The systems depicted in some figures can be provided in various configurations. In some examples, the system can be configured as a distributed system, where one or more components of the system are distributed across one or more networks in a cloud computing system.

As described in further detail above, certain aspects and features of the present disclosure relate to identifying unknown data points by comparing the unknown data point with one or more reference data points. The systems and methods described herein improve the efficiency of storing and searching large data sets for identifying unknown data points. For example, the systems and methods allow identification of unknown data points while reducing the density of the large data sets required for performing the identification. The technology can be applied to any system that harvests and manipulates large amounts of data. Illustrative examples of these systems include content-based automatic search systems (e.g., automatic content recognition for video-related applications or other suitable applications), Map Reduce systems, Big table systems, pattern recognition systems, facial recognition systems, classification systems, computer vision systems, data compression systems, cluster analysis, or any other suitable systems. Those of ordinary skill in the art will recognize that the technology described herein can be applied to any other system that stores data for comparison with unknown data. For example, in the case of automatic content recognition (ACR), the system and method reduce the amount of data that must be stored in order to match the system search and find the relationship between the unknown data group and the known data group.

By way of example only and not limitation, for purposes of illustration, some of the examples described herein use automatic audio and/or video content recognition systems. However, one of ordinary skill in the art will recognize that other systems may use the same technology.

Substantial variations can be made depending on specific requirements. For example, customized hardware can be used, and/or specific elements can be implemented using hardware, software (including portable software, such as applets, etc.), or both. In addition, connections to other access devices or computing devices, such as network input/output devices, can be utilized.

In the foregoing description, various aspects of various embodiments have been described with reference to their specific examples, but those skilled in the art will recognize that the present embodiment is not limited thereto. The various features and aspects of the above-described embodiments may be used individually or in combination. In addition, without departing from the broader spirit and scope of this specification, examples may be used in any number of environments and applications other than those described herein. Therefore, the description and drawings are to be considered illustrative rather than restrictive.

In the foregoing description, for the purpose of illustration, method is described in a specific order. It should be understood that, in an alternative example, these methods can be performed in an order different from the described order. It should also be understood that the above method can be performed by hardware components, or can be implemented in the order of machine executable instructions, which can be used to make a machine (such as a general or special processor or a logic circuit programmed with these instructions) perform the method. These machine executable instructions can be stored on one or more machine-readable media, such as CD-ROM or other types of optical disks, floppy disks, ROM, RAM, EPROM, EEPROM, magnetic cards or optical cards, flash memories or other types of machine-readable media suitable for storing electronic instructions. Alternatively, the method can be performed by a combination of hardware and software.

Where a component is described as being configured to perform certain operations, such configuration may be achieved, for example, by designed electronic circuits or other hardware that perform the operations, by programmed programmable electronic circuits (e.g., a microprocessor or other suitable electronic device circuitry) that perform the operations, or any combination thereof.

While illustrative examples of the present application have been described in detail herein, it should be understood that the inventive concept may be otherwise variously embodied and employed, and that the appended claims are intended to be interpreted to include such variations, except as limited by the prior art.

Claims (20)

1. A method for identifying media content streams, comprising: Receive multiple media content streams at a computing device, wherein the multiple media content streams include media content according to a schedule, and wherein the computing device is configured to identify media content included in the media content streams; Determine the identification information of the displayed media content stream among the plurality of media content streams, wherein the identification information identifies the displayed media content stream; Determine content related to the background corresponding to the displayed media content stream, wherein the determination is based on the identification information; The background-related content is displayed simultaneously with the displayed media content stream; Generate one or more clues from the displayed media content stream; Generate one or more clues from one or more other media content streams among the plurality of media content streams; Determining that one or more clues from the displayed media content stream match one or more clues from one or more other media content streams, wherein determining that one or more clues from the displayed media content stream match one or more clues from one or more other media content streams indicates that an unscheduled media segment is included in the displayed media content stream among the plurality of media content streams; When the unscheduled media segment is being displayed, remove the background-related content that is simultaneously displayed with the displayed media content stream from the display; and After the unscheduled media segment has been displayed, the background-related content is displayed simultaneously with the displayed media content stream. 2. The method of claim 1, wherein the background-related content is provided to the media display device. 3. The method of claim 1, wherein determining the identification information includes detecting a graphic superimposed on the unscheduled media segment while the unscheduled media segment is being displayed, wherein the graphic provides additional identification information for the displayed media content stream. 4. The method of claim 1, wherein the media content used to determine the identification information includes media content included in the displayed media content stream before or after the unscheduled media segment. 5. The method of claim 1, further comprising: It is determined that the unscheduled media segment has been continuously displayed since the beginning of the unscheduled media segment; and The displayed media content stream is identified using identification information determined for media content included in the displayed media content stream prior to the unscheduled media segment. 6. The method of claim 1, further comprising: Determine that the unscheduled media segment has been continuously displayed since the point in time following the start of the unscheduled media segment; and The displayed media content stream is identified using identification information of the media content included in the displayed media content stream after the unscheduled media segment. 7. The method of claim 1, wherein the unscheduled media segment is not included in the scheduling. 8. A computing device, comprising: One or more processors; and A non-transitory computer-readable medium including instructions that, when executed by the one or more processors, cause the one or more processors to perform operations, the operations including: Receive multiple media content streams, wherein the multiple media content streams include media content according to a schedule; Determine the identification information of the displayed media content stream among the plurality of media content streams, wherein the identification information identifies the displayed media content stream; Determine content related to the background corresponding to the displayed media content stream, wherein the determination is based on the identification information; The background-related content is displayed simultaneously with the displayed media content stream; Generate one or more clues from the displayed media content stream; Generate one or more clues from one or more other media content streams among the plurality of media content streams; Determining that one or more clues from the displayed media content stream match one or more clues from one or more other media content streams, wherein determining that one or more clues from the displayed media content stream match one or more clues from one or more other media content streams indicates that an unscheduled media segment is included in the displayed media content stream among the plurality of media content streams; When the unscheduled media segment is being displayed, remove the background-related content that is simultaneously displayed with the displayed media content stream from the display; and After the unscheduled media segment has been displayed, the background-related content is displayed simultaneously with the displayed media content stream. 9. The computing device of claim 8, wherein the instructions for determining the identification information include instructions that, when executed by the one or more processors, cause the one or more processors to perform an operation, the operation including: While the unscheduled media segment is being displayed, a graphic overlaid on the unscheduled media segment is detected, wherein the graphic provides additional identification information for the displayed media content stream. 10. The computing device of claim 8, wherein the media content used to determine the identification information includes media content included in the displayed media content stream before or after the unscheduled media segment. 11. The computing device of claim 8, further comprising instructions that, when executed by the one or more processors, cause the one or more processors to perform an operation, the operation comprising: It is determined that the unscheduled media segment has been displayed since the beginning of the unscheduled media segment; and The displayed media content stream is identified using identification information determined for media content included in the displayed media content stream prior to the unscheduled media segment. 12. The computing device of claim 8, further comprising instructions that, when executed by the one or more processors, cause the one or more processors to perform an operation, the operation comprising: Determine that the unscheduled media segment has been continuously displayed since the point in time following the start of the unscheduled media segment; and The displayed media content stream is identified using identification information of the media content included in the displayed media content stream after the unscheduled media segment. 13. The computing device of claim 8, wherein identifying that the displayed media content is being displayed includes: Obtain a sample of the displayed media content; Generate clues from the sample; and The clues are matched with a clue database, which includes identification information. 14. The computing device of claim 8, wherein identifying that the displayed media content is being displayed includes: Data is used from the displayed media content, wherein the data is obtained from video or audio data included in the displayed media content. 15. A computer-readable storage medium comprising instructions which, when executed by one or more processors, cause the one or more processors to perform the following operations: Receive multiple media content streams, wherein the multiple media content streams include media content according to a schedule; Determine the identification information of the displayed media content stream among the plurality of media content streams, wherein the identification information identifies the displayed media content stream; Determine content related to the background corresponding to the displayed media content stream, wherein the determination is based on the identification information; The background-related content is displayed simultaneously with the displayed media content stream; Generate one or more clues from the displayed media content stream; Generate one or more clues from one or more other media content streams among the plurality of media content streams; Determining that one or more clues from the displayed media content stream match one or more clues from one or more other media content streams, wherein determining that one or more clues from the displayed media content stream match one or more clues from one or more other media content streams indicates that an unscheduled media segment is included in the displayed media content stream among the plurality of media content streams; When the unscheduled media segment is being displayed, remove the background-related content that is simultaneously displayed with the displayed media content stream from the display; and After the unscheduled media segment has been displayed, the background-related content is displayed simultaneously with the displayed media content stream. 16. The computer-readable storage medium of claim 15, wherein the background-related content is provided to the media display device. 17. The computer-readable storage medium of claim 15, wherein the instructions for determining the identification information include instructions that, when executed by the one or more processors, cause the one or more processors to perform the following operations: While the unscheduled media segment is being displayed, a graphic overlaid on the unscheduled media segment is detected, wherein the graphic provides additional identification information for the displayed media content stream. 18. The computer-readable storage medium of claim 15, wherein the media content used to determine the identification information includes media content included in the displayed media content stream before or after the unscheduled media segment. 19. The computer-readable storage medium of claim 15, further comprising instructions that, when executed by the one or more processors, cause the one or more processors to: It is determined that the unscheduled media segment has been displayed since the beginning of the unscheduled media segment; and The displayed media content stream is identified using identification information determined for media content included in the displayed media content stream prior to the unscheduled media segment. 20. The computer-readable storage medium of claim 15, further comprising instructions that, when executed by the one or more processors, cause the one or more processors to perform the following operations: It is determined that the unscheduled media segment has been displayed since the point in time that the unscheduled media segment began; and The displayed media content stream is identified using identification information of the media content included in the displayed media content stream after the unscheduled media segment.