Finding the same image twice

Ask a library of 200,000 photographs whether it already contains the picture in your hand and you are asking a question with no exact answer. The file you are holding has been re-encoded, resized for the web, colour-graded by a different retoucher, and cropped square for Instagram. Not one byte matches. Every human who looks at the two says "yes, obviously, same photo."

This is the second article in a series on how image search actually works. The first one covered the text path: manufacturing a searchable document, fusing BM25 with pgvector, guaranteeing recall under caps. This one removes text from the problem entirely. Same library, same PostgreSQL instance, completely different index, and a different definition of correct.

It is also the subsystem where the textbook algorithm most obviously fails on real data, which is the interesting part.

Part 1: "The same image" is not a definition

Before any algorithm, you need a policy. Here are six things that happen to an image inside an organisation, and there is no single technique that handles all of them.

Which rows matter is not a technical question. Inside a DAM the same engine answers three jobs with three different definitions of correct.

"Did we already upload this?" runs at ingestion, unprompted, on every file. A false positive here interrupts somebody's upload with a wrong accusation, so it must be conservative to the point of pedantry: rows 1 to 3 only.

"Find the rest of this shoot." is a human at a keyboard who wants recall and will discard the noise themselves. Rows 1 to 5, generously.

"Have we licensed this before?" is the expensive one. Somebody is about to pay for a stock image, and the copy already in the library may have been cropped, re-graded and re-exported beyond recognition. A miss here costs real money, so it wants maximum recall and a human confirmation step.

Same index, same query engine, three thresholds. Hold that thought; it comes back at the end.

Two further conclusions fall out of the table immediately.

A byte hash is not a weak solution, it is a different question. MD5 answers "is this the same file", which is worth knowing at upload time and answers none of the six rows above except by accident.

Embeddings alone are the wrong tool here, despite being the fashionable one. A vision embedding is trained to put semantically similar images near each other, and "the same photograph, re-encoded" and "a different photograph of the same subject" are both semantically similar. For search, that generalisation is the feature. For deduplication, it is precisely the bug: the model will happily tell you that two different SKUs shot on the same white sweep are neighbours, because as far as the model is concerned they are.

So the architecture that follows is a compromise with a shape: a cheap structural method that is nearly blind to meaning, used to generate candidates, and a semantic method used only to verify them.

Part 2: A hash that survives re-encoding

Perceptual hashing solves row 1 to row 3 of that table with an idea from image compression: throw away everything a JPEG encoder would also throw away, and hash what is left.

It is worth being clear about why the DCT is in there at all, because two simpler perceptual hashes are widely used and both are worse for this job. An average hash thresholds pixels against the mean brightness, which is fast and falls apart under any contrast adjustment. A difference hash compares each pixel to its neighbour, which handles brightness well and gradients badly. The DCT variant costs more arithmetic and buys robustness where it matters: it separates coarse structure from fine detail explicitly, so discarding "everything a compressor would discard" becomes a deliberate choice of which coefficients to keep rather than a side effect of downsampling.

The result is a 63-bit integer where similar images produce similar integers, and "similar" has a precise meaning: the Hamming distance, the number of bit positions where two hashes disagree. A re-encode moves it by one or two bits. A resize moves it by a handful. A crop moves it enormously, which is the next problem.

Part 3: One hash per image is one hash too few

Crop 20% off an image and every coefficient in that DCT changes, because the pixels feeding it have all moved. The hash is unrecognisable, even though four fifths of the picture is identical.

The fix is to stop treating an image as one thing. freedam hashes six regions independently: the full frame centre-cropped square, the central 70%, and the four quadrants at 60% each.

Part 4: Searching a space that has no index

Now the hard part. You have a query hash and a table with six rows per asset. You need every row within, say, 12 bits. There is no index for that. B-trees order values; Hamming distance has nothing to do with numeric order. WHERE hamming(phash, $1) <= 12 is a sequential scan over every tile of every asset, forever.

Multi-index hashing is the standard escape, and it is a genuinely elegant piece of pigeonhole reasoning. Split each 64-bit hash into four 16-bit chunks, stored as four indexed columns. If two hashes differ in at most 3 bits, those 3 bits cannot touch all four chunks, so at least one chunk must be bit-for-bit identical. An unindexable radius search becomes four indexed equality lookups.

Three implementation notes worth stealing.

Compute the distance in the database, once. A tiny SQL function keeps the arithmetic next to the data: bit_count((a # b)::bit(64)), declared IMMUTABLE STRICT PARALLEL SAFE so the planner is free to parallelise it and fold it into a filter rather than materialising rows into your application.

Fan out over tiles with UNION ALL, then collapse per asset. Six tiles produce six chunk lookups; the results are unioned, distances computed, and grouped down to one row per asset carrying MIN(hd) and the tile that produced it. One asset that matches on four tiles should be one strong result, not four weak ones.

Understand what a chunk lookup actually costs. Sixteen bits gives 65,536 possible values per chunk column. On a library of uniform random hashes, one chunk equality lookup returns roughly one row in 65,536, which is why this works. Real hashes are not uniform. A corpus with many flat or near-identical regions produces chunk values that repeat thousands of times, and a query landing on one of those pays for every row it returns before a single distance has been computed. This is the same corpus-shape problem as the next section, arriving through a different door: the algorithm's cost model assumes a distribution your library may not have. If lookups are slow, measure the value distribution of c0 through c3 before you touch anything else.

Cap the candidate set and know what the cap means. Stage A stops at 2,000 candidates ordered by distance. That is a performance bound with a recall cost, and the honest framing is the one from the first article: a cap that nobody reports is a silent lie. Here the cap is safe because the ordering is by exact distance and the verification stage is strictly narrowing, but it is still a number that deserves to be written down.

Part 5: Where the textbook breaks, and what your corpus does to it

Now the part that no paper warns you about.

Perceptual hashing assumes images carry structure. Feed it a catalogue of product photography shot on a clean white sweep and that assumption collapses. Most of every frame is the same white. The DCT of "mostly uniform with a small object in the middle" is dominated by near-zero coefficients, the median threshold splits noise rather than signal, and two completely different products land within a few bits of each other. At an interactive tolerance the system confidently reports that a kettle is a near-duplicate of a toaster.

The failure has a signature worth recognising, because it never arrives as an exception. It arrives as a support message saying the duplicate warnings are "wrong all the time", from one customer, while every other customer is happy and every test passes. Perceptual hashing has no error state for this. It returns a confident small number, and the number is honestly computed; it is the assumption behind the number that has stopped holding. If you only look for bugs where something crashed, you will never find it.

The instinct is to lower the global threshold. That is the wrong fix: it breaks detection for the photographs that were working. The right fix is to notice that this image is the dangerous kind and tighten only for it.

freedam measures two cheap statistics on the 16 by 16 greyscale thumbnail, before normalising it: the variance of the pixel values, and the edge density from gradient magnitude.

The generalisable lesson is not "handle white backgrounds". It is that a similarity threshold is a property of the pair, not of the system, and if your corpus has a dominant photographic style then a single global constant is guaranteed to be wrong for it. Measuring two numbers per image at ingestion is a cheap way to buy back the precision that the style took away.

Part 6: Three candidate sources, one verdict

Because the pigeonhole guarantee stops at radius 3 and because crops defeat structure entirely, hashing alone leaves holes. freedam runs three candidate generators in parallel, and each one exists because of a specific, named failure of the others.

Two details in there are worth pulling out.

The vision embedding is fenced in by the thumbnail vector. Source C is the only one that survives a hard crop, and also the only one that will cheerfully return a different photograph of the same subject. So a C candidate must pass two tests: cosine distance within the semantic threshold, and thumbnail L2 distance within a structural threshold. Semantics proposes, structure disposes. A genuine crop stays structurally close; a re-shoot does not.

Give the ANN scan the shape it wants. The vision query is written as ORDER BY clip_vector <=> $1 LIMIT 50 with no distance predicate in the WHERE clause, and the distance filter is applied afterwards. Adding AND distance <= x to that query looks tighter and makes it slower, because the filter blocks the HNSW index scan. This is the same lesson as the BM25 row bound from the first article, in a different index: an approximate index only performs when the executor can see the limit.

A match that skipped a stage says so. A vector-only match carries a sentinel Hamming distance of -1 and a vision-only match carries -2, rather than a plausible-looking number. Confidence is then computed by a formula appropriate to the evidence that actually exists. Inventing a distance for a comparison you never ran is how a result set becomes untrustworthy in a way nobody can debug six months later.

Part 7: Tolerance is a product decision, not a constant

The last piece is the one most systems get wrong by having no opinion at all.

The same detection engine serves two jobs with opposite risk profiles. At ingestion, a false positive interrupts an upload and annoys someone, so it should flag only near-exact copies. In interactive search, a false negative means the user concludes the feature does not work, so it should be generous. One threshold cannot serve both.

So there is a single tolerance on a 0 to 50 scale, and everything else is derived from it. Five threshold families move together along a piecewise-linear curve with anchors at 0, 10 and 50.

That bend deserves a note, because it is a pattern worth reusing. When you replace a set of hard-coded constants with a tunable curve, put an anchor exactly where the old constants were. Then the new system provably reproduces the old behaviour at one point on the dial, and every argument about the new range is about the range, not about whether you broke what already worked.

Part 8: What it costs, and what it still cannot do

Everything above is paid for at ingestion. Each image is opened by ImageMagick, cropped into six tiles at 256 pixels, converted to 32 by 32 greyscale six times, put through six two-dimensional DCTs, and reduced once more to a 16 by 16 thumbnail for the vector and the two statistics. That is a real cost per asset, it is CPU-bound, and it belongs on a queue rather than in the request that uploaded the file. What lands in the database is small: six rows of eight integers, one 256-dimension vector, one optional 768-dimension vector.

The asymmetry is the point. Indexing is expensive and happens once. Querying is four indexed equality lookups, two approximate-nearest-neighbour scans and a few thousand bit_count calls, which is why "is this already in the library?" can run synchronously on a 200,000-asset library while somebody waits.

Being honest about the limits matters as much as the capabilities, so:

Rotation and mirroring defeat it. A DCT hash of a flipped image has no relationship to the original. Small rotations of a degree or two survive; 90 degrees does not, and neither does a horizontal flip. Systems that need this hash the transformed variants too, at a multiple of the indexing cost. We do not, because in a brand library a mirrored asset is usually a deliberately different asset.

Heavy composites are out of scope. One source photograph placed inside a designed layout, with type over it and a colour treatment on top, is not a near-duplicate of the photograph by any of these measures. Finding it needs region-level matching, which is a different and much more expensive architecture.

It is per-image, not per-region. The tiles are a fixed grid, not a detector. They approximate crop tolerance well and object-level matching not at all.

Video is handled by proxy, not directly. Frames can be hashed, but the shape of the question changes, because "the same video" involves time.

Any of these is buildable. None of them is free, and a system that pretends its limits do not exist produces the worst outcome available: a user who trusts a duplicate check that is quietly blind to half the ways their team copies images.

What we would tell anyone building this

• Decide what "the same image" means before you pick an algorithm. Write the transform table. The row you decide must not match is the one that determines the architecture.
• Do not use embeddings alone for deduplication. They are trained to generalise across exactly the distinction you are trying to make. Use them to verify or to rescue crops, fenced in by a structural check.
• Hash regions, not images. Tiles turn a fragile all-or-nothing comparison into a vote, and the tile that matched tells you how the two images are related.
• Know where your pigeonhole guarantee stops. Multi-index hashing is exact below radius m and heuristic above it. If your thresholds are above it, say so and add a second source rather than pretending.
• A threshold is a property of the corpus. Two statistics per image at ingestion beat one global constant tuned on a sample that did not include your customer's catalogue.
• Let the index have its shape. An ANN scan needs a visible limit; a filter that looks like a tightening can be a full scan in disguise.
• Never invent a distance you did not measure. Sentinels and evidence-appropriate scoring keep a result set debuggable.
• Expose one control, derive the rest. Users have one question ("how picky should this be?"), and every pipeline stage needs a different number to answer it.

Where this lives in the product

Near-duplicate detection runs at ingestion, where it flags likely copies before they enter the library, and on demand as visual similarity search and duplicate detection. Everything above runs inside the same PostgreSQL instance that stores the assets, on pgvector and four ordinary B-tree indexes, which is part of what makes freedam practical to self-host.

Next in this series: how a single search index serves twenty languages, and why falling back the index name without falling back the text configuration quietly breaks an entire corpus.

If you would rather see it than read about it, try the demo and upload a cropped, re-saved copy of an image that is already in the library.