How We Made Image Copy-Detection ~1,000,000x Faster — by Refusing to Look at Pixels
The story of Pixagram's 1024-byte structural hashing technique that evaluates artwork similarity in 115 nanoseconds without neural networks.
Stock photo for illustration only, not from the actual event
- A 1024-byte structural hashing system for pixel art evaluates artwork similarity in 115 nanoseconds.
- Cuts verification time down from the 9-day naive pixel-comparison method per single mint.
- Diagnoses exact image edits without relying on heavy neural networks or embedding models.
- Ported completely to dependency-free JavaScript for an interactive browser-based lab environment.
The best computation is the one you never repeat. For Pixagram, a pixel-art social network featuring an on-chain marketplace, every newly minted artwork must be checked against millions of existing pieces. This check goes far beyond basic byte-equality; it must detect near-theft scenarios including recolors, 2x exports, single-pixel shifts, reduced color palettes, negative inversions, and half-size reposts.
The naive approach reads both images and compares them pixel by pixel. The true cost of this method is hidden and severe, breaking instantly upon the first recolor. To answer similarity queries pixel-wise, one must search through various invariances such as plausible rescaling factors and monotonic recolor normalizations across roughly 120 passes. Against a corpus of 10 million artworks, a single incoming mint would cost approximately 9 CPU days.
Conversely, the structural method compares two precomputed 1024-byte keys in 115 nanoseconds. The same corpus searched on a single core takes about 1.1 seconds via brute-force, dropping to sub-second speeds once keys reside in a BK-tree. This achieves a speedup of roughly 700,000x to 1,000,000x, not through magic, but by paying for all query-time invariances once at hash-generation time.
This architectural shift relies on a classic compute-time trade-off. By frontloading heavy analytical work into the initial upload hash phase, the system avoids expensive runtime comparisons. This design shines specifically in the domain of pixel art, where strict grid constraints and limited palettes allow for precise mathematical modeling unlike continuous photographic images.
Stock photo for illustration only, not from the actual event
Before arriving at this solution, the team evaluated two prior art families and their distinct failures:
- Cryptographic hashes are built for avalanche effects where a single flipped byte alters the entire digest, making them useless for similarity matching.
- Photographic perceptual hashes (aHash/dHash/pHash) rely on blurring, downsampling, and DCTs designed for continuous photos. Pixel art relies on hard 1-pixel edges and exact index relationships, meaning Gaussian blur destroys the medium rather than summarizing it.
Consequently, they engineered a custom hash tailored to the medium. Before hashing, images are reduced to a canonical form: palettes are deduplicated, unused entries stripped, fully transparent pixels collapsed, and colors sorted by luminance rank.
The resulting hash is not a single digest but a stack of independent signatures. It includes palette populations, 16x16 tile digests with exact FNV-1a checksums to isolate single-pixel edits, an edge layer tracking index-transition counts, 32x32 supertile average colors, and a fixed 1024-byte global signature serving as the database key.
"An embedding model gives you a cosine similarity of 0.93 and a shrug; the hash gives you a report a moderator can act on — and a court can read."
Pixagram Development TeamSource:
Dev.to
Found something wrong in this article? Report an issue with this article
Comments
Leave a Comment