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

Perceptual Image Hashing

bertolami.com

Post reply on HN
Print view View original

21–30 of 35 posts

Re: Perceptual Image Hashing

#21

Post by morsch »

elzr wrote: post #15

Hash functions impose practical mappings between unlike domains. When volatile (~1-to-1) identifying (crypto), when correlated (~n-to-n) perceiving (AI). (Tweet summary of the article. I'm becoming increasingly fascinated by hash functions. I'm finding all important this tension between abstraction/correlation/perception & groundedness/volatility/identification.) https://twitter.com/elzr/status/497893639000190976

That is a remarkable way to put it. But aren't has functions -- per definition -- n-to-1? That seems to be what the perceiving function is about: map multiple sensations into a single correlated perception.

Re: Perceptual Image Hashing

#22

Post by bcoates »

I've used this technique before for image searching, here's some tips:

The algorithm presented here can be summarized as "Take the low-frequency DCT components of the luminance channel, quantized down to one bit". Hashing is a very misleading term for what you get from it: In particular, it doesn't have anything like the uniform coverage of the output space you would expect from a hash function, as almost all encountered images exist in a very small range of hashes. Also, the bits in the hash are not all created equal; assuming you encode them in a zig-zag pattern truncation is equivalent to a low-pass filter, so if you want to make the hash different sizes while matching on the same image elements you'll want to alter the quantization amount, not the output DCT size (this is directly equivalent to what JPEG does, which uses a fixed DCT size but lossily quantizes the information in it to varying degrees for different compression quality settings). Experiment with different quantization techniques; you don't have to treat every bit in the output the same.

This technique is only suitable for a small subset of the image files that you will encounter in the real world: it's mostly unsuitable for anything but photographs and photograph-like images (3d renders, paintings, etc.) Many classes of image have no useful distinguishing information in the low-frequency luminance space, such as screenshots, pictures of text, line drawings, many forms of graph and diagram, most "clip art" style drawings, pictures that include layout elements in the image file (like most of the meme/sucessories/demotivator format pictures you'll see on imageboards). Of course, an image with a flat or heavily compressed luminance channel will yield no information at all.

You don't have to do anything special to match flipped images, as you should be using (iirc) DCT-II that has the same output for a mirror image. It's insensitive to scaling and mild translation.

For debugging purposes, note that the transformation performed is lossy but easily reversible: you can undo all the steps but quantization to generate a 'stereotype' image of a particular hash value and its neighbors. There is no more information available to the matching algorithm than you can see with your own eyes with the round-trip conversion, so if the round-tripped image preserves important distinguishing detail the matching will work and if it turns the image into a meaningless grey smear you'll get tons of false positive matches.

Re: Perceptual Image Hashing

#23

Post by elzr »

morsch wrote: post #21
elzr wrote: post #15

Hash functions impose practical mappings between unlike domains. When volatile (~1-to-1) identifying (crypto), when correlated (~n-to-n) perceiving (AI). (Tweet summary of the article. I'm becoming increasingly fascinated by hash functions. I'm finding all important this tension between abstraction/correlation/perception & groundedness/volatility/identification.) https://twitter.com/elzr/status/497893639000190976

That is a remarkable way to put it. But aren't has functions -- per definition -- n-to-1? That seems to be what the perceiving function is about: map multiple sensations into a single correlated perception.

Thanks for pointing it out, you're right! I rewrote the summary (the original is still at the linked tweet). So it's ~1-to-1 (usually, that's what I mean with practical) when it's volatile. And I'm calling it ~n-to-n (again, usually, practically) when it's correlated: mapping ~n correlations in the source domain to ~n correlations in the destination.

To my mind, an ~n-to-1 mapping would actually be a bit more like idealistic Platonic classifying than Wittgensteinian perception (~"we spin perceptual threads by twisting n attributes like fiber on fiber. And the strength of the thread does not reside in the fact that some 1 fiber runs through its whole length, but in the overlapping of the fibers.").

What do you think? :)

Re: Perceptual Image Hashing

#24

Post by andreasvc »

vitovito wrote: post #12
daveloyall wrote: post #6

Does the term "perceptual hashing" only apply to the domain of images? What would you call this concept applied to text files? I am familiar with Levenshtein distance, but that family of algorithms provide a similarity score or value whereas I'd like a hash as the output.

What would you be hashing, on a text file? What the text "looks like," e.g. particular density and repeated patterns of alphanumerics? Or would you be hashing the content, the language, the words used, the meaning of the words? Stylometry is the study of written style. It's used forensically to see if two texts were written the same, to identify anonymous/pseudonymous authors, and there's "adversarial stylometry," wh…

In text analysis you can broadly focus either on style or on topic. Stylometry does the former and typically focuses on highly frequent function words; this technique is good at identifying authors. There are various techniques that focus on topics such as distributional semantic models and bag-of-word models; these techniques are good at clustering documents about the same topics together (regardless of author style). I think that in both cases a text can be reduced by the model to a single vector, which could be considered a hash, but in the end what matters is how well the models perform on a task such as identifying authors or finding documents on a given topic.

Re: Perceptual Image Hashing

#25

Post by bcoates »

TheLoneWolfling wrote: post #9

How would an adversary break this? My first idea would be to rotate it by something that's halfway between the steps used. Say, 360/32 degrees. How does that compare? Also: because it discards the high frequency data one should be able to construct something like this: http://cvcl.mit.edu/hybrid/CatDogHybrid.jpg - where to us at a close distance it looks like one thing but to this it looks like something else.

It would be pretty easy to assign any image an arbitrary value. Compare the image's current (unquantized) DCT values to the desired ones, find the value that differs from the target but is closest to being quantized as the desired bit, and apply a filter that just barely flips it. Each time you do this you reduce the Hamming distance score between the image and the target by 1.

If getting close enough results in unsightly blotches on the image, reduce the power of the low frequency luminance channel across the board, which will mask the changes by making the unmodified high frequency components more noticeable. That looks like what's being done in the catdog image, at least.

You could increase the saturation as well, as this fingerprinting system ignores color.

Re: Perceptual Image Hashing

#26

Post by ma2rten »

daveloyall wrote: post #6

Does the term "perceptual hashing" only apply to the domain of images? What would you call this concept applied to text files? I am familiar with Levenshtein distance, but that family of algorithms provide a similarity score or value whereas I'd like a hash as the output.

Yes, such a thing exists for text files: There are techniques used for near-duplicate detection (MinHash), and then there are latent topic models (e.g. using lda, lsi, autoencoders) which map documents onto a lower-dimensional ("semantic") space which is supposed to give a similar representation to semantically similar documents.

Re: Perceptual Image Hashing

#27

Post by opless »

ahknight wrote: post #18
667 wrote: post #16

Earlier quoted context omitted.

But I actually want to know what I'm missing-- what's interesting about this "closed source but available for academic purposes" application which appears to simply be a re-implementation of existing work? I'm trying to give benefit of the doubt here actually.

It's using a very similar technique to pHash, actually. DCT-based hash and all. It's not brand new, but perhaps a variation on a theme. I've actually been working in this domain for the last week or so and DCT-based hashes are quite accurate, but slow as hell. Average hashes (aHash) or Delta Hashes (dHash) are much faster and rather good at weeding out large numbers of images. A mix of ideas is usually a good idea.

Yup, it's been shown that the accuracy of a set of poor classifiers together can be greater than a known 'good' classifier.

The implication is that there's no single 'perfect' classifier for a problem, engineers have used this notion for many years having multiple systems vote for fail-proof operations.

Re: Perceptual Image Hashing

#28

Post by wisty »

daveloyall wrote: post #17
vitovito wrote: post #12

Earlier quoted context omitted.

What would you be hashing, on a text file? What the text "looks like," e.g. particular density and repeated patterns of alphanumerics? Or would you be hashing the content, the language, the words used, the meaning of the words? Stylometry is the study of written style. It's used forensically to see if two texts were written the same, to identify anonymous/pseudonymous authors, and there's "adversarial stylometry," wh…

Hm. Well, I want to hash the pattern of bits in the text file, like a cryptographic hash does (suppose md5 or sha-1 for simplicity's sake). I'll provide some examples of input and output. These examples happen to contain no linefeeds. Suppose: Hello, World! --> 65a8e27d8879283831b664bd8b7f0ad4 Then I want something like: Hello, Worlds! --> 65a8e27d8879283831b664bd8b7f4ad4 ...Rather than what md5 currently provides: H…

Yes, that's possible. You could a topic clustering algorithm, for example.

Text -> topic_id.

Re: Perceptual Image Hashing

#29

Post by petercooper »

If this sort of thing fascinates you, here's a related approach: http://grail.cs.washington.edu/projects/query/ .. for some reason numerous people were working on image search features like this (i.e. draw what you want to find) 10 years ago but they don't seem to have caught on other than with Google Images.

Re: Perceptual Image Hashing

#30

Post by petercooper »

daveloyall wrote: post #17
vitovito wrote: post #12

Earlier quoted context omitted.

What would you be hashing, on a text file? What the text "looks like," e.g. particular density and repeated patterns of alphanumerics? Or would you be hashing the content, the language, the words used, the meaning of the words? Stylometry is the study of written style. It's used forensically to see if two texts were written the same, to identify anonymous/pseudonymous authors, and there's "adversarial stylometry," wh…

Hm. Well, I want to hash the pattern of bits in the text file, like a cryptographic hash does (suppose md5 or sha-1 for simplicity's sake). I'll provide some examples of input and output. These examples happen to contain no linefeeds. Suppose: Hello, World! --> 65a8e27d8879283831b664bd8b7f0ad4 Then I want something like: Hello, Worlds! --> 65a8e27d8879283831b664bd8b7f4ad4 ...Rather than what md5 currently provides: H…

Perhaps I'm missing the point, but I came up with a naive and sloppy part solution: https://gist.github.com/peterc/737d9178f02118f8e315 .. there are some weaknesses to this solution but it does perform similarly to your examples.
Post reply on HN