Clickbait, cashed out: content-addressed perceptual hashing for pixel art — Rust, WebAssembly, and the arithmetic that turns hours into milliseconds.
Yes, the title is clickbait. Here is the unusual part: by the end of this article it will be paid in full, with the arithmetic shown. The trick is not a faster kernel, a bigger GPU, or a secret SIMD incantation. The trick is a refusal.
The fastest way to compare two images is to have compared them already.
That maxim is the whole architecture. Everything else is engineering — and the engineering is where it gets fun.
The problem: every upload is a question
We build Pixagram, a social network and marketplace for pixel art. Every upload must answer a question before it goes anywhere near a feed or a listing: have we seen this artwork before — or an edit of it? Not the same file; files are trivial. The same artwork: re-exported at 2×, recolored, background swapped to transparent, cropped by two pixels, re-rendered by hand at another resolution. Copyminting — republishing someone else's piece with cosmetic changes — is exactly as cheap as the cheapest edit your detector misses.
Now the cost model. Say the corpus holds ten million images and a decent structural comparison of two decoded rasters costs five milliseconds — generous, once you count fetching and decoding the stored side. One upload, checked naively against everything:
10,000,000 pairs × 5 ms ≈ 14 hours per upload
Fourteen hours. Per image. The naive shape of the problem is not slow — it is absent. No amount of kernel tuning rescues an O(N × pixels) architecture; you have to change what a comparison is.
Step one: stop looking at pixels
The move is old and honorable — content addressing — applied with prejudice. Each image is decomposed once, at upload, into a structured hash: a few kilobytes that carry the palette, the arrangement, the color field, the edge structure, even a tiny contour map of the composition. From that moment on, no comparison ever touches a pixel again. Every question the platform asks is answered by reading hashes.
But "a hash" answering "is this a near-duplicate?" with one distance number is throwing away the interesting part. Different questions have different prices, so pixa-image-hash answers at three price points, all derived from the same stored bytes:
Tier 1 — the content key. A 32-byte SHA-256 identity with a twist: the hash normalizes integer nearest-neighbour upscales before encoding and stores the provenance (source dimensions, detected scale) in its own little compartment — and the content key is computed with that compartment spliced out. Result: a 1× original and its 2× re-export produce the same key. Dedup tier one is a hashmap probe. Cost: ~100 nanoseconds, O(1).
Tier 2 — the index code. A 256-bit code compared by Hamming distance — XOR and popcount over 32 bytes, single-digit nanoseconds per candidate, and friendly to any ANN index you like. Calibration puts the recall radius at R = 48: integer upscales, monotone recolors, and same-palette edits land at distance 0; unrelated art stays outside with zero false admissions on our calibration corpus. Cost of a full linear scan over ten million codes: ~20 ms. With an index: far less.
Tier 3 — the arbiter. For the shortlist that survives, diagnose reads both hashes and produces a verdict from sixteen classes — Recolored, Rescaled, LocallyEdited, BackgroundSwapped, Rerendered, Unrelated… — with a confidence and the evidence behind the call: which tiles changed and their bounding box, what the palette did, how the background detector voted, how well the contour maps align. Cost: microseconds. It reads bytes, not pixels.
The same upload, re-priced:
1 hashmap probe ≈ 0.0001 ms
10M popcounts (worst) ≈ 20 ms
~5 diagnoses ≈ 0.25 ms
--------------
≈ 20 ms — versus 14 hours
Fourteen hours to twenty milliseconds is a factor of about 2.5 million. There is the title, paid — and notice where the million lives. Not in a kernel. In an architecture that lets the cheap question run first and the expensive question run rarely. Hashing itself costs ~0.35 ms for a 64×64 sprite native, ~1.7 ms for a 256×256 through wasm — paid once per image, ever.
Why not just use pHash?
Because photographic perceptual hashes were built for photographs. pHash and its cousins live on DCT coefficients and gradient statistics over smooth natural images. Pixel art violates their premises from the first pixel: it is flat color fields with hard edges, where a twelve-color palette is a first-class object, a one-pixel outline is a decision, and nearest-neighbour scaling is lossless re-publication. A photographic hash sees noise where a pixel artist sees intent — and worse, it sees similarity where an artist sees theft, because two sprites sharing a background and a vibe compress to nearly the same DCT signature.
So the hash speaks the medium's own grammar. Colors become a luminance-ranked palette; pixels become palette indices; the raster becomes 16×16 tiles (an exact digest plus average-rank cells — so a one-pixel edit disturbs only its own tile, and the differ can literally draw a box around your edit), 32×32 supertiles of average color, resolution-independent global grids for cross-size comparison, and — since format v5 — a ~140-byte contour bitmap from an all-integer Canny, which is what lets the hash recognize the same composition re-executed as a different raster. Total: about 2.9 KB for a 128×128 sprite.
Three scars from the trenches
A release is a collection of survived surprises. Three worth your time:
1. Determinism is a feature you build, not a property you get. The hash runs in native Rust, in WebAssembly, and in a JavaScript mirror — and stored hashes are forever, so all three must produce byte-identical output. Floating point said no. Rust's f32 entropy math and JavaScript's f64 Math.log2 disagreed on 416 of the 268 million reachable input counts — four hundred and sixteen quiet little landmines. The fix: no floats in the hash path at all. The entropy and quantile boundaries were computed once, frozen as integer constant tables (canonized with their 59 boundaries that sit one or two counts off "true" math — determinism outranks purity), and the release gate now hashes an 87-image corpus through old and new builds and asserts byte equality. Not similarity. Equality.
2. Your metric can lie in exactly the direction attackers push. Storage uses Gray code — lovely property: values differing by ±1 differ by one bit. We scored similarity with Hamming distance over those Gray-coded bytes, which inherits a horrible converse: gray(0) and gray(255) also differ by one bit. Large jumps were systematically under-counted — precisely the transformations a copyminter reaches for. The demonstration that forced the fix: flip half the canvas from near-black to near-white, an edit visible from orbit, and the old metric scored it 0.91 color similarity. Un-Gray-code and score L1 instead: 0.65. Meanwhile an honest monotone recolor rose from 0.76 to 0.97. The scale finally orders edits by magnitude — and since only scoring changed, every stored hash remained valid without re-hashing.
3. Thresholds interact; redesign beats renumbering. On the new scale, a two-pixel crop suddenly cleared the 0.97 "this is a rescale" gate — crops and rescales had become indistinguishable by score alone. The separator was hiding in evidence the report already carried: a true whole-canvas rescale preserves aspect ratio exactly (checked with a u64 integer cross-product — no float ratios, thank you, lesson one) or leaves the projection profiles unshifted; a crop does neither. One redesigned gate later, the detector also fixed a bug the old version shipped with: 1.5× resamples that used to mislabel as "Reframed" now classify correctly, six for six.
Poke it yourself
The whole instrument fits in one HTML file — the analyser lab, with the wasm build embedded as base64. No server, no install: open it, drag two images in, and read the verdict, the per-channel bars, the dedup-tier line (content key + index distance against R = 48), and the contour overlay. The screenshot at the top of this article is that lab. One of its quieter lessons: load the recolor preset and watch the dedup row report content key: different, index distance: 0 — two tiers, two different questions, both right.
The honest fine print
A million-fold speedup deserves an equally sized disclaimer, so: this detects raster edits, not concepts — a from-scratch redraw of the same character is embedding-model territory (the contour layer covers one slice: the same composition re-rendered). It refuses images above 256 unique colors rather than pretending to be a photo hash. The index tier is deliberately blind to background swaps and inversions — those are the arbiter's job, and sizing your index otherwise will disappoint you. It is not a cryptographic authenticator; it raises the price of evasion, it does not prove provenance. And the 3.0.0 verdict thresholds were calibrated on a synthetic corpus — the mapping tables ship in the release notes precisely so real-corpus nudges stay one-liners.
Rust + WebAssembly, MIT, sixteen verdicts, three tiers, zero pixels touched after upload:
→ github.com/pixagram-blockchain/pixa-image-hash
The fastest comparison is the one you already made. Everything else is bookkeeping — done well.
Top comments (0)