Simple, Fast, and Scalable Reverse Image Search Using Perceptual Hashes and DynamoDB

Christopher Bong16 Oct 2022

Problem

Canva stores a fast-growing collection of user media. Exact file hashes such as SHA512 or MD5 change completely after one pixel, a watermark or a quality change, so they only find byte-identical files. The team needed a lookup that returns all stored images within a small visual distance of a query image, at the scale of billions of images. Uses: storage deduplication and moderation takedowns.

Example from the article: an image and the same image with a small watermark have a perceptual-hash Hamming distance of 2, while their MD5 hashes are fully different.

Solution in brief

Compute a perceptual hash per image and search by Hamming distance with multi-index hashing: split each hash into segments and store every segment as a DynamoDB partition key. A query runs one lookup per segment, then filters the merged candidates by exact Hamming distance. At rollout the system was unusable until the split count was reduced and low-complexity images were left out of hashing.

Questions this case answers
  • How to retrieve all stored items within a small Hamming distance of a query hash at billions-of-items scale with millisecond latency
  • How to keep a key-value-store index for approximate matching from returning huge candidate sets because of skewed or low-entropy keys
  • How to find visually duplicate or lightly edited images among billions of stored files in tens of milliseconds?
  • How to choose the number of hash segments in multi-index hashing so that queries stay cheap?

Tools and methods

  • Perceptual hashing (pHash) — hash from pixel content; similar images differ in few positions
  • Hamming distance — number of differing positions between two hashes; the match criterion
  • Multi-index hashing (Norouzi, 2012) — splits hashes into segments so a distance threshold needs only exact-match lookups
  • DynamoDB — one row per hash segment: partition key = indexed segment, sort key = image id
Continue reading — it's free

Google or a one-time email code. No password.