4 ms·

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 whi

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 way of doing it. Maybe a hash that starts with a random subsample is inherently slower for comparing millions of images, but I shouldn't think so.

nuitblanche 15y ago
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).
nuitblanche 15y ago
I developed my answer there: Are Perceptual Hashes an instance of Compressive Sensing ? http://nuit-blanche.blogspot.com/2011/06/are-perceptual-hashes-instance-of.html http://nuit-blanche.blogspot.com/2011/06/are-perceptual-hash...

nuitblanche 15y ago

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

nuitblanche 15y ago

I developed my answer there: Are Perceptual Hashes an instance of Compressive Sensing ? http://nuit-blanche.blogspot.com/2011/06/are-perceptual-hashes-instance-of.html http://nuit-blanche.blogspot.com/2011/06/are-perceptual-hash...