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

• US 10,185,768 B2
• Filed: 08/18/2016
• Issued: 01/22/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,815
• Publication Number:
  US 20170032034A1
• Time in Patent Office: 887 Days
• Field of Search: 725 90, 725 53, 382103, 382195
• 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:

identifying multiple video frames represented in a media database, wherein an identified video frame is represented in the media database by one or more hash values associated with one or more pixel locations in the identified video frame, and wherein the one or more hash values are stored in the media database;

identifying a pixel location in a video frame, wherein the pixel location includes one or more pixels in the video frame;

identifying, for the pixel location, multiple pixel values from the multiple video frames represented in the media database, wherein an identified pixel value represents the pixel location in an identified video frame;

computing a median value for the pixel location, wherein the median value is computed using the multiple pixel values identified for the pixel location from the multiple video frames, and wherein the median value is used to determine a hash value associated with the pixel location;

receiving a new pixel value for the pixel location in a new video frame;

modifying the new pixel value using the median value;

generating a new hash value for the new video frame, wherein the new hash value is generated by performing a hashing function on the modified new pixel value;

determining a media database sector of the media database for storing the new hash value, wherein the media database sector is determined using the new hash value; and

storing the new hash value in the media database sector.

2. The computer-implemented method of claim 1, wherein the new pixel value is an average of two or more pixels included in the pixel location in the new video frame, and wherein a pixel value of the multiple pixel values is an average of two or more pixels included in the pixel location in a video frame.

3. The computer-implemented method of claim 1, wherein modifying the new pixel value using the median value includes subtracting the median value from the new pixel value.

4. The computer-implemented method of claim 1, further including:

facilitating an identification of an unknown video segment being displayed on a media system, wherein the identification is performed using pixel data received from the media system and the new hash value stored in the media database sector.

5. The computer-implemented method of claim 1, wherein the new video frame is received from a media system displaying a stream of video, and wherein the stream of video includes the new video frame.

6. The computer-implemented method of claim 1, wherein the media database sector corresponds to a sector of a graph of pixel values representing the media database, wherein the sector includes the modified new pixel value, and wherein an origin of the graph is the median value.

19. The method of claim 1, wherein the median value is used to normalize new pixel values that are received.

7. 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;

identify multiple video frames represented in a media database, wherein an identified video frame is represented in the media database by one or more hash values associated with one or more pixel locations in the identified video frame, and wherein the one or more hash values are stored in the media database;

identify a pixel location in a video frame, wherein the pixel location includes one or more pixels in the video frame;

identify, for the pixel location, multiple pixel values from the multiple video frames represented in the media database, wherein an identified pixel value represents the pixel location in an identified video frame;

compute a median value for the pixel location, wherein the median value is computed using the multiple pixel values identified for the pixel location from the multiple video frames, and wherein the median value is used to determine a hash value associated with the pixel location;

receive a new pixel value for the pixel location in a new video frame;

modify the new pixel value using the median value;

generate a new hash value for the new video frame, wherein the new hash value is generated by performing a hashing function on the modified new pixel value;

determine a media database sector of the media database for storing the new hash value, wherein the media database sector is determined using the new hash value; and

store the new hash value in the media database sector.

8. The system of claim 7, wherein the new pixel value is an average of two or more pixels included in the pixel location in the new video frame, and wherein a pixel value of the multiple pixel values is an average of two or more pixels included in the pixel location in a video frame.

9. The system of claim 7, wherein modifying the new pixel value using the median value includes subtracting the median value from the new pixel value.

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

facilitating an identification of an unknown video segment being displayed on a media system, wherein the identification is performed using pixel data received from the media system and the new hash value stored in the media database sector.

11. The system of claim 7, wherein the new video frame is received from a media system displaying a stream of video, and wherein the stream of video includes the new video frame.

12. The system of claim 7, wherein the media database sector corresponds to a sector of a graph of pixel values representing the media database, wherein the sector includes the modified new pixel value, and wherein an origin of the graph is the median value.

13. 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:

identify multiple video frames represented in a media database, wherein an identified video frame is represented in the media database by one or more hash values associated with one or more pixel locations in the identified video frame, and wherein the one or more hash values are stored in the media database;

identify a pixel location in a video frame, wherein the pixel location includes one or more pixels in the video frame;

identify, for the pixel location, multiple pixel values from the multiple video frames represented in the media database, wherein an identified pixel value represents the pixel location in an identified video frame;

compute a median value for the pixel location, wherein the median value is computed using the multiple pixel values identified for the pixel location from the multiple video frames, and wherein the median value is used to determine a hash value associated with the pixel location;

receive a new pixel value for the pixel location in a new video frame;

modify the new pixel value using the median value;

generate a new hash value for the new video frame, wherein the new hash value is generated by performing a hashing function on the modified new pixel value;

determine a media database sector of the media database for storing the new hash value, wherein the media database sector is determined using the new hash value; and

store the new hash value in the media database sector.

14. The computer-program product of claim 13, wherein the new pixel value is an average of two or more pixels included in the pixel location in the new frame video, and wherein a pixel value of the multiple pixel values is an average of two or more pixels included in the pixel location in a video frame.

15. The computer-program product of claim 13, wherein modifying the new pixel value using the median value includes subtracting the median value from the new pixel value.

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

facilitate an identification of an unknown video segment being displayed on a media system, wherein the identification is performed using pixel data received from the media system and the new hash value stored in the media database sector.

17. The computer-program product of claim 13, wherein the new video frame is received from a media system displaying a stream of video, and wherein the stream of video includes the new video frame.

18. The computer-program product of claim 13, wherein the media database sector corresponds to a sector of a graph of pixel values representing the media database, wherein the sector includes the modified new pixel value, and wherein an origin of the graph is the median value.