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

Detecting duplicate images with Python

blog.iconfinder.com

Post reply on HN
Print view View original

41–50 of 52 posts

Re: Detecting duplicate images with Python

#41

Post by sushirain »

acslater00 wrote: post #24

Here is my question for OP. It seems like the image shrinking step coupled with the transformation to +/- values loses so much information that the hash would suffer from big false positive problem. I would have loved to see some data on this based on their own dataset. To give a concrete example, I noticed recently that a lot of app store icons within a category look pretty similar. See for example this: https://twi…

I am more concerned here with false negatives due to cropping, resizing, rotating, etc.

Re: Detecting duplicate images with Python

#42

Post by ominous_prime »

liuliu wrote: post #40
ominous_prime wrote: post #29

Earlier quoted context omitted.

Only if it's progressively encoded (though the decoder can still do fast 1/2, 1/4, and 1/8 reductions). Also, low resolution data isn't the same as what you get from a scaling algorithm like ALTIALIAS (though I don't know what that does, probably something like Lanczos). Plus, you still have to handle other formats like png, and get the same output from the same image.

Not really. JPEG encodes by 8x8 blocks, thus, for the DCT transform at the beginning, the first component after the transformation is always the mean value (of the 64 elements). Therefore, if your resizing target is more than 8x smaller, you can use the mean value directly without doing expensive DCT transform and the whole decoding process.

well, that's what I was hinting at by the fast 1/8 reduction, so yes you can speed up the process by "decoding" a smaller version of the jpeg image.

This is just an optimization to add later though. You might be able to quickly scale your jpeg down, but you can't skip the rest of the transforms, because you still need to get deterministic fingerprint of the image. And in the article's use case, the file size is so small that you shouldn't be dominated by decoding time (that test jpeg from the site decodes in 12ms on my laptop with libjpeg at full size).

Re: Detecting duplicate images with Python

#43

Post by razius »

szidev wrote: post #33

Great write-up! We did something very similar when trying to find duplicate product images for a consumer review site we were working on. Our implementation desaturated the image, broke it into a fixed number of tiles, and generated a histogram of each tile's values. Then we put a threshold on the histogram values, and had each value in the tile represent a bit. Combine the bits, and we had a hash to store in the DB.…

In practice we are using an image size of 17x16 which will result in a hash size of 256 bits and currently it seems to work pretty well. I ran the algorithm through the whole dataset (about 330.000+ icons) and I would say that from all the duplicate matches about 1% where false positives.

Also, we will be integrating this into the reviewing process for an iconset, where we also do a manual quality check, showing possible matches to something currently uploaded so skimming over one or two false positives isn't such a big deal and we where more interested in the speed of the algorithm.

Re: Detecting duplicate images with Python

#44

Post by razius »

acslater00 wrote: post #24

Here is my question for OP. It seems like the image shrinking step coupled with the transformation to +/- values loses so much information that the hash would suffer from big false positive problem. I would have loved to see some data on this based on their own dataset. To give a concrete example, I noticed recently that a lot of app store icons within a category look pretty similar. See for example this: https://twi…

First as a reply to the false positive problem: https://news.ycombinator.com/item?id=7527982

Idealy we would like to move to a content-based image retrieval system where we would be able to search based on certain features that can be derived from the image itself (color, shape, texture for example) so we could fine tune our results.

Yes, the presented example is a curious case, if we take the first three icons there and compare them based on share and color we can see that their shape is identical but the background is different. Based on this, should we consider different or identical? You can't have too many variations on a simple shape like a checkmark or a facebook logo so what variations should you allow and which ones would you consider as copying previous work?

Re: Detecting duplicate images with Python

#47

Post by good_guy »

johndavidback wrote: post #46

This might be a stupid question - but what if you have two icons, one with the cat with a black nose, one with the cat with a gray nose?

I had the same thought.i think they are going to use this to flag similar icons(and to show recommended images).so, most likely it'll be reviewed by a human.

Edit:

From the last paragraph. > we will be using the algorithm in the future on Iconfinder to warn us if a submitted icon already exists in our collection but it can also have other practical uses. For example, because images with similar features have the hamming distance of their hashes close, it can also be used as a basic recommendation system where the recommended images are within a certain hashing distance of the current image.

Re: Detecting duplicate images with Python

#48

Post by szidev »

razius wrote: post #43
szidev wrote: post #33

Great write-up! We did something very similar when trying to find duplicate product images for a consumer review site we were working on. Our implementation desaturated the image, broke it into a fixed number of tiles, and generated a histogram of each tile's values. Then we put a threshold on the histogram values, and had each value in the tile represent a bit. Combine the bits, and we had a hash to store in the DB.…

In practice we are using an image size of 17x16 which will result in a hash size of 256 bits and currently it seems to work pretty well. I ran the algorithm through the whole dataset (about 330.000+ icons) and I would say that from all the duplicate matches about 1% where false positives. Also, we will be integrating this into the reviewing process for an iconset, where we also do a manual quality check, showing poss…

That's pretty impressive performance given the hash size and speed. Thanks for sharing!

Re: Detecting duplicate images with Python

#49

Post by Torrents »

avaku wrote: post #45

Be careful not to get sued like that guy who posted an article about detecting songs and got sued by Shazam, even though everybody knows about FFT (I've been doing something like that for my BSc)

Any idea if that article is still available? Or do you have any good resources for implementing FTT? I'm working on a project to compare sound clips for similarity, but I haven't grasped an effective way to accomplish that yet.

Re: Detecting duplicate images with Python

#50

Post by jmmcd »

Torrents wrote: post #49
avaku wrote: post #45

Be careful not to get sued like that guy who posted an article about detecting songs and got sued by Shazam, even though everybody knows about FFT (I've been doing something like that for my BSc)

Any idea if that article is still available? Or do you have any good resources for implementing FTT? I'm working on a project to compare sound clips for similarity, but I haven't grasped an effective way to accomplish that yet.

FFTW
Post reply on HN