What a fascinating topic, it's too bad that Gazopa (mentioned at the end of the article) just announced that they're shutting down their CBIR service:
http://gazopablog.blogspot.com/2011/05/shut-down-notice-from...
How Perceptual Hashes Work
71–77 of 77 posts
Re: How Perceptual Hashes Work
#72I have a feeling there is a deep connection between perceptual hashes and compressed sensing. Could someone more familiar with the latter weigh in?
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…
Just an interesting note, from implementation perspective, random projection is used for both cases (LSH or CS).
Re: How Perceptual Hashes Work
#73This 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!
It was my understanding that (for a lot of the steps) it does not matter what mechanism you use, so long as you use the same one.
The problem you are addressing would matter if someone were trying to query TinyEye's database without submitting the image to TinyEye's servers.
Re: How Perceptual Hashes Work
#74Earlier quoted context omitted.
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…
>approach that can can be extended to handle more cases "when you need it."
I guess my take on TinEye is that cases "when you need it" may be cases outside their target current market segment. Getting people to use their service is probably more important than using a sophisticated algorithm.
Re: How Perceptual Hashes Work
#75Earlier quoted context omitted.
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…
I agree. Briefly looking at the description of it, it is some sort of compressed sensing. The differences from traditional CS are minimal in fact, but the scheme is in line with some of the work undertaken in manifold signal processing. The differences are:
- the proposed hash is deterministic, generally in CS, you want to rely on random projections (yet there are some results for deterministic problems) in order to get some sort of universality and by the same token some sort of robustness.
- step 3 and 4, are the most fascinating steps because they are clearly one of the approaches used in manifold signal processing for images. To summarize, in order for pictures to be close to each other on a manifold, you really want to defocus them. I'll put something on my blog on the matter. This is the reason why the has of two images next to each other are close in the "hash" or manifold space.
- for one image, the hash seems to provide 16 measurements (16 bits of the hash result). That would be OK if the initial picture was at the size and color of the picture after step 1 and 2. So in effect, that information is lost. However, in CS you also have "lossy" scheme such as the 1-bit compressed sensing approach (there you retain only the sign of the measurement!, i.e. a little bit like step 6). The reconstruction of these 1-bit pictures are not the original but they are close).
(ps: I write a small blog on CS).
Re: How Perceptual Hashes Work
#76Earlier quoted context omitted.
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…
I developed my answer there:
Are Perceptual Hashes an instance of Compressive Sensing ? http://nuit-blanche.blogspot.com/2011/06/are-perceptual-hash...
Re: How Perceptual Hashes Work
#77Earlier quoted context omitted.
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…
indeed. it took me forever to wrap my head around fft of an image.
one thing you can do is read how JPEG works, the DCT is a lot like generalized FFT.