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

11–20 of 77 posts

Re: How Perceptual Hashes Work

#11

Post by cdavid »

barrkel wrote: post #5
michaeldhopkins wrote: post #2

Thank you, I learned something. Since TinEye pre-computes the hashes, do they use something like Redis to retrieve information? Redis seems perfect for a such quick results using the hash as the key and a URL or object of some kind as the value.

It seems to me that what you want is some kind of spatial index - you might not get an exact match on the hash, but instead get one that's one or two bits away, and you'll want something better than linear search to find it.

That would be a good idea as along as you have a good distance between images (d(image1, image2) small equivalent to image1 and image2 are equivalent). I have little experience in image processing, but this is generally a hard problem with complex signals (as images, music and speech are).

Most of what is described in the article concerns dimension reduction, where the goal overlaps with the above.

Re: How Perceptual Hashes Work

#13

Post by gsmaverick »

andrewflnr wrote: post #4

Wow, I had no idea it was so easy. Could this in fact be used to combat copyright infringement for the likes of The Oatmeal on large scale, given someone (Google) with the requisite computing power?

From the looks of it this is actually TinEye's main commercial activity, they merely expose the search interface to demonstrate their technology.

Re: How Perceptual Hashes Work

#14

Post by barrkel »

cdavid wrote: post #11
barrkel wrote: post #5

Earlier quoted context omitted.

It seems to me that what you want is some kind of spatial index - you might not get an exact match on the hash, but instead get one that's one or two bits away, and you'll want something better than linear search to find it.

That would be a good idea as along as you have a good distance between images (d(image1, image2) small equivalent to image1 and image2 are equivalent). I have little experience in image processing, but this is generally a hard problem with complex signals (as images, music and speech are). Most of what is described in the article concerns dimension reduction, where the goal overlaps with the above.

The article explicitly mentions Hamming distance, which is also what I mean by bit distance.

Re: How Perceptual Hashes Work

#15

Post by jamii »

barrkel wrote: post #5
michaeldhopkins wrote: post #2

Thank you, I learned something. Since TinEye pre-computes the hashes, do they use something like Redis to retrieve information? Redis seems perfect for a such quick results using the hash as the key and a URL or object of some kind as the value.

It seems to me that what you want is some kind of spatial index - you might not get an exact match on the hash, but instead get one that's one or two bits away, and you'll want something better than linear search to find it.

Here is a good overview of existing approaches to approximate sequence matching - http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.96.... . I also wrote in a fair bit of detail about solving the similar problem of searching through LaTeX syntax trees - http://scattered-thoughts.net/one/1291/799313/731344 . Adapting my code to searching by Hamming distance should be trivial should anyone want to play around with image searches.

Re: How Perceptual Hashes Work

#16

Post by piotrSikora »

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=200806150... (2008/06/26).

Re: How Perceptual Hashes Work

#17

Post by wickedchicken »

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 and identifies features that peak even as the chunk around it gets bigger. Once these are identified, they are described in a way forcing them to the same size and orientation for lookup. Since these features should presumably be scattered throughout the image, the image can be recognized even if certain features are obscured or modified. It's certainly not as straight-forward as a DCT metric on a downsampled image, but the nature of widespread image capture, creation and manipulation usually requires this robustness.

Re: How Perceptual Hashes Work

#18

Post by wickedchicken »

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...

Re: How Perceptual Hashes Work

#19

Post by wickedchicken »

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…

As a followup (and this is rather unrelated to the original post), you can combine a feature detector with a statistical clustering algorithm to automatically identify the generic visual properties of objects in an unsupervised manner. One of the first papers attempting this is http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.... but many have followed it. From what I understand these still simply check for the existence of features in an image instead of their spatial relationship ('a picture of a cat has two ears, a tail, and a blob for a body' versus 'a picture of a cat has two ears positioned on the end of a blob with a tail on the other end of the blob'). Nevertheless, they represent the current state-of-the-art in automatic object classification and recognition algorithms.
Post reply on HN