Структурное хеширование пиксель-арта: ускорение в миллион раз

Почему структурное хеширование пиксель-арта — это прорыв

Представьте: нужно проверить, не является ли новое изображение копией одного из десяти миллионов уже существующих. Наивный подход занимает девять дней на одну проверку. Структурное хеширование пиксель-арта решает ту же задачу за одну секунду. В этой статье я расскажу, как устроен этот алгоритм, и покажу, как применить его в ваших проектах на Python.

Проблема: каждая публикация — это потенциальная копия

Pixagram — социальная сеть пиксель-арта с маркетплейсом на блокчейне. Каждое новое произведение нужно проверять на совпадение с уже существующими — не по байтам, а по целой таксономии плагиата: перекраска, экспорт в 2×, «оригинал» со сдвинутым пикселем, уменьшенная палитра, негатив, репост в половинном размере. Это задача поиска почти дубликатов, а не распознавания образов в духе нейросетей.

Наивный метод и его цена

Наивный подход — сравнить попиксельно два изображения. Но прямое сравнение не работает даже при лёгкой перекраске. Чтобы учесть инвариантности, приходится перебирать масштабы и нормализации: примерно 120 проходов на пару. Для двух изображений 512×512 это около 80 миллисекунд. А против базы в 10 миллионов изображений одна проверка новой картинки требует девяти дней процессорного времени. Неприемлемо.

Структурный метод: 115 наносекунд на пару

Структурный метод сравнивает два предвычисленных ключа по 1024 байта за 115 наносекунд. Для той же базы — около 1,1 секунды на всю проверку, а с использованием BK-дерева — менее секунды. Ускорение в 700 000 раз достигается не магией, а сменой подхода: все инвариантности, которые наивный метод ищет на каждом запросе, мы оплачиваем один раз при вычислении хеша.

Почему стандартные хеши не подходят

Криптографические хеши (SHA, MD5) обладают лавинным эффектом: изменение одного пикселя полностью меняет дайджест. Они идеальны для проверки целостности, но бесполезны для поиска похожих изображений — нам нужно, чтобы расстояние между хешами соответствовало расстоянию между изображениями.

Перцептивные хеши для фотографий (aHash, dHash, pHash) используют размытие, уменьшение размера и DCT — это хорошо для непрерывных фотографий, но пиксель-арт квантован: ≤256 плоских цветов, жёсткие границы в 1 пиксель. Размытие разрушает суть пиксель-арта. Поэтому мы создали хеш, подходящий именно этому медиуму.

Идея 1: канонизация — убираем лишние вариации

Перед хешированием изображение приводится к канонической форме: палитра дедуплицируется, пустые записи удаляются, полностью прозрачные пиксели схлопываются, палитра сортируется по яркости, а каждый пиксель перекодируется в его ранг яркости. Это автоматически нейтрализует целые классы атак:

• Порядок хранения палитры не важен — одинаковое искусство даёт одинаковый хеш.
• Любая монотонная перекраска (яркость, контраст, большинство оттенков) сохраняет порядок яркости, поэтому индексный слой бит-в-бит идентичен. Изменения остаются только в сигнатуре палитры, где их можно прочитать.
• Целочисленные экспорты (2×, 3×, 4×) обнаруживаются через НОД длин серий и отменяются. Экспорт 2× хешируется так же, как оригинал.

Идея 2: код Грея — операция с палитрой стоит один бит

Если удалить или объединить запись палитры, все ранги выше сдвигаются на единицу. В двоичном коде сдвиг на ±1 может изменить много битов (7 → 8 меняет четыре). В коде Грея сдвиг на ±1 меняет ровно один бит:

def gray(b):
    """Бинарный отражённый код Грея: соседние значения отличаются одним битом."""
    return b ^ (b >> 1)

Таким образом, объединение оттенка стоит расстояния Хэмминга, пропорционального тому, как часто этот оттенок использовался — плавная деградация вместо лавины.

Идея 3: слои — каждый тип правки повреждает только один слой

Хеш — это не один дайджест, а стек независимых сигнатур:

• палитра (с лог-квантованными частотами использования, чтобы отличать объединение рабочего оттенка от удаления акцентного);
• дайджесты тайлов 16×16 с точным FNV-1a для каждого тайла (правка одного пикселя меняет один тайл, и его можно точно указать);
• слой границ — счётчики переходов между индексами;
• средние цвета супертайлов 32×32;
• глобальная сигнатура 1024 байта, не зависящая от разрешения — ключ для сравнения за 115 нс.

Слой границ мы сделали на основе подсчёта переходов, а не алгоритма Канни. Канни ищет границы в непрерывных изображениях, а в пиксель-арте границы очевидны: каждая пара соседних пикселей с разными рангами и есть граница. Подсчёт переходов даёт преимущества Канни без порогов и размытия.

Идея 4: разделение анализа изображения и анализа хеша

Архитектура разделена на две части. Функция compute() — анализатор изображения, единственное место, где читаются пиксели. Функция compare() отвечает на вопрос «насколько похожи», а diagnose() — анализатор хеша — отвечает на вопрос «что изменилось», используя только два хеша:

затемнить на 25%        → Перекраска: яркость −0.08, контраст −0.25
добавить +60 красного   → Перекраска: оттенок [r+0.19, g−0.05, b−0.05]
изменён 1 пиксель       → Локальная правка: тайлы 1/24, bbox(2,1)–(2,1)
объединить 6→5 цветов   → Уменьшение палитры: цветов −1 (1 часто используемый)
негатив                 → Инверсия: порядок яркости обратный
экспорт 2×              → Изменение масштаба: общий 1.000

Обратите внимание на первую строку: затемнение на 25% — это контраст −0.25, и анализатор восстановил точный коэффициент фильтра по выравниванию палитры, не видя самих изображений. Векторная модель дала бы косинусную близость 0.93 и плечами пожала бы, а хеш даёт отчёт, на основе которого модератор может принять решение.

Практические результаты

Замеры на одном vCPU (Rust, -O):

• compute() для 96×64: 153 мкс, 6500 хешей/с
• compute() для 512×512: 6.4 мс, 157 хешей/с
• полный compare(): 966 нс, ~1 млн пар/с
• полный diagnose(): 4.0 мкс, 250 тыс. отчётов/с
• глобальный ключ 1024 байта, Хэмминг: 115 нс, ~9 млн пар/с
• наивное сравнение 512×512 RGBA (одна попытка): 0.66 мс

Код скалярный, без SIMD — с AVX-512 скорость ещё выше. Для сравнения: нейросетевые эмбеддинги тратят миллиарды операций на кодирование одного изображения, а наш кодировщик — около миллиона целочисленных операций. Ключ — это 1024 байта, которые можно инспектировать, а не непрозрачный вектор.

Попробуйте сами — вся лаборатория в одном HTML-файле

Весь пайплайн портирован на JavaScript без зависимостей и упакован в одностраничную лабораторию: перетащите два изображения (или сгенерируйте сценарии правок), прочитайте вердикт и увидите анализ прямо на изображении — изменённые тайлы обведены, ограничивающая рамка пунктирная, зеркальные тайлы помечены.

Порт байт-в-байт идентичен Rust-версии: тестовый корпус сериализуется в те же 1649 байт, сверяется с эталоном, все вердикты воспроизводятся с точностью до трёх знаков. Что скажет браузер, то скажет и продакшн.

Живое демо: {LIVE_DEMO_URL}. Исходный код (Rust + лаборатория): {SOURCE_URL}.

Что пока не работает

Честность дороже возвратов. Кадрирование и переводы не выравниваются (шейдинг тайлов — следующий шаг). Фильтры, нарушающие порядок яркости (кроме негатива), ломают ранговый слой, хотя цветовые слои совпадают. Ограничение ≤256 цветов — особенность медиума, а не метода. Пороги вердиктов настраивались на синтетических правках — настройка на реальных парах — следующий этап.

Лицензия и выводы

Лицензия MIT, © 2026 Pixagram SA — берите, ломайте, расскажите, что нашли.

Мораль: скорость была не в сравнении, а в отказе сравнивать то, что уже ответила канонизация. Ускорение в миллион раз — это то, что остаётся, когда перестаёшь повторяться.

Автор: Матиас Аффольтер, сооснователь и председатель Pixagram SA. Сеть Pixa — форк HIVE/STEEM, хранящий пиксель-арт полностью в блокчейне, поэтому каждый байт механизма происхождения должен оправдывать своё место.

Что делать прямо сейчас

Если вы работаете с пиксель-артом и сталкиваетесь с поиском копий, попробуйте реализовать структурное хеширование в своём проекте. Начните с простого: канонизируйте палитру, отсортируйте её по яркости, используйте код Грея для рангов. Уже это даст огромный выигрыш по сравнению с попиксельным сравнением. А если нужна готовая библиотека — используйте Rust-модуль или JavaScript-лабораторию из статьи.