Веб 2.0 — отличная штука. Сайты на самообслуживании. Пользователи наполняют их собственноручно («постят контент», как сейчас выражаются). Сами напостили, сами посмеялись. А владелец сайта только платит за хостинг и стрижет купоны на рекламе. Удобно же.

Но жизнь наша так странно устроена, что плюсов без минусов не бывает, а нередко недостатки вообще являются продолжением достоинств. Есть проблемы и у самонаполняемых сайтов — баяны. В смысле, дубли.

Дубли многие посетители не любят, особенно старожилы, на зубок помнящие мемасики, появившиеся во времена превед‑медведа и олбанского йазыгга. Каждое очередное их появление они встречают фырканьем и угрозами немедленно отписаться.

Что же делать? Конечно, призвать на помощью железную машину — пусть она сама ищет баяны.

С текстом процедура более‑менее освоена. Простенькую машину для полнотекстового поиска можно найти чуть ли не в любой СУБД. Если кому‑то надо посложнее, например, учитывающую морфологию языка, — к вашим услугам Sphinx, Solr и так далее. Даже если ваши запросы простираются настолько далеко, что вы желаете искать не просто дубли, а переделки бородатых анекдотов, в которых Василий Иванович и Петька в духе времени заменены на Дарта Вейдера и Гарри Поттера, к вашим услугам td/idf, косинусы угла между векторами и прочие методы поиска плагиата.

С текстом разобрались. Но что делать с картинками? Ведь это же наверное как‑то можно? Гугл‑то ищет похожие, хоть и паршиво. Яндекс ищет, и даже получше, чем Гугл. Да что там Яндекс — на некоторых развлекательных сайтах вроде Пикабу тоже есть средства дебаянизации.

Да, можно. И не очень сложно, как ни странно, — потому что умные люди уже выполнили за нас самую сложную часть работы, придумав и испытав красивые и остроумные алгоритмы.

Как же искать дубли картинок? Очень просто.

Шаг 1. Для каждой картинки в базе составить ее цифровой отпечаток (fingerprinting) — какую‑то последовательность битов, отражающую ее содержание.

Шаг 2. Создать отпечаток для искомой картинки и сравнить его с теми, что уже лежат в нашей базе.

Вуаля! А дьявол, как водится, обитает уже в деталях.

Делай раз: создаем отпечаток

Здравый смысл подсказывает, что отпечаток не должен быть слишком длинным — чем короче, тем лучше. Его надо ведь хранить в самой базе, а потом еще и сравнивать с остальными. Если он будет размером с само изображение, и то, и другое станет делать затруднительно.

Значим, нам нужна какая‑то хэш‑функция, которая свернет содержимое рисунка в короткую строку битов.

Традиционные хэш‑функции вроде cемейства sha разумеется, отпадают. Они слишком чувствительны — даже если двоичное содержимое двух картинок различается всего на один бит, посчитанные хэши вообще не будут иметь ничего общего (хотя, как ни странно, именно sha1 используется в движке Википедии. Могли бы выдумать и получше).

О криптографических хэшах речи тем более нет. Они точно так же нервно реагируют на лишний бит, только при этом и считать их еще гораздо напряжнее.

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

И такие хэши действительно придуманы. Можно, например, с помощью методов машинного обучения распознать, что у нас нарисовано, — допустим, собачка, распознать, какой именно породы, какой расцветки и в какой позе она стоит, и потом закодировать в хэше эти признаки.

Но нам такие изыски точно ни к чему, мы обойдемся кое‑чем попроще. Нам ведь не надо классифицировать нарисованное, нам надо просто найти дубликаты.

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

Можно, например, посчитать средний цвет по всему изображению и выставить для каждого пиксела значение 0 или 1 — темнее или светлее он среднего. Это быстро и легко, но результаты получаются довольно посредственные.

Гораздо лучше использовать дискретное косинусное преобразование, получив в результате так называемый перцептивный хэш (perceptual hash, phash). Можно даже не писать алгоритм самому, phash уже включен в самую популярную библиотеку обработки изображений — ImageMagick.

Другой вариант — разностный хэш (difference hash, dhash). Он дает результаты чуть хуже, чем перцептивный, однако же вполне приемлемые, а считается при этом проще и быстрее. Идея та же самая, но при этом в битах кодируется разница соседних пикселей — положительная она или отрицательная.

Можно, разумеется, выдумать что‑нибудь еще в том же духе, но надо ли?

Делай два: сравниваем хэши

Это совсем легко. Говоря умными словами, используем расстояние Хэмминга, а выражаясь по-простому, считаем, сколько битов в двух хэшах различаются.

Если, к примеру, вы используете MySQL или ее младшую сестру Марию, то это можно сделать с помощью встроенной функции:

SELECT * FROM images WHERE BIT_COUNT(newMem ^ hash) <= 6

newMem тут - dhash (или phash) новой картинки, дубли которой мы хотим найти, hash - соответственно хэш картинки, уже лежащей в базе. Крышка символизирует побитовый XOR, а число 6 получено опытным путем.

Вот для наглядности пример исходной картинки.

А вот различные ее искажения и извращения, с посчитанными для них расстояниями Хэмминга (расстояния приведены для исходных картинок размером 3000х2000, для размещения на сайте я их ужал):

Как видите, хэш (в данном случае — dhash) отлично справляется с небольшими изменениями в исходном изображении — такими, которые берутся от легкого редактирования, конечно, а не от сознательных попыток обмануть алгоритм. Не потянул он только зеркальное переворачивание изображения, но ведь нам никто не мешает взять картинку, вызывающую сомнение, отзеркалить ее и прогнать по базе еще раз.

Если на вашем сайте собираются пользователи, размещающие на нем свои любовно собранные фотографии старых трамваев с бугелями, русских печек, спасательных лодок на пляже, выращенных собственноручно лимонных деревьев и тому подобные захватывающие вещи, — то есть, серьезные, солидные люди, а не подростки, из больного тщеславия возжелавшие сломать систему, то большего, чем dhash, вам и не требуется.

Делай два: сравниваем хэши по-настоящему

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

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

Да и с индексами тоже все непонятно — нам нужен такой, чтобы показывал расстояние Хэмминга от... От чего? То‑то и оно. Очевидно, тут нужно что‑то хитрое.

Такие индексы, вернее, деревья, в природе существуют. Например, есть такая экзотика, как vp‑tree (vantage point tree), что можно художественно перевести как «дерево с точками удобного наблюдения за другими точками». Понять его принцип несложно — это обычное двоичное дерево, только точки в нем группируются по удалению друг от друга. Не так радостно с построением дерева и поиском по нему — с первого раза врубиться в алгоритм нелегко, но это не самая большая проблема. Куда хуже, что такое дерево строится один раз и при добавлении новых точек или удалении старых его приходится перестраивать чуть ли не целиком. Это означает, что для использования на сайте, где постоянно добавляется новый материал и нередко удаляется старый, оно не очень подходит.

А как с этим справляется Гугл? О, Гугл, а вернее, работавший на него Мозес Чарикар (Moses Charikar), придумал весьма изящную вещь под названием Simhash, которая куда проще запутанных пространственных деревьев. Вот смотрите:

Допустим для конкретики, что наш хэш состоит из 64 битов. Разобьем их на 8 байтов.

Мы хотим найти хэши, отстоящие на расстояние не более 6 битов от проверяемого. Но это означает, что даже если все 6 отличающихся битов находятся в разных байтах хэша, то все равно, как ни крути, какие‑то два байта будут в обоих хэшах полностью совпадать.

А это значит, что мы можем заранее отобрать из базы те хэши, которые совпадают с нашим проверяемым в каких-то двух байтах, и высчитать расстояние только для них. Это прилично сокращает объем работ - раз в 200-300.

Как же это сделать?

Согласно оригинальной идее, нужно завести для хэшей дополнительные таблицы, число которых будет равно числу возможных сочетаний двух байтов из восьми, в нашем случае = 28. В каждой таблице хранятся одни и те же хэши, но с переставленными байтами. В основной в первом и втором байте - первый и второй байт хэша, в первой дополнительной - первый и третий, во второй - первый и четвертый, и так далее, пока мы не переберем все комбинации. Вот, на случай, если вам лень их считать самим.

{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {4, 5}, {4, 6}, {4, 7}, {4, 8}, {5, 6}, {5, 7}, {5, 8}, {6, 7}, {6, 8}, {7, 8}

А теперь мы отсортируем эти таблицы по первым двум байтам и сможем воспользоваться двоичным поиском, отобрав с его помощью кандидатов на последующее сравнение!

Впрочем, в этом месте мы можем уклониться от совета уважаемого автора. У нас все-таки не Гугл, а сайт попроще, картинок мы храним гораздо меньше и поэтому нам не требуется изобретать собственные велосипеды с турбонаддувом. У нас ведь уже есть база - мы же где-то держим ссылки и атрибуты наших фотографий. Давайте воспользуемся ею и положим рядом с хэшем в виде двоичной строки этот же хэш, разбитый на байты.

CREATE TABLE images (
  name VARCHAR(100) NOT NULL,
  hash BIGINT UNSIGNED NOT NULL,
  b1 TINYINT UNSIGNED NOT NULL,
  ...
  b8 TINYINT UNSIGNED NOT NULL,
)

К каждому байту, естественно, добавим отдельный индекс, а затем станем искать наш хэш вот таким запросом, перебирающим все возможные сочетания двух байтов из восьми:

SELECT name FROM images WHERE (
  (b1=newMem_b1 AND b2=newMem_b2) OR
  (b1=newMem_b1 AND b3=newMem_b3) OR
  ...
  (b7=newMem_b7 AND b8=newMem_b8)
) 
AND BIT_COUNT(newMem ^ hash) <= 6

Запрос для человека, конечно, длинноват, но база смотрит на него по‑другому, и оптимизировать его ей не сложно, задействовав индексы по полям b1...b8.

Сочетания 2 по 8, разумеется, не написаны на скрижалях, это всего лишь один из вариантов, хотя и практически удобный. В зависимости от предполагаемого числа хранящихся изображений и расстояния Хэмминга, на котором мы хотим искать, можно разбить хэш на другое количество частей, не обязательно даже одинаковой длины.

Немного практических цифр. На моей старенькой, отпраздновавшей уже десятилетие машине, создание разностного хэша в nodejs занимает примерно полторы секунды, из которых секунда уходит на уменьшение изображения с помощью ImageMagick.

Поиск одного хэша по базе в 30.000 фотографий (больше котиков и фигуристых девушек у меня не нашлось) требует примерно двух секунд, из которых секунда уходит опять же на уменьшение исходного изображения. Это без индексов — я поленился для прототипа их создавать — так что задел для масштабирования поиска имеется. Хватит ли его на миллион‑другой фотографий — вопрос открытый. Если у вас есть столько разных фоточек, было бы интересно узнать ваши впечатления.

Ну и напоследок еще один вопрос. Что делать, если мы хотим найти более удаленные в смысле Хэмминга фотографии — различающиеся не на 6 битов, а на 20 или 30? Отвечаю: это уже совсем иная задача — если по‑английски, то не near‑duplicate search, а similarity detection, и совсем другая история, для которой описанные методы не подходят и надо придумывать что‑то еще.