Hashing a video file

Question

Bit of a long post, but this is a complex topic:

I want to hash of a series of video files so that they can be quickly checked for duplication. I know that any amount of data can be reduced to a hash, but I'd like to do this in a way that is:

• Format independent, i.e. not a binary hash, but one based on what you see
• Resolution independent - aspect ratio notwithstanding
• Offset independent - this is the tricky part

So far this is what I've got:

• I use handbrake to extract still images from a video stream - this makes an FLV come out the same as an MP4
• I wrote some code that will blur (nearest neighbor) the image into a smaller one, e.g. 640x480 => 64x48. It then reduces the colors to a smaller palate. This eliminates minor differences in aspect ratio and small pixel differences due to different codecs/bitrates.
• Some more code that will hash that image into a 128-bit byte array. These can be stored in a database and compared very efficiently

Where I'm really stuck is the offset. If video A and video B are the "same" video, but B is missing the first 2 seconds, or has additional minute/hour/etc. of footage, the whole thing is off; hashes either match or they don't. In fact, I might even have issues with my sampling rate in handbrake as I don't totally understand key-frames - I'm just taking X frames per second.

So what I'd like is some way to sample sections of the video, and store many hashes per video file, and if any hashes from A match any hashes from B, do further analysis.

I figure this must be possible because of the way SoundHound and Shazaam work on music. Does anyone have insight into this?

Answer 1

Extracting one single hash per video and expecting it to work for subsegment matching is unrealistic.

The approach - which is the one used in audio identification systems but could be extended to video - is to extract many hashes, one for each small segment of content (say a few seconds of video). The matching process consists in matching your "query" sequence of hashes to the sequence of hashes extracted from your video. This is quite similar to a text indexing/retrieval problem, and traditional data structure for such problems (like inverted indices) would work. You can probably build your implementation on top of an existing text indexing system like Lucene/Solr. See for example, the echoprint server code, built on Solr.

This addresses the sequence aspect. Remains the problem of generating robust hashes for images. What you are doing is probably going to still be sensitive to minor differences in compression/resolution - You'll need a very rough quantization of a small number of DCT / wavelet coefficients for it to be robust.