Neal Krawetz wrote an interesting article on image fingerprinting, or how to search for images that are similar. He proposes an algorithm to do image fingerprinting and reproduce the functionality of TinEye, a service that allows to give one image and get back all the web pages where that picture, or a slightly modified version of it, is included. By resizing the image to 8×8 pixels, creating a B/W version, and then a binary (only black or white pixels, no grey levels), he reduces a picture to a hash that is 8 x 8 = 64 bits. This can then be compared to a database of hashes of millions of other pictures found on the web (by calculating the “Hamming distance” – read the article for details).
On the other hand, something similar can be done on segments of audio. Youtube has been doing it for years (using technology from Audible Magic) and recently the Echo Next has released Echo Print, a music fingerprint and identification service that does the same thing for free.
Since I work (and play) a lot with video, I was thinking about how to extend the ideas Neal proposes to video. Video material consists of audio (which I will ignore for now) and a sequence of images (typically between 24 and 30 per second). I’ve taken a video clip from Youtube as inspiration, but I won’t tell you yet which one, let’s discover it while I create the fingerprint of 1 of the frames, using the method described by Neal:
|first we reduce the frame to a small format, e.g. 16×8 pixels|
|then we desaturate: make the picture grayscale|
|then we normalize it: we maximize the contrast, the darkest pixel become the new black, the lightest becomes the new white|
|we calculate the average darkness and any pixel that is darker we make black, and the others become white -this is what is proposed in the article. Total size of fingerprint: 16 pix * 8 pix * 1 bit = 96 bits = 16 bytes|
|I found the details in the above fingerprint too coarse, so I used 4 color levels instead of 2. Total size of fingerprint = 16 pix * 8 pix * 2 bits = 32 bytes|