Путь к оптимизации поиска изображений миллиардного масштаба (1/2)
Yupoo Picture Manager обслуживает десятки миллионов пользователей и управляет десятками миллиардов изображений. По мере того как пользовательская галерея становится всё больше, у Yupoo возникает срочная бизнес-потребность в решении, которое может быстро находить изображение. Другими словами, когда пользователь загружает изображение, система должна находить его оригинальное изображение и похожие изображения в галерее. Разработка сервиса поиска по изображению предоставляет эффективный подход к этой проблеме.
Сервис поиска по изображению прошёл две эволюции:
- Началось первое техническое исследование в начале 2019 года, и система первого поколения была запущена в марте и апреле 2019 года;
- Началось исследование плана обновления в начале 2020 года, и в апреле 2020 года началось общее обновление до системы второго поколения.
В этой статье описаны выбор технологий и базовые принципы, лежащие в основе двух поколений системы поиска по изображению, на основе моего собственного опыта работы над этим проектом.
Обзор
Что такое изображение?
Прежде чем работать с изображениями, мы должны знать, что такое изображение.
Ответ состоит в том, что изображение — это набор пикселей.
Например, часть в красной рамке на этом изображении фактически представляет собой ряд пикселей.
Рисунок 1.
Предположим, что часть в красной рамке является изображением, тогда каждый независимый маленький квадрат в изображении — это пиксель, базовая единица информации. Тогда размер изображения составляет 11 x 11 px.
Рисунок 2.
Математическое представление изображений
Каждое изображение может быть представлено матрицей. Каждый пиксель в изображении соответствует элементу в матрице.
Бинарные изображения
Пиксели бинарного изображения бывают либо чёрными, либо белыми, поэтому каждый пиксель может быть представлен 0 или 1. Например, матричное представление бинарного изображения 4 * 4 выглядит так:
0 1 0 1
1 0 0 0
1 1 1 0
0 0 1 0
RGB-изображения
Три основных цвета (красный, зелёный и синий) можно смешивать для получения любого цвета. Для RGB-изображений каждый пиксель содержит базовую информацию трёх RGB-каналов. Аналогично, если каждый канал использует 8-битное число (в 256 уровнях) для представления своей шкалы серого, то математическое представление пикселя выглядит так:
([0 .. 255], [0 .. 255], [0 .. 255])
Возьмём в качестве примера RGB-изображение 4 * 4:
Рисунок 3.
Суть обработки изображений заключается в обработке этих пиксельных матриц.
Техническая проблема поиска по изображению
Если вы ищете оригинальное изображение, то есть изображение с точно такими же пикселями, вы можете напрямую сравнить их значения MD5. Однако изображения, загруженные в Интернет, часто сжимаются или снабжаются водяными знаками. Даже небольшое изменение в изображении может создать другой результат MD5. Пока существует несоответствие в пикселях, найти оригинальное изображение невозможно.
Для системы поиска по изображению мы хотим искать изображения с похожим содержимым. Тогда нам нужно решить две основные проблемы:
- Представить или абстрагировать изображение в формате данных, который может быть обработан компьютером.
- Данные должны быть сопоставимыми для вычисления.
Более конкретно, нам нужны следующие функции:
- Извлечение признаков изображения.
- Вычисление признаков (вычисление сходства).
Система поиска по изображению первого поколения
Извлечение признаков — абстрагирование изображения
Система поиска по изображению первого поколения использует алгоритм Perceptual hash или pHash для извлечения признаков. Каковы основы этого алгоритма?
Поиск изображений первого поколения.
Как показано на рисунке выше, алгоритм pHash выполняет ряд преобразований над изображением, чтобы получить хеш-значение. В процессе преобразования алгоритм непрерывно абстрагирует изображения, тем самым приближая результаты похожих изображений друг к другу.
Вычисление признаков — вычисление сходства
Как вычислить сходство между значениями pHash двух изображений? Ответ — использовать расстояние Хэмминга. Чем меньше расстояние Хэмминга, тем более схоже содержимое изображений.
Что такое расстояние Хэмминга? Это количество различающихся битов.
Например,
Значение 1： 0 1 0 1 0
Значение 2： 0 0 0 1 1
В приведенных выше двух значениях есть два различающихся бита, поэтому расстояние Хэмминга между ними равно 2.
Теперь мы знаем принцип вычисления сходства. Следующий вопрос: как вычислять расстояния Хэмминга для данных масштаба 100 миллионов из изображений масштаба 100 миллионов? Короче говоря, как искать похожие изображения?
На ранней стадии проекта я не нашел удовлетворительного инструмента (или вычислительного движка), который мог бы быстро вычислять расстояние Хэмминга. Поэтому я изменил свой план.
Моя идея в том, что если расстояние Хэмминга двух значений pHash мало, то я могу разрезать значения pHash, и соответствующие небольшие части, скорее всего, будут равны.
Например:
Значение 1： 8 a 0 3 0 3 f 6
Значение 2： 8 a 0 3 0 3 d 8
Мы делим два приведенных выше значения на восемь сегментов, и значения шести сегментов полностью совпадают. Можно сделать вывод, что их расстояние Хэмминга близко, а значит, эти два изображения похожи.
После преобразования можно увидеть, что проблема вычисления расстояния Хэмминга превратилась в проблему сопоставления на равенство. Если я делю каждое значение pHash на восемь сегментов, то, пока существует более пяти сегментов с полностью одинаковыми значениями, два значения pHash являются похожими.
Таким образом, решить сопоставление на равенство очень просто. Мы можем использовать классическую фильтрацию традиционной системы баз данных.
Конечно, я использую multi-term matching и указываю степень совпадения с помощью minimum_should_match в ElasticSearch (в этой статье не рассматривается принцип ES, вы можете изучить его самостоятельно).
Почему мы выбираем ElasticSearch? Во-первых, он предоставляет вышеупомянутую функцию поиска. Во-вторых, сам проект image manager использует ES для предоставления функции полнотекстового поиска, и использование существующих ресурсов очень экономично.
Краткое описание системы первого поколения
Система поиска по изображению первого поколения выбирает решение pHash + ElasticSearch, которое имеет следующие особенности:
- Алгоритм pHash прост в использовании и может противостоять определенной степени сжатия, водяному знаку и шуму.
- ElasticSearch использует существующие ресурсы проекта, не добавляя дополнительных затрат на поиск.
Но ограничение этой системы очевидно: алгоритм pHash является абстрактным представлением всего изображения. Как только мы нарушаем целостность изображения, например добавляем черную рамку к исходному изображению, становится почти невозможно судить о сходстве между оригиналом и другими изображениями.
Чтобы преодолеть такие ограничения, появилась система поиска изображений второго поколения с совершенно иной базовой технологией.
Эта статья написана rifewang, пользователем Milvus и software engineer в UPYUN. Если вам понравилась эта статья, заходите поздороваться! https://github.com/rifewang
Читать далее
How to Install and Run OpenClaw (Previously Clawdbot/Moltbot) on Mac
Turn your Mac into an AI gateway for WhatsApp, Telegram, Discord, iMessage, and more — in under 5 minutes.
Zilliz Cloud BYOC Now Available Across AWS, GCP, and Azure
Zilliz Cloud BYOC is now generally available on all three major clouds. Deploy fully managed vector search in your own AWS, GCP, or Azure account — your data never leaves your VPC.
Selecting the Right ETL Tools for Unstructured Data to Prepare for AI
Learn the right ETL tools for unstructured data to power AI. Explore key challenges, tool comparisons, and integrations with Milvus for vector search.