Определение процента % похожести двух картинок онлайн
Главное нужно указать две картинки на вашем компьютере или телефоне, нажать кнопку OK внизу. Остальные настройки выставлены по умолчанию.
Если обе картинки похожие, то их процент похожести будет равным 90-100%, а если разные — обычно меньше 70%. На этом сайте также есть автоматическое выделение отличий двух похожих изображений.
Исходные изображения никак не изменяются. Вам будет предоставлен процент похожести двух картинок.
Compare & find Differences in two Image Files
�� Free Online Diff Checker Tool to Compare Two Image Files
How to Compare Two Images and find Changes?
- To compare and contrast two images files you can simply drop or choose two images on the two side-by-side boxes to the top.
- The box below them will show a generated 'diff' image, pink areas show mismatch.
- Then you tweak options like tranparency, diff color, anti-aliasing etc.
- You can also download the result diff image as .png file by click on the Download button.
Example diff ��
Is image comparison processed & stored on remote server?
No, all the processing is done on your �� browser, so nothing is saved on our server unless you choose to save.
You can download the image as png file to share diff with others.
What features does this Image Compare tool Have?
It has enough features to cover all your needs like ignoring colors, ignoring transparency, ignoring antialiasing etc. The diff image can be opaque or Transparent for suitable visibility.
Поиск похожего изображения
tl;dr; Качаем фотографии из интернетов. Натренированной нейросетью VGG19 вычисляем 4096-мерные вектора каждого изображения. Косинусной метрикой находим ближайшего соседа к целевой картинке. Получаем наиболее похожие картинки в каком-то смысле. Profit!
Source code.
Введение
Еще каких-то 5 лет назад, чтобы сделать свой поиск по картинкам, приходилось погружаться в тонкости машинного зрения. Нужно было придумывать то, каким образом преобразовать картинку в некоторый индекс, отпечаток, по которому можно найти другую, похожую на неё. Судя по всему, для этих целей могли использовать перцептивные хеши и вариации, разные преобразования характеристик изображений и даже каскады Хаара. В общем, всё это напоминало классические алгоритмы эпохи до машинного обучения, когда исследователям основываясь на их восприятии самим приходилось придумывать некоторые модели. Это всё безумно интересно и серьезно, можно защитить не один диплом и диссертацию. Но что примечательно, сейчас существует достаточно простой способ для построения своего собственного движка поиска похожих картинок и начать решать свои бизнес задачи немного проще, чем это было раньше.
Что такое “похожие” изображения
Прежде чем мы рассмотрим существующие подходы, необходимо правильно поставить вопрос — определить метрику похожести изображений. Но проблема подстерегает нас сразу, так как эта метрика может отличаться от задачи к задаче. Например, нам нужно находить исходное изображение по черно белому экземпляру. А может, необходимо находить картинки близкие по цветовой гамме. Возможна и постановка задачи, когда похожими считаются изображения со схожими формами объектов. А будет ли похожи фотографии одной и той же собаки в разных ракурсах или похожи фотографии разных собак, но в одном ракурсе.
Как видите, есть некоторые трудности в постановке задачи. Обычно даже не говорят, что две фотографии похожи, а рассматриваю некоторую величину похожести от, скажем, нуля — совершенно похожи, до бесконечности — совершенно не похожи. Измерение этой величины будет зависеть от той формы индексов, которые будет давать некоторый алгоритм; это может быть расстояние Хемминга или расстояние между точками в многомерном пространстве, или ещё что-то. Выбор метрики естественно будет влиять на результат не меньше, чем сам алгоритм поиска признаков в изображениях.
Обзор существующих классических решений
Если посмотреть на обычные алгоритмические методы сравнения изображений, то в основном всё сводится к вычислению некоторой хеш функции над изображением, а потом вычислению расстояния, например, Хэмминга между двумя значениями хешей. Чем меньше расстояние, тем больше картинки похожи между собой.
Далее начинается типичный для алгоритмических моделей путь выбора некоторой магической функции, которая будет сохранять в себе похожесть изображений. Один из примеров таких функций — это перцептивный хеш. В этом подходе с помощью дискретного косинусного преобразования оставляют так называемые нижние частоты, в которых сконцентрировано больше информации о форме изображения, чем о его цветовых характеристиках. В итоге большое изображение превращается в 64-битный хеш.
Есть еще несколько алгоритмов, даже на основе каскадов Хаара, но в результате так или иначе, алгоритм очень сильно страдает от преобразований над изображением: от поворотов, отражений, изменений размера, модификации цветности. Но тем не менее они очень быстро работают. Их можно использовать для поиска дубликатов с незначительными искажениями. Но для поиска изображениях, в которых “похожие” определяются в том смысле, что на них изображены коты, а не собаки, алгоритмы этого типа не подходят, да в принципе этого от них и не требуют. Забавно, что еще в 2011 году в комментариях к статьям писали, что невозможно написать такой алгоритм для кошек-собак.
Предлагаемый подход весьма наивный и простой, основывается на использовании машинного обучения и нейросетей. Так сразу в лоб и не совсем понятно чему надо обучать модель. Мы сами не можем сформулировать понятие “похожесть”. Тем не менее есть способ, и для его использования нам понадобится для начала решить задачу классификации.
Классификация изображений
На качественно ином уровне задачу классификации изображений начали решать с 2013 года. Тогда на наборе данных ImageNet пробили барьер в 15% ошибок классификации тысячи видов объектов. С тех пор за 5 лет было спроектировано и натренированно очень много разных моделей нейросетей, и был пробит барьер в 5% ошибок. Самыми успешными из них считаются: VGG16, ResNet50, Inception, GoogLeNet и много других. Большинство их них построено на основе свёрточных нейросетей.
На рисунке вы можете посмотреть как выглядит схематически архитектура VGG16.
Слои нейросети на изображении состоят из набора разных фильтров-сверток. Каждый из фильтров отвечает за поиск определенного шаблона, и когда он находит некоторый участок изображения, в котором есть этот узор, то фильтр посылает сигнал в следующий слой. В свою очередь сигналы предыдущего слоя составляют новое изображение для следующего слоя. На рисунке архитектуры VGG16 вы можете видеть, что сначала было цветное RGB изображение размера 224×224 пикселей с 3 каналами(red, green, blue). Потом после прохода первого слоя сверток у нас получилось изображение размера 224×224 пикселей с 64 каналами. Эти каналы уже представляют не цвета, а результаты работы каждого из 64 фильтров-свёрток. И так далее, до изображения 7×7 пикселей с 512 каналами.
Строя каскады свёрточных слоёв и обучая модель, вы получаете слои, содержащие в себе абстракции изображений. Первые слои в себе могут содержать мелкие детали: линии. Далее идут комбинации деталей — фигуры. Следующие слои уже могут содержать формы, а в конце целые объекты.
Feature Visualization of Convnet trained on ImageNet from [Zeiler & Fergus 2013]
Обратите внимание еще на одну интересную особенность свёрточных слоев в этой модели: каждый следующий слой “толще”, так как в нём больше фильтров, но “меньше”, так как изображение специально уменьшают с помощью операции MaxPooling (субдискретизация). Используют этот прием по следующей причине: важнее факт детекции некоторого признака-объекта, чем знание точного расположения этого объекта на изображении. Именно поэтому берут максимум внутри небольшого окошка, тем самым создавая карту расположений признаков.
Max Pool 2×2, http://cs231n.github.io/convolutional-networks/
Ближе к выходу модели у нас имеется маленькое изображение — карта признаков размера 7×7 пикселей с 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:
-
и Tensorflow для работы с нейросетями;
- 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 датасетом, похожими считаются изображения, на которых есть объекты одних классов. Например, фотографии с только с портфелями, только с обувью одного типа, портреты, прически, руки. Смотрите сами:
Что здесь интересного? Сеть сама решила что для нее похожее. Мы это не контролировали, оно получилось само. Мы потеряли некоторый контроль, но мы можем его вернуть, если сделаем обучения сами. И меня впечатляет то, что я не знаю как можно всё это сделать обычными алгоритмическими методами.
Кстати, на загруженных пользователем фотографиях поиск тоже работает. Обратите внимание, что здесь похожесть выражается в том, что на всех картинках есть один и тот же предмет — деревянный меч. Датасет в этом примере другой и модель немного хуже, поэтому есть ошибки.
Похож = есть один и тот же предмет
Что можно с этим делать
Какие еще реальные задачи можно решать подобным этому подходом? Приведу список первого, что пришло в голову:
Найти за полсекунды: сравниваем похожие фотографии
Привет, меня зовут Петр и я работаю в Badoo в команде биллинга. В этой статье я хочу поделиться своим опытом работы над пет-проектом по созданию хранилища фотографий с возможностью поиска дубликатов. Я расскажу, с каким багажом я вошел в этот проект, в чем заключалась задача и как её решал. В конце поделюсь результатами и почему я считаю, что это один из лучших проектов, которым я занимался.
Однажды мои знакомые попросили сделать им хранилище изображений для их проекта по модерации внешних ресурсов. Условия: срок хранения до трех лет, фотографии при этом присылаются неравномерно, в среднем поток — 150.000 картинок в сутки.
Казалось бы, достаточно банальная задача. Если бы не еще одно условие: хорошо бы сопоставлять фотографии с уже имеющимися: искать дубликаты и помечать их.
Начну с того, что есть два класса дубликатов. Первый — это миниатюры, то есть одно и то же изображение, которое растянули или сжали. Второй класс назовем полудубликатами. Это изображения, которые получены из оригинала с более серьезными изменениями. Типичный пример: отрезали у изображения верх с водяным знаком и добавили свой:
Эти полудубликаты нас и интересовали: мы хотели сопоставлять именно этот класс. Но мне было неясно, как решить эту задачу, пока я не наткнулся на теорию о ключевых точках, которой очень загорелся, воспринял как личный вызов и активно ею занялся. Кратко расскажу, в чем заключается теория и как она позволила нам сравнивать полудубликаты.
Ключевые точки
Ключевая точка — это некоторая особенность изображения, где что-то происходит. Например, изменение контраста, который проявляется на углах и гранях. Есть очень много алгоритмов, которые позволяют выделить эти ключевые точки, и все они работают по-разному. На одном изображении они выдадут разное количество точек да и сами точки будут отличаться. Но, как правило, все они возвращают массив из структуры из трех параметров, x, y и q, где
x, y — координаты этой самой точки на картинке;
q — это некоторый параметр, который определяет качество этой точки, то есть насколько сильным было изменение.
Для сравнения алгоритмов я ввел для себя такое понятие как покрытие. Взял набор картинок из 10.000, разбил каждую на области 16х16 пикселей и посмотрел, в какой процент таких областей попадает хотя бы одна ключевая точка:
Это было нужно, чтобы выбрать алгоритм, который лучше всего описывает тестируемые мной изображения. Если в область не попадает ни одна ключевая точка, то сравнивание в этой области проводится не будет. И чем больше таких областей, тем менее точный поиск будет. В результате я получил большую таблицу, но основные алгоритмы выделились следующие:
Исходя из таблицы, я выбрал алгоритм AKAZE: у него хоть и не самое высокое максимальное покрытие, но хорошее среднее значение и приемлемое время обработки. Стоит обратить внимание: выделение ключевых точек и анализ по этому алгоритму занимает полсекунды, что достаточно много при большом объеме изображений.
Анализ изменений
Итак, мы нашли локальную особенность на картинке. Теперь ее надо как-то описать, и в качестве примера я приведу принцип работы самого простого алгоритма — BRISK. На вход мы передаем алгоритму координаты x и y, и тот разбивает область диаметром в 30 пикселей вокруг этих координат на множество мелких частей. Дальше алгоритм бинарно сравнивает эти части между собой. Производится 512 вычислений, в результате мы получаем вектор длиной 512 бит, то есть для описания области диаметром 30 пикселей у нас уходит 64 байта. Этот вектор дальше будет называться дескриптором.
Теперь мы можем выделить ключевые точки по обоим нашим изображениям, посчитать дескрипторы и получить их массив для одного и второго изображения. И, сравнив эти строчки побитово, найти пары. Если это сделать аккуратно и визуализировать, то можно получить вот такую вот картинку:
Все алгоритмы достаточно сложны, чтобы нивелировать изменения, в частности поворот. Поэтому если просто перевернуть изображение, то ключевые точки также сопоставляются.
И вроде бы всё хорошо, но возникает другая проблема: такое прямое сравнение хорошо работает, только если изображение было сохранено без потери качества или масштабирования. Иначе появляются ошибки и дескрипторы не сопоставляются. Чтобы это исправить, я использовал одну интересную функцию.
Расстояние Хэмминга
Эта функция, которая говорит, сколько у нас есть позиций, где две строки одной длины отличаются. Рассмотрим пример:
Видно, что две бинарные строки отличаются в трех позициях, то есть расстояние Хэмминга между этими двумя строками будет равно трем. Это расстояние для простоты я буду называть дальше также ошибкой.
Выбор дескриптора
Теперь, учитывая расстояние Хэмминга, мне было нужно выбрать подходящий алгоритм. К этому времени в базе проекта было собрано много изображений, и я скриптом создал для 10,000 картинок их различные модификации: обрезал сверху или снизу, именил размеры, добавленный текст. Полученные картинки сопоставил, чтобы сравнить заведомо похожие и заведомо не похожие изображения.
Потом я построил графики для каждого алгоритма, где видно, что чем большую ошибку (расстояние Хэмминга) мы допускаем, тем больше получаем положительных, но и ложноположительных сопоставлений:
Разделив один график на другой, можно получить оптимальное расстояние Хэмминга, при котором максимально соотношение положительных к ложноположительным сопоставлениям. Например, для выбранного мной алгоритма получилось 3:
Выбирая алгоритм я также смотрел на процессорное время которое требуется на обработку изображения алгоритмом. А еще — на длину дескриптора, у разных алгоритмов его длина различна. Одно дело 8 байт, другое дело 64 на одну ключевую точку, которых будут миллиарды.
Итак, мы смогли сопоставить точки и даже нивелировали какую-то погрешность. Какие изображения теперь можно считать похожими?
Критерии
Во-первых, я пришел к выводу, что если у фото меньше 10 ключевых точек, то это, как правило, очень низкокачественные изображения. Их я просто отбрасывал, помечая как некачественные.
Во-вторых, картинки можно считать похожими, если пересечений больше 20% от возможного. Например, в одном изображении 100 ключевых точек, в другом — 200. Максимум может пересечься 100 точек, и, соответственно, достаточно 20 сопоставленных дескрипторов, чтобы эти два изображения признать похожими.
После того как мы научились сравнивать картинки, осталось только научиться искать одну в большой базе.
Как искать похожие изображения
Первой идеей был линейный поиск. Он очень простой: берем картинку и сравниваем с первой, а потом — со второй, третьей и так далее, пока они не закончатся. Номера тех что совпали — возвращаем как достигнутый результат. Но линейный поиск был вскоре отброшен. При линейном поиске с ростом базы в 2 раза время на обработку вырастает в те же 2 раза, что в итоге оказалось слишком много уже на базе в миллион.
Загружен 1 миллион изображений;
Получено примерно 350 миллионов ключевых точек;
База занимает 10 ГБ (то есть одна картинка в таком индексе занимает примерно 10 Кб).
Поиск одной ключевой точки — 47 секунд, а поиск всего изображения — 4,5 часа. Напомню, что в изначальной постановке задачи в день добавляется порядка 150 тысяч новых изображений — получится либо очень долго, либо нужно безумное количество серверов (чего не было).
Дальше я опробовал много других методов: например, HEngine, VP-деревья и разные специализированные движки. Все, кроме последних, я реализовывал на PHP. Но проблема оказалась не в производительности языка, а в алгоритмической сложности задачи, которую я пытался решить. И наконец одна интересная структура помогла мне найти решение.
Префиксное дерево
Это дерево, в котором ключ закодирован не значением в самом узле, а путем до этого узла. В префиксном дереве есть два типа узлов. Голубым я отметил узлы, которые хранят информацию только о дочерних узлах. Зеленым — те, что хранят конечную информацию, это может быть какое-то значение, массив, указатель, всё что угодно.
Вот пример префиксного дерева, где закодированы 6 строк длиной в 3 бита:
Теперь разберемся, как можно в префиксном дереве искать с допустимой ошибкой. Например, нам нужно найти все строки которые отличаются от 010 на 1 бит. То есть мы допускаем только одно искажение в любом бите:
Сначала мы идем с корня, в котором пока накоплена ошибка 0, в узел и дальше по ветке 0. Она совпадает с нашим первым битом, поэтому накопленная ошибка не увеличивается.
Идем в следующий 0, а он уже отличается от нашего второго бита, поэтому накопленная ошибка становится 1.
Она не превышает максимально допустимую, поэтому мы продолжаем рассматривать решение и так, идя по ветке 0, доходим до самого низа. Если накопленная ошибка у нас остается равной 1, то мы признаем решение успешным.
Возвращаемся наверх и идем по ветви 1. Так как она отличается от нашего последнего бита, то ошибок становится две, то есть данное решение нам не подходит.
Дальше пробегаем вторую ветку и переходим на вторую половину дерева. И итоге нам подойдут три значения: два из них с искажением в 1 бит:
Смысл в том, что когда ошибка достигает максимального значения, глубже по дереву спускаться уже не нужно. Ошибка может только расти, и если она достигла какого-то максимального значения, то дальше будет только хуже. В результате поиск начинает работать очень быстро, даже если у дескриптора 512 уровней. А при росте количества элементов скорость с какого-то момента просто превращается в константу и никуда не двигается.
Таблица, которая у меня получилась при сравнении дерева с линейным поиском:
Видим, что на той же базе в 1 млн изображений размер базы внезапно уменьшился на 3 ГБ. Почему так произошло? Потому что префиксные деревья изначально делают дедупликацию данных, и поиск одной ключевой точки вместо 40 секунд стал занимать всего 3,5 мс. А поиск одного изображения стал быстрее в десять тысяч раз!
Конечно, чтобы обрабатывать 150 тысяч изображений в день, обработка должна проходить за полсекунды. Но никто не мешает искать в префиксном дереве во множестве потоков — и тем самым увеличивать скорость. Первая версия префиксное дерева была реализована на PHP, и она так быстро работала за счет удачно подобранного алгоритма.
На мой взгляд, префиксные деревья — это очень недооцененная структура данных в современном мире. Те же индексы: если у вас какое-то значение закодировано строкой и в данных мало энтропии — префиксные деревья будут занимать гораздо меньше памяти, чем двоичные деревья, которые используются в современных реляционных базах данных. Когда я использовал в Postgres префиксные деревья для индексов, мне удавалось уменьшить размер индекса в среднем в два раза.
Префиксное дерево может давать еще такой интересный эффект как рекомендации. Поскольку мы можем искать с какой-то допустимой ошибкой, а у вас, допустим, есть миллиард товаров или каких-то объектов, чье качество кодируется битами — то вы можете поискать и предложить объект, очень похожий на тот, что изначально искал пользователь.
Перейдём от теории к практике.
Реализация проекта
Хранение изображений
В первой итерации я просто складывал файлы на диск. Но когда картинок стало несколько миллионов, то выяснилось, что бэкапить такие данные, переносить и анализировать очень сложно. Поэтому в итоге была собрана такая схема:
NGINX принимает запрос и пересылает его демону, написанному на ReactPHP. Демон с помощью данных, хранящихся в реляционных базах данных, понимает: что это за картинка, на каком сервере она хранится, в каком устройстве, с каким смещением и какого объема. Эта информация передается нужному серверу, который просто читает с блочного устройства нужное количество байт с нужным смещением.
Это дает очень большой прирост к производительности, особенно на задачах массовых данных, когда одновременно надо делать бэкап, пересчитывать все картинки для индекса или переносить их. Но даже одно чтение может проходить в десять раз быстрее.
Это решение пришло мне из системы резервного копирования Bacula. Как следствие, я понял, что ленточные носители очень удобно бэкапить, и при современных ценах на жесткие диски это вышло очень недорого (напомню, что проект был личным, много делалось на энтузиазме, поэтому позволить себе какие-то дорогие решения мы не могли).
Как выглядел кластер
При поиске одной картинки в префиксном дереве происходит примерно 10 тысяч операций чтения памяти для одной ключевой точки, то есть операций чтений из разных случайных блоков. Поэтому данные обязательно должны храниться в памяти, с диска читать такое количество данных невозможно. Но, конечно, рано или поздно заканчивается память. Где-то на 30 миллионах, заняв все 128 ГБ оперативной памяти, нам пришлось переходить к шардированию:
Для данного алгоритма это не проблема, но все ключевые точки одного изображения должны лежать в одном блоке. После чего данные разбиваются по разным блокам. Каждый блок может обслуживаться своим отдельным сервером или группой серверов. Всё это позволяет достигнуть отказоустойчивости и линейно повышать скорость поиска.
Как происходит поиск
Конвейер поиска выглядит достаточно просто. Есть некоторый PHP-демон, который успешно живет месяцами. Он принимает на вход картинку и отправляет ее на кластер, который выделяет ее ключевые точки. Так как картинки могут приходить очень большими пачками, то их нужно обрабатывать максимально быстро — поэтому этим занималось несколько узлов.
Дальше полученные ключевые точки отправлялись во все блоки, и один из обслуживающих блок серверов брал на себя задачу найти id всех похожих изображений и отправить их мастеру. Который компилировал эту информацию:
Вставка работала примерно также, но с единственным различием: запись происходила через демон ReactPHP и только в один блок, в зависимости от внутренней логики. У меня использовалась round-robin:
Результаты
Нам удалось достичь поиска 95 перцентиля (95% изображений) за 8 секунд. Но при большом количестве потоков это работало очень быстро. Кластер спокойно искал 200 фотографий в день, что позволяло с запасом решать наши задачи.
Всего у нас было 150 млн изображений на 18 ТБ, и в пики их обслуживало 9 узлов. Почему я говорю про пики? По мере того как мы узнавали что-то новое, нам удавалось оптимизировать расходы и оборудование. В конце у нас был узел, который имел на борту 768 ГБ оперативной памяти. Он держал почти весь индекс, который составлял 790 ГБ, но его стоимость была сопоставима с топовым игровым компьютером. Никаких заоблачных цен.
К сожалению, в прошлом году проект был закрыт, но я совершенно не жалею, что работал над ним. Потому что до этого я жил в некой парадигме, что PHP подходит только для сайтов. Как только вам нужно что-то серьезное или большое, то нужно использовать любой другой язык. Мой взгляд изменился, потому что почти всё в этом проекте было написано на PHP. Только один маленький кусочек был переписан на С — мультипоточность для дерева.
Я получил огромный опыт работы с распределенными вычислениями. Этот опыт до сих пор мне полезен. Я активно ищу и помогаю решить задачи в Badoo, связанные именно с этим, поскольку у нас очень большая инфраструктура. Пока я этим занимался, я много читал про базы данных, и многие мои решения были почерпнуты из документации Postgres и MySQL. У меня теперь есть уверенность в том, что почти любую задачу можно решить, если подойти к ней системно и выделить для этого достаточно времени.
К тому же, я очень интересно провел время, потому что люблю программировать. Мне интересно решать очень сложные задачи. Эта задача, наверное, была одной из самых сложных. Причем не только технических: непросто было не опускать руки каждый раз, когда я натыкался на новые проблемы и думал, что теперь точно конец, ничего больше нельзя сделать.
Что я хочу сказать напоследок? Хочу пожелать всем найти свой пет-проект, который так же как и меня в свое время, увлечет на пару лет и поможет круто прокачаться.
Конференция PHP Russia 2022 — отличное место, где можно рассказать о своём опыте сообществу. Она пройдет 12 и 13 сентября в Москве, в Radisson SAS Славянская. В центре внимания: развитие экосистемы (сам PHP, стандарты, фреймворки, библиотеки, OpenSource); опыт крупных компаний для построения на PHP сложных проектов и лучшие практики. И, конечно, темы повседневной разработки.
До 25 мая идет прием заявок на выступления. Оплачиваются расходы на дорогу и проживание спикеров. Все подробности на сайте.