What about images which are mirror-flipped? Unless it is a symmetrical icon that particular algorithm will consider the two highly different.
Detecting duplicate images with Python
31–40 of 52 posts
Re: Detecting duplicate images with Python
#32Earlier quoted context omitted.
Yes, you're right. We're not using SQL queries at the moment as that would be very inefficient, it was just as an example for a small dataset. I'm currently researching MVP's and reading on VP-trees, BK-trees [1], GNAT [2] and HEngine [3]. Do you have any advice? [1] http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK... [2] http://www.vldb.org/conf/1995/P574.PDF [3] https://www.cse.msu.edu/~alexliu/publicat…
I think you are on the right track there. The thing is though, you won't have difficulties finding papers on those topics. However, you will probably not have any luck finding many concrete and practical implementations that you could look at. So it's a far way from reading the papers to having something working. If you find something, please let me know.
There's a list of CBIR's on Wikipedia and ammong those there are a few open source ones. I didn't really had time to check them all but during skimming through them imgSeek [2] caught my eye.
Re: Detecting duplicate images with Python
#33Great 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. Our hashes were a bit larger, so images within a certain hamming distance were flagged, rather than just looking for exact hash matches. It took quite a bit of tuning for us to get good results, but it seemed to work pretty well. Do you see many false positives with such a small processed image size (the 9x8 one, I mean)?
Re: Detecting duplicate images with Python
#34This is a bad approach for a couple reasons:
1) The total measurable space/information over a resized icon-size greyscale image is pretty small, so you run into a much higher likelyhood of collisions/false positives.
2) It's not too hard to program a Haar wavelet[1] transform[2] (basically iterative scaled thesholding). This has worked well over at IQDB[3], where they do reverse image lookups on databases of over several million images via a modified Haar wavelet.
You can't beat this algorithm for simplicity, though. Have you guys done any false positive checks with this algorithm? The saving grace might be that icons are fairly small and limited in detail/color.
[1] http://en.wikipedia.org/wiki/Haar_wavelet
[2] http://stackoverflow.com/questions/1034900/near-duplicate-im...
[3] http://iqdb.org/
Re: Detecting duplicate images with Python
#35If the has were really looked up by value, like in the example SQL:
SELECT pk, hash, file_path FROM image_hashes
WHERE hash = '4c8e3366c275650f';
Re: Detecting duplicate images with Python
#36Node implementation -> https://github.com/rompetoto/dhash
Re: Detecting duplicate images with Python
#37I wonder if this algorithm would work if someone uploaded a rotated version of a previously uploaded icon. As it only compares row adjacent values, if the rotation was 90 or 270 degrees I'm not sure it'd detect the duplicate.
Re: Detecting duplicate images with Python
#38An idea: This would require more information storage, but would it be possible to hash an image and take snapshots of the hashing algorithm as it processes the image, say after each block of hashing (hashing digests a block - such as 64 bytes - at a time). Then simply compare the list of snapshots between two images and come up with a statistical threshold for a "similar image"? In the case of the two cats the images only differ in the nose, so the first half of the image up to the nose would produce the same list of snapshots.
You could also hash forwards, backwards and starting at several random midpoints to prevent someone from simply changing the first block to throw off the hashing algorithm.
Re: Detecting duplicate images with Python
#39Or you can use OpenCV with SIFT/SURF/ORB + KNN/RANSAC and have a very robust solution. Example [1]. OpenCV has awesome Python bindings (cv2), btw. [1] http://stackoverflow.com/questions/2146542/opencv-surf-how-t...
Using feature detectors and descriptors is only half of the solution. If you really want robust image recognition you need to use something like the vocabulary tree developed by Nister[1][2]. [1] http://www.wisdom.weizmann.ac.il/~bagon/CVspring07/files/sca... [2] http://www.cc.gatech.edu/~phlosoft/files/schindler07cvpr2.pd...
True, however, OpenCV implements a bag of visual words, too [1]
[1] http://docs.opencv.org/modules/features2d/doc/object_categor...
Re: Detecting duplicate images with Python
#40JPEG already has the low resolution information stored in an easily retrievable way. You could use that directly, no need to do the transforms. It would be a lot faster.
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.