Hacker News Reader

Comment by fake-name | Hacker News Reader

I have a C++ + Cython implementation of a BK-tree that I use for large-scale image deduplication on github: https://github.com/fake-name/IntraArchiveDeduplicator/tree/m...

The core is a single, header-only BK-tree implementation here: https://github.com/fake-name/IntraArchiveDeduplicator/blob/m....

There are also relatively comprehensive unit-tests for the whole thing: https://github.com/fake-name/IntraArchiveDeduplicator/tree/m...

I use it for image deduplication across a ~28M image dataset. It works quite well, though it does take a lot of ram to hold the entire dataset in memory (~18 GB).

View on HN

Out of curiosity: why not store hashes of the images instead of the entire image?

Or even better: a bloom filter to find likely duplicates?

may you please elucidate your scheme ? in my naïveté, it seems to me, that hashing etc would not help at all.

As mentioned in one reply to the parent comment, hashing here usually is not cryptographic.

I'm familiar with location-sensitive hashing[1], which acts like a dimensionality reducer but, instead of receiving as input the image itself receives a feature vector extracted from it (or something analogous that allows for similarity assessment).

[1] https://en.wikipedia.org/wiki/Locality-sensitive_hashing

Presumably, the idea is to count sufficiently similar images as the same image when doing the deduplication, so traditional hashing doesn't help here.

Maybe they were thinking of fingerprinting, e.g., by downsampling. It’s dual in some sense to hashing—a small change to some data should produce a large change in its hash, but a small change in its fingerprint.

Hashing is the correct term here, but it's not a cryptographic hash, but rather a perceptual hash: https://en.wikipedia.org/wiki/Perceptual_hashing

The 18 GB is for just the hashes. The dataset is several terabytes.

A bloom filter is useless, as it doesn't let you do searches within an edit distance. Basically, I use a BK-tree of perceptual hashes (https://en.wikipedia.org/wiki/Perceptual_hashing). Then, I can find similar images by searching within a certain edit-distance.

Basically, the end result is a system that functions very similarly to how google's reverse image search works.

I used a google paper's approach in a mosaic competition. I didn't end up submitting it, but I got it working.

It uses locality sensitive hashing to hash vectors into buckets. These buckets are a subset of the total set of items. It worked with similar images of a small size when I used it, but I didn't have many images.

In my case, the vectors were just the rgb values of the down-sampled image.

Reply on news.ycombinator.com