7 ms·

Simple, Fast, and Scalable Reverse Image Search

129 points by SerCe 4y ago

Corendos 4y ago
This was my internship subject (in another company) just before I graduated, I wonder what they used for the Perceptual Hash, ours was SIFT features. Happy to see that what I implemented would have been able to scale that much !
- HanClinto 4y ago
  So when you run SIFT on an image, one gets dozens (maybe hundreds) of SIFT features back. The trouble with SIFT features is that each individual SIFT feature is a local image descriptor -- it describes a single point in the image. One can't just append the two lists of SIFT descriptors together and do a Hamming comparison on them, because it's not guaranteed that both images will have all of the same SIFT descriptors, nor that they would be in the same order. When you want to do image comparison on image descriptors, one must compare every local feature with every local feature in every other image. This is great for comparing two images together, or for finding where one image is located in another image (homography matching), but this does not scale for large image sets. In contrast, descriptors like perceptual hashes look at the entire image, and so are a _global_ image descriptor. There are ways to convert local SIFT image descriptors into a single global image descriptor for doing more rapid lookup (Bag of Visual Words is one technique that comes to mind), but SIFT and pHash really are in two categories all their own. More info on pHash: https://hackerfactor.com/blog/index.php%3F/archives/432-Looks-Like-It.html https://hackerfactor.com/blog/index.php%3F/archives/432-Look... Example of SIFT for fine-grained image matching: https://docs.opencv.org/3.4/d1/de0/tutorial_py_feature_homography.html https://docs.opencv.org/3.4/d1/de0/tutorial_py_feature_homog...
- starkd 4y ago
  I have found the ML image categorization models an excellent method of extracting a unique descriptor. It is possible to compress the image for matching and storage into a compact signature. I did it here: https://github.com/starkdg/phashml https://github.com/starkdg/phashml https://github.com/starkdg/pyphashml https://github.com/starkdg/pyphashml It is available in a python module that uses tensorflow model. Feel free to message me.
  - mzs 4y ago
    thanks, first link 404s
tiffanyh 4y ago
https://tineye.com https://tineye.com is pretty great for doing internet wide reverse image searches.
- hbn 4y ago
  It's still nowhere close to how good Google's reverse image search was several years back. Ever since they handicapped that, there just hasn't been as good of a way to do reverse image searches. I've tried on searching for images I know are on the internet, running them through Google, TinEye, Bing, Yandex, to no avail. It seems like a lot of the focus has moved from "find this exact image" to "find similar images," like you give it a picture of a Husky and it'll find more pictures of Huskies.
  - coolca 4y ago
    Interesting, I didn't know Google reverse image was better several years ago.
  - swyx 4y ago
    why exactly did they handicap it? i've noticed it's also weirdly desktop only, i have to add ?imghp to get it to display the reverse image search button on ipad
    - vintermann 4y ago
      Well, yandex search was better for a while. Then Bellingcat managed to identify some spy with it. Then yandex got worse too. I think maybe that's part of the picture. Edit: I looked up the details again. It was an FSB officer named Andrei Burlaka, involved in the shooting down of MH17. Someone in Russia were selling their TV set online, and had taken a picture of the TV for the ad. It just so happened that Burlaka was on TV exactly that moment. Yandex images indexed the ad, leading the investigators to identify him.
    - AdvancedCarrot 4y ago
      My suspicion is that they did it for privacy reasons. Let me give you an example - you have a photo of someone. Should Google give you their facebook profile in the results if you search for the picture? Their AI is certainly capable of this, but some people would be understandably creeped out by it.
ajtulloch 4y ago
“Fast Search in Hamming Space with Multi-Index Hashing” (https://www.cs.toronto.edu/~norouzi/research/papers/multi_index_hashing.pdf https://www.cs.toronto.edu/~norouzi/research/papers/multi_in...) is a great paper. Note that you can do significantly better (in terms of query latency/throughput) with specialized implementations as in eg FAISS (https://github.com/facebookresearch/faiss/wiki/Binary-hashing-index-benchmark https://github.com/facebookresearch/faiss/wiki/Binary-hashin...).
mxmlnkn 4y ago
Interesting read. Especially the lookup method based on partitioning. I tried to implement a similar reverse image search based on dHash as explained here https://github.com/Rayraegah/dhash https://github.com/Rayraegah/dhash . However, I also had lookup performance problems. Exact matches are not a problem but the Hamming distance threshold matching is. Because my project was in Python, I tried to eke out more performance by writing a BK-tree backend module in C++ https://github.com/mxmlnkn/cppbktree https://github.com/mxmlnkn/cppbktree It was 2 to 10x faster than an existing similar module but still was too slow when trying to look up something in a database of millions of images. However, as lookup tended to depend on the exact Hamming-distance threshold value, my next step would have been to try and optimize the hash. E.g, make it shorter so that only a short Hamming distance is necessary to be looked up but the mentioned multi-indexing method looks much more promising and tested.
- starkd 4y ago
  There's limits to how short you can make the perceptual hash. The more you compress it, the more information you lose. The ML image classification models can be used to extract a good descriptor that can be further reduced into a compact signature. https://github.com/starkdg/pyphashml https://github.com/starkdg/pyphashml For indexing, I've had some success with distance-based indexing. Here's a comparison of some structures I used: https://github.com/starkdg/hftrie#comparison https://github.com/starkdg/hftrie#comparison Feel free to contact me, if you want to discuss this further.
swyx 4y ago
something i felt was missing from the piece - what is the typical hamming distance cutoff for something like this? he explains 2 is small enough to be identical but presumably it can go really high. what happens with a distance of like 100? what's the state of research on false positives and adversarial attacks?
- starkd 4y ago
  It's tricky. You have to customize it. But any index method needs a fairly low threshold or the search devolves to a linear search. But as you increase the threshold, you quickly reach a cutoff where it's all just completely dissimilar images. So, a threshold of 100 would be utterly pointless.
  - dark_pattern 4y ago
    It'll depend on your needs, you have to compute your precision against recall to then decide what is a good cutoff for your application
culi 4y ago
95% of the time when I'm using reverse image search I'm just trying to find the original source of something. This is the opposite of what Google Lens focuses on but is a much simpler problem to solve :(
jonatron 4y ago
I used ORB descriptors and Hamming Distance for a fuzzy/partial/inexact reverse image search at my last job. While it didn't scale like the OP does, it found some really interesting fuzzy matches.
johndough 4y ago
There is also https://rom1504.github.io/clip-retrieval/?back=https%3A%2F%2Fknn5.laion.ai&index=laion5B&useMclip=false https://rom1504.github.io/clip-retrieval/?back=https%3A%2F%2... which indexes the 5B images LAION dataset (basically a subset of the images from Common Crawl) and allows both text and image queries. The code as well as the image dataset is open source (although you need a new hard drive just to store the URLs).
fxtentacle 4y ago
I would love to hear about the cost of this deployment. 10 billion images x4 rows each in Amazon DynamoDB with 2000 rps sounds like it'll burn through your wallet faster than most explosives...
fxtentacle 4y ago
4 requests per image lookup x 2000 requests per second = 8000 DynamoDB Reads per Second = 28,800,000 reads per hour AWS price list says reserved instances come in at "$0.00013 per RCU" x 28,800,000 = $3744 per hour. Does this really cost $2.6 mio per month to operate? If yes, contact me and I'll be happy to save you $2.595 mio monthly by re-implementing things in C++ on bare metal servers.
- tiffanyh 4y ago
  Just charge them the cost of 1-months savings. Seems like a fair amount for them to spend for your efficiency gains and quick ROI for them :)
- srijs 4y ago
  1x RCU gives you 1 strongly consistent read of up to 4KB _per second_. So 8000 reads per second require 8000 RCUs, which at list pricing comes to $1 per hour. And that's assuming reads do need to be strongly consistent (otherwise half the price) and no discounts are applied.
jcbages 4y ago
This looks to cool I didn't know anything about perceptual hashing but the idea makes a lot of sense. I'm curious if the system lose its effectiveness if a user shifts an image a few pixels, reflects it, or apply a certain filter that makes all pixels have a slightly different tonality. I'm also thinking of some system maybe a small ML program that applies a minimal amount of noise to the image such that to the human eye it looks the same but pixel-wise is totally different.

129 points by SerCe 4y ago

This was my internship subject (in another company) just before I graduated, I wonder what they used for the Perceptual Hash, ours was SIFT features. Happy to see that what I implemented would have been able to scale that much !

HanClinto 4y ago
So when you run SIFT on an image, one gets dozens (maybe hundreds) of SIFT features back. The trouble with SIFT features is that each individual SIFT feature is a local image descriptor -- it describes a single point in the image. One can't just append the two lists of SIFT descriptors together and do a Hamming comparison on them, because it's not guaranteed that both images will have all of the same SIFT descriptors, nor that they would be in the same order. When you want to do image comparison on image descriptors, one must compare every local feature with every local feature in every other image. This is great for comparing two images together, or for finding where one image is located in another image (homography matching), but this does not scale for large image sets. In contrast, descriptors like perceptual hashes look at the entire image, and so are a _global_ image descriptor. There are ways to convert local SIFT image descriptors into a single global image descriptor for doing more rapid lookup (Bag of Visual Words is one technique that comes to mind), but SIFT and pHash really are in two categories all their own. More info on pHash: https://hackerfactor.com/blog/index.php%3F/archives/432-Looks-Like-It.html https://hackerfactor.com/blog/index.php%3F/archives/432-Look... Example of SIFT for fine-grained image matching: https://docs.opencv.org/3.4/d1/de0/tutorial_py_feature_homography.html https://docs.opencv.org/3.4/d1/de0/tutorial_py_feature_homog...
starkd 4y ago
I have found the ML image categorization models an excellent method of extracting a unique descriptor. It is possible to compress the image for matching and storage into a compact signature. I did it here: https://github.com/starkdg/phashml https://github.com/starkdg/phashml https://github.com/starkdg/pyphashml https://github.com/starkdg/pyphashml It is available in a python module that uses tensorflow model. Feel free to message me.
- mzs 4y ago
  thanks, first link 404s

tiffanyh 4y ago

https://tineye.com https://tineye.com is pretty great for doing internet wide reverse image searches.

hbn 4y ago
It's still nowhere close to how good Google's reverse image search was several years back. Ever since they handicapped that, there just hasn't been as good of a way to do reverse image searches. I've tried on searching for images I know are on the internet, running them through Google, TinEye, Bing, Yandex, to no avail. It seems like a lot of the focus has moved from "find this exact image" to "find similar images," like you give it a picture of a Husky and it'll find more pictures of Huskies.
- coolca 4y ago
  Interesting, I didn't know Google reverse image was better several years ago.
- swyx 4y ago
  why exactly did they handicap it? i've noticed it's also weirdly desktop only, i have to add ?imghp to get it to display the reverse image search button on ipad
  - vintermann 4y ago
    Well, yandex search was better for a while. Then Bellingcat managed to identify some spy with it. Then yandex got worse too. I think maybe that's part of the picture. Edit: I looked up the details again. It was an FSB officer named Andrei Burlaka, involved in the shooting down of MH17. Someone in Russia were selling their TV set online, and had taken a picture of the TV for the ad. It just so happened that Burlaka was on TV exactly that moment. Yandex images indexed the ad, leading the investigators to identify him.
  - AdvancedCarrot 4y ago
    My suspicion is that they did it for privacy reasons. Let me give you an example - you have a photo of someone. Should Google give you their facebook profile in the results if you search for the picture? Their AI is certainly capable of this, but some people would be understandably creeped out by it.

ajtulloch 4y ago

“Fast Search in Hamming Space with Multi-Index Hashing” (https://www.cs.toronto.edu/~norouzi/research/papers/multi_index_hashing.pdf https://www.cs.toronto.edu/~norouzi/research/papers/multi_in...) is a great paper. Note that you can do significantly better (in terms of query latency/throughput) with specialized implementations as in eg FAISS (https://github.com/facebookresearch/faiss/wiki/Binary-hashing-index-benchmark https://github.com/facebookresearch/faiss/wiki/Binary-hashin...).

mxmlnkn 4y ago

Interesting read. Especially the lookup method based on partitioning. I tried to implement a similar reverse image search based on dHash as explained here https://github.com/Rayraegah/dhash https://github.com/Rayraegah/dhash . However, I also had lookup performance problems. Exact matches are not a problem but the Hamming distance threshold matching is. Because my project was in Python, I tried to eke out more performance by writing a BK-tree backend module in C++ https://github.com/mxmlnkn/cppbktree https://github.com/mxmlnkn/cppbktree It was 2 to 10x faster than an existing similar module but still was too slow when trying to look up something in a database of millions of images. However, as lookup tended to depend on the exact Hamming-distance threshold value, my next step would have been to try and optimize the hash. E.g, make it shorter so that only a short Hamming distance is necessary to be looked up but the mentioned multi-indexing method looks much more promising and tested.

starkd 4y ago
There's limits to how short you can make the perceptual hash. The more you compress it, the more information you lose. The ML image classification models can be used to extract a good descriptor that can be further reduced into a compact signature. https://github.com/starkdg/pyphashml https://github.com/starkdg/pyphashml For indexing, I've had some success with distance-based indexing. Here's a comparison of some structures I used: https://github.com/starkdg/hftrie#comparison https://github.com/starkdg/hftrie#comparison Feel free to contact me, if you want to discuss this further.

swyx 4y ago

something i felt was missing from the piece - what is the typical hamming distance cutoff for something like this? he explains 2 is small enough to be identical but presumably it can go really high. what happens with a distance of like 100? what's the state of research on false positives and adversarial attacks?

starkd 4y ago
It's tricky. You have to customize it. But any index method needs a fairly low threshold or the search devolves to a linear search. But as you increase the threshold, you quickly reach a cutoff where it's all just completely dissimilar images. So, a threshold of 100 would be utterly pointless.
- dark_pattern 4y ago
  It'll depend on your needs, you have to compute your precision against recall to then decide what is a good cutoff for your application

culi 4y ago

95% of the time when I'm using reverse image search I'm just trying to find the original source of something. This is the opposite of what Google Lens focuses on but is a much simpler problem to solve :(

jonatron 4y ago

I used ORB descriptors and Hamming Distance for a fuzzy/partial/inexact reverse image search at my last job. While it didn't scale like the OP does, it found some really interesting fuzzy matches.

johndough 4y ago

There is also https://rom1504.github.io/clip-retrieval/?back=https%3A%2F%2Fknn5.laion.ai&index=laion5B&useMclip=false https://rom1504.github.io/clip-retrieval/?back=https%3A%2F%2... which indexes the 5B images LAION dataset (basically a subset of the images from Common Crawl) and allows both text and image queries. The code as well as the image dataset is open source (although you need a new hard drive just to store the URLs).

fxtentacle 4y ago

I would love to hear about the cost of this deployment. 10 billion images x4 rows each in Amazon DynamoDB with 2000 rps sounds like it'll burn through your wallet faster than most explosives...

fxtentacle 4y ago

4 requests per image lookup x 2000 requests per second = 8000 DynamoDB Reads per Second = 28,800,000 reads per hour AWS price list says reserved instances come in at "$0.00013 per RCU" x 28,800,000 = $3744 per hour. Does this really cost $2.6 mio per month to operate? If yes, contact me and I'll be happy to save you $2.595 mio monthly by re-implementing things in C++ on bare metal servers.

tiffanyh 4y ago
Just charge them the cost of 1-months savings. Seems like a fair amount for them to spend for your efficiency gains and quick ROI for them :)
srijs 4y ago
1x RCU gives you 1 strongly consistent read of up to 4KB _per second_. So 8000 reads per second require 8000 RCUs, which at list pricing comes to $1 per hour. And that's assuming reads do need to be strongly consistent (otherwise half the price) and no discounts are applied.

jcbages 4y ago

This looks to cool I didn't know anything about perceptual hashing but the idea makes a lot of sense. I'm curious if the system lose its effectiveness if a user shifts an image a few pixels, reflects it, or apply a certain filter that makes all pixels have a slightly different tonality. I'm also thinking of some system maybe a small ML program that applies a minimal amount of noise to the image such that to the human eye it looks the same but pixel-wise is totally different.