HK1255273B - Optimizing media fingerprint retention to improve system resource utilization - Google Patents

Description

Optimize media fingerprint retention to improve system resource utilization

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of U.S. Provisional Application No. 62/193,342, filed July 16, 2015, which is hereby incorporated by reference in its entirety. This application also incorporates by reference in its entirety U.S. Patent Application No. 14/089,003, filed November 25, 2013, 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. Application No. 12/788,748, filed May 27, 2015, and U.S. Application No. 12/788,721, filed May 27, 2015.

Technical Field

The present disclosure relates to improving the management of system resources used to identify content displayed by a media system (e.g., a television system, a computer system, or other electronic device capable of connecting to the Internet). In some examples, various techniques and systems are provided for removing portions of data sent to a matching server in order to reduce the amount of data sent to the matching server and the amount of data stored by the matching server or a database associated with the matching server.

Background Art

Managing dense datasets presents significant challenges. For example, there are difficulties in storing, indexing, and managing large amounts of data. This difficulty can arise in systems that use reference data stored in a dataset to search for and identify the closest matches between data.

Summary of the Invention

Devices, computer program products, and methods for removing redundant data associated with a frame are provided. The removal can be performed by a media system or a matching server. In some embodiments, a device, computer program product, and method for removing redundant data are provided. For example, a method may include receiving an initial frame. In some examples, the initial frame includes pixel data. The method may further include determining initial clue data for the initial frame. In some examples, the initial clue data includes a plurality of initial pixel data samples associated with the initial frame.

The method may further include sending initial clue data. In some examples, the initial clue data is addressed to a server. The method may further include receiving a new frame. In some examples, the new frame includes pixel data. The method may further include determining new clue data for the new frame. In some examples, the new clue data includes a plurality of new pixel data samples associated with the new frame. The method may further include identifying a pixel value range. In some examples, the pixel data samples are determined to be similar when a pixel value difference between the pixel data samples is within the pixel value range.

The method may further include determining a pixel value difference between the initial pixel data sample and the new pixel data sample. In some examples, the initial pixel data sample corresponds to the new pixel data sample. The method may further include determining that the pixel value difference is within a pixel value range. The method may further include, when the pixel value difference is within the pixel value range, updating the new clue data by removing the new pixel data sample from the new clue data. The method may further include sending the updated new clue data. In some examples, the updated new clue data is addressed to a server.

In some embodiments, the method may further include sending a flag indicating removal of the new pixel data sample from the new clue data. In some examples, the flag is addressed to a server.

In some embodiments, the method may further include sending a flag indicating removal of a row of pixel data samples from the new clue data. In such embodiments, the new pixel data samples are included in the row. In some examples, the flag is addressed to the server.

In some embodiments, the pixel data sample is calculated from the pixel block. In some examples, the flag is addressed to the server. In such embodiments, the pixel block comprises an array of pixels of a frame. In some embodiments, the pixel data sample is calculated by taking the average of the pixel values of the pixels in the pixel block.

In some embodiments, an apparatus, computer program product, and method for matching data to one or more removed portions are provided. For example, the method may include storing a plurality of reference data sets in a reference database. In some examples, the reference data sets are associated with media segments. The method may further include receiving, by a server, clue data for a frame. In some examples, the clue data includes a plurality of pixel data samples from a frame. In some examples, the frame is associated with an unrecognized media segment.

The method may further include identifying a pixel data sample that is absent from the clue data for the frame. The method may further include matching the clue data for the frame to a reference dataset. In some examples, the matching includes using a previous pixel data sample from previous clue data. In some examples, the previous clue data is from a previous frame. In some examples, the previous pixel data sample corresponds to a pixel data sample that is absent from the frame. In some examples, the reference dataset is associated with a media segment. The method may further include determining that the unidentified media segment is the media segment.

In some embodiments, the method may further include receiving a flag indicating that the pixel data sample is not present in the clue data. In such embodiments, the absence of the pixel data sample is identified using the flag.

In some embodiments, the method may further include receiving a flag indicating that a row of pixel data samples is not present in the clue data. In such embodiments, the pixel data samples are included in the row.

In some implementations, identifying the absence of pixel data samples includes analyzing clue data for missing pixel data samples.

In some embodiments, the method may further include identifying previous clue data. In such embodiments, the method may further include determining that the previous clue data comprises a previous pixel data sample.

In some embodiments, the method may further include identifying previous clue data. In such embodiments, the method may further include determining that the previous pixel data sample does not exist in the previous clue data. In such embodiments, the method may further include determining to use the previous pixel data sample to match the clue data of the frame to the reference data set.

The features, aspects, and advantages of the present disclosure will be most readily understood when the following description is read with reference to the accompanying drawings, in which like numerals refer to like components or parts throughout.

BRIEF DESCRIPTION OF THE DRAWINGS

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

1 is a block diagram of an example of a matching system for identifying video content being viewed by a media system.

FIG. 2 illustrates an example of a matching system for identifying unknown data points.

3 is a block diagram of an example of a video capture system.

4 is a block diagram of an example of a system for collecting video content presented by a display.

FIG. 5 shows an example of a sequence of frames that may be sent to a matching server.

FIG. 6 shows an example of a frame sequence with several rows of pixel data samples removed.

FIG. 7 shows an example of a sequence of frames that are not sent to the matching server.

8 is a flow diagram illustrating an example of a process for discarding pixel data samples from clue data for a frame.

9 is a flow chart illustrating an example of a process for using initial frame data to determine unidentified media segments to supplement new frame data.

FIG. 10 is a diagram showing point locations and their surrounding waypoints.

FIG. 11 is a graph showing a set of points that are within a distance from a query point.

FIG. 12 is a chart showing possible point values.

FIG. 13 is a diagram showing a space partitioned into rings of exponentially increasing width.

FIG. 14 is a diagram illustrating self-intersecting paths and query points.

FIG. 15 is a diagram showing three consecutive point locations and their surrounding waypoints.

DETAILED DESCRIPTION

In the following description, for the purpose of explanation, specific details are set forth in order to provide a thorough understanding of the examples of the present disclosure. However, it is apparent that the various examples can be practiced without these specific details. The drawings and descriptions are not intended to be limiting.

The following description provides only exemplary examples and is not intended to limit the scope, applicability, or configuration of the present disclosure. On the contrary, the subsequent description of the exemplary examples will provide those skilled in the art with possible descriptions for implementing the exemplary 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 disclosure as set forth in the appended claims.

Specific details are provided in the following description to provide a thorough understanding of the examples. However, one of ordinary skill in the art will appreciate that the examples can be practiced without these specific details. For example, circuits, systems, networks, processes, and other components may be shown 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.

In addition, it should be noted that various examples may be described as processes, which are depicted as flow charts, flow diagrams, 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 diagram. A process may correspond to a method, function, procedure, subroutine, subprogram, etc. When a process corresponds to a function, its termination may correspond to returning the functionality 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 non-transient media in which data can be stored and does not include carrier waves and/or transient electronic signals that are transmitted wirelessly or via a wired connection. Examples of non-transient media may include, but are not limited to, disks or tapes, optical storage media such as compact discs (CDs) or digital versatile discs (DVDs), flash memory, memory, or storage devices. A computer program product may include code and/or machine-executable instructions representing any combination of a program, 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, the program code or code segments that perform the necessary tasks (e.g., a computer program product) 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 below, certain aspects and features of the present disclosure relate to identifying unknown video segments by comparing unknown data points 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 video segments. For example, the systems and methods allow the identification of unknown data segments while reducing the density of the large data sets required to perform the identification. The technology can be applied to any system that harvests and manipulates large amounts of data. Illustrative examples of these systems include automated content-based 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 system. 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 to enable the matching system to search and find the relationship between unknown data groups and known data groups.

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.

A significant challenge with ACR systems and other systems that use large amounts of data can be the volume of data required to manage the system to do its job. Another challenge includes the need to establish and maintain a database of known content to use as a reference for matching incoming content. Establishing and maintaining such a database involves collecting and extracting large amounts (e.g., hundreds, thousands, or more) of content (e.g., nationally distributed television programs and an even larger number of local television broadcasts among many other potential content sources). Extraction can be performed using any available technology that reduces raw data (e.g., video or audio) to compressed, searchable data. With a 24-hour, 7-day-a-week operating schedule and a sliding window of approximately two weeks of content (e.g., television programs) to store, the volume of data required to perform ACR can be quickly established. Similar challenges may exist for other systems that harvest and manipulate large amounts of data, such as the example systems described above.

The systems and methods described herein may allow for improved management of system resources in an ACR system. For example, examples may improve the efficiency of system resource utilization by managing data sent to and/or stored on the ACR system. Although the description herein may relate to video segments, other media segments, including audio segments, may also be used.

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 such as 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 the video received 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, 50 bytes, 75 bytes, 100 bytes, 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 during a 24-hour period over three days 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 to 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, when the pixels at each sample location are within a specific range of pixel values, the reference data point can be a certain distance away from the unknown data point.

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) 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 approximately matches an unknown data point, thereby resulting in the identification of multiple candidate data points (associated with different media segments) for the unknown data point. The candidate determination engine 114 may return the candidate data points to the matching engine 112 .

For candidate data points, the matching engine 112 may add tokens to bins associated with the candidate data points and assigned to the identified video segments from which the candidate data points were derived. Corresponding tokens may be added to all bins corresponding to the identified candidate data points. As the matching server 104 receives more unknown data points (corresponding to 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 bins corresponding to the identified candidate data points. Only one of these bins corresponds to the unknown video content segment being viewed; the other bins correspond to candidate data points that match 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 unknown video content segment being viewed will have more tokens assigned to it than other bins for video content segments not being viewed. 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 contains a certain number of tokens, the matching engine 112 may determine that the video segment associated with the bin is currently being displayed on the client device 102. A video segment may comprise an entire video program or a portion of a video program. For example, a video segment may 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, facial images or patterns, etc.). For example, the matching engine 212 receives unknown data content 202 (which may be referred to as "clue data") that is to be matched with a reference data point 204 in a reference database. The unknown data content 202 may also be received by or sent from the matching engine 212 to the candidate determination engine 214. The candidate determination engine 214 may 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 may 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 candidate data points 206 are input to the matching engine 212 for a matching process to generate matching results 208. Depending on the application, the 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.

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 requiring 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 build 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 a video frame buffer. The array of video pixels is referred to as 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) values or any other suitable color values.

An average (or, in some cases, mean) is taken for each pixel block, and the resulting data record is created and marked with a time code (or timestamp). For example, a mean is found for each 10×10 pixel block array, in which case 24 bits of data are generated for every 25 display buffer locations, for a total of 600 bits of pixel information per frame. In one example, the mean for pixel block 304 is calculated and shown by pixel block mean 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, January 1, 1970. For example, pixel block mean 308 value 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. Metadata can 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 mean, time code, and metadata forms a "data point" (also known 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.

In some examples, the clue data can be analyzed before being sent to a matching server (e.g., matching server 104) to reduce the amount of data sent to the matching server and the amount of data stored remotely from the media system (e.g., on the matching server or in a database associated with the matching server). In some examples, at least a portion of the new clue data can be discarded based on determining whether the new clue data is sufficiently similar to previous clue data that has already been sent to the matching server. For example, one or more pixel data samples can be discarded from the new clue data. In other examples, the methods described herein for discarding pixel data samples can occur on the matching server after the pixel data samples are received by the matching server.

5 shows an example of a frame sequence that may be sent to a matching server (e.g., matching server 104). The frame sequence may include a first frame 510, a second frame 520, a third frame 530, and a fourth frame 540. One of ordinary skill in the art will recognize that there may be more or fewer frames in the frame sequence.

In some examples, the process of converting frames of a frame sequence into clue data can be similar to that discussed in FIG. 3 . For example, one or more positions (e.g., position 1, position 2, position 3, position 4, position 5, position 6, position 7, and position 8) can be identified in a frame. In some examples, the position can be a pixel block, which can include a pixel array (e.g., one or more pixels arranged in a format such as 10×10). In some examples, the pixel can include a red value, a green value, and a blue value (in a red-green-blue (RGB) color space). One of ordinary skill in the art will recognize that other color spaces can be used. In some examples, one or more pixels in the pixel array can be summarized before being sent to the matching server. For example, one or more pixels can each have the red value of one or more pixels averaged to create an average red value for the one or more pixels. One or more pixels can also each have the green value of one or more pixels averaged to create an average green value for the one or more pixels. One or more pixels can also each have the blue value of one or more pixels averaged to create an average blue value for the one or more pixels. In some examples, the average red value, average green value, and average blue value of a pixel can be averaged in a similar manner with other average red values, average green values, and average blue values of pixels in the pixel array to create a pixel data sample for the location. For example, the average red value of one or more pixels can be 0, the average green value of one or more pixels can be 255, and the average blue value of one or more pixels can be 45. In such an example, the pixel data samples for the one or more pixels can be 0, 255, and 45, allowing the use of a three-digit number to summarize the one or more pixels.

In other examples, the red value, green value, and blue value of a pixel can be averaged together to create an average pixel value for the pixel. The average pixel value of a pixel in a pixel array can be averaged together with other average pixel values of other pixels in the pixel array to create a pixel data sample for a position. In such an example, one or more red values, one or more green values, and one or more blue values can be averaged together to create a number to summarize one or more pixels. In the above example, a number summarizing one or more pixels can be 100, which is the average value of 0, 255, and 45.

In some examples, pixel data samples can be calculated for each position in the frame. The pixel data samples of the frame can then be combined to send to the matching server. In some examples, the combination can include appending numbers together to create one number. For example, 100, 25, and 55 can be combined into 100025055. In other examples, a clue data object can be created with a variable for each position. In such an example, the clue data object can be sent to the matching server. In other examples, the pixel data (e.g., the red value, green value, and blue value of a pixel) can be connected in series with a bitmap indicating whether the position (as described above) includes a value. For example, a position that includes a value can include "1", and a position that does not include a value (e.g., a value is removed) can include "0". Those skilled in the art will recognize that other methods can be used to summarize the positions in the frame.

FIG6 shows an example of a frame sequence in which several rows of pixel data samples are removed. By removing several rows of pixel data samples, the size of the frame sequence can be reduced and the amount of memory required to store the frame sequence can be reduced. One of ordinary skill in the art will recognize that individual pixel data samples can be removed from the clue data rather than removing entire rows.

In some examples, a row of pixel data samples may be removed from the clue data when one or more pixel data samples of the clue data are similar to the previous clue data. In some examples, a pixel data sample may be similar to another pixel data sample when the difference between the two pixel data samples is within a pixel value range. The pixel value range may be preconfigured. For example, the pixel value range may be 5 values in a value range of 0-255 (positive or negative). In such an example, a first pixel data sample is similar to a second pixel data sample when the first pixel data sample is within 5 values of the second pixel data sample.

In one illustrative example, frame 610 may include all eight pixel data samples. However, frame 620 may include pixel data samples 4-8, but not 1-3. Because at least one of pixel data samples 1-3 of frame 620 is similar to the corresponding pixel data sample of pixel data samples 1-3 of frame 610, pixel data samples 1-3 of frame 620 may be removed. Furthermore, frame 630 may include pixel data samples 1-3 and 6-8, but not pixel data samples 4-5. Because pixel data samples 1-3 of frame 630 are different from pixel data samples 1-3 of frame 620, pixel data samples 1-3 of frame 620 may be retained. However, because at least one of pixel data samples 4-5 of frame 630 is similar to the corresponding pixel data sample of pixel data samples 4-5 of frame 620, pixel data samples 4-5 of frame 630 may be removed. Additionally, frame 640 may include pixel data samples 6-8, but not pixel data samples 1-5. Because at least one of pixel data samples 1-3 of frame 640 is similar to a corresponding pixel data sample of pixel data samples 1-3 of frame 630, pixel data samples 1-3 of frame 640 can be removed. Because at least one of pixel data samples 4-5 of frame 640 is similar to a corresponding pixel data sample of pixel data samples 4-5 of frame 620, pixel data samples 4-5 of frame 640 can be removed (because pixel data samples 4-5 of frame 630 have already been removed, comparison with frame 630 can be skipped). In other examples, the media system can store pixel data samples 4-5 of frame 630 so that the media system does not have to store pixel data samples from multiple frames. In such an example, frame 640 can be compared to frame 630 for all pixel data samples.

In some examples, one or more flags may be sent to the matching server along with the clue data or in addition to the clue data. The one or more flags may indicate whether a row has been removed from the frame. For example, a flag of "0" may indicate that a row has not been removed, and a flag of "1" may indicate that a row has been removed. In other examples, a flag may be associated with each pixel data sample, indicating whether a particular pixel data sample has been removed. One of ordinary skill in the art will recognize that the one or more flags may be implemented in different ways, as long as the one or more flags indicate to the matching server which rows or which pixel data samples have been removed.

FIG6 illustrates flags for each row of a frame. Flags 612 are associated with frame 610. Flags 612 include a first flag 614, a second flag 616, and a third flag 618. First flag 614 may be associated with a first row of pixel data samples of frame 610, which may include pixel data samples 1-3. First flag 614 includes a “0,” indicating that pixel data samples 1-3 of frame 610 have not yet been removed. Second flag 616 may be associated with a second row of pixel data samples of frame 610, which may include pixel data samples 4-5. Second flag 616 includes a “0,” indicating that pixel data samples 4-5 of frame 610 have not yet been removed. Third flag 616 may be associated with a third row of pixel data samples of frame 610, which may include pixel data samples 6-8. Third flag 618 includes a “1,” indicating that pixel data samples 6-8 of frame 610 have not yet been removed.

6. Flags 622 are associated with frame 620. Flags 622 include a first flag 624, a second flag 626, and a third flag. First flag 624 may be associated with a first row of pixel data samples of frame 620, which may include pixel data samples 1-3. First flag 624 includes a "1," indicating that pixel data samples 1-3 of frame 610 have been removed. Second flag 626 may be associated with a second row of pixel data samples of frame 620, which may include pixel data samples 4-5. Second flag 616 includes a "0," indicating that pixel data samples 4-5 of frame 620 have not yet been removed.

In some examples, the matching server can receive flags. The matching server can determine which pixel data samples to use when performing an operation on the clue data based on one or more flags associated with the clue data. For example, when performing an operation on the clue data of frame 620, the matching server can determine to use the clue data of frame 610 for pixel data samples 1-3 and to use the clue data of frame 620 for pixel data samples 4-8. In some examples, the operation can include matching the clue data to a reference dataset, as described above.

In the event that a previous frame (e.g., frame 630) has the same removed pixel data samples as a current frame (e.g., frame 640), the matching server may use a frame preceding the previous frame (e.g., frame 620). For example, when performing an operation on frame 640, the matching server may use pixel data samples 1-3 of frame 630, pixel data samples 4-5 of frame 620, and pixel data samples 6-8 of frame 640.

In some examples, there may not be an indication (e.g., a flag) that the pixel data sample does not exist that is sent to the matching server. By not sending the indication of the lost pixel data sample, the media system can send less data to the matching server. In this example, the matching server can detect the non-existence of the pixel data sample. A method of determining that the pixel data sample does not exist is to identify whether a part of the clue data is lost. For example, when the clue data is an object with a variable at each position in the position, when the variable does not include a value (or includes null, negative, or pixel data samples are not yet included in some other indications), the matching server can identify the lost pixel data sample. When the clue data is a non-object format, a field delimiter can be used, such as a comma, space, or other character. The expected lost data can be conveyed by not including one or more values between two field delimiters. When the lost pixel data sample is detected, the matching server can replace the last non-similar pixel data sample from one or more previous frames.

By removing pixel data samples from the frames, the overall storage load on the matching server can also be reduced. An example of how this would occur would be a video segment that includes a blue sky that does not change for many frames. The pixel data samples associated with the blue sky for many frames can be removed from the clue data and not sent to the matching server or stored by the matching server. Another example of redundant data can be found in news, sports, or entertainment talk shows where only a portion of the frames are moving (e.g., people talking). The portion of the frame that is not moving can be removed from the clue data and not sent to the matching server or stored by the matching server.

FIG7 illustrates an example of a frame sequence 700 in which frames are not sent to a matching server (e.g., matching server 104). In some examples, the media system may determine not to send a frame to the matching server when the frame is sufficiently similar to a previous frame. In other examples, the media system may determine not to send a frame to the matching server at a particular time of day. In such examples, a lower frame rate may be sufficient for monitoring viewing statistics.

In some examples, sufficiently similar can be determined by comparing one or more current pixel data samples of the current frame with one or more previous pixel data samples of the previous frame, as discussed above. In some examples, one or more current pixel data samples of the current frame can be compared with any previous pixel data samples of similar pixel data samples. The media system can compare the number of matches between the current pixel data samples of the current frame and the previous pixel data samples of the previous frame. In some embodiments, if the number exceeds a threshold, the media system can determine not to send the current frame to the matching server. In some examples, the threshold can be a percentage of pixel data samples (e.g., 80%, 90%, or some other percentage indicating that the media system is sufficiently confident that the current frame and the previous frame are sufficiently similar). One of ordinary skill in the art will recognize that the threshold can be in different formats (e.g., a minimum number of similar pixel data samples, the number of similar pixel data samples on each row, or some other metric indicating similarity between one frame and another).

To illustrate an example where a frame is not sent, frame sequence 700 includes several frames (e.g., first frame 710, second frame 720, third frame 730, fourth frame 740, fifth frame 750, sixth frame 760, and seventh frame 770). A frame including a solid line may indicate that the frame is sent from the media system to the matching server. A frame including a dashed line may indicate that the frame is not sent from the media system to the matching server. First frame 710 includes a solid line, indicating that first frame 710 is sent to the matching server. First frame 710 can be sent to the matching server because first frame 710 does not have a previous frame that matches it. On the other hand, the media system may determine that second frame 720 should not be sent to the matching server because second frame 720 is sufficiently similar to first frame 710.

The third frame 730 may be sent to the matching server, indicating that the third frame is sufficiently different from the second frame 720 to require sending the third frame 730 to the matching server.

In some examples, when a frame is not sent to the matching server, the media system may not store the frame. In such examples, the comparison of the current frame and the previous frame may skip any frames that were not sent to the matching server. For example, since both the fifth frame 750 and the sixth frame 760 were not sent to the matching server, the seventh frame 770 may be compared with the fourth frame 740. In such an example, the media system may only store the previous frame that was sent to the matching server.

In other embodiments, the media system may only store previous frames that have been converted into clue data, regardless of whether the clue data has been sent to the matching server. In such an example, frames that have not been sent to the matching server can be compared with the current frame and previous frames. For example, even if the sixth frame 760 has not been sent to the matching server, the seventh frame 770 can be compared with the sixth frame 760.

Examples of similar frames can be found, but are not limited to, in news, sports, or entertainment talk shows, where only the audio component of the frame changes (e.g., a fixed picture). In such an example, the media system can determine that a certain number of consecutive frames have not been sent to the matching system. Upon determining that the certain number of consecutive frames have not been sent, the media system can determine to send additional information to the matching server to identify the frame being displayed on the media system (e.g., the audio portion of the frame can be sent instead of the video portion). In such an example, the matching server can use one or more audio portions instead of one or more video portions (e.g., pixels in one or more frames) to identify the video segment being displayed on the media system.

In the example where a frame is not sent to the matching server, the media system may send a flag indicating that the frame was not sent. In other embodiments, a flag may be included in the frame sent to the matching server, the flag indicating the frame number, so that the matching server can determine when a frame was not sent. In other embodiments, the flag may not be sent to the matching server. In such an embodiment, the matching server may continue to match frames to video segments without any knowledge of the missing frames. The matching method herein allows the matching server to still identify video segments when one or more frames have not been sent to the matching server.

Figure 8 is a flow diagram illustrating an example of a process 800 for discarding pixel data samples from clue data for a frame. In some examples, process 800 can be performed by a media system. Process 800 is illustrated as a logical flow diagram, the operations of which represent a series of operations that can be implemented in hardware, computer instructions, or a combination thereof. In the context of computer instructions, the operations represent computer-executable instructions stored on one or more computer-readable storage media that, when executed by one or more processors, perform the operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures, etc. that perform specific functions or implement specific data types. The order in which the operations are described is not intended to be construed as a limitation, and any number of the described operations can be combined in any order and/or in parallel to implement the processes.

In addition, process 800 can be executed under the control of one or more computer systems configured with executable instructions, and can be implemented as code (e.g., executable instructions, one or more computer programs, or one or more applications) that is executed together on one or more processors through hardware or a combination thereof. As described above, the code can be stored on a machine-readable storage medium, for example, in the form of a computer program including multiple instructions that can be executed by one or more processors. The machine-readable storage medium can be non-transitory.

At step 805, process 800 includes receiving an initial frame. In some examples, the initial frame may be associated with a first video segment. In such examples, the media system may not know the identity of the first video segment. The media system may receive the initial frame from a remote source, including a broadcast provider or a server on a network (e.g., the Internet). In some examples, the initial frame may include pixel data. The pixel data may include pixels that allow the frame to be displayed. In some examples, the pixels may include one or more pixel values (e.g., a red value, a green value, and a blue value in a red-green-blue (RGB) color space).

At step 810, process 800 includes determining initial clue data for the initial frame. The initial clue data may include a plurality of initial pixel data samples associated with the initial frame. In some examples, the initial pixel data samples may be determined for each of one or more locations (e.g., blocks of pixels) of the initial frame. In some examples, the initial pixel data samples may be calculated for a location by summarizing (e.g., averaging) one or more pixels included in the location. The one or more pixels may be an array of pixels (e.g., 10×10). In some examples, the red value, green value, and blue value of the one or more pixels may be summarized separately. In other examples, the red value, green value, and blue value of the one or more pixels may be summarized together to create a number for the location.

At step 815, process 800 includes sending initial clue data. The initial clue data can be sent to a server (e.g., a matching server) by addressing the initial clue data to the server. The server can attempt to match the initial clue data with a first reference data set. Matching can occur by comparing the initial clue data with other clue data (e.g., the first reference data set).

At step 820, process 800 includes receiving a new frame. In some examples, the new frame may include pixel data and be received after the initial frame. The new frame may be associated with a second video segment. In some examples, the second video segment may be the same as the first video segment. For example, the media system may receive two frames from the same video segment. In other examples, the second video segment may be different from the first video segment. For example, a transition between the first video segment and the second video segment may occur between receiving the initial frame and the new frame.

At step 825, process 800 includes determining new clue data for the new frame. The new clue data may include a plurality of new pixel data samples associated with the new frame. The new clue data may be determined in the same manner as discussed above for the initial clue data.

At step 830, process 800 includes identifying a pixel value range. In some examples, the pixel value range can be a plurality of pixel values. In some examples, the pixel data samples are determined to be similar when the pixel value difference between the pixel data samples is within the pixel value range. For example, the pixel value range can be 5 values. In such an example, when the second pixel data sample is within a value of plus or minus 5 of the first pixel data sample, the first pixel data sample will be within the pixel value range of the second pixel data sample.

At step 835, process 800 includes determining a difference in pixel value range between the initial pixel data sample and the new pixel data sample. In some examples, the initial pixel data sample can correspond to the new pixel data sample. For example, if the initial pixel data sample is associated with position 1 of first frame 510 of FIG. 5 , then the pixel data sample associated with position 1 of second frame 520 would correspond to the initial pixel data sample.

At step 840 , process 800 includes determining that the pixel value difference is within the pixel value range. In some examples, the pixel value difference can be determined to be within the pixel value range by comparing the pixel value difference to the pixel value range to identify whether the pixel value difference is less than the pixel value range.

At step 845, process 800 includes updating the new clue data by removing the new pixel data sample from the new clue data when the pixel value difference is within the pixel value range. In some examples, removing the new pixel data sample from the new clue data may include removing a row of pixel data samples from the new clue data. In such examples, the new pixel data sample may be included in the row of pixel data samples. In other examples, only the new pixel data sample may be removed from the new clue data, rather than removing the entire row.

At step 850, process 800 includes sending updated new clue data. The updated new clue data can be sent to the server by addressing the updated new clue data to the server. The server can attempt to match the updated new clue data with the second reference data set. The matching can be performed by comparing the new updated clue data with other clue data (e.g., the second reference data set). In some examples, when comparing the new updated clue data with the other clue data, the matching server can replace the removed pixel data samples with pixel data samples from clue data received before the updated new clue data. In such an example, the matching server can use pixel data samples in the previous frame that correspond to the removed pixel data samples.

In some examples, process 800 can further include sending a flag indicating that the new pixel data sample is to be removed from the new clue data. In other examples, process 800 can further include sending a flag indicating that a row of pixel data samples is to be removed from the new clue data. In such an example, the new pixel data sample can be included in the row. In either set of examples, the flag can be sent to the server by addressing the flag to the server.

FIG9 is a flow chart illustrating an example of a process 900 for using initial frame data to determine unrecognized media segments to supplement new frame data. In some examples, process 800 can be performed by a media system. Process 900 is illustrated as a logical flow chart, the operations of which represent a sequence of operations that can be implemented in hardware, computer instructions, or a combination thereof. In the context of computer instructions, the operations represent computer-executable instructions stored on one or more computer-readable storage media that, when executed by one or more processors, perform the operations. Typically, computer-executable instructions include routines, programs, objects, components, data structures, etc. that perform specific functions or implement specific data types. The order of the operations described is not intended to be construed as limiting, and any number of the operations described can be combined in any order and/or in parallel to implement the process.

In addition, process 900 can be executed under the control of one or more computer systems configured with executable instructions, and can be implemented as code (e.g., executable instructions, one or more computer programs, or one or more applications) that is executed together on one or more processors through hardware or a combination thereof. As described above, the code can be stored on a machine-readable storage medium, for example, in the form of a computer program including multiple instructions that can be executed by one or more processors. The machine-readable storage medium can be non-transitory.

At step 910, process 900 includes storing a plurality of reference data sets in a reference database. In some examples, the reference data sets can be associated with media segments. In some examples, the reference data sets can correspond to clue data (e.g., the reference data sets can be determined in a manner similar to the clue data such that the reference data sets can be matched with the clue data).

At step 920, process 900 includes receiving clue data for a frame. The clue data can be received from a server (e.g., a matching server). In some examples, the clue data can include a plurality of pixel data samples associated with the frame. The frame can be associated with the first unrecognized media segment.

At step 930, process 900 includes identifying absent pixel data samples in clue data for the frame. In some examples, as described above, identifying absent pixel data samples includes analyzing the clue data for missing pixel data samples.

In other examples, process 900 can identify that a pixel data sample does not exist by following the steps described above. As described above, the matching server can identify previous clue data and determine that the previous clue data includes a previous pixel data sample. The previous clue data can be received before the clue data. In other examples, the matching server can identify previous clue data, determine that the previous pixel data sample does not exist in the previous clue data, and determine to use the previous pixel data sample to match the clue data of the frame of the reference dataset, as described above.

At step 940, process 900 includes matching clue data for the frame to a reference data set. The reference data set can be associated with the media segment. In some examples, the matching can include using previous pixel data samples of previous clue data. The previous clue data can be from a previous frame. In some examples, the previous pixel data samples correspond to pixel data samples that are not present in the frame.

At step 950, process 900 includes determining that the unidentified media segment is the media segment. As described above, the unidentified media segment can be identified as the media segment when the bin associated with the media segment reaches a threshold.

In some examples, process 900 may further include receiving a flag indicating that the pixel data sample is not present in the clue data. The absence of the pixel data sample can be identified using the flag. In other examples, process 900 may further include receiving a flag indicating that a row of pixel data samples is not present in the clue data. In such an example, the pixel data sample may be included in the row.

In some examples, process 900 can further include identifying intermediate cue data from the intermediate frame. The intermediate cue data can include a plurality of pixel data samples from the intermediate frame. In some examples, the intermediate frame can be associated with the first unidentified media segment. In such examples, process 900 can further include identifying intermediate cue data having no intermediate pixel data samples from the intermediate frame.

In such an example, process 900 may further include identifying previous clue data from a previous frame. The previous clue data may include multiple pixel data samples from the previous frame. In some examples, the previous frame may be associated with a second unidentified media segment. In some examples, the second unidentified video segment may be the same as the first unidentified video segment. For example, the media system may receive two frames from the same unidentified video segment and send the two frames to the matching server. In other examples, the second unidentified video segment may be different from the first unidentified video segment. For example, the transition between the first unidentified video segment and the second unidentified video segment may occur between receiving the initial frame and the new frame.

As discussed above, the video matching system can be configured to identify the media content stream when the media content stream includes unidentified media segments. As discussed further above, identifying the media content stream can include identifying the media content presented by the media display device before or after the unidentified 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 content.

The video matching system may further include various methods for improving the efficiency of finding potential matches or "candidates" in the database. The database may contain a large number of clues, and therefore the video matching system may include an algorithm for finding candidate clues to match the clues generated by 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 locate candidate queues in a reference database. Below is an example of using fuzzy cues to track video transmissions, but the general concept can be applied to any field where candidate matches are selected from a reference database.

A method for efficient video tracking is presented. Given a large number of video segments, the system must be able to identify in real time what video segment a given query video input was taken from and at what time offset. The video 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 video segments and switches to unknown video segments. Before being able to track live video, a database is processed. Visual clues (a few pixel values) are taken from the frame every constant fraction of a second and put into a specialized data structure (note that this can also be done in real time). Video tracking is performed by constantly receiving clues from the input video and updating a set of beliefs or estimates about its current position. Each clue 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 position. This can be done efficiently by tracking only a small number of possible "suspicious" positions.

Methods for video tracking are described, but the method uses mathematical constructions to explain and investigate it. The purpose of this introduction is to give the reader 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 made up 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 high in dimension, typically between 15 and 150, they can be imagined as points in a two-dimensional space. 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 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, just as a bead would on a curved line.

In the language of this analogy, in video tracking, we receive the position of a bead in space (a clue point) and try to find the part of the line that the bead follows (the path). This is significantly more difficult for two reasons. First, the bead does not follow the line exactly, but rather maintains an unknown distance from it with some variation. Second, the lines are all tangled together. These statements become 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 suspicious positions with low probability. This history update process ensures that only a small piece of history is retained and that possible positions are not deleted. The general algorithm is given in Algorithm 1 and illustrated in Figure 10.

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 the search for suspects is crucial to the applicability 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 equal spheres (PPLEB). In traditional PLEB (point location in equal spheres), 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. 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 deal with 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 be easily verified 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. 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)

Now calculate the probability that h(x) = h(y) given that they are neighbors:

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 increase this probability to 1/2.

1.2 Node Search Algorithm

Each 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 sections 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 13, 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 ‖x _i ‖∈[2r(1+∈) ⁱ , 2r(1+∈) ⁱ⁺¹ ]. This achieves two goals. First, if x _i and x _j belong to the same ring, then ||x _j ||/(1+∈)≤‖x _i ‖≤||x _j ||(1+∈). Second, any search can be performed in at most 1/∈ such rings. Furthermore, if the maximum length vector in the dataset 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 positions as positions along 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 14. 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 identify with certainty where a particle actually is 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 deviation is the one that the particle's history makes most likely for it. 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 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 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 denote 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 larger constant factor. The final stage of the algorithm is to output a specific value δ if some threshold is exceeded.

Figure 10 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 11, 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 it (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 12 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 13 shows that by dividing the space into multiple rings such that a ring R _i is between radius 2r(1+∈) ⁱ and 2r(1+∈) ⁱ⁺¹ , it is ensured that any two vectors within the ring are of the same length, up to a factor of (1+∈), and any search is performed in at most 1/∈ rings.

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

Figure 15 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.

Substantial variations can be made depending on specific requirements. For example, customized hardware can also 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 or computing devices, such as network input/output devices, can be utilized.

In the foregoing description, various aspects of the present disclosure have been described with reference to their specific examples, but those skilled in the art will recognize that the present disclosure is not limited thereto. The various features and aspects disclosed above can be used individually or in combination. In addition, without departing from the broader spirit and scope of this specification, examples can 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 alternative examples, 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.

Figure 1

102 client devices

104 Matchmaking Servers

106 Media Client

108 Input Devices

110 Output Devices

112 Matching Engine

114 Candidate Determination Engine

116 reference databases

118 Data Sources

120 Results Engine

126 Background-triggered applications

128 video programs

Figure 2

Timecode

Metadata

204 reference data points

212 Matching Engine

214 Candidate Determination Engine

Figure 3

Timecode

Metadata

10pixel 10 pixels

Figure 4

10pixel 10 pixels

Figure 7

700 frame sequence

Figure 8

805 Receive initial frame

810 Determine the initial clue data of the initial frame

815 Send initial clue data

820 Receive new frame

825 Determine the new clue data for the new frame

830 Identify pixel value range

835 Determine the pixel value difference between the initial pixel data sample and the new pixel data sample

840 Determine if the pixel value difference is within the pixel value range

845 When the pixel value difference is within the pixel value range, the new pixel data sample is removed from the new clue data.

Originally updated new clue data

850 Send updated new lead data

Figure 9

910 Storing multiple reference datasets in a reference database

920 Receive frame clue data

930 The pixel data sample does not exist in the clue data of the recognition frame

940 Matching the clue data of the frame with the reference dataset

950 Determine if the unrecognized media segment is this media segment

Figure 10

Path points

Suspect

Particle location

Claims (17)

1. A computer-implemented method for optimizing clue data sent to a matching server for content recognition, the method comprising: Receive an initial frame, wherein the initial frame includes pixel data; Determine initial clue data for the initial frame, wherein the initial clue data includes at least one average value of pixel data from a plurality of initial pixel data samples associated with the initial frame or a subset of pixels in the initial frame; Send the initial clue data, wherein the initial clue data is addressed to the server; Receive a new frame, wherein the new frame includes pixel data, and wherein the new frame is received after the initial frame; Determine new cue data for the new frame, wherein the new cue data includes at least one average value of pixel data from a plurality of new pixel data samples associated with the new frame or a subset of pixels in the new frame; Identify a range of pixel values, wherein pixel data samples are determined to be similar when the difference in pixel values between them is within the range of pixel values; Determine the pixel value difference between an initial pixel data sample and a new pixel data sample, wherein the initial pixel data sample and the new pixel data sample are associated with the same region of the initial frame and the new frame; The pixel value difference is determined to be within the range of the pixel values; When the pixel value difference is within the pixel value range, the new clue data is updated by removing the new pixel data sample from the new clue data; Sending the updated new lead data to the matching server, wherein the updated new lead data is addressed to the server; and A flag is sent to the matching server, the flag indicating that the new pixel data sample has been removed from the new frame data. 2. The computer-implemented method according to claim 1, wherein: The flag indicates the removal of a row of pixel data samples from the new clue data, wherein the new pixel data samples are included in the row, and wherein the flag is addressed to the server. 3. The computer-implemented method of claim 1, wherein pixel data samples are calculated from pixel blocks, and wherein the pixel blocks comprise a pixel array of a frame. 4. The computer-implemented method according to claim 3, wherein the pixel data sample is calculated by taking the average of the pixel values of the pixels in the pixel block. 5. The computer-implemented method of claim 1, wherein the server is configured to identify the removal of the new pixel data sample from the updated new clue data. 6. The computer-implemented method of claim 1, wherein the initial frame is included in the broadcast signal. 7. A system for optimizing clue data sent to a matching server for content recognition, comprising: One or more processors; and A non-transitory computer-readable medium containing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations including: Receive an initial frame, wherein the initial frame includes pixel data; Determine initial clue data for the initial frame, wherein the initial clue data includes at least one average value of pixel data from a plurality of initial pixel data samples associated with the initial frame or a subset of pixels in the initial frame; Send the initial lead data, wherein the initial lead data is addressed to the matching server; Receive a new frame, wherein the new frame includes pixel data, and wherein the new frame is received after the initial frame; Determine new cue data for the new frame, wherein the new cue data includes at least one average value of pixel data from a plurality of new pixel data samples associated with the new frame or a subset of pixels in the new frame; Identify a range of pixel values, wherein pixel data samples are determined to be similar when the difference in pixel values between them is within the range of pixel values; Determine the pixel value difference between an initial pixel data sample and a new pixel data sample, wherein the initial pixel data sample and the new pixel data sample are associated with the same region of the initial frame and the new frame; The pixel value difference is determined to be within the range of the pixel values; When the pixel value difference is within the pixel value range, the new clue data is updated by removing the new pixel data sample from the new clue data; Sending the updated new lead data to the matching server, wherein the updated new lead data is addressed to the matching server; and A flag is sent to the matching server, the flag indicating that the new pixel data sample has been removed from the new frame data. 8. The system according to claim 7, wherein: The flag indicates the removal of a row of pixel data samples from the new clue data, wherein the new pixel data samples are included in the row, and wherein the flag is addressed to the matching server. 9. The system of claim 7, wherein pixel data samples are calculated from pixel blocks, and wherein the pixel blocks comprise a pixel array of a frame. 10. The system of claim 9, wherein the pixel data sample is calculated by taking the average of the pixel values of the pixels in the pixel block. 11. The system of claim 7, wherein the matching server is configured to identify the removal of the new pixel data sample from the updated new clue data. 12. The system of claim 7, wherein the initial frame is included in the broadcast signal. 13. A non-transitory machine-readable storage medium, comprising instructions that, when executed by one or more processors, cause the one or more processors to: Receive an initial frame, wherein the initial frame includes pixel data; Determine initial clue data for the initial frame, wherein the initial clue data includes at least one average value of pixel data from a plurality of initial pixel data samples associated with the initial frame or a subset of pixels in the initial frame; Send the initial clue data, wherein the initial clue data is addressed to the matching server; Receive a new frame, wherein the new frame includes pixel data, and wherein the new frame is received after the initial frame; Determine new cue data for the new frame, wherein the new cue data includes at least one average value of pixel data from a plurality of new pixel data samples associated with the new frame or a subset of pixels in the new frame; Identify a range of pixel values, wherein pixel data samples are determined to be similar when the difference in pixel values between them is within the range of pixel values; Determine the pixel value difference between an initial pixel data sample and a new pixel data sample, wherein the initial pixel data sample and the new pixel data sample are associated with the same region of the initial frame and the new frame; The pixel value difference is determined to be within the range of the pixel values; When the pixel value difference is within the pixel value range, the new clue data is updated by removing the new pixel data sample from the new clue data; Sending the updated new lead data to the matching server, wherein the updated new lead data is addressed to the matching server; and A flag is sent to the matching server, the flag indicating that the new pixel data sample has been removed from the new frame data. 14. The non-transitory machine-readable storage medium according to claim 13, wherein: The flag indicates the removal of a row of pixel data samples from the new clue data, wherein the new pixel data samples are included in the row, and wherein the flag is addressed to the matching server. 15. The non-transitory machine-readable storage medium of claim 13, wherein pixel data samples are calculated from pixel blocks, and wherein the pixel blocks comprise a pixel array of a frame. 16. The non-transitory machine-readable storage medium of claim 15, wherein the pixel data sample is calculated by taking the average of the pixel values of the pixels in the pixel block. 17. The non-transitory machine-readable storage medium of claim 13, wherein the matching server is configured to identify the removal of the new pixel data sample from the updated new clue data.