Video hashing system and method

• US 8,494,234 B1
• Filed: 03/06/2008
• Issued: 07/23/2013
• Est. Priority Date: 03/07/2007
• Status: Expired due to Fees

• Current Assignee: Cubic Corporation
• Original Assignee: MotionDSP, Inc. (Cubic Corporation)
• Inventors: Bozinovic, Nikola, Velickovic, Ivan, Vuckovic, Ivan, Andjelkovic, Sasa, Andjelkovic, Nebojsa, Djordjevic, Danilo
• Primary Examiner(s): Liew, Alex
• Application Number:
  US12/043,579
• Time in Patent Office: 1,965 Days
• Field of Search: 382/103, 382124-127
• US Class Current: 382/124
• CPC Class Codes: G06F 16/783 using metadata automatically derived from the content
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames

Abstract

Methods, apparatuses, and systems directed to video hashing. Video hashing can be used to identify video content in a first video data file with video content of a second video data file. In a particular implementation, video matching or video content identification can be divided into two phases: Feature Extraction and Matching. During a feature extraction phase video material is analyzed and a video fingerprint is generated. The video fingerprint may comprise one video hash or multiple video hashes generated using different video hashing algorithms.

Claims

1. A method, comprising:

video hashing a first video data set comprising a first ordered time sequence of frames of a first video to generate a first fingerprint of the first video data set, the first fingerprint comprising one or more video hash values of the first video data set,

video hashing a second video data set comprising a second ordered time sequence of frames of a second video to generate a second fingerprint of the second video data set, the second fingerprint comprising one or more video hash values of the second video data set; and

comparing the first and second fingerprints of the first and second video data sets,

wherein the video hashing of a video data set that comprises an ordered time sequence of frames of video includes;

analyzing the video data set to identify one or more events in the ordered time sequence, an identified event comprising one or more of a change-of-motion-based event identified by detecting a change of motion in the sequence, a sub-sampling-based event determined by sub-sampling in time the ordered time sequence according to a pre-determined sampling profile, and a detected change-of-scene-based event; and

generating, for each identified event, one or more binary descriptors for one or more frames of the video data set that correspond to the identified event.

2. The method of claim 1 wherein analyzing the video data set comprises calculating global camera motion parameters for a plurality of frames of the video data set, and identifying frames corresponding to change-in-motion-based events including detecting change in motion using the global camera motion parameters calculated for the video data set.

3. The method of claim 1 wherein analyzing the video data set comprises sub-sampling in time the ordered time sequence according to a pre-determined sampling profile, such that the generating includes calculating binary descriptors for a plurality of frames of the first video data set corresponding to the sub-sampling.

4. The method of claim 1 wherein analyzing the video data set comprises identifying scene-cut events and frames corresponding to the scene-cut events by detecting changes of scene in the video data set.

5. The method of claim 1 wherein generating one or more binary descriptors for one or more frames of the video data set that correspond to an identified event comprises

dividing a video frame corresponding to the identified event into tiles;

calculating the average luminance for each tile; and

applying a global threshold across the tiles to form a binary word comprising a plurality of bits, wherein each bit corresponds to one of the tiles, and wherein a first bit value indicates an average luminance of the tile above the global threshold, while the opposite bit value to the first bit value indicates an average luminance of the tile below or equal to the global threshold.

6. The method of claim 1 wherein comparing the first and second fingerprints comprises correlating a first time line of events and a second time-line of events indicative of the times of identified events of the first and second fingerprints, respectively.

7. The method of claim 1 wherein comparing the first and second fingerprints comprises correlating a first time line of events and a second time line of events indicative of the times of identified events of the first and second fingerprints, respectively, matching identified events from the first time line to identified events of the second time line, and comparing binary descriptors corresponding to frames associated with the matched identified events.

8. The method of claim 1 wherein comparing the first and second fingerprints comprises generating a score characterizing a degree to which the first and second fingerprints match.

9. A non-transitory computer readable medium comprising computer-readable instructions operative, when executed, to cause one or more processors to:

video-hash a first video data set comprising a first ordered time sequence of frames of a first video to generate a first fingerprint of the first video data set, the first fingerprint comprising one or more video hash values of the first video data set;

video-hash a second video data set comprising a second ordered time sequence of frames of a second video to generate a second fingerprint of the second video data set, the second fingerprint comprising one or more video hash values of the second video data set; and

compare the first and second fingerprints of the first and second video data sets,

wherein the video hashing of a video data set that comprises an ordered time sequence of frames of video includes;

analyzing the video data set to identify one or more events in the ordered time sequence, an identified event comprising one or more of a change-of-motion-based event identified by detecting a change of motion in the sequence, a sub-sampling-based event determined by sub-sampling in time the ordered time sequence according to a pre-determined sampling profile, and a detected change-of-scene-based event; and

generating, for each identified event, one or more binary descriptors for one or more frames of the video data set that correspond to the identified event.

10. The non-transitory computer readable medium of claim 9 wherein analyzing the video data set comprises calculating global camera motion parameters for a plurality of frames of the video data set, and identifying frames corresponding to change-in-motion-based events including detecting change in motion using the global camera motion parameters calculated for the video data set.

11. The non-transitory computer readable medium of claim 9 wherein analyzing the video data set comprises sub-sampling in time the ordered time sequence according to a pre-determined sampling profile, such that the generating includes calculating binary descriptors for a plurality of frames of the first video data set corresponding to the sub-sampling.

12. The non-transitory computer readable medium of claim 9 wherein analyzing the video data set comprises identifying scene-cut events and frames corresponding to the scene-cut events by detecting changes of scene in the video data set.

13. The non-transitory computer readable medium of claim 11 wherein generating one or more binary descriptors for one or more frames of the video data set that correspond to an identified event comprises

dividing a video frame corresponding to the identified event into tiles;

calculating the average luminance for each tile; and

applying a global threshold across the tiles to form a binary word comprising a plurality of bits, wherein each bit corresponds to one of the tiles, and wherein a first bit value indicates an average luminance of the tile above the global threshold, while the opposite bit value to the first bit value indicates an average luminance of the tile below or equal to the global threshold.

14. The non-transitory computer readable medium of claim 9 wherein comparing the first and second fingerprints comprises correlating a first time line and a second time line indicative of the times of identified events of the first and second fingerprints, respectively.

15. The non-transitory computer readable medium of claim 9 wherein comparing the first and second fingerprints comprises correlating a first time line and a second time line indicative of the times of the identified events of the first and second fingerprints, respectively, matching identified events from the first time line to identified events of the second time line, and comparing binary descriptors corresponding to frames associated with the matched identified events.

16. The non-transitory computer readable medium of claim 9 wherein comparing the first and second fingerprints comprises generating a score characterizing a degree to which the first and second video fingerprints match.