Finding the same image twice

Ask a library of 200,000 photographs whether it already contains the picture in your hand and the answer depends on what counts as the same image. The file may have been re-encoded, resized, colour-graded or cropped, so its bytes no longer match even though a person would recognise the source photograph.

This is the second article in a series on image search. The first one covered the text path: building a searchable document, fusing BM25 with pgvector and handling candidate caps. This article removes text from the problem and uses a different index in the same PostgreSQL instance, with a different definition of correctness.

The basic algorithm works well on ordinary photographs, but a common catalogue style exposes an assumption that matters in production.

"The same image" needs 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 automatically during ingestion. A false positive interrupts the upload, so this path is deliberately conservative and covers 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.

The three jobs can share an index and query engine, but they need different thresholds.

The table also suggests two useful distinctions.

A byte hash answers a different question. MD5 tells us whether this is the same file, which is useful at upload time but does not cover transformed copies.

Embeddings alone are a poor fit for deduplication. A vision embedding is trained to place semantically similar images near each other, so "the same photograph, re-encoded" and "a different photograph of the same subject" can both look like good matches. That generalisation helps normal search but creates false positives between different SKUs photographed on the same background.

We therefore use a cheap structural method, which is mostly insensitive to meaning, to generate candidates and use semantic information only as part of verification.

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.

We use a DCT because the two simpler perceptual hashes are less robust for this job. An average hash thresholds pixels against mean brightness, so contrast adjustments affect it easily. A difference hash compares neighbouring pixels, which handles brightness better but struggles with gradients. The DCT costs more arithmetic but separates coarse structure from fine detail explicitly, allowing us to choose which coefficients to keep.

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.

Hashing regions as well as the full image

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.

Searching a space that has no index

Given a query hash and six rows per asset, we need every row within a Hamming distance such as 12 bits. A B-tree cannot answer that directly because numeric order has no useful relationship to Hamming distance, so WHERE hamming(phash, $1) <= 12 requires a sequential scan over all tiles.

Multi-index hashing turns this into indexed equality lookups. Split each 64-bit hash into four 16-bit chunks stored in indexed columns. If two hashes differ in at most three bits, those differences cannot touch all four chunks, so at least one chunk must be identical. The guarantee stops beyond that distance, which is why this remains only one candidate source.

Three implementation details mattered in practice.

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.

Record the candidate cap. Stage A stops at 2,000 candidates ordered by exact distance. The verification stage only narrows that set, but the cap still has a recall cost and needs to be included in completeness reporting, as described in the first article.

Where catalogue photography breaks the assumption

Perceptual hashing assumes that images contain enough structure to compare. Catalogue photography on a clean white background weakens that assumption because most of each frame is uniform. The DCT of "mostly white with a small object in the middle" is dominated by near-zero coefficients, so the median threshold may split noise rather than useful structure and place different products within a few bits of each other.

This does not produce an exception. It appears as one catalogue reporting poor duplicate suggestions while other libraries and tests behave normally. The distance is computed correctly; the image distribution has simply violated an assumption behind the metric. Tests therefore need examples from the photographic styles present in the real corpus, not only generic photographs.

Lowering the global threshold would reduce recall for ordinary photographs, so we classify this image shape and tighten thresholds 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 more general lesson is that a similarity threshold depends on the image pair and the corpus. When a library has a dominant photographic style, a single global constant is unlikely to provide the same precision across all assets. Measuring variance and edge density at ingestion gives us a cheap way to adjust for that style.

Three candidate sources, one result

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.

Three details are worth making explicit.

The thumbnail vector constrains the vision embedding. Source C is the only one that survives a hard crop, but it can also return a different photograph of the same subject. A candidate must therefore pass both a semantic cosine threshold and a structural thumbnail-distance threshold. A genuine crop usually remains structurally close, while a new photograph often does not.

Keep the limit visible to the ANN scan. The vision query uses ORDER BY clip_vector <=> $1 LIMIT 50, with the distance filter applied afterwards. Adding AND distance <= x appears tighter but prevents the HNSW index scan in this query shape. As with the BM25 row bound in the first article, the executor needs to see the limit to use the approximate index effectively.

Record which comparisons ran. A vector-only match carries a sentinel Hamming distance of -1 and a vision-only match carries -2, rather than a plausible value. Confidence can then use a formula appropriate to the available evidence, and later debugging can distinguish a skipped comparison from a measured distance.

Tolerance depends on the use case

The same detection engine serves jobs with different risk profiles. During ingestion, a false positive interrupts an upload, so the system should flag only near-exact copies. In interactive search, users can inspect noisy results themselves, so the threshold can favour recall. One threshold cannot serve both cases well.

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.

The bend at 10 preserves the old ingestion constants exactly. When replacing hard-coded values with a tunable curve, an anchor at the previous defaults provides a known compatibility point and makes changes elsewhere on the range easier to evaluate.

Cost and current limits

Most of the cost is paid at ingestion. ImageMagick opens the image, creates six 256-pixel tiles, converts them to 32 by 32 greyscale inputs for the DCTs, and produces a 16 by 16 thumbnail for the vector and image statistics. The work is CPU-bound and runs on a queue rather than in the upload request. Its stored output is relatively small: six rows of eight integers, one 256-dimensional vector and one optional 768-dimensional vector.

Doing more work once at ingestion keeps queries to four indexed equality lookups, two approximate-nearest-neighbour scans and a few thousand bit_count calls. That makes "is this already in the library?" practical as a synchronous query on a 200,000-asset library.

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.

Each limitation can be addressed with more indexing and computation, but the current system reports only the transformations it is designed to cover so users do not treat the duplicate check as stronger than it is.

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 search serves twenty languages, including why the index name, language predicate and text configuration have to fall back together.

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.