https://phash.org/https://github.com/aetilius/pHash/blob/master/src/pHash.cpp:ph_dct_imagehashПродолжаю оценивать применимость этой штуки в поиске дубликатов и схожих вариаций картинок. Позволяет оценить непохожесть картинок по количеству отличающся бит в их хэшах, то бишь по расстоянию Хэмминга, popcnt(phash(A) ^ phash(B)).По запросу "phash PHP" Google находит две штуки.https://github.com/xwiz/phash/blob/master/phash.php Считает не phash, а ahash.https://github.com/jenssegers/imagehash/blob/master/src/Implementations/PerceptualHash.php +- оригинальный алгоритм, но фиксированной длины.PHP связка с libphash есть и в оригинальном проекте, но там файл-заметка EXPERIMENTAL в корне и файлы, судя по всему, не тронутые с 2013-ого. Да и libphash компилять надо, а у меня не скомпилялся, лол.Какого-то стандарта, судя по всему, нет.Мне было это дело интересно по-twick'ать, посмотреть на эффект от большей длины и посмотреть, насколько сложно это реализовать в JS, чтобы на сервер отправлять только готовый хэш. Написал своё.На счёт реализации, всё достаточно просто на самом деле.Втискиваем картинку в квадратный sample фиксированного размера, конвертируя цвета в серый;Считаем DCT как N · (C × sample × Cᵀ), где N и C матрицы с константными коэффицентами;Находим медиану для DCT[y,x], у которых y² + x² меньше некого threshold, но без DCT[0,0]; круглый low-pass фильтр;Обходим DCT[y,x] из того круга посекторно, в порядке возрастания удаления от центра, смотрим больше или нет текущий DCT[y,x], чем медиана, и результатами сравнения определяем биты phash. DCT[0,0] исключаем.То бишь, у меня пока так; php-vips для чтения картинок и матричного умножения.В какой-то степени первый пункт тут самая сложная часть; если добиваться библиотеко-инвариантого thumbnailing'а и учитывать rgb565, gray16, прочие разнообразые форматы пикселей, цветовые профиля и прозрачность (да, у нас есть такие картинки и это несколько влияет на результат).Отличия.В оригинальном phash для DCT берётся 32x32 sample'а и хэш считается по окну 8x8, то бишь длина хэша 64 бита. У меня окно круглое потому, что так больше свободы в выборе длины хэша; в частности, появляется возможность естественным образом определить хэши длиной в 64, 128 и 192 бита; без нужды отбрасывать DCT[y;x] соответствующие тому же сектору/изочастотной группе или оставлять байты полупустыми. Это, и мы не берём большие куски от групп более высокой частоты; 8x8 квадрат берёт вплоть до DCT[8;0] и DCT[0;8] по вертикали и по горизонтали, но в то же время и DCT[8;8], который про большую детализацию.
Поделал хэши с разными длинами и с разным размером sample'а. Data set'ы — 16112 Булочных и 136508 Ычановых картинок из тредов circa 999 последних страниц Якуевого архива. Наблюдения таковы.Большая часть дубликатов, полученных переужатием/изменением размера, находится на расстоянии 0 или — при длинных хэшах — достаточно близко к нему. Однако даже при 512-битном phash на расстоянии 0 встречаются и картинки с незначительными модификациями, хоть и редко.При этом некоторые изменения размера/переужатия, хоть чем дальше, тем куда реже, бывает находятся на значительно большем, чем 0, расстоянии друг от друга.16/512 — расстояние меж https://ii.yakuji.moe/b/src/1705971491904.jpg и https://ii.yakuji.moe/b/src/1688504889304.jpg28/512 — меж >>9388 и >>949640/512 — меж https://ii.yakuji.moe/b/src/1648398268154.jpg и https://ii.yakuji.moe/b/src/1572851490178.jpgНесмотря на большую визуальную схожесть, картинки с сэнсэем нашлись лишь расстоянии 40/512. Для сравнения, на расстоянии 40/512 можно обнаружить https://ii.yakuji.moe/b/src/1681308511905.jpg и https://ii.yakuji.moe/b/src/1683280427230.jpg.Куда хуже бывает с дубликатами, полученными, помимо scaleing'а, сдвигом, crop'ом или padding'ом.138/512 — >>15995 и >>18833148/512 — >>3380 и >>9520Примечательно, что на Ичане есть один некий юзер (ну, по выбору цвета для padding'а и по характеру картинок некий конкретный прослеживается), который очень любит делать такие модификации. У меня его otherwise одинаковые картинки all over the place в дельтах меж классами эквивалентности по достижимости.Например, https://ii.yakuji.moe/b/src/1673088974447.jpg, 1674079476839.jpg, 1676900847615.jpg, 1678044547885.jpg, 1695834706311.jpg, 1708415679326.jpg. Хотя меж некоторыми парами картинок из набора прямое расстояние и меньше 100/512, связным граф становится только при предельном прямом расстоянии меж индивидуальными хэшами-нодами 171/512. И это ещё не полный набор!Так что такого рода дубликаты содержимого, хотя и не всегда, оказываются почти наравне с вариациями/частичными изменениями содержимого.Например, меж >>3681 и >>4892 36/512, >>8513 >>8614 76/512, >>5390 >>5455 116/512, >>6377 >>6379 140/512, >>14826 >>14826 152/512, >>16709 >>16721 192/512.Так что в целом находимость сложных дубликатов и вариаций — среднее оптимистическое между значительностью измений и "как на синусоиду ляжет, лол".В связи с этм интересно, что картинки с одинаковыми блоками текста/интерфейса бывает отсыкивает не так уж и плохо даже при otherwise разном содержимом, судя по классам достижимости. Можно искать скришоты из ВН или игр, вариации ответов Порфирьича или посты с капчей похожей на "бувочбу".Начиная где-то с 170/512 появляются первые серьёзные ошибки — на одинаковом расстоянии оказываются совершенно разные картинки. На ичанском data set'е — где-то с 130/512. Поначалу редко, но ближе к 180/512 часто. При 200/512 классификация по достижимости разваливается, с каждой новой итерацией увеличения d/512 соединяя куда больше совершенно разных картинок, чем похожих. При 218/512 все 16112 картинок Булочного data set'а поглощаются одним классом.In so far, лечится соразмерным увеличением длины хэша и размера sample'а для DCT. Данные выше приведены для sample'а 128x128. Чем длиннее хэш, тем больше релевантных друг другу картинок находится до момента, когда начинаются ошибки.
Некоторые другие заметки, по самим данным.Из взятых 136508 ычанских картинок получается только 93121 уникальных хэша. 91213 классов по достижимости на дистанции 16, 87705 на дистанции 170, 64483 на дистанции 200.Встречаются картинки с прозрачностью, у sample'а которых средняя по альфа каналу 0. Интересно, что там такое.Вместо некоторых картинок в архиве HTML. Например, https://ii.yakuji.moe/b/src/1753093687170.jpg и https://ii.yakuji.moe/b/src/1601404535917.jpgВозможно, у https://ii.yakuji.moe/b/src/1672258318418.jpg файла bit rot.Из взятых 16112 Булочных картинок хэша 16043. 15995 классов по достижимости на дистанции 16, 15904 на дистанции 170, 14916 на дистанции 200. На порядок больше непохожих картинок.>>1006362> +- оригинальный алгоритм> и в оригинальном проектеВ английском смысле слова, не в русском.
Возможные пути к улучшению.В оригинале медиана берётся по всему 8x8 вырезке из DCT. У нас тоже по всему четверть-кругу. Можно попробовать брать медианы либо вплоть до текущего сектора включительно, чтобы высокие частоты не flip'или bit'ы низким, но низкие частоты, как и сейчас, могли подавлять высокие; либо брать эти медианы отдельно для каждого сектора, убирая зависимость вообще. Поможет? Сделает хуже? Dunno.Можно и дальше попробовать увеличивать длину хэша. Но. В https://github.com/aetilius/pHash/blob/master/src/pHash.cpp есть хэш на wavelet'е Marr'а. Берётся 512x512 sample, делается преобразование, по нему ходят окном, делают с ним ещё что-то, из этого чего-то берут медиану и по ней текущим окном определяют несколько бит хэша. Всего длина хэша 72 байта. Будет ли лучше работать, I wonder. В целом попробовать другие хэши на настолько же большом количестве бит.Сделать перед взятием DCT некое преобразование, которое даёт устойчивость к сдвигам и небольшим crop'ам. И уже по его результатам брать DCT. Но какое? в pHash.cpp некая вариация с преобразованием есть, но она про ротации, насколько я понимаю.Вместо одного бита больше/меньше медианы писать номер квадранта, куда попадает DCT компонента. Но в таком случае расстояние определяется сложнее, чем просто по-xor'ить и посчитать еденицы. Для приблизительного расстояния Хэмминга меж битовым строками у Postgres есть HNSFW HNSW индекс, а для строк с задаваемым размером символа вряд ли.Если вдруг интересно, могу выложить код, который пишет CSV c хэшами, и код, который кушает этот CSV и делает для каждого расстояния директории с симлинками на картинки для тех классов по достижимости, у которых появились новые члены. Можете попробовать и вы на своих данных.>>1006363> Ычановых картинок из тредов circa 999 последних страницПоследних в смысле latest.
>>1006366> писать номер квадранта, Квартиля.
>>1006364>some_vn.webpВН со скриншотов - Lessons in Love, за авторством Selebus."Если бы Достоевский был виабушником".>в поиске дубликатовПодсказка из зала: не сохраняйте всё подряд.Если уж так получилось, что с памятью (в голове) беда сохранили дважды или более - значит картинка того стоит и разве жалко дискового пространства на сокровище? Такой-то бекап для любимого!Весь контент не сохранишь: нужно выбирать с умом.
>>1006371> Такой-то бекап для любимого!Так это я не для localhost, а для 014chan.org же. >>/d/1000697 FR на поиск картинок.
Спасибо за проделанную исследовательскую работу, конечно.Могу прокомментировать только применимость в UI, по опасениям в конце поста >>/d/1000718. Можно выводить юзверю уверенное утверждение про точное совпадение (md5 файла и/или пикселей), а это ниже как "Похожие изображения:".Какая-то работа ведётся на Данбуре по такому.https://github.com/danbooru/danbooru/commit/1378c6fd9bf02b5f4b1c66da096e1f3ac99d0d82 - тут видимо про хэш пикселей, который в api media_asset pixel_hash https://cdn.lewd.host/ZUQhFPyH.png.А вот их похожесть https://github.com/danbooru/iqdb. Работает так себе, по моему опыту-впечатлению (недостаточно обобщает, а ложнопозитивы вообще не в ту степь). Что-то нейронное из больших общих поисковиков (g, ya) лучше предлагает похожести. Или алгоритм SauceNao.
