Hashes are supposed to change a lot with small changes in the data source. I wouldn't call this hashing, but fingerprinting, and there're plenty of fingerprinting algorithms for images, some related to steganography.
Perceptual Image Hashing
11–20 of 35 posts
Re: Perceptual Image Hashing
#12Does 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," which is intentionally changing a writing style to make it look like someone else wrote something.
This deck seems to summarize a lot of these points and issues, but offers no "stylometric hash" solution: http://wiki.uni.lu/mine/docs/RDPresentation.ppt
Plagiarism detection is another forum that might do these sorts of analyses. How many metaphors do you have to change, and synonyms do you have to replace, before it's an original work, or would it always still hash nearby?
Textometry tries to make texts more analyzable. Wordprints or stylometric fingerprints, seem to turn up more results than "hash".
Re: Perceptual Image Hashing
#13Also look at Semantic Hashing, which uses deep learning to compress an input (e.g. a document) into a low dimensional bit vector with fast lookup:
http://www.cs.toronto.edu/~rsalakhu/papers/semantic_final.pd...
The idea is that you could hash one billion objects, and do a very fast lookup of similar objects.
There is later academic work that refines this approach. For example, here is work applying it to image search: http://www.cs.utexas.edu/~grauman/temp/GraumanFergus_Hashing...
You can consider this a variant of Locality-Sensitive Hashing, where the hash function is specifically induced through a machine learning technique.
Re: Perceptual Image Hashing
#14This seems to work well for modifications that are basically in-place and high frequency, but how well does it handle things like one image being a crop of another, or translation, or flipping?
Re: Perceptual Image Hashing
#15Hash 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.)
Re: Perceptual Image Hashing
#16Is it different from existing implementations? Am I missing something? http://phash.org/ http://hzqtc.github.io/2013/04/image-duplication-detection.h... http://www.hackerfactor.com/blog/?/archives/432-Looks-Like-I...
A more tactful question might be, "How is it different from existing implementations?" And then don't ask "Am I missing something?" Best practices for engineering is always to see what else is out there, so to assume the author hasn't conducted a review of the field might be read as rudeness or snark. Many developers, even when they do compare and contrast their own work as they develop it, don't write up the results…
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.
Re: Perceptual Image Hashing
#17Does 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…
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
Hello, Worlds! --> 65a8e27d8879283831b664bd8b7f4ad4
Hello, Worlds! --> d0478649ad1c15f0e623846c3e26ebeb
Said differently: I'd like a hashing algorithm where the Levenshtein distance between any given two outputs correlates with the Levenshtein distance between the corresponding inputs.
I can imagine lots of uses for such a tool. ...But I can't imagine how it could be possible to make one: files (or strings) vary in length, for one thing, but a good hash does not! Of course, I couldn't imagine md5 before I saw it in action, either.
Re: Perceptual Image Hashing
#18Earlier quoted context omitted.
A more tactful question might be, "How is it different from existing implementations?" And then don't ask "Am I missing something?" Best practices for engineering is always to see what else is out there, so to assume the author hasn't conducted a review of the field might be read as rudeness or snark. Many developers, even when they do compare and contrast their own work as they develop it, don't write up the results…
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.
Re: Perceptual Image Hashing
#19Hashes are supposed to change a lot with small changes in the data source. I wouldn't call this hashing, but fingerprinting, and there're plenty of fingerprinting algorithms for images, some related to steganography.
A cryptographic hash, yes. Not all hashes are cryptographic hashes.
Re: Perceptual Image Hashing
#20Very interesting approach. I have worked with image feature extraction in the past. Although using DCT coefficients has been used as a way to analyze texture features, the idea idea of generating the hash (step 5) seems to be new. I am curious however on why you are discarding color information. Usually for reverse image search this kind of information can be quite useful.
Not new. pHash (phash.org) has been doing it for a while now. :)