4 ms·

Isn't it really expensive to dedupe images based on content? As you have to compare every image to every other image in the dataset? How could one go about ded

Isn't it really expensive to dedupe images based on content? As you have to compare every image to every other image in the dataset? How could one go about deduping images? Maybe using something similar to rsync protocol? Cheap hash method, then a more expensive one, then a full comparison, maybe. Even so 2B+ images... and you are talking about saving on storage costs, mostly which is quite cheap these days.

ALittleLight 4y ago
You don't have to compare all images to one another and doing so wouldn't reliably dedupe - what if one image is slightly different resolution, different image type, different metadata, etc? They would different hashes but still basically the same data. I think the way you do it is to train a model to represent images as vectors. Then you put those vectors into a BTree which will allow you to efficiently query for the "nearest neighbor" to an image on log(n) time. You calibrate to find a distance that picks up duplicates without getting too many non-duplicates and then it's n log(n) time rather than n^2. If that's still too slow there is also a thing called ANNOY which lets you do approximate nearest neighbor faster.
minimaxir 4y ago
Convert the images to embeddings, and perform an approximate nearest neighbor search on them and identify images that are very close together (e.g. with faiss, which the page alludes to using). It's performant enough even at scale.
deleted 4y ago
[deleted]
gpm 4y ago
I don't have experience with image duplication, but if you can make a decent hash a 2.3 billion item hashtable is really cheap. If you need to do something closer to pairwise (for instance, because you can't make a cheap hash of images which papers over differences in compression), make the hash table for the text descriptions, then compare the images within buckets. Of the few 5 or 6 text fields I just spot checked (not even close to random selection) the worst false positive I found (in the 12M data set) was 3 pairs of two duplicates with the same description. On the other hand I found one set of 76 identical images with the same description.
wongarsu 4y ago
There are hash algorithms for image similarity. For a toy example, imagine scaling the image to 8x8px, making it grayscale, and using those 64 bytes as hash. That way you only have to hash each picture once, and can find duplicates by searching for hashes with a low hamming distance (number of bit flips) to each other, which is very fast. Of course actual hash algorithms are a bit cleverer, there are a number to choose from depending on what you want to consider a duplicate (cropping, flips, rotations, etc)
- ClassyJacket 4y ago
  But even a single pixel being one shade brighter would make one hash completely different, that's the point of hashes.
  - fjkdlsjflkds 4y ago
    You're probably confusing "cryptographic hash functions" with "perceptual hashing" (or other forms of "locality-sensitive hashing"). In the case of the latter, what you say is almost always not true (that's the point of using "perceptual hashing" after all: similar objects get mapped to similar/same hash). See: https://en.wikipedia.org/wiki/Perceptual_hashing https://en.wikipedia.org/wiki/Perceptual_hashing
acdha 4y ago
It depends on exactly what problem you're trying to solve. If the goal is to find the same image with slight differences caused by re-encoding, downsampling, scaling, etc. you can use something like phash.org pretty efficiently to build a database of image hashes, review the most similar ones, and use it to decide whether you've already “seen” new images. That approach works well when the images are basically the same. It doesn't work so well when you're trying to find images which are either different photos of the same subject or where one of them is a crop of a larger image or has been modified more heavily. A number of years back I used OpenCV for that task[1] to identify the source of a given thumbnail image in a larger master file and used phash to validate that a new higher resolution thumbnail was highly similar to the original low-res thumbnail after trying to match the original crop & rotation. I imagine there are far more sophisticated tools for that now but at the time phash felt basically free in comparison the amount of computation which OpenCV required. 1. https://blogs.loc.gov/thesignal/2014/08/upgrading-image-thumbnails-or-how-to-fill-a-large-display-without-your-content-team-quitting/ https://blogs.loc.gov/thesignal/2014/08/upgrading-image-thum...
visarga 4y ago
No, you embed all images with CLIP and use an approximate nearest neighbour library (like faiss) to get the most similar ones to the query in logarithmic time. Embedding will also be invariant to small variations. You can try this on images.yandex.com - they do similarity search with embeddings. Upload any photo and you'll get millions of similar photos, unlike Google that has only exact duplicate search. It's diverse like Pinterest but without the logins. Query image: https://cdn.discordapp.com/attachments/1005626182869467157/1006065194721607721/the_upper_torso_of_a_terminator_gorgon_medusa_with_borg_implants_and_robotic_snakes_coming_out_of_her_head_is_hanging_from_cables_and_wires_off_the_ceilin_-n_9_-i_-S_4163032289_ts-1659935033_idx-7.png https://cdn.discordapp.com/attachments/1005626182869467157/1... Yandex similarity search results: https://yandex.com/images/search?rpt=imageview&url=https%3A%2F%2Fyandex-images.clstorage.net%2F9M7ss3q73%2Fcb8f48oc%2FNxfA302eE-Jg118uUcurxCMrXWIHU6cdgPI4MngjwezlV74Xq5vPQNCUv5zaTarhpeSW5AIhr6yeJVf42JO6fQYD5Nlp-kEzMobNKlW6fpCS7pxiZEAVXhYxKpAeQcMvQBc-J_u6GpQwVEz-Crn-5aIxovB0Rc3-X6WmLqjhS6-1x4BI2FgxUYDlfXzjzYn3MN3cQVfwlC6k0VjBfFEijgNnrGYb2K8GsfYcXozq3KbQsdChx0QuXTx1ZI_4kcvNtxWTGLpp0UEjlG6_YHxZtVGOjcAko1R_dZKpMU_B4W9Sx74FW_mPBjOmHa8smn03kiLA8bdHr22fFcZvSACJv2X1sbqbeWCAIlbtr9Hvq-VxT51RB1DlDCbi-MGNorKNgNesl4mbblWSFO8fnEucVYNBwtJ1xH1NnCcG7MngGkxExLDIySihQ-G2PQ1B_bg14Y2soxdxt52HQOlRn7LjjWG3fDWI2L4U0kWeHcyJTzeQYMFDV9Xvj620lA1L0Ir9F0RyuavLg6BQBT_toM5qVQEdP-F2EaQOpEO5ADwAMu1yx2_XOZqs5YIUf978K732AGOggqfGPc1v1sSe6XOLrzRE40mLiZKzEfd_7YPOSURAvr7TV0LFHaRDSRGdsxDdIoYftviazUaihc1d7bqM5OPyoZIXRnx9b4VH3skh-ew1xoBreQiCgUO1Pj-AL7h3wiyOUgQSluyFU7tBjKCyzcNGjBd7iPzFEFXN7X5orVewgYNyZPXeLQ0W9Hz7E1s_VyfgqHnao6FiNG1dwl8ZVeL_fKJG0se-VPC7MXxgM61zl73XyckdJkJGzV5_q9-kcaCCs_f2Xg7MFLVdGtPqjnaEkau6KbKhYgbdj5IdCyTTPL9yVsC2fxTS6xEfo4KvE0auhWrpjWZD1L1f7MvtxhDTAVAWhr4cfMXm32hRa43EBjObmYmhQaIkf18DneuEIU4vYVdxxA7kg_kh39Cjg&cbir_id=4330723%2F5mvtJz4mInge23XijLcDmA2438 https://yandex.com/images/search?rpt=imageview&url=https%3A%...

ALittleLight 4y ago

You don't have to compare all images to one another and doing so wouldn't reliably dedupe - what if one image is slightly different resolution, different image type, different metadata, etc? They would different hashes but still basically the same data. I think the way you do it is to train a model to represent images as vectors. Then you put those vectors into a BTree which will allow you to efficiently query for the "nearest neighbor" to an image on log(n) time. You calibrate to find a distance that picks up duplicates without getting too many non-duplicates and then it's n log(n) time rather than n^2. If that's still too slow there is also a thing called ANNOY which lets you do approximate nearest neighbor faster.

minimaxir 4y ago

Convert the images to embeddings, and perform an approximate nearest neighbor search on them and identify images that are very close together (e.g. with faiss, which the page alludes to using). It's performant enough even at scale.

deleted 4y ago

[deleted]

gpm 4y ago

I don't have experience with image duplication, but if you can make a decent hash a 2.3 billion item hashtable is really cheap. If you need to do something closer to pairwise (for instance, because you can't make a cheap hash of images which papers over differences in compression), make the hash table for the text descriptions, then compare the images within buckets. Of the few 5 or 6 text fields I just spot checked (not even close to random selection) the worst false positive I found (in the 12M data set) was 3 pairs of two duplicates with the same description. On the other hand I found one set of 76 identical images with the same description.

wongarsu 4y ago

There are hash algorithms for image similarity. For a toy example, imagine scaling the image to 8x8px, making it grayscale, and using those 64 bytes as hash. That way you only have to hash each picture once, and can find duplicates by searching for hashes with a low hamming distance (number of bit flips) to each other, which is very fast. Of course actual hash algorithms are a bit cleverer, there are a number to choose from depending on what you want to consider a duplicate (cropping, flips, rotations, etc)

ClassyJacket 4y ago
But even a single pixel being one shade brighter would make one hash completely different, that's the point of hashes.
- fjkdlsjflkds 4y ago
  You're probably confusing "cryptographic hash functions" with "perceptual hashing" (or other forms of "locality-sensitive hashing"). In the case of the latter, what you say is almost always not true (that's the point of using "perceptual hashing" after all: similar objects get mapped to similar/same hash). See: https://en.wikipedia.org/wiki/Perceptual_hashing https://en.wikipedia.org/wiki/Perceptual_hashing

acdha 4y ago

It depends on exactly what problem you're trying to solve. If the goal is to find the same image with slight differences caused by re-encoding, downsampling, scaling, etc. you can use something like phash.org pretty efficiently to build a database of image hashes, review the most similar ones, and use it to decide whether you've already “seen” new images. That approach works well when the images are basically the same. It doesn't work so well when you're trying to find images which are either different photos of the same subject or where one of them is a crop of a larger image or has been modified more heavily. A number of years back I used OpenCV for that task[1] to identify the source of a given thumbnail image in a larger master file and used phash to validate that a new higher resolution thumbnail was highly similar to the original low-res thumbnail after trying to match the original crop & rotation. I imagine there are far more sophisticated tools for that now but at the time phash felt basically free in comparison the amount of computation which OpenCV required. 1. https://blogs.loc.gov/thesignal/2014/08/upgrading-image-thumbnails-or-how-to-fill-a-large-display-without-your-content-team-quitting/ https://blogs.loc.gov/thesignal/2014/08/upgrading-image-thum...

visarga 4y ago

No, you embed all images with CLIP and use an approximate nearest neighbour library (like faiss) to get the most similar ones to the query in logarithmic time. Embedding will also be invariant to small variations. You can try this on images.yandex.com - they do similarity search with embeddings. Upload any photo and you'll get millions of similar photos, unlike Google that has only exact duplicate search. It's diverse like Pinterest but without the logins. Query image: https://cdn.discordapp.com/attachments/1005626182869467157/1006065194721607721/the_upper_torso_of_a_terminator_gorgon_medusa_with_borg_implants_and_robotic_snakes_coming_out_of_her_head_is_hanging_from_cables_and_wires_off_the_ceilin_-n_9_-i_-S_4163032289_ts-1659935033_idx-7.png https://cdn.discordapp.com/attachments/1005626182869467157/1... Yandex similarity search results: https://yandex.com/images/search?rpt=imageview&url=https%3A%2F%2Fyandex-images.clstorage.net%2F9M7ss3q73%2Fcb8f48oc%2FNxfA302eE-Jg118uUcurxCMrXWIHU6cdgPI4MngjwezlV74Xq5vPQNCUv5zaTarhpeSW5AIhr6yeJVf42JO6fQYD5Nlp-kEzMobNKlW6fpCS7pxiZEAVXhYxKpAeQcMvQBc-J_u6GpQwVEz-Crn-5aIxovB0Rc3-X6WmLqjhS6-1x4BI2FgxUYDlfXzjzYn3MN3cQVfwlC6k0VjBfFEijgNnrGYb2K8GsfYcXozq3KbQsdChx0QuXTx1ZI_4kcvNtxWTGLpp0UEjlG6_YHxZtVGOjcAko1R_dZKpMU_B4W9Sx74FW_mPBjOmHa8smn03kiLA8bdHr22fFcZvSACJv2X1sbqbeWCAIlbtr9Hvq-VxT51RB1DlDCbi-MGNorKNgNesl4mbblWSFO8fnEucVYNBwtJ1xH1NnCcG7MngGkxExLDIySihQ-G2PQ1B_bg14Y2soxdxt52HQOlRn7LjjWG3fDWI2L4U0kWeHcyJTzeQYMFDV9Xvj620lA1L0Ir9F0RyuavLg6BQBT_toM5qVQEdP-F2EaQOpEO5ADwAMu1yx2_XOZqs5YIUf978K732AGOggqfGPc1v1sSe6XOLrzRE40mLiZKzEfd_7YPOSURAvr7TV0LFHaRDSRGdsxDdIoYftviazUaihc1d7bqM5OPyoZIXRnx9b4VH3skh-ew1xoBreQiCgUO1Pj-AL7h3wiyOUgQSluyFU7tBjKCyzcNGjBd7iPzFEFXN7X5orVewgYNyZPXeLQ0W9Hz7E1s_VyfgqHnao6FiNG1dwl8ZVeL_fKJG0se-VPC7MXxgM61zl73XyckdJkJGzV5_q9-kcaCCs_f2Xg7MFLVdGtPqjnaEkau6KbKhYgbdj5IdCyTTPL9yVsC2fxTS6xEfo4KvE0auhWrpjWZD1L1f7MvtxhDTAVAWhr4cfMXm32hRa43EBjObmYmhQaIkf18DneuEIU4vYVdxxA7kg_kh39Cjg&cbir_id=4330723%2F5mvtJz4mInge23XijLcDmA2438 https://yandex.com/images/search?rpt=imageview&url=https%3A%...