How Perceptual Hashes Work

Yes, but his remarks suggests that hamming distance is not very nice for pictures after his transformation (d(i1, i2) == 5 -> small, d(i1, i2) == 10 -> big). As I am not familiar with image signals, I don't know if this can be somehow mitigated with other techniques. Of course, the only way to be sure would be to actually test it, but I would not bet much on it.

Another issue I forgot to mention is that each "point" (image ) is a k-dimensional vector. Organizing those so that to easily retrieve points which are close to each other quickly becomes intractable. Conventional techniques like kd-trees quickly break down when k is above a few units, because of the curse of dimensionality. This introduces a "non-linearity" in your distance which makes comparing points in a k-dimension space quite different than in 2/3 dimension spaces.

If you're interested in this article, then you may interested in locality sensitive hashing (LSH), a randomized hash that has been used seemingly everywhere. I recently used it to speed up music source separation (papers pending).

The idea is similar to the one mentioned in this article, but more general. Unlike a cryptographically secure hash where x != y implies that h(x) != h(y) (collisions aside), LSH says that if x and y are "near", then P(h(x) = h(y)) is "high". This quality is important when doing robust similarity search. For example, if your image is noisy or rotated or scaled, you hope that you can still find the clean version in a database.

LSH has been used in many application domains including images, video, music, text, bioinformatics, and more. LSH is not directly comparable to a feature extraction algorithm such as SIFT.

[Edited for clarity.]

Kinda sorta not really. Compressed sensing and sparse coding show that, under certain sparsity assumptions, you can perfectly reconstruct your original data with fewer bits than previously thought. It is a coding principle.

Perceptual hashes (or hashes in general) are used for fast indexing and retrieval. You cannot recreate the original data from a hash, pretty much by definition.

So hashes and coding algorithms both provide smaller representations of data. But hashes are used for indexing and do not provide the original data, or even an approximation thereof, while compressed sensing can.

In short, a wave with a high frequency has a short wavelength, and vice-versa.

The Discrete Cosine Transform is a variant of a 2-dimensional Fourier Transform. The 1-D version of a Fourier Transform is what we use to break a signal, like a sound wave, into its constituent frequencies. It takes as input the wave amplitude at various times, and returns amplitudes for various frequencies. If you were to take waves of those frequencies and amplitudes, and add them together, you would get back the original sound wave you started with. (I'm hand-waving away a bunch of details like phase, boundary conditions, undersampling, and overtones--but this is the general idea.)

You can make the Fourier Transform and its relatives deal with images the same way as sound, by pretending that the image is periodic, i.e. that you are tiling an infinite wall with copies of that image. You could create this same wall by overlaying waves of color on top of each other. The Fourier Transform will find these waves, the same way it found the frequencies for the sound.

With sound, low frequency = slow vibration = long wavelength (imagine an oscilliscope). High frequency = rapid vibration = short wavelengths. So if you were to try yo draw a picture using waves instead of a brush, you would use low frequencies for large things like a head. You would use medium frequencies to add smaller objects like eyes. You would use high frequencies to give small details, like hair or freckles, or the specific shape of a specific person's head.

Could you add RSS?