Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How Perceptual Hashes Work

hackerfactor.com

Post reply on HN
Print view View original

61–70 of 77 posts

Re: How Perceptual Hashes Work

#61

Post by bct »

killerswan wrote: post #51
wickedchicken wrote: post #18

Earlier quoted context omitted.

This is pretty much the opposite from what the article is talking about -- the article is trying to get a hash from an image in order to compare that image to another, while you're talking about synthesizing an image from an arbitrary hash...

Well, one could use a variation of this technique to compare tons of other things... Music?

http://musicbrainz.org/doc/Audio_Fingerprint

The Picard MP3 tagger uses this kind of thing (and MusicBrainz' database of tracks and audio fingerprints) to identify files.

Re: How Perceptual Hashes Work

#62

Post by tsewlliw »

zackattack wrote: post #58
tsewlliw wrote: post #12

That is completely brilliant! I want to go out and write a image diff viewer that uses this on blobs in the image to detect pieces moving around!

I don't understand? :)

so you have a before and after image, say a webpage mockup thats where the logo moved from top left to top right.

the blob finder finds the interesting pieces of each version, and the perceptual hash picks which blobs match each other, and the software can say with reasonable certainty that the top left part of the image was moved to top right.

don't eat my lunch :)

Re: How Perceptual Hashes Work

#63

Post by CountHackulus »

This is really interesting, but I'm sad that they skip over the step "convert to grayscale." There's a ton of ways to convert an image to grayscale, each with their own pros and cons.

How do you weight each channel? Do you convert to HSL and just use L? Do you instead use Lab? HSV? Do you do a global or local algorithm? So many questions!

Re: How Perceptual Hashes Work

#64

Post by kenjackson »

thesz wrote: post #50
kenjackson wrote: post #25

Earlier quoted context omitted.

For pop/rock/rap music it probably doesn't matter. For classical, I'm not sure.

I think you just suggested that classical music is all the same.

I meant to suggest the near opposite. That with pop/rock/rap, a 10s chunk is enough to get a signature for the wole piece. While for classical, the music changes enough that any 10s chunk may not respesent adequately a different 10s chunk.

Re: How Perceptual Hashes Work

#65

Post by iandanforth »

mjb wrote: post #45
stevetjoa wrote: post #36

Earlier quoted context omitted.

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 bot…

The key thing here is that compressed sensing is an attempt to throw away redundant data as early as possible in the process. Any data which is redundant in the actual data stream, or can be inferred from prior knowledge about the stream does not need to be measured. Perceptual hashing is instead an attempt to make the matching problem easier by throwing away data that is seen as irrelevant. In the case of the descri…

If we take the principles from compressed sensing and use a random-lens approach to subsampling the original image, we can create a fingerprint of the image which also happens to be able to reconstruct the original.

Both techniques are compressions that rely on the sparse properties of images to devine which bits are meaningful and which are redundant. It appears to me that using compressed sensing is just a smarter way of doing it. Maybe a hash that starts with a random subsample is inherently slower for comparing millions of images, but I shouldn't think so.

Re: How Perceptual Hashes Work

#66

Post by gbog »

zackattack wrote: post #55
noblethrasher wrote: post #37

Earlier quoted context omitted.

Thanks, that is a bit more helpful.

another way i like to think of it (someone please correct me if i'm wrong) is that high-frequency means high-detail (highly frequently needing information to specify how it looks) whereas low-frequency means low-detail (is that completely off or is it an analogous transform?)

What is misleading when one talk about Fourier transform for pictures, is that it has nothing to do with the waves emitted by the colored particles and received by our eyes. It is more about the spatial distribution of intensities.

Applied to the sound, this "frequency view" is much more natural: we hear a sound, and there is a low and a high part of it. It's because our ears really do real time frequency analysis, a kind of biological Fast Fourier transform.

From what I remember, doing this transformation is just a matter of taking the original signal s, get its level n of the lowest frequency f, and compute s - n × f, and recurse on the result with the next frequency. The theorem proves that if you go to the limit you get two equivalent representations of the signal, one being the wave itself s = f(t), one being its "spectrum" s1 = f(freq) (a function of the frequencies).

For many purposes, f(freq) is much more convenient than f(t), including comparisons, frequency shifting, extraction, compression, etc.

It applies equally well to images, but for me the frequency representation of a picture is not perceptively useful, maybe because our eyes are not Fourier transforming what we see.

All that is's old story for me (I studied acoustics in IRCAM), please correct if my memory is wrong.

Re: How Perceptual Hashes Work

#67

Post by sigil »

_delirium wrote: post #48
sigil wrote: post #43

Earlier quoted context omitted.

I went to a talk by Yann LeCun [1] a few months back, "Learning Feature Hierarchies for Vision." The current state of the art in this field is mind-blowing to an outsider. The final demo was a program that he trained in a matter of seconds to recognize and distinguish faces of various random audience members, in real time, from different viewing angles. [1] http://yann.lecun.com/

Is any of that software available?

Some of the libraries are [1]. Probably not the whole kit and caboodle. Interestingly, there was a focus on special purpose hardware that made convolutional network learning possible in realtime. One of the other demos was an autonomous driving robot that learned to recognize obstacles in video. Again, just mind-blowing.

[1] http://www.cs.nyu.edu/~yann/software/index.html

Re: How Perceptual Hashes Work

#68

Post by NickC_dev »

pavel_lishin wrote: post #40
NickC_dev wrote: post #26

There's a publicly available implementation of a perceptual hashing algorithm called phash at http://phash.org . I use some of their c++ code to detect reposts on an image sharing site I run ( http://lolstack.com ).

Could you add RSS?

It's definitely on my summer to-do list. You're the first person to ask.

Re: How Perceptual Hashes Work

#69

Post by starkdg »

stevetjoa wrote: post #28
seanalltogether wrote: post #21

I've always wondered how services like Shazam work. I'm amazed that they can do this kind of perceptual hash against ANY 10 second portion of a song. How do they search against something like that when they don't know the start or end time of the segment that is being input?

I do research in music information retrieval. See the ISMIR 2003 paper below. In short, it searches for landmarks in the spectrogram, hashes those landmarks, then compares those hashes against database hashes for temporal continuity. http://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf A seminal paper on audio fingerprinting is the one by Haitsma and Kalker. http://ismir2002.ismir.net/proceedings/02-fp04-2.pdf

There's a gpl implementation of an audio information retrieval approach here: http://code.google.comp/audioscout/

Re: How Perceptual Hashes Work

#70

Post by wickedchicken »

brudgers wrote: post #60
wickedchicken wrote: post #17

The two main problems with this approach is it is not rotation-invariant and it does not work well if the image is damaged or added to. A more robust system (that, admittedly, will take longer) is to use one of the affine-invariant feature detection algorithms pioneered by SIFT. SURF is a faster, open-sourced version of SIFT that has many implementations. Essentially it scans chunks of the image at different scales a…

How serious a problem is non-rotational invariance given the purposes for which Tineye may be using perceptual hashing? In Tineye's data set, wouldn't rotational issues tend to be edge cases since the vast majority of images on the web are already properly oriented? And given that most of the edge cases are likely to involve 90, 180 or 270 degrees of rotation, the additional computational requirements to cover those…

The difference is that you're throwing ad-hoc enhancements on top of an underlying framework which can't be modified beyond its basic principle. Yes, if you are looking for exact or simply scaled duplicates on other websites, a vector search for downsampled images would work ok. However, SIFT/SURF has a much more principled approach that can can be extended to handle more cases "when you need it." It's the difference between hand-writing HTML and using a template engine. On one scale, of course it makes sense to just copy and paste some HTML. But as things get hairier over time, you have to switch to something more powerful.
Post reply on HN