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

51–60 of 77 posts

Re: How Perceptual Hashes Work

#51

Post by killerswan »

wickedchicken wrote: post #18
piotrSikora wrote: post #16

This reminds me of OpenSSH's fingerprint visualization support ("VisualHostKey yes"): $ ssh A.B.C.D Host key fingerprint is b0:c9:c9:96:fb:fd:ac:a4:ff:70:8f:1b:35:f4:f9:2e +--[ECDSA 256]---+ | | | | | . . | | o * . ..| | O S o..| | . . . ..| | . o o .| | . + + +E. | | o.++*....| +-----------------+ me@A.B.C.D's password: Original article introducing this feature: http://www.undeadly.org/cgi?action=article&sid=2008061…

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?

Re: How Perceptual Hashes Work

#52

Post by killerswan »

noblethrasher wrote: post #24

"With pictures, high frequencies give you detail, while low frequencies show you structure." I have a vague idea of what this means but can someone please explain it in a bit more detail?

Also, the DCT is what is used for JPEG, so maybe that helps you think about this a bit more intuitively: http://en.wikipedia.org/wiki/JPEG

Re: How Perceptual Hashes Work

#53

Post by eru »

neworbit wrote: post #46
piotrSikora wrote: post #16

This reminds me of OpenSSH's fingerprint visualization support ("VisualHostKey yes"): $ ssh A.B.C.D Host key fingerprint is b0:c9:c9:96:fb:fd:ac:a4:ff:70:8f:1b:35:f4:f9:2e +--[ECDSA 256]---+ | | | | | . . | | o * . ..| | O S o..| | . . . ..| | . o o .| | . + + +E. | | o.++*....| +-----------------+ me@A.B.C.D's password: Original article introducing this feature: http://www.undeadly.org/cgi?action=article&sid=2008061…

I can't be the only one who thinks "This looks like the visualization algorithm is nethack"

Plane of fire, or so.

Re: How Perceptual Hashes Work

#54

Post by zackattack »

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?

There was a cool HN article a while back on building your own Shazam clone in Java.. I think the author received a C&D..

Found it! http://www.redcode.nl/blog/2010/06/creating-shazam-in-java/

Re: How Perceptual Hashes Work

#55

Post by zackattack »

noblethrasher wrote: post #37
joshu wrote: post #33

Earlier quoted context omitted.

Ok, I'll take a shot at this. Let's work in one dimension rather than two dimensions. It's easy enough to extend later. You know that a any signal is the sum of a (potentially infinite) number of sine waves. For example, a square wave is the sum of ever higher-frequency (but smaller-amplitude) sine waves. The higher frequencies are necessary to get the sharp edges. If you strip the high frequencies, the sharp edges d…

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?)

Re: How Perceptual Hashes Work

#56

Post by zackattack »

I don't understand why compressing an image is going to generate the same 8x8 image each time no matter what aspect ratio it was originally... whether it has been stretched before.. If you stretch and then recompress a bunch of times don't you eventually lose the information?

That math is for some reason totally counter-intuitive to me. Could someone do a proof?

Re: How Perceptual Hashes Work

#57

Post by icegreentea »

buddydvd wrote: post #29

Isn't tineye's signature algorithm based on Fourier transform? http://www.reddit.com/r/programming/comments/bvmln/how_does_...

As the post notes, that algorithm is great at matching, but sucks at searching. Hashes on the other hand are probably better off at matching. My guess is that you use some variation of hashing to get a set of candidate images, and then do more detailed examinations.

Re: How Perceptual Hashes Work

#59

Post by bryanh »

zackattack wrote: post #56

I don't understand why compressing an image is going to generate the same 8x8 image each time no matter what aspect ratio it was originally... whether it has been stretched before.. If you stretch and then recompress a bunch of times don't you eventually lose the information? That math is for some reason totally counter-intuitive to me. Could someone do a proof?

From my understanding, its not a md5 hash or equivalent. Its just encoding the 64 bits to a "hash" thus allowing a fuzzy comparison between hashes. Someone correct me if I am wrong.

Obviously, this isn't robust enough to find all matches. A simple cropping would throw it completely off.

Re: How Perceptual Hashes Work

#60

Post by brudgers »

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 would appear to be significantly less than required for true non-translational calculation - i.e. wouldn't rotating the low frequency image 90 degrees and generating a second hash + creating reverse order hashes of the original and second hash work?

It seems to me that for applications such as cryptography where the costs of false positives are high, a SIFT algorithm makes sense. But for a free consumer oriented search tool, might it be considered overkill?

Link to SIFT: http://en.wikipedia.org/wiki/Scale-invariant_feature_transfo...

Post reply on HN