Какие способы существуют для поиска дубликатов и похожих изображений хэш функции

Обновлено: 04.07.2024

Реализация хеш-алгоритма на Python и руководство по обнаружению повторяющихся изображений

Iconfinder - это поисковая система для иконок, которая предоставляет изысканные иконки для дизайнеров, разработчиков и других творческих работников, в настоящее время она содержит более 340 000 иконок и является крупнейшей в мире платной библиотекой иконок. Пользователи также могут загружать и продавать оригинальные работы в торговом разделе Iconfinder. Каждый месяц в Iconfinder загружаются тысячи иконок, а также большое количество пиратских изображений. В этой статье инженер Iconfinder Сильвиу Тантос предлагает новый и умный метод проверки дублирования изображений для предотвращения пиратства.

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

Криптографический алгоритм хеширования - это широко используемый алгоритм хеширования. Подобно MD5, SHA1, SHA256, вы можете найти вызываемые стандартные библиотеки на любом языке, и они очень эффективны для простых случаев использования.

Например, сначала импортируйте модуль hashlib в Python, а затем вызовите функцию, чтобы сгенерировать значение хеш-функции определенной строки или файла.

>>> hashlib.md5( 'The quick brown fox jumps over the lazy dog' ).hexdigest()

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

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

>>> hashlib.md5( 'The quick brown fox jumps over the lazy dog' ).hexdigest() >>> hashlib.md5( 'The quick brown fox jumps over the lazy dog.' ).hexdigest()

Если цвет фона изображения изменяется, изображение обрезается, поворачивается или изменяется определенный пиксель, это не может быть сопоставлено в библиотеке хэшей изображения. Видно, что традиционный алгоритм хеширования не практичен. Как вы можете видеть в приведенном выше примере, хеш-значения 9 e107d9d372bb6826bd81d3542a419d6 и e4d909c290d0fb1ca068ffaddf22cbd0 практически различаются (за исключением нескольких символов).

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

>>> image_file_modified = open ( 'data/cat_grumpy_modif.jpg' ).read()

Существует множество алгоритмов перцептивного хеширования. В этой статье будет предложен новый алгоритм dhash (разностного хеширования), который вычисляет разницу яркости между соседними пикселями и определяет относительный градиент. Для приведенных выше вариантов использования алгоритм перцептивного хеширования будет очень эффективным. Алгоритм перцептивного хеширования получает отпечаток мультимедийного файла, который может гибко различать тонкие различия между разными файлами от различных характеристик содержимого файла.

dHash

Прежде чем углубленно изучать алгоритм dHash, сначала ознакомьтесь с некоторыми базовыми знаниями. Цветное изображение состоит из трех основных цветов RGB, которые можно рассматривать как набор цветов из трех основных цветов: красного, зеленого и синего. Например, используйте библиотеку изображений Python (PIL) для загрузки изображения и печати значения пикселя.

>>> print 'Width: %s px, Height: %s px' % (test_image.size[ 0 ], test_image.size[ 1 ]) [( 0 , 0 , 0 ), ( 212 , 45 , 45 ), ( 51 , 92 , 154 ), ( 130 , 183 , 47 )] [( 206 , 210 , 198 ), ( 131 , 78 , 8 ), ( 131 , 156 , 180 ), ( 117 , 155 , 201 )] [( 104 , 133 , 170 ), ( 215 , 130 , 20 ), ( 153 , 155 , 155 ), ( 104 , 142 , 191 )]

Теперь вернемся к алгоритму dHash, который состоит из четырех этапов. В этой статье подробно описывается каждый шаг и проверяется его влияние на исходное изображение и модифицированное изображение. Значения интенсивности красного, зеленого и синего цветов первых трех пикселей соответственно равны 255, два других значения интенсивности цвета соответственно равны 0, три основных цвета пикселей чисто черного цвета равны 0, а три основных цвета пикселей чисто белого цвета равны 255. Пиксели других цветов состоят из трех значений основного цвета разной интенсивности.

1. Изображение в градациях серого

При окрашивании изображения в серый цвет значение пикселя уменьшается до значения силы света. Например, белый пиксель (255, 255, 255) становится 255, а значение интенсивности черного пикселя (0, 0, 0) становится 0.

2. Уменьшить изображение до общего размера

Уменьшите изображение до общего базового размера, такого как размер 9 * 8 пикселей с большой шириной и одним значением пикселя (вы можете понять, почему этот размер находится на третьем шаге). С помощью этого метода удаляются высокие частоты и детали изображения, и получается образец с 72 значениями интенсивности. Поскольку изменение размера или растяжения изображения не меняет его значения хеш-функции, все изображения нормализуются до этого размера.

3. Сравните соседние пиксели

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

>>> img = Image. open ( 'data/cat_grumpy_orig_after_step_2.jpg' )

Первое значение 254 сравнивается со вторым 254, второе значение сравнивается с третьим значением и т. Д., Так что каждая строка получает 8 логических значений.

[ False , False , True , True , False , False , True , False ] [ False , True , True , False , False , True , False , False ] [ True , True , False , False , True , False , False , False ] [ True , False , False , True , False , False , False , True ] [ False , False , True , False , False , False , True , True ] [ False , True , False , False , False , True , True , False ] [ True , False , False , False , True , True , False , False ] [ False , False , False , True , True , False , False , True ]

4. Преобразовать в двоичный

Чтобы облегчить хранение и использование значений хеш-функции, 8 логических значений преобразуются в шестнадцатеричные строки. Туре становится 1, а Ложь становится 0.
Реализация Python

Ниже приводится полный алгоритм полной реализации Python:

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

В базе данных SQL, в которой хранятся хеш-значения, вы можете просто определить, существует ли хеш-значение "4 c8e3366c275650f" следующим образом:

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

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

Заключительные замечания

Как упоминалось во введении, алгоритм в этой статье будет применен к Iconfinder для предотвращения повторной отправки значков.Можно ожидать, что есть более практические применения алгоритма хеширования восприятия. Поскольку хеш-значения изображений с похожими функциями также похожи, это может помочь системам рекомендаций изображений найти похожие изображения.

В некоторых случаях нам необходимо обнаружить сходство между изображениями и выполнить необходимую обработку: удалить одно и то же изображение, отметить пиратские копии и т. Д.
Как судить об одинаковой картинке? Самый простой способ - использовать криптографический хэш (например, MD5, SHA-1) для определения. Но ограничения очень большие. Например, текстовый документ, значение MD5 которого вычисляется на основе двоичных данных этого текстового документа.Если это полная копия этого текстового документа, их значения MD5 точно такие же. Однако после изменения содержимого копии, даже если это просто формат отступа копии, ее MD5 будет сильно отличаться. Следовательно, зашифрованный хэш может использоваться только для оценки двух идентичных и неизмененных файлов.Если это изображение было оценено или масштабировано, невозможно определить, является ли оно тем же изображением, что и другое изображение.
Итак, как судить, является ли картинка, которая была PS, по существу такой же, как другая картина? Относительно простым и простым в использовании решением является использование Perceptual Hash Algorithm.

Алгоритм перцептивного хеширования - это общий термин для класса алгоритмов, включая aHash, pHash и dHash. Как следует из названия, перцептивное хеширование не вычисляет хеш-значение строго, но вычисляет хеш-значение более относительным способом, потому что «похожий» или нет - это относительное суждение.

aHash: средний хэш. Скорость относительно высокая, но часто менее точная.
pHash: перцептивный хэш. Точность относительно высокая, но скорость относительно низкая.
dHash: хэш разностного значения. Удивительный! Точность высокая, и скорость тоже очень высокая. Поэтому я выбрал dHash в качестве алгоритма оценки веса моих фотографий.

1. Шаги обнаружения похожих изображений:

Рассчитайте значение dHash для двух картинок отдельно
Вычислите расстояние Хэмминга двух изображений по значению dHash и оцените сходство двух изображений по размеру расстояния Хэмминга.

Два, расчет dHash

Шаг 1. Увеличьте изображение

Если мы хотим вычислить значение dHash на приведенном выше рисунке, первым делом нужно поместить его Масштаб достаточно мал , Зачем вам зум? Потому что разрешение исходного изображения обычно очень высокое. Изображение размером 200 * 200 имеет в общей сложности 40 000 пикселей, и каждый пиксель содержит значение RGB.40 000 RGB - это огромный объем информации, требующий обработки множества деталей. Поэтому нам нужно увеличить изображение до очень маленького размера, скрыть его детали и видеть только лес, но не деревья. Рекомендуемое масштабирование - 9 * 8. Хотя оно может быть масштабировано до любого размера, это значение является относительно разумным. А ширина - 9, что нам полезно преобразовать в хеш-значение, посмотрите ниже, вы поймете.

Шаг 2. Поседение

Полное имя dHash - это хэш разностного значения, который получается путем вычисления разницы интенсивности цвета между соседними пикселями. Детали нашего увеличенного изображения были скрыты, а количество информации стало меньше. Но этого мало, потому что он цветной и состоит из значений RGB. Белый цвет представлен как (255,255,255), а черный - как (0,0,0). Чем больше значение, тем ярче цвет, а чем меньше - темнее. Каждый цвет состоит из 3 числовых значений, а именно красного, зеленого и синего значений. Если вы напрямую используете значение RGB для сравнения разницы в интенсивности цвета, это довольно сложно, поэтому мы преобразуем его в значение серого - только целое число от 0 до 255 представляет серый. В этом случае трехмерное сравнение упрощается до одномерного сравнения.

Шаг 3. Расчет разницы

Шаг 4. Преобразовать в хеш-значение

Мы обрабатываем каждое значение в массиве значений разности как бит, и каждые 8 битов образуют шестнадцатеричное значение, объединяют шестнадцатеричные значения и преобразуют их в строку, чтобы получить окончательное значение dHash.

3. Рассчитайте расстояние Хэмминга

Концепция расстояния Хэмминга используется не только в области сравнения изображений, но и во многих других областях. Подробнее см. В Википедии.
Расстояние Хэмминга указывает, сколько шагов необходимо, чтобы преобразовать A в B. Например, для строк «abc» и «ab3» расстояние Хэмминга равно 1, потому что только «c» необходимо изменить на «3».
Расстояние Хэмминга в dHash - это количество битов, измененных путем вычисления значения разности. Наше разностное значение представлено 0 и 1, что можно рассматривать как двоичное. Расстояние Хэмминга между двоичным кодом 0110 и 1111 равно 2.
Мы конвертируем значение dHash двух изображений в двоичную разность и берем XOR. Количество цифр «1» в результате XOR - это количество различных цифр, которое является расстоянием Хэмминга.

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

Вообще говоря, расстояние Хемминга составляет менее 5, что в основном та же картина. Вы можете оценить критическое значение расстояния Хэмминга на основе вашей реальной ситуации.

За последние несколько месяцев несколько человек спросили меня, как работает TinEye и как в принципе работает поиск похожих картинок.

По правде говоря, я не знаю, как работает поисковик TinEye. Он не раскрывает деталей используемого алгоритма(-ов). Но глядя на поисковую выдачу, я могу сделать вывод о работе какой-то формы перцептивного хэш-алгоритма.

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

Перцептивные хэши — это другая концепция по сравнению с криптографическими хэш-функциями вроде MD5 и SHA1. В криптографии каждый хэш является случайным. Данные, которые используются для генерации хэша, выполняют роль источника случайных чисел, так что одинаковые данные дадут одинаковый результат, а разные данные — разный результат. Из сравнения двух хэшей SHA1 на самом деле можно сделать только два вывода. Если хэши отличаются, значит, данные разные. Если хэши совпадают, то и данные, скорее всего, одинаковые (поскольку существует вероятность коллизий, то одинаковые хэши не гарантируют совпадения данных). В отличие от них, перцептивные хэши можно сравнивать между собой и делать вывод о степени различия двух наборов данных.

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

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

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

1. Уменьшить размер. Самый быстрый способ избавиться от высоких частот — уменьшить изображение. В данном случае мы уменьшаем его до 8х8, так что общее число пикселей составляет 64. Можно не заботиться о пропорциях, просто загоняйте его в квадрат восемь на восемь. Таким образом, хэш будет соответствовать всем вариантам изображения, независимо от размера и соотношения сторон.

2. Убрать цвет. Маленькое изображение переводится в градации серого, так что хэш уменьшается втрое: с 64 пикселей (64 значения красного, 64 зелёного и 64 синего) всего до 64 значений цвета.

3. Найти среднее. Вычислите среднее значение для всех 64 цветов.

4. Цепочка битов. Это самое забавное: для каждого цвета вы получаете 1 или 0 в зависимости от того, он больше или меньше среднего.

5. Постройте хэш. Переведите 64 отдельных бита в одно 64-битное значение. Порядок не имеет значения, если он сохраняется постоянным (я записываю биты слева направо, сверху вниз).

= = 8f373714acfcf4d0

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

Если вам нужно сравнить две картинки, то просто строите хэш для каждой из них и подсчитываете количество разных битов (это расстояние Хэмминга). Нулевое расстояние означает, что это, скорее всего, одинаковые картинки (или вариации одного изображения). Дистанция 5 означает, что картинки в чём-то отличаются, но в целом всё равно довольно близки друг к другу. Если дистанция 10 или больше, то это, вероятно, совершенно разные изображения.

Хэш по среднему простой и быстрый, но он даёт сбои. Например, может не найти дубликат картинки после гамма-коррекции или изменения цветовой гистограммы. Это объясняется тем, что цвета меняются в нелинейной масштабе, так что смещается положение «среднего» и многие биты меняют свои значения.

В хэш-функции pHash используется более надёжный алгоритм (вообще-то, я использую собственный вариант этого алгоритма, но концепция та же самая). Метод pHash заключается в доведении идеи средних значений до крайности, применив дискретное косинусное преобразование (DCT) для устранения высоких частот.

1. Уменьшить размер. Как и в случае хэша по среднему, pHash работает на маленьком размере картинки. Однако, здесь изображение больше, чем 8х8, вот 32x32 хороший размер. На самом деле это делается ради упрощения DCT, а не для устранения высоких частот.

2. Убрать цвет. Аналогично, цветовые каналы убирают, чтобы упростить дальнейшие вычисления.

3. Запустить дискретное косинусное преобразование. DCT разбивает картинку на набор частот и векторов. В то время как алгоритм JPEG прогоняет DCT на блоках 8x8, в данном алгоритме DCT работает на 32x32.

4. Сократить DCT. Это магический шаг. В то время как первоначальный блок был 32x32, сохраните только левый верхний блок 8x8. В нём содержатся самые низкие частоты из картинки.

5. Вычислить среднее значение. Как и в хэше по среднему, здесь вычисляется среднее значение DCT, оно вычисляется на блоке 8x8 и нужно исключить из расчёта самый первый коэффициент, чтобы убрать из описания хэша пустую информацию, например, одинаковые цвета.

6. Ещё сократить DCT. Тоже магический шаг. Присвойте каждому из 64 DCT-значений 0 или 1 в зависимости от того, оно больше или меньше среднего. Такой вариант уже выдержит без проблем гамма-коррекцию или изменение гистограммы.

7. Постройте хэш. 64 бита превращаются в 64-битное значение, здесь тоже порядок не имеет значения. Чтобы посмотреть, на что похож отпечаток визуально, можно присвоить каждому пикселю значения +255 и -255, в зависимости от того, там 1 или 0, и преобразовать DCT 32x32 (с нулями для высоких частот) обратно в изображение 32x32.

= 8a0303769b3ec8cd

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

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

Поскольку я плотно занимаюсь экспертизой цифровых фотографий и работаю с гигантскими архивами изображений, то мне нужен инструмент для поиска одинаковых картинок. Так что я сделал такой поисковик, в котором используется несколько перцептивных хэш-алгоритмов. Как показывает мой богатый, хотя и ненаучный опыт, хэш-функция по среднему работает гораздо быстрее pHash и она отлично подходит, если вы ищете что-то конкретное. Например, если у меня есть крохотная иконка фотографии и я точно знаю, что где-то в коллекции хранится полноразмерный оригинал, то хэш по среднему быстро его найдёт. Однако, если с изображением осуществляли какие-то манипуляции, например, добавили текст или приклеили новое лицо, то он уже вряд ли справится, тогда как pHash хоть и медленнее, но гораздо более терпимо относится к незначительным модификациям изображения (менее 25% площади).

И ещё раз, если вы держите сервис вроде TinEye, то не будете каждый раз запускать pHash. Я полагаю, что у них есть база данных с заранее рассчитанными значениями хэшей. Основная функция сравнения изображений работает чрезвычайно быстро (есть некоторые способы сильно оптимизировать вычисление расстояние Хэмминга). Так что вычисление хэша — это одноразовая задача, и выполнять миллионы операций сравнения за пару секунд (на одном компьютере) вполне реально.

Существуют разновидности перцептивного хэш-алгоритма, которые также повышают быстродействие. Например, изображение можно обрезать перед тем как уменьшать размер. В этом случае потеря информации вокруг основной части изображения не играет особой роли. Кроме того, картинку можно поделить на части. Например, если у вас работает алгоритм распознавания лиц, то можно вычислять хэш для каждого лица (я подозреваю, что алгоритм TinEye делает нечто подобное).

Другие разновидности могут анализировать общее распределение цвета (например, её волосы более красные, чем синие или зелёные, а фон скорее светлый, чем тёмный) или относительно взаиморасположение линий.

Если вы можете сравнивать картинки, то перед вами открываются совершенно новые перспективы. Например, поисковик GazoPa позволяет рисовать картинку на экране. Как и в случае с TinEye, я не знаю всех деталей их алгоритма, но похоже на какой-то вариант перцептивного хэша. И поскольку хэш-функция сводит всё что угодно на низкие частоты, то мой кривой рисунок трёх фигурок с ручками-палочками может сравниться с другими изображениями, в том числе с фотографиями, на которых изображены трое людей.

Небольшой отчет о создании приложения KawaiiSearch — поиска похожих фотографий с помощью сверточной нейросети и kNN

tl;dr; Качаем фотографии из интернетов. Натренированной нейросетью VGG19 вычисляем 4096-мерные вектора каждого изображения. Косинусной метрикой находим ближайшего соседа к целевой картинке. Получаем наиболее похожие картинки в каком-то смысле. Profit!
Source code.

Введение

Еще каких-то 5 лет назад, чтобы сделать свой поиск по картинкам, приходилось погружаться в тонкости машинного зрения. Нужно было придумывать то, каким образом преобразовать картинку в некоторый индекс, отпечаток, по которому можно найти другую, похожую на неё. Судя по всему, для этих целей могли использовать перцептивные хеши и вариации, разные преобразования характеристик изображений и даже каскады Хаара. В общем, всё это напоминало классические алгоритмы эпохи до машинного обучения, когда исследователям основываясь на их восприятии самим приходилось придумывать некоторые модели. Это всё безумно интересно и серьезно, можно защитить не один диплом и диссертацию. Но что примечательно, сейчас существует достаточно простой способ для построения своего собственного движка поиска похожих картинок и начать решать свои бизнес задачи немного проще, чем это было раньше.

Что такое “похожие” изображения

Sheepdog or mop?

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

Как видите, есть некоторые трудности в постановке задачи. Обычно даже не говорят, что две фотографии похожи, а рассматриваю некоторую величину похожести от, скажем, нуля — совершенно похожи, до бесконечности — совершенно не похожи. Измерение этой величины будет зависеть от той формы индексов, которые будет давать некоторый алгоритм; это может быть расстояние Хемминга или расстояние между точками в многомерном пространстве, или ещё что-то. Выбор метрики естественно будет влиять на результат не меньше, чем сам алгоритм поиска признаков в изображениях.

Обзор существующих классических решений

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

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

Есть еще несколько алгоритмов, даже на основе каскадов Хаара, но в результате так или иначе, алгоритм очень сильно страдает от преобразований над изображением: от поворотов, отражений, изменений размера, модификации цветности. Но тем не менее они очень быстро работают. Их можно использовать для поиска дубликатов с незначительными искажениями. Но для поиска изображениях, в которых “похожие” определяются в том смысле, что на них изображены коты, а не собаки, алгоритмы этого типа не подходят, да в принципе этого от них и не требуют. Забавно, что еще в 2011 году в комментариях к статьям писали, что невозможно написать такой алгоритм для кошек-собак.

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

Классификация изображений

На качественно ином уровне задачу классификации изображений начали решать с 2013 года. Тогда на наборе данных ImageNet пробили барьер в 15% ошибок классификации тысячи видов объектов. С тех пор за 5 лет было спроектировано и натренированно очень много разных моделей нейросетей, и был пробит барьер в 5% ошибок. Самыми успешными из них считаются: VGG16, ResNet50, Inception, GoogLeNet и много других. Большинство их них построено на основе свёрточных нейросетей.

На рисунке вы можете посмотреть как выглядит схематически архитектура VGG16.

Слои нейросети на изображении состоят из набора разных фильтров-сверток. Каждый из фильтров отвечает за поиск определенного шаблона, и когда он находит некоторый участок изображения, в котором есть этот узор, то фильтр посылает сигнал в следующий слой. В свою очередь сигналы предыдущего слоя составляют новое изображение для следующего слоя. На рисунке архитектуры VGG16 вы можете видеть, что сначала было цветное RGB изображение размера 224x224 пикселей с 3 каналами(red, green, blue). Потом после прохода первого слоя сверток у нас получилось изображение размера 224x224 пикселей с 64 каналами. Эти каналы уже представляют не цвета, а результаты работы каждого из 64 фильтров-свёрток. И так далее, до изображения 7x7 пикселей с 512 каналами.

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

Feature Visualization of Convnet trained on ImageNet from [Zeiler & Fergus 2013]

Обратите внимание еще на одну интересную особенность свёрточных слоев в этой модели: каждый следующий слой “толще”, так как в нём больше фильтров, но “меньше”, так как изображение специально уменьшают с помощью операции MaxPooling (субдискретизация). Используют этот прием по следующей причине: важнее факт детекции некоторого признака-объекта, чем знание точного расположения этого объекта на изображении. Именно поэтому берут максимум внутри небольшого окошка, тем самым создавая карту расположений признаков.

Ближе к выходу модели у нас имеется маленькое изображение — карта признаков размера 7x7 пикселей с 512 фильтрами. По этой трёхмерной карте всё еще невозможно сделать предсказания классов объектов на изображении — котик или собака. Для того чтобы перейти уже к предсказаниям классов, эту карту укладывают на плоскости с помощью операции Flatten и соединяют с полносвязным скрытым слоем из 4096 нейронов. А дальше классическая схема: еще один скрытый слой с 4096 нейронами и выходной слой с 1000 нейронами, каждый из которых выдает вероятность принадлежности к одному из 1000 классов в задаче ImageNet.

Fine Tuning и переиспользование модели

Как оказалось, сети обученные на данных ImageNet можно переиспользовать для других задач компьютерного зрения. Например, у нас задача отличать кошку от собаки. Вам не надо создавать свою модель CatDogVGG, искать миллионы картинок и обучать с нуля сеть. Всё куда проще! Вы берёте предобученную модель VGG, срезаете последние полносвязные слои нейронов, отвечающие за финальную классификацию(да, так можно), оставляя только внутренние 4096 нейронов, которые соединяете со своими 2 нейрона для выхода кошка-собака. Получается, что вам нужно будет только дообучить модель этим 2*4096 связям, что делается легко и быстро.

Какой физический смысл в срезании последнего слоя сети и подстановки нового? Оказывается, что все слои свертки внутри себя заключают способность “понимать” изображение. А поскольку обучение происходило на тысяче разных классов, то и обобщающая способность этих слоев достаточно сильная. В итоге внешние 4096 нейронов на самом деле выдают вектор характеристик(признаков) любого изображения в целом. Поэтому для того чтобы проходила наша классификация, отличная от изначальной, нам остается дообучить нейросеть только и только переводить этот 4096-мерный вектор в наш вектор предсказаний принадлежности классов, не меняя существующую глубокую свёрточную сеть.

Подобный финт можно провернуть не только с VGG, но и с другими свёрточными архитектурами распознавания изображений. Для этой цели в библиотеке Keras есть даже специальные конструкты, которые вы можете изучить это в разделе keras-applications. Распознавание образов еще никогда не было таким простым!

Поиск похожих изображений с помощью нейросети

Как мы поняли из предыдущего параграфа, срезанная нейросеть производит по своей сути извлечение признаков из изображения и переводит изображение в осмысленный вектор. Получение такого вектора раньше требовало экспертной оценки и придумывания очередного алгоритма хеширований. Полученные теми методами вектора (64-битные хешсуммы) заключали в себе информацию, в лучшем случае, о контурах и простых формах в целом. Нейросеть же даёт как минимум 4096-мерное представление, в котором заключена и форма, и цвет, и целые объекты.

Хорошо, нами получен вектор признаков изображения, что мы делаем дальше? Считать расстояние Хэмминга, как мы это делали с хешами, тут бессмысленно. Здесь мы должны использовать другой подход. Представьте, каждый из векторов куда-то направлен в пространстве, это направление характеризует изображение. Если мы посчитаем вектора для множества картинок, то логично предположить, что похожие картинки будут иметь вектора характеристик расположенные в пространстве близко. Отличной метрикой близости векторов в многомерном пространстве служит косинусная метрика, хорошо себя зарекомендовавшая в задачах классификации текстов.

Чем меньше метрика, тем ближе объекты в векторном пространстве, тем больше похожи изображения по “мнению” нейросети.

Собираем модель как конструктор

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

Я предлагаю построить веб-приложение, похожее на Google Image Search. Для его построения нам понадобятся следующие библиотеки для Python3:

Numpy (a.k.a np) для математических функций; для алгоритма ближайших соседей и косинусной метрики; для веба;
Pandas, pillow, scipy, h5py для разных вспомогательных нужд.

Ещё нужно откуда-то взять много изображений на одну тематику. Я скачал все фотографии из блога tokio-fashion (около 50 тысяч фото), надеясь что нейросеть будет находить похожие образы или позы или еще что-нибудь. Кстати анализ fashion-индустрии это отдельная интересная область исследований!

Опишем базовые use-cases, которые мы хотим реализовать:

пользователь заходит на страницу;
пользователь жмёт кнопку “мне повезет”, тем самым выбирая случайную картинку из всего набора данных;
сервер ищет методом ближайших соседей K самых близких вектора к случайно выбранному, эти K векторов будут описывать самые похожие картинки;
пользователь видит на странице исходную картинку и 9 похожих с метрикой похожести в подписи.

Как делать веб часть и так все знают, поэтому рассмотрим наиболее неясные шаги.

Векторизация базы фотографий

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

Для более тонкой настройки можно указать имя определенного слоя. Как найти имя слоя — это отдельный анекдот, поэтому я смотрел в исходники модели.

После того как у вас загружена модель, она, кстати, будет реально загружать из интернета веса, можно конвертировать все изображения в вектора с помощью метода predict , что логично, так как мы “предсказываем” этот вектор.

Теперь всё тайное стало явью, и осталось дело техники — итерироваться по всем изображениям и для каждого из него произвести векторизацию. Потом сохранить эти вектора в БД или csv файла, не важно. Это мы оставим за кулисами.

Поиск похожего методом kNN

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

Мы выбрали cosine метрику и активировали полный перебор, загрузили все вектора в knn методом fit . Обычно этот метод запускает обучение, но в данном случае он просто сохранит все вектора внутри объекта knn , так как это алгоритм обучения без учителя.

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

В similar_images у нас будет лежать массив из 10 пар: имя файла и значение похожести по метрике, которая чем меньше, тем более похожее изображение к целевому. Всё, теперь этот список можно отдавать на фронтенд и рисовать красивую галерею. Изменяя параметр n_neighbours можно менять количество возвращаемых соседей, которые упорядочены по увеличению метрики, то есть дальше будут более непохожие картинки.

Тонкий момент. Функция load_images_filenames() возвращает список файлов ровно в том же порядке, в котором они перечислены в массиве load_images_vectors() , так как нам нужно точное соответствие вектора картинке.

Результат

Теперь вы видите, что с точки зрения кода задача теперь стала весьма простой. Но это всё благодаря развитию нейросетей и добрым экспериментаторам, которые выкладывают предобученные модели в интернет, иначе вам пришлось бы это всё самим обучать очень долго и мучительно.

А что в результате получилось? С моим результатом вы можете ознакомиться на сайте kawaii-search, исходники которого доступны на github. Всё это крутиться на сервере google-cloud n1-standard-1 c 3.75GB RAM чего не хватает и пришлось добавить еще столько же swap. Так как задача предсказания не сильно сложная, то видеокарта не нужна.

А в каком смысле теперь определено “похоже”. В случае с fashion датасетом, похожими считаются изображения, на которых есть объекты одних классов. Например, фотографии с только с портфелями, только с обувью одного типа, портреты, прически, руки. Смотрите сами:

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

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

Похож = есть один и тот же предмет

Что можно с этим делать

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

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

В этой статье я познакомлю вас с лучшими бесплатными программами для поиска одинаковых фотографий на компьютере с операционной системой Windows 10/8/7. Перечисленные в статье программы помогут вам отыскать одинаковые изображения и даже незначительно модифицированную их версию.

Программы для поиска одинаковых фотографий

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

Find.Same.Images.OK

Программа Find.Same.Images.OK находит одинаковые изображений, сравнивая их на уровне пикселей. Таким образом, даже если изображения отредактированы, то есть повернуты, зеркалированы и даже изменены, программа сможет их найти.

Awesome Duplicate Photo Finder

Данная утилита делает поиск и может находить точные копии изображений, а также показывает процент их сходства. Я проверил работу программы в одной из моих папок, в которой были разные вариации одной и той же фотографии с точки зрения цветов, размеров и даже изображений с похожими лицами. Awesome Duplicate Photo Finder смог найти все.

С помощью настроек можно регулировать поиск похожих изображений от точных копий до похожих снимков. Программа доступна так же в портабельной (версия не требующая установки на компьютер) версии.

CCleaner

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

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

Загрузить программу CCleaner вы можете с официального сайта.

Glary Duplicate Finder

Используя Glary Duplicate File Finder, вы можете полностью просматривать все изображения на своем компьютере, чтобы найти дубликаты изображений. Результат делится на две части: на файлы и дубликаты файлов. Вы можете указать, что вы хотите сохранить и удалить все остальное. Чтобы найти дубликат, утилита сопоставляет файлы по типу, содержанию, размеру и дате создания.

Вы также можете нажать кнопку «Check Intelligent» (Проверить интеллектуальность), и он будет выбирать только те дубликаты файлов, которые можно удалить одним щелчком мыши не задумываясь.

VisiPics

Это старое программное обеспечение, но оно довольно хорошо работает. Возможно, вам не понравится его интерфейс, но способность находить изображения безусловно впечатлит. Вы можете найти дубликаты изображений, используя три разных фильтра: строгий, простой и свободный. Он также находит небольшие и несжатые изображения с низким разрешением в виде дубликатов, что дает вам возможность выбрать и сохранить лучшую копию. VisiPics поддерживает изображения JPEG, GIF, PNG, BMP, PCX, TIFF, TGA и RAW. Результаты отображаются в реальном времени. Поэтому вам не нужно ждать завершения сканирования. Вы можете продолжать удалять изображения по мере их появления в результате.

Загрузить программу VisiPics вы можете с официального сайта.

Visual Similarity Duplicate Image Finder

Этот поисковик изображений ищет похожие изображения на основе форматов изображений, разной глубины бит и размеров изображений. Программа позволяет вам выбрать процент сходства при выполнении поиска изображений. Как и VisiPics, Visual Similarity Duplicate Image Finder также может находить меньшие изображения с меньшим разрешением в виде дубликатов.

AntiTwin

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

Результаты ясно показывают дубликаты изображений, но при этом вы можете также просмотреть каждый файл во избежание удаления важной для вас информации.

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

Читайте также: