php поиск фрагмента изображения

Red Spirit

Блог Алексея Таянчина

Поиск картинок по контенту на PHP (CBIR)

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

Есть большое количество алгоритмов, от простых, основанных на сравнении яркости двух изображений, до навороченных, основанных на “точках опоры” воспринимаемые человеческим глазом (как в tineye.com). Раньше я использовал простецкий скрипт, который был полностью реализован на php и использовал принцип разности яркостей. Но на деле этот метод оказался полной ерундой, который порой не мог распознать даже два визуально абсолютно идентичных изображения. Да и к тому же скорость работы оставляла желать лучшего (с использованием хэшей – около 1.5 сек на 1000 сравнений).

ImageMagick

Начал искать более приемлемые решения. Обнаружил, что у ImageMagick есть интересный метод Imagick::compareImages он как раз таки сравнивает два изображения (заранее приведенных к одной высоте и ширине) и выдает результат с учетом выбранной метрики (см. пример). В качестве результата возвращается массив с двумя значениями: разница картинок в визуальном виде (новый объект картинки imagick) и числовое значение, которое обуславливает разницу между изображениями, чем оно меньше, тем меньше разница. Если оно равно нулю, то картинки 100% идентичны.

Я провел эксперименты с несколькими сотнями разных изображений для того, чтобы достоверно определить какой коэффициент разности выставить, чтобы картинки считались идентичными. Из примера ниже видно, что значение $d я преобразовал по формуле $d = round($d/1000) для того, чтобы можно было удобно подбирать пороговые значения. Для себя я определил его так:

В первом примере к исходному изображения было применено уменьшенная яркость и увеличенная контрастность, а также добавлена желтая рамка и надпись черным цветом. Как видно, эти изображения были признаны “похожими”. Во втором примере была взята совершенно другая картинка, и видно, что результат гораздо больше 50, это значит, что картинки никаким боком не похожи (хотя персонаж и один).

Касательно качества распознавания этим инструментом мне все понравилось, но есть минус – скорость. Сама по себе скорость загрузки изображения и его сравнения небольшая (около 1 сек на 1000 сравнений). Но помимо этого надо еще привести изображение к общему размеру и преобразовать к одному формату, все это значительно влияет на скорость. Особые проблемы могут возникнуть с GIF, ImageMagick не всегда корректно читает гифки с анимацией, по этому приходится еще дополнительно извлекать первый кадр анимации и работать уже с ним (покадрово ImageMagick читает анимацию нормально). При всем при этом нет никакой возможность извлечь из изображения некий хэш или сигнатуру, которая бы характеризовала уже обработанное изображение и которую можно было бы сохранить в базе данных для быстрого доступа. Максимум, что можно сделать, это хранить в базе уменьшенные изображения (например 30х30 png) и работать с ним без лишних преобразований. Но это во-первых уменьшает качество распознования, во-вторых значительно напрягает БД, и в-третьих не так уж сильно увеличивается скорость. Я уже делал таким способом, скорость была все те же 900-1000 сравнений за сек.

Puzzle library

Потом не без помощи товарища ConstXife я узнал о библиотечке Libpuzzle. Эта штука делает как раз то, что мне надо. Программа поставляется исходниками, отдельно сама программа и отдельно PHP-модуль к ней. Скомпилировалось и установилось все без проблем и заработало с первого раза.

Puzzle library мне сразу понравилась своей скоростью и возможностью хранить очень компактные сигнатуры изображений в MySQL. То есть, чтобы эффективно использовать эту библиотеку, нужно заранее индексировать все изображения, которые будут задействованы в поиске и сохранить индекс (сигнатуры) в БД от куда и производить выборку. Вот простой пример использования Libpuzzle:

Источник

PHP и чтение текста на изображении: начало

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

1. Работа с исходным изображением.

У нас есть изображения фиксированного размера, но с разным текстом.
В моем случае такие:

1.1 Упрощаем изображения

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

После этого я получаю инвертированное двухцветное черно-белое изображение.

1.2 Находим символы на изображении

В моем случае задача простая: все символы находятся всегда на одних и тех же местах. Поэтому немного хардкода:

2. Преобразуем символы в массив

На выходе получаем нечто такое:
01111111110000
00000100000000
00000100000000
00000100000000
00000100000000
00000100000000
00000100000000
00000100000000
00000100000000
00000100000000
00000100000000
00000100000000
00000000000000

3. Распознание символа в массиве

Используем простую однослойную нейронную сеть. Для начала необходимо ее научить.

Для ускорения, можно проводить обучение в несколько итераций.
На самое главное это «покормить» нашу нейросеть всеми символами.
Что бы спросить сеть используем метод:

Пример работы алгоритма:

Источник

Поиск изображений по фрагменту с помощью ORB

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

ORB – бесплатная, быстрая и эффективная альтернатива алгоритмам обнаружения ключевых точек SIFT и SURF. Алгоритм не патентован, а значит, его использование в любых проектах не ограничивается. Входит в состав opencv.

Для задачи поиска изображений по фрагменту на Python необходимы библиотеки numpy и opencv.

Загрузка изображений и перевод в монохром:

Поиск ключевых точек и дескрипторов:

Сравнение дескрипторов ключевых точек и сортировка результатов по расстоянию Хамминга:

matches будет содержать массивы объектов – результатов сравнения дескрипторов. Для каждого такого массива атрибут distance будет содержать значение расстояния Хэмминга.

Отображение результата, отрисованы и сопоставлены первые 20 ключевых точек:

Для поиска исходного изображения фрагмента среди множества изображений предлагается:

Создать список с результатами сравнения для каждого изображения,

Отсортировать результаты сравнения (то есть, каждый элемент списка) по расстоянию Хэмминга,

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

При искажении изображения, в зависимости от способа искажения, качество работы алгоритма может сильно пострадать, например:

Результат работы алгоритма с искажением изображения для поиска (поворот)

Результат работы алгоритма с искажением изображения для поиска (наклон, вращение)

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

Результат работы алгоритма с искажением исходного изображения (уменьшение разрешения до 30% от начального)

Результат работы алгоритма с искажением изображения для поиска (повышение яркости)

Результат работы алгоритма с искажением изображения для поиска (повышение яркости) и обрезкой исходного изображения

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

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

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

Источник

Как определить дубликаты картинок с помощью PHP

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

Потому рано или поздно встает вопрос автоматизации процесса поиска повторов, и тут мы рассмотрим основные, а также попробуем в деле.

Сравнение файлов через функцию hash

Одним из способов определения дубликатов является сравнение файлов путем генерации хеш-значения из содержимого заданного файла.

Простой пример вычисления хеша изображения:

Результат выглядит примерно так: bff8b4bc8b5c1c1d5b3211dfb21d1e76

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

ImageMagick

Функция обработки изображений Imagick::compareImages возвращает массив, который содержит восстановленное изображение и разницу между изображениями.

Пример использования при сравнении двух изображений:

В итоге две сравниваемые картинки лепятся в одну, на которой видны отличия.
Также можно получить числовое выражение отличий по каждому параметру (пример с оф.сайта):

gd2 и libpuzzle

Для быстрого поиска дубликатов необходимо установить библиотеки gd2 и libpuzzle.

Libpuzzle создана для быстрого поиска визуального сходства изображений (GIF, PNG, JPEG). Сначала растровая картинка разбивается на блоки — автоматически отбрасываются рамки, не несущие особо значимой информации. Разница между смежными блоками формирует вектор — это так называемая подпись картинки. Похожесть картинок определяется расстоянием между двумя такими векторами. Потому обычно изменение цвета, ресайз или сжатие не влияют на результаты, выдаваемые libpuzzle.

Libpuzzle довольно проста в использовании. Вычисление подписи для двух изображений:

Вычисление расстояния между подписями:

Проверка изображений на схожесть:

Сжатие подписей для хранения в базе данных:

Перцептивный хеш

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

Отличается от первого способа тем, что указывает не только на одинаковость/неодинаковость, но и на степень различия. Подробнее об этом принципе можно прочитать в неплохом переводе.

Установка для UNIX платформ выглядит так:

Попробовать на деле можно через i.onthe.io/phash. Загрузка изображений через интерфейс и на выходе показатель «одинаковости».

Как это работает

Получаем хеш первого изображения:

Получаем хеш второго изображения:

Получаем расстояние Хэмминга между двумя изображениями:

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

Например, при зеркальном отражении — картинка остается неузнанной.
Зато с цветами можно играться сколько угодно — на результат сравнения это не повлияет.
Чего нельзя сказать о манипуляциях с RGB-каналами, Джона опять не узнали, хоть и расстояние Хэмминга для такого случая гораздо меньше.

Остальные результаты выглядят так:

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

**то же самое, что и с кропом. При повороте на пару градусов расстояние незначительное, но чем больше угол наклона — тем сильнее различие.

Источник

Поиск изображений по фрагменту

В своем выступлении Александр Крайнов рассказал каким способом Яндекс.Картинки кластеризировали дубликаты изображений. Другими словами, выделяли и отфильтровывали дубли картинок. Где основная идея была в том, чтобы выделить контуры изображения посредством фильтра DoG, после чего найти ключевые точки и получить их дескрипторы.
Кластеризация дубликатов сводится к поиску совпадений дескрипторов. Это и есть «цифровой формат» ключевых точек из статьи Кластеризация дубликатов в поиске по картинкам.

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

Дескрипторы

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

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

Но надо с чего-то начинать, поэтому обратимся на помощь к библиотеке OpenCV.

Первое на что бросается взгляд — это дескрипторы SURF.
Которые обещают необычайную точность. Что и подтверждается после тестов.

Но есть несколько нюансов.
Дескрипторы SURF — это вектора из 128 (или 64) чисел на одну ключевую точку. Проверка на совпадение выполняется поиском ближайшей точки (или даже двух). И чем ближе точка, тем лучше.

Получается что на изображение с 1 000 ключевых точек, потребуется 128 000 чисел с плавающей точкой.
Кроме того, само обнаружение точек довольно сложная операция и требует значительное время. Что не позволяет эффективно использовать данный алгоритм на небольших устройствах. К тому же сам алгоритм закрытый и запатентован (в США).

После ознакомления с SIFT и SURF, захотелось чего-то простого в реализации с возможностью применить на небольшом сервере либо устройстве.

Перцептивные хеши

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

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

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

Другими словами перцептивные хеши не годятся для поиска полудубликатов.

Исходя из этого была предпринята попытка объединить SURF дескрипторы и перцептивные хеши с целью решить проблему поиска нечетких полудубликатов.

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

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

Сама идея о том, что бы из изображения выделялось некоторое количество отпечатков (fingerprint), которые можно было бы просто сопоставить друг с другом, завораживала.

Поэтому было решено попытаться найти решения данным проблемам.

Низкая скорость выборки

60 раз ускорить выборку из базы данных.

SURF и ключевые точки

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

В общем виде OpenCV предоставляет два типа дескрипторов:

— Дескрипторы с плавающей точкой
— И бинарные дескрипторы

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

ORB: an efficient alternative to SIFT or SURF

OpenCV уже имеет у себя отличную альтернативу SURF, которая мало того, что открытая и без лицензионных ограничений, так еще легче и работает быстрее [1].

ORB — это Oriented FAST and Rotated BRIEF — улучшенная версия и комбинация детектора ключевых точек FAST и бинарных дескрипторов BRIEF.

ORB имеет один существенный нюанс для нас — размер дескрипторов 32 байта на одну точку.
Проверка на совпадение — это сумма расстояний Хэмминга для каждого байта дескриптора (первый сравнивается с первым, второй со вторым и тд).

В нашей задаче подразумевается, что одна точка дает одно значение, а тут получается 32, которые надо еще и суммировать с соответствующими по индексу (первый с первым, второй со вторым и тд) в целевой базе данных.

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

После некоторых тестов было решено попробовать эти 32 байта представить в виде матрицы 16×16 бит. А потом эту матрицу пропустить через перцептивный хеш PHash. Результатом должно было оказаться как раз 64 битное число.

Теперь мы подошли к полному описанию концепта.

Как работает индексация

1. Получаем ключевые точки и дескрипторы ORB, выбираем количество требуемых точек на изображении.
2. Полученные дескрипторы по 32 байта представляем в виде битовой матрицы 16×16.
3. Конвертируем матрицу в 64битное число с помощью PHash.
4. Сохраняем 64битные отпечатки в MySQL.
5. Выбираем требуемое расстояние Хэмминга и запускаем демон HEngine, который будет выполнять поиск.

Как работает поиск

Выполняем идентичные шаги 1 — 3 из индексации, но только на запрашиваемом изображении.
4. Делаем запрос демону HEngine, который возвращает все хеши в заданном пределе.
5. Если требуется, отфильтровать неактуальные результаты.

Рис 1. Предел расстояния Хэмминга 7. Серые точки — это найденные ключевые точки. Зеленые — совпадающие точки. Красные — совпадающие стандартным ORB полным перебором.

А что в итоге?

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

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

Рис 2. Сладкое к пятнице

Учитывая то, что в зависимости от настроек, описанный алгоритм через бинарные дескрипторы ORB выдает около 1 000 хешей на картинку.
На базу в 1 000 изображений получается 1 000 000 хешей в базе. Поиск и кластеризация всех дубликатов занимает полторы минуты. Включает в себя полный перебор и поиск совпадающих хешей.

Источник