Какие способы существуют для поиска дубликатов и похожих изображений хэш функции
Поиск изображений в интернете уже давно стал привычным: пользователь ожидает от поисковой системы точного, быстрого и полного ответа так же, как и при поиске текстовой информации. Большинство популярных поисковых систем следом за поиском веб-страниц с текстовой информацией начали работать над поиском изображений.
Компания Picsearch выпустила первую публичную версию поиска по изображениям в сентябре 2001 года. В июле того же года запустил свой поиск по картинкам Google. Яндекс.Картинки официально открылись в июле 2002 года, став первым российским поисковиком, ищущим изображения. В ноябре 2003 г. Yahoo! добавил справа от поисковой строки меню с опцией поиска по изображениям в том числе.
На начальном этапе своего существования поиск изображений основывался исключительно на извлечении и анализе метаданных, связанных непосредственно с изображениями: атрибутов alt, заголовков страниц и текстов ссылок на изображения. Постепенно для поиска изображений стали учитывать также и текст, расположенный на той же веб-странице, что и картинка. Таким образом, задача поиска изображений некоторое время ограничивалась нахождением всей возможной относящейся к нему текстовой информации, и определением степени правдоподобия, с которой эта информация относится именно к изображению.
Параллельно с поиском изображений по метаданным развивалось, и продолжает успешно развиваться, другое направление – поиск изображений по их содержанию. Этот вид поиска основывается на технологии компьютерного зрения. Она призвана обучить машину смотреть на изображение глазами человека, понимать и анализировать его содержимое: цвета и формы объектов, их текстуру, взаимное расположение. Набор метаданных, характеризующих изображение, ограничен, а компьютерное зрение позволяет значительно расширить количество атрибутов, которые учитываются при поиске картинок и ранжировании результатов.
Наглядным примером внедрения технологии поиска изображений по содержанию являются разнообразные фильтры в расширенном поиске Яндекс.Картинок: преобладание цвета, клипарт, графика, фотография, портрет. В основе работы этих фильтров – анализ одного или нескольких свойств изображения: цвет, градиенты, наличие однородного фона и другие. Каждый раз, когда пользователь включает тот или иной фильтр, происходит сравнение всех найденных изображений с некой абстрактной моделью-образцом, которая идеально соответствует данному типу изображения. Таким образом из результатов поиска исключаются изображения, не обладающие свойствами этой идеальной модели, либо обладающие ими не в той степени.
Более сложная задача, которая решается с помощью технологии поиска изображений по содержанию, - это поиск похожих изображений.
Какие картинки более схожи между собой?
Разные люди по-разному ответят на этот вопрос. Для одних – важнее цветовая схожесть, для других – схожесть форм, для третьих – текстур, а иногда - всё вместе в одинаковой пропорции. Какие же критерии являются определяющими? Даже человек, не говоря уже о машине, затрудняется порой объяснить, на чём основан его выбор в данном конкретном случае. Это всегда совокупность факторов при частом доминировании одного из них. Сложность в том, чтобы обучить машину понимать, какой фактор важнее в каждом конкретном случае. К тому же при поиске похожих изображений, в отличие от упомянутой выше работы фильтров, сравнение каждый раз происходит с новой картинкой-образцом, а не с одной и той же моделью. Для этого нужно обучить машину анализировать не отдельные свойства изображения, а всю их совокупность. Она должна за сотые доли секунды находить среди миллионов проиндексированных картинок изображения, максимально похожие на картинку-образец, учитывая при этом представления о похожести у разных пользователей.
На Яндекс.Картинках появилась первая версия поиска похожих изображений. В результатах поиска рядом с большинством картинок можно увидеть ссылку «похожие», при клике на которую открывается страница с изображениями, похожими на выбранное. Таким образом, используются оба направления поиска изображений - картинка-образец ищется по метаинформации, а похожие - с помощью технологии поиска изображений по их содержанию.
Конечно, мы будем совершенствовать поиск похожих изображений и дальше развивать функционал Яндекс.Картинок. Результаты можно будет увидеть в самое ближайшее время :)
За последние несколько месяцев несколько человек спросили меня, как работает 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, я не знаю всех деталей их алгоритма, но похоже на какой-то вариант перцептивного хэша. И поскольку хэш-функция сводит всё что угодно на низкие частоты, то мой кривой рисунок трёх фигурок с ручками-палочками может сравниться с другими изображениями, в том числе с фотографиями, на которых изображены трое людей.
Недавно, в связи с разработкой новой линейки продукции, в нашей компании встала задача поиска идентичных изображений в базе.
Отдавать реализацию на аутсорс слишком дорого и не гарантирует наилучшего решения. Отдать на откуп фрилансеру — дешевле, но и решение скорее всего будет таким же дешевым и основанным на существующих библиотеках, типа OpenCV. Но если бы задача решалась так просто, то конкуренты уже давно бы этим воспользовались и сделали достойный продукт, но его на рынке нет. В общем, присущие нам перфекционизм, амбициозность и желание быть лучшими, не позволяют нам выводить на рынок продукт «как у всех», нам нужно лучше, быстрее, сильнее. Приняли решение самостоятельно разобраться в вопросе, выработать решение, написать подробное техническое задание и уже отдать на реализацию фрилансеру. Была надежда, что существуют готовые решения, которых просто не заметили конкуренты. Но изучив вопрос (а вместе с ним и алгоритмы ORB, BRIEF, FAST, SIFT, SURF, BRISK, A-KAZE, Viola-Jones и еще несколько) стало понятно, что у всех этих алгоритмов есть свои недостатки. Хотя для решения нашей задачи некоторые из вышеперечисленных алгоритмов и подходили, но как то неожиданно захотелось уникальности и простоты решения. И вот выношу на суд сообщества, алгоритм собственного сочинения.
Любителей покритиковать (конструктивно) прошу под кат.
Соотношение сторон
Визуально одинаковые изображения, как правило, обладают близкими соотношениями ширины и высоты. Отсюда логичный вывод — сравнивать только изображения с близкими соотношениями сторон. На практике, большинство изображений в одной коллекции, как правило, имеет одинаковое соотношение сторон (например — 3:4), но имеет разную ориентацию (вертикальную или горизонтальную). Таким образом, мы получаем два изолированных класса изображений, которые не обязательно сравнивать друг с другом. Приблизительное ускорение алгоритмов от этого факта — около двух раз.
1. Принцип работы алгоритма
Изначально, и это принципиально, был выбран способ сравнения изображений основанный на поиске и сравнении т.н. ключевых точек.
Как и любой (или практически любой) алгоритм подобного рода, мой состоит из следующих шагов.
Шаг 1. Поиск ключевых точек на изображении.
Шаг 2. Формирование дескриптора.
Шаг 3. Формирование бинарной строки (хэша).
Шаг 4. Сравнение хэшей обрабатываемого изображения с хэшами изображений хранящимися в БД.
Шаг 5. Получение результата в требуемом виде.
3.1. К достоинствам приведенного алгоритма можно отнести:
- Простоту,
- Высокую скорость работы,
- Гибкость (можно применять различные методы поиска ключевых точек, в зависимости от задачи, характеристик изображения и необходимой точности).
- Возможность применять для изображений разного качества, благодаря коэф. лояльности Е.
- Инвариантность к повороту и масштабированию изображения.
Мера схожести изображений
При сравнении похожих изображений первым встает вопрос: что считать мерой схожести изображений? Очевидно, что это величина имеет значение обратное различию изображений друг от друга. Следственно нужно выбрать некую метрику, характеризующую различие изображений друг от друга. Тогда схожими изображениями будут считаться изображения, отличие между которыми меньше некоторого порога. Для изображений с одинаковыми габаритами, обычно такой мерой различия служит среднеквадратическое отклонение пикселей одного изображения от другого. Хотя конечно, нам ни что не мешает выбрать другую метрику, например усредненную абсолютную разность пикселей изображений друг от друга.
2.1. Поиск ключевых точек на изображении.
Ключевая (особая точка, или особенность) – это точка изображения, удовлетворяющая ряду свойств:
- Определенность (distinctness) – особенность должна выделяться на фоне среди соседних точек.
- Устойчивость (repeatability) – изменение яркости, контрастности и цветовой гаммы не должны влиять на место особой точки на объекте или сцене.
- Стабильность (stability) –зашумленность изображения, не превышающая определенный порог, не должна влиять на работу детектора.
- Интерпретируемость (interpretability) – особые точки должны быть представлены в формате, пригодном для дальнейшей работы.
- Количество (quantity) – количество обнаруженных особых точек должно обеспечивать требуемому их количеству для обнаружения объектов.
Для поиска особых точек я использую «Детектор FAST» как лучший по соотношению скорость работы к качеству, хотя для других задач можно использовать и другие детекторы.
Далее с помощью «Детектора углов Харриса» отбираем не большое (у меня это 50) количество самых значимых ключевых точек.
* С принципами работы детекторов FAST и Харриса, можно ознакомиться в интереснейшей статье lightsource "Детекторы углов".
2. Описание работы алгоритма
Недостатки быстрого алгоритма
В целом эффективность индексирования сильно зависит от порога схожести изображения — при нулевом пороге сложность поиска похожих изображений приближается к линейной О(N), а при большом пороге к квадратичной О(N^2). Тем не менее, это является значительным прогрессом, так как в базовом варианте алгоритма сложность поиска всегда квадратична О(N^2). Также стоит отметить, что на практике для реализации сортировки по n-мерному индексному пространству приходится организовывать n-мерный массив со списками изображений, лежащих в определенном диапазоне индексов. Что вносит дополнительные накладные расходы и делает неоправданным использование индексирования большой размерности, а также не эффективность такого индексирования для небольших коллекций изображений.
В целом, если суммировать все улучшения, которые применяются в улучшенном варианте алгоритма, то получаем выигрыш на 3-4 порядка по сравнению с базовой реализацией. Тесты на больших коллекциях изображений показывают, что это действительно так. Так непосредственно сравнение изображений друг с другом занимает порядка 30 сек на одноядерном процессоре для коллекции 100 тысяч изображений. На практике, скорость сравнения становится несущественным фактором в общем процессе поиска изображений — ведь их еще нужно найти, считать с диска и сформировать уменьшенные изображения (хотя конечно последние два пункта можно выполнять только 1 раз, так как очевидно, что уменьшенные изображения весом всего по 1000 байт целесообразно сохранять для повторного использования).
Надеюсь, что читателей заинтересовало мое изложение. Возможно, даже кому-то показалось полезным. Жду отзывов.
C момента написания данной статьи прошло достаточно много времени. Я решил сделать небольше дополнение к ней. В рамках проекта Simd был написан класс на C++ ImageMatcher, который реализует алгоритм, описанный в данной статье. Приятного использования!
В этом посте мы пытаемся достичь вышеуказанного результата, то есть, учитывая изображение, мы должны быть в состоянии найти похожие изображения изБаза данных Caltech-101, В этом посте рассказывается о том, как я это сделал. Вся база кода для репликации проекта находится в моемGitHub репозиторий, Процесс достижения вышеуказанного результата можно разбить на следующие несколько шагов:
- Передача обучения по модели ResNet-34 (обученной в ImageNet) для обнаружения 101 класса вНабор данных Caltech-101с помощьюFastAIа такжеPytorch,
- Возьмите выходные данные второго последнего полностью подключенного слоя из обученной модели ResNet 34, чтобы получить вложение для всех 9,144 изображений Caltech-101.
- Используйте локально-чувствительное хеширование, чтобы создать LSH-хеширование для встраивания нашего изображения, что позволяет быстро приближенно искать ближайшего соседа
- Затем по заданному изображению мы можем преобразовать его во встраивание изображения, используя нашу обученную модель, а затем выполнить поиск похожих изображений, используя Приблизительный ближайший сосед в наборе данных Caltech-101.
Как я упоминал выше, для этого проекта моя цель состоит в том, чтобы запросить любое изображение и найти семантически похожее изображение вБаза данных Caltech-101, Эта база данных содержит 9,144 изображений, разделенных на 101 категории. В каждой категории около 50–800 изображений.
Первое упражнение в нашем проекте - создать сеть глубокого обучения, которая может точно классифицировать эти категории. Для этой задачи мы будем использовать предварительно обученную сеть ResNet 34, которая обучена работе с базой данных ImageNet, и перенесем ее на обучение для классификации 101 категории базы данных Caltech-101 с использованием Pytorch 1.0 и библиотеки FastAI. Как я уже писал о том, как сделать перенос обучения с любым данным набором в моемпредыдущий блогЯ просто собираюсь изложить процесс в этом блоге. Вы можете обратиться кэтот блокнотчтобы найти код, чтобы сделать то же самое. Ниже приведены шаги, чтобы выполнить трансферное обучение для классификации изображений Caltech-101 -
- Загрузка данных с использованием загрузчиков наборов данных Pytorch с использованием библиотеки FastAI
- Возьмите предварительно обученную сеть, в данном случае ResNet 34, и удалите последние полностью подключенные слои.
- Добавьте новые полностью связанные слои в конце сети и обучите только те слои, используя изображение Caltech-101, сохраняя все остальные слои замороженными
- Обучите всю сеть, разморозив все слои
Теперь, когда у нас есть предварительно обученная сеть, нам нужно извлечь вложения из этой сети для всех наших изображений Caltech-101. Встраивание - это не что иное, как представление объекта в N-мерном векторе. В этом случае встраивание изображения является представлением изображения в N-измерении. Основная идея заключается в том, что чем ближе данное изображение к другому изображению, их вложение также будет сходным и близким в пространственном измерении.
Визуализация встраивания изображений. Кредит -Блог
Вы можете увидеть на изображении выше, взятом изэтот блогэто вложение изображения является пространственным представлением изображения в векторизованной форме, где сходные изображения также близки в пространственном измерении.
Мы можем получить вложения изображений из ResNet-34, взяв выходные данные его второго последнего полностью связанного слоя, который имеет размерность 512. Чтобы сохранить промежуточные вычисления в модели глубокого обучения в Pytorch для проверки или в нашем случае для извлечения вложений, мы использовать Pytorch Hooks. Крючки могут быть двух типов - вперед и назад. Прямые перехватчики используются для сохранения информации, передаваемой вперед в сети, чтобы сделать вывод, в то время как обратные перехватчики используются для сбора информации о градиентах во время обратного распространения. В нашем случае нам нужен вывод наших вторых последних Полностью связанных слоев на этапе вывода, что означает, что нам нужно использовать прямой хук. Давайте посмотрим на код для создания хука (также в разделе «Извлечение функции» моегоблокнот) -
Приведенный выше код - это все, что вам нужно для создания хука Pytorch. Класс SaveFeatures вызываетregister_forward_hookфункция отмодуль torch.nnи с учетом любого уровня модели он сохранит промежуточные вычисления в массиве, который можно получить с помощью функций SaveFeatures.features. Давайте посмотрим код для использования этого класса -
Строка 1–2: вызывает класс SaveFeatures, используя в качестве входных данных ссылку на слой модели на выход второго последнего полностью связанного слоя.
Строка 4–6: Передача данных Caltech-101 для получения их прогнозов. Обратите внимание, что нас не интересует сохранение прогнозов, и поэтому мы использовали «_». В этом случае промежуточный вывод вторых последних слоев сохраняется в переменной с именем «sf», которая является экземпляром класса SaveFeatures.
Строка 8–10: создание словаря python, где путь к изображению является ключом, а вложения изображения - это значение
Теперь у нас есть встраивание представления каждого изображения в Caltech-101 в нашем словаре.
Мы можем использовать наши недавно сгенерированные вложения изображений Caltech 101 и получить новое изображение, преобразовать его во встраивание, чтобы вычислить расстояние между новым изображением и всей базой данных Caltech 101, чтобы найти похожие изображения. Этот процесс по своей природе дорогостоящий в вычислительном отношении, и, поскольку новое вложение изображения необходимо сравнить со всем встраиванием изображения 9K + в базу данных Caltech 101, чтобы найти наиболее похожее изображение (ближайший сосед), которое в обозначении сложности вычислений является проблемой O (N²) и будет занимать экспоненциально больше времени для извлечения похожих изображений по мере увеличения количества изображений.
Чтобы решить эту проблему, мы будем использовать локально-чувствительное хеширование (LSH), которое является приближенным алгоритмом ближайшего соседа, который уменьшает вычислительную сложность до O (log N).Этот блогобъясняет LSH в хороших деталях с точки зрения сложности времени и реализации. Короче говоря, LSH генерирует хэш-значение для встраивания изображений, сохраняя при этом пространственность данных; особенно; элементы данных, которые похожи в высоком измерении, будут иметь более высокую вероятность получения того же значения хеш-функции.
Ниже приведены шаги о том, как LSH преобразует вложение в хэш размера K-
- Генерация K случайных гиперплоскостей в размерности вложения
- Проверьте, находится ли конкретное вложение над или под гиперплоскостью, и назначьте 1/0
- Выполните шаг 2 для каждой K гиперплоскостей, чтобы получить хеш-значение
Давайте теперь посмотрим, как LSH будет выполнять запрос ANN. Учитывая вложение нового изображения, мы будем использовать LSH, чтобы создать хеш для данного изображения, а затем сравним расстояние от встраивания изображений из набора данных Caltech-101, который имеет такое же значение хеш-функции. Таким образом, вместо поиска сходства по всей базе данных Caltech-101, мы будем выполнять поиск сходства только с подмножеством изображений, которые имеют одинаковое значение хеш-функции с входным изображением. Для нашего проекта мы используемlshash3пакет для приблизительного поиска ближайшего соседа. Давайте посмотрим на код, чтобы сделать то же самое (вы можете найти код в разделе «Использование хеширования с учетом локальных особенностей для поиска похожих изображений» моегоблокнот) -
Приведенный выше код берет словарь встраивания изображений и преобразует его в таблицу LSH. Чтобы запросить таблицу LSH, мы можем использовать код ниже -
Теперь у нас есть созданная таблица LSH. Давайте напишем скрипт, который может принимать URL-адрес изображения и предоставлять нам N (определенных пользователем) похожих изображений из базы данных CalTech 101. Код для этой части на моемGithub здесь,
Скрипт выполняет следующую задачу -
- Загрузите таблицу LSH и нашу модель ResNet 34 (функция load_model)
- Возьмите URL-адрес изображения из звонка пользователя и загрузите изображение (функция download_img_from_url)
- Передайте изображение из ResNet-34, чтобы получить вложение изображения 512 размеров (функция image_to_vec)
- Запросите его с помощью таблицы LSH, чтобы найти N (пользовательских) похожих изображений и их путь (функция get_simil_images)
- Вернуть вывод по желаемому выходному пути, при желании отобразить его с помощью Open CV (функция get_s Similar_images)
Мы можем использовать аналогичную концепцию в различных приложениях, таких как поиск похожих изображений в нашей фотогалерее, рекомендации по элементам для похожих элементов, поиск по изображениям в Интернете, поиск почти дублированных изображений и т. Д.
Резюме (TL; DR),
В блоге мы увидели применение глубокого обучения в поискесемантически похожие изображенияи как сделатьпримерный ближайший соседзапрос с использованием локально-чувствительного хеширования (LSH), чтобы ускорить время запроса для больших наборов данных. Кроме того, важно отметить, что мы использовали LSH не для необработанных функций (изображений), а для встраиваний, которые помогаютбыстрый поиск сходства в огромных коллекциях.
Одномерное индексирование изображений
Как известно, поиск в упорядоченном массиве данных может быть осуществлен за время порядка О(ln(N)), в отличие от неупорядоченного, которое требует О(N). Таким образом, если каким-то образом нам удастся упорядочить изображения, то теоретически можно свести квадратичную сложность поиска О(N^2) к квазилинейной — О(N*ln(N)). И так попытаемся создать индекс, с помощью которого мы будем производить сортировку изображений. Для этого берем нашу уменьшенную картинку размером 4х4 и уменьшаем ее еще в два раза до размера 2х2. Из этой картинки легко сформировать первый индекс:
который представляет собой среднюю яркость нашего изображения. Фактически, это изображение, уменьшенное до размера 1х1. Среднеквадратическая разность исходных изображений, будет не меньше, чем разность их интенсивностей. Таким образом, если порог для сравнения изображений имеет значение t, то все возможные кандидаты на сравнение должны иметь среднюю яркость в диапазоне от i[0] — t до i[0] + t. Фактически, если мы отсортируем все изображения по индексу i[0], то можем проводить сравнение со значительно меньшим числом изображений — 2*t/255. Не сложно подсчитать, что для типичного порога в 5% — имеем теоретический выигрыш в 10 раз. Практически, выигрыш будет меньше, так как статистическое распределение изображений по средней яркости не равномерно в диапазоне [0. 255], а имеет колоколообразный максимум вблизи значения 127 и спадает по краям диапазона. Его фактическая ширина, а следственно и практический выигрыш алгоритма от теоретически возможного составляет порядка 70-80%.
3.2. К недостаткам я бы отнес:
- Отсутствие инвариантности к искажениям перспективного характера. Хотя в некоторой степени этого можно достичь если разделить исходное изображение на не большие фрагменты и увеличить коэф. Е.
- Не возможность поиска куска изображения в большом изображении.
Картинки разных размеров
Вопрос несколько усложняется, если нужно сравнить изображения разных размеров. Однако достаточно очевидным решением этой проблемы является приведение всех изображений к одинаковому размеру. Остается выбрать это размер — если выбрать его слишком маленьким, то очевидно, что различия между изображениями тогда будут нивелироваться, и у нас будет много ложно положительных срабатываний. При слишком большом размере неоправданно повышается ресурсоёмкость алгоритма сравнения. Опыт показывает, что наиболее оптимальным является размер приведенного изображения от 16х16 до 64х64. Так же опыт показывает, что цветовые характеристики изображения оказывают гораздо меньшее влияние на визуальные ощущения схожести изображений по сравнению с яркостными, потому их можно отбросить.
3.3. Неопределенность
Не являясь программистом, я не имею возможности самостоятельно проверить алгоритм в работе. Буду рад, если кто-то из членов Хабра-сообщества, сможет реализовать программно этот алгоритм и протестировать его в работе.
После такой проверки мы сможем отнести самый важный параметр «точность работы» к достоинствам или недостаткам моего алгоритма.
2.2. Формирование дескриптора
Дескриптор (от лат. descriptor — описывающий) – описание особой точки, определяющее особенности её окрестности, представляет собой числовой или бинарный вектор определенных параметров. Длина вектора и вид параметров определяются применяемым алгоритмом. Дескриптор позволяет выделить особую точку из всего их множества на изображении, это необходимо для составления ключевых пар особенностей, принадлежащих одному объекту, при сравнении разных изображений.
На этом шаге, я предлагаю отойти методов описания ключевых точек, которые обычно используются в подобных алгоритмах и обратиться к более простым методам.
Я предлагаю, вместо того, чтобы описывать каждую ключевую точку через ее окружение, измерить расстояния от каждой такой точке к оставшимся точкам. Т.е. проложить все возможные отрезки между найденными точками и измерить их длинны.
Так вот, такое полученное, в результате измерения, число (длину отрезка), я и предлагаю называть дескриптором.
Основные шаги
- Приведение всех изображений к одному размеру (возьмем для определенности размер 32х32).
- Отбрасыванию цветовой информации (преобразование в серое изображение).
- Нахождение среднеквадратической разности для каждой пары уменьшенных серых изображений.
- Сравнение полученной среднеквадратической разности с некоторым порогом.
Предварительное сравнение
Первый самый очевидный шаг: если мы один раз уменьшили изображение, то почему бы не сделать это снова? Делаем из картинки 32х32 картинку размером 4х4, где каждая точка уменьшенного изображения представляет собой усредненную яркость соответствующей части исходного изображения размером 8х8. Можно математически строго доказать, что среднеквадратическая разность для этого уменьшенного изображения будет не больше, чем среднеквадратическая разность исходного изображения. Следовательно, мы можем путем предварительного сравнения уменьшенных изображений размером 4х4 создать своеобразный фильтр, который будет отсеивать большую часть кандидатов на полноценное сравнение (при условии, что в выборке большая часть изображений относительно уникальны). Таким несложным приемом можно достичь, как несложно подсчитать, практически 50-и кратного ускорения. Однако, очевидно, что чем выше порог, с которым мы сравниваем изображения, тем меньше эффективность данного фильтра.
Недостатки базового алгоритма
К недостаткам данного алгоритма, можно отнести его плохую чувствительность при сравнении слабо контрастных изображений, а также изображений без крупномасштабных особенностей (контурные рисунки, изображения текста). Слабая чувствительность объясняется тем, что при уменьшении исходного изображения до размера 32х32, как правило все такие изображения становятся не различимыми друг от друга. Также недостатком данного подхода можно считать квадратическую зависимость времени исполнения алгоритма в зависимости от общего числа изображений, так как нужно провести сравнение для каждой пары изображений. Так для сравнения пары отнормированных изображений друг с другом алгоритму нужно выполнить порядка 10^3 арифметических операций, то для тысячи изображений это уже порядка 10^9 операций, а для миллиона изображений — 10^15 операций. Конечно не у каждого пользователя есть коллекции изображений с миллионом картинок, но даже для сравнения 100 тысяч изображений (что не является такой уж редкостью для фотолюбителей) нам требуется выполнения порядка 10^13 операций, что может занять существенное время даже на современном железе.
Как уже было сказано, у данной базовой реализации алгоритма две проблемы — невысокая точность на изображениях без крупномасштабных особенностей и квадратичная зависимость времени исполнения от общего числа изображений. Первая проблема достаточно специфична и характерна для довольно узкого круга изображений, потому далее мы сосредоточимся на решении второй проблемы. Очевидно, что данный алгоритм хорошо распараллеливается и векторизуется. Однако, в рамках данной статьи мне хотелось бы остановиться не на программной, а на алгоритмической оптимизации данного алгоритма.
3. Достоинства и недостатки алгоритма
Многомерное индексирование изображений
Помимо средней яркости i[0], из изображения размером 2x2 можно построить еще 3 дополнительных индекса:
i[1] = 128 + (p[0][0] — p[0][1] + p[1][0] — p[1][1])/4,
i[2] = 128 + (p[0][0] + p[0][1] — p[1][0] — p[1][1])/4,
i[3] = 128 + (p[0][0] — p[0][1] — p[1][0] + p[1][1])/4,
которые имеют простой физический смысл: индекс i[1] показывает на сколько левая часть изображения ярче чем правая, i[2] — на сколько верхняя часть ярче нижней, а i[3] — на сколько отличаются диагонали изображения. По всем этим индексам можно также отсортировать изображения, как и по первому, причем все возможные кандидаты на сравнение будут лежать в диапазонах от i[j] — t до i[j] + t. Т.е. в четырехмерном пространстве, образованном этими индексами область поиска будет представлять 4-х мерный куб со стороной 2*t и центром с координатами, образованными индексами искомого изображения. Теоретическое ускорение, равно отношению объема этого 4-мерного куба к общему объему индексного пространства и равна (2*t/255)^4 = 1/10000. Практическое ускорение значительно скромнее, так как эффективная ширина распределения изображений по индексам i[1] и i[2] составляет порядка 40-50%, а i[3] — всего 20-30% от максимально возможного. Из-за узкого фактического диапазона, на практике использование последнего индекса часто вообще не целесообразно, потому можно ограничиться первыми 3-мя индексами. Тем не менее практически достижимое ускорение достигает двух порядков (для пороговой разности в 5%).
2.4. Сравнение хэша с БД
Для поиска подобных изображений в БД нужно сравнить полученный нами хэш А1, А2. А1225 с хранящимися в БД.
Для примера сравним хэш А1, А2. А1225, где А1>А2>. >А1225 с В1, В2. В1225 причем пусть дескрипторы А трехзначны, а дескрипторы В четырех. Это может быть в двух случаях, если изображения разные или если одно изображения в разных масштабах.
Для достижения инвариантности к масштабу приведем каждый дескриптор к единому масштабу. Для этого определяем максимальное число М той же разрядности, что и разрядность большего дескриптора (для нашего примера максимальное четырехзначное число М = 9999) и находим коэф. масштабирования К по формуле: Ка=М/А1 (для строки А1, А2. А1225) и Кв=М/В1 (для строки В1, В2. В1225). Далее приведем хаши к единому масштабу, для это перемножим каждый дескриптор хэша А на Ка, а каждый дескриптор хэша В на Кв. Запишем результаты в строки А'1, А'2. А'1225 и В'1, В'2. В'1225, округляя значения до целого числа. В результате получим 2 хэша одного масштаба и одной размерности.
Теперь строки А'1, А'2. А'1225 и В'1, В'2. В'1225 можно сравнивать. Для этого будем использовать модифицированную формулу расстояния Хемминга.
Дело в том, расстояние Хемминга учитывает количество ошибок, как количество не равных значений в строках. Но мы на предыдущем шаге применили округление до целого числа, что может привести к ложным результатам. Поэтому мы не будем считать ошибкой, если значения соответствующих дескрипторов строк А и В, отличаются на Е (т.е. разность Аi и Вi взятая по модулю должна быть больше Е, для того, что бы считать значения в строках не равными). Назовем Е «коэф. лояльности» и в общем случае принимаем Е=1.
Далее простым суммированием считаем количество ошибок. Получаем расстояние Р.
2.3. Формирование хэша
Как известно через Х точек можно проложить Х*(Х-1)/2 отрезков, т.е. из 50 точек можно составить 50*49/2=1225 отрезков. Т.е. наша строка будет состоять из 1225 целых чисел. Причем эти числа должны иметь одинаковое количество знаков. Требуемое количество знаков, выбирается исходя из разрешения изображения (например, для изображения 500*500 максимальна длина отреза 707 (по диагонали), а значит знаков должно быть 3).
Для достижения инвариантности к повороту в плоскости, запишем длинны отрезков в строчку не по мере их вычисления, а от большего к меньшему.
Получим строку: А1, А2. А1225, где А1>А2>. >А1225
Основные этапы улучшенного алгоритма
- Приведение всех изображений к одному размеру (32х32) и отбрасывание цветовой информации.
- Нахождение уменьшенного изображения для предварительного сравнения размером 4х4.
- Построение n-мерного индекса изображения на основании изображения для предварительного сравнения.
- Определение границ области поиска в n-мерном индексном пространстве.
- Проверка соотношения сторон у кандидатов из этой области.
- Проведение предварительного сравнения изображений с кандидатами прошедшими предыдущий пункт.
- Проведение полноценного сравнения изображений с кандидатами прошедшими предыдущие пункты.
2.5. Получение результатов
Для разных задач, может понадобится разное представление результатов работы алгоритма.
2.5.1. Оценка схожести 2х изображение
Результатом будет показ вычисленного на шаге 2.4. расстояния 2х хэшей Р. Или их оценочное значение. Например, при Р можно считать, что изображения идентичны; при 10 — изображения похожи; и т.д.
2.5.2. Поиск изображения в БД максимально похожего на исследуемое
Читайте также: