Detecting duplicate images with Python • Hacker News Board

Re: Detecting duplicate images with Python

#11

Post by razius » Thu, Apr 03, 2014, 1:05 PM UTC

herrherr wrote: post #10

We are currently using perceptual hashes (e.g. phash.org) to do hundreds of thousands of image comparisons per day. As mentioned in another comment, you really have to test different hashing algorithms to find one that suits your needs best. In general though, I think it is in most cases not necessary to develop an algorithm from scratch :) For us, the much more challenging part was/is to develop a system that can fi…

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/publications/HammingQuery/H...

Re: Detecting duplicate images with Python

#12

Post by thearn4 » Thu, Apr 03, 2014, 1:08 PM UTC

I've done a fair amount of work in image processing and computer vision, but haven't read much into hashing of images. Interesting article.

Re: Detecting duplicate images with Python

#13

Post by danso » Thu, Apr 03, 2014, 1:14 PM UTC

For Rubyists, check out the phashion gem, which is a light wrapper around pHash

https://github.com/westonplatter/phashion

Re: Detecting duplicate images with Python

#14

Post by steeve » Thu, Apr 03, 2014, 1:16 PM UTC

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

Re: Detecting duplicate images with Python

#15

Post by feelstupid » Thu, Apr 03, 2014, 1:24 PM UTC

I can't work out why the width would be need to be 1px bigger in width? I don't see the explanation in #3. Also, the array in #3 shows a 9x9 grid of 81 values when there are only 72 pixels?

Re: Detecting duplicate images with Python

#16

Post by kaivi » Thu, Apr 03, 2014, 1:29 PM UTC

herrherr wrote: post #10

We are currently using perceptual hashes (e.g. phash.org) to do hundreds of thousands of image comparisons per day. As mentioned in another comment, you really have to test different hashing algorithms to find one that suits your needs best. In general though, I think it is in most cases not necessary to develop an algorithm from scratch :) For us, the much more challenging part was/is to develop a system that can fi…

Indeed, the storage and retrieval of similar images is the hardest part. I do not know of a single networked open-source storage solution for this. I really wish that there was a project with a mindset of Redis, but for MVP trees. By the way, may it be possible to implement MVP data structure in Redis, as the project is now? I can not think of possible replication issues with this, apart from the fact that one would have to pre-define a metric space for every tree.

It could be a great extension to Redis DSL.

Re: Detecting duplicate images with Python

#17

Post by kasperset » Thu, Apr 03, 2014, 1:31 PM UTC

Although slower than this solution, I like this program: http://ssdeep.sourceforge.net/

Re: Detecting duplicate images with Python

#18

Post by sp332 » Thu, Apr 03, 2014, 1:59 PM UTC

feelstupid wrote: post #15

I can't work out why the width would be need to be 1px bigger in width? I don't see the explanation in #3. Also, the array in #3 shows a 9x9 grid of 81 values when there are only 72 pixels?

If you only have 8 samples per row, then you have 7 adjacent pairs. If you use a bit to represent the differences, you'll only have 7 bits. If you want 8 bits, you need 8 differences, so 9 samples.

Re: Detecting duplicate images with Python

#19

Post by herrherr » Thu, Apr 03, 2014, 1:59 PM UTC

razius wrote: post #11

herrherr wrote: post #10

We are currently using perceptual hashes (e.g. phash.org) to do hundreds of thousands of image comparisons per day. As mentioned in another comment, you really have to test different hashing algorithms to find one that suits your needs best. In general though, I think it is in most cases not necessary to develop an algorithm from scratch :) For us, the much more challenging part was/is to develop a system that can fi…

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.

Re: Detecting duplicate images with Python

#20

Post by feelstupid » Thu, Apr 03, 2014, 2:07 PM UTC

sp332 wrote: post #18

feelstupid wrote: post #15

I can't work out why the width would be need to be 1px bigger in width? I don't see the explanation in #3. Also, the array in #3 shows a 9x9 grid of 81 values when there are only 72 pixels?

If you only have 8 samples per row, then you have 7 adjacent pairs. If you use a bit to represent the differences, you'll only have 7 bits. If you want 8 bits, you need 8 differences, so 9 samples.

That makes sense, but why does the example have a 9 by 9 grid, would it be a 9 columns but only 8 rows?