Systems and methods for addressing a media database using distance associative hashing

• US 10,169,455 B2
• Filed: 08/18/2016
• Issued: 01/01/2019
• Est. Priority Date: 05/29/2009
• Status: Active Grant

• Current Assignee: Inscape Data, Inc. (VIZIO, Inc.)
• Original Assignee: Inscape Data, Inc. (VIZIO, Inc.)
• Inventors: Neumeier, Zeev, Reed, Brian
• Primary Examiner(s): Pendleton, Brian T
• Assistant Examiner(s): Luong, Alan H
• Application Number:
  US15/240,801
• Publication Number:
  US 20170032033A1
• Time in Patent Office: 866 Days
• Field of Search: 725 19, 725 32, 725 34- 36, 705 1449, 709226
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• CPC Class Codes: H04N 21/23109 by placing content in organized collections, e.g. EPG data repository details of retrieval of video data and associated meta data in video databases G06F16/739
• CPC Class Codes: H04N 21/23418 involving operations for analysing video streams, e.g. detecting features or characteristics television picture signal circuitry for scene change detection H04N5/147; filtering for image enhancement G06T5/00; methods or arrangements for recognising scenes G06V20/00; arrangements characterised by components specially adapted for monitoring, identification or recognition of video in broadcast systems H04H60/59
• CPC Class Codes: H04N 21/23424 involving splicing one content stream with another content stream, e.g. for inserting or substituting an advertisement
• CPC Class Codes: H04N 21/4316 for displaying supplemental content in a region of the screen, e.g. an advertisement in a separate window
• CPC Class Codes: H04N 21/4394 involving operations for analysing the audio stream, e.g. detecting features or characteristics in audio streams arrangements characterised by components specially adapted for monitoring, identification or recognition of audio in broadcast systems H04H60/58
• CPC Class Codes: H04N 21/44008 involving operations for analysing video streams, e.g. detecting features or characteristics in the video stream arrangements characterised by components specially adapted for monitoring, identification or recognition of video in broadcast systems H04H60/59
• CPC Class Codes: H04N 21/44204 Monitoring of content usage, e.g. the number of times a movie has been viewed, copied or the amount which has been watched monitoring of user activities for profile generation for accessing a video database G06F16/739; protecting generic digital content where the protection is independent of the precise nature of the content G06F21/10; arrangements for monitoring the use made of the broadcast services in broadcast systems H04H60/31
• CPC Class Codes: H04N 21/4532 involving end-user characteristics, e.g. viewer profile, preferences monitoring of user activities for profile generation for accessing a video database G06F16/739; user profiles in network data switching protocols H04L67/306; processing of user preferences or user profiles in wireless networks H04W8/18
• CPC Class Codes: H04N 21/462 Content or additional data management, e.g. creating a master electronic program guide from data received from the Internet and a Head-end, controlling the complexity of a video stream by scaling the resolution or bit-rate based on the client capabilities
• CPC Class Codes: H04N 21/4667 Processing of monitored end-user data, e.g. trend analysis based on the log file of viewer selections
• CPC Class Codes: H04N 21/47 End-user applications
• CPC Class Codes: H04N 21/478 Supplemental services, e.g. displaying phone caller identification, shopping application
• CPC Class Codes: H04N 21/8126 involving additional data, e.g. news, sports, stocks, weather forecasts
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments

Abstract

A system, method and computer program utilize a distance associative hashing algorithmic means to provide a highly efficient means to rapidly address a large database. The indexing means can be readily subdivided into a plurality of independently-addressable segments where each such segment can address a portion of related data of the database where the subdivided indexes of said portions reside entirely in the main memory of each of a multiplicity of server means. The resulting cluster of server means, each hosting an addressable sector of a larger database of searchable audio or video information, provides a significant improvement in the latency and scalability of an Automatic Content Recognition system, among other uses.

Claims

1. A computer-implemented method comprising:

receiving a pixel cue point associated with a frame of an unknown video segment, wherein the pixel cue point includes a set of pixel values corresponding to the frame;

identifying a plurality of bins, wherein a bin facilitates identification of a candidate video segment;

identifying candidate reference data points in a database of reference data points, wherein identified candidate reference data points are similar to the pixel cue point, and wherein a candidate reference data point includes one or more pixel values corresponding to a candidate frame of a candidate video segment;

adding a first token to a first bin associated with a first candidate video segment, wherein the first token is added to the first bin in response to identifying a first candidate reference data point;

adding a second token to a second bin associated with a second candidate video segment, wherein the second token is added to the second bin in response to identifying a second candidate reference data point;

determining that a quantity of tokens in the first bin exceeds a value, wherein the value is associated with a probability that the first candidate video segment matches the unknown video segment;

identifying the unknown video segment as matching the first candidate video segment when the quantity of tokens in the first bin exceeds the value; and

transmitting data associated with the first candidate video segment when the unknown video segment is identified.

2. The computer-implemented method of claim 1, further comprising:

removing one or more tokens from the first bin when a time period has elapsed.

3. The computer-implemented method of claim 1, wherein the pixel cue point includes an average value of the set of pixel values, and wherein the set of pixel values includes an array of pixel values extracted from the frame of the unknown video segment.

4. The computer-implemented method of claim 1, wherein a candidate reference data point is similar to the pixel cue point when the one or more pixel values corresponding to the candidate frame are within a pixel value range of the set of pixel values corresponding to the frame.

5. The computer-implemented method of claim 1, further comprising:

determining content associated with the candidate video segment;

retrieving the content from a database; and

transmitting the retrieved content, wherein the retrieved content is addressed to a media system, and wherein the pixel cue point is received from the media system.

6. The computer-implemented method of claim 1, further comprising:

removing one or more tokens from the first bin when an action occurs to change a source of video data, wherein the pixel cue point is derived from the source of video data.

7. The computer-implemented method of claim 6, wherein the action includes changing a first source of video data to a second source of video data, rewinding the unknown video segment, fast forwarding the unknown video segment, or pausing the unknown video segment.

8. A system 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;

receiving a pixel cue point associated with a frame of an unknown video segment, wherein the pixel cue point includes a set of pixel values corresponding to the frame;

identifying a plurality of bins, wherein a bin facilitates identification of a candidate video segment;

identifying candidate reference data points in a database of reference data points, wherein identified candidate reference data points are similar to the pixel cue point, and wherein a candidate reference data point includes one or more pixel values corresponding to a candidate frame of a candidate video segment;

adding a first token to a first bin associated with a first candidate video segment, wherein the first token is added to the first bin in response to identifying a first candidate reference data point;

adding a second token to a second bin associated with a second candidate video segment, wherein the second token is added to the second bin in response to identifying a second candidate reference data point;

determining that a quantity of tokens in the first bin exceeds a value, wherein the value is associated with a probability that the first candidate video segment matches the unknown video segment;

identifying the unknown video segment as matching the first candidate video segment when the quantity of tokens in the first bin exceeds the value; and

transmitting data associated with the first candidate video segment when the unknown video segment is identified.

9. The system of claim 8, further comprising instructions that, when executed by the one or more processors, cause the one or more processors to perform operations including:

removing one or more tokens from the first bin when a time period has elapsed.

10. The system of claim 8, wherein the pixel cue point includes an average value of the set of pixel values, and wherein the set of pixel values includes an array of pixel values extracted from the frame of the unknown video segment.

11. The system of claim 8, wherein a candidate reference data point is similar to the pixel cue point when the one or more pixel values corresponding to the candidate frame are within a pixel value range of the set of pixel values corresponding to the frame.

12. The system of claim 8, further comprising instructions that, when executed by the one or more processors, cause the one or more processors to perform operations including:

determining content associated with the candidate video segment;

retrieving the content from a database; and

transmitting the retrieved content, wherein the retrieved content is addressed to a media system, and wherein the pixel cue point is received from the media system.

13. The system of claim 8, further comprising instructions that, when executed by the one or more processors, cause the one or more processors to perform operations including:

removing one or more tokens from the first bin when an action occurs to change a source of video data, wherein the pixel cue point is derived from the source of video data.

14. The system of claim 13, wherein the action includes changing a first source of video data to a second source of video data, rewinding the unknown video segment, fast forwarding the unknown video segment, or pausing the unknown video segment.

15. A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, including instructions that, when executed by one or more processors, cause the one or more processors to:

receive a pixel cue point associated with a frame of an unknown video segment, wherein the pixel cue point includes a set of pixel values corresponding to the frame;

identify a plurality of bins, wherein a bin facilitates identification of a candidate video segment;

identify candidate reference data points in a database of reference data points, wherein identified candidate reference data points are similar to the pixel cue point, and wherein a candidate reference data point includes one or more pixel values corresponding to a candidate frame of a candidate video segment;

add first token to a first bin associated with a first candidate video segment, wherein the first token is added to the first bin in response to identifying a first candidate reference data point;

add a second token to a second bin associated with a second candidate video segment, wherein the second token is added to the second bin in response to identifying a second candidate reference data point;

determine that a quantity of tokens in the first bin exceeds a value, wherein the value is associated with a probability that the first candidate video segment matches the unknown video segment;

identify the unknown video segment as matching the first candidate video segment when the quantity of tokens in the first bin exceeds the value; and

transmitting data associated with the first candidate video segment when the unknown video segment is identified.

16. The computer-program product of claim 15, further including instructions that, when executed by the one or more processors, cause the one or more processors to:

remove one or more tokens from the first bin when a time period has elapsed.

17. The computer-program product of claim 15, wherein a candidate reference data point is similar to the pixel cue point when the one or more pixel values corresponding to the candidate frame are within a pixel value range of the set of pixel values corresponding to the frame.

18. The computer-program product of claim 15, further including instructions that, when executed by the one or more processors, cause the one or more processors to:

determine content associated with the candidate video segment;

retrieve the content from a database; and

transmit the retrieved content, wherein the retrieved content is addressed to a media system, and wherein the pixel cue point is received from the media system.

19. The computer-program product of claim 15, further including instructions that, when executed by the one or more processors, cause the one or more processors to:

remove one or more tokens from the first bin when an action occurs to change a source of video data, wherein the pixel cue point is derived from the source of video data.

20. The computer-program product of claim 19, wherein the action includes changing a first source of video data to a second source of video data, rewinding the unknown video segment, fast forwarding the unknown video segment, or pausing the unknown video segment.