Fucking around with perceptual hashes
Introduction
TODO: why this project exists, the master's thesis that wasn't, discovering pHash after the fact.
TODO: the rules of the game: 64 bits per image, hamming distance, nothing else.
Perceptual hashing
TODO: cryptographic hash vs perceptual hash. One flipped pixel: md5 avalanches, a perceptual hash shrugs.
Terminology
TODO: descriptor / fingerprint / perceptual hash / signature all mean roughly the same thing depending on which corner of the literature you are standing in. Copy detection vs near-duplicate detection vs LSH.
Subjective image similarity
TODO: what "the same image" even means. Same pixels? Same scene? Same vibe?
Demo
Select an image to run this demo with. Don't worry, nothing will be sent to any server! All calculations are done in the browser.
Unanimated images with no transparancy work best, but feel free to experiment.
or pick a sample:Step 1: Resize
The first step is to size the image down, and remove all color information. Converting the image to grayscale is done by simply averaging the pixels. Since we are aiming for a 64-bit descriptor, the logical target size is 8 by 8 since that will give us 64 pixels to work with.
It is obvious, but worth noting, that this action is destructive. We are throwing away a lot of information here, especially regarding the finer details. For now, this is a good thing.
Here we use a nearest neighbour downscaling algorithm that does not preserve aspect ratio.
Press the button to resize your image:
Step 2: The simplest hash that could possibly work
TODO: median hash: one bit per pixel, brighter than the median or not. This is the "Median" baseline from Thomee et al.
Bits
Hash
TODO: why this breaks: global median shifts, flips scramble everything. Foreshadow the moon/plate anecdote.
Step 3: Frequency space
TODO: what the DCT does. JPEG uses the same trick. Low frequencies = global shape, high frequencies = detail we already threw away.
DCT coefficients
TODO: reading the coefficient grid: top-left is the average, first row is horizontal waves, first column vertical waves.
From coefficients to bits
TODO: sign bits of the first 36 zigzag coefficients + 28 ordinal comparisons between neighbours in zigzag order. The odd-column signs get multiplied by the sign of coefficient (1,0), which buys horizontal flip invariance for one bit.
Sign mask (36)
Ordinal mask (28)
Hash
Step 4: How pHash does it
TODO: same idea, different route: resize to 32x32 instead of 8x8, DCT, keep the top-left 8x8 block of low frequencies, threshold against the median coefficient.
32×32
Low-frequency block
Bits
Hash
TODO: what's genuinely different between our dct hash and phash (bit extraction, flip invariance) and what isn't (everything else).
Mutations
TODO: a copy is rarely byte-identical. Recoding, resampling, content processing, framing, inserted logos (the Thomee et al. taxonomy). Sweep the slider and watch which hash survives what.
| dct | median | phash | |
|---|---|---|---|
| hamming distance |
TODO: what counts as "the same" now? Thresholds. pHash uses 22 of 64 bits, we will measure our own.
Find the copy
TODO: the fun part: a tiny search engine. Add a pile of images, click one, get the nearest neighbours per algorithm. Mention the white plate that matched the moon.
Results
At scale
TODO: the browser demo is anecdote, this section is data. 25k images, 16 mutations each, precision-recall over the hamming threshold.
TODO: how the PR curves are computed, what a false positive means here, where the thresholds land per algorithm.
Loose ends
TODO: vertical flips and 180 rotations (same trick, one more bit). Coefficient stability near zero. Video: keyframes vs temporally averaged frames vs 3D-DCT. The seen-images daemon idea. Sorting a folder by visual similarity.